Lecture
RC4 (from Rivest cipher 4, or Ron’s code), also known as ARC4 or ARCFOUR (alleged RC4) — a stream cipher widely used in various information-security systems in computer networks (for example, in the SSL and TLS protocols, and in the WEP and WPA wireless-network security algorithms).
The cipher was developed by RSA Security, and using it requires a license.
The RC4 algorithm, like any stream cipher, is built around a pseudorandom bit generator. The generator's input is loaded with a key, and pseudorandom bits are read from its output. The key length can range from 40 to 2048 bits . The generated bits have a uniform distribution.
The main advantages of the cipher:
RC4 is fairly vulnerable if:
These factors, together with the way it is used, can make the cryptosystem insecure (as happened with WEP).
The RC4 stream cipher was created by Ronald Rivest, an employee of RSA Security[en], in 1987. The abbreviation “RC4” officially stands for “Rivest cipher 4” or the “Rivest cipher” (“4” is the version number; see RC2, RC5, RC6; RC1 was never published; RC3 was under development, but a vulnerability was found in it), but it is often thought to stand for “Ron’s code” (“Ron’s code”) .
For seven years the cipher was a trade secret, and an exact description of the algorithm was provided only after signing a non-disclosure agreement, but in September 1994 a description of it was anonymously posted to the “Cypherpunks” mailing list . Soon afterward, a description of RC4 was published in the usenet newsgroup “sci.crypt”. From there the source code spread to many sites on the Internet. The published algorithm produced, on output, ciphertexts matching those produced by the genuine RC4. Holders of legal copies of the RC4 source code confirmed the algorithms were identical, despite differences in notation and program structure.
Since this algorithm is known, it is no longer a trade secret. However, the name “RC4” is a trademark of RSA Security[en]. To avoid possible claims from the trademark owner, the cipher is sometimes called “ARCFOUR” or “ARC4”, standing for alleged RC4 — “alleged” RC4 (since “RSA Security” never officially published the algorithm).
The RC4 encryption algorithm is used in a number of widely adopted encryption standards and protocols (for example, WEP, WPA, SSL, and TLS).
RC4 became popular thanks to:
In the United States, the key length recommended for domestic use is 128 bits. An agreement between the “SPA” (software publishers association) and the US government permitted the export of RC4 ciphers with a key length of up to 40 bits. Foreign branches of American companies are permitted to use 56-bit keys .
The core of the stream-cipher algorithm is a function — a pseudorandom bit generator (keystream generator) — that outputs a stream of key bits (the keystream, or sequence of pseudorandom bits).
Fig. Keystream generation mode for stream ciphers
Encryption algorithm.
).
). The result is the ciphertext ( 
): 
.
Decryption algorithm.
).) by the “xor” operation. Owing to the properties of the “xor” operation, the output is the original (unencrypted) text ( ): 
RC4 — is in fact a class of algorithms, defined by the block size (from here on, the S-box size). The parameter n is the word size for the algorithm and determines the length of the S-box. Usually n = 8, but for analysis purposes it can be reduced. However, to increase security this value must be increased. There is nothing in the algorithm preventing an increase in the size of the S-box . If n is increased, say, to 16 bits, the number of elements in the S-box becomes 65,536, and the initialization time will increase accordingly. However, the encryption speed will increase .
The internal state of RC4 is represented as an array of size 2n and two counters. The array is known as the S-box, and will henceforth be denoted S. It always contains a permutation of 2n possible word values. The two counters are denoted i and j.
RC4 initialization consists of two parts:
K.The algorithm is also known as the “key-scheduling algorithm” or “KSA”. This algorithm uses a key supplied by the user as input, stored in Key, and having a length of L bytes. Initialization begins by filling the array S, after which this array is shuffled by permutations determined by the key. Since only one operation is performed on S, the following invariant must hold: S always contains one set of values, which was given at the initial initialization (S[i] := i).
This part of the algorithm is called the pseudo-random generation algorithm (pseudo-random generation algorithm, PRGA). The RC4 keystream generator permutes the values stored in S. In each RC4 cycle, one n-bit word K of the keystream is determined. This key word is then combined by addition modulo two with the plaintext that the user wants to encrypt, producing the ciphertext.
Unlike modern ciphers (such as eSTREAM), RC4 does not use a nonce (nonce — “number that can only be used once” — a number that may be used only once) together with the key. This means that if a single key has to be used over a long period to encrypt multiple streams, the cryptosystem using RC4 itself must combine the nonce and the long-term key to obtain a stream key for RC4. One possible solution is to generate a new key for RC4 using a hash function of the long-term key and the nonce. However, many applications that use RC4 simply concatenate the key and the nonce. Because of this, and the weak key schedule used in RC4, the application can become vulnerable . For this reason it has been deemed obsolete by many software companies, such as Microsoft. For example, Microsoft’s .NET Framework has no implementation of RC4.
Here we will look at some attacks on the cipher and methods of protecting against them.
In 1995, Andrew Roos experimentally observed that the first byte of the keystream is correlated with the first three bytes of the key, and that the first several bytes of the permutation after the key-scheduling algorithm (KSA) are correlated with some linear combination of the key bytes . These biases were not proven until 2007, when Paul, Rafi, and Maitra proved the correlation between the key and the keystream. Paul and Maitra also proved the correlation between the permutation and the key. The latter work also uses the correlation between the key and the permutation to build the first algorithm for full key recovery from the final permutation after the KSA, without making any assumptions about the key or the initialization vector (IV, initial vector). This algorithm has a constant probability of success as a function of time, which corresponds to the square root of the complexity of exhaustive search. Later, much work was done on recovering the key from the internal state of RC4.
In 2001, Fluhrer, Mantin, and Shamir published a paper on the vulnerability of the RC4 key schedule. They showed that the first bytes of the keystream, across all possible keys, are non-random. From these bytes it is possible, with high probability, to obtain information about the key used by the cipher. And if the long-term key and the nonce are simply concatenated to form the RC4 cipher key, then this long-term key can be recovered by analyzing a sufficiently large number of messages encrypted with that key[10]. This vulnerability, together with some related effects, was used to break WEP encryption in IEEE 802.11 wireless networks. This demonstrated the need for a swift replacement of WEP, which led to the development of the new WPA wireless-network security standard.
A cryptosystem can be made immune to this attack by discarding the beginning of the keystream. The modified algorithm is accordingly called “RC4-drop[n]”, where n is the number of bytes from the start of the keystream that should be discarded. It is recommended to use n = 768; a conservative estimate is n = 3072[11][12].
The attack is based on a weakness of the initialization vector[en]. Knowing the first pseudorandom word K and m bytes of the input key Key, and exploiting a weakness in the algorithm that generates the pseudorandom word K , it is possible to obtain m + 1 bytes of the input key. Repeating the steps yields the full key. In an attack on WEP, for n = 8 the IV has the form (B; 255; N), where B ranges from 3 to 8, and N is any number . To determine around 60 values of N, approximately 4 million packets need to be intercepted.[10]
In 2005, Andreas Klein presented an analysis of the RC4 cipher in which he pointed out a strong correlation between the RC4 key and keystream. Klein analyzed first-round attacks (similar to the FMS attack), second-round attacks, and possible improvements to them. He also proposed some changes to the algorithm to strengthen the cipher. In particular, he argues that reversing the direction of the loop in the key-scheduling algorithm can make the cipher more resistant to FMS-type attacks .
In 2001, Adi Shamir and Itsik Mantin were the first to pose a combinatorial problem related to the number of possible input and output values of the RC4 cipher. If, out of the 256 possible elements of the cipher’s internal state, x elements of the state are known (x ≤ 256), then, assuming the remaining elements are zero, the maximum number of elements that can be obtained by a deterministic algorithm over the following 256 rounds is also equal to x. In 2004, this conjecture was proven by Souradyuti Paul and Bart Preneel[13].
In the summer of 2015, Mathy Vanhoef and Frank Piessens from the University of Leuven in Belgium demonstrated a practical attack on the TLS protocol when it uses RC4 to encrypt transmitted data[14]. The idea behind the attack is based on the MITM principle. By inserting itself into the data channel, the attacking party generates a large number of requests to the server, forcing it to return cookies encrypted with the same key each time. Having at its disposal about 9x227 ~ 230 {plaintext, ciphertext} pairs, the attacking party was able, using the Fluhrer-McGrew and ABSAB statistical methods, to recover the key and, consequently, the encrypted cookies, with a probability of 94%. In practice the attack took about 52 hours, while the upper-bound estimate of the time required at the time of the demonstration was about 72 hours[15].
Earlier we looked at attacks based on the correlation between the first bytes of the ciphertext and the key. Weaknesses of this kind in the algorithm can be addressed by discarding the initial part of the ciphertext[16]. Discarding the first 256, 512, 768, or 1024 bytes is considered reliable. Studies of the beginning of the ciphertext were carried out to demonstrate the unreliability of a certain number of the first bytes, which could allow an attacker to obtain the encryption key. Several modifications of RC4 have been proposed to accomplish the task of strengthening security when using the algorithm: RC4A, VMPC, RC4+.
In 2004, a paper by Souradyuti Paul and Bart Preneel was published, proposing the RC4A modification[17].
RC4A uses two S-boxes instead of one, as in RC4; let us denote them S₁ and S₂. Correspondingly, two counters j₁, j₂ are used for them. The counter i, as in RC4, is used singly for the whole algorithm. The principle of the algorithm's operation remains the same, but there are a number of differences:
S₁ serves as a parameter for S₂.i, two bytes of ciphertext are generated.Algorithm :
The encryption speed of this algorithm can be increased through parallelization.
In 2008, the RC4+ modification was developed and proposed. Its authors, Subhamoy Maitra and Goutam Paul, modified the initialization of the S-box(KSA+), using a 3-level scrambling scheme. The pseudorandom word generation algorithm (PRGA+) was also modified[18].
Algorithm:
All arithmetic operations are performed mod 256. The symbols “<<” and “>>” denote left and right bit shifts respectively. The symbol “⊕” denotes the “exclusive OR” operation
Many stream ciphers operate on the basis of linear feedback shift registers (LFSR). This makes it possible to achieve high efficiency when implementing the cipher as an integrated circuit (a hardware implementation), but it makes software implementation of such ciphers more difficult. Since the RC4 cipher does not use an LFSR and is based on byte operations, it is convenient to implement in software. A typical implementation executes 8 to 16 machine instructions per byte of text, so a software implementation of the cipher should run quickly[19].
The word “(optionally)” means that RC4 is one of several encryption algorithms that the system may use.
Comments