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].
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].
