Information Technology Reference
In-Depth Information
New Distinguishers Based on Random Mappings
against Stream Ciphers
Meltem Sonmez Turan
1
, ¸agda¸s ¸ alık
1
, Nurdan Buz Saran
2
,
and Ali Doganaksoy
1
1
Institute of Applied Mathematics,
Middle East Technical University, Ankara, Turkey
2
Computer Engineering Department, ¸ ankaya University, Ankara, Turkey
{
msonmez, ccalik, e135760, aldoks
}
@metu.edu.tr
Abstract.
Statistical randomness testing plays an important role in
security analysis of cryptosystems. In this study, we aim to propose
a new framework of randomness testing based on random mappings.
Considering the probability distributions of coverage and
ρ
-lengths, we
present three new distinguishers; (i) coverage test, (ii)
-test and (iii) DP-
coverage test and applied them on Phase III Candidates of eSTREAM
project. We experimentally observed some statistical weaknesses of Po-
maranch using the coverage test.
ρ
Keywords:
Random Mappings, TMTO Attacks, Randomness tests,
Stream Ciphers.
1
Introduction
Random mappings are functions from a finite set of
n
elements into itself. They
are widely used in many combinatorial problems such as (i) proportion of empty
urns after throwing
n
balls into
n
urns, (ii) probability that two persons have the
same birthday among a group of
n
people, (iii) the required number of random
selections among
n
coupons to obtain a full collection, etc. Using a subset of key
and IV bits as input and a subset of keystream bits as output, it is possible to
form random mappings by using stream ciphers.
The problem of inverting (finding the pre-image of a given point) random
mappings has a great practical importance. For mappings generated by stream
ciphers, this problem corresponds to obtaining secret state bits using the out-
put keystream sequence, i.e. breaking the cipher. However, there is no known
ecient algorithm to find the pre-image of a given point for a random function.
Trivially, using exhaustive search, it is possible to check all possible inputs until
desired output is obtained, leading an excessive time requirement. Alternatively,
a lookup table that contains the pre-images of all points can be constructed,
resulting in a large memory requirement. To balance solution time and required
memory, Time Memory Tradeoff (TMTO) attacks are proposed as generic meth-
ods to invert random mappings [1].
