Skip to content

The Security of Tandem-DM in the Ideal Cipher Model

Research output: Contribution to journalArticle

  • Jooyoung Lee
  • Martijn Stam
  • John Steinberger
Original languageEnglish
Pages (from-to)495-518
Number of pages24
JournalJournal of Cryptology
Volume30
Issue number2
Early online date21 Mar 2016
DOIs
DateAccepted/In press - 15 Oct 2014
DateE-pub ahead of print - 21 Mar 2016
DatePublished (current) - 1 Apr 2017

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 has function, has birthday-type collision resistance in the ideal cipher model. For n=128, an adversary must make at least 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 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 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 22n/n blockcipher queries. This bound improves upon the previous best bound of Ω(2n) queries and is optimal (ignoring log factors) since Tandem-DM has range of size 22n.

Documents

View research connections

Related faculties, schools or groups