Greedy distinguishers and nonrandomness detectors

Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

Abstract

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.

Detaljer

Författare
Enheter & grupper
Forskningsområden

Ämnesklassifikation (UKÄ) – OBLIGATORISK

  • Elektroteknik och elektronik

Nyckelord

Originalspråkengelska
Titel på värdpublikationProgress in Cryptology - INDOCRYPT 2010 / Lecture Notes in Computer Science
RedaktörerGuang Gong, Kishan Chand Gupta
FörlagSpringer
Sidor210-226
Antal sidor17
Volym6498
ISBN (tryckt)978-3-642-17400-1
StatusPublished - 2010
PublikationskategoriForskning
Peer review utfördJa
EvenemangINDOCRYPT 2010, 11th International Conference on Cryptology in India - Hyderabad, Indien
Varaktighet: 2010 dec 122010 dec 15

Publikationsserier

Namn
Volym6498
ISSN (tryckt)1611-3349
ISSN (elektroniskt)0302-9743

Konferens

KonferensINDOCRYPT 2010, 11th International Conference on Cryptology in India
LandIndien
OrtHyderabad
Period2010/12/122010/12/15

Nedladdningar

Ingen tillgänglig data