Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:18:28
Alex Alten (Alten@Home.Com)
Wed, 17 Feb 1999 23:56:44 -0800
At 06:35 AM 2/17/99 -0600, John Kelsey wrote:
>-----BEGIN PGP SIGNED MESSAGE-----
>
>[ To: CodherPlunks ## Date: 02/17/99 ##
> Subject: reflecting on RC4 ]
>
>>Date: Wed, 17 Feb 1999 00:21:45 -0800
>>To: CodherPlunks@toad.com
>>From: Alex Alten <Alten@Home.Com>
>>Subject: reflecting on RC4
>
>>Correct me if I'm wrong, but doesn't RC4's strength drop to
>>a maximum of 16 bits with a chosen plaintext attack? The
>>chosen plaintext would be the first 256 bytes enciphered.
>
>Hmmm. RC4 is a keystream generator. You give it a key, it
>sets up and starts cranking out random-looking bytes. A
>chosen-plaintext attack on such a system is equivalent to a
>known-plaintext attack. So no, I don't think there is any
>such attack. But if there is, I'd sure like to see it.
>
>Is it possible you're thinking of some variant of RC4 with
>ciphertext or plaintext feedback? I've seen such variants
>proposed, and they're generally *very* weak. There's just
>not enough stuff going on in RC4 to give you any protection
>once you start letting an attacker choose inputs to
>manipulate your RC4 byte permutation state. (This whole
>thing leads me to suspect that it ought to be cheaper to run
>a block cipher in a stream-ciphering mode than to run it in
>a normal block ciphering mode. It just ought to take fewer
>rounds when you only have to worry about known-plaintext
>attacks, if even those.)
>
John,
The attack I was thinking of is to discover the
arrangement of the 256 byte substitution array after
key setup. Since you know the resulting pad bytes
and the start state the only entropy is in the array
itself (a result of random shuffling). Basically
there are two operations that count (the swap
doesn't add strength in this attack scenario).
x = (S[i] + S[j]) mod 256
P = S[x]
P is the final pad byte. x, i, & j are byte sized.
So S[i] and S[j] each have 8 bits of entropy (the
16 I first noticed). S[x] is known but x itself is
probably another 8 bits of entropy. This means that
each P is probably the result of 24 bits of entropy.
At worst doing this for each array element requires
another 8 bits. So the resistance to attack is 32
bits maximum? I suspect that the possible array
patterns narrows fairly quickly by about a third of
the way through the pad bytes. I wonder how much
memory this attack would require?
- Alex
--Alex Alten
Alten@Home.Com Alten@TriStrata.Com
P.O. Box 11406 Pleasanton, CA 94588 USA (925) 417-0159
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:18:28