[147688] in cryptography@c2.net mail archive
Re: [Cryptography] /dev/random is not robust
daemon@ATHENA.MIT.EDU (Jerry Leichter)
Wed Oct 16 14:05:43 2013
X-Original-To: cryptography@metzdowd.com
From: Jerry Leichter <leichter@lrw.com>
In-Reply-To: <CACXcFm=7L3SPuyjQnOBUWMejp+2dj2eSOKiNLBOGG7YH0Tey4g@mail.gmail.com>
Date: Wed, 16 Oct 2013 13:58:31 -0400
To: Sandy Harris <sandyinchina@gmail.com>
Cc: Cryptography <cryptography@metzdowd.com>
Errors-To: cryptography-bounces+crypto.discuss=bloom-picayune.mit.edu@metzdowd.com
--===============3115595182577254124==
Content-Type: multipart/alternative; boundary="Apple-Mail=_153E5CF0-0099-4984-A193-1A78BE495DDB"
--Apple-Mail=_153E5CF0-0099-4984-A193-1A78BE495DDB
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain;
charset=windows-1252
On Oct 16, 2013, at 8:49 AM, Sandy Harris <sandyinchina@gmail.com> =
wrote:
> =46rom the paper:
>=20
> " Several security notions have been defined:
> " =96 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;
> " =96 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 ...
>=20
> 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
--Apple-Mail=_153E5CF0-0099-4984-A193-1A78BE495DDB
Content-Transfer-Encoding: quoted-printable
Content-Type: text/html;
charset=windows-1252
<html><head><meta http-equiv=3D"Content-Type" content=3D"text/html =
charset=3Dwindows-1252"></head><body style=3D"word-wrap: break-word; =
-webkit-nbsp-mode: space; -webkit-line-break: after-white-space; =
"><div><div>On Oct 16, 2013, at 8:49 AM, Sandy Harris <<a =
href=3D"mailto:sandyinchina@gmail.com">sandyinchina@gmail.com</a>> =
wrote:</div><blockquote type=3D"cite">=46rom the paper:<br><br>" Several =
security notions have been defined:<br>" =96 Resilience: an adversary =
must not be able to predict future PRNG<br>outputs even if he can =
influence the entropy source used to initialize<br>or refresh the =
internal state of the PRNG;<br>" =96 Forward security ( resp. backward =
security): an adversary must not<br>be able to predict past (resp. =
future) outputs even if he can<br>compromise the internal state of the =
PRNG.<br>" ... Barak and Halevi [BH05] model a PRNG with input ... and =
define a<br>new security property called robustness that implies =
resilience,<br>forward and backward security. This property actually =
assesses the<br>behavior of a PRNG after compromise of its internal =
state ...<br><br>None of this matters much if the enemy does not already =
have root on<br>your system.</blockquote><div>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 <i>*</i><i>potential capabilities*</i>, 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.)</div><br><blockquote type=3D"cite"> If an enemy does have root, =
he has far better targets<br>than the RNG available and the defenders =
have bigger worries. Without<br>root, he cannot see the internal state =
and, if you use the typical<br>setup where some saved entropy from last =
time is pumped in by the boot<br>scripts, he cannot read that file and =
using it seems to complicate the<br>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....</blockquote>I'm amazed and disturbed by the nature =
of the responses to this paper. They are <i>*indistinguishable* =
</i>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.</div><div><br></div><div>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.</div><div><br></div><div>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.)</div><div><br></div><div>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?</div><div><div> =
=
=
-- Jerry</div><div><br></div></div></body></html>=
--Apple-Mail=_153E5CF0-0099-4984-A193-1A78BE495DDB--
--===============3115595182577254124==
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
--===============3115595182577254124==--
