**On Stream Ciphers with Provable Beyond-the-Birthday-Bound Security against Time-Memory-Data Tradeoff Attacks**

*Matthias Hamann and Matthias Krause*

**Abstract: **We propose and analyze the LIZARD-construction, a way to construct keystream generator (KSG) based stream ciphers with provable $\frac{2}{3} n$-security with respect to generic time-memory-data tradeoff attacks. Note that for the vast majority of known practical KSG-based stream ciphers such attacks reduce the effective key length to the birthday bound $n/2$, where $n$ denotes the inner state length of the underlying KSG. This implies that practical stream ciphers have to have a comparatively large inner state length (e.g., $n=288$ bit for Trivium and $n=160$ bit for Grain v1).

The LIZARD-construction proposes a state initialization algorithm for stream ciphers working in packet mode (like the GSM cipher A5/1 or the Bluetooth cipher $E_0$). The proposal is that for each packet $i$ the packet initial state $q^i_{init}$ is computed from the secret session key $k$ and the packet initial value $IV^{i}$ via $q^i_{init}=P(k\oplus IV^{i})\oplus k$, where $P$ denotes a state mixing algorithm. Note that the recently published cipher LIZARD (see ePrint 2016/926), a stream cipher having inner state length of only $121$ bit, is a lightweight practical instantiation of our proposal, which is competitive w.r.t. the usual hardware and power consumption metrics.

The main technical contribution of this paper is to introduce a formal ideal primitive model for KSG-based stream ciphers and to show the sharp $\frac{2}{3} n$-bound for the security of the LIZARD-construction against generic time-memory-data tradeoff attacks.

**Category / Keywords: **Stream Ciphers, Time-Memory-Data Tradeoff Attacks, Provable Security, Ideal Primitive Model, LIZARD

**Date: **received 26 Jun 2015, last revised 24 Feb 2017

**Contact author: **hamann at uni-mannheim de

**Available format(s): **PDF | BibTeX Citation

**Version: **20170224:184429 (All versions of this report)

**Short URL: **ia.cr/2015/636

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]