[Cryptography] Opening Discussion: Speculation on "BULLRUN"

[Jerry Leichter]

[This drifts from the thread topic; feel free to attach a different subject line to it]

On Sep 5, 2013, at 4:41 PM, Perry E. Metzger wrote:
> 3) I would not be surprised if random number generator problems in a
> variety of equipment and software were not a very obvious target,
> whether those problems were intentionally added or not.
Random number generators make for a very interesting target.  Getting decent amounts of entropy on conventional machines is very difficult.  Servers have almost no random variation in their environments; desktops somewhat more; modern laptops, yet more.  Virtualization - now extremely common on the server side - makes things even harder.  But even laptops don't have much.  So we're left trying to distill "enough" randomness for security - a process that's error-prone and difficult to check.

So ... along comes Intel with a nice offer:  Built-in randomness on their latest chips.  Directly accessible to virtual machines, solving the very difficult problems they pose.  The techniques used to generate that randomness are published.  But ... how could anyone outside a few chip designers at Intel possibly check that the algorithm wasn't, in some way, spiked?  For that matter, how could anyone really even check that the outputs of the hardware Get Random Value instruction were really generated by the published algorithm?

Randomness is particularly tricky because there's really no way to test for a spiked random number generator (unless it's badly spiked, of course).  Hell, every encryption algorithm is judged by its ability to generate streams of bits that are indistinguishable from random bits (unless you know the key).

Now, absolutely, this is speculation.  I know of no reason to believe that the NSA, or anyone else, has influenced the way Intel generates randomness; or that there is anything at all wrong with Intel's implementation.  But if you're looking for places an organization like the NSA would really love to insert itself - well, it's hard to pick a better one.

Interestingly, though, there's good news here as well.  While it's hard to get at sources of entropy in things like servers, we're all carrying computers with excellent sources of entropy in our pockets.  Smartphones have access to a great deal of environmental data - accelerometers, one or two cameras, one or two microphones, GPS, WiFi, and cell signal information (metadata, data, signal strength) - more every day.  This provides a wealth of entropy, and it's hard to see how anyone could successfully bias more than a small fraction of it.  Mix these together properly and you should be able to get extremely high quality random numbers.  Normally, we assume code on the server side is "better" and should take the major role in such tasks as providing randomness.  Given what we know now about the ability of certain agencies to influence what runs on servers, *in general*, we need to move trust away from them.  The case is particularly strong in the case of randomness.

Of course, there's a whole other layer of issue introduced by the heavily managed nature of phone software.
                                                        -- Jerry