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 $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.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
Stream CiphersTime-Memory-Data Tradeoff AttacksProvable SecurityIdeal Primitive ModelLIZARD
Contact author(s)
hamann @ uni-mannheim de
History
2017-02-24: last of 4 revisions
2015-06-30: received
See all versions
Short URL
https://ia.cr/2015/636
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/636,
      author = {Matthias Hamann and Matthias Krause},
      title = {On Stream Ciphers with Provable Beyond-the-Birthday-Bound Security against Time-Memory-Data Tradeoff Attacks},
      howpublished = {Cryptology ePrint Archive, Paper 2015/636},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/636}},
      url = {https://eprint.iacr.org/2015/636}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.