RC4 for Authentication and Encryption

From: Giorgio Tani (giorgio.tani_at_email.it)
Date: 04/27/05 

Date: 27 Apr 2005 08:52:01 -0700

Excuse me for posting in that way, Google Groups seem to have
something strange...

>David Wagner wrote:
>I'm puzzled. RC4 doesn't normally have an IV. WEP tried to
>add an IV, but they did so in a in a way that was susceptible to
>Fluhrer-Mantin-Shamir attacks, so I always get a little worried
>when people talk about adding an IV to RC4.
>Also, Random isn't a crypto-strength pseudorandom number generator.
Maybe he is referring to Ciphersaber or Ciphersaber-2 style in adding
IV to RC4, AFAIK boot are still susceptible to Fluhrer-Mantin-Shamir
attacks, but Cs-2 seem ways harder.
Another interesting way in combining IV with key in a nonlinear way,
without adding code for, in example, hashing or so, is the way used by
Zoltak in VMPC KSA (run KSA with IV as key, then run KSA with the real
key), that seem not to be susceptible to Fluhrer-Mantin-Shamir
attacks, however if he want to keep compatibility with Cs and Cs-2 KSA
this method will be not suitable.
Generally in IV-salted RC4 implementation the IV have just to be
unique, it's not necessary to keep the IV secret and it's not needed
to be random, so even a plain counter shoul be fine and the weakness
of Random as crypto RNG shouldn't be a problem to generate (with high
probability) an unique IV.

>I guess this means you have no message authentication, and will be
>susceptible to bit-flipping and other attacks on message integrity.
>That is risky. See, e.g., WEP for some of the dangers here as well.
>Do you have to use RC4? Can you use some block cipher that is
>well-suited for embedded platforms? Skipjack, AES, RC5, DES, TEA?
That's true, maybe AES is still the best option (because is so widely
known and studied and exists may working reference implementations)
for protecting against those attacks; TEA (or XTEA) would also be an
interesting choiche because of the tyniness of the code to implement,
it would be an elegant and easy to implement solution.
BTW, in a mine work of last september (searck my name and Kyu on the
web) I implemented also some RC4-like algorithms (warning, they are
still at level of proof of concept even if i implemented it in a
working application) that alter in a non linear way the internal state
of the function depending the previously decrypted byte and/or (I
coded many algorithms) chose between different ways in calculating the
output of the next byte.
The good is that a single bit alteration can generate a random
alteration in the function, making really difficult to stop the
propagation of alterations from that point to the end of the stream
(the output from the point of the alteration to the end of the stream,
deciphering an altered ciphertext, pass Diehard tests).
The bad is that it's clearly still at level of proof of concept (so
I'm not going to suggest it to the writer) and so I haven't
implemented yet a condition that intercept any of the 255 possible
differences between byte values (and it woul not be so "light")... so
the concept is the same, but the implementation will not intercept all
possible alterations.

Relevant Pages

  • Re: Some thoughts about ways to use RC4
    ... While this is easy to implement for encryption, ... >more difficult for the attacker: ... any alteration at all is useful. ... distinguishing attack against RC4, but it just ...
    (sci.crypt)
  • Re: Limiting RC4 to "40 bit" strength
    ... Bill Unruh wrote: ... Since no attacks on RC4 ... RC4...". ... Greg Rose ...
    (sci.crypt)
  • Re: Limiting RC4 to "40 bit" strength
    ... ]<ggr@qualcomm.com (Gregory G Rose) writes: ... Since no attacks on RC4 ...
    (sci.crypt)
  • Re: RC4 - discard first n bytes
    ... ...which means that for RC4 chosen-plaintext attacks and known- ... plaintext attacks are the exact same attack. ... >output of RC4 rather than using it to encrypt some text and ... Do you have an "impossible" engineering project that only someone like Doc Brown can solve? ...
    (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)