Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Optical Cryptography for Cyber Secured and Stealthy Fiber-Optic Communication Transmission Read chapter Read first chapter

2018 | OriginalPaper | Chapter

Efficient Construction of the Kite Generator Revisited

Authors : Orr Dunkelman, Ariel Weizman

Published in: Cyber Security Cryptography and Machine Learning

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

The kite generator, first introduced by Andreeva et al. [1], is a strongly connected directed graph that allows creating a message of almost any desired length, connecting two chaining values covered by the kite generator. The kite generator can be used in second pre-image attacks against (dithered) Merkle-Damgård hash functions.
In this work we discuss the complexity of constructing the kite generator. We show that the analysis of the construction of the kite generator first described by Andreeva et al. is somewhat inaccurate and discuss its actual complexity. We follow with presenting a new method for a more efficient construction of the kite generator, cutting the running time of the preprocessing by half (compared with the original claims of Andreeva et al. or by a linear factor compared to corrected analysis). Finally, we adapt the new method to the dithered Merkle-Damgård structure.

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!

inform now

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!

inform now

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!

inform now
previous chapter Optical Cryptography for Cyber Secured and Stealthy Fiber-Optic Communication Transmission
next chapter Using Noisy Binary Search for Differentially Private Anomaly Detection
Footnotes
1
We describe here the standard padding step done in many real hash functions such as MD5 and SHA1. Other variants of this step exist, all aiming to achieve prefix-freeness.
 
2
It is common to set \(2^{\ell }-1\) as the maximal length of a message.
 
3
Note that using this method \(d_{out}(a)\) follows a Poi(2) distribution, and about \(13\%\) of the chaining values are expected to have \(d_{out}(a)=0\). To solve this issue, it is possible to generate for each chaining value as many message blocks as needed to find two out-edges. Now, the average time complexity needed for a chaining value a is \(2^{k+1}\). The actual running time for a given chaining value is the sum of two geometric random variables with mean \(2^k\) each. Hence, the total running time is the sum of \(2^{n-k+1}\) geometric random variables \(X_i\sim Geo(2^{-k})\). Since \(\sum _{i=1}^{2^{n-k+1}}(X_i-1)\sim NB(2^{n-k+1},1-2^{-k})\), then \(\sum _{i=1}^{2^{n-k+1}}X_i\sim 2^{n-k+1}+NB(2^{n-k+1},1-2^{-k})\). Therefore, \(E[\sum _{i=1}^{2^{n-k+1}}X_i]=2^{n-k+1}+\frac{(1-2^{-k})2^{n-k+1}}{2^{-k}} = 2^{n+1}\) with a standard deviation of \(\frac{\sqrt{2^{n-k+1}(1-2^{-k})}}{2^{-k}}\le 2^{\frac{n+k+1}{2}}\).
 
4
Andreeva et al. [1] note that it is possible to find the common chaining value by a more sophisticated algorithm which requires the same time but negligible additional memory, using memoryless collision finding. Our findings affect these variants as well.
 
5
It is not necessary to use only two different message blocks in the setting, but it is possible since they are used for different chaining values.
 
6
With high probability we expect some collisions in A. This can be easily solved during the construction: If a chaining value \(f(h_i,m_j)\) is already generated, replace the message block \(m_j\) one by one until a new chaining value is reached. It is easy to see that the additional time complexity is negligible.
 
7
Again, in this step we actually need to generate for each chaining value as many message blocks as needed to find two out-edges. Now, the average time complexity needed for a chaining value a is \(2^{k+1}\). The actual running time for a given chaining value is the sum of two geometric random variables with mean \(2^k\) each. Hence, the total running time is the sum of \(2^{n-k}\) geometric random variables \(X_i\sim Geo(2^{-k})\). Since \(\sum _{i=1}^{2^{n-k}}(X_i-1)\sim NB(2^{n-k},1-2^{-k})\), then \(\sum _{i=1}^{2^{n-k}}X_i\sim 2^{n-k}+NB(2^{n-k},1-2^{-k})\). Therefore, \(E[\sum _{i=1}^{2^{n-k}}X_i]=2^{n-k}+\frac{(1-2^{-k})2^{n-k}}{2^{-k}} = 2^{n}\) with a standard deviation of \(\frac{\sqrt{2^{n-k}(1-2^{-k})}}{2^{-k}}\le 2^{\frac{n+k}{2}}\).
 
8
This issue happens also in the online phase, when the adversary looks for common chaining values between the two lists described in Sect. 3.1. The fixing is similarly – increase the size of these lists accordingly.
 
Literature
1.
Andreeva, E., Bouillaguet, C., Dunkelman, O., Fouque, P.-A., Hoch, J., Kelsey, J., Shamir, A., Zimmer, S.: New second-preimage attacks on hash functions. J. Cryptol. 29(4), 657–696 (2016)MathSciNetCrossRef
2.
3.
Athreya, K.B., Ney, P.E.: Dover books on mathematics. In: Branching Processes, pp. 1–8. Dover Publications, New York (2004). Chap. 1
4.
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)MathSciNetCrossRef
5.
6.
Dean, R.D.: Formal aspects of mobile code security. Ph.D. thesis, Princeton University, Princeton (1999)
7.
8.
9.
10.
11.
12.
National Institute of Standards and Technology: Secure hash standard. FIPS, PUB 17, 3–180 (1995)
13.
Rivest, R.L.: Abelian square-free dithering for iterated hash functions. In: ECrypt Hash Function Workshop, vol. 21, June 2005
14.
Metadata
Title
Efficient Construction of the Kite Generator Revisited
Authors
Orr Dunkelman
Ariel Weizman
Copyright Year
2018
Book
Cyber Security Cryptography and Machine Learning

Print ISBN: 978-3-319-94146-2

Electronic ISBN: 978-3-319-94147-9

Copyright Year: 2018

DOI
https://doi.org/10.1007/978-3-319-94147-9_2

Premium Partner

    Image Credits