Not logged in
Log in now
Create an account
Subscribe to LWN
LWN.net Weekly Edition for May 23, 2013
An "enum" for Python 3
An unexpected perf feature
LWN.net Weekly Edition for May 16, 2013
A look at the PyPy 2.0 release
bogus random entropy sources
Posted Oct 5, 2010 6:03 UTC (Tue) by butlerm (subscriber, #13312)
What does that matter, if they ultimately connect to underlying physical devices which are not?
Posted Oct 5, 2010 6:42 UTC (Tue) by smurf (subscriber, #17840)
Posted Oct 6, 2010 17:01 UTC (Wed) by drag (subscriber, #31333)
Posted Oct 5, 2010 10:25 UTC (Tue) by nix (subscriber, #2304)
Posted Oct 5, 2010 15:51 UTC (Tue) by jzbiciak (✭ supporter ✭, #5246)
I don't understand why more processors don't include a proper hardware random number generator. It's a classic case of something that is significantly easier to do in hardware, I'd think.
I mean, sure, you could try to derive a few bits of entropy here, an few bits there from what is otherwise a deterministic system. It's maddeningly frustrating, though, and you have to apply new thought and new techniques every time your system assumptions change. Your case is just such a case, and it sounds like you just punted to a dedicated hardware solution.
Modern CPUs have accelerators for all sorts of things as standard equipment. Why not random numbers? We spend countless millions of transistors on ever larger caches and datapaths. Surely they could spare a few for a really high quality true random number generator.
Posted Oct 5, 2010 17:09 UTC (Tue) by strappe (guest, #53440)
Posted Oct 5, 2010 17:22 UTC (Tue) by jzbiciak (✭ supporter ✭, #5246)
Posted Oct 5, 2010 18:24 UTC (Tue) by ejr (subscriber, #51652)
Posted Oct 5, 2010 19:10 UTC (Tue) by jzbiciak (✭ supporter ✭, #5246)
VIA's approach on the C3 doesn't sound too unwieldy. This white paper analyzing the generator's output makes for an informative read. The punch line is that it looks like a pretty reasonable source of entropy as long as you do appropriate post processing. The random numbers it generates aren't caveat free, but they're heckuva lot better than disk seeks and keypresses.
Posted Oct 6, 2010 8:40 UTC (Wed) by pcampe (guest, #28223)
Posted Oct 6, 2010 13:56 UTC (Wed) by jzbiciak (✭ supporter ✭, #5246)
Probably because they didn't have a time machine. ;-) The document you reference was written this year. The white paper I reference was written in 2003. And if you meant Rev 1, that didn't come out until 2008.
Maybe you meant the original 800-22? That one came out in 2001.
(Dates came from here.)
Posted Oct 5, 2010 18:26 UTC (Tue) by mpr22 (subscriber, #60784)
Posted Oct 5, 2010 18:46 UTC (Tue) by jzbiciak (✭ supporter ✭, #5246)
If anything, it would make it harder for them to export the chips outside of the United States without getting special approval from the Feds. Cryptographic hardware is a munition under ITAR.
I remember there was some concern awhile back when we put our AES implementation in ROM on some devices, because it calculated AES "too quickly" for some peoples' taste. We ended up making that part of the ROM protected (ie. not user accessible) so that it was only used for boot authentication.
Posted Oct 6, 2010 11:27 UTC (Wed) by intgr (subscriber, #39733)
The solution has always been obvious to cryptographers. Use a solid cryptographical pseudorandom RNG; as long as there is _some_ truly random data in its input -- 128 or so bits worth -- the output will always be irreversible. As long as this randomness exists, it doesn't matter that the attacker can predict all other input.
In fact, hardware RNGs should _never_ be used directly, because there may be manufacturing flaws or deliberate sabotage. And unlike deterministic algorithms like AES, non-deterministic hardware RNG sources are almost impossible to verify completely. Also it's really quite easy to replace the hw RNG with a deterministic PRNG that passes all randomness tests, yet whose output is entirely predictable to its designer.
So at most, the hw RNG is just one of several randomness sources on any system. As such cryptographers in general don't consider it worthwhile -- only on diskless embedded systems where there really aren't any entropy sources.
Unfortunately /dev/random is a poor legacy choice in Linux that goes against this concept.
Posted Oct 7, 2010 12:24 UTC (Thu) by nix (subscriber, #2304)
Posted Oct 7, 2010 12:48 UTC (Thu) by intgr (subscriber, #39733)
But in general, virtual machine disk I/O still reaches a physical disk sooner or later, so entropy can be successfully gathered from interrupt timings. In some virtualization scenarios, you wouldn't want the VM to access host-CPU-specific features anyway.
Posted Oct 5, 2010 19:01 UTC (Tue) by patrick_g (subscriber, #44470)
Posted Oct 6, 2010 3:36 UTC (Wed) by PaulWay (✭ supporter ✭, #45600)
Posted Oct 6, 2010 3:47 UTC (Wed) by jzbiciak (✭ supporter ✭, #5246)
Well, /dev/urandom doesn't block when the kernel entropy pool runs out. The hardware crypto acceleration may've been getting used, but that's orthogonal to the question of gathering entropy.
Posted Oct 6, 2010 19:34 UTC (Wed) by paulj (subscriber, #341)
Posted Oct 5, 2010 21:58 UTC (Tue) by nowster (subscriber, #67)
It's actually a hard problem to provide a cheap reliable hardware random number generator. If you look at the effort that a device like Simtec's Entropy Key takes to ensure that each chunk of randomness it delivers is truly random, you'll see why a random number generator is not something that a CPU designer should drop on a spare corner of a CPU die last thing on a Friday afternoon. Semiconductor junction noise generators can be affected by environmental influences: an RNG on a CPU die running hot might have a bias compared with the same one when the CPU is idle and cooler.
Posted Oct 6, 2010 3:51 UTC (Wed) by jzbiciak (✭ supporter ✭, #5246)
I linked this whitepaper above on the technique VIA used on its C3. They used multiple free-running oscillators to gather entropy. The resulting output varies in quality, from 0.75 to 0.99 bits of entropy per output bit, depending on the decimation factor used and whether or not you enable von Neumann whitening.
Given that it generates entropy in the megabits/second range, this is several orders better than you can get from hard disk seeks and user keystrokes, even if you have to throw most of the numbers away. And, given the high apparent entropy of the raw bits, you don't really need to throw many away at all.
Posted Oct 7, 2010 12:28 UTC (Thu) by nix (subscriber, #2304)
Posted Feb 6, 2012 21:33 UTC (Mon) by tconnors (guest, #60528)
Because random number generators are only used for cryptography, and only terrorists use cryptography. Are you a terrorist?
Posted Feb 6, 2012 21:40 UTC (Mon) by dlang (✭ supporter ✭, #313)
Posted Feb 7, 2012 7:50 UTC (Tue) by cladisch (✭ supporter ✭, #50193)
> Business Justification:
> Core cryptographic functions are used in Windows to provide platform integrity as well as protection of user data.
(note the priorities)
In completely unrelated news, all recent AMD and Intel processors support AES-NI, and Intel has announced that Ivy Bridge processors will have a RNG.
Posted Oct 7, 2010 14:34 UTC (Thu) by BenHutchings (subscriber, #37955)
Getting more entropy
Posted Oct 10, 2010 11:55 UTC (Sun) by kleptog (subscriber, #1183)
The point is that while the interrupt is predictable, between the time that the interrupt fires and the driver finally gets run you have cache misses at various levels, PCI bus transfers, DRAM refresh cycles and even just hyperthreading making things very unpredictable. Conclusion: if there's predictability here, I couldn't find it (there's a toolkit for estimating randomness, it concluded that the output was indistinguishable from real random data).
The basic idea was to just use the last few bits of the cycle counter, don't worry about the high order bits. The last bit was enough, but even taking the last four bits didn't show any patterns. It might be worth making such a driver for the purpose of giving otherwise entropy starved machines something to work with. I imagine within VMs the cycle counter becomes even more variable, due to contention with things outside the VM.
Posted Oct 10, 2010 21:56 UTC (Sun) by man_ls (subscriber, #15091)
Copyright © 2013, Eklektix, Inc.
Comments and public postings are copyrighted by their creators.
Linux is a registered trademark of Linus Torvalds