How The Mighty Have Fallen: RC4 — Fast, Compact, and Insecure

How The Mighty Have Fallen: RC4 — Fast, Compact, and Can Be Insecure

When I started in networking, the world was just getting into wireless communications. For the first time on a local area network, we could communicate with a computer without wires. But, it was a technical disaster — aka WEP (Wired Equivalent Privacy).

WEP broke almost every rule in how to design Wifi security. It used a broadcast encryption key for the whole network, which meant that anyone with the key could read every other packet on the network and decrypt it. It also used a 24-bit IV (Initial Vector), which was too small, and it rolled around within a relatively short period. When this happened, it was then easy to crack the encryption. And, finally, it used RC4. While fast and efficient, it has been shown to have security issues [1]:

For this, Fluher et al showed that there were a large number of weak keys, where the outputs could be guessed for given inputs, and which Klein improved on. When the Fluhrer et al method was uncovered, it caused many — including Ron Rivest — problems in their implementations:

It should be noted that the cracking team included one of Ron’s co-researchers: Adi Shamir — one of the great cryptanalysts.

RC4 — Ron’s Cipher 4

RC4 is a stream cipher that was created by Ron Rivest and created in 1987. It is generally a fast cipher, and where we create a key stream based on a password. RC4 was used in WEP (Wired Equivalent Privacy), and where a small IV value caused serious security problems.

The key length can vary from one to 256 bytes and is used to create an initial 256-byte state vector (S). The output is basically X-OR’ed one bit at a time with the keystream, and the plaintext is recovered by X-OR’ing the cipher stream with the keystream. As we are using a stream cipher, there is no need for padding, and where the ciphertext stream size will be the same as the plaintext length.

The basics of key generation are given here:

https://asecuritysite.com/symmetric/rc4_key

Coding

In this case, we will use ARC4 (Alleged RC4). It was created by Ron Rivest at RSA and was kept a trade secret for seven years. Thus, to avoid trademark claims it is often defined as ARC4 — as it was never actually released as an algorithm. It is still a fairly popular method, especially due to variable key lengths from 40 bits up to 256 bits. The code is [here]:

import os
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes
from cryptography.hazmat.primitives import padding
import sys

message="Hello"

keysize=5
iv = os.urandom(8)
mode=0

if (len(sys.argv)>1):
 message=str(sys.argv[1])
if (len(sys.argv)>2):
 keysize=int(sys.argv[2])

key = os.urandom(keysize)


cipher=None


cipher = Cipher(algorithms.ARC4(key), mode=None)

encryptor = cipher.encryptor()



ciphertext = encryptor.update(message.encode()) + encryptor.finalize()

# Now decrypt

decryptor = cipher.decryptor()
rtn=decryptor.update(ciphertext) 

print("Type:\t\t\t",cipher.algorithm.name)
print("Message:\t\t",message)

print("\nKey:\t\t\t",key.hex())
if (mode!=3): print("IV:\t\t\t",iv.hex())
print("\nCipher:\t\t\t",ciphertext.hex())
print("Decrypt:\t\t",rtn.decode())

and a sample run for a 256-bit key is [here]:

Type:    RC4
Message:   Hello

Key:    2583f2a76196ce63d0aa762bb922b02070565e4f16be58fab349ac27d5b9c2ef
IV:    ace37ba097415115

Cipher:    b0c85964c4
Decrypt:   Hello

Notice that the cipher length is the same length as the plaintext (in terms of the number of bytes).

Conclusions

And, so, RC4 crashed and burned. One vulnerability and it was gone. Most systems moved to use the AES standard, which was much more robust. While the block cipher mode of AES was much slower, the GCM mode converted it into a stream cipher and made it just as fast as RC4. So, thank you, Ron, you have led the way in so many areas, but RC4 was not something that will sustain into the future in the way that RSA has.

References

[1] Klein, A. (2008). Attacks on the RC4 stream cipher. Designs, codes and cryptography, 48, 269–286.

[2] Fluhrer, S., Mantin, I., & Shamir, A. (2001). Weaknesses in the key scheduling algorithm of RC4. In Selected Areas in Cryptography: 8th Annual International Workshop, SAC 2001 Toronto, Ontario, Canada, August 16–17, 2001 Revised Papers 8 (pp. 1–24). Springer Berlin Heidelberg.