TurboSHAKE

Abstract

In a recent presentation, we promoted the use of 12-round instances of Keccak, collectively called “TurboSHAKE”, in post-quantum cryptographic schemes, but without defining them further. The goal of this note is to fill this gap: The definition of the TurboSHAKE family simply consists in exposing and generalizing the primitive already defined inside KangarooTwelve.

Keywords: symmetric cryptography, hashing, Keccak

Introduction

Cryptography involves careful trade-offs between performance and security. In symmetric cryptography, an important such trade-off is the choice of the number of rounds, which on the one hand is proportional to the amount of time taken to evaluate a primitive and on the other needs to be high enough to provide safety margin against possible progresses in attacks. Ideally, this choice is driven by cryptanalysis on round-reduced versions, but cryptanalysis requires hard work by cryptographic experts. Fortunately, Keccak has received quite a large amount of cryptanalysis since its publication; in fact, Keccak has seen more scientific publications on cryptanalysis than any other unbroken hash function to this date. In the light of these publications, we feel we can confidently propose to halve the number of rounds without compromising security.

It seems clear that a round-reduced version of the Keccak sponge function can be useful in many cases. We proposed a few years ago an extendable output function (XOF), called KangarooTwelve (or K12 for short), with the explicit goal of being able to build upon existing cryptanalysis, instead of creating a new design that would require fresh one [BDH+18]. More recently, for post-quantum cryptography, the NIST selected a number of public-key schemes that they will standardize and that use instances of Keccak internally [NIST22]. In some cases, the time spent by these schemes is dominated by the evaluation of the sponge function, and so logically we brought up the idea of reducing the number of rounds for this use-case [BDPV22]. Despite NIST’s decision to stick to the nominal number of rounds, we believe the interest remains in general.

We observe that there are already quite a large number of named instances of Keccak—besides the four SHA-3 hash functions and the two SHAKE XOFs in FIPS 202, the NIST SP 800-185 standard defines a few more [60, 61]. We therefore wish to keep the number of new definitions to a minimum. In fact, we are not defining anything really new: We are making the primitive inside K12 available and more broadly usable.

1. Specifications of TurboSHAKE

TurboSHAKE is a family of eXtendable Output Functions (XOF) parameterized by their capacity c, where the capacity directly relates to the claimed security level as detailed in Section 2. We restrict the capacity c to multiples of 8 not greater than 512.

A given instance, denoted \text{TurboSHAKE}[c], takes as input:

• a message M, a byte string of variable length, and
• a domain separation parameter D, a byte with a value in the range [\text{0x01}, \ldots, \text{0x7F}] in hexadecimal.

As a XOF, the output of \text{TurboSHAKE}[c] is unlimited, and the user can request as many output bits as desired. It can be used for traditional hashing simply by generating outputs of the desired digest size.

TurboSHAKE produces unrelated outputs on different tuples (c, M, D). For a given capacity, the value D is meant to provide domain separation, that is, for two different values D_1 \neq D_2, \text{TurboSHAKE}[c](\cdot, D_1) and \text{TurboSHAKE}[c](\cdot, D_2) act as two independent functions of M. We believe the range of D to be sufficient to cover all use cases.

Users that do not require multiple instances can take as default D = \text{0x1F}.

Named instances

In addition, we define:

• TurboSHAKE128 as \text{TurboSHAKE}[c = 256], and
• TurboSHAKE256 as \text{TurboSHAKE}[c = 512].

Procedure

To compute \text{TurboSHAKE}[c](M, D), proceed as follows. Let R = 200 - c/8 be the rate in bytes and f the \text{Keccak-}p[1600, n_r = 12] permutation [NIST15].

1. Input preparation
   1. (a) Append to M the byte D, followed by the minimum number of bytes 0x00 (possibly none) until M' = M \| D \| \text{0x00}^* has a length that is a multiple of R bytes.
   2. (b) Bitwise add (XOR) the byte 0x80 into the last byte of M'.
   3. (c) Cut M' into m blocks of R bytes each, i.e., M' = M_1 \| \ldots \| M_m.
