5

In this answer, it was recommended that you add random padding when hashing messages for a trusted timestamp, such as for predictions, in order to avoid dictionary and brute force attacks (at least when the message itself doesn’t have much entropy, as in the example in the question).

The answer briefly says that 80 bits of entropy (at most 16 printable characters) should be enough to stop any attacker. Is there anywhere I can find more information about this? Most of the information I’m able to find is about hashing passwords, which isn’t particularly applicable (you need to be able to verify the password without having the user remember 80 bits of information, so analyses of random salts don’t particularly apply in this case, and bcrypt is overkill when you can use random padding).

Community
  • 1
Daniel H
  • 153
  • 4
  • So you're asking "Why 80 bits?"? Or is this about the general idea? – StackzOfZtuff Apr 07 '15 at 08:08
  • Mostly I’m asking “Why 80 bits”, but I also want to know how much this number changes between hash functions, how much it’s expected to grow with time (1 bit per 18 months in accordance with Moore’s law? Faster?), etc. I’d also be interested in anything else relevant, like not using MD5 because you could fake two different predictions with different “random” padding using prefix collision attacks, or my analysis here being wrong and something similar to bcrypt still being necessary. – Daniel H Apr 07 '15 at 13:51
  • Alternatively, I just realized that for a hash function outputting n bits, then using more than n bits of padding would be more than enough for even theoretical uncrackability because then a wide variety of plaintexts could all hash to the same value with different paddings. This should remain valid as long as preimage attacks are infeasible. – Daniel H Sep 22 '15 at 20:03

1 Answers1

0

I think 80 bits is just a reference to the general lower limit of what's considered computationally infeasible to brute force.

From wiki:

In 2002, distributed.net cracked a 64-bit key in 4 years, 9 months, and 23 days.

As of October 12, 2011, distributed.net estimates that cracking a 72-bit key using current hardware will take about 45,579 days or 124.8 years.

Alternatively, by my calculations using the hashcat benchmarks it would take about 3 million years to brute force 80 bits using SHA256 on their "PC4".

how much it’s expected to grow with time

It would be the same as brute forcing any other random value, however in the case of predictions it's also relevant how long that prediction is likely to be of value to an attacker.

80 bits is probably excessive if your prediction is about something that happens next week, about 54 bits would keep an attacker busy until then.

thexacre
  • 8,444
  • 3
  • 24
  • 35