A tag comparison is written as a byte-by-byte loop that returns false at the first mismatch. Explain the attack this permits against a 16-byte tag, estimate the number of queries needed, and give the correct comparison.

A tag comparison is written as a byte-by-byte loop that returns false at the first mismatch. Explain the attack this permits against a 16-byte tag, estimate the number of queries needed, and give the correct comparison.

Approach: Note that the loop's running time depends on how many leading bytes matched, then count the queries to determine each byte in turn.

The early return leaks how many leading bytes were correct, so an attacker recovers the whole 16-byte tag one byte at a time in about 4,096 queries instead of the 2^128 a forgery should cost. The loop returns after k+1 comparisons when the first k bytes match, so the response time grows by one iteration per correct byte. The attacker fixes a message, tries all 256 values of the first tag byte, and keeps the one whose response was measurably slower, which costs 128 queries on average and 256 in the worst case. Repeating for all 16 bytes is 16 times 256, which is 4,096 queries at worst. One iteration is only a few nanoseconds, so on a noisy network the attacker averages over many samples per candidate, which raises the query count by a few orders of magnitude and still leaves the attack entirely practical, especially from a colocated machine. The correct comparison accumulates the difference over every byte and tests once at the end, for example by setting diff to the running bitwise or of x[i] xor y[i] across all 16 bytes and returning whether diff is zero. It must have no early exit, no branch on the data, and no table lookup indexed by secret bytes, since a data-dependent memory access is a cache timing side channel with the same consequence. Length must be checked separately and constant time comparison must be used for every secret, including passwords and session tokens.

Follow-up: Your constant time compare is correct in C but the compiler optimises the loop into an early exit. How do you stop that happening?

Key concepts: timing attack, constant time, side channel, byte at a time.