Paper 2020/046

On Analysis of Lightweight Stream Ciphers with Keyed Update

Orhun Kara and Muhammed F. Esgin


As the need for lightweight cryptography has grown even more due to the evolution of the Internet of Things, it has become a greater challenge for cryptographers to design ultra lightweight stream ciphers in compliance with the rule of thumb that the internal state size should be at least twice as the key size to defend against generic Time-Memory-Data Tradeoff (TMDT) attacks. However, recently in 2015, Armknecht and Mikhalev sparked a new light on designing keystream generators (KSGs), which in turn yields stream ciphers, with small internal states, called KSG with Keyed Update Function (KSG with KUF), and gave a concrete construction named Sprout. But, currently, security analysis of KSGs with KUF in a general setting is almost non-existent. Our contribution in this paper is two-fold. 1) We give a general mathematical setting for KSGs with KUF, and for the first time, analyze a class of such KSGs, called KSGs with Boolean Keyed Feedback Function (KSG with Boolean KFF), generically. In particular, we develop two generic attack algorithms applicable to any KSG with Boolean KFF having almost arbitrary output and feedback functions where the only requirement is that the secret key incorporation is biased. We introduce an upper bound for the time complexity of the first algorithm. Our extensive experiments validate our algorithms and assumptions made thereof. 2) We study Sprout to show the effectiveness of our algorithms in a practical instance. A straightforward application of our generic algorithm yields one of the most successful attacks on Sprout.

Note: Pre-print of an article published in IEEE Transactions on Computers (TC).

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. Minor revision. IEEE Transactions on Computers (TC)
Lightweight CipherKeystream generatorStream cipherTime-Memory-Data tradeoffKeyed Update FunctionSymmetric EncryptionSprout
Contact author(s)
orhun kara @ tubitak gov tr
muhammed esgin @ monash edu
2020-01-17: received
Short URL
Creative Commons Attribution


      author = {Orhun Kara and Muhammed F.  Esgin},
      title = {On Analysis of Lightweight Stream Ciphers with Keyed Update},
      howpublished = {Cryptology ePrint Archive, Paper 2020/046},
      year = {2020},
      doi = {10.1109/TC.2018.2851239},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.