How could HMAC comparison ever not be constant-time in Python?

Question

Python has a method specifically for comparing HMAC to prevent timing attacks: https://docs.python.org/3.7/library/hmac.html#hmac.compare_digest

And I read about timing attacks here: https://security.stackexchange.com/questions/74547/timing-attack-against-hmac-in-authenticated-encryption

My question is, how could it possibly ever not be constant-time? It would be necessary to calculate the actual HMAC in order to compare it, and it's not like you could calculate the digest 1 character at a time, right? At the end, it would just be a simple string comparison, which is 2 orders of magnitude faster than the actual HMAC calculation in my tests. So where exactly is the attack surface here? Could someone please give an example of exactly where the actual vulnerability is if I don't use hmac.compare_digest()?

Answer 1

At the end, it would just be a simple string comparison, which is 2 orders of magnitude faster than the actual HMAC calculation in my tests.

But it is not constant time. Just because they are done fast doesn't mean the difference is not measurable. For bytes values, Python first tests for equal length and equal first bytes before using memcmp to test the rest. For strings, Python compares length, then kind (if the string uses 1, 2 or 4 bytes per character), then also uses memcmp.

The Linux manpage for memcmp explicitly states:

Do not use memcmp() to compare security critical data, such as cryptographic secrets, because the required CPU time depends on the number of equal bytes. Instead, a function that performs comparisons in constant time is required. Some operating systems provide such a function (e.g., NetBSD's consttime_memequal()), but no such function is specified in POSIX. On Linux, it may be necessary to implement such a function oneself.)

A sufficiently determined attacker can exploit this weakness to figure out what hash you have stored vs the hash of the data it is sending.

Timing attacks make it possible to forge signatures. Say, a service stores authorization information in a token shared with the client. If the client could alter this token, they could gain access they would not otherwise have. To protect against this, the token is signed using an HMAC signature, letting the server verify the returned token before accepting it as valid. If the authorization data doesn't match the signature, the token is rejected.

If the server does this:

auth_data, signature = split_token(token)
expected = hmac_signature(auth_data)
if signature == expected:
    # ...

then an attacker can detect how many characters of a forged signature match the expected signature, and adjust accordingly. They start with XXXXX:000000..., then try XXXXX:1000000..., etc. until the time taken by the service increases, indicating that they have a matching first character. Then the second character can be altered, until the full signature matches.