Cryptanalysis Taskforce

Security Evaluation of SHA-3

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.

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.

3. Preimage Attacks

3.1 Preimage attacks on Keccak/SHA-3

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.

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

4.2 Authenticated Encryptions

Keyak and Ketje are two Keccak-p based authenticatedencryption schemes.

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).

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. 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].

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.

6. Differential Propagation Analysis

The 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].

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.

    18. Jian Guo, Guohong Liao, Guozhen Liu, Meicheng Liu, Kexin Qiao, Ling Song: Practical Collision Attacks against Round-Reduced SHA-3, Journal of Cryptology 2019.

    19. Guozhen Liu, Weidong Qiu, Yi Tu: New Techniques for Searching Differential Trails in Keccak. IACR Trans. Symmetric Cryptol. 2019(4): 407-437 (2019)

    20. 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)

    21. Joan Deamen, Gilles Van Assche: Differential Propagation Analysis of Keccak. FSE 2012: 422-441