Paper 2015/232

Cryptanalysis of Full Sprout

Virginie Lallemand and María Naya-Plasencia

Abstract

A new method for reducing the internal state size of stream cipher registers has been proposed in FSE 2015, allowing to reduce the area in hardware implementations. Along with it, an instantiated proposal of a cipher was also proposed: Sprout. In this paper, we analyze the security of Sprout, and we propose an attack that recovers the whole key more than $2^{10}$ times faster than exhaustive search and has very low data complexity. The attack can be seen as a divide-and-conquer evolved technique, that exploits the non-linear influence of the key bits on the update function. We have implemented the attack on a toy version of Sprout, that conserves the main properties exploited in the attack. The attack completely matches the expected complexities predicted by our theoretical cryptanalysis, which proves its validity. We believe that our attack shows that a more careful analysis should be done in order to instantiate the proposed design method.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Stream cipherCryptanalysisLightweightSprout
Contact author(s)
virginie lallemand @ inria fr
History
2015-08-20: last of 3 revisions
2015-03-12: received
See all versions
Short URL
https://ia.cr/2015/232
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/232,
      author = {Virginie Lallemand and María Naya-Plasencia},
      title = {Cryptanalysis of Full Sprout},
      howpublished = {Cryptology ePrint Archive, Paper 2015/232},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/232}},
      url = {https://eprint.iacr.org/2015/232}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.