Practical collision attacks against round-reduced SHA-3
The Keccak hash function is the winner of the SHA-3 competition (2008–2012) and became the SHA-3 standard of NIST in 2015. In this paper, we focus on practical collision attacks against round-reduced SHA-3 and some Keccak variants. Following the framework developed by Dinur et al. at FSE 2012 where...
Saved in:
Main Authors: | , , , , , |
---|---|
Other Authors: | |
Format: | Article |
Language: | English |
Published: |
2019
|
Subjects: | |
Online Access: | https://hdl.handle.net/10356/100424 http://hdl.handle.net/10220/49481 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Nanyang Technological University |
Language: | English |
id |
sg-ntu-dr.10356-100424 |
---|---|
record_format |
dspace |
spelling |
sg-ntu-dr.10356-1004242023-02-28T19:22:01Z Practical collision attacks against round-reduced SHA-3 Guo, Jian Liao, Guohong Liu, Guozhen Liu, Meicheng Qiao, Kexin Song, Ling School of Physical and Mathematical Sciences Strategic Centre for Research in Privacy-Preserving Technologies and Systems Cryptanalysis Hash Function Science::Mathematics::Discrete mathematics::Cryptography The Keccak hash function is the winner of the SHA-3 competition (2008–2012) and became the SHA-3 standard of NIST in 2015. In this paper, we focus on practical collision attacks against round-reduced SHA-3 and some Keccak variants. Following the framework developed by Dinur et al. at FSE 2012 where 4-round collisions were found by combining 3-round differential trails and 1-round connectors, we extend the connectors to up to three rounds and hence achieve collision attacks for up to 6 rounds. The extension is possible thanks to the large degree of freedom of the wide internal state. By linearizing S-boxes of the first round, the problem of finding solutions of 2-round connectors is converted to that of solving a system of linear equations. When linearization is applied to the first two rounds, 3-round connectors become possible. However, due to the quick reduction in the degree of freedom caused by linearization, the connector succeeds only when the 3-round differential trails satisfy some additional conditions. We develop dedicated strategies for searching differential trails and find that such special differential trails indeed exist. To summarize, we obtain the first real collisions on six instances, including three round-reduced instances of SHA-3, namely 5-round SHAKE128, SHA3-224 and SHA3-256, and three instances of Keccak contest, namely Keccak[1440, 160, 5, 160], Keccak[640, 160, 5, 160] and Keccak[1440, 160, 6, 160], improving the number of practically attacked rounds by two. It is remarked that the work here is still far from threatening the security of the full 24-round SHA-3 family. Ministry of Education (MOE) National Research Foundation (NRF) Accepted version This research is supported by the National Research Foundation, Prime Minis- ter’s Office, Singapore under its Strategic Capability Research Centres Funding Initiative, NTU Research Grant M4080456 and M4082123, and Ministry of Edu- cation Singapore Grant M4012049. Guohong Liao is partially supported by the National Natural Science Foundation of China (Grants No. 61572028). Guozhen Liu is partially supported by the State Scholarship Fund (No. 201706230141) organized by China Scholarship Council. Meicheng Liu is partially supported by the National Natural Science Foundation of China (Grants No. 61672516). Kexin Qiao and Ling Song are partially supported by the National Natural Science Foundation of China (Grants No. 61802399, 61802400, 61732021 and 61772519), the Youth Innovation Promotion Association CAS, and Chinese Ma- jor Program of National Cryptography Development Foundation (Grant No. MMJJ20180102). 2019-07-29T06:10:26Z 2019-12-06T20:22:18Z 2019-07-29T06:10:26Z 2019-12-06T20:22:18Z 2019 Journal Article Guo, J., Liao, G., Liu, G., Liu, M., Qiao, K., & Song, L. Practical collision attacks against round-reduced SHA-3. Journal of Cryptology, 33, 228-270. doi:10.1007/s00145-019-09313-3 0933-2790 https://hdl.handle.net/10356/100424 http://hdl.handle.net/10220/49481 10.1007/s00145-019-09313-3 33 228 270 en Journal of Cryptology Journal of Cryptology © 2019 International Association for Cryptologic Research. All rights reserved. This paper was published in Journal of Cryptology and is made available with permission of International Association for Cryptologic Research. application/pdf |
institution |
Nanyang Technological University |
building |
NTU Library |
continent |
Asia |
country |
Singapore Singapore |
content_provider |
NTU Library |
collection |
DR-NTU |
language |
English |
topic |
Cryptanalysis Hash Function Science::Mathematics::Discrete mathematics::Cryptography |
spellingShingle |
Cryptanalysis Hash Function Science::Mathematics::Discrete mathematics::Cryptography Guo, Jian Liao, Guohong Liu, Guozhen Liu, Meicheng Qiao, Kexin Song, Ling Practical collision attacks against round-reduced SHA-3 |
description |
The Keccak hash function is the winner of the SHA-3 competition (2008–2012) and became the SHA-3 standard of NIST in 2015. In this paper, we focus on practical collision attacks against round-reduced SHA-3 and some Keccak variants. Following the framework developed by Dinur et al. at FSE 2012 where 4-round collisions were found by combining 3-round differential trails and 1-round connectors, we extend the connectors to up to three rounds and hence achieve collision attacks for up to 6 rounds. The extension is possible thanks to the large degree of freedom of the wide internal state. By linearizing S-boxes of the first round, the problem of finding solutions of 2-round connectors is converted to that of solving a system of linear equations. When linearization is applied to the first two rounds, 3-round connectors become possible. However, due to the quick reduction in the degree of freedom caused by linearization, the connector succeeds only when the 3-round differential trails satisfy some additional conditions. We develop dedicated strategies for searching differential trails and find that such special differential trails indeed exist. To summarize, we obtain the first real collisions on six instances, including three round-reduced instances of SHA-3, namely 5-round SHAKE128, SHA3-224 and SHA3-256, and three instances of Keccak contest, namely Keccak[1440, 160, 5, 160], Keccak[640, 160, 5, 160] and Keccak[1440, 160, 6, 160], improving the number of practically attacked rounds by two. It is remarked that the work here is still far from threatening the security of the full 24-round SHA-3 family. |
author2 |
School of Physical and Mathematical Sciences |
author_facet |
School of Physical and Mathematical Sciences Guo, Jian Liao, Guohong Liu, Guozhen Liu, Meicheng Qiao, Kexin Song, Ling |
format |
Article |
author |
Guo, Jian Liao, Guohong Liu, Guozhen Liu, Meicheng Qiao, Kexin Song, Ling |
author_sort |
Guo, Jian |
title |
Practical collision attacks against round-reduced SHA-3 |
title_short |
Practical collision attacks against round-reduced SHA-3 |
title_full |
Practical collision attacks against round-reduced SHA-3 |
title_fullStr |
Practical collision attacks against round-reduced SHA-3 |
title_full_unstemmed |
Practical collision attacks against round-reduced SHA-3 |
title_sort |
practical collision attacks against round-reduced sha-3 |
publishDate |
2019 |
url |
https://hdl.handle.net/10356/100424 http://hdl.handle.net/10220/49481 |
_version_ |
1759853516388564992 |