Cryptography Reference
In-Depth Information
Proof:
P(t
1
= 2 | K[0] + K[1] = 0)
= P(S
1
[i
1
] + S
1
[j
1
] = 2 | K[0] + K[1] = 0)
= P(S
1
[i
1
] = 1,S
1
[j
1
] = 1 | K[0] + K[1] = 0)
N−1
P(S
1
[j
1
] = x,S
1
[i
1
] = N −x + 2 | K[0] + K[1] = 0)
+
x=0
x=1,
N+2
2
> P(S
1
[i
1
] = 1,S
1
[j
1
] = 1 | K[0] + K[1] = 0)
= P(S
0
[1] = 1 | K[0] + K[1] = 0)
as (S
1
[i
1
] = 1∧S
1
[j
1
] = 1) ⇐⇒ (S
0
[1] = 1)
= P(S
0
[1] = K[0] + K[1] + 1 | K[0] + K[1] = 0)
≈ P(S
0
[1] = K[0] + K[1] + 1)
N
N −1
N
≈
(by Corollary 3.1.2, item 1).
Recall that in the derivation of P(S
0
[1] = K[0] +K[1] + 1) in Corollary 3.1.2,
no assumption on K[0]+K[1] was required. Hence, the event (S
0
[1] = K[0]+
K[1]+1) may be considered independent of the event (K[0]+K[1] = 0), which
justifies the removal of the conditional in the last line of the proof.
1
The bias in the output index (Theorem 5.3.1), the conditional bias in the
output index (Theorem 5.5.3), and the bias of the first byte of the output
toward the first three bytes of the secret key (Theorem 5.5.2) was discovered
in [131].
Roos [146] experimentally observed that given any RC4 key with the re-
striction K[0] +K[1] = 0, the probability that the first keystream byte gener-
ated by RC4 will be K[2]+ 3 ranges between 12% and 16% with an average of
13.8%. The work [131], for the first time, provided a theoretical justification
of this observation that we present in Theorem 5.5.4 below.
Theorem 5.5.4. Assume that the first two bytes K[0], K[1] of the secret key
add to 0 mod N. Then the correlation between the key bytes and the first byte
of the keystream output is given by
P(z
1
= K[2] + 3 | K[0] + K[1] = 0) > (
N−1
N
)
N
φ
N
.
1
In fact, along the same line of proof of Theorem 3.1.5, one can directly show that
P
(
S
0
[1] =
X
+ 1
| K
[0] +
K
[1] =
X
)
≈
(
N−1
)
N
, for 0
≤ X ≤ N −
1.
N
