Information Technology Reference
In-Depth Information
In [5], the following remarks are given; (i) putting restriction on the number of
resynchronizations using a fixed key does not increase the security of the cipher
against TMTO, (ii) the complexity of the initialization phase has no effect on
the eciency of the attack, and (iii) the attack may be applied to any keystream
positionsaslongastheyareknown.
4
Chosen IV Statistical Attacks
In the following subsections, we present three new distinguishers against syn-
chronous stream ciphers, but they can also be used to test the security of
other cryptosystems such as block ciphers and hash functions. For a syn-
chronous stream cipher with
k
bit key
K
=(
k
1
,k
2
,...,k
k
)and
v
bit
IV
=
(
iv
1
,iv
2
,...,iv
v
), let
Z
=
z
0
,z
1
,...
denote the keystream sequence.
It is possible to test stream ciphers statistically in various ways. In a classical
way, a long keystream is generated and standard randomness tests such as fre-
quency, runs, etc. are applied [9]. Alternatively, it is also possible to use a chosen
IV approach and analyze the cipher using tests such as
d
-monomial [10] and cor-
relation tests [11]. In this study, we also considered the chosen IV approach where
the attacker has access to a number of different keystream sequences generated
using different (possibly chosen) IV values and same key.
In our tests, we used
Pearson's Chi Square (
χ
2
)test
that involves grouping
data into classes and comparing observed outcomes to the expected figures under
the null distribution. The test statistic is defined as
k
χ
2
=
e
i
)
2
/e
i
(
o
i
−
(6)
i
=1
where
o
i
and
e
i
is the observed and expected frequency for group
i
, respectively.
If the null hypothesis is true, then
χ
2
is distributed according to
χ
2
(
k
p
)
where
k
is the number of groups and
p
is the number of parameters estimated
from the data and the hypothesis is rejected if the test statistics
χ
2
−
1
−
is greater
than tabulated
χ
2
(1
−
α
;
k
−
1
−
p
) value for some significance level
α
with
k
−
1
−
p
degrees of freedom.
4.1 Coverage Test
The coverage test is a new probabilistic distinguisher against stream ciphers
where a table similar to the approach of Babbage-Golic is used. In the original
approach, output keystreams of length
n
(state size) are generated. Since for our
statistical test, it is impractical to use keystream bits of size as large as
n
,we
focus on a subset of IV bits (
l
out of
v
) and generate
l
bit keystreams.
First, we select
l
random (active) positions from IV and fix the rest (inactive)
bits to a random value. Then, we synchronize the cipher for all possible 2
l
IVs and
generate
l
bit keystream (
z
(
i
1
,z
(
i
2
,...,z
(
i
)
) for each IV as given in Fig. 3. Then,
l
