Weaknesses in the Key Scheduling Algorithm of RC4

Lecture notes in computer sciencePublished 1 January 2001

Scott Fluhrer, Itsik Mantin, Adi Shamir

DOI10.1007/3-540-45537-x_1

Source URL

Citations1,040

SJR quartileQ2

SJR score0.35

SNIP0.55

TL;DR

It is shown that RC4 is completely insecure in a common mode of operation which is used in the widely deployed Wired Equivalent Privacy protocol (WEP, which is part of the 802.11 standard), in which a fixed secret key is concatenated with known IV modifiers in order to encrypt different messages.

Abstract

In this paper we present several weaknesses in the key scheduling algorithm of RC4, and describe their cryptanalytic significance. We identify a large number of weak keys, in which knowledge of a small number of key bits suffices to determine many state and output bits with non-negligible probability. We use these weak keys to construct new distinguishers for RC4, and to mount related key attacks with practical complexities. Finally, we show that RC4 is completely insecure in a common mode of operation which is used in the widely deployed Wired Equivalent Privacy protocol (WEP, which is part of the 802.11 standard), in which a fixed secret key is concatenated with known IV modifiers in order to encrypt different messages. Our new passive ciphertext-only attack on this mode can recover an arbitrarily long key in a negligible amount of time which grows only linearly with its size, both for 24 and 128 bit IV modifiers.

Keywords

Computer Science

Lecture notes in computer scienceReal Time Cryptanalysis of A5/1 on a PC

453 Citations2001Alex Biryukov, Adi Shamir +1 more

New attacks on A5/1 are described, which are based on subtle flaws in the tap structure of the registers, their noninvertible clocking mechanism, and their frequent resets, which make it vulnerable to hardware-based attacks by large organizations, but not to software- based attacks on multiple targets by hackers.

Using the Fluhrer, Mantin, and Shamir Attack to Break {WEP}

317 Citations2002Adam Stubblefield, John P. A. Ioannidis +1 more

It is concluded that 802.11 WEP is totally insecure, and some recommendations are provided to make the attack more efficient.

Lecture notes in computer scienceA Practical Attack on Broadcast RC4

240 Citations2002Itsik Mantin, Adi Shamir

A major statistical weakness in RC4 makes it trivial to distinguish between short outputs of RC4 and random strings by analyzing their second bytes, which can be used to mount a practical ciphertext-only attack on RC4 in some broadcast applications.

Lecture notes in computer scienceStatistical Analysis of the Alleged RC4 Keystream Generator

214 Citations2001Scott Fluhrer, David McGrew

A method for distinguishing 8-bit RC4 from randomness is demonstrated and it is observed that an attacker can, on occasion, determine portions of the internal state with nontrivial probability.

View PDF

Lecture notes in computer scienceLinear Statistical Weakness of Alleged RC4 Keystream Generator

135 Citations1997Jovan Dj. Golić

A keystream generator known as RC4 is analyzed by the linear model approach and it is shown that the second binary derivative of the least significant bit output sequence is correlated to 1 with the correlation coefficient close to 15ċ2-3n.

View PDF

Lecture notes in computer scienceAnalysis Methods for (Alleged) RC4

126 Citations1998Lars R. Knudsen, Willi Meier +3 more

The analysis methods reveal intrinsic properties of alleged RC4 which are independent of the key scheduling and the key size, and the complexity of one of the attacks is estimated to be less than the time of searching through the square root of all possible initial states.

Lecture notes in computer scienceCryptanalysis of RC4-like Ciphers

86 Citations1999Serge Mister, S.E. Tavares

This analysis shows that, although the full-size RC4 remains secure against known attacks, keystreams are distinguishable from randomly generated bit streams, and the RC4 key can be recovered if a significant fraction of the full cycle of keystream bits is generated.

View PDF