We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
The Security of Tandem-DM in the Ideal Cipher Model.
- Authors
Lee, Jooyoung; Stam, Martijn; Steinberger, John
- Abstract
We prove that Tandem-DM, one of the two 'classical' schemes for turning an n-bit blockcipher of 2 n-bit key into a double-block-length hash function, has birthday-type collision resistance in the ideal cipher model. For $$n=128$$ , an adversary must make at least $$2^{120.87}$$ blockcipher queries to achieve chance 0.5 of finding a collision. A collision resistance analysis for Tandem-DM achieving a similar birthday-type bound was already proposed by Fleischmann, Gorski and Lucks at FSE 2009. As we detail, however, the latter analysis is wrong, thus leaving the collision resistance of Tandem-DM as an open problem until now. Our analysis exhibits a novel feature in that we introduce a trick never used before in ideal cipher proofs. We also give an improved bound on the preimage security of Tandem-DM. For $$n=128$$ , we show that an adversary must make at least $$2^{245.99}$$ blockcipher queries to achieve chance 0.5 of inverting a randomly chosen point in the range. Asymptotically, Tandem-DM is proved to be preimage resistant up to $$2^{2n}/n$$ blockcipher queries. This bound improves upon the previous best bound of $${{\varOmega }}(2^n)$$ queries and is optimal (ignoring log factors) since Tandem-DM has range of size $$2^{2n}$$ .
- Subjects
BLOCK ciphers; COMPUTER security; HASHING; FACTORS (Algebra); CONSTRUCTIVE proofs
- Publication
Journal of Cryptology, 2017, Vol 30, Issue 2, p495
- ISSN
0933-2790
- Publication type
Article
- DOI
10.1007/s00145-016-9230-z