8
$\begingroup$

I am looking for some reference documentation suggesting a minimum reasonable length for a truncated hash (specifically, a truncated SHA-256 hash) to ensure preimage resistance.

Obviously, truncating a SHA-256 hash to, let's say, a 32-bit value is unsafe since a preimage can be quickly found by bruteforcing.

But what about a 64bit value? What about a 128-bit value?

I found NIST Special Publication 800-107 R1: Recommendation for Applications Using Approved Hash Algorithms but I did not find there any specific suggested minimum value.

$\endgroup$
7
$\begingroup$

minimum reasonable length for a truncated hash (specifically, a truncated SHA256 hash) to ensure preimage resistance.

To answer this one might consider the attacks.

  • Brute-force preimage algorithm: Currently, the collective power of the BitCoin miners reached $\approx 2^{92}$ SHA-256 double hashes per year in 06 Agust 2019. If you assume that the miners double this in every year, they need 18 years to reach $2^{128}$. Though doubling every year is highly unreasonable and we don't expect that. Here, larger than 128 will be enough.

  • Multi-target preimage algorithm: There is also multi-target attack by using classical computing. Using Oechslin's rainbow tables on a parallel machine:

    For $\mathcal{O}(2^n/t^3)$ sequential evaluation of the hash function it will require $\mathcal{O}(2^n/t)$ time if parallelized $t^2$ ways to find a preimage for the first of $t$ targets.

    This really depends on the number of the target, however, with 128-bit output, for a billion targets the cost would be below $2^{100}$ and the time would be below $2^{70}$ if you truncated to 128-bit. Adjust the numbers according to your requirements.

  • Generic quantum preimage algorithm If ever build a quantum algorithm for Grover's algorithm it will find a pre-image in $\mathcal{O}(2^{n/2})$-time. Therefore, if you consider this target you need to double the output size like stay with around 256.

    The above cost is not included the cost of the hash implementation and set times.

The hash functions, classically, recommended by the collision resistance, which hash $\mathcal{O}(\sqrt{n})$ by the generic birthday attack. Recommending a truncation for a hash function with only pre-image resistance like 100-bit is not a good idea. Since there will be some people who will use this truncated version where collision resistance is also required. The 100-bit output will have 50-bit collision resistance with 50% probability and the 50% probability for an adversary it too high, which is not negligible in some sense. One might consider, the lower probabilities.

In short, SHA256-224 is the least recommended size if you consider all available NIST hash families after the SHA-1 which has 160-bit output. Of course, for SHA256-224, the collision attack is considered, too.

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