RC4

RC4 , ARC4 or Arcfour is a stream encryption that has found widespread use with standards such as HTTPS , SSH 1 and WEP or WPA .

RC4 ( Ron's Code 4 ) was developed by Ronald L. Rivest in 1987 , is a trademark of RSA Security and is officially secret ( Security by Obscurity ). ARC4 ( Alleged RC4) or Arcfour goes back to an anonymous publication of source code in 1994 and is open source .

In February 2015, RFC 7465 banned the use of RC4 in the context of TLS because it has significant security deficiencies.

description

A random sequence is generated from a key that can only be used once. The plaintext is bit by bit by the XOR linked to the random sequence to encode the data.

The random number generator uses a so-called S-Box , a randomly selected permutation or substitution of the numbers 0 to 255. In a first step, the S-Box is calculated from the secret key and then used to calculate the random sequence. After each calculation step, two values of the S-Box are swapped.

The security of such a procedure is only guaranteed if the random sequence is not repeated. Therefore the key or the password may only be used once. For the composition of the S-box and the values of two other variables, there are about 2 ^{1 684} options, which would correspond to a key length of 210 (1684/8) characters. According to the birthday paradox, it is to be expected that there are keys with a key length of ((1684/2) / 8) 105 characters that generate identical permutations of the S-Box. We now know at least two 24-character (192-bit) keys that lead to the same permutation of the S-Box. This means that there are two different keys that lead to the same encryption sequence.

The algorithm is very easy to implement with practically any hardware and software and can be calculated very efficiently.

In the WEP , the unique key was determined by simply combining a fixed secret key and a session key . In this case, however, it is possible to derive the fixed secret key. If the key with a hash function is chosen more or less randomly, the RC4 can still be regarded as secure.

With Microsoft Windows systems that are connected to an NT domain , the login password that the user enters in the GINA interface is encrypted after a key has been negotiated via RC4- HMAC and transmitted to the server using a Kerberos frame . The key is negotiated during the message “Network connections are being prepared”.

algorithm

RC4's look-up phase on a byte-sized alphabet. The output byte is selected from the values and , these are added modulo 256.

{\ displaystyle S [i]}

{\ displaystyle S [j]}

The core of the process is the so-called S-Box, a random swap or permutation of the standard alphabet ( byte values 0–255). The S-Box is used to generate a random sequence that is linked to the message stream bit for bit by addition modulo 2, also known as an XOR link . The S-Box is initially pre-assigned as an identical mapping , so that i = 0 to 255 applies. ${\ displaystyle S [i] = i}$

The initial assignment of the S-Box can be described with the following pseudo code. The S-Box is calculated from the byte length key : ${\ displaystyle k}$ ${\ displaystyle L}$

  k[]: gegebene Schlüssel-Zeichenfolge der Länge 5 bis 256 Byte
  L := Länge des Schlüssels in Byte
  s[]: Byte-Vektor der Länge 256
  Für i = 0 bis 255
    s[i] := i
  j := 0
  Für i = 0 bis 255
    j := (j + s[i] + k[i mod L]) mod 256
    vertausche s[i] mit s[j]

The subsequent calculation of the random sequence is carried out in the same way:

  klar[]: gegebene Klartext-Zeichenfolge der Länge X
  schl[]: Vektor zum Abspeichern des Schlüsseltextes
  i := 0
  j := 0
  Für n = 0 bis X-1
    i := (i + 1) mod 256
    j := (j + s[i]) mod 256
    vertausche s[i] mit s[j]
    zufallszahl := s[(s[i] + s[j]) mod 256]
    schl[n] := zufallszahl XOR klar[n]

The same algorithm is used for decryption, whereby the ciphertext is entered instead of the plaintext. Two XOR operations with the same random number cancel each other out, and the plaintext is output again.

safety

Like any stream cipher , RC4 does not offer any integrity protection. If an attacker changes a bit in an encrypted message, he also changes the same bit in the plaintext.

The first practical attack on the RC4 cipher was made by Scott Fluhrer, Itsik Mantin and Adi Shamir in 2001. RSA Security then recommended that the first 256 bytes of the keystream be discarded. Andreas Klein improved the attack so that it works even if the first 256 bytes are discarded. He recommended discarding the output of the first 12 rounds.

At the beginning of 2013, a new attack scenario was proposed by AlFardan, Bernstein, Paterson, Poettering and Schuldt, which uses statistical anomalies in the key table of RC4 to decrypt a plaintext that is transmitted over several TLS connections encrypted with RC4 . In 2015 Mathy Vanhoef and Frank Piessens presented a practically feasible attack on RC4 in which Magic Cookies could be decrypted within 52 hours.

Jacob Appelbaum believes that the NSA can break the RC4 encryption in real time . Bruce Schneier called this a plausible guess.

The European Network and Information Security Agency recommends replacing RC4 with Rabbit or Snow 3G . The Federal Office for Information Security also advises against the use of RC4. For example, the German finance agency has not been using RC4 since November 2013.

The Internet Engineering Task Force prohibits the RFC 7465 , since February 2015, the use of RC4 as the encryption in practice would have to be cracked few attempts and a sufficiently high security for TLS can make sessions more.

successor

Spray

On October 27, 2014, Ronald L. Rivest and Jacob CN Schuldt introduced an improved version of RC4 called Spritz. However, the performance of RC4 is not quite achieved. The algorithm is only about half as fast as RC4, but still considerably faster than standardized block ciphers such as the Advanced Encryption Standard . The key calculation takes longer than with RC4.

A brief comparison of the core pieces of RC4 and SPRITZ follows.

RC4:

  i = i + 1
  j = j + S[i]
  SWAP(S[i],S[j])
  z = S[S[i] + S[j]]
  Return z

SPRAY:

  i = i + w
  j = k + S[j + S[i]]
  k = i + k + S[j]
  SWAP(S[i],S[j])
  z = S[j + S[i + S[z + k]]]
  Return z

The parameter w is a to N are relatively prime numbers, wherein N (usually 256), the size of the array S is. Is always added modulo N . After N iterations, i has therefore assumed every value from 0 to N-1 exactly once. Each value in S was accordingly swapped at least once with a randomly selected position.

Web links

Overview about the safety of RC4 about work (English)
Original post of the then still secret RC4 algorithm on Usenet (English)
Scott Fluhrer , Itsik Mantin , Adi Shamir : Weaknesses in the Key Scheduling Algorithm of RC4 . (PDF; 297 kB; English)
A Stream Cipher Encryption Algorithm “Arcfour” ( Internet Engineering Task Force Network Working Group 1997)
RFC 4345 - Improved Arcfour Modes for the Secure Shell (SSH) Transport Layer Protocol

Individual evidence

↑ Jürgen Schmidt: IETF prohibits RC4 encryption in TLS. Heise Security, February 20, 2015, accessed February 20, 2015 .

^ ^A ^b A. Popov: Prohibiting RC4 Cipher Suites. Internet Engineering Task Force (IETF), February 2015, accessed March 11, 2016 .

↑ Mitsuru Matsui: Key Collisions of the RC4 Stream Cipher . Fast Software Encryption, 2009. In: Lecture Notes . In: Computer Science , number 5665, Springer Verlag, 2009, pp. 38–50, presentation (PDF; 267 kB; English)

↑ Scott Fluhrer, Itsik Mantin, Adi Shamir: Weaknesses in the Key Scheduling Algorithm of RC4 . In: Selected Areas in Cryptography (= Lecture Notes in Computer Science ). tape 2259 . Springer, 2001, p. 1-24 , doi : 10.1007 / 3-540-45537-X_1 ( weizmann.ac.il ). Weaknesses in the Key Scheduling Algorithm of RC4 ( Memento of the original from June 2, 2004 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. @1@ 2
↑ RSA Security Response to Weaknesses in Key Scheduling Algorithm of RC4. (No longer available online.) RSA Security, archived from the original on September 29, 2011 ; accessed on September 10, 2012 . Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. @1@ 2
^ Andreas Klein: Attacks on the RC4 stream cipher . In: Designs, Codes and Cryptography . tape 48 , no. 3 . Springer, 2008, p. 269-286 , doi : 10.1007 / s10623-008-9206-6 .
↑ Pouyan Sepehrdad, Serge Vaudenay, Martin Vuagnoux: Discovery and Exploitation of New Biases in RC4 . In: Lecture Notes in Computer Science . 6544, 2011, pp. 74-91. doi : 10.1007 / 978-3-642-19574-7_5 .
^ Green, Matthew: Attack of the week: RC4 is kind of broken in TLS . In: Cryptography Engineering . Retrieved March 12, 2013.
↑ Nadhem AlFardan, Dan Bernstein, Kenny Paterson, Bertram Poettering, Jacob Schuldt: On the Security of RC4 in TLS . Royal Holloway University of London. Retrieved March 13, 2013.
↑ Mathy Vanhoef, Frank Piessens: All Your Biases Belong To Us: Breaking RC4 in WPA-TKIP and TLS (pdf).
↑ NSA supposedly decrypts web server data in real time . Heise Security. Retrieved November 7, 2013.
↑ Michael Brenner: ENISA recommendations on crypto procedures . Heise Security. Retrieved November 18, 2013.
↑ Important information for Internet banking users. (No longer available online.) German Finance Agency, November 19, 2013, archived from the original on January 7, 2015 ; accessed on January 2, 2014 . Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. @1@ 2
↑ Jürgen Schmidt: IETF prohibits RC4 encryption in TLS. In: Heise Security. Heise online , February 20, 2015, accessed July 8, 2015 .
↑ Spritz - a spongy RC4-like stream cipher and hash function. Ronald L. Rivest and Jacob CN Schuldt, October 27, 2014, accessed November 1, 2014 .
↑ Spritz: A New RC4-Like Stream Cipher. Bruce Schneier, October 27, 2014, accessed November 1, 2014 .

[1] Jürgen Schmidt: IETF prohibits RC4 encryption in TLS. Heise Security, February 20, 2015, accessed February 20, 2015 .

[rfc7465-2] A ^b A. Popov: Prohibiting RC4 Cipher Suites. Internet Engineering Task Force (IETF), February 2015, accessed March 11, 2016 .

[fse2009matsui-3] Mitsuru Matsui: Key Collisions of the RC4 Stream Cipher . Fast Software Encryption, 2009. In: Lecture Notes . In: Computer Science , number 5665, Springer Verlag, 2009, pp. 38–50, presentation (PDF; 267 kB; English)