Paper 2017/289
On the Hardness of Trivium and Grain with respect to Generic TimeMemoryData Tradeoff Attacks
Matthias Krause
Abstract
TimeMemoryData tradeoff attacks (TMDattacks) like those of Babbage, Biryukov and Shamir, and Dunkelman and Keller reduce the security level of keystream generator basedstream ciphers to $L/2$, where $L$ denotes the inner state length. This is one of the reasons why stream ciphers like Trivium and Grain use a session key length $n$ of at most $L/2$. In this paper, we deal with the question if this smallkeylargestate design principle really provides the maximal possible security of $\min\{n,\frac{L}{2}\}$ w.r.t. to TMDattacks, or if it opens the door for new TMDattack approaches, which possibly allow to discover a secret inner state and/or the secret session key with cost essentially lower than $2^n$. We give an answer by analyzing the security of stream ciphers like Trivium and Grain w.r.t. generic TMDattacks in an appropriate random oracle model. We show that each TMDattacker with TMDcosts bounded by $M$ can only achieve an advantage of $\min\left\{\frac{2M}{2^nM},\frac{(8L4)M^2}{2^L(4L2)M^2}\right\}$ for distinguishing a truly random bitstream from a pseudorandom bitstream generated by the stream cipher. This lower bound matches the security upper bounds defined by exhaustive key search and the classical TMDattacks mentioned above.
Metadata
 Available format(s)
 Category
 Secretkey cryptography
 Publication info
 Preprint. MINOR revision.
 Keywords
 Stream CiphersTimeMemoryData Tradeoff AttacksSecurity Lower Bound ProofsRandom Oracle Models
 Contact author(s)
 krause @ unimannheim de
 History
 20170403: received
 Short URL
 https://ia.cr/2017/289
 License

CC BY
BibTeX
@misc{cryptoeprint:2017/289, author = {Matthias Krause}, title = {On the Hardness of Trivium and Grain with respect to Generic TimeMemoryData Tradeoff Attacks}, howpublished = {Cryptology {ePrint} Archive, Paper 2017/289}, year = {2017}, url = {https://eprint.iacr.org/2017/289} }