cryptography, RC4 (also known as ARC4 or ARCFOUR meaning Alleged RC4, see below) is the most widely-used software stream cipherand is used in popular protocols such as Secure Sockets Layer(SSL) (to protect Internet traffic) and WEP (to secure wireless networks). While remarkable for its simplicity and speed in software, RC4 is vulnerable to attacks when the beginning of the output keystreamis not discarded, or a single keystream is used twice; some ways of using RC4 can lead to very insecure cryptosystems such as WEP.
RC4 was designed by
Ron Rivestof RSA Securityin 1987. While it is officially termed "Rivest Cipher 4", the RC acronym is alternatively understood to stand for "Ron's Code" [ [http://people.csail.mit.edu/rivest/faq.html#Ron Rivest FAQ] ] (see also RC2, RC5and RC6).
RC4 was initially a
trade secret, but in September 1994 a description of it was anonymously posted to the Cypherpunksmailing list [cite mailing list |url=http://cypherpunks.venona.com/date/1994/09/msg00304.html |title=Thank you Bob Anderson |date= 1994-09-09|accessdate=2007-05-28 |mailinglist= Cypherpunks] . It was soon posted on the sci.cryptnewsgroup, and from there to many sites on the Internet. The leaked code was confirmed to be genuine as its output was found to match that of proprietary software using licensed RC4. Because the algorithm is known, it is no longer a trade secret. The name "RC4" is trademarked, however. RC4 is often referred to as "ARCFOUR" or "ARC4" (meaning Alleged RC4, because RSA has never officially released the algorithm), to avoid possible trademark problems. It has become part of some commonly used encryption protocols and standards, including WEP and WPA for wireless cards and TLS.
The main factors which helped its deployment over such a wide range of applications consisted in its impressive speed and simplicity. Implementations in both software and hardware are very easy to develop.
RC4 generates a pseudorandom stream of bits (a
keystream) which, for encryption, is combined with the plaintext using bit-wise exclusive-or; decryption is performed the same way (since exclusive-or is a symmetric operation). (This is similar to the Vernam cipherexcept that pseudorandom bits, rather than random bits, are used.) To generate the keystream, the cipher makes use of a secret internal state which consists of two parts:
permutationof all 256 possible bytes(denoted "S" below).
# Two 8-bit index-pointers (denoted "i" and "j").The permutation is initialized with a variable length key, typically between 40 and 256 bits, using the "key-scheduling" algorithm (KSA). Once this has been completed, the stream of bits is generated using the "pseudo-random generation algorithm" (PRGA).
The key-scheduling algorithm (KSA)
The key-scheduling algorithm is used to initialize the permutation in the array "S". "keylength" is defined as the number of bytes in the key and can be in the range 1 ≤ keylength ≤ 256, typically between 5 and 16, corresponding to a
key lengthof 40 – 128 bits. First, the array "S" is initialized to the identity permutation. S is then processed for 256 iterations in a similar way to the main PRGA algorithm, but also mixes in bytes of the key at the same time.
for i from 0 to 255 S [i] := i endfor j := 0 for i from 0 to 255 j := (j + S [i] + key [i mod keylength] ) mod 256 swap(S [i] ,S [j] ) endfor
The pseudo-random generation algorithm (PRGA)
For as many iterations as are needed, the PRGA modifies the state and outputs a byte of the keystream. In each iteration, the PRGA increments "i", adds the value of S pointed to by "i" to "j", exchanges the values of S ["i"] and S ["j"] , and then outputs the value of S at the location S [i] + S [j] (modulo 256). Each value of S is swapped at least once every 256 iterations.
i := 0 j := 0 while GeneratingOutput: i := (i + 1) mod 256 j := (j + S [i] ) mod 256 swap(S [i] ,S [j] ) output S [(S [i] + S [j] ) mod 256] ^ input [i] endwhile
Many stream ciphers are based on
linear feedback shift registers (LFSRs), which while efficient in hardware are less so in software. The design of RC4 avoids the use of LFSRs, and is ideal for software implementation, as it requires only byte manipulations. It uses 256 bytes of memory for the state array, S  through S  , k bytes of memory for the key, key  through key [k-1] , and integer variables, i, j, and k. Performing a "modulus 256" can be done with a bitwise ANDwith 255 (or on most platforms, simple addition of bytes ignoring overflow).
These test vectors are not official, but convenient for anyone testing their own RC4 program. The inputs are
ASCII, the output is in hexadecimal.RC4( "Key", "Plaintext" ) = BBF316E8D940AF0AD3
RC4( "Wiki", "pedia" ) = 1021BF0420
RC4( "Secret", "Attack at dawn" ) = 45A01F645FC35B383552544B9BF5
OR In Plain/Text:Password: Text: Output:RC4( "24g3", "24z0") = nhnWRC4( "24g3", "24z2") = nhnURC4( "5ybdt", "5ybu8") = XJrkp
RC4 falls short of the standards set by cryptographers for a secure cipher in several ways, and thus is not recommended for use in new applications.
Unlike a modern stream cipher (such as those in
eSTREAM), RC4 does not take a separate nonce alongside the key. This means that if a single long-term key is to be used to securely encrypt multiple streams, the cryptosystem must specify how to combine the nonce and the long-term key to generate the stream key for RC4. One approach to addressing this is to generate a "fresh" RC4 key by hashing a long-term key with a nonce. However, many applications that use RC4 simply concatenate key and nonce; RC4's weak key schedulethen gives rise to a variety of serious problems.
Biased Outputs of the RC4
The keystream generated by the RC4 is biased in varying degrees towards certain sequences. The best such attack is due to Itsik Mantin and
Adi Shamirwho showed that the second output byte of the cipher was biased toward zero with high probability. Such bias can be detected by observing only 256 bytes. Souradyuti Pauland Bart Preneelof COSICshowed that the first and the second bytes of the RC4 were also biased. The number of required samples to detect this bias is 225 bytes.
Fluhrer and McGrew also showed such attacks which distinguished the keystream of the RC4 from a random stream given a gigabyte of output. [Scott R. Fluhrer and David A. McGrew, Statistical Analysis of the Alleged RC4 Keystream Generator. FSE 2000, pp19 – 30 [http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/FluhrerMcgrew.pdf (PDF)] ]
Fluhrer, Mantin and Shamir attack
In 2001 a new and surprising discovery was made by Fluhrer, Mantin and Shamir: over all possible RC4 keys, the statistics for the first few bytes of output keystream are strongly non-random, leaking information about the key. If the long-term key and nonce are simply concatenated to generate the RC4 key, this long-term key can be discovered by analysing a large number of messages encrypted with this key. This and related effects were then used to break the WEP ("wired equivalent privacy") encryption used with
802.11 wireless networks. This caused a scramble for a standards-based replacement for WEP in the 802.11 market, and led to the IEEE 802.11ieffort and WPA.
Cryptosystems can defend against this attack by discarding the initial portion of the keystream. Such a modified algorithm is traditionally called "RC4-drop [n] ", where n is the number of initial keystream bytes that are dropped. The SCAN default is n = 768 bytes, but a conservative value would be n = 3072 bytes. [ [http://www.users.zetnet.co.uk/hopwood/crypto/scan/cs.html#RC4-drop "RC4-drop(nbytes)"] in the "Standard Cryptographic Algorithm Naming" database]
In 2005, Andreas Klein presented an analysis of the RC4 stream cipher showing more correlations between the RC4 keystream and the key.
Erik Tews, Ralf-Philipp Weinmann, and Andrei Pyshkinused this analysis to create aircrack-ptw, a tool which cracks 104-bit RC4 used in 128-bit WEP in under a minute [Erik Tews, Ralf-Philipp Weinmann, Andrei Pyshkin. [http://eprint.iacr.org/2007/120 Breaking 104-bit WEP in under a minute] .] Whereas the Fluhrer, Mantin, and Shamir attack used around 10 million messages, aircrack-ptw can break 104-bit keys in 40,000 frames with 50% probability, or in 85,000 frames with 95% probability.
A combinatorial problem related to the number of inputs and outputs of the RC4 cipher was first posed by
Itsik Mantinand Adi Shamirin 2001, whereby, of the total 256 elements in the typical state of RC4, if "x" number of elements ("x" ≤ 256) are "only" known (all other elements can be assumed empty), then the maximum number of elements that can be produced deterministically is also "x" in the next 256 rounds. This conjecture was put to rest in 2004 with a formal proof given by Souradyuti Pauland Bart Preneel.
BitTorrent protocol encryption
* Microsoft Point-to-Point Encryption
Secure Sockets Layer(optionally)
Remote Desktop Client (RDC over RDP)
* Kerberos (optionally)
* SASL Mechanism Digest-MD5 (optionally)
Gpcode.AK, an early June 2008 computer virus for Microsoft Windows, which takes documents hostage for ransomby obscuring them with RC4 and RSA-1024 encryption
Where a cryptosystem is marked with "(optionally)", RC4 is one of several ciphers the system can be configured to use.
eSTREAM- An evaluation of new stream ciphers being conducted by the EU.
* TEA, Block TEA also known as eXtended TEA and Corrected Block TEA - A family of
block ciphers that, like RC4, are designed to be very simple to implement.
Advanced Encryption Standard
* Scott R. Fluhrer, Itsik Mantin and Adi Shamir, Weaknesses in the Key Scheduling Algorithm of RC4.
Selected Areas in Cryptography2001, pp1 – 24 [http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/Rc4_ksa.ps (PS)] .
* Jovan Dj. Golic, Iterative Probabilistic Cryptanalysis of RC4 Keystream Generator. ACISP 2000, pp220 – 233
* Jovan Dj. Golic, Linear Statistical Weakness of Alleged RC4 Keystream Generator.
EUROCRYPT1997, pp226 – 238 [http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/Golic.PDF (PDF)] .
Lars R. Knudsen, Willi Meier, Bart Preneel, Vincent Rijmenand Sven Verdoolaege, Analysis Methods for (Alleged) RC4. ASIACRYPT1998, pp327 – 341 [http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/Knudsen.ps (PS)] .
* Itsik Mantin and
Adi Shamir, A Practical Attack on Broadcast RC4. FSE 2001, pp152 – 164 [http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/bc_rc4.ps (PS)] .
* Serge Mister and
Stafford E. Tavares, Cryptanalysis of RC4-like Ciphers. Selected Areas in Cryptography 1998, pp131 – 143
* Ilya Mironov, (Not So) Random Shuffles of RC4.
CRYPTO2002, pp304 – 319
Souradyuti Pauland Bart Preneel, Analysis of Non-fortuitous Predictive States of the RC4 Keystream Generator. INDOCRYPT2003, pp52 – 67 [http://www.cosic.esat.kuleuven.be/publications/article-86.pdf (PDF)] .
Souradyuti Pauland Bart Preneel, A New Weakness in the RC4 Keystream Generator and an Approach to Improve the Security of the Cipher. Fast Software Encryption- FSE 2004, pp245 – 259 [http://www.cosic.esat.kuleuven.be/publications/article-40.pdf (PDF)] .
* [http://www.mozilla.org/projects/security/pki/nss/draft-kaukonen-cipher-arcfour-03.txt IETF Draft - A Stream Cipher Encryption Algorithm "Arcfour"]
* [http://cypherpunks.venona.com/archive/1994/09/msg00304.html Original posting of RC4 algorithm to Cypherpunks mailing list]
* [http://www.users.zetnet.co.uk/hopwood/crypto/scan/cs.html#RC4 SCAN's entry for RC4]
* [http://www.wisdom.weizmann.ac.il/~itsik/RC4/rc4.html Attacks on RC4]
* [http://research.cyber.ee/~lipmaa/crypto/link/stream/rc4.php RC4 - Cryptology Pointers by Helger Lipmaa]
* [http://www.rsasecurity.com/rsalabs/node.asp?id=2009 RSA Security Response to Weaknesses in Key Scheduling Algorithm of RC4]
* [http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=76258 T-SQL implementation]
"RC4 in WEP"
* [http://www.isaac.cs.berkeley.edu/isaac/wep-faq.html (in)Security of the WEP algorithm]
* [http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/rc4_wep.ps Fluhrer, Mantin, and Shamir attack on WEP (postscript format)]
Wikimedia Foundation. 2010.
Look at other dictionaries:
RC4 — (англ. Rivest Cipher 4 или англ. Ron’s Code, также известен как ARCFOUR или ARC4 (англ. Alleged RC4)) потоковый шифр, широко применяющийся в различных системах защиты информации в компьютерных сетях (например, в протоколах… … Википедия
Rc4 — (auch bekannt als ARC4 oder ARCFOUR) ist eine einfache Stromchiffre. Er wurde 1987 von Ronald L. Rivest (Ron s Code 4) für RSA Data Security Inc. (heute RSA Security) entwickelt und von vielen bekannten Unternehmen und in einer Vielzahl von… … Deutsch Wikipedia
RC4 — RC4, ARC4 oder Arcfour ist eine Stromverschlüsselung, die mit Standards wie HTTPS, SSH 1 und WEP bzw. WPA weite Verbreitung gefunden hat. RC4 (Ron s Code 4) wurde 1987 von Ronald L. Rivest entwickelt, ist eine Marke von RSA Security und offiziell … Deutsch Wikipedia
RC4 — [Abk. für Rivest Cipher 4, dt. »Rivest Verschlüsselung 4«, oder auch für Ron s Code 4], ein 1987 von Ronald L. Rivest für die Firma RSA Data Security Inc. (heute RSA Security) entwickeltes Verfahren zur Datenverschlüsselung. Den zugrunde… … Universal-Lexikon
RC4 — Ne doit pas être confondu avec Route coloniale 4. Schéma d un tour de RC4 RC4 est un algorithme de chiffrement à flot conçu en 1987 par Ronald Rivest, l un des inventeurs du … Wikipédia en Français
RC4 — Diagrama del algoritmo RC4. Dentro de la criptografía RC4 o ARC4 es el sistema de cifrado de flujo Stream cipher más utilizado y se usa en algunos de los protocolos más populares como Transport Layer Security (TLS/SSL) (para proteger el tráfico… … Wikipedia Español
RC4 — Rivest Cypher algorithm version (199)4 Verschlüsselungsalgorithmus mit 128bit Schlüssel, siehe auch RC5 … Acronyms
RC4 — ● ►en sg. np. m. ►CRYPTO Rivest Cypher 4. algorithme de chiffrement en continu à clés symétriques et de longueur variable. Utilisé pour chiffrer des fichiers ainsi que des communications, par exemple via SSL … Dictionnaire d'informatique francophone
RC4 — Rivest Cypher algorithm version (199)4 Verschlüsselungsalgorithmus mit 128bit Schlüssel, siehe auch RC5 … Acronyms von A bis Z
RC4 — abbr. Rivest Cipher / Ron s Code 4 (Verschluesselung) … United dictionary of abbreviations and acronyms