Yeah, like fdomig said: timing attacks. The Python example included a mitigation. PHP includes hash_equals() and a constant time comparison in Javascript isn't difficult to write.
> (I don't write Ruby so I don't know if this is overloadable somewhere.)
Ruby allows overriding the == operator[1], but OpenSSL::HMAC.digest returns an instance of String[2], rather than returning a special subclass of string or some other kind of special HMAC-representing class overloading ==.
To be pedantic, in Ruby, the fact that an object is of class String is not sufficient evidence that a method has not been overloaded (they can be overloaded via the objects eigenclass), though you're probably right.
Even if it did (and it doesn't, I checked), you're probably still better off doing it explicitly since it's easier to audit, less likely to differ across implementations, and less error prone (e.g. swap the order of the comparison and you're back to plain old String#==).
Unnecessarily so too, Python provides hmac.compare_digests since Python 3.3 and it was backported to Python 2.7.7, which was released almost a year ago.
All crypto libraries should provide and developers should use constant time comparisons for exactly this purpose. A good example from the same page is the Go crypto/hmac package includes mac.Equal to check for equality without introducing timing weaknesses.
It's also pretty sad that they didn't use a constant time comparison function. Whether it exists in the target language standard library or not, it's easy enough to write one.
No. A timing attack is used to determine the shared key that creates the HMAC. Because == and === (depending on the language) use memcmp(), the time of the comparison varies. EG:
The code would compare only up to the difference and return, indicating through the time spent analyzing the HMAC how many characters are the same. The attacker can then work the HMAC like they would a combination lock, till they reproduce the key used.
That's why a constant time comparison is so important: it leaks far less information.
Ideally, the execution time in this verification is independent of T. But many languages use string-comparison algorithms that exit immediately on failure. If Eve can detect this difference with high granularity, she has an oracle telling her how many leading bytes of a guessed tag T' are valid:
O(M, T') -> n
She can use this to recover the first byte of a valid tag for M:
for k in [0, 255]:
if O(M, k || 0000...) > 0:
return k
She can extend this to recover the second byte, the third, and so on. Eventually, Eve will recover T such that MAC(K, M) = T. In other words, Eve is able to forge an authentication tag T for an arbitrary message M.
What she won't do is recover K. So while she can forge tags for arbitrary messages, each forgery will require a fresh, online interaction with the verifying party. She cannot work backwards from (M, T) to K.
