Paper 2017/384

Time-Memory-Data Tradeoff Attacks against Small-State Stream Ciphers

Matthias Hamann, Matthias Krause, Willi Meier, and Bin Zhang


Time-memory-data (TMD) tradeoff attacks limit the security level of many classical stream ciphers (like $E_0$, A5/1, Trivium, Grain) to $\frac{1}{2}n$, where $n$ denotes the inner state length of the underlying keystream generator. This implies that to withstand TMD tradeoff attacks, the state size should be at least double the key size. In 2015, Armknecht and Mikhalev introduced a new line of research, which pursues the goal of reducing the inner state size of lightweight stream ciphers below this boundary by deploying a key-dependent state update function in a Grain-like stream cipher. Although their design Sprout was broken soon after publication, it has raised interest in the design principle, and a number of related ciphers have been suggested since, including Plantlet, a follow-up of Sprout, and the cipher Fruit. In this paper, existing TMD tradeoff attacks are revisited, and new insights on distinguishers and key recovery related to small-state stream ciphers are derived. A particular result is the transfer of a generic distinguishing attack suggested in 2007 by Englund, Hell, and Johansson to this new class of lightweight ciphers. Our analysis shows that the initial hope of achieving full security against TMD tradeoff attacks by continuously using the secret key has failed. In particular, we demonstrate that there are generic distinguishing attacks against Plantlet and Fruit with complexity significantly smaller than that of exhaustive key search. However, by studying the assumptions underlying the applicability of these attacks, we are able to come up with a new design idea for small-state stream ciphers which might allow to finally achieve full security against TMD tradeoff attacks. Another contribution of this paper is the first key recovery attack against the most recent version of Fruit. We show that there are at least $2^{64}$ weak keys, each of which does not provide 80-bit security as promised by designers. This new attack against Fruit, together with previous attacks against Sprout, raises the question whether a more complicated key schedule than the basic one used in Plantlet is actually beneficial for the security of such ciphers.

Available format(s)
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Stream CiphersLightweight CryptographyTime-Memory-Data Tradeoff AttacksPlantletFruit
Contact author(s)
hamann @ uni-mannheim de
2017-06-27: revised
2017-05-04: received
See all versions
Short URL
Creative Commons Attribution


      author = {Matthias Hamann and Matthias Krause and Willi Meier and Bin Zhang},
      title = {Time-Memory-Data Tradeoff Attacks against Small-State Stream Ciphers},
      howpublished = {Cryptology ePrint Archive, Paper 2017/384},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.