[Cryptography] /dev/random is not robust

Jerry Leichter leichter at lrw.com
Wed Oct 16 13:58:31 EDT 2013


On Oct 16, 2013, at 8:49 AM, Sandy Harris <sandyinchina at gmail.com> wrote:
> From the paper:
> 
> " Several security notions have been defined:
> " – 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.
> " ... Barak and Halevi [BH05] model a PRNG with input ... and define a
> new security property called robustness that implies resilience,
> forward and backward security. This property actually assesses the
> behavior of a PRNG after compromise of its internal state ...
> 
> None of this matters much if the enemy does not already have root on
> your system.
Backwards security is a prerequisite for building PFS, among other things.  Without it, if an attacker seizes your system, he can (in principle, but we're considering *potential capabilities*, not what we know how to do in detail today) "run the random number generator backwards", which would allow any keys that were created using the RNG - like those created in "secure" DH negotiations, for example - to be generated.  (But keep in mind the adage:  Attacks only get better.)

> If an enemy does have root, he has far better targets
> than the RNG available and the defenders have bigger worries. Without
> root, he cannot see the internal state and, if you use the typical
> setup where some saved entropy from last time is pumped in by the boot
> scripts, he cannot read that file and using it seems to complicate the
> state enough for security.... Also, the definition of resilience mentions an adversary who "can influence the entropy source" but the random(4) driver uses multiple sources so the degree of influence is generally limited....
I'm amazed and disturbed by the nature of the responses to this paper.  They are *indistinguishable* from the typical PR blather we get from every commercial operation out there when someone reports a potential attack:  It's just theory, it can't be translated into practice, we have multiple layers of security so even if one of them can be attacked the others still protect you, yadda yadda yadda.

Yes, this is a theoretical attack.  Yes, the Linux RNG is much more complex than the attackers assume in their model.  (Complexity is a good thing?)  No, no one is likely to be able to be able to use the attack actually get much out of the Linux RNG.  But attacks only get better.  The fact is, the Linux RNG, like all the "stir entropy into the pool" RNG's out there, were developed in an essentially ad hoc fashion, without even a solid idea of what the desired properties of such a primitive are supposed to be.  This paper is a step along a path begun in 2005 by Barak and Halevi (the instant paper has extensive references), and, frankly, it's about time.  For such RNG's we've been in about the same position we were in for ciphers in the 1980's and even beyond, before a great deal of theoretical effort got us to characterizations like IND-CPA and all sorts of excellent work on tight reductions and concrete security.

There's always been a strain of anti-academy bias - even anti-intellectualism - in the OSS community.  It's highly undesirable.  There's good academic academic work, and there's bad academic work.  Even with the domain of good academic work, some is of practical interest today, and some isn't.  (And some that isn't of interest today may be tomorrow.)

This kind of "shoot the messenger" approach is just plain wrong.  Look at the definition of robustness they come up with and tell me what parts of it aren't things you'd *like* to get in your RNG, if you could.  Can you come up with anything beyond hand-waving to show that the Linux RNG actually provides you with those properties?  Suppose someone was able to build on the current paper's work and design a Linux RNG that actually *did* provide those properties, with performance comparable to what we have today?  That's how, for example, we've gotten beyond the old, ineffective Modes of Operation to modern ones that have actual security techniques.  Wouldn't it be nice to be able to make the same transition for RNG's?  How will we ever do so without the initial work of the theoreticians to provide a target to aim for?
                                                        -- Jerry

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20131016/d5edf01c/attachment.html>


More information about the cryptography mailing list