Hacker News Reader

Comment by ramchip | Hacker News Reader

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"...

View on HN

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.

Reply on news.ycombinator.com