Google Groups

Re: implementation of one-time-pad with Mersenne Twister PRNG


Martin Grajcar Jul 2, 2011 3:44 PM
Posted in group: sci.crypt
On Saturday, July 2, 2011 11:13:58 PM UTC+2, bystander wrote:
> I agree that no PRNG is "secure" in the sense that it is theoretically
> unbreakable but I believe that sequences generated by the MT have been
> shown to have all the statistical properties of "true" randomness.

I can't tell if this is true, but I'm sure that it's not enough.

> For
> example, sufficiently large samples pass all the Diehard tests for
> randomness. Obviously, the OTP is only as strong as the method used
> for generating the pad.

Again: DO NOT CALL IT OTP. It is a stream cipher.

> In David Kahn's book he states that the
> Soviets generated their OTPs by having clerks type "randomly" on
> typewriter keyboards! Surely, the MT is as secure as that. Soviet OTP
> encryption was broken but only because some pads were used more than
> once.

The so called "two times pad" is really a terrible cipher. :D

> It seems to me that the distinction between a stream cipher and a OTP
> is tenuous at best. In practice, they both accomplish the same thing:
> producing a key as long as the message itself.

They're similar, but the distinction is not tenuous at all:
- The OTP requires a key as long as the message, stream ciphers do not.
- The OTP is unbreakable in every sense you can imagine, stream ciphers are not.
- The OTP is terribly impractical, stream ciphers are not.

> The period of the MT is
> 2^19937 - 1, long enough for any practical message.

A period of 2**64 would also suffice for most practical reasons, a period of 2**256 would suffice until the sun goes out. But the period length itself in that important. AFAIK seeing as much output of the MT as its internal state allows you to reconstruct the state easily, so it's quite insecure.

See RC4 for an obsolete, but very simple stream cipher. See Salsa20 for a modern and yet unbroken one. Both are simpler and more practical than MT.