Suppose I want to commit to a uniformly picked nonce of fixed length $n$ bits without revealing the nonce, so I use a secure hash function $H$ mapping messages to digests of length $d$ bits. Suppose $H$ promises a complexity of $\sim 2^d$ for a preimage attack, and $\sim 2^{d/2}$ for a collision attack. Suppose $n$ is publicly known.

Clearly, at least for the preimage attack, the above promise cannot gain you a complexity of more than $2^n$ for $n<d$, because then you can just try out all $2^n$ messages.

My question is: is it considered safe for practical purposes (say, for $H$ from the SHA-2 or SHA-3 family) to use $n=d$ for obtaining the full or almost full complexity of $H$, or should $n$ be even greater?

  • $\begingroup$ @kelalaka No, the length of the nonce is supposed to be fixed to n bits. I've edited the question to make that clearer. $\endgroup$ – Alexander Klauer Jan 12 '19 at 16:13
  • $\begingroup$ could you also name some the practical purposes? $\endgroup$ – kelalaka Jan 12 '19 at 16:51

First of all, the output sizes of SHA2 are 224, 256, 384 or 512-bit and of SHA3 are 224,256, 384, 512-bit.

Normally, hash functions are accepting arbitrary length inputs and producing fixed-length outputs. Hence, collisions are inevitable by the pigeonhole principle. We want them to have collision resistant in a way that even mathematically they exist, it must be hard to find one.

There are no known collisions for SHA2 and SHA3 series (but SHA-1 is shuttered).

If we limit the input size shorter than the output size, it is unlikely that we will find a collision. Consider 128-bit input size, the total inputs are $2^{128}$ and even for today technology, it is far to reach for search. The SHAs will map these $2^{128}$ different inputs into a much larger space as 224, or to 521-bit. Since we don't know how the values are distributed by these hash functions, we cannot prove it but we can say that it very likely that the values are distinct.

We can say similar arguments if the input size equal to output size.

| improve this answer | |

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.