[128664] in cryptography@c2.net mail archive
Re: Looking through a modulo operation
daemon@ATHENA.MIT.EDU (David Wagner)
Tue Jul 22 17:49:46 2008
From: David Wagner <daw@cs.berkeley.edu>
To: cryptography@metzdowd.com
Date: Tue, 22 Jul 2008 12:09:19 -0700 (PDT)
Matt Ball writes:
>Another attacking avenue is the 32-bit initial seed. If the
>implementation re-seeds frequently, or leaks to you the first outputs
>after initialization, then you only have to brute-force the 32-bit
>seed space, times the number of samples since reseeding.
Well, that's good and broken then, isn't it? No ifs about it.
It doesn't matter whether the implementation re-seeds frequently or
rarely. It doesn't matter whether it leaks to you the first outputs
after initialization or only later ones. If it's using a 32-bit seed,
this sucker is just plain broken, period.
The attack is trivial -- it's just exhaustive keysearch.
Attack: Given ~ 3 known outputs from the RNG, try all possible 32-bit
seeds. You'll be able to recognize when your guess at the seed is correct
because the output from your guessed seed will match the observed output.
This assumes you know the offsets of your outputs (how many times the
RNG has been cranked before producing your known outputs), but even
if you only have partial information about that you can still make a
variant of this attack work. The exhaustive search attack has to try
only 2^32 possibilities, so I'm guessing this attack should only take
minutes (at worst, hours) on a fast computer.
My earlier email about fancy attacks on this scheme is irrelevant.
There's no need to bother with fancy attacks, when the PRNG only uses
a 32-bit seed -- that's just blatantly insecure. This is a textbook
error, one of the oldest mistakes in the book. (For example, look
here: http://www.cs.berkeley.edu/~daw/papers/ddj-netscape.html)
Using this PRNG for security-critical purposes would not be wise.
I'll include your code snippet for seeding the PRNG below. Note: I'm
assuming, per your comments, that "unsigned long" is a 32-bit type.
>Here is the function that performs the initial seeding, based on a 32-bit seed:
>
>static void __set_random32(struct rnd_state *state, unsigned long s)
>{
> if (s == 0)
> s = 1; /* default seed is 1 */
>#define LCG(n) (69069 * n)
> state->s1 = LCG(s);
> state->s2 = LCG(state->s1);
> state->s3 = LCG(state->s2);
> /* "warm it up" */
> __random32(state);
> __random32(state);
> __random32(state);
> __random32(state);
> __random32(state);
> __random32(state);
>}
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
