| |||||||||||||
bogus random entropy sourcesbogus random entropy sourcesPosted Oct 5, 2010 15:51 UTC (Tue) by jzbiciak (✭ supporter ✭, #5246)In reply to: bogus random entropy sources by nix Parent article: Solid-state storage devices and the block layer
Off-topic rant: 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.
(Log in to post comments)
bogus random entropy sources Posted Oct 5, 2010 17:09 UTC (Tue) by strappe (guest, #53440) [Link] All VIA x86-compatible processors since the C3 (introduced 2003?) have included a hardware random number generator based on quantum effects; it produces millions of random bits each second, and is accessible with a non-privileged instruction. AFAIK, their opcode choice is unused by either AMD or Intel, so those companies could implement similar functionality (an infinitesimal bit of silicon) and we would have a standard solution at least across the x86 architecture going forward.
bogus random entropy sources Posted Oct 5, 2010 17:22 UTC (Tue) by jzbiciak (✭ supporter ✭, #5246) [Link]
Yeah, I was aware of VIA's accelerator. It boggles me that Intel and AMD bothered to put AES acceleration on their chips without getting something more basic and generic like random numbers on there too. Is it a verification issue? What's holding them back?
bogus random entropy sources Posted Oct 5, 2010 18:24 UTC (Tue) by ejr (subscriber, #51652) [Link]
It's not as easy as it seems. You can generate random bits, but they are highly skewed, with different skews depending on the temperature, etc. You need to extract a more regular randomness from them, and extractors can require a good bit of space. The extractors I know (theory, not actual architecture) also must be running continually, sucking power.
bogus random entropy sources Posted Oct 5, 2010 19:10 UTC (Tue) by jzbiciak (✭ supporter ✭, #5246) [Link] 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.
bogus random entropy sources Posted Oct 6, 2010 8:40 UTC (Wed) by pcampe (guest, #28223) [Link]
I don't understand why they didn't follow the guidelines in NIST Standard 800-22 (rev 1a), "A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications".
bogus random entropy sources Posted Oct 6, 2010 13:56 UTC (Wed) by jzbiciak (✭ supporter ✭, #5246) [Link] 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.)
bogus random entropy sources Posted Oct 5, 2010 18:26 UTC (Tue) by mpr22 (subscriber, #60784) [Link] The AES accelerator probably lets them tick a required-feature box for some government programme or other.
bogus random entropy sources Posted Oct 5, 2010 18:46 UTC (Tue) by jzbiciak (✭ supporter ✭, #5246) [Link] 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.
bogus random entropy sources Posted Oct 6, 2010 11:27 UTC (Wed) by intgr (subscriber, #39733) [Link]
> without getting something more basic and generic like random numbers on there too.
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.
bogus random entropy sources Posted Oct 7, 2010 12:24 UTC (Thu) by nix (subscriber, #2304) [Link]
"Diskless embedded systems" of course includes "all virtual machines". So there are a lot of them.
bogus random entropy sources Posted Oct 7, 2010 12:48 UTC (Thu) by intgr (subscriber, #39733) [Link]
For virtual machines you already have a paravirtual RNG device called 'virtio-rng' (CONFIG_HW_RANDOM_VIRTIO).
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.
bogus random entropy sources Posted Oct 5, 2010 19:01 UTC (Tue) by patrick_g (subscriber, #44470) [Link] >>> 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 think Intel will is working on this. See these link : http://www.technologyreview.com/computing/25670/
bogus random entropy sources Posted Oct 6, 2010 3:36 UTC (Wed) by PaulWay (✭ supporter ✭, #45600) [Link]
Purely an anecdote, but the other day I had the occasion to use shred to shred two disks at once. The machine was a modern Intel Core Quad system, and the disks were writing at 60MBytes/sec with 3% CPU load. Since modern shred just writes a number of layers of pure random data from /dev/urandom, I have to assume that there was either hardware crypto or randomness generation going on there. Who knew?!
Have fun,
Paul
bogus random entropy sources Posted Oct 6, 2010 3:47 UTC (Wed) by jzbiciak (✭ supporter ✭, #5246) [Link] 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.
bogus random entropy sources Posted Oct 6, 2010 19:34 UTC (Wed) by paulj (subscriber, #341) [Link]
Hehe, so shred was using entropy collected from the disk controllers, collected from shred writing to disks..
bogus random entropy sources Posted Oct 5, 2010 21:58 UTC (Tue) by nowster (subscriber, #67) [Link]
> I don't understand why more processors don't include a proper hardware random number generator.
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.
bogus random entropy sources Posted Oct 6, 2010 3:51 UTC (Wed) by jzbiciak (✭ supporter ✭, #5246) [Link] 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.
bogus random entropy sources Posted Oct 7, 2010 12:28 UTC (Thu) by nix (subscriber, #2304) [Link]
From all accounts I've read, the entropy of the numbers derived from the C3's RNG hardware sucks rather badly, probably because there are so many sources of regular noise in a CPU that it's hard to stop some of them leaking in. The figures I've heard are *well* below 0.75, more like 0.4 if you're lucky. And IIRC the C3 doesn't bother to validate them either (certainly from the description in the whitepaper they don't), and because the pair of oscillators comprise a single system, if it breaks down or becomes coupled to something external you *also* cannot tell.
bogus random entropy sources Posted Feb 6, 2012 21:33 UTC (Mon) by tconnors (guest, #60528) [Link]
> 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.
Because random number generators are only used for cryptography, and only terrorists use cryptography. Are you a terrorist?
bogus random entropy sources Posted Feb 6, 2012 21:40 UTC (Mon) by dlang (✭ supporter ✭, #313) [Link]
some chips do have high quality random number generators built in.
bogus random entropy sources Posted Feb 7, 2012 7:50 UTC (Tue) by cladisch (✭ supporter ✭, #50193) [Link]
The Windows 8 Hardware Certification Requirements demand that "Connected Standby"-capable device (i.e., mobile ones) have encryption acceleration and a RNG.
> Business Justification:
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.
|
|||||||||||||