RC4
• RC4 is a stream cipher designed in 1987 by Ron Rivest for RSA Security, simple but
effective.
• variable key size, byte-oriented stream cipher
• The algorithm is based on the use of a random permutation Eight to sixteen machine
operations are required per output byte, and the cipher can be expected to run very
quickly in software.
• RC4 is used in the Secure Sockets Layer/Transport Layer Security (SSL/TLS) standards
that have been defined for communication between Web browsers and servers.
• It is also used in the Wired Equivalent Privacy (WEP) protocol and the newer WiFi
Protected Access (WPA) protocol that are part of the IEEE 802.11 wireless LAN standard.
RC4
• RC4 was kept as a trade secret by RSA Security.
• In September 1994, the RC4 algorithm was anonymously posted on the Internet on the
Cypherpunks anonymous remailers list.
• The RC4 algorithm is remarkably simple and quite easy to explain.
• A variable-length key of from 1 to 256 bytes (8 to 2048 bits) is used to initialize a 256-byte state
vector S, with elements S[0], S[1], …, S[255].
• At all times, contains a permutation of all 8-bit numbers from 0 through 255.
• For encryption and decryption, a byte k is generated from S by selecting one of the 255 entries in a
systematic fashion.
• As each value of K is generated, the entries in S are once again permuted.
RC4 Key Schedule
• starts with an array S of numbers: 0..255
• A temporary vector T is created
• If the length of the key is 256 bytes, then is transferred to T. Otherwise, for a key of length keylen bytes, the
first keylen elements of T are copied from K, and then K is repeated as many times as necessary to fill out T .
• S forms internal state of the cipher
/* Initialization */
for i = 0 to 255 do
S[i] = i
T[i] = K[i mod keylen])
j = 0
/* Initial permutation of S */
for i = 0 to 255 do
j = (j + S[i] + T[i]) (mod 256)
swap (S[i], S[j])
the only operation on S is a swap, the only effect is a permutation. S still contains all the numbers from 0 through 255
RC4 Encryption
• Once the S vector is initialized, the input key is no longer used.
• Stream generation involves cycling through all the elements of S[i], and for each S[i] , swapping S[i] with
another byte in S according to a scheme dictated by the current configuration of S. After S[255] is reached,
the process continues, starting over again at S[0]:
• encryption continues shuffling array values
• sum of shuffled pair selects "stream key" value from permutation
• XOR S[t] with next byte of message to en/decrypt
/* Stream Generation */
i = j = 0
for each message byte Mi
i = (i + 1) (mod 256)
j = (j + S[i]) (mod 256)
swap(S[i], S[j])
t = (S[i] + S[j]) (mod 256)
Ci = Mi XOR S[t]
RC4 Overview
RC4 Security
• claimed secure against known attacks
• have some analyses, none practical
• result is very non-linear
• since RC4 is a stream cipher, must never reuse a key
• have a concern with WEP, but due to key handling rather than RC4
itself