2. Absorbing phase
   1. (a) Let S = \text{0x00}^{200}.
   2. (b) For each block M_i for i = 1 to m:
      S \leftarrow f\!\left(S \oplus (M_i \| \text{0x00}^{200-R})\right)
3. Squeezing phase
   1. (a) Repeat as long as necessary:
      1. i. Output the first R bytes of S.
      2. ii. Let S \leftarrow f(S).
   2. (b) Truncate the output if longer than needed.

2. Security Claim

We make a flat sponge claim [BDPV11a] with c bits of claimed capacity in Claim 1. Informally, it means that TurboSHAKE shall offer the same security strength as a random oracle whenever that offers a strength below c/2 bits and a strength of c/2 bits in all other cases.

The flat sponge claim covers all attacks against \text{TurboSHAKE}[c] up to a given security strength of c/2 bits. Informally, saying that a cryptographic function has a security strength of s bits means that no attacks exist with complexity N and success probability p such that N/p < 2^s [MW18]. For more details on the interpretation of the claim, we refer to [BDH+18, Section 4.1].

3. Rationale

In this section, we exhibit the equivalence with Keccak reduced to 12 rounds, motivate our security claim and clarify its use in KangarooTwelve.

Equivalence

Consider the sponge function on top of the \text{Keccak-}p[1600, n_r = 12] permutation, with multi-rate padding \text{pad}10^*1, capacity c and rate r = 1600 - c, as defined in the FIPS 202 standard [NIST15], and let us call it \mathcal{TS}_c for short, i.e.,

In comparison, note that the standard Keccak is defined the same way, except for the number of rounds, i.e.,

Then, \text{TurboSHAKE}[c](M, D) is equivalent to \mathcal{TS}_c(M \| \text{unpad}(D)), where

