| |||||||||||||
Russell: Sources of Randomness for UserspaceRussell: Sources of Randomness for UserspacePosted Mar 30, 2012 12:46 UTC (Fri) by man_ls (subscriber, #15091)In reply to: Russell: Sources of Randomness for Userspace by alankila Parent article: Russell: Sources of Randomness for Userspace
(Hypothetical answer: people simply are really paranoid about randomness of their random numbers. But is such paranoia justified?)I would say people are not paranoid enough, given the consequences. A bad random generator can easily go unnoticed and can cause real problems. How can I be sure that PHP's openssl_random_pseudo_bytes is really random? How can I be sure that my implementation is not removing randomness? A couple of examples. There was this incident a couple of months back, not to speak about Debian's fiasco with SSH keys.
(Log in to post comments)
Russell: Sources of Randomness for Userspace Posted Mar 30, 2012 16:13 UTC (Fri) by alankila (subscriber, #47141) [Link]
All of these problems seem to relate to the fact that people don't just read a bit of /dev/urandom and be happy. The reason why I don't recommend reading from /dev/random is the very low data rate. I have in memory an incident where I had to build ghostscript to not read image dithering data from /dev/random...
It seems to me that this ball should be just dumped into kernel's turf and require that urandom provide "industrial strength" random numbers at rates that make the thing usable for almost all applications.
My instincts say that random numbers *can't* be this hard. I think adding complexity to what should be simple is just making things worse.
True randomness Posted Mar 30, 2012 16:41 UTC (Fri) by man_ls (subscriber, #15091) [Link] Why, random numbers are incredibly complex. Try asking someone to give you a few random numbers and check them for patterns. Or just try to play rock-paper-scissors with the random strategy. I have won some of these rps simulators, and boy is it exhausting!How do you find random numbers in Nature? You can expect to find noise from many sources, but there are many different types of noise: white, brown, pink. Each one has its own characteristics; you would have to use a filter for each of them if you want good, old white noise, or you are losing entropy bits. Even with a source of white noise, you have to normalize it and remove any non-random components that may appear (either from the noise source or from your equipment). And even if you make sure that you are getting random values using all the tests you know, someone may come along and find a regularity you did not think of, and put your "random" source to shame. With pseudo-random number generators (which cause, as you will know, a state of sin) you can never be sure either. Sure, the period can be huge, but that only speaks about repeating values. The big question is again: what hidden regularities are there in any algorithm that we don't know about? /dev/urandom is a nice trick, but in fact you are only brushing the problem under the carpet: is the kernel's PRNG implementation good enough for you? Does it get entropy from any sources, or is it just going through the PRNG sequence? In fact it may be even worse than your own algorithm, since you may be trusting it to be secure (getting some entropy from somewhere) when in fact it is not. So, /dev/urandom is not good enough to be happy for cryptographic applications. And crypto is not so esoteric these days: any programmer worth their salt should be able to hash passwords (pun intended but not deployed). For me, haveged is a great concept because it should make /dev/urandom quite secure (and make you really happy), but I share drag's reservations about VMs.
True randomness Posted Mar 30, 2012 16:53 UTC (Fri) by alankila (subscriber, #47141) [Link]
While this all sounds appropriately cryptic,
dark and foreboding, it seems more relevant to ask if there are any practical attacks against urandom. It seems to me that the existing entropy could be used to fully replace urandom's seed several times per second.
True randomness Posted Mar 30, 2012 17:09 UTC (Fri) by man_ls (subscriber, #15091) [Link] See, the problem about randomness (and probably why you perceive my message as cryptic and foreboding) is that it can only be defined in the negative. The complete absence of patterns is basically impossible to prove; it can only be suspected.But I see you like your solutions simple and your answers straight. Your hypothesis is easy to test: $ cat /dev/randomand see how quickly it fills out. For me it is barely enough to reseed urandom (32 bytes) once a minute, while using it; if I leave it alone it seems to take quite longer. As to practical attacks against /dev/urandom: I hope that there are none because then I fear all my communications (and most in the world) would be vulnerable. But perhaps the NSA (or other sinister organizations) have a few of their own.
True randomness Posted Mar 31, 2012 16:47 UTC (Sat) by alankila (subscriber, #47141) [Link]
I just tested this. It seems that entropy collection takes very long time indeed. What a pity. Apparently there's just a kernel buffer that contains gathered entropy, and consuming that entropy allows me to see that it will be replenished rather slowly. So the statistic munin graphs me is not the rate of entropy generation, but merely the amount of available entropy.
Somehow this multi-gigahertz multi-core machine and all its myriad peripherals together are not harvested for more entropy than about 10 bits per second.
True randomness Posted Mar 31, 2012 16:52 UTC (Sat) by man_ls (subscriber, #15091) [Link] Right, that is where haveged should help. Whether it works well in virtualized machines remains to be seen.
True randomness Posted Mar 31, 2012 15:25 UTC (Sat) by man_ls (subscriber, #15091) [Link] While this all sounds appropriately cryptic, dark and foreboding,By the way, the foreboding part is not just theoretical. See precisely this week's security QotW: I believe that what the "top official" was referring to is attacks that focus on the implementation and bypass the encryption algorithm: side-channel attacks, attacks against the key generation systems (either exploiting bad random number generators or sloppy password creation habits) [...]Guess who employs thousands of cryptographers precisely to study these vulnerabilities. If the NSA had found a vulnerability in /dev/urandom (or ten) they would probably not publish them. "No known attacks" in cryptography seems to be a meager consolation, but in RNGs it is doubly so.
True randomness Posted Mar 31, 2012 2:18 UTC (Sat) by engla (guest, #47454) [Link]
Why not use an encrypted stream with a random key?
Read a relatively short key off /dev/random, then generate a stream of bytes by encrypting /dev/zero using that key. With AES-NI you get more than 300 MB/s using AES-256 and this *should* be good enough.
True randomness Posted Mar 31, 2012 8:58 UTC (Sat) by man_ls (subscriber, #15091) [Link] Because you would be leaking key material like crazy. Even if you used a correct stream mode you would transform the business of running a PRNG into a known plaintext problem, which is about the easiest in cryptography.
True randomness Posted Mar 31, 2012 13:15 UTC (Sat) by intgr (subscriber, #39733) [Link]
> Because you would be leaking key material like crazy.
> you would transform the business of running a PRNG into a known plaintext > problem, which is about the easiest in cryptography.
Sorry, but this is nonsense. In practice, every cryptographic protocol transmits some known (e.g. predictable) plaintext. If a cipher is vulnerable to a known plaintext attack at all, the cipher is simply broken.
In fact, a stream cipher (or a block cipher in CTR mode) in its most basic form, *is* a PRNG -- put a key in and it spits out a pseudorandom keystream. Most cryptographic PRNG systems (Yarrow, Fortuna, CryptGenRandom) do use a cipher this way to generate the output stream -- because ciphers have well-known security properties.
True randomness Posted Mar 31, 2012 14:29 UTC (Sat) by man_ls (subscriber, #15091) [Link] Sorry about the confusion, I should have refreshed these things before answering. (This goes to show how non-trivial this random number generation business is.) The original suggestion was to just encrypt /dev/zero which had all the faults described above, because it was not using an IV and key material would be leaking. Correct block cipher modes (not "stream modes" as I said) such as CRT use an initialization vector, use the result of one operation to XOR the next value, and use a counter instead of /dev/zero. All these things are done to avoid a plaintext attack.Once you take care of these issues, then you have a cryptographic PRNG system. Even so you have to pick a correct cipher to avoid a plaintext attack. And even with good ciphers apparently there are attacks based on the regularity of the input.
|
|||||||||||||