bogus random entropy sources

Posted Oct 5, 2010 5:24 UTC (Tue) by shemminger (subscriber, #5739)
In reply to: Solid-state storage devices and the block layer by nix
Parent article: Solid-state storage devices and the block layer

Actually many types of devices also bogusly report that they provide
entropy when they do not. For example, Xen drivers are purely virtual
and therefore deterministic.

bogus random entropy sources

Posted Oct 5, 2010 6:03 UTC (Tue) by butlerm (subscriber, #13312) [Link] (2 responses)

"For example, Xen drivers are purely virtual and therefore deterministic."

What does that matter, if they ultimately connect to underlying physical devices which are not?

bogus random entropy sources

Posted Oct 5, 2010 6:42 UTC (Tue) by smurf (subscriber, #17840) [Link] (1 responses)

_If_. They might not.

bogus random entropy sources

Posted Oct 6, 2010 17:01 UTC (Wed) by drag (guest, #31333) [Link]

I know that I have had problems with ssh hanging on new nodes on xen due lack of entropy. But I think this is no longer a problem.

bogus random entropy sources

Posted Oct 5, 2010 10:25 UTC (Tue) by nix (subscriber, #2304) [Link] (25 responses)

And many devices which often do provide entropy (e.g. the network) were specified to never provide any, because an attacker can sometimes control *some* of the packets on it. I never understood that, and now my headless and virtual systems have next to no entropy at all (or did, until I got an entropy key, and now I don't care where the kernel gets its entropy sources from :) )

bogus random entropy sources

Posted Oct 5, 2010 15:51 UTC (Tue) by jzbiciak (guest, #5246) [Link] (21 responses)

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.

bogus random entropy sources

Posted Oct 5, 2010 17:09 UTC (Tue) by strappe (guest, #53440) [Link] (10 responses)

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 (guest, #5246) [Link] (9 responses)

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] (3 responses)

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 (guest, #5246) [Link] (2 responses)

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] (1 responses)

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 (guest, #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] (1 responses)

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 (guest, #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] (2 responses)

> 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] (1 responses)

"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] (3 responses)

>>> 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 (guest, #45600) [Link] (2 responses)

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 (guest, #5246) [Link] (1 responses)

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] (2 responses)

> 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 (guest, #5246) [Link] (1 responses)

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] (2 responses)

> 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 (guest, #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:
> 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.

bogus random entropy sources

Posted Oct 7, 2010 14:34 UTC (Thu) by BenHutchings (subscriber, #37955) [Link]

Most network controllers now implement interrupt moderation (deferring interrupts so that multiple packets can be handled at once). With a high enough packet rate, they will interrupt at regular and predictable intervals.

Getting more entropy

Posted Oct 10, 2010 11:55 UTC (Sun) by kleptog (subscriber, #1183) [Link] (1 responses)

A while back just for the fun of it I wrote a kernel driver whose goal was to extract entropy from the timer interrupt. After all, if anything is predictable, then it'd have to be the timer interrupt.

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.

Getting more entropy

Posted Oct 10, 2010 21:56 UTC (Sun) by man_ls (guest, #15091) [Link]

I guess that the problem is to prove that an attacker cannot influence the timers so that the result is predictable. For example a guy on a different VM doing odd things with the same CPU. As it is hard to prove a negative statement of this kind, then people may tend to distrust such a source of entropy, even if it sounds really interesting.