Cryptography Reference
In-Depth Information
Case II: S
x−1
[x] = S
x+1
[x].
This happens with probability 1 − (
N−
N
)
N−2
. Given this, we assume
that x−z
x
can be equal to S
x+1
[x] having any one of N −1 remaining
values other than S
x−1
[x] with equal probabilities. Thus,
P(x−z
x
= S
x+1
[x] | S
x−1
[x] = S
x+1
[x]) =
1−
N
N −2
N(N −1)
.
N −1
=
Combining these two cases, we have
P(x−z
x
= S
x
[j
x
+ S
x
[x] + K[x])
= P(x−z
x
= S
x+1
[x])
= P(S
x−1
[x] = S
x+1
[x])P(x−z
x
= S
x+1
[x] | S
x−1
[x] = S
x+1
[x])
+P(S
x−1
[x] = S
x+1
[x])P(x−z
x
= S
x+1
[x] | S
x−1
[x] = S
x+1
[x])
N−2
2
N−2
N −1
N
N −1
N
N −2
N(N −1)
=
N
+
1−
≈
1.36
N
(for N = 256).
Thus, the relation
K[x] = S
−1
x
[x−z
x
]−j
x
+ S
x
[x]
(7.8)
holds with probability
1.3
N
. To achieve a success probability greater than 50%
for a 16-byte key with 3-byte IV, Klein's attack requires approximately 43000
IVs.
7.5 PTW and VX Attacks
In [180], Tews, Weinmann and Pyshkin extended Klein's Attack to guess
m
sums of key bytes instead of individual key bytes. Let σ
m
=
κ[r]. Note
r=0
that κ[0] = σ
0
. Once σ
0
,σ
1
,σ
2
,... are known, one can derive κ[r] as σ
r
−σ
r−1
.
As usual, assume that for x > 1, K[0],...,K[x−1] (and hence S
x
and j
x
)
are known. After the next m steps of the KSA, we have i
x+m
= x + m− 1
and
x+m−1
j
x+m
= j
x
+
(S
r
[r] + K[r]).
(7.9)
r=x
Then the swap in round x + m moves S
x+m−1
[j
x+m
] into S
x+m
[x + m−1].
Let us now calculate the lower bound of the probabilities of the following
two events.
