Cryptography Reference
In-Depth Information
3.2.2 Bias in Each Permutation Byte
If the permutation after the KSA is perfectly random, then P(S
N
[u] = v)
should be
1
N
for 0 ≤u,v ≤ N−1. However, in [110, Chapter 6 and Appendix
C] it has been shown that this bivariate distribution is not uniform.
Theorem 3.2.3. At the end of KSA, for 0 ≤u ≤N −1, 0 ≤ v ≤N −1,
8
<
v
+
v
N−u−1
1
N
N−1
N
N−1
N
N−1
N
1−
if v ≤u;
P(S
N
[u] = v) =
:
N−u−1
+
v
1
N
N−1
N
N−1
N
if v > u.
Later, the same distribution has been independently studied in [122]
and [135]. Here, we present the proof approach of [135].
In Figure 3.3, we present a few graphs for P(S
N
[u] = v) versus v, 0 ≤ v ≤
N−1, for a few values of u as motivating examples. These graphs are plotted
using 10 million trials over randomly chosen keys of 32 bytes. It is clear that
the probabilities P(S
N
[u] = v) are not uniform.
x 10
−3
5.5
u=254
5
u=200
u=127
4.5
4
3.5
u=40
3
u=1
N=256
2.5
0
50
100
150
200
250
300
v −−−−>
FIGURE 3.3: P(S
N
[u] = v) versus v for some specific u's.
Below we present the proof technique of [135] for estimating the probabil-
ities P(S
N
[u] = v). It turns out that each permutation byte after the KSA
is significantly biased (either positive or negative) toward many values in the
range 0,...,N − 1. These biases are independent of the secret key and thus
