# zbMATH — the first resource for mathematics

Greedy distinguishers and nonrandomness detectors. (English) Zbl 1294.94078
Gong, Guang (ed.) et al., Progress in cryptology – INDOCRYPT 2010. 11th international conference on cryptology in India, Hyderabad, India, December 12–15, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-17400-1/pbk). Lecture Notes in Computer Science 6498, 210-226 (2010).
Summary: We present the concept of greedy distinguishers and show how some simple observations and the well known greedy heuristic can be combined into a very powerful strategy (the Greedy Bit Set Algorithm) for efficient and systematic construction of distinguishers and nonrandomness detectors. We show how this strategy can be applied to a large array of stream and block ciphers, and we show that our method outperforms every other method we have seen so far by presenting new and record-breaking results for Trivium, Grain-128 and Grain v1.
We show that the greedy strategy reveals weaknesses in Trivium reduced to 1026 (out of 1152) initialization rounds using $$2^{45}$$ complexity – a result that significantly improves all previous efforts. This result was further improved using a cluster; 1078 rounds at $$2^{54}$$ complexity. We also present an 806-round distinguisher for Trivium with $$2^{44}$$ complexity.
Distinguisher and nonrandomness records are also set for Grain-128. We show nonrandomness for the full Grain-128 with its 256 (out of 256) initialization rounds, and present a 246-round distinguisher with complexity $$2^{42}$$.
For Grain v1 we show nonrandomness for 96 (out of 256) initialization rounds at the very modest complexity of $$2^{7}$$, and a 90-round distinguisher with complexity $$2^{39}$$.
On the theoretical side we define the Nonrandomness Threshold, which explicitly expresses the nature of the randomness limit that is being explored.
For the entire collection see [Zbl 1202.94009].

##### MSC:
 94A60 Cryptography 68P25 Data encryption (aspects in computer science)
##### Software:
eSTREAM; Camellia; TEA ; PRESENT; MICKEY; Rabbit ; Grain; HIGHT; Edon80; CLEFIA; XTEA ; SOSEMANUK
Full Text: