"Assume the attacker can tell how long it takes for mac == computedMac to run. If the first byte of an attacker-chosen mac is wrong for the attacker-chosen message, the loop terminates after just one comparison. With 256 attempts, the attacker can find the first byte of the expected MAC for the attacker-controlled message. Repeating this process, the attacker can forge an entire MAC."
How precisely should an attacker guess how long the comparison runs?
This is white-box security, a hypothetical setting where we assume the attacker has access to the entire knowledge of the system and to every oracle they want (like an oracle telling them how much time each function takes), but don't know any secret, like private or symmetrical keys. If you can prove that your function is secure in that setting, then it's secure in real-case situations where the attacker knows even less.
byte [32] (actualMac, expectedMac)
for int x = 0..31
if (actualMac[x] != expectedMac[x])
return false;
fi
end
return true;
This is why we should check the arrays in constant time - compare every byte in both arrays before returning. We do not return early so we can’t leak information
Also ignoring the fact that calling constant_strcompare(string, string) instead of strcompare(string, string) when working with secrets isn't that big of an ask.
why is it called constant time if it isn't constant with respect to array length? Just seems confusing because the algorithm is linear without a short circuit
What's even more confusing is that it is also constant time in the complexity analysis sense given that the mac is usually a fixed-size string after choosing a hashing algorithm.
Many current memcmp implementations use such large comparisons because they avoid hard-to-predict data-dependent branches for extracting the specific point of mismatch.
(Note that Java’s MessageDigest.isEqual has been constant time since shortly after that article and you should use it rather than writing your own in Java).
For the normal way to safely compare MAC values, see for example: https://docs.python.org/3/library/hmac.html#hmac.compare_dig...
You're asking a different question, though. You're asking about precision.
The answer here is that in many cases timing attacks pose a theoretical risk, but they can't be exploited in practice due to a low signal-to-noise ratio.
It really depends on the attack vector.
Measuring the latency of a network call (TCP) from across the other side of the world, as an example, is going to be too noisy (in many cases). Especially if the attacker wants to remain covert.
timing safe means always using the full loop and not branching away on certain values. every value needs the same time.