Cryptology ePrint Archive: Report 2015/636

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