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
Bill Stewart (bill.stewart@pobox.com)
Mon, 13 Jul 1998 01:41:24 -0700
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