Guido Bertoni^{3}, Joan Daemen^{2}, Seth Hoffert, Michaël Peeters^{1}, Gilles Van Assche^{1} and Ronny Van Keer^{1}

^{1}STMicroelectronics - ^{2}Radboud University - ^{3}Security Pattern

2 October 2013

*This article is a copy of a message we posted on the NIST hash-forum mailing list on September 30, 2013.*

SUMMARY: Keccak instances with a capacity of 256 bits offer a generic security strength level of 128 bits against **all** generic attacks, including multi-target attacks. 2^{128} is an astronomical number and attacks with such complexities are expected to remain unreachable for decades to come.

Among other options, we have proposed instances with capacity *c*=256 as an option because they have a generic security strength of 128 bits. This means **any** single-stage (*) generic attack has an expected complexity of 2^{128} computations of Keccak-*f*, unless easier on a random oracle. This is such an astronomical amount of work that one may wonder why we would ever need more than 128 bits of security (see also *Tune Keccak to your requirements*).

In the discussions on SHA-3 we have seen some remarks on 128-bit security not being sufficient in the light of multi-target attacks. Multi-target attacks can be illustrated nicely with block ciphers.

**Single-target attack:**Say we have a 32-byte ciphertext*C*that is the result of applying AES-128 in ECB mode on a known plaintext with some unknown key*K*. Then*K*can be found by exhaustive key search: enciphering*P*by all possible values*K*until*C*appears. The right key will be hit after about 2^{127}trials and so the security strength is around 128 bits. This is the security strength the layman typically expects when using AES-128.**Multi-target attack:**Say we now have*M*ciphertexts*C*obtained by enciphering the same plaintext_{i}*P*with*M*different keys*K*. And assume the attacker is satisfied if he can find at least one key_{i}*K*. Then if he applies exhaustive key search, the expected number of trials is 2_{i}^{128}/M. So the security strength is reduced to 128-log_{2}(*M*). If*M*is very large, this can reduce the security strength quite a lot. E.g.,*M*= 2^{40}reduces the time complexity to only 2^{88}. This is still a huge number, but it can no longer be dismissed as science-fiction. Among cryptographers this security degeneration is well-known and there are methods of avoiding this, such as salting, enciphering in CBC mode with random IVs etc.

If the application does not allow avoiding multi-targets, one can decide to use AES-192 or AES-256. The reason to use 192-bit or 256-bit keys is **not** because the security strength level 128 is too small, but because in the light of multi-target attacks, we need a block cipher with a key longer than 128 bits to offer a security strength level of 128 bits. Summarizing, AES-128, AES-192 and AES-256 have key lengths of 128, 192 and 256 bits, but this does not mean they offer a generic security strength of 128, 192 and 256 bits. This is not specific for AES, it is true for any block cipher. This is also not a problem. A protocol designer who understands these issues can easily build efficient protocols offering excellent generic security strengths.

Multi-target also applies to finding (first or second) pre-images. Finding one pre-image out of *M* 128-bit hashes only takes 2^{128}/*M* hash computations.

So it is tempting to think that the 128-bit generic security strength of Keccak instances with 256-bit capacity will also degrade under multi-target attack. Fortunately, this is **not** the case, as the generic security strength level *c*/2 follows from the bound in our indifferentiability proof for the sponge construction. More specifically, the success probability of a generic attack on a sponge function is upper bounded by the sum of the attack probability of that attack on a random oracle plus the RO-differentiating advantage *N*^{2}/2^{c+1}. We have explained that in our Eurocrypt 2008 paper on Sponge indifferentiability and this was formalized by Elena Andreeva, Bart Mennink and Bart Preneel in Appendix B, Theorem 2 of their paper *Security Reductions of the Second Round SHA-3 Candidates*, and this is also true for multi-target attacks.

If one wants a hash function (any) that offers a generic security strength level of 128 bits against multi-target attacks with at most say 2^{64} targets, then one must take the output length equal to 128+64=192 bits. For a sponge function, the capacity does not need to be increased to twice the output length; if we target a security strength level of 128 bits, *c*=256 is still sufficient.

So a 256-bit capacity offers a generic security strength level of 128 bits that is absolute and does not degenerate under multi-target attacks.

For the record, we as Keccak team proposed setting *c*=256 (and even a user-chosen capacity) as an option in our SHA-3 proposal: “*If the user decides to lower the capacity to c=256, providing a claimed security level equivalent to that of AES-128, the performance will be 31% greater than for the default value c=576.*” (See page 4 of

- see slide 5 of our presentation
*1001 ways to implement Keccak*at the Third SHA-3 Conference; - see slides 13 and 22 of our presentation at FOSDEM 2013;
- see slide 48 of our presentation to NIST in February 2013.

(*) See Thomas Ristenpart, Hovav Shacham, and Thomas Shrimpton, Advances in Cryptology - Eurocrypt 2011.