Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Fri Aug 21 1998 - 17:20:23 ADT
David Wagner (daw@CS.Berkeley.EDU)
Tue, 14 Jul 1998 12:58:00 -0700 (PDT)
Two comments:
* Your proposal uses MD5(secret || counter) as a stream cipher to
stretch a short secret into a longer output. I'm not sure that
this is wise.
I don't think it's very safe to rely on MD5 to be too secure in
this mode, especially when the output length is much longer than
the length of the secret. This requires stronger properties
from the hash than are needed for most conventional applications
of MD5, and I don't think MD5 has seen much analysis directed
towards this application.
* Your proposal doesn't stand up very well to ``state compromise''
attacks. These are relevant if the attacker can learn the entire
state at some time (perhaps by a one-time breakin), and then
use known outputs from the generator to extend his knowledge.
In your proposal, if the state is compromised at time t, and the
the attacker can obtain a known output from the generator at time
t+e, and if the entropy samples between time t and time t+e can
be guessed, then the attacker can deduce the state at time t+e.
(Guess the entropy samples, compute the expected output at time
t+e, and compare to the known output.) Repeat as long as possible.
In this way, the attacker may be able to extend his knowledge of
the state forward for quite some time.
In practice, known outputs are often available -- e.g. when IV's
or protocols nonces are generated using the generator. (E.g.
imagine a prototocol where you mix a new entropy sample, generate
an IV, generate a key, and then repeat; in this case, a single
state compromise would often allow all subsequent states, and
outputs, to be deduced quite easily.) Also, in your generator,
each entropy sample has only a little bit of entropy, so it would
be possible to simultaneously guess quite a number of samples,
if known outputs from the generator are only rarely available.
Your proposal is better than some, in that it prevents backtracking
and meet-in-the-middle attacks after a state compromise. However,
it would be better to prevent iterative-guessing attacks. The
typical countermeasure is to save up a number of entropy samples,
and only mix them into the pool once their combined entropy exceeds
some threshold (perhaps 64--160 bits, according to taste).
John Kelsey, Bruce Schneier, Chris Hall, and I have done some work
on these sorts of attacks; for more info, see the following paper:
John Kelsey, Bruce Schneier, David Wagner, and Chris Hall.
``Cryptanalytic Attacks on Pseudorandom Number Generators.''
FSE '98, or <http://www.cs.berkeley.edu/~daw/prngs-fse98.ps>.
The following archive was created by hippie-mail 7.98617-22 on Fri Aug 21 1998 - 17:20:23 ADT