Hacker News Reader

Comment by yellow_lead | Hacker News Reader

If you check hash(a) == hash(b), the attacker cannot produce a valid hash, because cryptographic hash functions are one way. This assumes you use a secure hash function, like not md5.

Even if they discover hash(b), they can't produce b.

View on HN

What people always forget when they make statements about hashing being one way is that these algorithms are designed to be incredibly fast.

So if what you’re hashing has low entropy/randomness (say a password) then you can totally brute force it.

In fact if there’s not a salt you can look it up in a rainbow table, saving yourself some compute. Googling a hash also works sometimes. If you want to brute force look at hashcat.

Something like SHA256 protects about 128 bits of entropy. If you go much lower than that, you’ll be brute forced. You can look at hashcat benchmarks online to estimate the time and money necessary to perform the attack. Anyone can crack an average simple password using a single round of SHA256 in no time.

For passwords you often intentionally use an algorithm that is known to be somewhat slow. You want to rate limit passwords anyway and generally you should not be getting enough logins that an inefficient algorithm matters (if it does you apply denial of service protection not fix your password algorithm).

If the check is not done in constant time, the attacker can discover hash(b), by trying one byte at a time (without knowing b).

Of course it's way less impactful than discovering b, but it's nonetheless a vulnerability.

H is a cryptographic hash. You observe via timing that H("123") starts with the same byte as H(key). How do you then guess the next byte?

Consider what happens to the first byte of the hash if you add a new byte to the input, e.g. "1230"...

I just guess the HASH's bytes, not the KEY's.

To be practical: my first guesses are:

0000...0000

1000...0000

2000...0000

...

f000...0000

I discover that c000...0000 takes slightly longer. Then, my next guesses are:

c000...0000

c100...0000

c200...0000

...

cf00...0000

Now I discovered that c700...0000 takes slightly longer...

And so on.

At the end I have the full hash.

Getting the plaintext key from that hash is a different problem.

UPDATE: damn, I understood what you mean now. Sorry. Yes, it will take a lot of computation to generate the good hashes.

The problem is that as an attacker sending requests to the server, what you control is the API key, not the hash of the API key. To test a specific hash like "c000...0000" you would need to find an input to the hash function that will yield this output. Cryptographic hash functions have a property called preimage resistance that means this is prohibitively difficult (see e.g. https://crypto.stackexchange.com/a/1174).

But you're not passing the hash to the service. You're passing the key. The hashing is done on a system not controlled by you, so you need to guess a plaintext that has the prefix you need.

This is not an easy problem, and in fact is what is used as proof-of-work for many cryptocurrencies.

>This assumes you use a secure hash function, like not md5.

There is no practical preimage attack against MD5, it would work fine in this case.

Reply on news.ycombinator.com