1
$\begingroup$

Regular hash functions like SHA-256 have a variable length input and measure security against collision attacks in bits. For SHA-256 this is 128 bits. When I limit the input length of SHA-256 to for instance a fixed 8 bits, the chance of a collision drops to zero (with SHA-256 there are no collisions possible with only 256 inputs, all inputs have an unique output).

How much can I truncate the output of the SHA-256 with a fixed input length of 64 bits so that I keep the same collision resistance strength characteristics as the original SHA-256 with variable length input?

$\endgroup$
3
  • 1
    $\begingroup$ What probability are you willing to accept for there to be a collision in these $2^{64}$ inputs? $\endgroup$ – SEJPM Sep 26 '20 at 14:26
  • $\begingroup$ I want the same collision resistance as the original SHA-256 with variable length input or a stronger collision resistance. With a bounded input this would basically mean no collisions at all with the 2^64 inputs, like with the 8 bit input example. $\endgroup$ – Vincent007 Sep 26 '20 at 15:46
  • $\begingroup$ A Merkle-Damgard construction (which is what SHA-256 uses) doesn't reach zero probability of collisions, even if you only have 1 input bit. The probability is vanishingly small, but never reaches zero. $\endgroup$ – Serpent27 Sep 26 '20 at 20:39
1
$\begingroup$

SHA256

The Max File Size

First of all the variable length has a limit due to the padding of SHA256. A message with length $\ell$ is padded with a 1 with necessary minimal $k$ zero bits so that

$$\ell+1+k ≡ 448 \bmod 512$$

This upper limit, actually, due to the Merkle-Damgård (MD) design of SHA256. MD based hash functions are vulnerable to length extension attacks and appending the length simplifies the security proof.

The Collisions are inevitable

Since the output of the SHA256 is limited to 256 bits and the input to $2^{64}$ bits. By the pigeonhole principle there is a least one hash output that contains more than one input. Therefore, there is always collisions.

Actually, if we consider that the SHA256 behaves uniformly, then we expect that all of the output values are equally distributed. A simple and similar experiment done for SHA-1

The generic collision attack

The generic collision of hash functions is calculated by the birthday paradox, and in cryptography, it is called birthday attack.

For a hash function with $t$ bit output the attacks requires $\mathcal{O}(\sqrt{2^{t}})$-time with %50 probability. For SHA256 this is $\mathcal{O}(\sqrt{2^{256}}) = \mathcal{O}(2^{128})$-time with %50 percentage.

Questions

When I limit the input length of SHA-256 to for instance a fixed 8 bits, the chance of a collision drops to zero (with SHA-256 there are no collisions possible with only 256 inputs, all inputs have a unique output).

You consider the reverse case. You limit the input space to 8-bit, i.e. 64 elements. Seeing a collision here is near to zero. Now you tested it experimentally and it is zero. Actually, this is like one throws 64 balls into the air and you expect them to get some of them into the same bin from $2^{256}$ bins. Hopefully, SHA256 is not such a bad hash function that doesn't have a collision with these very related inputs that have almost 8 bits differs. Theoretically, we expect the hash functions have the avalanche effect that changing one bit flips the output bit with %50 percentage. This distributes them randomly.

How much can I truncate the output of the SHA-256 with a fixed input length of 64 bits so that I keep the same collision resistance strength characteristics as the original SHA-256 with variable-length input?

$2^{64}$ cannot be easily tested for this size due to the memory and CPU requirements, entities like Google can test it like in their SHA1 experiment.

If the time is not a problem then one can build a Rainbow table to see the existence a collision or not. We, however, can calculate a probability for this assuming the $n=2^{64}$ values are chosen randomly, not sequentially.

$$ 2^{64} \approx \sqrt{2 \times 2^{256} \times p(n)}$$

$$2^{128} \approx 2 \times 2^{256} \times p(n) $$

$$ p(n) \approx \frac{1}{2 \times 2^{128}}$$

This is the probability of having a collision of randomly chosen $2^{64}$ values for SHA256. This is not going to happen.

Small input space

In Cryptography, we want the hash functions to have the pre-image resistance. Almost all cryptographic hash functions are secure against pre-image attacks. There is one special case of this attack that when the input space is small, then the attackers can calculate, too. In this case, the $2^{64}$ Input space may not be enough to protect the data. To mitigate a keyed hash function like HMAC or KMAC is advised.

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