Hacker News Reader

Comment by histories | Hacker News Reader

What's the difference between a plaintext key and a hash in this context?

>The attacker can crack the first byte of the key by trying all 256 possibilities, and observing which one caused the comparison to take longer.

It means that at the end you get the hash and not the key, but it is still a vulnerability

View on HN

Yeah, I (but I am not not OP) agree that hashing is not absolutely perfect, but it's still much much better than leaking the actual password, and it would be cool to at least compare it as a feasible solution.

Getting the first character of the hash is trivial, but as you get further and further out you need to do more and more computational work locally to guess a string which will hash to the prefix you already know (given that your hash is secure against Preimage attack). And then at the end you end up with the complete hash, which itself is extremely hard to get anything useful out of. (all of this is given that you use a hash that is resistant to Preimage attack, and preferably salting as well).

> What's the difference between a plaintext key and a hash in this context?

> The attacker can crack the first byte of the key by trying all 256 possibilities, and observing which one caused the comparison to take longer.

OK as a thought experiment, the algorithm is passed plaintext data A (the input that the hacker is trying to guess) and hashed data B.

It hashes A before starting a comparison and then does a naive check, an we have code like-

  function checkApiKey(inputKey, correctHashedKey) {
    inputHashedKey=sha256(inputKey)
    if (inputHashedKey !== correctHashedKey) {
      throw new Error("wrong key");
    }
  }

If we're using a decently secure hash algorithm, for every bit that changes in the input, we will create (indistinguishable from) random changes throughout the output. An attacker on this system can't just continually tweak the first byte of input to figure out when a longer comparison takes place, because there's no guarantee that doing that will ever result in the first byte of the hash matching the first byte of the stored hash. And in theory that doesn't actually give away any information about the full password, because if you've matched byte one, adding the next byte to your guess changes the whole hash in unpredictable ways.

Constant time still removes this sort of avenue entirely, but this would seem to confound the attack (or at least make it much harder problem to solve).

Happy to be educated otherwise if someone that's actually an expert would like to chime in?

Basically you can figure out the hash using the aforementioned timing attack.

You can now perform an offline attack against the password that produced the hash.

It’s like you hacked into the database and got the password hashes.

Then, you fall back to something like hashcat.

If with a bit of luck you just hashed your password with a single round of SHA and did not use something cool like Argon2id then you’re toast. If your password is simple you’re toast too.

On the other hand, if you hashed a totally random key, the safety will rely on whether the hashing algorithm itself is constant time or not. You just moved the needle.

> Basically you can figure out the hash using the aforementioned timing attack.

All popular hashing procedures (sha, argon, etc) to my knowledge produce high difference output for small difference inputs. This means that even with one round of sha128[0] your comparison timings turn very erratic. I won't go as far as saying that they turn random, because somebody will jump on it, but what they do achieve is render timing attacks at least impractical for the next few decades.

At least to my own knowledge.

[0] please don't use sha128!!!

> Basically you can figure out the hash using the aforementioned timing attack.

How are you going to do that?

You could use a non-constant salt for the hash, for instance use a sufficiently random number or start with one and increment it, so the comparison is hash(input+salt)==hash(secret+salt), that way each attempt gets the attacker at best a part of a different hash.

This is also assuming the secret is know in plain text – for properly stored passwords you now have hash2(hash1(input+salt1)+salt2)==hash2(prehashed-secret+salt2) with salt2 changing on each attempt.

Of course this is a more computationally expensive than a more direct time-invariant string compare such as bitwise-xor-secret-with-guess-then-bitwise-or-all-bytes-in-result-and-compare-that-to-0, so messing around with hashes & salts is probably not what you would do. The XOR-the-OR method isn't perfect, it will still at least leak the length of the secret if it is unhashed (hashing just before the comparison won't save this because the hashing itself is not time invariant).

Odds are a modern computer can crack the salt plus hash in a few seconds. Just assume secret is less than 9 chars and run a simple brute force attack.

You can use a hash where the supplier of inputKey is not able to know the hash value. E.g.,

  function checkApiKey(inputKey, correctKey) {

    r = randomString()
    inputHash = hash(r + inputKey)
    correctHash = hash(r + correctKey)
    
    if (inputHash !== correctHash) {
      throw new Error("wrong key");
    }
  }

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.

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