[Cryptography] randomness +- entropy

[John Denker]

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