Skip to main content
Top
Published in: Journal of Cryptology 2/2017

21-03-2016

The Security of Tandem-DM in the Ideal Cipher Model

Authors: Jooyoung Lee, Martijn Stam, John Steinberger

Published in: Journal of Cryptology | Issue 2/2017

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Appendix
Available only for authorised users
Footnotes
1
 More formally, if its query history does not contain any triple of the form \((\cdot , U||V, W)\).
 
2
 More formally, if its query history does not contain any triple of the form \((U, V||W, \cdot )\).
 
3
 Neither do we, in fact. Using a careful trick, we manage to upper bound the number of good R’s by only considering the possibilities for the query BL rather than by considering the possible triples (BL, TR, BR). In the ePrint version of [10], however, we give for comparison the “brute-force” proof which uses the method of upper bounding the number of triples (BL, TR, BR).
 
Literature
1.
go back to reference F. Armknecht, E. Fleischmann, M. Krause, J. Lee, M. Stam and J. Steinberger, The preimage security of double-block-length compression functions. Asiacrypt 2011, LNCS 7073, pp. 233–251. Springer, Heidelberg (2011) F. Armknecht, E. Fleischmann, M. Krause, J. Lee, M. Stam and J. Steinberger, The preimage security of double-block-length compression functions. Asiacrypt 2011, LNCS 7073, pp. 233–251. Springer, Heidelberg (2011)
3.
go back to reference E. Fleischmann, C. Forler, M. Gorski and S. Lucks, Collision Resistant Double-Length Hashing. ProvSec 2010, LNCS 6401, pp. 102–118. Springer, Heidelberg (2010) E. Fleischmann, C. Forler, M. Gorski and S. Lucks, Collision Resistant Double-Length Hashing. ProvSec 2010, LNCS 6401, pp. 102–118. Springer, Heidelberg (2010)
4.
go back to reference E. Fleischmann, M. Gorski and S. Lucks, On the security of Tandem-DM. FSE 2009, LNCS 5665, pp. 84–103. Springer, Heidelberg (2009) E. Fleischmann, M. Gorski and S. Lucks, On the security of Tandem-DM. FSE 2009, LNCS 5665, pp. 84–103. Springer, Heidelberg (2009)
5.
go back to reference E. Fleischmann, M. Gorski and S. Lucks, Security of cyclic double block length hash functions, Cryptography and Coding, 12th IMA International Conference, Cirencester, UK, LNCS 5921 pp. 153–175. Springer, Heidelberg (2009) E. Fleischmann, M. Gorski and S. Lucks, Security of cyclic double block length hash functions, Cryptography and Coding, 12th IMA International Conference, Cirencester, UK, LNCS 5921 pp. 153–175. Springer, Heidelberg (2009)
6.
go back to reference S. Hirose, Provably secure double-block-length hash functions in a black-box model. ICISC 2004, LNCS 3506, pp. 330–342. Springer, Heidelberg (2005) S. Hirose, Provably secure double-block-length hash functions in a black-box model. ICISC 2004, LNCS 3506, pp. 330–342. Springer, Heidelberg (2005)
7.
go back to reference S. Hirose, Some plausible constructions of double-block-length hash functions. FSE 2006, LNCS 4047, pp. 210–225. Springer, Heidelberg (2006) S. Hirose, Some plausible constructions of double-block-length hash functions. FSE 2006, LNCS 4047, pp. 210–225. Springer, Heidelberg (2006)
8.
go back to reference X. Lai and J. Massey, Hash function based on block ciphers. Eurocrypt 1992, LNCS 658, pp. 55–70. Springer, Heidelberg (1993) X. Lai and J. Massey, Hash function based on block ciphers. Eurocrypt 1992, LNCS 658, pp. 55–70. Springer, Heidelberg (1993)
10.
11.
go back to reference J. Lee and J. Steinberger, Multi-property preservation using polynomial-based modes of operation, Eurocrypt 2010, LNCS 6110, pp. 573–596. Springer, Heidelberg (2010) J. Lee and J. Steinberger, Multi-property preservation using polynomial-based modes of operation, Eurocrypt 2010, LNCS 6110, pp. 573–596. Springer, Heidelberg (2010)
12.
go back to reference S. Lucks, A collision-resistant rate-1 double-block-length hash function. Symmetric Cryptography, Dagstuhl Seminar Proceedings 07021 (2007) S. Lucks, A collision-resistant rate-1 double-block-length hash function. Symmetric Cryptography, Dagstuhl Seminar Proceedings 07021 (2007)
13.
go back to reference O. Özen and M. Stam, Another Glance at Double-Length Hashing, Cryptography and Coding, 12th IMA International Conference, Cirencester, UK, LNCS 5921, pp. 94–115. Springer, Heidelberg (2009) O. Özen and M. Stam, Another Glance at Double-Length Hashing, Cryptography and Coding, 12th IMA International Conference, Cirencester, UK, LNCS 5921, pp. 94–115. Springer, Heidelberg (2009)
14.
go back to reference P. Rogaway and T. Shrimpton, Cryptographic hash-function basics: definitions, implications, and separations for preimage resistance, second-preimage resistance, and collision-resistance. FSE 2004, LNCS 3017, pp. 371–388. Springer, Heidelberg (2004) P. Rogaway and T. Shrimpton, Cryptographic hash-function basics: definitions, implications, and separations for preimage resistance, second-preimage resistance, and collision-resistance. FSE 2004, LNCS 3017, pp. 371–388. Springer, Heidelberg (2004)
15.
go back to reference P. Rogaway and J. Steinberger, Constructing cryptographic hash functions from fixed-key blockciphers. Crypto 2008, LNCS 5157, pp. 433–450. Springer, Heidelberg (2008) P. Rogaway and J. Steinberger, Constructing cryptographic hash functions from fixed-key blockciphers. Crypto 2008, LNCS 5157, pp. 433–450. Springer, Heidelberg (2008)
16.
go back to reference T. Satoh, M. Haga and K. Kurosawa, Towards secure and fast hash functions. IEICE Transactions 82-A(1), pp. 55–62. (1999) T. Satoh, M. Haga and K. Kurosawa, Towards secure and fast hash functions. IEICE Transactions 82-A(1), pp. 55–62. (1999)
17.
go back to reference T. Shrimpton and M. Stam, Building a collision-resistant compression function from non-compressing primitives. ICALP 2008, Part II. LNCS 5126, pp. 643–654, Springer, 2008. T. Shrimpton and M. Stam, Building a collision-resistant compression function from non-compressing primitives. ICALP 2008, Part II. LNCS 5126, pp. 643–654, Springer, 2008.
18.
go back to reference J. Steinberger, The collision intractability of MDC-2 in the ideal-cipher model, Eurocrypt 2007, LNCS 4515, pp. 34–51. Springer, Heidelberg (2007) J. Steinberger, The collision intractability of MDC-2 in the ideal-cipher model, Eurocrypt 2007, LNCS 4515, pp. 34–51. Springer, Heidelberg (2007)
19.
go back to reference M. Stam, Beyond uniformity: better security/efficiency tradeoffs for compression functions, Crypto 2008, LNCS 5157, pp. 397–412. Springer, Heidelberg (2008) M. Stam, Beyond uniformity: better security/efficiency tradeoffs for compression functions, Crypto 2008, LNCS 5157, pp. 397–412. Springer, Heidelberg (2008)
20.
go back to reference M. Stam, Blockcipher-based hashing revisited, FSE 2009, LNCS 5665, pp. 67–83. Springer, Heidelberg (2009) M. Stam, Blockcipher-based hashing revisited, FSE 2009, LNCS 5665, pp. 67–83. Springer, Heidelberg (2009)
21.
go back to reference D. Wagner, Cryptanalysis of the Yi-Lam hash, Asiacrypt 2000, LNCS 1976, pp. 483–488. Springer, Heidelberg (2000) D. Wagner, Cryptanalysis of the Yi-Lam hash, Asiacrypt 2000, LNCS 1976, pp. 483–488. Springer, Heidelberg (2000)
22.
go back to reference X. Yi and K.-Y. Lam, A new hash function based on block cipher. ACISP 1997, Second Australasian Conference on Information Security and Privacy, LNCS 1270, pp. 139–146. Springer, Heidelberg (1997) X. Yi and K.-Y. Lam, A new hash function based on block cipher. ACISP 1997, Second Australasian Conference on Information Security and Privacy, LNCS 1270, pp. 139–146. Springer, Heidelberg (1997)
Metadata
Title
The Security of Tandem-DM in the Ideal Cipher Model
Authors
Jooyoung Lee
Martijn Stam
John Steinberger
Publication date
21-03-2016
Publisher
Springer US
Published in
Journal of Cryptology / Issue 2/2017
Print ISSN: 0933-2790
Electronic ISSN: 1432-1378
DOI
https://doi.org/10.1007/s00145-016-9230-z

Other articles of this Issue 2/2017

Journal of Cryptology 2/2017 Go to the issue

Premium Partner