Skip to main content

2017 | OriginalPaper | Buchkapitel

Efficient Construction of Diamond Structures

verfasst von : Ariel Weizmann, Orr Dunkelman, Simi Haber

Erschienen in: Progress in Cryptology – INDOCRYPT 2017

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

A cryptographic hash function is a function \(H:\{0,1\}^{*}\rightarrow \{0,1\}^{n}\), that takes an arbitrary long input and transforms it to an n-bit output, while keeping some basic properties that ensure its security. Because they are very useful in computer security, cryptographic hash functions are amongst the most important primitives in the modern cryptography.
The Merkle-Damgård structure is an iterative construction for transforming a compression function \(f:\{0,1\}^{n}\times \{0,1\}^{m}\rightarrow \{0,1\}^{n}\) into a hash function, and it is widely used by different hash functions such as MD4, MD5, SHA0 and SHA1. Some generic attacks on this structure were presented in the last 15 years. Some of these attacks use the diamond structure, first introduced by Kelsey and Kohno in the herding attack. This structure is a complete binary tree that allows \(2^{k}\) different inputs to lead to the same hash value, and it used in numerous attacks on the Merkle-Damgård structure. Following the herding attack, other papers analyzed and optimized the diamond structure. The best time complexity of constructing a diamond structure to date is about \(a \cdot 2^{\frac{n+k}{2}+2}\) for \(a\approx 2.732\).
In this work we suggest a new and simple method for constructing a diamond structure with better time complexity of \(c\,\cdot \,2^{\frac{n+k}{2}+2}\) for \(c\approx 1.254\). We present a pseudo-code for this new method, and a recursive formulation of it. We also present analysis supported by experiments of our new method.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Fußnoten
1
It is common to set \(2^{\ell }-1\) as the maximal length of a message.
 
2
He should consider the length of the prefix P, or at least the maximum length of it, and if the real length is less than he considered, he can add some blocks to the \(M_{link}\) block, which will defined in the second phase.
 
3
The degree of each vertex follows a Poisson distribution with a mean of 2. Thus, for each vertex, the probability that it is an isolated vertex is \(e^{-2}\), and thus we expect to about \(2^{k}\cdot e^{-2}\) isolated vertices.
 
4
Blackburn et al. [6] discuss another model to represent the diamond construction: Sampling With Replacement Random Intersection Graph \(G_{SWR}(\nu ,m,L)\) random graph, defined as follow: Let V be a set of vertices where \(|V|=\nu \) (in our case \(\nu =2^{k}\)), and F be a colors set where \(|F|=m\) (in our case \(m=2^{n}\)). For each vertex \(v\in V\) generate a subset \(F_{v}\subset F\) by sampling uniformly with replacement L colors from F (in Kelsey-Kohno’s case \(L=2^{\frac{n-k+1}{2}}\)). Finally, \((v,u)\in E\iff F_{v}\cap F_{u}\ne \phi \). They achieve from this model the same results as from the G(np) model.
 
5
Although usually we are looking for collisions, this requirement about the cardinality of \(H_{k,0}\) is needed for their analysis. Later, by our method, we will show how to use such collisions. If there are collisions, they replace the appropriate message blocks one by one until the required cardinality is obtained.
 
6
If not, they replace some message blocks one by one until it is obtained.
 
7
We note that the analysis of [20] uses a slightly different definition of a, but for more natural comparison with previous methods, we took a as the coefficient of \(2^{\frac{n+k}{2}+2}\).
 
8
We tested this idea on more cases: when \(|E|\sim Poi(a\cdot |V|), a = 0.5 + \frac{t}{20},\forall t\in \{0,1,2,\dots ,19\}\). The difference between the results in the Kelsey-Kohno’s case and the best results is quite small (less than one standard deviation).
 
9
It is easy to see that if we switch to the Blackburn et al. process earlier, the expected length of the diamond will decrease.
 
