[Cryptography] randomness +- entropy

John Denker jsd at av8n.com
Fri Nov 8 14:23:57 EST 2013


-----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-----


More information about the cryptography mailing list