On the Hardness of Trivium and Grain with respect to Generic Time-Memory-Data Tradeoff Attacks.
Matthias Krause · MADOC (University of Mannheim) · 2017
Time-Memory-Data tradeoff attacks (TMD-attacks) like those of Babbage [1], Biryukov and Shamir [2] and Dunkelman, Keller [5] 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 [3] and Grain [8] 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, 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 2M 2 n -M , (8L-4)M 2 2 L -(4L-2)M 2 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.