On the Security of Tandem-DM

摘要

We provide the first proof of security for Tandem-DM, one of the oldest and most well-known constructions for turning a block cipher with n-bit block length and 2n-bit key length into a 2n-bit cryptographic hash function. We prove, that when Tandem-DM is instantiated with AES-256, block length 128 bits and key length 256 bits, any adversary that asks less than 2~(120.4) queries cannot find a collision with success probability greater than 1/2. We also prove a bound for preimage resistance of Tandem-DM.rnInterestingly, as there is only one practical construction known turning such an (n, 2n) bit block cipher into a 2n-bit compression function that has provably birthday-type collision resistance (FSE'06, Hirose), Tandem-DM is one out of two constructions that has this desirable feature.