Re: RC4 broken?

From: Bill Unruh (unruh@string.physics.ubc.ca)
Date: 02/04/03 

From: unruh@string.physics.ubc.ca (Bill Unruh)
Date: 4 Feb 2003 18:19:17 GMT

"WinTerMiNator" <winterminator@no_spam.chez.com> writes:

]"Yama" <Yama@yomama.com> a écrit dans le message de news:
]kj7r3voc85t9n13epr16363g4c2i3toh0q@4ax.com...
]> On Sun, 2 Feb 2003 22:37:45 +0100, "WinTerMiNator"
]> <winterminator@no_spam.chez.com> wrote:
]>
]> >----- Original Message -----
]> >From: "Scott Fluhrer" <sfluhrer@ix.netcom.com>
]> >Newsgroups: sci.crypt
]> >Sent: Sunday, February 02, 2003 7:08 PM
]> >Subject: Re: RC4 broken?
]> >
]> >[...]
]> >
]> >> Well, no. What can be said is that RC4 is weak against related key
]> >attacks
]> >> (unless you drop a sufficiently large amount of initial keystream) --
]if
]> >you
]> >> use RC4 in a way that avoids this weakness, it is still believed to be
]> >> strong (that is, not known to be weak). In essence, this is another
]part
]> >of
]> >> the "cryptographical hygiene" you need to follow if you use RC4.
]> >
]> >Hello,
]> >
]> >Do you mean that "running the RC4 key scheduling N times in a row " as
]done
]> >in Cipher Saber 2 makes RC4 safe against both "weak keys" and "related
]keys
]> >attack"? (In other terms, when you collect millions messages ciphered
]with
]> >the same "long term key", if RC4 has been used with N>20 you have no
]longer
]> >the weak relation between guessed beginning of the message and the key
]bytes
]> >value).
]> >
]> <snip>
]>
]> The key scheduling N times is NOT what Scott Fluhrer is talking about,
]> and I would think after all the information published about proper
]> hygiene for RC4 that Arnold Reinhold would change the frickin
]> information on his site (www.Ciphersaber,Gurus.com).
]>
]> He persists on "upping" the key mixing number, and Fluhrer is making
]> mincemeat of Cipersaber, while telling anyone who'll clue in that
]> increasing key mixing is NOT the way to go, but dropping bytes IS the
]> way to go. Meanwhile Reinhold goes to 2, 10 and now 20 times to mix
]> the dang key... !!!
]>
]> I like the Ciphersaber philosophy, and I wish Arnold Reinhold would
]> fix it by posting the proper hygiene technique on his site.

]Hello,

]Don't you think that you arrive to the same result? while you increase key
]mixing, bytes that would have normally be used are discarded.

]It may be shorter to discard 256 bytes than to do 20 rounds of key mixing,
]but in what key mixing would be worse than bytes discarding, in what regards
]security?

Because RC4 is know to be biased in its first few rounds. Thus the first
n bytes should be discarded, no matter how you use RC4 or how you select
the key.

Let me give an extreme example. Lets say that in the first 256 rounds
RC4 simply spewed out the key. Clearly no matter how strong the key was,
those first few rounds would make that irrelevant. And discarding those
first 256 rounds would make it far stronger, no matter what the key was.
Thus key mixing would be completely irrelevant, and would be far worse
than discarding the first 256 bytes. The argument is that RC4 is not
that extreme, but that the first number of bytes does give too much
information that could be used to attack the cypher.

Relevant Pages

  • Re: Limiting RC4 to "40 bit" strength
    ... ]> RC4 output XORed with random data helps him. ... discarding an initial segment of ... ]a useful measure of improving the quality of output of RC4 ...
    (sci.crypt)
  • Re: RC4 Drop
    ... What you have to do is simply to run the RC4 for a while without ... xoring the output bytes with the plaintext, ... discarding n bytes is very quick, discarding at least 256 output bytes ... key for the KSA. ...
    (sci.crypt)
  • Re: Limiting RC4 to "40 bit" strength
    ... > plaintext and discarding it at the other end is just as good, ... > RC4 output XORed with random data helps him. ... discarding an initial segment of ...
    (sci.crypt)
  • Re: Limiting RC4 to "40 bit" strength
    ... >> only one, I'd mildly prefer hashing. ... Here is a reference to a paper that I've seen discussed several times ... in sci-crypt with respect to discarding bytes in RC4: ...
    (sci.crypt)
  • Re: RC4 broken?
    ... What can be said is that RC4 is weak against related key ... > increasing key mixing is NOT the way to go, ... > I like the Ciphersaber philosophy, and I wish Arnold Reinhold would ... It may be shorter to discard 256 bytes than to do 20 rounds of key mixing, ...
    (sci.crypt)