[147998] in cryptography@c2.net mail archive
[Cryptography] randomness +- entropy
daemon@ATHENA.MIT.EDU (John Denker)
Mon Nov 4 14:32:46 2013
X-Original-To: cryptography@metzdowd.com
Date: Mon, 04 Nov 2013 12:21:00 -0700
From: John Denker <jsd@av8n.com>
To: RNG mlist <rng@lists.bitrot.info>,
Cryptography <cryptography@metzdowd.com>
In-Reply-To: <B73B9CCA-9532-4DA0-AAFE-16641204C7C6@gmail.com>
Errors-To: cryptography-bounces+crypto.discuss=bloom-picayune.mit.edu@metzdowd.com
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
Hi Folks --
Some people have been throwing around the word "entropy"
rather carelessly.
Entropy means something very special.
For a great many cryptological purposes, a high-quality
PSEUDO-random distribution is good enough, even though its
entropy density is very low. Note the contrast:
TRNG entropy density = 1 - epsilon
PRNG entropy density = epsilon
As another way of emphasizing the distinction: a PRNG places
orders-of-magnitude harsher demands on the strength of the
cryptological primitives it uses. This can be quantified
in terms of classical cryptologic ideas such as unicity
distance, but for present purposes I prefer the "entropy
density" language.
The rubber meets the road here: Consider the contrast:
PRNG: I am quite sure that on startup the machine needs to
have on board a crypographically strong, well-seeded PRNG.
This needs to be up and running very, very early in the
boot-up process. Some things that need the PRNG cannot
wait.
TRNG: At the moment I have no firm opinions as to how much
actual entropy the machine needs on start-up. I look
forward to having a discussion on this topic, with use-case
scenarios et cetera.
In particular, AFAICT it is not a settled question as
to whether the things that need a TRNG can wait, or how
long they can wait.
Both of these are solvable problems. They are not, however,
the same problem.
*) A reservoir of true-randomly distributed bits would,
as an immediate corollary, provide a seed that solves
the PRNG problem.
*) The converse is spectacularly not true.
FWIW note that current Linux distros make no attempt to
provide a reservoir of true-randomly distributed bits for
use at the next startup. There are some efforts toward
storing a seed for the kernel PRNG, but the stored seed is
itself pseudo-randomly generated, and the kernel correctly
attributes zero entropy to it.
Even more tangential remark: Note that even if there were
a reservoir of true-randomly distributed bits, AFAICT ssh
would not use them. Openssh is built on top of openssl,
which has its own internal PRNG, which it prefers to seed
using the kernel PRNG via /dev/urandom AFAICT. I refuse
to get too excited about this, because obviously this is
not set in stone. There is an engineering principle that
says we should "aim for the moving target" which in this
case means providing services to support the way apps /should/
work, even if some of them don't presently work that way.
By way of contrast, gnupg seems to be good about insisting
on true-randomly distributed bits for cutting its keys.
Bottom line:
-- If you mean "randomness" please say "randomness"
-- If you say "entropy", please be sure you really mean it.
-- Please do not use "entropy" as a misnomer for "randomness",
or even for "cryptologically strong randomness".
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.12 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/
iQIVAwUBUnfzm/O9SFghczXtAQKG5hAAzzFm59R4ZP93jZzq+xZQRUSPbeMCo7ae
xxkO5ZfBdtJZYCgG5P3+bgqEUZNqEfRgtyox/ZF4Kt+VAvzySjDpbxVtjBfi6kWX
qlO8OBjKwcilK8ZueqMKLLsTbQXOQie6jzjEoiNgnI/R/dN+Wp/L1Bq7aZREqa78
32dIWLWdYOfZlOz5JfWioOrJ8KBdp7IBvOXyv/VyyrY9zoQ1hJ83092XYabIcDJJ
gngCgoDJ+LmuaJeljhO+sjubtgucBT8iB9SI5u238YnYUeX959YNNDLq3WxWbYuC
eCFIXx96QjSoLpBLhNMTq1y8wZWDFFy91CXGiEzhxU1IjtQND9o5EoGCXD4E7QzB
5ihLO1DxcSVXq2O+gfU4ztfSyWLaOLPM4LJFZl9NkSrX0qWpDup1SSOdXolOOUNB
vqufo5yGyBZvLx9KyPPjb5tLD1cslmUskCFSHBovPBJ+QU1NIfppNoN5fzbZ+xvW
yUtfwPCSkI4331MTQCFwdEBa46LUwCyo4kb/qQ32QoJZsno6XbTLtsErWZ+ehrAQ
BY9vGcLrqZt2Cq4CVhb9H5o6JmNQTdMv296Tqa4g5NyOUU0tMqpH6Ofi7bzFA6To
+l582b+bxKx7n6yUZbRHEYZjp6DKpx+/HnSfBI/suI+BvZ1yFzL4cowum/iByXb6
sGqqZwiGz/Q=
=fd7g
-----END PGP SIGNATURE-----
_______________________________________________
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography