## The Collision Security of Tandem-DM
in the Ideal Cipher Model

**Jooyoung Lee, Martijn Stam, and John Steinberger**

*
Faculty of Mathematics and Statistics, Sejong University, Seoul, Korea;
Department of Computer Science, University of Bristol, United Kingdom;
and Institute of Theoretical Computer Science, Tsinghua University, Beijing, China*
**
Abstract.**
We prove that Tandem-DM, which is one of the two “classical”
schemes for turning a blockcipher of 2*n*-bit key into a double block
length hash function, has birthday-type collision resistance in the ideal
cipher model. A collision resistance analysis for Tandem-DM achieving
a similar birthday-type bound was already proposed by Fleischmann,
Gorski and Lucks at FSE 2009 [3]. 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 not used before in ideal cipher proofs.

**Keywords:**
Hash functions, collision resistance, ideal cipher model.