Re: RC4 broken?
From: Scott Fluhrer (sfluhrer@ix.netcom.com)
Date: 02/02/03
- Next message: Jennifer Williams: "EUGENICS is Back!"
- Previous message: Scott Fluhrer: "Re: Resolved cases in the known IV attack on WEP"
- In reply to: cafe: "RC4 broken?"
- Next in thread: TC: "Re: RC4 broken?"
- Reply: TC: "Re: RC4 broken?"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
From: "Scott Fluhrer" <sfluhrer@ix.netcom.com> Date: Sat, 1 Feb 2003 21:47:27 -0800
cafe <a@b.c.d> wrote in message news:1044159654.56462@teuthos...
> Hi folks
>
> I just read the following from a year-old newsgroup post. It was not in
> sci.crypt, but it was written by someone who posts to sci.crypt:
>
> "RC4 was developed by Ron Rivest in 1987. For fourteen years it withstood
> every known attack. On July 25, 2001 a method was found to crack RC4, but
> only if about a million separate plaintext messages are encrypted with the
> same secret key, and the method fails if two iterations of RC4 are used.
> (Twenty iterations is probably overkill, but considering the speed at
which
> RC4 runs, it doesn't hurt.) Few encryption algorithms have had the
intense
> scrutiny that RC4 has, and until July of 2001 was considered to by a very
> strong cipher."
>
> Can someone explain to me, what he is referring to? I know that with RC4,
> only *two* messages encrypted with the same secret key, are sufficient to
> break all other messages encrypted with that key. As I understand it, that
> it a protocol error - not a break in the cipher. What's with the
"million"?
> What am I missing?
I suspect that whoever wrote this was talking about Ciphersaber, which used
RC4 in a way that made it vulnerable to the attack presented in the paper
http://citeseer.nj.nec.com/fluhrer01weaknesses.html
To encrypt, Ciphersaber takes the long term key, postpends 10 random bytes,
and uses that as the RC4 key. It then sends the 10 random bytes along with
the ciphertext (so that the legitimate receiver can use them to decrypt the
message). And so if we have a million messages encrypted with the same long
term key, we really have a million message encrypted with related RC4 keys
(where we know the long 10 bytes of each key, and although we don't know the
earlier bytes, we know they are consistent between ciphertexts). The paper
showed how we can attack this set up -- if we assume we know the first byte
of plaintext, we can compute the first byte of keystream, and we use a weak
relation between that and the key byte values to reconstruct the long term
key.
Oh, and when the author talkes about "N iterations of RC4", he's talking
about running the RC4 key scheduling N times in a row -- since the attack is
against some weak mixing in the RC4 key schedule, running it multiple times
defeats it.
Just a few corrections to the post:
- The attack was found several months earlier then July 2001 -- we just
hadn't told anyone about it up to that point.
- Against Ciphersaber, the situation is considerably more complex than "you
need a million messages" -- long term keys vary considerably as to their
strength against this attack. A small percentage of keys (approximately
0.1%, IIRC) are extremely weak in the sense that about 20,000 messages
suffice [1]. More keys (approximately 3%, IIRC) become breakable at the
circa 1,000,000 message level, and virtually all keys become breakable at
the 100,000,000 key level -- the full skinny (with the correct values) are
found in the paper.
[1] Amusingly enough, the word (IIRC, it's been a while) "indecipherable"
happens to be one of these extremely weak keys. Of course, I am easily
amused.
-- poncho
- Next message: Jennifer Williams: "EUGENICS is Back!"
- Previous message: Scott Fluhrer: "Re: Resolved cases in the known IV attack on WEP"
- In reply to: cafe: "RC4 broken?"
- Next in thread: TC: "Re: RC4 broken?"
- Reply: TC: "Re: RC4 broken?"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
|
