Weak Apple PRNG Threatens iOS Exploit Mitigations 143
Trailrunner7 writes "A revamped early random number generator in iOS 7 is weaker than its vulnerable predecessor and generates predictable outcomes. A researcher today at CanSecWest said an attacker could brute force the Early Random PRNG used by Apple in its mobile operating system to bypass a number of kernel exploit mitigations native to iOS. 'The Early Random PRNG in iOS 7 is surprisingly weak,' said Tarjei Mandt senior security researcher at Azimuth Security. 'The one in iOS 6 is better because this one is deterministic and trivial to brute force.' The Early Random PRNG is important to securing the mitigations used by the iOS kernel. 'All the mitigations deployed by the iOS kernel essentially depend on the robustness of the Early Random PRNG,' Mandt said. 'It must provide sufficient entropy and non-predictable output.'"
Why do we have all these custom PRNGs? (Score:2, Interesting)
Why don't we decide on a handful of strong PRNGs, and make every major OS use them exclusively, and in the case you really need something fast/psuedo-random you have to use a source/API explicitly named "insecure_rng".
That's both Android and iOS fallen victim to poor PRNGs in the last year..
Re: (Score:3, Interesting)
Who is going to do that... the cryptography police?
Crypto and security guys are an opinionated lot. Getting everyone to agree to some kind of standard is unlikely.
Re:Why do we have all these custom PRNGs? (Score:4, Insightful)
Crypto and security guys are an opinionated lot. Getting everyone to agree to some kind of standard is unlikely.
There are surely a set of criteria to be met in the design for a PRNG to be acceptable, a set of known attacks and weaknesses that the PRNG has to be resiliant to to some established degree, some minimum level of performance required (max ops per generation, average ops or ms per generation of n numbers on a certain CPU feature set), unencumbered by patents or full waiver provided. You put together some candidates, allow some window of time (e.g. a year) for everyone to poke holes in them provided all the known materials that would assist someone to make them fail the acceptance criteria. Whatever makes it through is your suite.
Re: (Score:3, Informative)
well, almost (Score:2)
That was for fast secure hashes, and not for psuedorandom numbers. They aren't really the exact same thing, are they?
Re: (Score:2)
Re: (Score:2)
But I think that's exactly why you don't roll your own. That would be a predictable sequence. I could make a rainbow table of sha1('1'), sha1('2') etc. up to 4 trillion, and then by sampling a few numbers from your stream I could very quickly identify the current counter value and the next sequences for ever. Total fail, and if the seed is the system time this is only a level of abstraction more difficult. (Chess & West, p. 398)
Re: (Score:2)
And I am not even a crypto expert! Well, this is a very long-winded way of saying that the GP "DigitAl56K" was probably right; that we do need a clearing-house of good software cryptographic random number generators.
Re: (Score:2)
Re: (Score:2)
There are well defined methods for evaluating randomness. The problem is that there is a speed/time tradeoff as you dictate the implementation of systems with more randomness. No one PRNG is appropriate in all cases.
Re: (Score:3, Informative)
Its called FIPS140-2. Among other things it requires that PRNG implementations are strong.
Sadly most people/companies/products do not require FIPS140-2 certification. If they did we wouldn't have weak PRNG implementations out there.
Re: (Score:2)
Whoops! NIST is an "Untrusted Organization"!
Re: (Score:3)
>Its called FIPS140-2. Among other things it requires that PRNG implementations are strong.
No. It required that a DRBG within a FIPS140-2 boundary, used in a FIPS140-2 function, be compliant with NIST SP800-90(A).
SP800-90A contains both secure and non-secure DRBGs.
Re: (Score:3)
Re:Why do we have all these custom PRNGs? (Score:4, Insightful)
Re: (Score:2)
That's because SP800-90B and C are still in draft form.
Weren't you at the NIST RNG Workshop helping to get them finished? Thought not.
Re: (Score:2)
I was the chubby guy at the front ranting about theoretical models.
Re: (Score:2)
Because the PRNG is used at a very low level; as such, it is unique to the hardware platform and the OS as well. You can't code it with a high-level language, as it even affects components of the boot process itself (in the case of iOS, that is...see Dallas de Atley's talk at BlackHat 2012 for some insight into this). So, you need separate PRNGs for the A4/A5/A6 line, the ARM, x86, ia64, etc. You can't just have one code library and use it across platforms, because you're using instruction sets that are
Re: (Score:3)
That doesn't make a lot of sense to me. If you define some performance criteria and the processors on which those criteria must be met, what's the problem? The operations would be the same, the instructions underlying those operations could be different. For any particular processor it could even be slightly inefficient. But at least it would be secure to an agreed upon/openly vetted standard. As I said, if you just want a fast/insecure PRNG, make one separately, and give it a very clear API name indicating
Re: (Score:2)
Why don't we decide on a handful of strong PRNGs, and make every major OS use them exclusively, ...
You do realize which US federal agency would almost certainly be involved in developing these, don't you?
Re: (Score:2)
They already did. They attend the meetings. They're open meetings, you can go can meet them and argue with them if you think their contributions suck.
Re: (Score:2)
Ususually it's not the prng itself but poor seeing that is the problem and seeding is very much an environement specific buisness.
Re: (Score:2)
You just identified the difference between /dev/random and /dev/urandom.
urandom is the 'good enough for everything except cryptography' RNG.
Re: (Score:2)
a source/API explicitly named "insecure_rng"
urandom is the 'good enough for everything except cryptography' RNG.
The complaint, as I understand it, is that the meaning of the u in urandom isn't explicit enough.
Re: (Score:2)
IMO there are a few problems
1: As you say lack of sufficient eduaction on what random and urandom do /dev/random is overly paranoid allowing the output to be blocked if it estimates there is less enropy coming in than going out. /dev/urandom is overly loose not blocking even if the system has never gathered enough entropy to give reasonablly secure randomness. What you really want for most crypto purposes is something that will wait for sufficient seed data
2: linux doesn't have a middle of the road option.
Re: (Score:2)
If you want a secure PRNG, use a decent seed source with whatever other entropy sources you want and use that to start a recursive hash loop, using the hash's output as your random number. Good hash functions have characteristics pretty close to a true RNG when used this way and many true RNGs use hash as an intermediate step to cancel input bias.
Because if somebody breaks THOSE ... (Score:2)
Why don't we decide on a handful of strong PRNGs, and make every major OS use them exclusively,
Maybe because if somebody then breaks one or more of THOSE they have a zero-day exploit for EVERYTHING.
While we're at it. why don't we standardize on an operating system, and version, and stop all this diversity? After all, if a committee comes up with a pick how can any individual or team invent anything better?
Genetic engineering is getting to the point that we can soon modify our children so they all have the
all PRNGs are deterministic (Score:4, Informative)
So "this one is deterministic" seems like a weak complaint.
This is essentially what makes them PRNGs instead of RNGs.
Re: (Score:2)
So "this one is deterministic" seems like a weak complaint.
This is essentially what makes them PRNGs instead of RNGs.
True...but that's by unavoidable effect, not by intent. The intention is to be as far from deterministic as possible...you can't help but be deterministic, as evinced by the classic "living in a state of sin" quote, but you can make it difficult for another person to predict that deterministic outcome. And apparently the PRNG fails, in this case. So the real goal is for a PRNG to have a very small value for the "P", so that the RNG part is bigger. (At least that's how I would explain it to a 5-year-old
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
please explain further.
I'm aware of the intel RNG that uses additional info (can't remember if it was the openbsd guys or freebsd; maybe linux but I seem to remember it was bsd that didn't trust the intel RNG and added extra sources of entropy).
I'd like to understand how adding more random sensor input can hurt randomness.
Re: (Score:2)
Multiple sensors in close proximity will just get you a more accurate picture of the energetic environment at that time. Whether or not this makes it harder to hack is a different story.
Re: (Score:2)
Randomness in sensor data surely exists. Take a recording with your computer's microphone or line-in port with maximum amplification and take the least significant bit of each sample. Unless you manage to get a recording where each and every sample is clipped (most won't be, even if you have clipping), the result is very random and absolutely not predictable.
Re: (Score:2)
Re: (Score:2)
>I'm aware of the intel RNG that uses additional info
No. It does not use 'additional info', personalization strings or derivation function. There are no external inputs when it's running. It's the simplest instantiation of an SP800-90A AES-CTR-DRBG possible.
Who told you it uses additional info? They were talking out of their arse.
Re: (Score:2)
Intel uses a phase noise amplifier to generate a random bit stream, passes that stream through a hash algorithm to cancel hardware bias and fill/refresh an entropy buffer, hashes parts of that buffer to produce the RNG output and that output also gets hashed back in the entropy buffer to provide a high-bandwidth RNG stream.
Basically, it is a low-bandwidth true hardware RNG (something like 1Mbps) continuously seeding a high-bandwidth PRNG to amplify its bandwidth.
Re: (Score:2)
The random number generator in the chips my employer makes consists of around 125 free-running ring oscillators fed into a 512-bit sha-1 engine with a feedback loop. There's a way for software to disable the ring oscillator input to test the deterministic operation of it for FIPS compliance testing. Each chip also has a unique number that is programmed in to seed it even if the ring oscillators are not input. The FIPS testing is fairly extensive from what I heard. They took many days worth of samples lookin
Re: (Score:2)
If you seed from 5 sources, and only one is truly random, you still have a good seed. This is why the linux folks try to use as many sources to seed urandom as possible; they posted on this recently regarding the intel CPU hardware RNG.
Re: (Score:3)
This is the problem with english.
you know, brownian motion, for the kids (Score:2)
Re: (Score:2)
I was not confusing the two. AFAIK we do have truly "random" sources, and thats what I was referring to.
I was also referring to the fact that the linux RNG uses multiple entropy sources-- including intel RdRand-- in order to address issues in any one of them. Theres a write-up here which indicates you CAN mix sources without losing entropy:
https://lkml.org/lkml/2013/9/1... [lkml.org]
More simply, if you XOR truly random source A with compromised source B to get seed C, an attacker could know all of the output of B, b
Re: (Score:2)
For crypto uses you need both deterministic PRNGs and non deterministic RNGs. You can compose a non deterministic RNG out of a PRNG an entropy source and an entropy extractor.
They have different uses. E.G. A secure PRNG can be used as a cipher. E.G. AES-CTR mode encryption is just XORing the output of a PRNG with the data.
A deterministic PRNG is a component function of larger systems. It is deterministic because that's what it is and what it needs to be.
Re: (Score:2)
So "this one is deterministic" seems like a weak complaint.
By your standards, this PRNG [dilbert.com] isn't so bad.
Re:all PRNGs are deterministic (Score:5, Informative)
For a CSPRNG* the primary aim is to make it computationally infeasable for an attacker to predict the output even if the attacker has an aribiterally long sample of the output and even if the attacker knows how much output has been requested from the prng since it started.
To do this places demands on both the prng itself (it must be computationally infeasible to reverse the operations done by the prng and hence determine it's internal state from an output sample) and on the seed data fed into the prng (it must be sufficiently unknown/unpredictable to the attacker that the attacker can't obtain the seed state through a combination of his knowlage of the state of the system and brute force checking of different seed values)
Afaict it is the latter where things usually go wrong.
* Cryptographically secure psuedo-random number generator.
Re: (Score:2)
This is true. Not something that can be said of most posts under this article.
What does Early mean? (Score:2)
Whats this "early" mean?
Seems it would be easy to gather entropy.. (Score:5, Insightful)
..on a smart phone like the iPhone. Use the gyros/accelerometers, make the user draw randomly on the screen, maybe use random info like wifi network names currently available, generate random info based on images on the phone, etc. etc. Plenty of data/means available to create the entropy needed.
Re: (Score:3)
..on a smart phone like the iPhone. Use the gyros/accelerometers, make the user draw randomly on the screen, maybe use random info like wifi network names currently available, generate random info based on images on the phone, etc. etc. Plenty of data/means available to create the entropy needed.
Easy, but not necessarily a good idea. Picture this threat case:
Attacker has iPhone they wish to compromise. Disassemble, remove gyro, replace with appropriate component (resistor, perhaps?) to generate a steady, predictable outcome. Random seed is no longer entropic, PRNG ends up following suit.
So, to counter that, you could do entropy analysis on the incoming entropy, right? Uh oh...then your iOS boot sequence consequentially develops a dependency: if the gyro doesn't function (or the phone is very st
Re: (Score:2)
Ironically, resistor thermal noise is probably a better source of entropy than the gyro would have been. Why does the boot process require random numbers, anyway?
The random numbers are to mitigate kernel exploits (Score:3)
Why does the boot process require random numbers, anyway?
They mention this in the article - one way to make a kernel harder to write an exploit for is to randomize the layout of memory somewhat, so system libraries, kernel tables, and the like are located in different places. Obviously if the "random" numbers are predictable, this makes those mitigation techniques less-useful.
Re: (Score:2)
If the attacker has control of the hardware, they've already won. Just ask the games console manufacturers.
Re: (Score:2)
That's not the job of a PRNG. Entropy gathering is something else.
Re: (Score:2)
This is the early PRNG that is used before the system is booted and the sensors are working. It is used for things like address space randomization.
Re: (Score:2)
..on a smart phone like the iPhone. Use the gyros/accelerometers, make the user draw randomly on the screen, maybe use random info like wifi network names currently available, generate random info based on images on the phone, etc. etc. Plenty of data/means available to create the entropy needed.
Wifi network names are not random, that's controlled by third parties.
It would be quite the attack, but in theory an attacker that could control the SSID's around the victim could influence the PRNG.
Not responsible disclosed (Score:4, Interesting)
"Mandt said he did not disclose the issue to Apple"
We really need to stop paying people — directly or indirectly — for irresponsible disclosure.
Re: (Score:2)
How is it irresponsible disclosure?
Apple might prefer someone disclosed it to them first, whereas some of Apple's users might like to know straight away that they're vulnerable. In either case there is the chance someone less scrupulous has identified the same problem and may use for nefarious purposes.
Open disclosure is only irresponsible depending on your point of view, just like private disclosure might be irresonsible depending on your point of view. There are researchers who will argue for both sides.
Re: (Score:3)
That and this disclosure does not immediately an exploit make. There are many steps between knowing the PRNG is weak, and being able use that in working exploit.
Re: (Score:2)
That's a good point, too. Disclosing a weakness is more reasonable than a ready made exploit.
Re: (Score:3)
Thanks for your reply. I've softened on this since making that comment. I think there's a huge grey area for responsible disclosure. A week ahead of time? A day ahead of time? I'd consider these fairly grey, but whatever. But I still think not disclosing it to Apple at all and relying on them picking it up through the grapevine is pretty irresponsible.
I've reported three security issues to Apple. While the issues I reported were relatively minor (one was a design flaw in Time Machine, the other a buffer ove
Re:Not responsible disclosed (Score:5, Insightful)
Bad PRNGs have jumped the shark. For a company like Apple to have a supposedly secure PRNG in their products and for them not to have had a group of security Nazis identify all the PRNGs in their products and make sure they're all good and fix them where not, it unconscionable.
In my company we systematically did exactly that. It's standard practice these days.
Re: (Score:1)
How is this comment not scored 5 yet? Page after page of drivel and misconceptions, and this comment nails it.
Re: (Score:2)
"Fixing a PRNG" if your primary business is not crypto seems like an incredibly bad idea.
Re: (Score:3)
More like replacing ad-hoc PRNGs with a standard's compliant ones that enjoys some consensus amongst cryptographers that it's fit for purpose.
Re: (Score:1)
It's not irresponsible to notify the vendor at the same time as everyone else. People need to take steps to secure themselves and chances are others (e.g. the NSA) already know about this and are exploiting it.
Besides which if you want people to disclose bugs in your products to you exclusively you should pay them a bounty. Otherwise don't expect them to work for free or agree to your irresponsible NDA, expect them to put the public good first instead.
Re: (Score:2)
It's left implied (I think) that he didn't notify the vendor at the same time as everyone else, just that the vendor noticed the public notification.
If I'm wrong and he explicitly looped Apple in, then I'd consider that responsible (or responsible enough, at any rate).
Re: (Score:2)
I've reported three security issues. Two of them were fixed in the next release — the third was fixed in the next release after that (but I reported it two days before the next release).
So I have to call bullshit. Report security issues through channels, they'll get fixed. Post them to your blog or on a forum, Apple will never see them.
Repeat repeat repeat (Score:2)
Please could you repeat some of the statements a few more times in the writeup. Focus especially on "mitigations" - you can never write that word too many times.
Why he's really complaining (Score:2)
Tarjei Mandt really hates Jonny Ives' new flat icons. Note that "iOS6 was teh better!" comment?
Re: (Score:2)
So do I. iOS 7 is a horrid interface.
Exploting a Weak Pr0ng for fun & profit (Score:2)
Wow, that'll be a great session title for the next BlackHat conference.
PRNG was outsourced (Score:5, Funny)
Told you so. (Score:2)
So while the tin-foil-hatters were all pointing their fingers at Intel, who provide a full cascade RNG that isn't weak, doesn't have a back door and has stood up to scrutiny [cryptography.com], they weren't paying attention to the OS vendors who were getting it wrong despite the hardware available to them.
Entropy Extraction on phones (Score:4, Informative)
The article incoherently addresses entropy extraction, not matters of PRNGs but the author doesn't appear to understand the difference.
However the 'issue' is still an issue. Predictable output is bad in this context.
What amazes me is when designers flap around looking for 'random looking' things in memory and interrupts to munch together to get entropic numbers when it's in a phone with a radio next to it which as directly sampling noise and is entirely capable of making it available to the OS for used in seeding PRNGs.
It's not just Apple. They all do it.
Re: (Score:2)
Re: (Score:2)
That's a chip design problem. Power on dependencies matter.
Hardware (Score:3)
The A7 has a hardware random number generator in the Secure Enclave, This isn't used where available?
Re: (Score:2)
Either way, the proof of a good (P)RNG is in statistical analysis of the output.
Re: (Score:3)
>Either way, the proof of a good (P)RNG is in statistical analysis of the output.
No. The proof of a PRNG is in mathematical analysis of the algorithm.
The proof of the implementation is in test vectors and known answer tests.
Obviously (Score:2)
Hypothesis not demonstrated nor peer reviewed. (Score:1)
The basis of Mandt's argument is that Apple used a Linear Congruent Generator to eliminate the time-based correlation issues from iOS6's use of the Mach's absolute time values. The LCG is based on information from four sources with 13 bits of output (the 3 LSB dropped). Because the outputs are subject to having repeated outputs over a period of time there is a chance that brute force method could be used to determine the PRNG output.
He didn't demonstrate that having four sources for the values were insuffi
Re: (Score:2)
No. You prove your extractor function is strong. If you don't do that you have nothing.
Dodis et al. proved [nyu.edu] that CBC-MAC is a strong extractor and that is what we use in our products as a result.
LCGs are not shown to be strong extractors to my knowledge. I can see how LCGs might fail completely if the input data isn't IID. Yuval Peres whiteners are in a similar state. There are proofs of its extraction properties, but only for IID data and you cannot get IID data out of the real world.
Re: (Score:2)
This isn't a fight between Mandt and Apple. This is Apple being expected to 'do the right thing'. Using an LCG for extraction isn't close to the right thing.
Re: (Score:2)
If they'd used one of the many extractors with proven properties, they would know exactly how strong it was.
Re: (Score:2)
To be fair, I tried googling "what is a good entropy extraction algorithm" and I got back a combination of nonsense and mathematical mumbo jumbo.
Maybe Bing would give better results but I would feel dirty trying.
Re: (Score:2)
A long period length does not make a good extractor.
Re: (Score:2)
No. I was pointing out that a PRNG isn't an entropy extractor and a PRNG with a long period still isn't an entropy extractor.
An entropy extractor has to throw out less data than it takes in in order to increase the per bit entropy. A PRNG does the opposite. It takes in a seed and throws out more data than the length of the seed.
Announcement from Apple (Score:2)
Why don't we ever see a demonstration? (Score:2)
Seems to me that there are all these stories of late about how 'flaw X' *could* be used to do 'bad thing y."
Why don't these clever researchers rarely if ever demonstrate the flaw in use, in a reproducible way?
"I will now demonstrate using the faulty random number generator to attack the kernel and I will do this Really Bad Thing."
Should be plenty of sources for entropy (Score:2)
Take a shot from each camera, sample each microphone for a few milliseconds, Sample the gyros and accelerometers for a few milliseconds. Sample the current battery voltage/charge state, Salt in the current time/date and last known location, along with the various readable serial numbers, SHA each of these sources and fold them into each other and SHA the result, and you should be good to go.
Once the device is booted, it can do a lengthy and more sophisticated RNG to make a seed that will be folded into the
Re: (Score:2)
Instead of SHAing each entropy source individually, I would simply concatenate all the entropy sources together and SHA that. It saves the hash initialization, finalization and intermediate "folding" steps.
Understanding PRNG (Score:3)
1) It should be realistically impossible for an outsider to determine or guess all the values that constitute a seed.
2) No matter how much of the "random stream" an attacker has seen, they should not be able to realistically determine the next value in the stream (without all the sources of entropy throughout the process).
3) Given the initial seed, an attacker should not be able to determine the random value at a point in the future because that value should constantly be affected by both new "entropy" inputs including the number of times, size, and amount of random data previously requested.
Re: (Score:2)
Do you have any evidence this was introduced in 7.0.6?
It was. Read on. (Score:2)
Now, was this a gift to the NSA, or to the Jailbreakers?
Re: (Score:1)
I didn't see that in the article. Can you point it out? (Seriously if this is true, I really want to know.)
Re: (Score:2)
Laugh : "surprisingly" (Score:2)
Re: Laugh : "surprisingly" (Score:5, Insightful)
Just because there are nefarious things going on doesnt mean that people have stopped making mistakes, or that the two are somehow mutually exclusive.
Yes, you should still want proof that this is malicious or subversive.
Re: (Score:2)
Yes, you should still want proof that this is malicious or subversive.
Want proof before doing what, exactly? There only needs to be a reasonable doubt about malicious, subversive or incompetent behavior by vendors of security products to justify writing those products off as untrustworthy and shunning them, at least until the doubt can be cleared. In the last year we have had a mountain of doubt dumped down on us thanks to the Snowden revelations.
Re: (Score:2)
Right, Smitty.