2
$\begingroup$

For SHAKE128 hash function in SHA3VS document, I find this paragraph:

Therefore, for testing SHAKE128, (168*2)+1) = 337 unpredictable messages will be generated with lengths from 0 to 337 336 bytes (omitting 0 if zero length is not supported) and SHAKE256, (136*2)+1) = 273 unpredictable messages will be generated with lengths from 0 to 273 272 bytes (omitting 0 if zero length is not supported).

I know the hash digest length is flexible: Hash(input, length N) = N-byte digest

Question:

Is there any requirement for input length (minimum or maximum no. of bytes) to achieve 128 security level?

$\endgroup$
5
$\begingroup$

The quoted paragraph talks about the testing of SHAKE128. As usual, for the 128-bit security achievement, you need to think about the generic attacks on hash functions.

For preimage resistance, you need 128-bit digest size. However, due to the birthday attack, you need 256-bit digest size to achieve 128-bit collision resistance. That is $\sqrt{2^{256}} = 2^{256/2} = 2^{128}$.

For the input length; if the input space is small, it can easily brute-forced or a special rainbow table can be implemented to find the preimage of the hash values. For 128-bit preimage resistance, you need your input space to be around 128-bit.

$\endgroup$
2
$\begingroup$

Let's say the output length is 256 bits and consider the input length.

Preimages. If the adversary is given $h = H(x)$ and they know that $x$ is either 0 or 1 but not which it was, it does not take a long time to find out what $x$ was. If the adversary knows $x$ is 32 bits long but otherwise knows nothing about $x$, it only takes an expected $2^{31}$ trials to find $x$ and a maximum of $2^{32}$ which is small enough you can find it on your laptop.

Worse, an adversary who has many pairs of inputs and outputs $h_1 = H(x_1),$ $\dotsc,$ $h_t = H(x_t)$ can find one of the $x_i$ at cost $2^{32}\!/t$ and in time less than $2^{32}\!/pt$ if parallelized $p \geq t^2$ ways. So even if you drive the size of the input up to 128, and the input is uniform random, the adversary's cost may still be far below $2^{128}$. There are two ways to avoid this:

  1. Use a 256-bit uniform random secret input so no matter how many targets $t$ there are, the cost of a search is still far above $2^{128}$.
  2. Use a distinct salt for each instance of the hash function. You could use a counter in your application, but then if someone else uses the same hash function in another application with the same counter, an adversary could derive advantage by attacking both applications simultaneously. So in practice, you want to choose a ${\geq}128$-bit salt (which you can safely reveal to the adversary) to hash together with the 128-bit secret input, but then you are handling 256 bits of data anyway.

(Of course, a preimage attack might not find $x$; it might find $x' \ne x$ with $H(x') = H(x)$. But that may be good enough to break your application.)

PRF. Consider the prefix-PRF $F_k(x) = H(k \mathbin\| x)$ for a fixed-length key $k$. (You might use this for message authentication, for instance. It is better to use KMAC for other reasons—to avoid accidentally using the same hash for different purposes in your application—but in isolation, the security is the same.) A generic PRF distinguisher for $F_k$ works by choosing $x$ and doing a preimage search on $k$. The answer is essentially the same as for preimage search: for security, the key $k$ must be long enough that a generic preimage search will never find it.

Collisions. There are no two 1-bit or 32-bit inputs that collide under SHAKE128-256. There are certainly 256-bit inputs, and probably 128-bit inputs, that do collide, but it costs approximately $2^{128}$ to find them. If your application is limited to 32-bit inputs, then you're essentially guaranteed nobody can find a collision that affects your application. But even if you allow arbitrary-size inputs, an adversary still can't find a collision. It's the output length and the sponge capacity, not the input length, that provides collision resistance here.


In summary, you should make sure that the input has at least 256 uniform random bits in it, of which at least 128 bits (and preferably all of them) are secret, in order to ensure that the cost of finding the secret is at least $2^{128}$.

$\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.