Attention CipherSaber Users!!
A draft paper by Scott Fluhrer, Itsik Mantin and Adi Shamir was released on July 25, 2001 and announces new attacks on the RC4 cipher that is the basis for CipherSaber-1. Some of these attacks specifically involve the use of an IV with a secret key, the very scheme used in CipherSaber. Prof. Shamir states in an e-mail accompanying the release: "Attached you will find a new paper which describes a truly practical direct attack on WEP's cryptography. It is an extremely powerful attack which can be applied even when WEP's RC4 stream cipher uses a 2048 bit secret key (its maximal size) and 128 bit IV modifiers (as proposed in WEP2). The attacker can be a completely passive eavesdropper (i.e., he does not have to inject packets, monitor responses, or use accomplices) and thus his existence is essentially undetectable. It is a pure known-ciphertext attack (i.e., the attacker need not know or choose their corresponding plaintexts). After scanning several hundred thousand packets, the attacker can completely recover the secret key and thus decrypt all the ciphertexts. The running time of the attack grows linearly instead of exponentially with the key size, and thus it is negligible even for 2048 bit keys." The paper itself, titled "Weaknesses in the Key Scheduling Algorithm of RC4," has been posted at http://www.eyetap.org/~rguerra/toronto2001/rc4_ksaproc.pdf (in PDF format) and at http://www.crypto.com/papers/others/rc4_ksaproc.ps (in Postscript). WEP is an encryption system used with 802.11 wireless Ethernet that employs RC4, but the attack affects CipherSaber as well. Note that "several hundred thousand" separate CipherSaber messages encrypted with the same key would have to be collected for this attack to succeed. None the less, from a cryptographic standpoint, this is too close for comfort. Accordingly I recommend that CipherSaber users switch to CipherSaber-2 with a parameter N=20 or larger. The RC4 state vector will thus be mixed 20 times instead of once. This large a value for N is probably overkill, but until there is time to fully digest the implications of this paper, it is better to err on the safe side. If this is impractical for any reason, I recommend changing keys on a regular basis to limit the amount of traffic encrypted with any one CipherSaber key (even though the IVs differ). If and when a consensus develops on the best way to fix RC4, I will announce a corresponding version of CipherSaber. Visit the CipherSaber page http://ciphersaber.gurus.com periodically for updated information. Arnold Reinhold
-- On 27 Jul 2001, at 11:33, Arnold G. Reinhold wrote:
A draft paper by Scott Fluhrer, Itsik Mantin and Adi Shamir was released on July 25, 2001 and announces new attacks on the RC4 cipher that is the basis for CipherSaber-1. Some of these attacks specifically involve the use of an IV with a secret key, the very scheme used in CipherSaber. Prof. Shamir states in an e-mail accompanying the release:
If I understand the paper http://www.eyetap.org/~rguerra/toronto2001/rc4_ksaproc.pdf correctly, Cybersabre and WEP would be fixed if instead of making the RC4 initialization by concatenating a permanent and unchanging secret key, and an ever changing visible random value, they instead constructed the RC4 key by doing several different SHA hashes of the unchanging secret key, and the ever changing visible random value, and concatenated those hashes, and also discarded some substantial number of initial bytes from the RC4 output. --digsig James A. Donald 6YeGpsZR+nOTh/cGwvITnSR3TdzclVpR0+pr3YYQdkG xXgj5w0VTwI81xCh6amG5KOaB6nNDXD/mS2s7VXR 4vvEsQrjo5uE2RHZQa/1atZPduIFyneZNWgzOS40c --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majordomo@wasabisystems.com
The fix that's been suggested for some time in the common wisdom about RC4, namely discarding the first 256 bytes of output, would seem to be entirely adequate to address the problems discovered. If this is considered to be part of the key setup, it slightly less than doubles the time, and it's extremely simple. I have always felt that folding in the key with only a single pass was a bit "close to the edge". Note that the RC5 *key schedule* does at least three passes! (Not strictly comparable, of course.) Another alternative suggests itself, which would be to continue the key-based randomisation for a second pass over the state array. I'd worry about weak keys that somehow undid their own actions, though, so I think I still prefer just letting the randomisation-through-generation continue. Greg. At 01:20 PM 7/28/2001 -0700, jamesd@echeque.com wrote:
-- On 27 Jul 2001, at 11:33, Arnold G. Reinhold wrote:
A draft paper by Scott Fluhrer, Itsik Mantin and Adi Shamir was released on July 25, 2001 and announces new attacks on the RC4 cipher that is the basis for CipherSaber-1. Some of these attacks specifically involve the use of an IV with a secret key, the very scheme used in CipherSaber. Prof. Shamir states in an e-mail accompanying the release:
If I understand the paper http://www.eyetap.org/~rguerra/toronto2001/rc4_ksaproc.pdf correctly, Cybersabre and WEP would be fixed if instead of making the RC4 initialization by concatenating a permanent and unchanging secret key, and an ever changing visible random value, they instead constructed the RC4 key by doing several different SHA hashes of the unchanging secret key, and the ever changing visible random value, and concatenated those hashes, and also discarded some substantial number of initial bytes from the RC4 output.
--digsig James A. Donald 6YeGpsZR+nOTh/cGwvITnSR3TdzclVpR0+pr3YYQdkG xXgj5w0VTwI81xCh6amG5KOaB6nNDXD/mS2s7VXR 4vvEsQrjo5uE2RHZQa/1atZPduIFyneZNWgzOS40c
--------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majordomo@wasabisystems.com
Greg Rose INTERNET: ggr@qualcomm.com Qualcomm Australia VOICE: +61-2-9817 4188 FAX: +61-2-9817 5199 Level 3, 230 Victoria Road, http://people.qualcomm.com/ggr/ Gladesville NSW 2111 232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majordomo@wasabisystems.com
Rumor has it that it does cross over the edge. - Alex At 08:09 AM 7/29/2001 +1000, Greg Rose wrote: ...
I have always felt that folding in the key with only a single pass was a bit "close to the edge". Note that the RC5 *key schedule* does at least three passes! (Not strictly comparable, of course.)
... -- Alex Alten Alten@Home.Com
participants (4)
-
Alex Alten -
Arnold G. Reinhold -
Greg Rose -
jamesd＠echeque.com