Greedy distinguishers and nonrandomness detectors

Research output: Chapter in Book/Report/Conference proceedingPaper in conference proceedingpeer-review

481 Downloads (Pure)


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.
Original languageEnglish
Title of host publicationProgress in Cryptology - INDOCRYPT 2010 / Lecture Notes in Computer Science
EditorsGuang Gong, Kishan Chand Gupta
Number of pages17
ISBN (Print)978-3-642-17400-1
Publication statusPublished - 2010
EventINDOCRYPT 2010, 11th International Conference on Cryptology in India - Hyderabad, India
Duration: 2010 Dec 122010 Dec 15

Publication series

ISSN (Print)1611-3349
ISSN (Electronic)0302-9743


ConferenceINDOCRYPT 2010, 11th International Conference on Cryptology in India

Subject classification (UKÄ)

  • Electrical Engineering, Electronic Engineering, Information Engineering

Free keywords

  • algebraic cryptanalysis
  • distinguisher
  • nonrandomness detector
  • maximum degree monomial
  • Trivium
  • Grain
  • Rabbit
  • Edon80
  • AES
  • DES
  • XTEA
  • TEA
  • SEED
  • SMS4
  • Camellia
  • RC6
  • RC5
  • Sosemanuk
  • HC
  • Salsa


Dive into the research topics of 'Greedy distinguishers and nonrandomness detectors'. Together they form a unique fingerprint.

Cite this