4
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.