The Security of Tandem-DM in the Ideal Cipher Model

详细信息    查看全文

• 作者：Jooyoung Lee ; Martijn Stam ; John Steinberger
• 关键词：Blockcipher ; Hash function ; Collision resistance ; Preimage resistance ; Ideal cipher
• 刊名：Journal of Cryptology
• 出版年：2017
• 出版时间：April 2017
• 年：2017
• 卷：30
• 期：2
• 页码：495-518
• 全文大小：
• 刊物类别：Computer Science
• 刊物主题：Coding and Information Theory; Computational Mathematics and Numerical Analysis; Combinatorics; Probability Theory and Stochastic Processes; Communications Engineering, Networks;
• 出版者：Springer US
• ISSN：1432-1378
• 卷排序：30

文摘

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\), 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}\).