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. 2128 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 2128 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.
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 2128/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 N2/2c+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 264 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: