nach oben

Erschienen in:

2017 | OriginalPaper | Buchkapitel

Functional Graph Revisited: Updates on (Second) Preimage Attacks on Hash Combiners

verfasst von : Zhenzhen Bao, Lei Wang, Jian Guo, Dawu Gu

Erschienen in: Advances in Cryptology – CRYPTO 2017

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

This paper studies functional-graph-based (second) preimage attacks against hash combiners. By exploiting more properties of functional graph, we find an improved preimage attack against the XOR combiner with a complexity of \(2^{5n/8}\), while the previous best-known complexity is \(2^{2n/3}\). Moreover, we find the first generic second-preimage attack on Zipper hash with an optimal complexity of \(2^{3n/5}\).

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel Time-Memory Tradeoff Attacks on the MTP Proof-of-Work Scheme

Nächstes Kapitel Non-full Sbox Linearization: Applications to Collision Attacks on Round-Reduced Keccak

Here we need to generalize the syntax of hash functions such that the initial value is also regarded as an input parameter.

In fact, Joux’s attacks require that only one hash function is iterative and narrow-pipe.

In fact, Dinur’s observation has been experimentally verified in [7], but the proof stays incomplete. More details are referred to [7, Appendix B].

Assuming compression functions are weak, second-peimage attacks have been published on Zipper hash [5, 19].

With very low probability \(L_1\) and \(L_2\) are not co-prime, and large t will result in repeated values.

Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.): ICALP 2008. LNCS, vol. 5126. Springer, Heidelberg (2008)

Allen, C., Dierks, T.: The TLS Protocol Version 1.0. RFC 2246, January 1999. https://rfc-editor.org/rfc/rfc2246.txt

Andreeva, E., Bouillaguet, C., Dunkelman, O., Kelsey, J.: Herding, second preimage and trojan message attacks beyond Merkle-Damgård. In: Jacobson, M.J., Rijmen, V., Safavi-Naini, R. (eds.) SAC 2009. LNCS, vol. 5867, pp. 393–414. Springer, Heidelberg (2009). doi:10.1007/978-3-642-05445-7_25 CrossRef

Brassard, G. (ed.): CRYPTO 1989. LNCS, vol. 435. Springer, New York (1990)MATH

Chen, S., Jin, C.: A second preimage attack on Zipper hash. Secur. Commun. Netw. 8(16), 2860–2866 (2015)CrossRef

Damgård, I.: A design principle for hash functions. In: Brassard [4], pp. 416–427

Dinur, I.: New attacks on the concatenation and XOR hash combiners. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016, Part I. LNCS, vol. 9665, pp. 484–508. Springer, Heidelberg (2016). doi:10.1007/978-3-662-49890-3_19 CrossRef

Dinur, I., Leurent, G.: Improved generic attacks against hash-based MACs and HAIFA. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014, Part I. LNCS, vol. 8616, pp. 149–168. Springer, Heidelberg (2014). doi:10.1007/978-3-662-44371-2_9 CrossRef

Fischlin, M., Lehmann, A.: Security-amplifying combiners for collision-resistant hash functions. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 224–243. Springer, Heidelberg (2007). doi:10.1007/978-3-540-74143-5_13 CrossRef

10.

Fischlin, M., Lehmann, A.: Multi-property preserving combiners for hash functions. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 375–392. Springer, Heidelberg (2008). doi:10.1007/978-3-540-78524-8_21 CrossRef

11.

Fischlin, M., Lehmann, A., Pietrzak, K.: Robust multi-property combiners for hash functions revisited. In: Aceto et al., [1], pp. 655–666

12.

Fischlin, M., Lehmann, A., Pietrzak, K.: Robust multi-property combiners for hash functions. J. Cryptol. 27(3), 397–428 (2014)MathSciNetCrossRefMATH

13.

Flajolet, P., Odlyzko, A.M.: Random mapping statistics. In: Quisquater, J.-J., Vandewalle, J. (eds.) EUROCRYPT 1989. LNCS, vol. 434, pp. 329–354. Springer, Heidelberg (1990). doi:10.1007/3-540-46885-4_34 CrossRef

14.

Freier, A.O., Karlton, P., Kocher, P.C.: The Secure Sockets Layer (SSL) Protocol Version 3.0. RFC 6101, August 2011. https://rfc-editor.org/rfc/rfc6101.txt

15.

Guo, J., Peyrin, T., Sasaki, Y., Wang, L.: Updates on generic attacks against HMAC and NMAC. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014, Part I. LNCS, vol. 8616, pp. 131–148. Springer, Heidelberg (2014). doi:10.1007/978-3-662-44371-2_8 CrossRef

16.

Hellman, M.E.: A cryptanalytic time-memory trade-off. IEEE Trans. Inf. Theory 26(4), 401–406 (1980)MathSciNetCrossRefMATH

17.

Hoch, J.J., Shamir, A.: Breaking the ICE – finding multicollisions in iterated concatenated and expanded (ICE) hash functions. In: Robshaw, M. (ed.) FSE 2006. LNCS, vol. 4047, pp. 179–194. Springer, Heidelberg (2006). doi:10.1007/11799313_12 CrossRef

18.

Hoch, J.J., Shamir, A.: On the strength of the concatenated hash combiner when all the hash functions are weak. In: Aceto et al. [1], pp. 616–630

19.

Jha, A., Nandi, M.: Some Cryptanalytic Results on Zipper Hash and Concatenated Hash. Cryptology ePrint Archive, Report 2015/973 (2015). http://eprint.iacr.org/2015/973

20.

Joux, A.: Multicollisions in iterated hash functions. application to cascaded constructions. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 306–316. Springer, Heidelberg (2004). doi:10.1007/978-3-540-28628-8_19 CrossRef

21.

Kelsey, J., Schneier, B.: Second preimages on n-bit hash functions for much less than 2ⁿ work. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 474–490. Springer, Heidelberg (2005). doi:10.1007/11426639_28 CrossRef

22.

Lehmann, A.: On the security of hash function combiners. Ph.D. thesis, Darmstadt University of Technology (2010)

23.

Leurent, G., Peyrin, T., Wang, L.: New generic attacks against hash-based MACs. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013, Part II. LNCS, vol. 8270, pp. 1–20. Springer, Heidelberg (2013). doi:10.1007/978-3-642-42045-0_1 CrossRef

24.

Leurent, G., Wang, L.: The sum can be weaker than each part. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015, Part I. LNCS, vol. 9056, pp. 345–367. Springer, Heidelberg (2015). doi:10.1007/978-3-662-46800-5_14

25.

Liskov, M.: Constructing an ideal hash function from weak ideal compression functions. In: Biham, E., Youssef, A.M. (eds.) SAC 2006. LNCS, vol. 4356, pp. 358–375. Springer, Heidelberg (2007). doi:10.1007/978-3-540-74462-7_25 CrossRef

26.

Mendel, F., Rechberger, C., Schläffer, M.: MD5 is weaker than weak: attacks on concatenated combiners. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 144–161. Springer, Heidelberg (2009). doi:10.1007/978-3-642-10366-7_9 CrossRef

27.

Merkle, R.C.: One way hash functions and DES. In: Brassard [4], pp. 428–446

28.

Nandi, M., Stinson, D.R.: Multicollision attacks on some generalized sequential hash functions. IEEE Trans. Inf. Theory 53(2), 759–767 (2007)MathSciNetCrossRefMATH

29.

van Oorschot, P.C., Wiener, M.J.: Parallel collision search with cryptanalytic applications. J. Cryptol. 12(1), 1–28 (1999)MathSciNetCrossRefMATH

30.

Perrin, L., Khovratovich, D.: Collision spectrum, entropy loss, T-sponges, and cryptanalysis of GLUON-64. In: Cid, C., Rechberger, C. (eds.) FSE 2014. LNCS, vol. 8540, pp. 82–103. Springer, Heidelberg (2015). doi:10.1007/978-3-662-46706-0_5

31.

Peyrin, T., Sasaki, Y., Wang, L.: Generic related-key attacks for HMAC. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 580–597. Springer, Heidelberg (2012). doi:10.1007/978-3-642-34961-4_35 CrossRef

32.

Peyrin, T., Wang, L.: Generic universal forgery attack on iterative hash-based MACs. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 147–164. Springer, Heidelberg (2014). doi:10.1007/978-3-642-55220-5_9 CrossRef

Titel: Functional Graph Revisited: Updates on (Second) Preimage Attacks on Hash Combiners
verfasst von: Zhenzhen Bao
Lei Wang
Jian Guo
Dawu Gu
Verlag: Springer International Publishing
Buch: Advances in Cryptology – CRYPTO 2017
Print ISBN: 978-3-319-63714-3

Electronic ISBN: 978-3-319-63715-0

Copyright-Jahr: 2017
DOI: https://doi.org/10.1007/978-3-319-63715-0_14

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"