Distinguishing Attacks - RC4: Stream Cipher and Its Variants - page 158

1
p 0 ǫ 2 ),

RC4 from random stream with a constant probability of success is O(

i.e., O(N).
Moreover, the bias of z 2 to 0 can be used to mount a linear-time ciphertext-
only attack on broadcast RC4 in which the same plaintext is sent to multiple
recipients under different keys. As mentioned in [107], a classical problem in
distributed computing is to allow N Byzantine generals to coordinate their
actions, when at most one third of them can be traitors. This problem is
solved by a multi-round protocol in which each general broadcasts the same
plaintext message (initially consisting of either “Attack” or “Retreat”) to all
the other generals. Each copy is encrypted under a different key agreed to in
advance between any two generals. In [107], the authors propose a practical
attack against an RC4 implementation of the broadcast scheme, based on the
bias observed in the second keystream byte.

Theorem 6.2.4. Let M be a plaintext,and let C 1 ,C 2 ,...,C k be the RC4
encryptions of M under k uniformly distributed keys. Then if k = Ω(N), the
second byte z 2 can be reliably extracted from C 1 ,C 2 ,...,C k .
Proof: Recall from Theorem 6.2.3 that P(z 2 = 0) ≈ N . Thus, for each
encryption key chosen during the broadcast scheme, M has probability

2
N

to

be XOR-ed with 0.
Due to this bias of z 2 toward zero,

2

N fraction of the second ciphertext
bytes would have the same value as the second plaintext byte, with a higher
probability. When k = Ω(N), the attacker can identify the most frequent
character in C 1 [2],C 2 [2],...,C k [2] as M[2] with constant probability of suc-
cess.
Many users send the same email message to multiple recipients, where the
messages are encrypted under different keys. Many groupware applications
also enable multiple users to synchronize their documents by broadcasting
encrypted modification lists to all the other group members. All such appli-
cations are vulnerable to this attack.

6.2.3 Positive Biases in Bytes 3 to 255 toward Zero
Contrary to the claim of Mantin and Shamir [107], it was demonstrated
in [100] that all the initial 253 bytes of RC4 keystream from round 3 to 255
are biased to zero. The approximations in the results of [100] has recently
been improved in [157]. Here we present the latter results that have better
approximations.
The main result is a positive bias for each of the events (z r = 0), 3 ≤ r ≤
255. We would decompose the event (z r = 0) into two mutually exclusive and
exhaustive paths, one in conjunction with the event (S r−1 [r] = r) and the
other in conjunction with the complimentary event (S r−1 [r] = r). Hence, we
first need to estimate the probability of the event (S r−1 [r] = r) for all rounds
r ≥ 3.
Let p t,r denote the probability P(S t [r] = r), after t rounds of PRGA,