[prev in list] [next in list] [prev in thread] [next in thread] 

List:       cryptography
Subject:    Re: depleting the random number generator
From:       John Kelsey <kelsey.j () ix ! netcom ! com>
Date:       1999-07-29 0:41:56
[Download RAW message or body]

-----BEGIN PGP SIGNED MESSAGE-----

[ To: Perry's Crypto List, Bram, James, Dave ##
  Date: 07/28/99 ##
  Subject: Re: depleting the random number generator ]

>Date: Mon, 26 Jul 1999 11:16:54 -0700
>To: bram <bram@gawth.com>
>From: "James A. Donald" <jamesd@echeque.com>
>Subject: Re: depleting the random number generator
>Cc: David Wagner <daw@cs.berkeley.edu>, cryptography@c2.net

>At 1018 AM 7/26/99 -0700, bram wrote
>> The threat model for yarrow and other SRNG's is that the
>> attacker can not only tell when entropy is coming in, but
>> control it's contents as well.

>The assumption was that entropy was the time of arrival.
>Even if the attacker has control over the entropy added to
>the RC4 state, this cannot give him any additional
>information about the state of the RC4 generator.

I think we're talking about different things, here.  I will
agree with you that if you take a totally unknown, pristine,
RC4 state, and then apply the RC4 key schedule to it with
bytes I get to choose, I will learn nothing about the
resulting RC4 state.  This is just another way of saying
that multiplying an unknown permutation by a known one
yields an unknown permutation, right?

But the problem is a little different.  In normal use, RC4
is keyed, and then is used to generate (say) a few million
bytes of keystream.  An attacker might be able to retrieve
these bytes of keystream, and might try to recover the key,
or some information about the RC4 state, at some point
during the encryption.  (Since RC4 is reversible, knowing
the state at any point lets you learn the state at all other
points in the keystream.)

In this kind of use, the attacker gets to observe outputs,
and then choose inputs, and then observe some more outputs,
and then choose some more inputs, etc.	The attacker is in
an *enormously* more powerful situation here than in
attacking the normal RC4.

Now, right off the top of my head, I don't have an attack on
RC4 under these circumstances.  But since essentially nobody
has looked at RC4 under these circumstances, it would be
foolish to design a system that assumed no such attacks
existed.

[ Some stuff deleted. ]

>> The idea is to build something which only fails if the
>> attacker both knows the state of the pool at some point and
>> manages to control all attempted reseedings.

>An RC4 state fulfills this requirement, plus if we reseed
>from the time of arrival of packets, the attacker cannot
>control all incoming packets, thus even if at some point he
>knows the state of the pool, that knowledge will soon be
>lost.

No, this ignores the iterative guessing attack:

a.  I know your RC4 state, maybe because your program started
out with insufficient entropy.

b.  You output a few bytes as a nonce or something.  I
verify that it matches with my knowledge of your state.  It
does, so I do nothing else.

c.  You receive a packet whose precise arrival time I don't
know, but which I can restrict to only a few hundred
possibilities.

d.  You output a few bytes from your RC4 state as a nonce or
something.

e.  I see that these bytes don't agree with my model, and so
try guessing the inputs to the RC4 state until they do
agree.  When I guess the right value, I learn your new
state.  At this point, the entropy from that packet has
given you no benefit.

You can repeat steps c-e many, many times, feeding thousands
of bits of entropy into your RC4 state, while still leaving
an attacker with complete knowledge of that state.  Since he
only has to guess a few bits at a time, he never has to face
an impossibly large guess.

This is like having a good passphrase that is hashed one
letter at a time, and all the intermediate hashes are
stored.  Even a really good passphrase would be trivial to
``guess,'' given this information.

There are only two reasons to add entropy to a PRNG once you
believe you have a secure state:

a.  You think that your generator might not have a long
enough cycle length or might not be secure for arbitrarily
long output sequences, and thus use entropy-bearing inputs
to sort-of rekey it.  You want to ensure that your PRNG's
generator doesn't have to output so many bits that some
statistical flaw shows through or something.

b.  You are concerned with some kind of state compromise,
most likely from starting up with insufficient entropy.  You
want to ensure that your PRNG eventually has a chance to
recover from such a compromise.

Note that these are the *only* reasons to collect and feed
in entropy.  Otherwise, once you have a secure state, why
bother?  It allows an attacker to send in inputs, which is
one more thing you have to worry about, and it doesn't do
any good otherwise.

If you're going to bother to add in entropy, then you need
to do it in such a way that you actually recover from key
compromises and defend against short cycles and such.  The
best way to do this is probably something like keeping your
entropy inputs in a hashing context, and then rekeying your
RC4 context with the hash output, once you're convinced
you've collected enough entropy.  Naturally, there are about
a hundred other engineering issues there, like how you
estimate the amount of entropy you're collecting,
specifically how you rekey RC4, etc.

The other issue with RC4 is that there are small statistical
flaws in its output sequence.  Golic found some of these,
which were published at Eurocrypt a couple of years ago;
previously, someone (Roos?  Jenkins?) found that pairs of
the same output byte appear either too commonly or too
rarely.  Neither of these have any impact to speak of on its
usefulness as a stream cipher, but in rare instances, may
have some impact on its usefulness as a PRNG.  (For example,
there are some protocols in which the random numbers used
must be truly indistinguishable from random numbers.)  That
clearly isn't the case for the application being discussed
here, though.

>--digsig
>	James A. Donald

- --John Kelsey, Counterpane Internet Security, kelsey@counterpane.com
NEW PGP print =  5D91 6F57 2646 83F9 6D7F 9C87 886D 88AF

-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 5.5.3i for non-commercial use <http://www.pgpi.com>

iQCVAwUBN5+hjCZv+/Ry/LrBAQEmtQP9GNYcnB/kkX9qWRc1WqXa6fejtuRLCspK
VBIV9xgXTwt/Gdg6XNkBozB7zlMjstyXIvBBapkdPaaWkR6En1pn8J+pGGJOPNdy
y3W3ue2RJqVLrggEcbD9l01lNal5JRFtIRtOEgs0VMTkDIiSUzr9ZRmlXnUjNcBr
YfByDYDKrCg=
=NvHc
-----END PGP SIGNATURE-----

[prev in list] [next in list] [prev in thread] [next in thread]