Cryptography Reference
In-Depth Information
3 to 255 to be specific) of the plaintext M. We can formally state the result
(analogous to Theorem 6.2.4) as follows.
Theorem 6.2.12. 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
3
), the
bytes 3 to 255 of M can be reliably extracted from C
1
,C
2
,...,C
k
.
1
N
c
r
N
2
for all
3 ≤ r ≤ 255 in the RC4 keystream. Thus, for each encryption key chosen
during the broadcast scheme, M[r] has probability
Proof: Recall from Theorem 6.2.9 that P(z
r
= 0) =
+
1
N
c
N
2
to be XOR-ed
+
with 0.
Due to this bias of z
r
toward zero,
N
+
c
N
2
fraction of the r-th ciphertext
bytes will have the same value as the r-th plaintext byte, with a higher proba-
bility. When k = Ω(N
3
), the attacker can identify the most frequent character
in C
1
[r],C
2
[r],...,C
k
[r] as M[r] with constant probability of success.
1
6.2.4 Distinguishers Based on Combination of Biases in RC4
Permutation
In Section 3.2, we discussed the bias of the permutation elements after the
KSA toward many values in Z
N
. Here we are going to show how combina-
tions of these biases propagate to the keystream and thus help distinguish the
RC4 keystream from random streams. The distinguishers presented here first
appeared in [135].
Lemma 6.2.13. Consider B ⊂
Z
N
with |B| = b. Let
P(S
N
[r] ∈B) =
b
N
+ ǫ,
where ǫ can be positive or negative. Then for r ≥ 1,
P(S
r−1
[r] ∈B) =
b
N
+ δ,
where
r−1
r−1
b
N
+ ǫ
N −1
N
N −1
N
b−1
N −1
−
b
N
δ =
+
1−
r−1
−
b
N
N −1
N
.
Proof: The event (S
r−1
[r] ∈B) can occur in three ways.
1. S
N
[r] ∈ B and the index r is not touched by any of the r−1 many j
G
values during the first r− 1 rounds of the PRGA. The contribution of
this part is (
N
+ ǫ)(
N−1
)
r−1
.
N
