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

Joseph Holsten joseph at josephholsten.com
Wed Oct 16 12:27:47 PDT 2013


Seems like their standard is from Barak & Halevi, “A model and architecture for pseudo-random generation with applications to /dev/random.”

– Resilience: an adversary must not be able to predict future PRNG outputs even if he can influence the entropy source used to initialize or refresh the internal state of the PRNG;
– Forward security ( resp. backward security): an adversary must not be able to predict past (resp. future) outputs even if he can compromise the internal state of the PRNG.

Seems like a lovely defense-in-depth goal, but I'd really like to read the original paper to figure out why I should care.
--
~j


On 2013-10-15, at 08:49, Eugen Leitl <eugen at leitl.org> wrote:

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

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 496 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <http://lists.cpunks.org/pipermail/cypherpunks/attachments/20131016/003cb6ed/attachment-0001.sig>


More information about the cypherpunks mailing list