On Analysis of Lightweight Stream Ciphers with Keyed Update

Orhun Kara; Muhammed F.  Esgin

Paper 2020/046

On Analysis of Lightweight Stream Ciphers with Keyed Update

Orhun Kara and Muhammed F. Esgin

Abstract

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).

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Published elsewhere. Minor revision. IEEE Transactions on Computers (TC)
DOI: 10.1109/TC.2018.2851239
Keywords: Lightweight Cipher Keystream generator Stream cipher Time-Memory-Data tradeoff Keyed Update Function Symmetric Encryption Sprout
Contact author(s): orhun kara @ tubitak gov tr
muhammed esgin @ monash edu
History: 2020-01-17: received
Short URL: https://ia.cr/2020/046
License: CC BY

BibTeX

@misc{cryptoeprint:2020/046,
      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{https://eprint.iacr.org/2020/046}},
      url = {https://eprint.iacr.org/2020/046}
}