Information Technology Reference
In-Depth Information
cipher using the Overlapping Template Matching Test from the randomness test
suite of NIST [9].
Algorithm 4.3:
DP-Coverage Test
(
R, l, k
)
Randomly select
K
;
Randomly select
l
positions
p
1
,p
2
,...,p
l
from
v
bits of IV;
for
i ←
0
to
R
⎨
⎩
Randomly select
IV
=(
iv
1
,iv
2
,...,iv
v
);
for
j ←
0
to
2
l
−
1
⎨
⎩
J
=(
j
1
,j
2
,...,j
l
) binary representation of
j
;
(
iv
p
1
,iv
p
2
,...,iv
p
l
)=
J
;
Z
(
j
)
=
l
bit keystream after
k
bit distinguisher using
K
and
IV
;
Coverage
i
= Number of distinct
Z
(0)
,...,Z
(2
l
−
1)
;
Evaluate (
Coverage
1
,...,Coverage
R
)using
χ
2
test;
return
(
p − value
)
An important criterion against stream ciphers is that the initial states (states
that are generated after key/IV initialization phase) should be uniformly dis-
tributed throughout the keystream. If for any key, there exist
IV
1
and
IV
2
that identify close starting points, most important assumption of stream ci-
phers
keystream must be used only once
may be violated. A similar observation
is pointed out by Biryukov et al. [12] and used to attack A5/1 by TMTO at-
tacks. The ciphers having close starting points are expected to reach the same
distinguished keystream portions resulting in low coverage.
5
Experimental Results
We applied the three distinguishers to the Phase III candidates of eSTREAM
project with the following parameters: Coverage(100,12), Coverage(100,14),
ρ
(100,15),
ρ
(100,20), DP-Coverage(100,12,10), DP-Coverage(100,14,10). The
last bits of the IVs are chosen to be active. Each test is repeated 100 times
using random keys and the average values are tabulated in Table 3. Since the
p
-values are expected to distribute uniformly between 0 and 1, the average of 100
p
-values are expected to be distributed normally with mean 0.5 and standard
deviation 0.0289.
Most significant deviation from 0.5 is obtained from the cipher Pomaranch
[13] using the coverage test with 14 variable IV bits. For a secure cipher, al-
though the probability that the average is less than 0
.
320433 is negligible, we
repeated the experiment 450 times and obtained the following histogram. As seen
from the figure, the distribution of
p
-values significantly deviates from uniform
distribution.
