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:
Secure Computation Based on Leaky Correlations: High Resilience Setting Read chapter Read first chapter

2017 | OriginalPaper | Chapter

Non-full Sbox Linearization: Applications to Collision Attacks on Round-Reduced Keccak

Authors : Ling Song, Guohong Liao, Jian Guo

Published in: Advances in Cryptology – CRYPTO 2017

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

The Keccak hash function is the winner of the SHA-3 competition and became the SHA-3 standard of NIST in 2015. In this paper, we focus on practical collision attacks against round-reduced Keccak hash function, and two main results are achieved: the first practical collision attacks against 5-round Keccak-224 and an instance of 6-round Keccak collision challenge. Both improve the number of practically attacked rounds by one. These results are obtained by carefully studying the algebraic properties of the nonlinear layer in the underlying permutation of Keccak and applying linearization to it. In particular, techniques for partially linearizing the output bits of the nonlinear layer are proposed, utilizing which attack complexities are reduced significantly from the previous best results.

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 Functional Graph Revisited: Updates on (Second) Preimage Attacks on Hash Combiners
next chapter Gaussian Sampling over the Integers: Efficient, Generic, Constant-Time
Appendix
Available only for authorised users
Footnotes
1
Our experiment shows \(2^{29.6}\) pairs of 5-round Keccak could be evaluated per second on NVIDIA GeForce GTX1070 graphic card.
 
2
Our experiment shows \(2^{28.87}\) pairs of 5-round Keccak could be evaluated per second on NVIDIA GeForce GTX970 graphic card.
 
Literature
1.
Aumasson, J.P., Meier, W.: Zero-Sum distinguishers for reduced keccak-f and for the core functions of Luffa and Hamsi. In: Rump Session of Cryptographic Hardware and Embedded Systems-CHES 2009 (2009)
2.
3.
4.
5.
Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: The Keccak SHA-3 Submission. Submission to NIST (Round 3) 6(7) (2011)
6.
7.
Canteaut, Anne (ed.): FSE 2012. LNCS, vol. 7549. Springer, Heidelberg (2012)MATH
8.
Cayrel, P.-L., Hoffmann, G., Schneider, M.: GPU implementation of the Keccak Hash function family. In: Kim, T., Adeli, H., Robles, R.J., Balitanas, M. (eds.) ISA 2011. CCIS, vol. 200, pp. 33–42. Springer, Heidelberg (2011). doi:10.​1007/​978-3-642-23141-4_​4 CrossRef
9.
Daemen, J., Assche, G.V.: Differential propagation analysis of keccak. In: Canteaut [7], pp. 422–441
10.
Dinur, I., Dunkelman, O., Shamir, A.: New attacks on keccak-224 and keccak-256. In: Canteaut [7], pp. 442–461
11.
Dinur, I., Dunkelman, O., Shamir, A.: Collision attacks on up to 5 rounds of SHA-3 using generalized internal differentials. In: Moriai, S. (ed.) FSE 2013. LNCS, vol. 8424, pp. 219–240. Springer, Heidelberg (2014). doi:10.​1007/​978-3-662-43933-3_​12
12.
13.
Dinur, I., Morawiecki, P., Pieprzyk, J., Srebrny, M., Straus, M.: Cube attacks and cube-attack-like cryptanalysis on the round-reduced keccak sponge function. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 733–761. Springer, Heidelberg (2015). doi:10.​1007/​978-3-662-46800-5_​28
14.
Duc, A., Guo, J., Peyrin, T., Wei, L.: Unaligned rebound attack: application to keccak. In: Canteaut [7], pp. 402–421
15.
Guo, J., Liu, M., Song, L.: Linear structures: applications to cryptanalysis of round-reduced Keccak. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016. LNCS, vol. 10031, pp. 249–274. Springer, Heidelberg (2016). doi:10.​1007/​978-3-662-53887-6_​9 CrossRef
16.
Jean, J., Nikolic, I.: Internal differential boomerangs: practical analysis of the round-reduced Keccak-f permutation. In: Leander, G. (ed.) FSE 2015. LNCS, vol. 9054, pp. 537–556. Springer, Heidelberg (2015)CrossRef
17.
Murthy, G.S.: Optimal loop unrolling for GPGPU programs. Ph.D. thesis, The Ohio State University (2009)
18.
Naya-Plasencia, M., Röck, A., Meier, W.: Practical analysis of reduced-round Keccak. In: Bernstein, D.J., Chatterjee, S. (eds.) INDOCRYPT 2011. LNCS, vol. 7107, pp. 236–254. Springer, Heidelberg (2011). doi:10.​1007/​978-3-642-25578-6_​18 CrossRef
19.
20.
Nvidia, C.: CUDA C Programming Guide. Nvidia Corporation 120(18) (2011)
21.
Qiao, K., Song, L., Liu, M., Guo, J.: New collision attacks on round-reduced Keccak. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10212, pp. 216–243. Springer, Cham (2017). doi:10.​1007/​978-3-319-56617-7_​8 CrossRef
22.
23.
24.
Volkov, V.: Better performance at lower occupancy. In: Proceedings of the GPU Technology Conference, GTC, vol. 10. San Jose, CA (2010)
Metadata
Title
Non-full Sbox Linearization: Applications to Collision Attacks on Round-Reduced Keccak
Authors
Ling Song
Guohong Liao
Jian Guo
Copyright Year
2017
Book
Advances in Cryptology – CRYPTO 2017

Print ISBN: 978-3-319-63714-3

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

Copyright Year: 2017

DOI
https://doi.org/10.1007/978-3-319-63715-0_15

Premium Partner

    Image Credits