Weak Apple PRNG Threatens iOS Exploit Mitigations

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.'"

Comments

all PRNGs are deterministic

[YesIAmAScript]

So "this one is deterministic" seems like a weak complaint.

This is essentially what makes them PRNGs instead of RNGs.

Re:all PRNGs are deterministic

[petermgreen]

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:all PRNGs are deterministic

[Jmc23]

Don't confuse the colloquial term 'random', with the cryptographic term 'random', and the real definition of 'random'.

This is the problem with english.

Seems it would be easy to gather entropy..

[Red_Chaos1]

..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:Seems it would be easy to gather entropy..

[Shoten]

..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 still) the phone won't even boot. PLUS you've now had to build all this functionality just to query the gyro/accelerometer into your boot-level code, along with the entropy analysis. At some point, you need to back off from packing lots of stuff into what is effectively the BIOS.

The PRNG in iOS plays a major role in everything, starting with the boot chain. So it's a bit of a challenge.

Re:Why do we have all these custom PRNGs?

[Anrego]

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.

Not responsible disclosed

[Trillan]

"Mandt said he did not disclose the issue to Apple"

We really need to stop paying people — directly or indirectly — for irresponsible disclosure.

Re:Not responsible disclosed

[TechyImmigrant]

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:Not responsible disclosed

[DarkOx]

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:Not responsible disclosed

[Trillan]

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 overrun in one of the image decoders; I don't even remember which, and the final one in the DMG handling), I wasn't at all happy with how Apple handled them. I received no email until a couple weeks later when they asked me how I'd like credit. They got patched in the next version of the OS, but in both cases I was left with several weeks of wondering if they'd even read my bug report. The design flaw was easy for the user to workaround (you just had to make sure to remove insecure apps from your Time Machine backup), so I mentioned the workaround a few days after reporting it.

But I can't imagine not at least telling Apple. In fact, one of the bugs I reported was a longstanding bug I found documented in public. I was just the first one to report it to Apple. It got fixed two weeks after I reported it. I just think it's absurd that we accept the bystander effect when it comes to computer security.

(I originally wrote this reply having forgotten of one of the issues I reported, so if there's anything left that implies only two that's why.)

Re:Not responsible disclosed

[TechyImmigrant]

More like replacing ad-hoc PRNGs with a standard's compliant ones that enjoys some consensus amongst cryptographers that it's fit for purpose.

Repeat repeat repeat

[Threni]

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.

Re:Why do we have all these custom PRNGs?

[DigitAl56K]

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:Why do we have all these custom PRNGs?

[Anonymous Coward]

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.

PRNG was outsourced

[ArhcAngel]

Apple didn't want another security embarrassment so they asked the NSA to supply the most secure PRNG they had.

Re:Why do we have all these custom PRNGs?

[DigitAl56K]

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 that it's insecure.

The only problem I see is where you draw your entropy from if you need to mix in something truly random.

Re:Why do we have all these custom PRNGs?

[TechyImmigrant]

>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:Why do we have all these custom PRNGs?

[INT_QRK]

spot on...specifically FIPS Pub 140-2 Annex C (draft) "Approved Random Number Generators" which can be found at http://csrc.nist.gov/publicati...

Re:Why do we have all these custom PRNGs?

[INT_QRK]

Which, by the way says at the bottom of page 1...wait for it..."There are no FIPS Approved nondeterministic random number generators."

Entropy Extraction on phones

[TechyImmigrant]

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.

Hardware

[Quila]

The A7 has a hardware random number generator in the Secure Enclave, This isn't used where available?

Re:Hardware

[TechyImmigrant]

>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.

The random numbers are to mitigate kernel exploits

[mbessey]

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: Laugh : "surprisingly"

[LordLimecat]

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:Why do we have all these custom PRNGs?

[cryptizard]

Good thing we just had that and it was called the SHA-3 competition.

Understanding PRNG

[shellster_dude]

When cryptographers say that a PRNG is deterministic (in a bad sense), they usually mean it violates one of the following rules (or similar):

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.