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¹²⁸ 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¹²⁸ 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¹²⁷ 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_i obtained by enciphering the same plaintext P with M different keys K_i. And assume the attacker is satisfied if he can find at least one key K_i. Then if he applies exhaustive key search, the expected number of trials is 2¹²⁸/M. So the security strength is reduced to 128-log₂(M). If M is very large, this can reduce the security strength quite a lot. E.g., M = 2⁴⁰ reduces the time complexity to only 2⁸⁸. 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¹²⁸/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^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⁶⁴ 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 The Keccak SHA-3 submission and page 3 of our Note on Keccak parameters and usage published in February 2010.) Furthermore, the option of c=256 was also presented at numerous occasions:

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