Welcome to the resource topic for 2017/289
Title:
On the Hardness of Trivium and Grain with respect to Generic Time-Memory-Data Tradeoff Attacks
Authors: 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,\frac{L}{2}\} 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 2^n. 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 M can only achieve an advantage of \min\left\{\frac{2M}{2^n-M},\frac{(8L-4)M^2}{2^L-(4L-2)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 TMD-attacks mentioned above.
ePrint: https://eprint.iacr.org/2017/289
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .