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 $160$) 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.