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

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.