Cryptology ePrint Archive: Report 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.

Category / Keywords: secret-key cryptography / Lightweight Cipher, Keystream generator, Stream cipher, Time-Memory-Data tradeoff, Keyed Update Function, Symmetric Encryption, Sprout

Original Publication (with minor differences): IEEE Transactions on Computers (TC)

Date: received 15 Jan 2020

Contact author: orhun kara at tubitak gov tr,muhammed esgin@monash edu

Available format(s): PDF | BibTeX Citation

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

Version: 20200117:082605 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]