3
$\begingroup$

It seems to me that a timing-safe way to compare any two strings is to take a secure hash of both of them and then compare the result. I would expect that the initial hashing would render any timing attack non-exploitable.

It also seems that when hashing passwords, there is no need for a timing-safe comparison of the hashes, since the salt (which is secret) means that the attacker does not know what is being compared.

Is this intuition justified, or is it incorrect?

$\endgroup$
4
$\begingroup$

Comparing hashes of strings does not fully defeat timing attacks.

For example, if we try to find a password by timing attack of

if (strcmp(sha256str(input),sha256str("honey7dew"))) ...

where sha256str outputs the SHA-256 hash of its input as a 64-char C string in hexadecimal (4 bits per char), and we initially do not know "honey7dew" but suspect that string might be a password with low entropy, we can do the following (assuming we can guess the number of characters matched by strcmp)

  • let k = "" (the hash prefix known so far)
  • for each password p in a list of common passwords, by decreasing popularity
    • let h = sha256str(p)
    • if h starts with k
      • submit p as input and find the number n of matching characters
      • if n is 64, p is the password, stop
      • set k to the first n characters of h

and it will find the password with only a few hundreds of online submissions (this can be improved significantly by avoiding submission of p that we know are not right, because we previously submitted a p0 with h0 matching h over at least 1 more character than k is).

Update per comment: the attack works just the same if the hash is salted, and the salt known to the attacker (but if there are restrictions to the number of online queries for a given salt, these restrictions might make the attack impractical).
If the hash is entropy-stretching (e.g. Argon2), the attack essentially allows to find the "honey7dew" low-entropy key/password with the same computational cost as if as if its hash was known, replacing that knowledge by a moderate number of online submissions.
If "honey7dew" is replaced by something with high entropy (hopeless to guess), there demonstrably is no attack enabled by timing of the comparison: if there was one, it would break the first preimage resistance of the hash.
If the salt is unknown to the attacker (that's often called pepper) and large enough, it is essentially an extension of the the key/password, and again there demonstrably is no attack enabled by timing of the comparison.

$\endgroup$
  • $\begingroup$ Does this attack work if the hash is salted, or if the strings have high entropy? $\endgroup$ – Demi Oct 4 '16 at 14:46
  • 1
    $\begingroup$ Important point; if you're using C, you do not want to use strcmp; it stops comparing things once it hits a 0x00 byte, which means that the above code might (depending on what sha256str("honey7dew") is), might accept a lot of invalid passwords. Worse case, the first byte of sha256str("honey7dew") is 0x00, which means that any string that hashes to a 'first byte 0x00' will be accepted. $\endgroup$ – poncho Oct 4 '16 at 16:18
  • $\begingroup$ @poncho: I was assuming sha256str outputs 64 hex characters. 64 was there, but hex was missing. $\endgroup$ – fgrieu Oct 4 '16 at 16:19
  • $\begingroup$ Is their still no attack if the hashes are properly-salted password hashes, and the salt is not known to the attacker? Example: the salt for each user is stored in the database and used to check the password. $\endgroup$ – Demi Oct 4 '16 at 20:26
  • $\begingroup$ Typically one considers salts public knowledge. $\endgroup$ – Stephen Touset Oct 4 '16 at 20:52

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.