Information Technology Reference
In-Depth Information
It is possible to apply TMTO attacks to stream ciphers by various different
approaches [2,3,4,5]. The success probabilities of the attacks are calculated under
the assumption that the cipher behaves like a random mapping. To avoid the
attacks, some conditions for stream ciphers are given as (i) IV size should be at
least equal to key size, (ii) state size should be at least the size of key plus IV
and (iii) key size should be at least 80 bits [5].
In this study, we aim to analyze the security of stream ciphers based on some
properties of random mappings. By focusing on different TMTO attacks, we
try to find suitable test statistics. First, we consider the coverage of mappings
generated using a subset of IV bits, then we analyze the index of the first rep-
etition when the random mapping is iteratively applied. Finally, we consider
the distinguished point method against stream ciphers and analyze the coverage
properties of random mappings that are followed by a special keystream pattern.
Using these test statistics, we propose three new distinguishers namely (i) cov-
erage test, (ii)
ρ
-test and (iii) distinguished point (DP) coverage test and apply
these tests to the Phase III Candidates of eSTREAM project [6].
The organization of the paper is as follows. In the following section, some
preliminary information about random mappings is presented and then back-
ground knowledge on TMTO attacks focusing on stream ciphers are presented.
In Sect. 4, the new distinguishers are presented and in Sect. 5 experimental re-
sults on eSTREAM candidates are given. Finally, we conclude the paper in the
last section.
2
Preliminaries
Let
f
(
x
) be a random mapping
X
X
where
X
is a finite set of
n
elements.
Random mappings independently assign one of the image points
y
→
∈
X
for
X
. The sample space consists of
n
n
random mappings. For each
mapping
f
, we can associate the random variable
C
=
each input
x
∈
|
image of
f
|
.
Proposition 1.
Let us have
n
independent and identically distributed random
variables
X
1
,X
2
,...X
n
, each uniformly selected from the set
{
1
,
2
,...,n
}
.Let
A
k
be the number of selections that contain
k
different elements. The recursive
formulation of
A
k
is given as
A
k
=
n
k
k
n
k
i
A
k−i
k−i
k−
1
−
(1)
i
=1
where
A
1
=
1
.
Example 1.
Let
n
= 3. The total number of selections is 3
3
= 27. The selections
with
k
= 1 distinct elements are
{
111
,
222
,
333
}
,with
k
= 2 distinct elements
are
112
,
121
,
211
,
113
,
131
,
311
,
221
,
212
,
122
,
223
,
232
,
322
,
331
,
313
,
133
,
332
,
323
,
233
{
}
and with
k
= 3 distinct elements are
{
123
,
132
,
213
,
231
,
312
,
321
}
.
Then,
A
1
=3,
A
2
= 18,
A
3
= 6, with a total of 27.
