What is an extendable output function?

Question

The standardization of SHA-3 included the specification of two functions, SHAKE128 and SHAKE256. Both SHAKEs are referred to as extendable output functions, but what makes a function an extendable output function?

Answer 1

As defined in FIPS 202, whereas SHA3-256 is a function mapping an arbitrary-length bit string to a string of 256 bits, the extendable output function SHAKE256 is a function mapping an arbitrary-length bit string to a string of infinitely many bits.

In both cases, the conjectured cost of computing a preimage or second preimage for a given $\ell$-bit output ($\ell = 256$ for SHA3-256, arbitrary for SHAKE256) is about $2^{\min\{256,\ell\}}$ bit operations, and the conjectured cost of computing a collision is about $2^{\min\{256,\ell/2\}}$ bit operations. For SHAKE128, it's rather $2^{\min\{128,\ell\}}$ for (second) preimages or $2^{\min\{128,\ell/2\}}$ for collisions.

For an adversary with a quantum computer, the exponents for preimage and second preimage attacks are halved for qubit operations due to Grover's algorithm: for SHAKE256, $2^{\min\{256,\ell\}/2}$, etc. (The costs of quantum collision search are sometimes reported to divide the exponent by three, but this is not really an accurate measure of the cost; I'd rattle off some citations but I have other work to do right now. Patches welcome!)

Note that while SHA3-256 is usually treated as an independent random oracle from SHA3-512, and while the derivative of another SHA-3 candidate BLAKE2b-256 is also usually treated as an independent random oracle from BLAKE2b-512, in contrast the functions SHAKE256-$\ell$ for all $\ell$ are dependent because they are all just $n$-bit truncations of the same SHAKE256 function. This also means that the length of the output need not be known ahead of time before computing SHAKE256.