Security Evaluation of Keccak

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  -  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-3842/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

3.2 Practical preimage 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 80 bits for collision challenges.

 Target  Authors  Reference  Update
 Keccak[r = 40, c = 160, nr = 1]  Joan Boyar and Rene Peralta  Acknowledgement by the Keccak Team  03/2013
 Keccak[r = 240, c = 160, nr = 3]  Yao Sun and Ting Li  Acknowledgement by the Keccak Team  08/2017
 Keccak[r = 640, c = 160, nr = 3]  The Cryptanalysis Taskforce Team  Acknowledgement by the Keccak Team  04/2016
 Keccak[r = 1440, c = 160, nr = 4]  The Cryptanalysis Taskforce Team  Acknowledgement by the Keccak Team  12/2016


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, pd and pe. 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 our attacks, the designers of Kravatte replaced the linear roll function in the expansion layer with a non-linear one and set nd and ne to 6.


5. Distinguishers

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


Reference

  1. Itai Dinur, Orr Dunkelman, Adi Shamir: Collision Attacks on Up to 5 Rounds of SHA-3 Using Generalized Internal Differentials. FSE 2013: 219-240
  2. 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
  3. 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
  4. Pawel Morawiecki, Josef Pieprzyk, Marian Srebrny: Rotational Cryptanalysis of Round-Reduced Keccak. FSE 2013: 241-262
  5. María Naya-Plasencia, Andrea Röck, Willi Meier: Practical Analysis of Reduced-Round Keccak. INDOCRYPT 2011: 236-254
  6. 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
  7. 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)
  8. 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
  9. 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
  10. Senyang Huang, Xiaoyun Wang, Guangwu Xu, Meiqin Wang, Jingyuan Zhao: Conditional Cube Attack on Reduced-Round Keccak Sponge Function. EUROCRYPT (2) 2017: 259-288
  11. Zheng Li, Wenquan Bi, Xiaoyang Dong, Xiaoyun Wang: Improved Conditional Cube Attacks on Keccak Keyed Modes with MILP Method. ASIACRYPT (1) 2017: 99-127
  12. 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)
  13. 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) 
  14. Rajendra Kumar, Mahesh Sreekumar Rajasree, Hoda AlKhzaimi: Cryptanalysis of 1-Round KECCAK. AFRICACRYPT 2018: 124-137
  15. Jérémy Jean, Ivica Nikolic: Internal Differential Boomerangs: Practical Analysis of the Round-Reduced Keccak-f Permutation. FSE 2015: 537-556
  16. 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
  17. Rajendra Kumar, Nikhil Mittal, Shashank Singh: Cryptanalysis of 2 round Keccak-384. Indocrypt 2018.




--- Last Update: Nov 2018 ---