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:21 ADT
Tom Otvos (tomo@everyware.com)
Tue, 14 Jul 1998 08:59:24 -0400
(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".
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.
Or, should I just go back to being a passive observer on this list?
Tom Otvos
Director of Research, EveryWare Development Inc.
http://www.everyware.com/
"Try not! Do, or do not. There is no 'try'." - Yoda
-----Original Message-----
From: Bill Stewart <bill.stewart@pobox.com>
To: Tom Otvos <tomo@everyware.com>; CodherPlunks@toad.com
<CodherPlunks@toad.com>
Date: Tuesday, July 14, 1998 4:04 AM
Subject: Re: Mersenne Twister - Why a PRNG isn't a OTP
>At 10:28 AM 7/10/98 -0400, Tom Otvos wrote:
>>I am usually a passive observer on this fascinating list, but this PRNG
>>raises a question for me. If this RNG has an "astronomical period"
>>(according to the authors), and if a one-time pad is the theoretical
nirvana
>>of encryption, then what is the downside of using something like the
Twister
>>as input to an OTP-based encryption scheme?
>>If this question is really goofy, please don't come down too hard on me.
>
>Well, you _have_ asked the FAQ "Why can't I just use a PRNG as a OTP?" :-)
>The generic XOR-based stream cypher works like this:
> M[i] Message bit i
> X[i] Some source of bits used for encryption
> C[i]==M[i] xor X[i] The encrypted message
> M[i]==C[i] xor X[i] Decrypting the message
>
>For a genuine perfectly-secure Claude Shannon style One Time Pad,
>the X[i]s are independent random bits, either generated by magic
>(e.g. mathematical supposition used for a proof) or by physical randomness,
>and knowing X[1]...X[i-1] and X[i+1] .... tells you entirely nothing
>about X[i], and therefore having copies of the plaintext and
>cyphertext for all the other bits tell you entirely nothing -
>Bit i is either a 0 or a 1, and if you don't have a copy of the pad,
>there's no way for you to tell which.
>
>However, with a PRNG, the initial state of the generator
>tells you what all the future values of X[i] are -
>so if it's possible to determine that state from X[1]...X[i-1],
>you can determine X[i], at least if i is big enough.
>And a known plaintext attack can often let you determine the Xs -
>this is especially a risk for email, which often starts out with
>"Received:" or "From:" or a few other easily guessed plaintexts.
>
>Some PRNGs are especially easy targets - the standard x*a+c mod m
>means that if you know _any_ m-bit word of PRNG output, it's toast.
>Similarly, PRNGs with short periods are also easy targets,
>but having a long period doesn't mean an algorithm is strong,
>any more than passing simple statistical tests means it's strong;
>they just mean it isn't insultingly weak.
>
>On the other hand, there are cryptographically strong algorithms
>that can be used as XOR cyphers (as long as you're careful to
>use them only once), because it's difficult to recover the internal
>state of the algorithm in any manner much simpler than brute-force search
>over a sufficiently large keyspace that searching takes too long.
>For instance RC4 appears to be about as strong as its keylength -
>40-bit keys only need ~2**40 tries, while 128-bit keys need 2**128 tries.
>
>How do you tell the strong algorithms from the weak ones? Practice!
>In particular, you show that there's some mathematical reason
>that it's hard to determine the state (and thus the key) from the output,
>and check lots of literature to find out if anybody's done it before,
>and you check it with other cryptographers to see if it's something
>obvious to them, and you do it before selling a product,
>so if Ian Goldberg can rip your algorithm to shreds over a long lunch,
>you don't have it embedded in 80 million cell phones.*
>
>[*This is different from having Schneier and Mudge rip your
>implementation to shreds for re-using RC4 keys several different ways;
>that's egregiously clueless misuse of a good algorithm
>rather than clueless use of a bad algorithm, though MS PPTP also
>had some of that kind of problem as well.]
>
>The NSA's VENONA intercepts of Russian One Time Pad traffic was
interesting.
>Sometimes the Russians reused pads (the big problem with OTPs
>is distributing them securely and having enough that you don't run out),
>but some of it the cracking was apparently finding hidden non-randomness
>in the pads - generating them by pounding "randomly" on typewriters
>sometimes isn't as random or uncorrelated as you'd like to think.
>
>>I presume the scheme would have to be "private key" so that the sender and
>>recipient (if they are different people) could initialize their Twisters
to
>>the same state, but I also presume that for dedicated channels, that
>>synchronization would only have to be done once after which both RNGs
would
>>stay in synch.
>
>Probably depends on whether packets get lost in the channel -
>some algorithms and modes can recover from that, and some can't.
>
> Thanks!
> Bill
>Bill Stewart, bill.stewart@pobox.com
>PGP Fingerprint D454 E202 CBC8 40BF 3C85 B884 0ABE 4639
>
The following archive was created by hippie-mail 7.98617-22 on Fri Aug 21 1998 - 17:20:21 ADT