Greedy distinguishers and nonrandomness detectors
Stankovski, Paul LU
(2010)
INDOCRYPT 2010, 11th International Conference on Cryptology in India
6498.
p.210-226
- 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... (More) - 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. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/1747288
- author
- Stankovski, Paul
LU
- organization
- publishing date
- 2010
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- keywords
- algebraic cryptanalysis, distinguisher, nonrandomness detector, maximum degree monomial, Trivium, Grain, Rabbit, Edon80, AES, DES, XTEA, TEA, SEED, PRESENT, SMS4, Camellia, RC6, RC5, HIGHT, CLEFIA, Sosemanuk, HC, MICKEY, Salsa
- host publication
- Progress in Cryptology - INDOCRYPT 2010 / Lecture Notes in Computer Science
- editor
- Gong, Guang and Gupta, Kishan Chand
- volume
- 6498
- pages
- 17 pages
- publisher
- Springer
- conference name
- INDOCRYPT 2010, 11th International Conference on Cryptology in India
- conference location
- Hyderabad, India
- conference dates
- 2010-12-12 - 2010-12-15
- external identifiers
-
- wos:000293683800016
- scopus:78651077262
- ISSN
- 0302-9743
- 1611-3349
- ISBN
- 978-3-642-17400-1
- DOI
- 10.1007/978-3-642-17401-8_16
- language
- English
- LU publication?
- yes
- id
- 3b8b8665-25eb-4d19-8305-f2614cc67a95 (old id 1747288)
- date added to LUP
- 2016-04-01 09:56:19
- date last changed
- 2025-01-14 01:46:41
@inproceedings{3b8b8665-25eb-4d19-8305-f2614cc67a95,
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.<br/><br>
<br/><br>
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.<br/><br>
<br/><br>
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}$.<br/><br>
<br/><br>
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}$.<br/><br>
<br/><br>
On the theoretical side we define the Nonrandomness Threshold, which explicitly expresses the nature of the randomness limit that is being explored.}},
author = {{Stankovski, Paul}},
booktitle = {{Progress in Cryptology - INDOCRYPT 2010 / Lecture Notes in Computer Science}},
editor = {{Gong, Guang and Gupta, Kishan Chand}},
isbn = {{978-3-642-17400-1}},
issn = {{0302-9743}},
keywords = {{algebraic cryptanalysis; distinguisher; nonrandomness detector; maximum degree monomial; Trivium; Grain; Rabbit; Edon80; AES; DES; XTEA; TEA; SEED; PRESENT; SMS4; Camellia; RC6; RC5; HIGHT; CLEFIA; Sosemanuk; HC; MICKEY; Salsa}},
language = {{eng}},
pages = {{210--226}},
publisher = {{Springer}},
title = {{Greedy distinguishers and nonrandomness detectors}},
url = {{https://lup.lub.lu.se/search/files/1406305/1747313.pdf}},
doi = {{10.1007/978-3-642-17401-8_16}},
volume = {{6498}},
year = {{2010}},
}