Re: Mersenne Twister - Why a PRNG isn't a OTP

Bill Stewart (bill.stewart@pobox.com)
Wed, 15 Jul 1998 00:16:38 -0700

• Next message: Chuck McManis: "For fun ..."
• Previous message: bram: "Re: One real life secure random generator"
• In reply to: David Wagner: "Re: One real life secure random generator"

At 08:59 AM 7/14/98 -0400, Tom Otvos wrote:
>(Sigh.) So much to learn. Thanks for taking the time to respond in such
>detail. Incidentally, the MT paper does offer that "by a simple linear
>transformation...one can easily guess the present state from a sufficiently
>large size of the output".
        Then it's toast, unless "sufficiently large" is sufficiently large,
e.g. 2**32 bytes is trivially small for most systems, but 2**128 is
big enough most things you'll do on this planet.

>But here is one more thought (or question really). If you combine a PRNG
>with a one-way hash, is the output still "random" and more secure? My
>thinking is that, since the key to breaking a PRNG/OTP is to guess its
>internal state from a relatively few known inputs, if I run the PRNG output
>through a one-way hash before the xor then the raw output (and hence clues
>to the state) would be substantially obscured. At this point, the only
>attack is a brute force one in which case the period becomes the determining
>factor of security.

That's certainly a lot better, if you do it right:
The PRNG generates P1, P2, P3, P4, ....
and you hash them into H1=hash(P1), H2=hash(P2), ....
and use H1, H2, ... to XOR with your plaintext.
(Or, better, use H1=hash(salt,P1), .....)

That's still no guarantee of security - if you use the same
output stream from the PRNG more than once, you still lose instantly.
And if the PRNG doesn't have much state, it's still easy to do brute-force -
for instance, if the PRNG state is a 32-bit random number,
the Bad Guy only has to try a few billion hits to guess the right one
(which is one reason to salt the hash.)

                                Thanks!
                                        Bill
Bill Stewart, bill.stewart@pobox.com
PGP Fingerprint D454 E202 CBC8 40BF 3C85 B884 0ABE 4639

• Next message: Chuck McManis: "For fun ..."
• Previous message: bram: "Re: One real life secure random generator"
• In reply to: David Wagner: "Re: One real life secure random generator"