Practical cryptanalysis of full sprout with TMD tradeoff attacks

Muhammed F. Esgin, Orhun Kara

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

13 Citations (Scopus)

Abstract

The internal state size of a stream cipher is supposed to be at least twice the key length to provide resistance against the conventional Time-Memory-Data (TMD) tradeoff attacks. This well adopted security criterion seems to be one of the main obstacles in designing, particularly, ultra lightweight stream ciphers. At FSE 2015, Armknecht and Mikhalev proposed an elegant design philosophy for stream ciphers as fixing the key and dividing the internal states into equivalence classes where any two different keys always produce non-equivalent internal states. The main concern in the design philosophy is to decrease the internal state size without compromising the security against TMD tradeoff attacks. If the number of equivalence classes is more than the cardinality of the key space, then the cipher is expected to be resistant against TMD tradeoff attacks even though the internal state (except the fixed key) is of fairly small length. Moreover, Armknecht and Mikhalev presented a new design, which they call Sprout, to embody their philosophy. In this work, ironically, we mount a TMD tradeoff attack on Sprout within practical limits using 2d output bits in 271−d encryptions of Sprout along with 2d table lookups. The memory complexity is 286−d where d ≤ 40. In one instance, it is possible to recover the key in 231 encryptions and 240 table lookups if we have 240 bits of keystream output by using tables of 770 Terabytes in total. The offline phase of preparing the tables consists of solving roughly 241.3 systems of linear equations with 20 unknowns and an effort of about 235 encryptions. Furthermore, we mount a guess-and-determine attack having a complexity about 268 encryptions with negligible data and memory. We have verified our attacks by conducting several experiments. Our results show that Sprout can be practically broken.

Original languageEnglish
Title of host publicationSelected Areas in Cryptography – SAC 2015
Subtitle of host publication22nd International Conference Sackville, NB, Canada, August 12–14, 2015 Revised Selected Papers
EditorsOrr Dunkelman, Liam Keliher
Place of PublicationCham Switzerland
PublisherSpringer
Pages67-85
Number of pages19
ISBN (Electronic)9783319313016
ISBN (Print)9783319313009
DOIs
Publication statusPublished - 2015
Externally publishedYes
EventSelected Areas in Cryptography 2015 - Sackville, Canada
Duration: 12 Aug 201514 Aug 2015
Conference number: 22nd
https://link.springer.com/book/10.1007/978-3-319-31301-6 (Proceedings)
http://sacworkshop.org/SAC15/index.html (conference website)

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume9566
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceSelected Areas in Cryptography 2015
Abbreviated titleSAC 2015
Country/TerritoryCanada
CitySackville
Period12/08/1514/08/15
Internet address

Keywords

  • Divide-and-conquer
  • Guess-and-determine
  • Keystream generator
  • LFSR
  • NLFSR
  • Sprout
  • Stream cipher
  • Time Memory Data tradeoff attacks

Cite this