Cryptography Reference
In-Depth Information
Proof:
P(z
1
= K[2] + 3 | K[0] + K[1] = 0)
= P(S
1
[t
1
] = K[2] + 3 | K[0] + K[1] = 0)
N−1
=
P(t
1
= x| K[0] + K[1] = 0)
x=0
P(S
1
[t
1
] = K[2] + 3 | K[0] + K[1] = 0,t
1
= x)
N−1
P(t
1
= x | K[0] + K[1] = 0)P(S
1
[x] = K[2] + 3 | K[0] + K[1] = 0)
=
x=0
> P(t
1
= 2 | K[0] + K[1] = 0)P(S
1
[2] = K[2] + 3 | K[0] + K[1] = 0)
= P(t
1
= 2 | K[0] + K[1] = 0)
P(S
1
[2] = K[0] + K[1] + K[2] + 3 | K[0] + K[1] = 0)
≈ P(t
1
= 2 | K[0] + K[1] = 0)P(S
1
[2] = K[0] + K[1] + K[2] + 3)
N
N −1
N
≈
φ
N
(by Theorem 5.5.3 and Proposition 5.5.1).
Recall that the derivation of P(S
1
[2] = K[0] + K[1] + K[2] + 3) in Propo-
sition 5.5.1 used Corollary 3.1.2. In that derivation, no assumption on
K[0] + K[1] was required. Hence, the event (S
1
[2] = K[0] + K[1] + K[2] + 3)
is considered independent of the event (K[0] + K[1] = 0) in the last line of
the proof.
2
For N = 256, the value of (
N−
N
)
N
φ
N
is approximately 0.13 that proves
the experimental observation of [146].
5.5.3 Cryptanalytic Applications
We present this section to demonstrate applications of Theorem 5.5.2 and
Theorem 5.5.4.
Let m
1
and c
1
denote the first bytes of the message and the ciphertext
respectively. Then c
1
= m
1
⊕ z
1
. One can use Theorem 6.1.1 to calculate
the number of samples that su
ce to mount the cryptanalysis. Let X be the
joint distribution of the two variables (K[0] + K[1] + K[2] + 3) and z
1
, when
K[0],K[1],K[2],z
1
are chosen uniformly at random from Z
N
, and Y be the
joint distribution of the same two variables for RC4 for randomly chosen keys.
Let A be the event that these two variables are equal. Using the notations
of Theorem 6.1.1 (to be discussed in Chapter 6), we write the probability
expression of Theorem 5.5.2 as p
0
(1 + ǫ), where p
0
=
1
N
and ǫ = φ
N
. Thus
2
In fact, along the same line of proof of Theorem 3.1.5, one can directly show that
P
(
S
1
[2] =
X
+
K
[2] + 3
| K
[0] +
K
[1] =
X
)
≈
(
N−1
N
)
N
, for 0
≤ X ≤ N −
1.
