Greedy Distinguishers and Nonrandomness Detectors

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.