1. Introduction
The Keccak hash function family was designed by Bertoni et al. and standardized as SHA-3 in 2015 by the National Institute of Standards and Technology of the U.S. (NIST). In this page, major cryptanalysis results against round-reduced Keccak/SHA-3 are listed, including collision attacks, preimage attacks, key recovery attacks on keyed schemes based on the Keccak permutation Keccak-p, as well as distinguishers against Keccak-p.
2. Collision Attacks
2.1 Collision attacks on Keccak/SHA-3
The standard SHA-3 and the original Keccak design differ only in the way of message padding, and hence share almost all security analysis. The internal state of Keccak or SHA-3 is of 1600 bits.
Target |
Rounds |
Complexity |
Authors |
Reference |
Update |
Keccak-512 |
3/24 |
Practical |
Itai Dinur, Orr Dunkelman, Adi Shamir |
[1] |
2013 |
Keccak-384 |
3/24 |
Practical |
Itai Dinur, Orr Dunkelman, Adi Shamir |
[1] |
2013 |
Keccak-384 |
4/24 |
2147 |
Itai Dinur, Orr Dunkelman, Adi Shamir |
[1] |
2013 |
Keccak-256/SHA3-256 |
5/24 |
Practical |
The Cryptanalysis Taskforce Team |
[18] |
07/2018 |
Keccak-224/SHA3-224 |
5/24 |
Practical |
The Cryptanalysis Taskforce Team |
[2] |
01/2017 |
SHAKE128 |
5/24 |
Practical |
The Cryptanalysis Taskforce Team |
[3] |
07/2016 |
2.2 Practical collision attacks on instances of the Keccak Challenge
To promote cryptanalysis against Keccak, the Keccak team proposed variants with lower security levels in the Keccak Challenge, where the size of the internal state varies from 200 up to 1600 bits, the capacity is of 160 bits and the output is truncated to 160 bits for collision challenges.
Target |
Authors |
Reference |
Update |
Keccak[r = 40, c = 160, nr = 1] |
Roman Walch and Maria Eichlseder |
Acknowledgement by the Keccak Team |
09/2017 |
Keccak[r = 240, c = 160, nr = 4] |
Stefan Kölbl, Florian Mendel, Martin Schläffer and Tomislav Nad |
Acknowledgement by the Keccak Team |
06/2013 |
Keccak[r = 640, c = 160, nr = 5] |
The Cryptanalysis Taskforce Team |
Acknowledgement by the Keccak Team |
07/2016 |
Keccak[r = 1440, c = 160, nr = 6] |
The Cryptanalysis Taskforce Team |
Acknowledgement by the Keccak Team |
02/2017 |
3. Preimage Attacks
3.1 Preimage attacks on Keccak/SHA-3
Target |
Rounds |
Complexity |
Authors |
Reference |
Update |
SHA3-384/512 |
4/24 |
2378/2506 |
Pawel Morawiecki, Josef Pieprzyk, Marian Srebrny |
[4] |
2013 |
SHA3-224/256 |
4/24 |
2213/2251 |
The Cryptanalysis Taskforce Team |
[6] |
2016 |
SHAKE128 |
4/24 |
2106 |
The Cryptanalysis Taskforce Team |
[6] |
2016 |
SHA3-384/512 |
3/24 |
2322/2482 |
The Cryptanalysis Taskforce Team |
[6] |
2016 |
SHA3-256/SHAKE256 |
3/24 |
2151/2153 |
Ting Li, Yao Sun, Maodong Liao, Dingkang Wang |
[7] |
2017 |
SHA3-224 |
3/24 |
297 |
The Cryptanalysis Taskforce Team |
[6] |
2013 |
SHAKE128 |
3/24 |
Practical |
The Cryptanalysis Taskforce Team |
[6] |
2016 |
SHA3-384/512 |
2/24 |
2129/2384 |
The Cryptanalysis Taskforce Team |
[6] |
2016 |
SHA3-224/256 |
2/24 |
Practical |
María Naya-Plasencia, Andrea Röck, Willi Meier |
[5] |
2011 |
Keccak-384 | 2/24 | 289 | Rajendra Kumar, Nikhil Mittal, Shashank Singh | [17] | 2018 |
Keccak-384/512 |
1/24 |
Practical |
Rajendra Kumar, Mahesh Sreekumar Rajasree, Hoda AlKhzaimi |
[14] |
2017 |
To promote cryptanalysis against Keccak, the Keccak team proposed variants with lower security levels in the Keccak Challenge, where the size of the internal state varies from 200 up to 1600 bits, the capacity is of 160 bits and the output is truncated to 80 bits for collision challenges.
4. Key Recovery Attacks
4.1 MAC
- KMAC128/256, SHA-3 based MAC recommended by NIST, where the key is processed as an independent block before absorbing message blocks
- Keccak-MAC, taking K||M as input
Target |
|K| |
Capacity |
Rounds |
Time(Data) |
Memory |
Authors |
Reference |
Update |
KMAC128 |
128 |
256 |
7/24 |
276 |
- |
The Cryptanalysis Taskforce Team |
[9] |
2018 |
KMAC256 |
256 |
512 |
9/24 |
2147 |
- |
The Cryptanalysis Taskforce Team |
[9] |
2018 |
Keccak-MAC |
128 |
256/512 |
7/24 |
272 |
- |
Senyang Huang et al. |
[10] |
2017 |
Keccak-MAC |
128 |
768 |
7/24 |
275 |
- |
Zheng Li et al. |
[11] |
2017 |
Keccak-MAC |
128 |
1024 |
7/24 |
2111 |
246 |
The Cryptanalysis Taskforce Team |
[8] |
2018 |
4.2 Authenticated Encryptions
Keyak and Ketje are two Keccak-p based authenticatedencryption schemes.
Target |
|K| |
Rounds |
Time(Data) |
Memory |
NR |
Authors |
Reference |
Lake Keyak |
128 |
8/12 |
271.01 |
- |
Yes |
The Cryptanalysis Taskforce Team |
[9] |
Lake Keyak |
256 |
9/14 |
2137.05 |
- |
Yes |
The Cryptanalysis Taskforce Team |
[9] |
Rive Keyak |
128 |
8/12 |
277 |
- |
Yes |
The Cryptanalysis Taskforce Team |
[9] |
FKD[1600] |
128 |
9/- |
290 |
- |
No |
The Cryptanalysis Taskforce Team |
[9] |
Ketje Major |
128 |
7/13 |
271.24 |
- |
Yes |
The Cryptanalysis Taskforce Team |
[9] |
Ketje Minor |
128 |
7/13 |
273.03 |
- |
Yes |
The Cryptanalysis Taskforce Team |
[9] |
Ketje Sr v1 |
128 |
7/13 |
291 |
- |
Yes |
The Cryptanalysis Taskforce Team |
[9] |
Kteje Sr v2 |
128 |
7/13 |
299 |
233 |
Yes |
The Cryptanalysis Taskforce Team |
[8] |
Ketje Jr v1 |
96 |
5/13 |
236.86 |
218 |
Yes |
The Cryptanalysis Taskforce Team |
[8] |
Ketje Jr v2 |
96 |
5/13 |
234.91 |
215 |
Yes |
The Cryptanalysis Taskforce Team |
[8] |
Xoodoo in Ketje style |
128 |
6/- |
289 |
255 |
Yes |
The Cryptanalysis Taskforce Team |
[8] |
Note: NR means nonce-respected
4.3 Pseudorandom Function
Farfalle is a construction for pseudorandom functions (PRF) with variable input and output length, and Kravatte is an instantiation of it by taking Keccak-p as the underlying permutations.
Farfalle consists of three steps:
- Mask derivation
- Compression layer
- Expansion layer
We exploit the properties of Farfalle and in the attacks on Kravatte only the number of rounds in the expansion layer matters. There are two permutations in the expansion layer, p d and p e. Let the number of rounds in pd and pe be nd, ne respectively. In the ePrint/ECC version of Kravatte, (nd, ne) = (4, 4)/(6,6).
(nd, ne) |
Type |
Data |
Memory |
Time |
Authors |
Reference |
(4, 4) |
Higher Order |
274.7 |
262.3 |
2112.2 |
Chaigneau et al. |
[13] |
(*, 4) |
MITM |
227.8 |
276.9 |
2115.3 |
Chaigneau et al. |
[13] |
(*, 4) |
Linear Recurrence |
251.2 |
251.2 |
265.1 |
Chaigneau et al. |
[13] |
(*, 4) |
Linear Recurrence |
229.9 |
262.3 |
287.0 |
Chaigneau et al. |
[13] |
(*, 6) |
Linear Recurrence |
288.4 |
288.4 |
2134.6 |
Chaigneau et al. |
[13] |
Due to this attack, the designers of Kravatte replaced the linear roll function in the expansion layer with a non-linear one and increased nd and ne from 4 to 6.
5.1 Differential Distinguishers
The differential distinguishers are mainly based on the differential properties, including the rebound-like distinguisher connecting two short differential paths under the limited birthday setting [16], and internal differential distinguisher [15].
Target |
Rounds |
Complexity |
Authors |
Reference |
Update |
Keccak-f[1600] |
6/24 |
25 |
Jérémy Jean, Ivica Nikolic |
[15] |
2015 |
Keccak-f[1600] |
7/24 |
213 |
Jérémy Jean, Ivica Nikolic |
[15] |
2015 |
Keccak-f[1600] |
8/24 |
218 |
Jérémy Jean, Ivica Nikolic |
[15] |
2015 |
Keccak-f[100] |
6/24 |
219 |
Duc, Guo, Peyrin, Wei |
[16] |
2011 |
Keccak-f[200] |
7/24 |
246 |
Duc, Guo, Peyrin, Wei |
[16] |
2011 |
Keccak-f[400] |
7/24 |
284 |
Duc, Guo, Peyrin, Wei |
[16] |
2011 |
Keccak-f[800] |
8/24 |
2109 |
Duc, Guo, Peyrin, Wei |
[16] |
2011 |
Keccak-f[1600] |
8/24 |
2491.5 |
Duc, Guo, Peyrin, Wei |
[16] |
2011 |
5.2 Algebraic Distinguishers
The algebraic distinguishers mainly take advantage of the low algebraic degree of the Keccak Chi operation (the only nonlinear operation) -- 2 and 3 in the forward and backward directions [6]. They take an inside-out approach, which gains 2 or 3 rounds from the middle at the starting point, by the technique of linear structures.
Target |
Rounds |
Complexity |
Authors |
Reference |
Update |
Keccak-f |
7/24 |
29 |
The Cryptanalysis Taskforce Team |
[6] |
2016 |
Keccak-f |
8/24 |
210 |
The Cryptanalysis Taskforce Team |
[6] |
2016 |
Keccak-f |
9/24 |
217 |
The Cryptanalysis Taskforce Team |
[6] |
2016 |
Keccak-f |
10/24 |
228 |
The Cryptanalysis Taskforce Team |
[6] |
2016 |
Keccak-f |
11/24 |
233 |
The Cryptanalysis Taskforce Team |
[6] |
2016 |
Keccak-f |
12/24 |
265 |
The Cryptanalysis Taskforce Team |
[6] |
2016 |
Keccak-f |
13/24 |
282 |
The Cryptanalysis Taskforce Team |
[6] |
2016 |
Keccak-f |
14/24 |
2129 |
The Cryptanalysis Taskforce Team |
[6] |
2016 |
Keccak-f |
15/24 |
2257 |
The Cryptanalysis Taskforce Team |
[6] |
2016 |
6. Differential Propagation AnalysisThe lower bounds on differential propagation weight of Keccak-f for 2/3-round differential trails are 8 and 32 [21]. For the permutation Keccak-f[1600], 3-round trails of propagation weight no greater than 53 are exhaustively searched giving better lower bounds for 4/5/6-round and full rounds trails [19]. Lower bounds on differential trails of other Keccak-f permutations are summarized in [20].Target | 3R | 4R | 5R | 6R | Full rounds | Authors | Reference | Update | Keccak-f[1600] | 53 | 56 | 58 | 108 | 432(24R) | The Cryptanalysis Taskforce Team | [19] | 2019 | Keccak-f[800] | 32 | 48 | 50 | 92 | 292(22R) | Silvia Mella, Joan Deamen, Gilles Van Assche | [20] | 2017 | Keccak-f[400] | 24 | 48 | 50 | 92 | 280(20R) | Silvia Mella, Joan Deamen, Gilles Van Assche | [20] | 2017 | Keccak-f[200] | 20 | 46 | 50 | 92 | 276(18R) | Silvia Mella, Joan Deamen, Gilles Van Assche | [20] | 2017 |
Reference
- Itai Dinur, Orr Dunkelman, Adi Shamir: Collision Attacks on Up to 5 Rounds of SHA-3 Using Generalized Internal Differentials. FSE 2013: 219-240
- Kexin Qiao, Ling Song, Meicheng Liu, Jian Guo: New Collision Attacks on Round-Reduced Keccak. EUROCRYPT (3) 2017: 216-243. Full version available: https://eprint.iacr.org/2017/128
- Ling Song, Guohong Liao, Jian Guo: Non-full Sbox Linearization: Applications to Collision Attacks on Round-Reduced Keccak. CRYPTO (2) 2017: 428-451. Full version available: https://eprint.iacr.org/2017/529
- Pawel Morawiecki, Josef Pieprzyk, Marian Srebrny: Rotational Cryptanalysis of Round-Reduced Keccak. FSE 2013: 241-262
- María Naya-Plasencia, Andrea Röck, Willi Meier: Practical Analysis of Reduced-Round Keccak. INDOCRYPT 2011: 236-254
- Jian Guo, Meicheng Liu, Ling Song: Linear Structures: Applications to Cryptanalysis of Round-Reduced Keccak. ASIACRYPT (1) 2016: 249-274. Full version available: https://eprint.iacr.org/2016/878
- Ting Li, Yao Sun, Maodong Liao, Dingkang Wang: Preimage Attacks on the Round-reduced Keccak with Cross-linear Structures. IACR Trans. Symmetric Cryptol. 2017(4): 39-57 (2017)
- Ling Song, Jian Guo: Cube-Attack-Like Cryptanalysis of Round-Reduced Keccak Using MILP. IACR Trans. Symmetric Cryptol. 2018(3): 182-214. Full version available: https://eprint.iacr.org/2018/810
- Ling Song, Jian Guo, Danping Shi, San Ling: New MILP Modeling: Improved Conditional Cube Attacks on Keccak-based Constructions. ASIACRYPT 2018. Full version available: https://eprint.iacr.org/2017/1030
- Senyang Huang, Xiaoyun Wang, Guangwu Xu, Meiqin Wang, Jingyuan Zhao: Conditional Cube Attack on Reduced-Round Keccak Sponge Function. EUROCRYPT (2) 2017: 259-288
- Zheng Li, Wenquan Bi, Xiaoyang Dong, Xiaoyun Wang: Improved Conditional Cube Attacks on Keccak Keyed Modes with MILP Method. ASIACRYPT (1) 2017: 99-127
- Xiaoyang Dong, Zheng Li, Xiaoyun Wang, Ling Qin: Cube-like Attack on Round-Reduced Initialization of Ketje Sr. IACR Trans. Symmetric Cryptol. 2017(1): 259-280 (2017)
- Colin Chaigneau, Thomas Fuhr, Henri Gilbert, Jian Guo, Jérémy Jean, Jean-René Reinhard, Ling Song: Key-Recovery Attacks on Full Kravatte. IACR Trans. Symmetric Cryptol. 2018(1): 5-28 (2018)
- Rajendra Kumar, Mahesh Sreekumar Rajasree, Hoda AlKhzaimi: Cryptanalysis of 1-Round KECCAK. AFRICACRYPT 2018: 124-137
- Jérémy Jean, Ivica Nikolic: Internal Differential Boomerangs: Practical Analysis of the Round-Reduced Keccak-f Permutation. FSE 2015: 537-556
- Alexandre Duc, Jian Guo, Thomas Peyrin, Lei Wei: Unaligned Rebound Attack: Application to Keccak. FSE 2012: 402-421. Full version available: https://eprint.iacr.org/2011/420
- Rajendra Kumar, Nikhil Mittal, Shashank Singh: Cryptanalysis of 2 round Keccak-384. Indocrypt 2018.
- Jian Guo, Guohong Liao, Guozhen Liu, Meicheng Liu, Kexin Qiao, Ling Song: Practical Collision Attacks against Round-Reduced SHA-3, Journal of Cryptology 2019.
- Guozhen Liu, Weidong Qiu, Yi Tu: New Techniques for Searching Differential Trails in Keccak. IACR Trans. Symmetric Cryptol. 2019(4): 407-437 (2019)
- Silvia Mella, Joan Deamen, Gilles Van Assche: New techniques for trail bounds and application to differential trails in Keccak. IACR Trains. Symmetric Cryptol. 2017(1): 329-357 (2017)
- Joan Deamen, Gilles Van Assche: Differential Propagation Analysis of Keccak. FSE 2012: 422-441
--- Last Update: October 2020 ---
|
|