Re: RC4 Drop

From: Giorgio Tani (giorgio.tani_at_email.it)
Date: 11/30/04 

Date: 30 Nov 2004 01:44:42 -0800

"RR" <newspaper.20.broom@spamgourmet.com> wrote in message news:<2qPqd.53019$K7.15294@news-server.bigpond.net.au>...
...
> Having read that thread and the articles it pointed to, I was still confused
> about what exactly you're supposed to drop.
...
> Is that how RC4 drop is supposed to work?
The problem is quite simple but puzzled me too for a while, so don't
worry, I'm not going laugh!
What you have to do is simply to run the RC4 for a while without
xoring the output bytes with the plaintext, then start xoring as
usual.
In decription you start the RC4 without xoring the output with the
ciphertext for the same amount of bytes, then start xoring as usual.
The use of IV is not affected by this, since you can simply prepend
the IV to the output cyphertext while encrypting and read it before
decrypting, as you would usually do.
The amount of RC4 output to discard is still questioned, more biased
bytes are more probable at the beginning of the stream. However since
discarding n bytes is very quick, discarding at least 256 output bytes
(the same size of the RC4 S-box)is considered the minimum but
discarding some times this value (up to 8 times) is considered better.
Using a variable number of bytes to discard is not usually considered
a significative way to make the cypher strongher, is rather considered
a "good" way to mess up the possibility of comunication between
unskilled users! ;)
Since you are interested to RC4 "hygene" you should even consider the
problem of IV-related weakness: if you use the same key for
unreasonably many messages the IV may be (hardly) exploited, to avoid
even this potential flaw you should not combine the IV to the key in a
simple way like doing in CipherSaber and other easy to memorize
implementation (post/pre-pending to the key, xor, add or so on), you
should combine key and IV using a strong hashing, or consider the
(IMHO very interesting) solution used by Zoltak in VMPC keying: first
use the key for the usual Key Scheduling Algorithm, then use the IV as
key for the KSA.
You will run the KSA two times (and it's fast) and you'll have an
initial state for RC4 box that depend boot from the key and the IV in
a non linear and non easy to invert way.
Zoltak uses a different KSA but the principle is the same, the
combination resulting between key and IV is not linear and not
exploitable with known means, and this is a (IMHO) good compromise
between simplicity and security. However this method is quite
experimental for now!
I think you can find a lot of interesting links and posts about RC4 in
sci.crypt.*, if you like delphi/pascal you can even visit my page
about RC4 and modification at
http://giorgiotani.interfree.it/s_kyu.html remembering that the
algorithms featured are still EXPERIMENTAL and for now shouldn't be
used for real life products and that certainly you can find more
exaustive and well written texts about RC4 and further developements
and modifications!

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 broken?
    ... What can be said is that RC4 is weak against related key ... ]> increasing key mixing is NOT the way to go, ... ]but in what key mixing would be worse than bytes discarding, ... Because RC4 is know to be biased in its first few rounds. ...
    (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)
  • RC4 for Authentication and Encryption
    ... RC4 doesn't normally have an IV. WEP tried to ... Zoltak in VMPC KSA (run KSA with IV as key, then run KSA with the real ... attacks, however if he want to keep compatibility with Cs and Cs-2 KSA ... The good is that a single bit alteration can generate a random ...
    (sci.crypt)