• D and each byte of M is interpreted as a string of 8 bits, from the least to the most significant bit of the byte;
• \text{unpad}(D) removes the trailing bits ‘0’ of D, if any, then the last bit ‘1’ (e.g., \text{unpad}(\text{0x01}) is the empty string, \text{unpad}(\text{0x0B}) = \text{`110'}).

Note that \text{unpad}(D) is not defined for strings of only zeroes, but that does not pose a problem for D as it has at least one ‘1’. We can view D as a string of bits that is padded with the \text{pad}10^* padding rule. Here, \mathcal{TS}_c uses the multi-rate padding rule \text{pad}10^*1 instead. Multi-rate padding appends an initial ‘1’-bit, then zeroes and then a final ‘1’-bit. In the pseudocode in Section 1, the initial ‘1’-bit is contained in the encoding of D, and the final one is materialized by XORing 0x80 into the last byte of M'. Thanks to the fact that the last bit of parameter D is ‘0’, setting the final bit of M' to ‘1’-bit corresponds with XORing 0x80 into the last byte of M'.

The default value for D, namely 0x1F, is such that \text{unpad}(D) = \text{`1111'} and so TurboSHAKE128 and TurboSHAKE256 coincide with round-reduced SHAKE128 and SHAKE256, respectively.

Security

Changing the number of rounds in the underlying permutation from 24 in the SHA-3 standard functions to 12 in TurboSHAKE implies a drastic reduction in safety margin. Still, TurboSHAKE is a reduced-round version of Keccak and thereby directly benefits from all the cryptanalysis on the latter. There is ample evidence from third-party cryptanalysis that 12 rounds provides a comfortable security margin [2, 3, 41, 4, 15, 14, 59, 25, 16, 20, 26, 57, 40, 21, 56, 58, 19, 22, 37, 24, 55, 23, 36, 1, 30, 44, 71, 64, 68, 45, 34, 42, 69, 17, 38, 39, 78, 70, 77, 35, 51, 66, 49, 46, 43, 27, 12, 72, 50, 28, 13, 47, 31, 76, 74, 33, 32, 63, 29, 75, 65, 48], as well as from our own investigations [8, 7, 18, 9, 53].

We maintain a list of cryptanalysis results on our ciphers [BDH+23]. At the time of this writing, the best collision attack applicable to TurboSHAKE or to any SHA-3 instance works only when the permutation is reduced to 6 rounds [71, 29], and preimage attacks reach only 4 rounds [31, 74, 65]. Hence our proposal has a safety margin of 6 out of 12 rounds for collision and (second) preimage resistance.

Currently, the structural distinguisher that reaches the highest number of rounds is called SymSum and works on Keccak reduced to 9 rounds [TGRL21]. This distinguisher considers self-symmetric strings of bits, that is, strings of the form X \| X \| Y \| Y \| \ldots \| Z \| Z, where X, Y and Z are 32-bit strings. The SymSum distinguisher produces a set of self-symmetric strings such that the set of corresponding outputs through 9-round Keccak sums to a self-symmetric string.

Finally, we limit the supported capacity to at most 512 bits, as we do not think that it makes much sense to claim more than 256 bits of security.

KangarooTwelve vs TurboSHAKE128

K12 is a XOF that is defined on top of the \text{Keccak-}p[1600, n_r = 12] permutation [10, 73]. In its specifications, K12 uses a tree hash mode on top of a function called “F”, which is exactly \mathcal{TS}_{256}, and hence K12 can be equivalently recast as a mode on top of TurboSHAKE128 instead.

K12 uses TurboSHAKE128 with three values for D, namely, D \in \{\text{0x06}, \text{0x07}, \text{0x0B}\}. For a protocol that uses both K12 and TurboSHAKE128, it is therefore recommended to avoid using these three values for D.

Acknowledgments

We wish to thank all the researchers who analyzed Keccak and contributed to its understanding. This is what allowed us to confidently propose schemes based on round-reduced Keccak.

References

• [ADG+16] Amy, Di Matteo, Gheorghiu, Mosca, Parent, Schanck. Estimating the Cost of Generic Quantum Pre-image Attacks on SHA-2 and SHA-3. Selected Areas in Cryptography, 2016, pp. 317–337.
• [AK09] Aumasson, Khovratovich. First Analysis of Keccak. NIST hash forum (2009).
• [AM09] Aumasson, Meier. Zero-sum distinguishers for reduced Keccak-f and for the core functions of Luffa and Hamsi. Rump session of CHES, 2009.
• [Ber10] Bernstein. Second preimages for 6 (7? (8??)) rounds of Keccak?. NIST hash forum (2010).
• [BDH+23] Bertoni, Daemen, Hoffert, Peeters, Van Assche, Van Keer. Third-party cryptanalysis, 2023. keccak.team.
• [BDPV11a] Bertoni, Daemen, Peeters, Van Assche. Cryptographic sponge functions. SHA-3 competition (round 3) (2011).
• [BDPV11b] Bertoni, Daemen, Peeters, Van Assche. On alignment in Keccak. Ecrypt II Hash Workshop, 2011.
• [BDPV11c] Bertoni, Daemen, Peeters, Van Assche. The Keccak reference. SHA-3 competition (round 3) (2011).
• [BDPV14] Bertoni, Daemen, Peeters, Van Assche. The Making of Keccak. Cryptologia 38 (2014), no. 1, 26–60.
• [BDH+18] Bertoni, Daemen, Peeters, Van Assche, Van Keer, Viguier. KangarooTwelve: Fast Hashing Based on Keccak-p. ACNS, 2018, pp. 400–418.
• [BDPV22] Bertoni, Daemen, Peeters, Van Assche. Twelve-round Keccak for secure hashing. NIST Fourth PQC Standardization Conference, 2022.
• [BDL+19] Bi, Dong, Li, Zong, Wang. MILP-aided Cube-attack-like Cryptanalysis on Keccak Keyed Modes. Des. Codes Cryptography 87 (2019), no. 6, 1271–1296.
• [HNR21] Heim Boissier, Noûs, Rotella. Algebraic Collision Attacks on Keccak. IACR Trans. Symmetric Cryptol. 2021 (2021), no. 1, 239–268.
• [BC10a] Boura, Canteaut. A zero-sum property for the Keccak-f permutation with 18 rounds. ISIT, 2010, pp. 2488–2492.
• [BC10b] Boura, Canteaut. Zero-Sum Distinguishers for Iterated Permutations and Application to Keccak-f and Hamsi-256. Selected Areas in Cryptography, 2010, pp. 1–17.
• [BCD11] Boura, Canteaut, De Cannière. Higher-Order Differential Properties of Keccak and Luffa. Fast Software Encryption, 2011, pp. 252–269.
• [CG18] Chen, Gao. Quantum Algorithms for Boolean Equation Solving and Quantum Algebraic Attack on Cryptosystems. IACR Cryptology ePrint Archive 2018 (2018), 8.
• [DVA12] Daemen, Van Assche. Differential Propagation Analysis of Keccak. Fast Software Encryption, 2012, pp. 422–441.
• [DM14] Das, Meier. Differential Biases in Reduced-Round Keccak. Africacrypt, 2014, pp. 69–87.
• [DDS12a] Dinur, Dunkelman, Shamir. New Attacks on Keccak-224 and Keccak-256. FSE, 2012, pp. 442–461.
• [DDS13] Dinur, Dunkelman, Shamir. Collision Attacks on Up to 5 Rounds of SHA-3 Using Generalized Internal Differentials. FSE, 2013, pp. 219–240.
• [DMP+14a] Dinur, Morawiecki, Pieprzyk, Srebrny, Straus. Practical Complexity Cube Attacks on Round-Reduced Keccak Sponge Function. IACR Cryptology ePrint Archive 2014 (2014), 259.
• [DMP+15] Dinur, Morawiecki, Pieprzyk, Srebrny, Straus. Cube Attacks and Cube-Attack-Like Cryptanalysis on the Round-Reduced Keccak Sponge Function. Eurocrypt, 2015, pp. 733–761.
• [DEM15] Dobraunig, Eichlseder, Mendel. Heuristic Tool for Linear Cryptanalysis with Applications to CAESAR Candidates. Asiacrypt, 2015, pp. 490–509.
• [DL11] Duan, Lai. Improved zero-sum distinguisher for full round Keccak-f permutation. IACR Cryptology ePrint Archive 2011 (2011), 23.
• [DGP+12] Duc, Guo, Peyrin, Wei. Unaligned Rebound Attack: Application to Keccak. Fast Software Encryption, 2012, pp. 402–421.
• [Gon19] Goncharov. Using fuzzy bits and neural networks to partially invert few rounds of some cryptographic hash functions. CoRR abs/1901.02438 (2019).
• [GLL+20] Guo, Liao, Liu, Liu, Qiao, Song. Practical Collision Attacks against Round-Reduced SHA-3. J. Cryptol. 33 (2020), no. 1, 228–270.
• [GLS+22] Guo, Liu, Song, Tu. Exploring SAT for Cryptanalysis: (Quantum) Collision Attacks Against 6-Round SHA-3. Asiacrypt, 2022, pp. 645–674.
• [GLS16] Guo, Liu, Song. Linear Structures: Applications to Cryptanalysis of Round-Reduced Keccak. Asiacrypt, 2016, pp. 249–274.
• [HLY21] He, Lin, Yu. Improved Preimage Attacks on 4-Round Keccak-224/256. IACR Trans. Symmetric Cryptol. 2021 (2021), no. 1, 217–238.
• [HLY22] He, Lin, Yu. Improved Preimage Attacks on Round-Reduced Keccak-384/512 via Restricted Linear Structures. IACR Cryptol. ePrint Arch. 2022 (2022), 788.
• [HAD+22] Huang, Agmon Ben-Yehuda, Dunkelman, Maximov. Finding Collisions against 4-Round SHA-3-384 in Practical Time. IACR Trans. Symmetric Cryptol. 2022 (2022), no. 3, 239–270.
• [HWX+17] Huang, Wang, Xu, Wang, Zhao. Conditional Cube Attack on Reduced-Round Keccak Sponge Function. Eurocrypt, 2017, pp. 259–288.
• [HWX+19] Huang, Wang, Xu, Wang, Zhao. New Distinguisher on Reduced-Round Keccak Sponge Function. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 102-A (2019), no. 1, 242–250.
• [JN15] Jean, Nikolić. Internal Differential Boomerangs: Practical Analysis of the Round-Reduced Keccak-f Permutation. Fast Software Encryption, 2015, pp. 537–556.
• [KSP+14] Kuila, Saha, Pal, Roy Chowdhury. Practical Distinguishers against 6-Round Keccak-f Exploiting Self-Symmetry. Africacrypt, 2014, pp. 88–108.
• [KMS18] Kumar, Mittal, Singh. Cryptanalysis of 2 Round Keccak-384. Indocrypt, 2018, pp. 120–133.
• [KRA18] Kumar, Rajasree, AlKhzaimi. Cryptanalysis of 1-Round Keccak. Africacrypt, 2018, pp. 124–137.
• [KMN+13] Kölbl, Mendel, Nad, Schläffer. Differential Cryptanalysis of Keccak Variants. IMA Int. Conf., 2013, pp. 141–157.
• [Lat09] Lathrop. Cube Attacks on Cryptographic Hash Functions. Master’s thesis, Rochester Institute of Technology, 2009.
• [LC17] Li, Cheng. Distinguishing Property for Full Round Keccak-f Permutation. CISIS, 2017, pp. 639–646.
• [LS19] Li, Sun. Preimage Attacks on Round-Reduced Keccak-224/256 via an Allocating Approach. Eurocrypt, 2019, pp. 556–584.
• [LSLW17] Li, Sun, Liao, Wang. Preimage Attacks on the Round-reduced Keccak with Cross-linear Structures. IACR Trans. Symmetric Cryptol. 2017 (2017), no. 4, 39–57.
• [LBD+17] Li, Bi, Dong, Wang. Improved Conditional Cube Attacks on Keccak Keyed Modes with MILP Method. Asiacrypt, 2017, pp. 99–127.
• [LDB+19] Li, Dong, Bi, Jia, Wang, Meier. New Conditional Cube Attack on Keccak Keyed Modes. IACR Trans. Symmetric Cryptol. 2019 (2019), no. 2, 94–124.
• [LHY21a] Lin, He, Yu. Improved Preimage Attacks on 3-Round Keccak-224/256. IACR Trans. Symmetric Cryptol. 2021 (2021), no. 3, 84–101.
• [LHY23] Lin, He, Yu. Practical Preimage Attack on 3-Round Keccak-256. IACR Cryptol. ePrint Arch. 2023 (2023), 101.
• [LCW19] Liu, Cao, Wang. Finding Ordinary Cube Variables for Keccak-MAC with Greedy Algorithm. IWSEC, 2019, pp. 287–305.
• [LIM+20] Liu, Isobe, Meier, Yang. Algebraic Attacks on Round-Reduced Keccak/Xoodoo. IACR Cryptol. ePrint Arch. 2020 (2020), 346.
• [LQT19] Liu, Qiu, Tu. New Techniques for Searching Differential Trails in Keccak. IACR Trans. Symmetric Cryptol. 2019 (2019), no. 4, 407–437.
• [MRH04] Maurer, Renner, Holenstein. Indifferentiability, Impossibility Results on Reductions, and Applications to the Random Oracle Methodology. TCC, 2004, pp. 21–39.
• [MDVA17] Mella, Daemen, Van Assche. New techniques for trail bounds and application to differential trails in Keccak. IACR Trans. Symmetric Cryptol. 2017 (2017), no. 1, 329–357.
• [MW18] Micciancio, Walter. On the Bit Security of Cryptographic Primitives. Eurocrypt, 2018, pp. 3–28.
• [Mor15] Morawiecki. Malicious Keccak. IACR Cryptology ePrint Archive 2015 (2015), 1085.
• [MPS13] Morawiecki, Pieprzyk, Srebrny. Rotational Cryptanalysis of Round-Reduced Keccak. FSE, 2013, pp. 241–262.
• [MPSS13] Morawiecki, Pieprzyk, Srebrny, Straus. Preimage attacks on the round-reduced Keccak with the aid of differential cryptanalysis. IACR Cryptology ePrint Archive 2013 (2013), 561.
• [MS13] Morawiecki, Srebrny. A SAT-based preimage analysis of reduced Keccak hash functions. Inf. Process. Lett. 113 (2013), no. 10–11, 392–397.
• [NPR+11] Naya-Plasencia, Röck, Meier. Practical Analysis of Reduced-Round Keccak. Indocrypt, 2011, pp. 236–254.
• [NIST15] NIST. Federal information processing standard 202, SHA-3 standard: Permutation-based hash and extendable-output functions. August 2015. doi:10.6028/NIST.FIPS.202.
• [NIST16] NIST. NIST special publication 800-185, SHA-3 derived functions: cSHAKE, KMAC, TupleHash and ParallelHash. December 2016. doi:10.6028/NIST.SP.800-185.
• [NIST22] NIST. Post-quantum cryptography, selected algorithms 2022. 2022. csrc.nist.gov.
• [Pre22] Preston. Applying Grover’s Algorithm to Hash Functions: A Software Perspective. CoRR abs/2202.10982 (2022).
• [QSL+17] Qiao, Song, Liu, Guo. New Collision Attacks on Round-Reduced Keccak. Eurocrypt, 2017, pp. 216–243.
• [QHD+22] Qin, Hua, Dong, Yan, Wang. Meet-in-the-Middle Preimage Attacks on Sponge-based Hashing. IACR Cryptol. ePrint Arch. 2022 (2022), 1714.
• [Raj19] Rajasree. Cryptanalysis of Round-Reduced Keccak using Non-Linear Structures. Indocrypt, 2019, pp. 175–192.
• [RSS11] Ristenpart, Shacham, Shrimpton. Careful with Composition: Limitations of the Indifferentiability Framework. Eurocrypt, 2011, pp. 487–506.
• [SKR17] Saha, Kuila, Roy Chowdhury. SymSum: Symmetric-Sum Distinguishers Against Round Reduced SHA3. IACR Trans. Symmetric Cryptol. 2017 (2017), no. 1, 240–258.
• [SG18] Song, Guo. Cube-Attack-Like Cryptanalysis of Round-Reduced Keccak Using MILP. IACR Trans. Symmetric Cryptol. 2018 (2018), no. 3, 182–214.
• [Song17] Song, Guo, Shi, Ling. New MILP Modeling: Improved Conditional Cube Attacks on Keccak-Based Constructions. Asiacrypt, 2018, pp. 65–95.
• [SGSL18] Song, Liao, Guo. Non-Full Sbox Linearization: Applications to Collision Attacks on Round-Reduced Keccak. Crypto, 2017, pp. 428–451.
• [TGRL21] Suryawanshi, Saha, Sachan. New Results on the SymSum Distinguisher on Round-Reduced SHA3. Africacrypt, 2020, pp. 132–151.
• [TGRL22] Viguier, Wong, Van Assche, Dang, Daemen. KangarooTwelve. Internet Research Task Force draft, August 2022. IETF datatracker.
• [WYD+16] Wang, Li, Gao, Li, Wang. Allocating Rotational Cryptanalysis based Preimage Attack on 4-round Keccak-224 for Quantum Setting. IACR Cryptol. ePrint Arch. 2022 (2022), 977.
• [XZWB17] Wang, Li, Gao, Li, Wang. Quantum rotational cryptanalysis for preimage recovery of round-reduced Keccak. IACR Cryptol. ePrint Arch. 2022 (2022), 13.
• [XZWB18] Wei, Wu, Fu, Dong, He, Hong, Wang. Preimage attacks on 4-round Keccak by solving multivariate quadratic systems. IACR Cryptol. ePrint Arch. 2021 (2021), 732.
• [YLWZ18] Yan, Lai, Wang, Yu, Xing. New zero-sum distinguishers on full 24-round Keccak-f using the division property. IET Inf. Secur. 13 (2019), no. 5, 469–478.
• [YT18] Ye, Tian. New Insights into Divide-and-Conquer Attacks on the Round-Reduced Keccak-MAC. IACR Cryptology ePrint Archive 2018 (2018), 059.