[147916] in cryptography@c2.net mail archive
Re: [Cryptography] [RNG] /dev/random initialisation
daemon@ATHENA.MIT.EDU (Peter Todd)
Thu Oct 31 13:24:20 2013
X-Original-To: cryptography@metzdowd.com
Date: Wed, 30 Oct 2013 20:46:54 -0400
From: Peter Todd <pete@petertodd.org>
To: Jerry Leichter <leichter@lrw.com>
In-Reply-To: <129DF2E9-6F7C-43AC-B136-F63A0FA3996D@lrw.com>
Cc: cryptography@metzdowd.com, jamesd@echeque.com
Errors-To: cryptography-bounces+crypto.discuss=bloom-picayune.mit.edu@metzdowd.com
--===============4164792886170218209==
Content-Type: multipart/signed; micalg=pgp-sha256;
protocol="application/pgp-signature"; boundary="vGgW1X5XWziG23Ko"
Content-Disposition: inline
--vGgW1X5XWziG23Ko
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable
On Wed, Oct 30, 2013 at 05:00:33PM -0400, Jerry Leichter wrote:
> On Oct 30, 2013, at 4:32 PM, "James A. Donald" <jamesd@echeque.com> wrote:
> > No source of entropy can ever be harmful. The worst that can happen is =
that it is entirely predictable to the adversary, in which case it does lit=
tle good, but can never do harm.
>=20
> Are you so sure?
>=20
> Consider a Linux-style RNG. Suppose I know that all the existing sources=
produce k bits/second of randomness. If I draw k bits/second of data out =
of it, after a while, it has no "spare" randomness inside - it's giving me =
exactly what it has. If I draw j >> k bits/second out of it, it quickly "r=
uns out". It may block, effectively rate-limiting me; or it may stretch wh=
at it had.
>=20
> Now suppose I inject j >> k bits of my own, controlled data, declaring th=
at it represents j bits of entropy - all the while continuing to draw j bit=
s out. The generator now has plenty of entropy - or thinks it does - so ne=
ver blocks. But eventually it must be the case that I'm getting way more b=
its out than the real entropy going in. If I can't predict the bits I'm ge=
tting out, it can only be because of the lingering entropy from the other s=
ources. (If j is much larger than k, then most of the bits I get out are c=
omputed without any bits other than my own going in.)
>=20
> But this is an odd state of affairs. If the assumption is that the resul=
ts remain unpredictable, no matter how much larger j is than k, then why sh=
ould the generator *ever* block because it's output more bits than it got i=
n? After all, that situation is effectively indistinguishable from it havi=
ng gotten all 0 bits at some very high rate.
>=20
> So: For extra sources to always be harmless, it must be the case that th=
e bits are unpredictable *even if no new entropy arrives*. All that matter=
s, in effect, is that the internal state be unknown and unpredictable *once=
*. BBS has this property, as (on different assumptions) do crypto-based PR=
NG's like Yarrow. But this has a performance cost, and I'm not sure that a=
Linux-style generator does. If you have it ... why would you need to allo=
w additional (allegedly random) sources?
This is why the Linux RNG allows anyone to add data to the pool as an
unprivileged operation, but requires root to change the estimates of how
much entropy is in the pool.
Try it: cat /dev/zero > /dev/random
--=20
'peter'[:-1]@petertodd.org
0000000000000005fc0cffa2f1c60362ad998d2a6dd92ab69c34235a0e0b064f
--vGgW1X5XWziG23Ko
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: Digital signature
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.12 (GNU/Linux)
iQGrBAEBCACVBQJScah+XhSAAAAAABUAQGJsb2NraGFzaEBiaXRjb2luLm9yZzAw
MDAwMDAwMDAwMDAwMDVmYzBjZmZhMmYxYzYwMzYyYWQ5OThkMmE2ZGQ5MmFiNjlj
MzQyMzVhMGUwYjA2NGYvFIAAAAAAFQARcGthLWFkZHJlc3NAZ251cGcub3JncGV0
ZUBwZXRlcnRvZC5vcmcACgkQJIFAPaXwkfvy/ggAua31fQdEjaUxizBiQk//EIY2
3sEA963bp+4jzjgOwQfq2gjZqTFWkODOi8neNwbrTBZqqENemU+Hta/MOUltifB6
yV51lguomgO2D8DGjUnzS8ueuDPjHrPjqi0RUDysmIbvdKvcDGNbSgspRiETLz2d
AxqWIYH9xA4OK7Euq+SgKXhoGxyEJqDpfocoR/SGsVYO0j00ebTcsdiN9RzBTJas
Befzqpxh1privzAkVC/Osbc/l2ntCM20TlNOfmycdp0+3Jzx/oKXxhj+lQzkokxK
9dWfUBu6X1L/poFVoMyKbNEn8qEV2J1WRIQNyYBGsGXzLMZFjg5jecd+FjXvcw==
=rfRH
-----END PGP SIGNATURE-----
--vGgW1X5XWziG23Ko--
--===============4164792886170218209==
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
_______________________________________________
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography
--===============4164792886170218209==--
