[Cryptography] "/dev/random is not robust"

[Eugen Leitl]

----- Forwarded message from John Gilmore <gnu at toad.com> -----

Date: Mon, 14 Oct 2013 18:53:58 -0700
From: John Gilmore <gnu at toad.com>
To: dj at deadhat.com
Cc: tytso at mit.edi, Cryptography List <cryptography at metzdowd.com>, cryptography at randombit.net
Subject: Re: [Cryptography] "/dev/random is not robust"
Message-Id: <201310150153.r9F1rwqQ011302 at new.toad.com>

> http://eprint.iacr.org/2013/338.pdf

I'll be the first to admit that I don't understand this paper.  I'm
just an engineer, not a mathematician.  But it looks to me like the
authors are academics, who create an imaginary construction method for
a random number generator, then prove that /dev/random is not the same
as their method, and then suggest that /dev/random be revised to use
their method, and then show how much faster their method is.  All in
all it seems to be a pitch for their method, not a serious critique of
/dev/random.

They labeled one of their construction methods "robustness", but it
doesn't mean what you think the word means.  It's defined by a mess of
greek letters like this:

  Theorem 2. Let n > m, , ?? ??? be integers. Assume that G :
  {0, 1}m ??? {0, 1}n+ is a deterministic (t, ??prg )- pseudorandom
  generator. Let G = (setup, refresh, next) be defined as above. Then
  G is a ((t , qD , qR , qS ), ?? ??? , ??)- 2 robust PRNG with
  input where t ??? t, ?? = qR (2??prg +qD ??ext +2???n+1 )
  as long as ?? ??? ??? m+2 log(1/??ext )+1, n ??? m + 2
  log(1/??ext ) + log(qD ) + 1.

Yeah, what he said!

Nowhere do they seem to show that /dev/random is actually insecure.
What they seem to show is that it does not meet the "robustness"
criterion that they arbitrarily picked for their own construction.

Their key test is on pages 23-24, and begins with "After a state
compromise, A (the adversary) knows all parameters."  The comparison
STARTS with the idea that the enemy has figured out all of the hidden
internal state of /dev/random.  Then the weakness they point out seems
to be that in some cases of new, incoming randomness with
mis-estimated entropy, /dev/random doesn't necessarily recover over
time from having had its entire internal state somehow compromised.

This is not very close to what "/dev/random is not robust" means in
English.  Nor is it close to what others might assume the paper
claims, e.g. "/dev/random is not safe to use".

	John

PS: After attending a few crypto conferences, I realized that
academic pressures tend to encourage people to write incomprehensible
papers, apparently because if nobody reading their paper can
understand it, then they look like geniuses.  But when presenting at
a conference, if nobody in the crowd can understand their slides, then
they look like idiots.  So the key to understanding somebody's
incomprehensible paper is to read their slides and watch their talk,
80% of which is often explanations of the background needed to
understand the gibberish notations they invented in the paper.  I
haven't seen either the slides or the talk relating to this paper.

_______________________________________________
The cryptography mailing list
cryptography at metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography


----- End forwarded message -----
-- 
Eugen* Leitl <a href="http://leitl.org">leitl</a> http://leitl.org
______________________________________________________________
ICBM: 48.07100, 11.36820 http://ativel.com http://postbiota.org
AC894EC5: 38A5 5F46 A4FF 59B8 336B  47EE F46E 3489 AC89 4EC5