Name
Abstract | ||
|---|---|---|
We prove that Tandem-DM, one of the two \"classical\" schemes for turning an n-bit blockcipher of 2n-bit key into a double-block-length hash function, has birthday-type collision resistance in the ideal cipher model. For $$n=128$$n=128, an adversary must make at least $$2^{120.87}$$2120.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$$n=128, we show that an adversary must make at least $$2^{245.99}$$2245.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$$22n/n blockcipher queries. This bound improves upon the previous best bound of $${{\\varOmega }}(2^n)$$Ω(2n) queries and is optimal (ignoring log factors) since Tandem-DM has range of size $$2^{2n}$$22n. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1007/s00145-016-9230-z | J. Cryptology |
Keywords | Field | DocType |
Blockcipher,Hash function,Collision resistance,Preimage resistance,Ideal cipher | Cipher,Discrete mathematics,Open problem,Collision resistance,Theoretical computer science,Collision,Mathematical proof,Hash function,Image (mathematics),Preimage attack,Mathematics | Journal |
Volume | Issue | ISSN |
30 | 2 | 0933-2790 |
Citations | PageRank | References |
1 | 0.37 | 22 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jooyoung Lee | 1 | 5 | 1.10 |
| Martijn Stam | 2 | 1659 | 67.36 |
| John P. Steinberger | 3 | 329 | 18.30 |