Paper 2017/289

On the Hardness of Trivium and Grain with respect to Generic Time-Memory-Data Tradeoff Attacks

Matthias Krause

Abstract

Time-Memory-Data tradeoff attacks (TMD-attacks) like those of Babbage, Biryukov and Shamir, and Dunkelman and Keller reduce the security level of keystream generator based-stream 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 small-key-large-state design principle really provides the maximal possible security of min{n,L2} w.r.t. to TMD-attacks, or if it opens the door for new TMD-attack approaches, which possibly allow to discover a secret inner state and/or the secret session key with cost essentially lower than 2n. We give an answer by analyzing the security of stream ciphers like Trivium and Grain w.r.t. generic TMD-attacks in an appropriate random oracle model. We show that each TMD-attacker with TMD-costs bounded by can only achieve an advantage of 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 TMD-attacks mentioned above.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Stream CiphersTime-Memory-Data Tradeoff AttacksSecurity Lower Bound ProofsRandom Oracle Models
Contact author(s)
krause @ uni-mannheim de
History
2017-04-03: received
Short URL
https://ia.cr/2017/289
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/289,
      author = {Matthias Krause},
      title = {On the Hardness of Trivium and Grain with respect to Generic Time-Memory-Data Tradeoff Attacks},
      howpublished = {Cryptology {ePrint} Archive, Paper 2017/289},
      year = {2017},
      url = {https://eprint.iacr.org/2017/289}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.