10
We note that the mean value of the experiment is greater than those of the recursion by a few standard deviation units. This difference is a subject for a future research.
 
11
We note that the mean value of the experiment is greater than those of the recursion by a few s.d. units. This difference is a subject for a future research.
 
Literatur
1.
Zurück zum Zitat Andreeva, E., Bouillaguet, C., Dunkelman, O., Fouque, P., Hoch, J.J., Kelsey, J., Shamir, A., Zimmer, S.: New second-preimage attacks on hash functions. J. Cryptol. 29(4), 657–696 (2016)MathSciNetCrossRefMATH Andreeva, E., Bouillaguet, C., Dunkelman, O., Fouque, P., Hoch, J.J., Kelsey, J., Shamir, A., Zimmer, S.: New second-preimage attacks on hash functions. J. Cryptol. 29(4), 657–696 (2016)MathSciNetCrossRefMATH
2.
Zurück zum Zitat Aronson, J., Frieze, A., Pittel, B.G.: Maximum matchings in sparse random graphs: Karp-Sipser revisited. Random Struct. Algorithms 12, 111–178 (1998)MathSciNetCrossRefMATH Aronson, J., Frieze, A., Pittel, B.G.: Maximum matchings in sparse random graphs: Karp-Sipser revisited. Random Struct. Algorithms 12, 111–178 (1998)MathSciNetCrossRefMATH
4.
Zurück zum Zitat Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: Keccak sponge function family main document. Submiss. NIST (Round 2) 3, 30 (2009) Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: Keccak sponge function family main document. Submiss. NIST (Round 2) 3, 30 (2009)
5.
Zurück zum Zitat Biham, E., Chen, R., Joux, A., Carribault, P., Lemuet, C., Jalby, W.: Collisions of SHA-0 and reduced SHA-1. In: Cramer [8], pp. 36–57 Biham, E., Chen, R., Joux, A., Carribault, P., Lemuet, C., Jalby, W.: Collisions of SHA-0 and reduced SHA-1. In: Cramer [8], pp. 36–57
6.
Zurück zum Zitat Blackburn, S.R., Stinson, D.R., Upadhyay, J.: On the complexity of the herding attack and some related attacks on hash functions. Des. Codes Crypt. 64(1–2), 171–193 (2012)MathSciNetCrossRefMATH Blackburn, S.R., Stinson, D.R., Upadhyay, J.: On the complexity of the herding attack and some related attacks on hash functions. Des. Codes Crypt. 64(1–2), 171–193 (2012)MathSciNetCrossRefMATH
9.
Zurück zum Zitat Damgård, I.: A design principle for hash functions. In: Brassard [7], pp. 416–427 Damgård, I.: A design principle for hash functions. In: Brassard [7], pp. 416–427
10.
Zurück zum Zitat Dean, R.D.: Formal aspects of mobile code security. Ph.D. thesis, Princeton University, Princeton (1999) Dean, R.D.: Formal aspects of mobile code security. Ph.D. thesis, Princeton University, Princeton (1999)
11.
Zurück zum Zitat Erdös, P., Rényi, A.: On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci 5, 17–61 (1960)MathSciNetMATH Erdös, P., Rényi, A.: On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci 5, 17–61 (1960)MathSciNetMATH
12.
Zurück zum Zitat Erdös, P., Rényi, A.: On the strength of connectedness of a random graph. Acta Math. Hung. 12(1–2), 261–267 (1961)MathSciNetMATH Erdös, P., Rényi, A.: On the strength of connectedness of a random graph. Acta Math. Hung. 12(1–2), 261–267 (1961)MathSciNetMATH
13.
Zurück zum Zitat Erdös, P., Rényi, A.: On the existence of a factor of degree one of a connected random graph. Acta Math. Hung. 17(3–4), 359–368 (1966)MathSciNetCrossRefMATH Erdös, P., Rényi, A.: On the existence of a factor of degree one of a connected random graph. Acta Math. Hung. 17(3–4), 359–368 (1966)MathSciNetCrossRefMATH
14.
Zurück zum Zitat Hoch, Y.Z.: Security analysis of generic iterated hash functions. Ph.D. thesis, Weizmann Institute of Science, Rehovot, Israel (2009) Hoch, Y.Z.: Security analysis of generic iterated hash functions. Ph.D. thesis, Weizmann Institute of Science, Rehovot, Israel (2009)
16.
Zurück zum Zitat Karp, R.M., Sipser, M.: Maximum matchings in sparse random graphs. In: 22nd Annual Symposium on Foundations of Computer Science, Nashville, Tennessee, USA, 28–30 October 1981, pp. 364–375. IEEE Computer Society (1981) Karp, R.M., Sipser, M.: Maximum matchings in sparse random graphs. In: 22nd Annual Symposium on Foundations of Computer Science, Nashville, Tennessee, USA, 28–30 October 1981, pp. 364–375. IEEE Computer Society (1981)
18.
Zurück zum Zitat Kelsey, J., Schneier, B.: Second preimages on n-bit hash functions for much less than 2\(^{\rm n}\) work. In: Cramer [8], pp. 474–490 Kelsey, J., Schneier, B.: Second preimages on n-bit hash functions for much less than 2\(^{\rm n}\) work. In: Cramer [8], pp. 474–490
19.
Zurück zum Zitat Klima, V.: Finding MD5 collisions on a notebook PC using multi-message modifications. Cryptology ePrint Archive, Report 2005/102 (2005) Klima, V.: Finding MD5 collisions on a notebook PC using multi-message modifications. Cryptology ePrint Archive, Report 2005/102 (2005)
20.
Zurück zum Zitat Kortelainen, T.: On iteration-based security flaws in modern hash functions. Ph.D. thesis, University of Oulu, Finland (2014) Kortelainen, T.: On iteration-based security flaws in modern hash functions. Ph.D. thesis, University of Oulu, Finland (2014)
22.
Zurück zum Zitat Merkle, R.C.: One way hash functions and DES. In: Brassard [7], pp. 428–446 Merkle, R.C.: One way hash functions and DES. In: Brassard [7], pp. 428–446
23.
Zurück zum Zitat Rivest, R.L.: Abelian square-free dithering for iterated hash functions. Presented at ECRYPT hash function workshop, Cracow, 21 June 2005, and at the cryptographic hash workshop, Gaithersburg, Maryland, 1 November 2005, August 2005 Rivest, R.L.: Abelian square-free dithering for iterated hash functions. Presented at ECRYPT hash function workshop, Cracow, 21 June 2005, and at the cryptographic hash workshop, Gaithersburg, Maryland, 1 November 2005, August 2005
25.
Zurück zum Zitat Stevens, M.: Attacks on hash functions and applications. Ph.D. thesis, Leiden University (2012) Stevens, M.: Attacks on hash functions and applications. Ph.D. thesis, Leiden University (2012)
26.
27.
Zurück zum Zitat Wang, X., Lai, X., Feng, D., Chen, H., Yu, X.: Cryptanalysis of the hash functions MD4 and RIPEMD. In: Cramer [8], pp. 1–18 Wang, X., Lai, X., Feng, D., Chen, H., Yu, X.: Cryptanalysis of the hash functions MD4 and RIPEMD. In: Cramer [8], pp. 1–18
29.
Zurück zum Zitat Wang, X., Yu, H.: How to break MD5 and other hash functions. In: Cramer [8], pp. 19–35 Wang, X., Yu, H.: How to break MD5 and other hash functions. In: Cramer [8], pp. 19–35
Metadaten
Titel
Efficient Construction of Diamond Structures
verfasst von
Ariel Weizmann
Orr Dunkelman
Simi Haber
Copyright-Jahr
2017
DOI
https://doi.org/10.1007/978-3-319-71667-1_9