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

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