Paper 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 $$). The proposal is that for each packet $$ the packet initial state $$ is computed from the secret session key $$ and the packet initial value $$ via $$, where $$ 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 $$ 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 $$-bound for the security of the LIZARD-construction against generic time-memory-data tradeoff attacks.