Stream Ciphers and RC4
Chapter Thirty
Syllabus topic Module 1, "Classical Encryption Techniques: Stream Ciphers"
Pages 173 to 178 of 678
In one line
Generate a key stream a byte at a time from a shuffled table of 256 values, and exclusive-or it with the data. It is the simplest serious cipher ever deployed, it was in almost everything, and it is now prohibited.
In the wording a student can write in an examination: a stream cipher encrypts a digital data stream one bit or one byte at a time, by generating a key stream from the key and combining it with the plaintext, usually by exclusive-or. RC4 is a stream cipher designed by Ron Rivest in 1987 with a variable key length from 1 to 256 bytes. It has two parts: the key scheduling algorithm, which uses the key to permute a 256-byte state array S; and the pseudorandom generation algorithm, which produces one key stream byte per call by swapping two entries of S and outputting a third.
The design conditions a key stream must meet
A stream cipher is only as good as its key stream, so the requirements are worth stating as a list, because that is how they are examined.
A long period. The key stream eventually repeats, and when it does, the key-reuse failure of the one-time pad chapter happens inside one message. A period of at least 2 to the power 128 is expected.
Statistically random output. The key stream must pass the same tests a true random sequence would: an equal number of ones and zeros, no correlation between positions, every byte value equally likely. RC4 fails this one, and section 6 measures by how much.
A key long enough to resist brute force. The same requirement as any cipher; at least 128 bits.
The key stream must depend on the whole key. A generator in which the first output bytes depend on only part of the key can be attacked piecewise, which is what happened to RC4 in WEP.
And the rule that is not a design condition but an operating condition, and the one that breaks real systems: a key stream must never be used twice. The one-time pad chapter proved why, and the run below proves it again for RC4.
The cipher, run against its own vectors and measured
# RC4, and why it is banned. The whole cipher is eleven lines.
def ksa(key):
"""The key scheduling algorithm: a keyed shuffle of the 256 byte values."""
s = list(range(256))
j = 0
for i in range(256):
j = (j + s[i] + key[i % len(key)]) % 256
s[i], s[j] = s[j], s[i]
return s
def prga(s, n):
"""The pseudorandom generation algorithm: the key stream, one byte at a time."""
i = j = 0
out = bytearray()
for _ in range(n):
i = (i + 1) % 256
j = (j + s[i]) % 256
s[i], s[j] = s[j], s[i]
out.append(s[(s[i] + s[j]) % 256])
return bytes(out)
def rc4(data, key):
return bytes(a ^ b for a, b in zip(data, prga(ksa(key), len(data))))
print("RFC 6229's first test vector, key 0102030405:")
ks = prga(ksa(bytes.fromhex("0102030405")), 16)
print(" key stream bytes 0 to 15:", ks.hex())
print(" the RFC gives : b2396305f03dc027ccc3524a0a1118a8")
print(" agrees:", ks.hex() == "b2396305f03dc027ccc3524a0a1118a8")
print()
msg = b"PAY 0500 TO 8817"
c = rc4(msg, b"Secret")
print("encryption and decryption are the same operation:")
print(" plaintext :", msg.decode())
print(" ciphertext:", c.hex())
print(" decrypted :", rc4(c, b"Secret").decode())
print()
print("the second byte of the key stream is BIASED. Over 200,000 random keys,")
print("counting how often each value appears in position 2:")
import random
random.seed(11)
counts = [0] * 256
TRIALS = 200000
for _ in range(TRIALS):
k = bytes(random.randrange(256) for _ in range(16))
counts[prga(ksa(k), 2)[1]] += 1
expected = TRIALS / 256
print(" expected count for any value : %.1f" % expected)
print(" count for the value 0 : %d" % counts[0])
print(" ratio : %.2f" % (counts[0] / expected))
top = sorted(range(256), key=lambda v: -counts[v])[:3]
print(" the three commonest values :",
", ".join("%d (%d)" % (v, counts[v]) for v in top))
print()
print(" a fair generator would give every value about %.0f times." % expected)
print(" The value 0 appears about twice as often, which is Mantin and Shamir's")
print(" result: the second byte of RC4's output is 0 with probability about")
print(" 2 in 256 rather than 1 in 256. That alone distinguishes RC4 from random.")
print()
print("and the rule RC4 shares with the one-time pad, which is what WEP broke:")
a = rc4(b"ATTACK AT DAWN!!", b"Secret")
b = rc4(b"HOLD POSITION!!!", b"Secret")
x = bytes(p ^ q for p, q in zip(a, b))
y = bytes(p ^ q for p, q in zip(b"ATTACK AT DAWN!!", b"HOLD POSITION!!!"))
print(" c1 XOR c2 :", x.hex())
print(" p1 XOR p2 :", y.hex())
print(" identical :", x == y, " so the key vanishes.")Stream Ciphers and RC4
RFC 6229's first test vector, key 0102030405:
key stream bytes 0 to 15: b2396305f03dc027ccc3524a0a1118a8
the RFC gives : b2396305f03dc027ccc3524a0a1118a8
agrees: True
encryption and decryption are the same operation:
plaintext : PAY 0500 TO 8817
ciphertext: 549532250c9d4b6961267f0ad4a388a5
decrypted : PAY 0500 TO 8817
the second byte of the key stream is BIASED. Over 200,000 random keys,
counting how often each value appears in position 2:
expected count for any value : 781.2
count for the value 0 : 1555
ratio : 1.99
the three commonest values : 0 (1555), 215 (856), 133 (850)
a fair generator would give every value about 781 times.
The value 0 appears about twice as often, which is Mantin and Shamir's
result: the second byte of RC4's output is 0 with probability about
2 in 256 rather than 1 in 256. That alone distinguishes RC4 from random.
and the rule RC4 shares with the one-time pad, which is what WEP broke:
c1 XOR c2 : 091b1805631b6f121d740d0e196f0000
p1 XOR p2 : 091b1805631b6f121d740d0e196f0000
identical : True so the key vanishes.Stream Ciphers and RC4
Read five things out of that run.
The vector matches RFC 6229. b2396305f03dc027ccc3524a0a1118a8 for the key 0102030405, which is the first line of the RFC's own table.
Encryption and decryption are the same operation. rc4(rc4(m, k), k) is m, because exclusive-or is its own inverse. That is true of every stream cipher and is why they are cheap.
The bias is real and it is large. Over 200,000 random 16-byte keys, the second key stream byte took the value 0 on 1,555 occasions where a fair generator would give about 781. The ratio is 1.99. This is Mantin and Shamir's result of 2001: the second output byte of RC4 is zero with probability about 2 in 256 rather than 1 in 256, and that single fact is enough to distinguish RC4's output from random, which is the formal definition of a broken stream cipher.
The third and second commonest values are unremarkable. 215 appeared 856 times and 133 appeared 850, both close to the expected 781. So the bias is specific to the value 0 in position 2 and is not noise in the measurement: one value is twice as likely and the rest are where they should be.
And the key stream must never repeat. Two messages under the key Secret gave c1 XOR c2 exactly equal to p1 XOR p2. The key vanished. This is the failure that destroyed WEP.
Why RC4 is banned, with the dates
| What happened | When | Consequence |
|---|---|---|
| RC4 designed at RSA Security, kept as a trade secret | 1987 | widely licensed |
| The algorithm leaked and was posted publicly | 1994 | free implementations everywhere, under the name ARCFOUR |
| Fluhrer, Mantin and Shamir publish the key scheduling weakness | 2001 | WEP is broken; a passive listener recovers a wireless key |
| Mantin and Shamir publish the second-byte bias | 2001 | RC4's output is distinguishable from random |
| Further biases found throughout the key stream | to 2013 | plaintext recovery from many TLS sessions becomes feasible |
| RFC 7465, Prohibiting RC4 Cipher Suites | February 2015 | "TLS clients MUST NOT include RC4 cipher suites in the ClientHello message" and servers must not select one |
The WEP failure is worth understanding because it is the clearest example in this subject of a sound component destroyed by its use. WEP combined a 24-bit initialisation vector with a fixed secret key and fed the concatenation straight into RC4's key schedule. Three things followed. A 24-bit initialisation vector repeats after about 16 million packets, which a busy network reaches in hours, and a repeat means a reused key stream. The initialisation vector was sent in the clear, so an attacker knew part of every RC4 key. And the key schedule's weakness meant that knowing part of the key made the first key stream bytes predictable. None of those is a flaw in RC4's arithmetic; all three are flaws in how RC4 was used.
Stream Ciphers and RC4
A worked example: tracing the key schedule by hand
The setting. Key 1 2 3, three bytes. Trace the first three steps of the key scheduling algorithm.
Step 0. S starts as the identity: S[0] is 0, S[1] is 1, and so on to S[255] is 255. And j starts at 0.
Step 1, i is 0. j becomes (0 + S[0] + key[0]) mod 256, which is (0 + 0 + 1) mod 256, which is 1. Swap S[0] and S[1]. Now S[0] is 1 and S[1] is 0.
Step 2, i is 1. j becomes (1 + S[1] + key[1]) mod 256, which is (1 + 0 + 2) mod 256, which is 3. Swap S[1] and S[3]. Now S[1] is 3 and S[3] is 0.
Step 3, i is 2. j becomes (3 + S[2] + key[2]) mod 256, which is (3 + 2 + 3) mod 256, which is 8. Swap S[2] and S[8]. Now S[2] is 8 and S[8] is 2.
The step that carries the marks. Notice that key[i mod keylen] cycles through the key, so a three-byte key is used about 85 times across the 256 steps, and notice that j accumulates: it is never reset, so each step depends on every step before it. Those two facts together are what makes the schedule a shuffle rather than a pattern, and they are also where the Fluhrer, Mantin and Shamir attack gets its grip: the early values of j depend on only the first few key bytes.
Distinctions that carry marks
| Block cipher | Stream cipher | |
|---|---|---|
| Processes | a fixed block | one bit or byte |
| Needs padding | yes | no |
| Same code for both directions | no | yes |
| State | usually a small register | a generator's whole internal state |
| Hardware cost | higher | lower |
| The fatal mistake | electronic codebook mode | reusing the key stream |
| Examples here | DES, 3DES, AES | the one-time pad, RC4 |
| One-time pad | RC4 | |
|---|---|---|
| Key stream | truly random, as long as the message | generated from a short key |
| Period | none, it never repeats | very long, but finite |
| Security | unconditional | computational, and now broken |
| Key length | the message length | 1 to 256 bytes |
| Reusing the key stream | fatal | fatal |
Stream Ciphers and RC4
| RC4's key scheduling algorithm | RC4's pseudorandom generation algorithm | |
|---|---|---|
| Runs | once, 256 steps | once per output byte |
| Uses the key | yes | no, only the state it left behind |
| Produces | the permuted state S | one key stream byte |
| Attacked by | Fluhrer, Mantin and Shamir, 2001 | the output biases |
What beginners get wrong here
Saying RC4 is insecure because its key is short. The key may be up to 256 bytes. RC4 is insecure because its output is biased and because its key schedule leaks, not for want of key length.
Blaming RC4 for WEP. WEP's failures were a 24-bit initialisation vector that repeats, an initialisation vector sent in the clear and concatenated with the key, and no integrity protection. RC4 was the victim, not the culprit, although its key schedule made the last step easy.
Thinking a stream cipher needs a separate decryption routine. It does not. The same function encrypts and decrypts.
Forgetting that the key stream must never repeat. It is the single operating rule, and the run demonstrates the consequence.
Claiming RC4 is still acceptable somewhere. RFC 7465 of February 2015 prohibits it in TLS in terms: clients must not offer RC4 cipher suites and servers must not select one.
Quick revision
- A stream cipher generates a key stream from the key and exclusive-ors it with the data, one bit or byte at a time. Encryption and decryption are the same operation.
- Design conditions: a long period, statistically random output, a key long enough to resist brute force, and the key stream must depend on the whole key.
- The operating condition: never use a key stream twice.
- RC4, Rivest 1987, key 1 to 256 bytes. KSA permutes a 256-byte array once using the key; PRGA then emits one byte per call, swapping two entries and outputting a third, and never looks at the key again.
- Verified against RFC 6229: key
0102030405givesb2396305f03dc027ccc3524a0a1118a8. - Measured bias: over 200,000 random keys the second output byte was 0 on 1,555 occasions against an expected 781, a ratio of 1.99, matching Mantin and Shamir's factor of 2.
- Prohibited in TLS by RFC 7465, February 2015.
- WEP failed by reusing key streams: a 24-bit initialisation vector that repeats within hours, sent in the clear and concatenated with the key.
Test yourself
1. Define a stream cipher and give RC4's two parts. A stream cipher encrypts a data stream one bit or byte at a time by generating a key stream from the key and combining it with the plaintext, normally by exclusive-or. RC4 has a key scheduling algorithm, which uses the key to permute a 256-byte state array in 256 steps, and a pseudorandom generation algorithm, which produces one key stream byte per call by swapping two entries of that array and outputting a third.
Stream Ciphers and RC4
2. State the design conditions for a key stream generator. The period must be very long, at least 2 to the power 128, because a repeat causes key stream reuse within a single message. The output must be statistically indistinguishable from random. The key must be long enough to resist exhaustive search, at least 128 bits. And the key stream must depend on the whole key, so that knowing part of the key does not make part of the stream predictable.
3. What is the bias in RC4's output, and what does it mean? The second byte of the key stream takes the value zero with probability about 2 in 256 rather than the 1 in 256 a fair generator would give. The chapter measures it over 200,000 random keys and finds 1,555 occurrences against an expected 781, a ratio of 1.99. It means RC4's output is distinguishable from random, which is the formal definition of a broken stream cipher, and it allows plaintext recovery from many sessions encrypting the same data.
4. Why is encryption the same as decryption in a stream cipher? Because the plaintext is combined with the key stream by exclusive-or, and exclusive-or is its own inverse: applying the same key stream to the ciphertext returns the plaintext. The key stream is generated from the key alone and does not depend on the data, so the receiver can produce the identical stream.
5. Explain how WEP failed, and say whether RC4 was to blame. WEP concatenated a 24-bit initialisation vector, sent in the clear, with a fixed secret key, and used the result as an RC4 key. A 24-bit value repeats after about 16 million packets, which a busy network reaches within hours, so key streams were reused and exclusive-oring two ciphertexts removed the key. The initialisation vector being public also gave an attacker part of every key, and RC4's key schedule made the early key stream bytes predictable from that. The design of the protocol was the primary fault, although RC4's key schedule made the final step easy.
6. What is RC4's current status? Prohibited in Transport Layer Security by RFC 7465 of February 2015, which requires clients not to offer RC4 cipher suites and servers not to select one. It should not be used anywhere.
7. Trace the first step of RC4's key schedule for the key 1 2 3. The array starts as the identity, with S[n] equal to n, and j starts at 0. With i at 0, j becomes (0 + S[0] + key[0]) mod 256, that is (0 + 0 + 1) mod 256, which is 1; then S[0] and S[1] are swapped, so S[0] becomes 1 and S[1] becomes 0.
The rest of this subject
These notes are cut from the University's printed syllabus. Open the syllabus itself for the same subject.