[Cryptography] /dev/random is not robust

Eugen Leitl eugen at leitl.org
Thu Oct 17 02:18:06 PDT 2013


----- Forwarded message from Jerry Leichter <leichter at lrw.com> -----

Date: Wed, 16 Oct 2013 17:10:00 -0400
From: Jerry Leichter <leichter at lrw.com>
To: Theodore Ts'o <tytso at mit.edu>
Cc: Sandy Harris <sandyinchina at gmail.com>, Cryptography <cryptography at metzdowd.com>
Subject: Re: [Cryptography] /dev/random is not robust
Message-Id: <2CE9C56B-774E-4152-8A21-237337F9954F at lrw.com>
X-Mailer: Apple Mail (2.1510)

Can we separate the issue of actual issues in the Linux RNG from the responses to this paper?

It's been a long time since I worked on an RNG, for a product that ran on systems that provided nothing like /dev/random; our Linux version mixed in /dev/random, and our Windows system mixed in whatever Windows calls its random number provider.  I have no doubt that the Linux RNG is immensely better than the hack we were able to cobble together - not being in the kernel severely restricted our entropy sources.  From what I've seen of the Linux RNG, it does a pretty good job.  I'm not about to suggest any code changes, and frankly nothing in this paper suggests any either.  Following its guidelines would produce an entirely new RNG, which absolutely *no one should trust* until it's been kicked around in the community for a while.

My problem is *entirely* with some of the intemperate responses I've seen out there, which basically say "Oh, that's just some academic nonsense, pay no heed".  I've seen nothing of that sort from you, Theodore Ts'o, personally; while you clearly have an emotional attachment to the work you've done - don't we all? - your responses are mainly technical in nature, pointing out places where the paper misunderstood what the current implementation does.  However, you do let a bit of an attitude come through in remarks about "not caring about publishing papers".  As I said, there is good and bad academic work, and not even all the good academic work is actually useful.  As an example of good and useful academic work, I usually point to Phil Rogoway's papers.  While the papers themselves are highly technical and get into a great deal of detail, what comes out at the end are simple designs that can be, and have been, implemented.  If you implement one of Rogoway's designs, you know t
 here's a formal proof behind it.  You don't need to actually understand the proof - others have reviewed it and it's almost certainly solid.  Merge sort will run in O(n log n) for you whether you understand the theory or not.

I see the paper as valuable for proposing strong security definitions for "PRNG's with input", showing that neither Barak and Halevi's algorithm nor the Linux RNG's algorithm attain those definitions, but suggesting an algorithm that does.  The answer "well, yes, the Linux generator fails if its entropy sources are bad in a particular way, but we have entropy sources that aren't" misses the point.  At one time, not so very long ago, no one knew how to build a cipher secure against a known-plaintext attack.  Today, that's assumed.  A defense of a modern cipher as "well, we won't let anyone see the plaintext" isn't good enough.  (Even worse is the claim that "you can only see the state of the PRNG from root, and then there are other attacks".  This isn't even true - a Linux system frozen into a VM can't prevent anyone from reading that state if they want it hard enough.)

Just as they extended Barak and Halevi's definitions, others may well come along and "tune" theirs.  That doesn't make theirs, or Barak and Halevi's, work "wrong"; it just makes them incomplete.  Others will also eventually come along and produce better algorithms that attain the various definitions that the community comes to agree on.

I'm not sure how the whole business of entropy estimation feeds into this.  There are others who've criticized it as just guesswork.  Frankly, they have a point.  John Denker's work on Turbid provides a much more principled approach to the problem.  Still, the Linux kernel has to work with what it has.

Whether new, better, strong approaches will come along in the future is impossible to tell.  If they do, I would hope those engineering Linux and other systems will have the humility to admit that the direction they've been going was, as it turns out, incorrect, and that they should start again from scratch.  That's how science and engineering are supposed to work.

Random numbers are way too important to allow the kinds of dismissive responses we've been seeing.

                                                        -- Jerry

_______________________________________________
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




More information about the cypherpunks mailing list