home | help | back | first | fref | pref | prev | next | nref | lref | last | post |
X-Original-To: cryptography@metzdowd.com Date: Fri, 08 Nov 2013 12:23:57 -0700 From: John Denker <jsd@av8n.com> To: RNG mlist <rng@lists.bitrot.info>, Cryptography <cryptography@metzdowd.com> In-Reply-To: <20131108014601.GU18713@localhost> Errors-To: cryptography-bounces+crypto.discuss=bloom-picayune.mit.edu@metzdowd.com -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 11/07/2013 06:46 PM, Nico Williams wrote: > I was only arguing that consuming n bits of PRNG output != lowering the > PRNG's "entropy" by n bits. That inequality is true and useful and well said. In a rational world that would be all there was to say about it. However, alas, there is more to the story, especially when we look at the context, which has to do with the Linux /dev/random and /dev/urandom. It turns out that: 1a) /dev/random is "supposed" to be a TRNG. 1b) However, it can operate as a PRNG in exceptional circumstances, when it is recovering from a compromise. 2a) /dev/urandom is some sort of hermaphroditic chimera. That is to say, I don't know what it is. Under a wide range of "typical" conditions it functions as a PRNG. 2b) However, it also tries to approximate a TRNG if it can. There are some heavy tradeoffs involved here, trading possibly-better performance under exceptional conditions against waste of CPU cycles and waste of entropy under normal conditions. This leaves us with more questions than answers. There are as-yet unanswered questions about the threat model, the cost of CPU cycles, the cost of obtaining raw entropy, etc. etc. etc. The answers will vary wildly from machine to machine. Because /dev/urandom is a hermaphroditic chimera, when somebody says they are reading thousands of bits with only 23 bits of entropy, that is not quite as insane as you might think. It's not a normal TRNG and it's not a normal PRNG, but it is what it is. There are millions upon millions of machines in the field that depend on it. It's difficult even to describe what's going on in /dev/urandom. Reading the code in drivers/char/random.c is painful, because it is aggressively misleading if not outright erroneous. There are places in the code where it is appropriately meticulous about accounting for entropy -- i.e. the actual real entropy -- and other places where it throws the word around recklessly. In particular the get_random_bytes() function that has been featured in this thread basically just calls extract_entropy() ... even though it is extracting bytes from a quasi-PRNG that under /normal/ conditions will not have any appreciable entropy. http://git.kernel.org/cgit/linux/kernel/git/tytso/random.git/tree/drivers/char/random.c?h=dev&#n1174 So the name "extract_entropy()" is quite misleading. The text of the printk warning mentions entropy, but we should not pay attention to that, because what it says is not what it means. It does not communicate the real meaning of the warning. The if-condition that governs the printk checks the initialization flag ... not the entropy content. Also note that this printk warning is in one person's "development" branch and has not been incorporated into any released version of the kernel. http://git.kernel.org/cgit/linux/kernel/git/tytso/random.git/log/?h=dev On 11/04/2013 06:16 PM, Theodore Ts'o wrote: > One of the reasons why we don't attempt to extract "true random bits" > and save them across a reboot is that even we had such bits that were > secure even if the underlying crypto primitives were compromised to a > fare-thee-well, once you write them to the file on the hard drive and > the OS gets shut down, there's no guarantee that an adversary might > not be able to read the bits while the OS is shut down. Even if you > don't do something truly stupid (such as leaving your laptop > unattended in a hotel room while visiting China), the risk of having > your "true random bits" stolen is probably higher than the > cryptographic primitives getting compromised. That reason doesn't make much sense. There is a better reason, as discussed below, but first we should observe that at present Linux stores only a pseudo-random seed and then relies entirely on the PRNG! This is in no way more trustworthy than storing some real entropy. Any attacker who could steal the hypothetical random-seed file can also steal the urandom-seed file. Here's a better reason why at present it would make no sense to take the obvious approach to storing real entropy across reboots: The /dev/urandom quasi-PRNG would immediately waste the entropy. The device apparently assumes that a steady supply of new raw entropy will always be available. In situations where entropy is scarce -- e.g. when there is a finite stored supply -- normal operation of /dev/urandom is tantamount to a denial-of-service attack on the entropy supply. Any application that wants to file away some entropy can perfectly well do so, provided it does not let /dev/urandom get its hands on it. -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.12 (GNU/Linux) Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/ iQIVAwUBUn06TPO9SFghczXtAQJOzQ//Ud3qD1Syxp5DEcRS+hyaeUaPkjyYJUkX VJGcxmic2ljWoUO+m1Vxs4ZVRsmUMPfmUxM7fpX0wKz/Isqndq2xN2RTsqsGDwgG 23+Uh0wZSMY1Cbe2SQJKJzQEuJH+KXa6nFsuRtIUzry67yYhnz7EuUjZMdU22pI7 xDyug4GukRO4jjl5eTG6XFNS6IKooHuBic28PXhC+BtNX0fDpwuB175t7VPZ/81J 5Q/ai4lJMPxjgrgoYOmhx7DfC3+vkKh2GG8EcsoGvZUqHSU53D+7n1fbgX/5q06e oUJdquqoOLu40ESBs+DifyDhWH3XzZrH3XR6lceGu9k9U/TNrfML30RsqNyo+LwD SQvtA/L7RCGdB9f5QB7i26/E5FUbeecCnC4Hqr+kflrNP13rSROG9Xzkr7K5ODR7 B2W5KtPMSQz49R+ooCrOZMX2KPI3cxoQh+UYL1V4WbeUlR83z2Y4sYL5kGWdpu1W i7P8JNLr9V5w278+SSwlozfH+2XZHdaNFtfGPdA4h1clQkDdvwhAgXsH28ScQbTt cGGtx8cv00oz4lgHXMB4z1cG8PKRu7T02/M+s9pPeWUtml/GUYG9AVADEV44yjuA UOGYyhNgpSqx6ONZeTJzd3TAUN3s8GsORbGIeQwDdRp244+eNniKAyiC9zzFdhyc Eo2MLiJQ+h0= =er6J -----END PGP SIGNATURE----- _______________________________________________ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
home | help | back | first | fref | pref | prev | next | nref | lref | last | post |