Spritz (cipher)
   HOME

TheInfoList



OR:

In
cryptography Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...
, RC4 (Rivest Cipher 4, also known as ARC4 or ARCFOUR, meaning Alleged RC4, see below) is a
stream cipher stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream (keystream). In a stream cipher, each plaintext digit is encrypted one at a time with the corresponding digit of the keystream ...
. While it is remarkable for its simplicity and speed in software, multiple vulnerabilities have been discovered in RC4, rendering it insecure. It is especially vulnerable when the beginning of the output
keystream In cryptography, a keystream is a stream of random or pseudorandom characters that are combined with a plaintext message to produce an encrypted message (the ciphertext). The "characters" in the keystream can be bits, bytes, numbers or actual cha ...
is not discarded, or when nonrandom or related keys are used. Particularly problematic uses of RC4 have led to very insecure
protocol Protocol may refer to: Sociology and politics * Protocol (politics), a formal agreement between nation states * Protocol (diplomacy), the etiquette of diplomacy and affairs of state * Etiquette, a code of personal behavior Science and technolog ...
s such as WEP. , there is speculation that some state cryptologic agencies may possess the capability to break RC4 when used in the TLS protocol.
IETF The Internet Engineering Task Force (IETF) is a standards organization for the Internet and is responsible for the technical standards that make up the Internet protocol suite (TCP/IP). It has no formal membership roster or requirements and a ...
has published RFC 7465 to prohibit the use of RC4 in TLS;
Mozilla Mozilla (stylized as moz://a) is a free software community founded in 1998 by members of Netscape. The Mozilla community uses, develops, spreads and supports Mozilla products, thereby promoting exclusively free software and open standards, wi ...
and
Microsoft Microsoft Corporation is an American multinational technology corporation producing computer software, consumer electronics, personal computers, and related services headquartered at the Microsoft Redmond campus located in Redmond, Washing ...
have issued similar recommendations. A number of attempts have been made to strengthen RC4, notably Spritz, RC4A, VMPC, and RC4+.


History

RC4 was designed by
Ron Rivest Ronald Linn Rivest (; born May 6, 1947) is a cryptographer and an Institute Professor at MIT. He is a member of MIT's Department of Electrical Engineering and Computer Science (EECS) and a member of MIT's Computer Science and Artificial Intell ...
of
RSA Security RSA Security LLC, formerly RSA Security, Inc. and doing business as RSA, is an American computer and network security company with a focus on encryption and encryption standards. RSA was named after the initials of its co-founders, Ron Rive ...
in 1987. While it is officially termed "Rivest Cipher 4", the RC acronym is alternatively understood to stand for "Ron's Code" (see also
RC2 In cryptography, RC2 (also known as ARC2) is a symmetric-key block cipher designed by Ron Rivest in 1987. "RC" stands for "Ron's Code" or "Rivest Cipher"; other ciphers designed by Rivest include RC4, RC5, and RC6. The development of RC2 wa ...
, RC5 and
RC6 In cryptography, RC6 (Rivest cipher 6) is a symmetric key block cipher derived from RC5. It was designed by Ron Rivest, Matt Robshaw, Ray Sidney, and Yiqun Lisa Yin to meet the requirements of the Advanced Encryption Standard (AES) competition. ...
). RC4 was initially a
trade secret Trade secrets are a type of intellectual property that includes formulas, practices, processes, designs, instruments, patterns, or compilations of information that have inherent economic value because they are not generally known or readily asc ...
, but in September 1994, a description of it was anonymously posted to the
Cypherpunk A cypherpunk is any individual advocating widespread use of strong cryptography and privacy-enhancing technologies as a route to social and political change. Originally communicating through the Cypherpunks electronic mailing list, informal g ...
s mailing list. It was soon posted on the sci.crypt
newsgroup A Usenet newsgroup is a repository usually within the Usenet system, for messages posted from users in different locations using the Internet. They are discussion groups and are not devoted to publishing news. Newsgroups are technically distinct ...
, where it was broken within days by
Bob Jenkins Robert F. Jenkins (September 4, 1947 – August 9, 2021) was an American television and radio sports announcer, primarily calling Indy car and NASCAR telecasts for ESPN/ABC and later Versus/NBCSN. Jenkins was the radio "Voice of the Indianapoli ...
. From there, it spread 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, so RC4 is often referred to as ''ARCFOUR'' or ''ARC4'' (meaning ''alleged RC4'') to avoid trademark problems.
RSA Security RSA Security LLC, formerly RSA Security, Inc. and doing business as RSA, is an American computer and network security company with a focus on encryption and encryption standards. RSA was named after the initials of its co-founders, Ron Rive ...
has never officially released the algorithm; Rivest has, however, linked to the
English Wikipedia The English Wikipedia is, along with the Simple English Wikipedia, one of two English-language editions of Wikipedia, an online encyclopedia. It was founded on January 15, 2001, as Wikipedia's first edition, and, as of , has the most arti ...
article on RC4 in his own course notes in 2008 and confirmed the history of RC4 and its code in a 2014 paper by him. RC4 became part of some commonly used encryption protocols and standards, such as WEP in 1997 and
WPA WPA may refer to: Computing *Wi-Fi Protected Access, a wireless encryption standard *Windows Product Activation, in Microsoft software licensing * Wireless Public Alerting (Alert Ready), emergency alerts over LTE in Canada * Windows Performance An ...
in 2003/2004 for wireless cards; and SSL in 1995 and its successor TLS in 1999, until it was prohibited for all versions of TLS by RFC 7465 in 2015, due to the RC4 attacks weakening or breaking RC4 used in SSL/TLS. The main factors in RC4's success over such a wide range of applications have been its speed and simplicity: efficient implementations in both software and hardware were very easy to develop.


Description

RC4 generates a pseudorandom stream of bits (a
keystream In cryptography, a keystream is a stream of random or pseudorandom characters that are combined with a plaintext message to produce an encrypted message (the ciphertext). The "characters" in the keystream can be bits, bytes, numbers or actual cha ...
). As with any stream cipher, these can be used for encryption by combining it with the plaintext using bitwise
exclusive or Exclusive or or exclusive disjunction is a logical operation that is true if and only if its arguments differ (one is true, the other is false). It is symbolized by the prefix operator J and by the infix operators XOR ( or ), EOR, EXOR, , ...
; decryption is performed the same way (since exclusive or with given data is an
involution Involution may refer to: * Involute, a construction in the differential geometry of curves * '' Agricultural Involution: The Processes of Ecological Change in Indonesia'', a 1963 study of intensification of production through increased labour inpu ...
). This is similar to the
one-time pad In cryptography, the one-time pad (OTP) is an encryption technique that cannot be cracked, but requires the use of a single-use pre-shared key that is not smaller than the message being sent. In this technique, a plaintext is paired with a ran ...
, except that generated ''pseudorandom bits'', rather than a prepared stream, are used. To generate the keystream, the cipher makes use of a secret internal state which consists of two parts: # A
permutation In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or proc ...
of all 256 possible
bytes The byte is a unit of digital information that most commonly consists of eight bits. Historically, the byte was the number of bits used to encode a single character of text in a computer and for this reason it is the smallest addressable uni ...
(denoted "S" below). # Two 8-bit index-pointers (denoted "i" and "j"). The permutation is initialized with a variable-length
key Key or The Key may refer to: Common meanings * Key (cryptography), a piece of information that controls the operation of a cryptography algorithm * Key (lock), device used to control access to places or facilities restricted by a lock * Key (map ...
, typically between 40 and 2048 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).


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 length In cryptography, key size, key length, or key space refer to the number of bits in a key used by a cryptographic algorithm (such as a cipher). Key length defines the upper-bound on an algorithm's security (i.e. a logarithmic measure of the faste ...
of 40–128 bits. First, the array "S" is initialized to the
identity permutation In mathematics, a permutation group is a group ''G'' whose elements are permutations of a given set ''M'' and whose group operation is the composition of permutations in ''G'' (which are thought of as bijective functions from the set ''M'' to it ...
. S is then processed for 256 iterations in a similar way to the main PRGA, but also mixes in bytes of the key at the same time. for i from 0 to 255 S := i endfor j := 0 for i from 0 to 255 j := (j + S + key
mod Mod, MOD or mods may refer to: Places * Modesto City–County Airport, Stanislaus County, California, US Arts, entertainment, and media Music * Mods (band), a Norwegian rock band * M.O.D. (Method of Destruction), a band from New York City, US ...
keylength]) mod 256 swap values of S and S endfor


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 ; * looks up the th element of , , and adds that to ; * exchanges the values of and , then uses the sum as an index to fetch a third element of (the keystream value below); * then bitwise exclusive ORed (
XOR Exclusive or or exclusive disjunction is a logical operation that is true if and only if its arguments differ (one is true, the other is false). It is symbolized by the prefix operator J and by the infix operators XOR ( or ), EOR, EXOR, , ...
ed) with the next byte of the message to produce the next byte of either ciphertext or plaintext. Each element of S is swapped with another element at least once every 256 iterations. i := 0 j := 0 while GeneratingOutput: i := (i + 1) mod 256 j := (j + S mod 256 swap values of S and S K := S +_S +_S[j">S_+_S[j_mod_256.html" ;"title=".html" ;"title="S + S[j">S + S[j mod 256">.html" ;"title="S + S[j">S + S[j mod 256 output K endwhile Thus, this produces a stream of which are
XOR Exclusive or or exclusive disjunction is a logical operation that is true if and only if its arguments differ (one is true, the other is false). It is symbolized by the prefix operator J and by the infix operators XOR ( or ), EOR, EXOR, , ...
ed with the to obtain the . So .


RC4-based random number generators

Several operating systems include , an API originating in OpenBSD security features, OpenBSD providing access to a random number generator originally based on RC4. In OpenBSD 5.5, released in May 2014, was modified to use
ChaCha20 Salsa20 and the closely related ChaCha are stream ciphers developed by Daniel J. Bernstein. Salsa20, the original cipher, was designed in 2005, then later submitted to the eSTREAM European Union cryptographic validation process by Bernstein. Ch ...
. The implementations of arc4random in
FreeBSD FreeBSD is a free and open-source Unix-like operating system descended from the Berkeley Software Distribution (BSD), which was based on Research Unix. The first version of FreeBSD was released in 1993. In 2005, FreeBSD was the most popular ...
,
NetBSD NetBSD is a free and open-source Unix operating system based on the Berkeley Software Distribution (BSD). It was the first open-source BSD descendant officially released after 386BSD was forked. It continues to be actively developed and is a ...
and
Linux Linux ( or ) is a family of open-source Unix-like operating systems based on the Linux kernel, an operating system kernel first released on September 17, 1991, by Linus Torvalds. Linux is typically packaged as a Linux distribution, which ...
's libbsd also use ChaCha20. According to manual pages shipped with the operating system, in the 2017 release of
macOS macOS (; previously OS X and originally Mac OS X) is a Unix operating system developed and marketed by Apple Inc. since 2001. It is the primary operating system for Apple's Mac computers. Within the market of desktop and lapt ...
and
iOS iOS (formerly iPhone OS) is a mobile operating system created and developed by Apple Inc. exclusively for its hardware. It is the operating system that powers many of the company's mobile devices, including the iPhone; the term also includes ...
operating systems, Apple replaced RC4 with AES in its implementation of arc4random.
Man page A man page (short for manual page) is a form of software documentation usually found on a Unix or Unix-like operating system. Topics covered include computer programs (including library and system calls), formal standards and conventions, and ev ...
s for the new arc4random include the
backronym A backronym is an acronym formed from an already existing word by expanding its letters into the words of a phrase. Backronyms may be invented with either serious or humorous intent, or they may be a type of false etymology or folk etymology. The ...
"A Replacement Call for Random" for ARC4 as a mnemonic, as it provides better random data than
rand() A pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG), is an algorithm for generating a sequence of numbers whose properties approximate the properties of sequences of random numbers. The PRNG-generate ...
does. Proposed new random number generators are often compared to the RC4 random number generator. Several attacks on RC4 are able to distinguish its output from a random sequence.


Implementation

Many stream ciphers are based on
linear-feedback shift register In computing, a linear-feedback shift register (LFSR) is a shift register whose input bit is a linear function of its previous state. The most commonly used linear function of single bits is exclusive-or (XOR). Thus, an LFSR is most often a sh ...
s (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 55 k bytes of memory for the key, key through key
−1 In mathematics, −1 (also known as negative one or minus one) is the additive inverse of 1, that is, the number that when added to 1 gives the additive identity element, 0. It is the negative integer greater than negative two (−2) and less t ...
and integer variables, i, j, and K. Performing a modular reduction of some value modulo 256 can be done with a
bitwise AND In computer programming, a bitwise operation operates on a bit string, a bit array or a binary numeral (considered as a bit string) at the level of its individual bits. It is a fast and simple action, basic to the higher-level arithmetic oper ...
with 255 (which is equivalent to taking the low-order byte of the value in question).


Test vectors

These test vectors are not official, but convenient for anyone testing their own RC4 program. The keys and plaintext are
ASCII ASCII ( ), abbreviated from American Standard Code for Information Interchange, is a character encoding standard for electronic communication. ASCII codes represent text in computers, telecommunications equipment, and other devices. Because of ...
, the keystream and ciphertext are in
hexadecimal In mathematics and computing, the hexadecimal (also base-16 or simply hex) numeral system is a positional numeral system that represents numbers using a radix (base) of 16. Unlike the decimal system representing numbers using 10 symbols, hexa ...
.


Security

Unlike a modern stream cipher (such as those in
eSTREAM eSTREAM is a project to "identify new stream ciphers suitable for widespread adoption", organised by the EU ECRYPT network. It was set up as a result of the failure of all six stream ciphers submitted to the NESSIE project. The call for primiti ...
), 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 protocol 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 Hash, hashes, hash mark, or hashing may refer to: Substances * Hash (food), a coarse mixture of ingredients * Hash, a nickname for hashish, a cannabis product Hash mark * Hash mark (sports), a marking on hockey rinks and gridiron football fiel ...
a long-term key with a nonce. However, many applications that use RC4 simply concatenate key and nonce; RC4's weak
key schedule In cryptography, the so-called product ciphers are a certain kind of cipher, where the (de-)ciphering of data is typically done as an iteration of ''rounds''. The setup for each round is generally the same, except for round-specific fixed valu ...
then gives rise to
related-key attack In cryptography, a related-key attack is any form of cryptanalysis where the attacker can observe the operation of a cipher under several different keys whose values are initially unknown, but where some mathematical relationship connecting the k ...
s, like the
Fluhrer, Mantin and Shamir attack In cryptography, the Fluhrer, Mantin and Shamir attack is a stream cipher attack on the widely used RC4 stream cipher. The attack allows an attacker to recover the key in an RC4 encrypted stream from a large number of messages in that stream. The ...
(which is famous for breaking the WEP standard). Because RC4 is a
stream cipher stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream (keystream). In a stream cipher, each plaintext digit is encrypted one at a time with the corresponding digit of the keystream ...
, it is more
malleable Ductility is a mechanical property commonly described as a material's amenability to drawing (e.g. into wire). In materials science, ductility is defined by the degree to which a material can sustain plastic deformation under tensile stres ...
than common
block cipher In cryptography, a block cipher is a deterministic algorithm operating on fixed-length groups of bits, called ''blocks''. Block ciphers are specified cryptographic primitive, elementary components in the design of many cryptographic protocols and ...
s. If not used together with a strong
message authentication code In cryptography, a message authentication code (MAC), sometimes known as a ''tag'', is a short piece of information used for authenticating a message. In other words, to confirm that the message came from the stated sender (its authenticity) and ...
(MAC), then encryption is vulnerable to a
bit-flipping attack A bit-flipping attack is an attack on a cryptographic cipher in which the attacker can change the ciphertext in such a way as to result in a predictable change of the plaintext In cryptography, plaintext usually means unencrypted information ...
. The cipher is also vulnerable to a
stream cipher attack Stream ciphers, where plaintext bits are combined with a cipher bit stream by an exclusive-or operation ( xor), can be very secure if used properly. However, they are vulnerable to attacks if certain precautions are not followed: *keys must neve ...
if not implemented correctly. It is noteworthy, however, that RC4, being a stream cipher, was for a period of time the only common cipher that was immune to the 2011 BEAST attack on TLS 1.0. The attack exploits a known weakness in the way cipher-block chaining mode is used with all of the other ciphers supported by TLS 1.0, which are all block ciphers. In March 2013, there were new attack scenarios proposed by Isobe, Ohigashi, Watanabe and Morii, as well as AlFardan, Bernstein, Paterson, Poettering and Schuldt that use new statistical biases in RC4 key table to recover plaintext with large number of TLS encryptions. The use of RC4 in TLS is prohibited by RFC 7465 published in February 2015.


Roos' biases and key reconstruction from permutation

In 1995, Andrew Roos experimentally observed that the first byte of the keystream is correlated with the first three bytes of the key, and the first few bytes of the permutation after the KSA are correlated with some linear combination of the key bytes. These biases remained unexplained until 2007, when Goutam Paul, Siddheshwar Rathi and Subhamoy Maitra proved the keystream–key correlation and, in another work, Goutam Paul and Subhamoy Maitra proved the permutation–key correlations. The latter work also used the permutation–key correlations to design the first algorithm for complete key reconstruction from the final permutation after the KSA, without any assumption on the key or
initialization vector In cryptography, an initialization vector (IV) or starting variable (SV) is an input to a cryptographic primitive being used to provide the initial state. The IV is typically required to be random or pseudorandom, but sometimes an IV only needs to ...
. This algorithm has a constant probability of success in a time, which is the square root of the exhaustive key search complexity. Subsequently, many other works have been performed on key reconstruction from RC4 internal states. Subhamoy Maitra and Goutam Paul also showed that the Roos-type biases still persist even when one considers nested permutation indices, like or . These types of biases are used in some of the later key reconstruction methods for increasing the success probability.


Biased outputs of the RC4

The keystream generated by the RC4 is biased to varying degrees towards certain sequences, making it vulnerable to
distinguishing attack In cryptography, a distinguishing attack is any form of cryptanalysis on data encrypted by a cipher that allows an attacker to distinguish the encrypted data from random data. Modern symmetric-key ciphers are specifically designed to be immune to ...
s. The best such attack is due to Itsik Mantin and
Adi Shamir Adi Shamir ( he, עדי שמיר; born July 6, 1952) is an Israeli cryptographer. He is a co-inventor of the Rivest–Shamir–Adleman (RSA) algorithm (along with Ron Rivest and Len Adleman), a co-inventor of the Feige–Fiat–Shamir identifi ...
, who showed that the second output byte of the cipher was biased toward zero with probability 1/128 (instead of 1/256). This is due to the fact that if the third byte of the original state is zero, and the second byte is not equal to 2, then the second output byte is always zero. Such bias can be detected by observing only 256 bytes.
Souradyuti Paul Souradyuti Paul (born 1976) is an Indian cryptologist. Formerly a member of COSIC, he is currently working as an associate professor at Indian Institute of Technology Bhilai and a Guest Researcher for the National Institute of Standards and Techno ...
and Bart Preneel of
COSIC The Computer Security and Industrial Cryptography research group, commonly called COSIC, is a research group at the Department of Electrical Engineering of KU Leuven, which is headed by Bart Preneel. Research Research and expertise in digital s ...
showed 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. Scott Fluhrer and David McGrew also showed attacks that distinguished the keystream of the RC4 from a random stream given a gigabyte of output. The complete characterization of a single step of RC4 PRGA was performed by Riddhipratim Basu, Shirshendu Ganguly, Subhamoy Maitra, and Goutam Paul. Considering all the permutations, they proved that the distribution of the output is not uniform given i and j, and as a consequence, information about j is always leaked into the output.


Fluhrer, Mantin and Shamir attack

In 2001, a new and surprising discovery was made by Fluhrer,
Mantin Mantin is a town in Seremban District, Negeri Sembilan, Malaysia. It lies along the main road connecting Kajang and Seremban. History This place has two names, Setul and Mantin. Setul is the name of a certain plant (''sandoricum koetjape''). ...
and Shamir: over all the possible RC4 keys, the statistics for the first few bytes of output keystream are strongly non-random, leaking information about the key. If the nonce and long-term key 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 IEEE 802.11 is part of the IEEE 802 set of local area network (LAN) technical standards, and specifies the set of media access control (MAC) and physical layer (PHY) protocols for implementing wireless local area network (WLAN) computer com ...
wireless network A wireless network is a computer network that uses wireless data connections between network nodes. Wireless networking is a method by which homes, telecommunications networks and business installations avoid the costly process of introducing c ...
s. This caused a scramble for a standards-based replacement for WEP in the 802.11 market and led to the IEEE 802.11i effort and
WPA WPA may refer to: Computing *Wi-Fi Protected Access, a wireless encryption standard *Windows Product Activation, in Microsoft software licensing * Wireless Public Alerting (Alert Ready), emergency alerts over LTE in Canada * Windows Performance An ...
. Protocols can defend against this attack by discarding the initial portion of the keystream. Such a modified algorithm is traditionally called "RC4-drop[]", where is the number of initial keystream bytes that are dropped. The SCAN default is = 768 bytes, but a conservative value would be = 3072 bytes. The Fluhrer, Mantin and Shamir attack does not apply to RC4-based SSL, since SSL generates the encryption keys it uses for RC4 by hashing, meaning that different SSL sessions have unrelated keys.


Klein's attack

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 Pychkine used this analysis to create aircrack-ptw, a tool that cracks 104-bit RC4 used in 128-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.


Combinatorial problem

A combinatorial problem related to the number of inputs and outputs of the RC4 cipher was first posed by Itsik Mantin and
Adi Shamir Adi Shamir ( he, עדי שמיר; born July 6, 1952) is an Israeli cryptographer. He is a co-inventor of the Rivest–Shamir–Adleman (RSA) algorithm (along with Ron Rivest and Len Adleman), a co-inventor of the Feige–Fiat–Shamir identifi ...
in 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 in the next 256 rounds. This conjecture was put to rest in 2004 with a formal proof given by
Souradyuti Paul Souradyuti Paul (born 1976) is an Indian cryptologist. Formerly a member of COSIC, he is currently working as an associate professor at Indian Institute of Technology Bhilai and a Guest Researcher for the National Institute of Standards and Techno ...
and Bart Preneel.


Royal Holloway attack

In 2013, a group of security researchers at the Information Security Group at Royal Holloway, University of London reported an attack that can become effective using only 234 encrypted messages. While yet not a practical attack for most purposes, this result is sufficiently close to one that it has led to speculation that it is plausible that some state cryptologic agencies may already have better attacks that render RC4 insecure. Given that, , a large amount of TLS traffic uses RC4 to avoid attacks on block ciphers that use
cipher block chaining In cryptography, a block cipher mode of operation is an algorithm that uses a block cipher to provide information security such as confidentiality or authenticity. A block cipher by itself is only suitable for the secure cryptographic transform ...
, if these hypothetical better attacks exist, then this would make the TLS-with-RC4 combination insecure against such attackers in a large number of practical scenarios. In March 2015, researcher to Royal Holloway announced improvements to their attack, providing a 226 attack against passwords encrypted with RC4, as used in TLS.


Bar mitzvah attack

At the Black Hat Asia 2015 Conference, Itsik Mantin presented another attack against SSL using RC4 cipher.


NOMORE attack

In 2015, security researchers from
KU Leuven KU Leuven (or Katholieke Universiteit Leuven) is a Catholic research university in the city of Leuven, Belgium. It conducts teaching, research, and services in computer science, engineering, natural sciences, theology, humanities, medicine, ...
presented new attacks against RC4 in both TLS and WPA-TKIP. Dubbed the Numerous Occurrence MOnitoring & Recovery Exploit (NOMORE) attack, it is the first attack of its kind that was demonstrated in practice. Their attack against TLS can decrypt a secure
HTTP cookie HTTP cookies (also called web cookies, Internet cookies, browser cookies, or simply cookies) are small blocks of data created by a web server while a user is browsing a website and placed on the user's computer or other device by the user's w ...
within 75 hours. The attack against WPA-TKIP can be completed within an hour and allows an attacker to decrypt and inject arbitrary packets.


RC4 variants

As mentioned above, the most important weakness of RC4 comes from the insufficient key schedule; the first bytes of output reveal information about the key. This can be corrected by simply discarding some initial portion of the output stream. This is known as RC4-drop''N'', where ''N'' is typically a multiple of 256, such as 768 or 1024. A number of attempts have been made to strengthen RC4, notably Spritz, RC4A, VMPC, and RC4+.


RC4A

Souradyuti Paul Souradyuti Paul (born 1976) is an Indian cryptologist. Formerly a member of COSIC, he is currently working as an associate professor at Indian Institute of Technology Bhilai and a Guest Researcher for the National Institute of Standards and Techno ...
and Bart Preneel have proposed an RC4 variant, which they call RC4A. RC4A uses two state arrays and , and two indexes and . Each time is incremented, two bytes are generated: # First, the basic RC4 algorithm is performed using and , but in the last step, is looked up in . # Second, the operation is repeated (without incrementing again) on and , and is output. Thus, the algorithm is: ''All arithmetic is performed modulo 256'' i := 0 j1 := 0 j2 := 0 while GeneratingOutput: i := i + 1 j1 := j1 + S1 swap values of S1 and S1 1 output S2 +_S1 +_S1[j1">1_+_S1[j1nowiki>.html" ;"title="1.html" ;"title="1 + S1[j1">1 + S1[j1nowiki>">1.html" ;"title="1 + S1[j1">1 + S1[j1nowiki>/nowiki> j2 := j2 + S2 swap values of S2 and S2[j2] output S1[S2 + S2[j2]] endwhile Although the algorithm required the same number of operations per output byte, there is greater parallelism than RC4, providing a possible speed improvement. Although stronger than RC4, this algorithm has also been attacked, with Alexander Maximov and a team from NEC developing ways to distinguish its output from a truly random sequence.


VMPC

Variably Modified Permutation Composition (VMPC) is another RC4 variant. It uses similar key schedule as RC4, with iterating 3 × 256 = 768 times rather than 256, and with an optional additional 768 iterations to incorporate an initial vector. The output generation function operates as follows: ''All arithmetic is performed modulo 256.'' i := 0 while GeneratingOutput: a := S j := S + a output S [S[j+_1.html" ;"title="[j.html" ;"title="[S[j">[S[j+ 1">[j.html" ;"title="[S[j">[S[j+ 1 Swap S and S (''b := S S := b; S := a)'') i := i + 1 endwhile This was attacked in the same papers as RC4A, and can be distinguished within 238 output bytes.


RC4+

RC4+ is a modified version of RC4 with a more complex three-phase key schedule (taking about three times as long as RC4, or the same as RC4-drop512), and a more complex output function which performs four additional lookups in the S array for each byte output, taking approximately 1.7 times as long as basic RC4. ''All arithmetic modulo 256. ''<<'' and ''>>'' are left and right shift, ''⊕'' is exclusive OR'' while GeneratingOutput: i := i + 1 a := S j := j + a Swap S and S (''b := S S := S S := b;'') c := S <<5 ⊕ j>>3+ S <<5 ⊕ i>>3 output (S +b+ S ⊕0xAA ⊕ S +b endwhile This algorithm has not been analyzed significantly.


Spritz

In 2014, Ronald Rivest gave a talk and co-wrote a paper on an updated redesign called
Spritz Spritz may refer to: * Hair spray * Spritz (cocktail), an aperitif consisting of wine, sparkling water, and liqueur * Spritz (wine), a term referring to small amounts of carbon dioxide added to wine * Spritz (cipher), a cryptographic stream cipher ...
. A hardware accelerator of Spritz was published in Secrypt, 2016 and shows that due to multiple nested calls required to produce output bytes, Spritz performs rather slowly compared to other hash functions such as SHA-3 and the best known hardware implementation of RC4. The algorithm is: ''All arithmetic is performed modulo 256'' while GeneratingOutput: i := i + w j := k + S + S[i k := k + i + S swap values of S and S output z := S[j + S[i + S[z + k] endwhile The value , is relatively prime to the size of the S array. So after 256 iterations of this inner loop, the value (incremented by every iteration) has taken on all possible values 0...255, and every byte in the S array has been swapped at least once. Like other
sponge function In cryptography, a sponge function or sponge construction is any of a class of algorithms with finite state (computer science), internal state that take an input bit stream of any length and produce an output bit stream of any desired length. Spon ...
s, Spritz can be used to build a cryptographic hash function, a deterministic random bit generator (
DRBG A pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG), is an algorithm for generating a sequence of numbers whose properties approximate the properties of sequences of random numbers. The PRNG-generate ...
), an encryption algorithm that supports
authenticated encryption Authenticated Encryption (AE) and Authenticated Encryption with Associated Data (AEAD) are forms of encryption which simultaneously assure the confidentiality and authenticity of data. Programming interface A typical application programming in ...
with associated data (AEAD), etc. In 2016, Banik and Isobe proposed an attack that can distinguish Spritz from random noise.


RC4-based protocols

* WEP * TKIP (default algorithm for
WPA WPA may refer to: Computing *Wi-Fi Protected Access, a wireless encryption standard *Windows Product Activation, in Microsoft software licensing * Wireless Public Alerting (Alert Ready), emergency alerts over LTE in Canada * Windows Performance An ...
, but can be configured to use
AES-CCMP Counter Mode Cipher Block Chaining Message Authentication Code Protocol (Counter Mode CBC-MAC Protocol) or CCM mode Protocol (CCMP) is an encryption protocol designed for Wireless LAN products that implements the standards of the IEEE 802.11i amen ...
instead of RC4) *
BitTorrent protocol encryption Protocol encryption (PE), message stream encryption (MSE) or protocol header encrypt (PHE) are related features of some peer-to-peer file-sharing clients, including BitTorrent clients. They attempt to enhance privacy and confidentiality. In addit ...
*
Microsoft Office XP Microsoft Office XP (codenamed Office 10) is an office suite which was officially revealed in July 2000 by Microsoft for the Windows operating system. Office XP was released to manufacturing on March 5, 2001, and was later made available to ret ...
(insecure implementation since nonce remains unchanged when documents get modified) *
Microsoft Point-to-Point Encryption Microsoft Point-to-Point Encryption (MPPE) encrypts data in Point-to-Point Protocol (PPP)-based dial-up connections or Point-to-Point Tunneling Protocol (PPTP) virtual private network (VPN) connections. 128-bit key (strong), 56-bit key, and 40-bit ...
*
Transport Layer Security Transport Layer Security (TLS) is a cryptographic protocol designed to provide communications security over a computer network. The protocol is widely used in applications such as email, instant messaging, and voice over IP, but its use in securi ...
/
Secure Sockets Layer Transport Layer Security (TLS) is a cryptographic protocol designed to provide communications security over a computer network. The protocol is widely used in applications such as email, instant messaging, and voice over IP, but its use in securi ...
(was optional and then the use of RC4 was prohibited in RFC 7465) *
Secure Shell The Secure Shell Protocol (SSH) is a cryptographic network protocol for operating network services securely over an unsecured network. Its most notable applications are remote login and command-line execution. SSH applications are based on a ...
(optionally) *
Remote Desktop Protocol Remote Desktop Protocol (RDP) is a proprietary protocol developed by Microsoft which provides a user with a graphical interface to connect to another computer over a network connection. The user employs RDP client software for this purpose, while t ...
(optionally) * Kerberos (optionally) * SASL Mechanism Digest-MD5 (optionally, ''historic'', obsoleted in RFC 6331) * Gpcode.AK, an early June 2008 computer virus for Microsoft Windows, which takes documents hostage for
ransom Ransom is the practice of holding a prisoner or item to extort money or property to secure their release, or the sum of money involved in such a practice. When ransom means "payment", the word comes via Old French ''rançon'' from Latin ''red ...
by obscuring them with RC4 and RSA-1024 encryption *
PDF Portable Document Format (PDF), standardized as ISO 32000, is a file format developed by Adobe in 1992 to present documents, including text formatting and images, in a manner independent of application software, hardware, and operating systems. ...
*
Skype Skype () is a proprietary telecommunications application operated by Skype Technologies, a division of Microsoft, best known for VoIP-based videotelephony, videoconferencing and voice calls. It also has instant messaging, file transfer, deb ...
(in modified form) Where a protocol is marked with "(optionally)", RC4 is one of multiple ciphers the system can be configured to use.


See also

*
TEA Tea is an aromatic beverage prepared by pouring hot or boiling water over cured or fresh leaves of ''Camellia sinensis'', an evergreen shrub native to East Asia which probably originated in the borderlands of southwestern China and north ...
, Block TEA also known as eXtended TEA and Corrected Block TEA – A family of
block cipher In cryptography, a block cipher is a deterministic algorithm operating on fixed-length groups of bits, called ''blocks''. Block ciphers are specified cryptographic primitive, elementary components in the design of many cryptographic protocols and ...
s that, like RC4, are designed to be very simple to implement. *
Advanced Encryption Standard The Advanced Encryption Standard (AES), also known by its original name Rijndael (), is a specification for the encryption of electronic data established by the U.S. National Institute of Standards and Technology (NIST) in 2001. AES is a variant ...
*
CipherSaber CipherSaber is a simple symmetric encryption protocol based on the RC4 stream cipher. Its goals are both technical and political: it gives reasonably strong protection of message confidentiality, yet it's designed to be simple enough that even no ...


References


Further reading

* *


External links


Original posting of RC4 algorithm to Cypherpunks mailing list
* – Improved Arcfour Modes for the Secure Shell (SSH) Transport Layer Protocol * – Test Vectors for the Stream Cipher RC4 * – Prohibiting RC4 Cipher Suites *

*

;RC4 in WEP

* {{Cryptography navbox, stream Stream ciphers Broken stream ciphers Pseudorandom number generators Free ciphers Articles with example C code