[sdevlin]

This is a forgery attack, not a key-recovery attack.

[trebor]

I am not a cryptographer. I don't quite understand the distinction you are drawing with so little information. Care to explain what I misunderstood?

[sdevlin]

Given a message M and a secret key K, we have:

    MAC(K, M) -> T

To validate a pair (M, T), we verify:

   T = MAC(K, M)

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.

[sarciszewski]

To put it another way: You (slowly and painstakingly) defeat the authentication without having to brute force, e.g. 2^128, possible keys.

However, the key is still unknown to you. It just doesn't matter, because you can forge messages without it.

[trebor]

Thank you for the in-depth explanation!