In May 2009, Nate Lawson reported a vulnerability in Google Keyczar, a cryptography library meant to make crypto hard to misuse. The entire bug was one line of Python:

python
return self.Sign(msg) == sig_bytes

The Java version had the same flaw, spelled Arrays.equals(hmac.doFinal(), sigBytes). Both compute the correct HMAC for a message and compare it to the signature the client sent. Both comparisons stop at the first byte that differs. That early exit is the vulnerability: the time it takes the server to say "invalid signature" tells the attacker how many leading bytes of their guess were correct.

A year later the same pattern turned up across OpenID. A July 2010 disclosure on the openid-security list named JOpenId, the Janrain Python library, and the Janrain Ruby library — every implementation the reporter had examined compared HMACs with == or equals().

The attack is linear, not exponential

An HMAC-SHA1 tag is 20 bytes. Guessing it blind means searching a 2^160 space. The early-exit comparison collapses that into 20 sequential searches of 256 values each.

The attacker fixes a message they want forged — say, an auth token with admin=true — and sends it with a candidate tag. The server computes the real HMAC and walks the two byte arrays until they disagree. If the attacker's first byte is wrong, the loop exits after one iteration. If it's right, the loop runs one iteration further before failing on byte two. So the attacker tries all 256 values for byte 0, keeps the one that takes measurably longer, then moves to byte 1 with the prefix locked in. Each position costs at most 256 guesses (times however many repeated samples the noise demands), and the comparison itself hands out progress markers.

Two things are worth being precise about, because this attack is often oversold. First, as Lawson spelled out in the OpenID thread, the attack recovers the correct HMAC for one chosen message — it does not reveal the server's key, and it must be repeated per token. That's still game over if the chosen message is an administrator's session token. Second, the per-byte timing difference is one loop iteration of a tight memory-compare — nanoseconds. Which raises the obvious objection: nobody can see nanoseconds through a network stack.

How small a difference survives the network

That objection was tested quantitatively by Crosby, Wallach, and Riedi in "Opportunities and Limits of Remote Timing Attacks" (ACM TISSEC, 2009), using tens of millions of timing measurements in the lab and across the Internet. Their headline numbers: with the right filtering, an attacker can measure remote processing-time differences with 15–100µs accuracy across the Internet, and as good as 100ns over a local network. Their simulated attacker, using statistical hypothesis testing, reliably distinguished processing-time differences as small as 200ns on a LAN and 30µs on a WAN with 1,000 measurements.

The non-obvious part is how. Averaging is the intuitive way to fight jitter, and it's the wrong one. Network response times aren't Gaussian — the distribution has a long, heavy tail of delayed packets. Crosby et al. found that the low-noise, low-varying part of the distribution sits around the 5th–15th percentile of response times, and that low-percentile filters significantly outperform both the mean and the median. (Interestingly, they also beat the minimum, which is noisier than the low percentiles.) Their best discriminator for deciding whether two request classes differ in processing time compared two low-percentile filters against each other.

A few more findings from the paper that recalibrate intuitions:

  • Server load barely helps the defender. With 1,000 samples, adding Apache application load contributed only about 1µs of jitter — versus roughly 20µs of WAN jitter it was already buried in.
  • Hardware artifacts matter more than hops. They observed no significant correlation between unfiltered jitter and network latency or hop count, but their Intel Gigabit NIC produced 10–30x more unfiltered jitter than a generic onboard adapter, depending on interrupt coalescing.
  • Precedent was already there. Brumley and Boneh had extracted a 1024-bit RSA private key from an SSL server with ~1.4 million queries (effective on a LAN, not across the Internet), and Canvel et al. recovered an IMAP password through TLS across two switches and a firewall by measuring a 2ms difference.

So the honest threat model for an early-exit HMAC compare: a single-iteration difference is near the edge of feasibility across the open Internet, but comfortably measurable from the same LAN, the same datacenter — or, in 2026, the same cloud availability zone. An attacker who can place a VM near your service gets the 1,000-samples-per-decision regime.

What the fix actually does

The fix Lawson proposed for Keyczar is the now-canonical accumulator loop:

python
def constant_time_eq(a, b):
    if len(a) != len(b):
        return False
    result = 0
    for x, y in zip(a, b):
        result |= ord(x) ^ ord(y)
    return result == 0

No comparison inside the loop, no early exit, no data-dependent branch. Every byte is XORed and OR-ed into the accumulator regardless of previous matches, so the loop's duration depends only on the length of the inputs. The length check does exit early — meaning an attacker can learn the length of the expected value, which for a fixed-width MAC is public anyway. Lawson flagged exactly this caveat: acceptable for HMAC verification, not necessarily for other secrets.

The 2010 OpenID disclosure added a subtler warning: avoid data-dependent branches in your "constant-time" code, including ternary expressions — a conditional that compiles to a branch reintroduces the timing difference you were trying to remove.

Standard libraries have since absorbed all of this, and their documentation encodes the same tradeoffs:

  • Python added hmac.compare_digest() in 3.3. The docs tell you to use it instead of == when verifying any externally supplied digest. Since 3.10 it calls OpenSSL's CRYPTO_memcmp() when available, and the docs note the residual leak honestly: a timing attack could theoretically reveal the types and lengths of the operands, but not their values.
  • Go's crypto/subtle.ConstantTimeCompare(x, y []byte) documents that "the time taken is a function of the length of the slices and is independent of the contents" — and that it returns 0 immediately on a length mismatch. The package also ships ConstantTimeSelect, ConstantTimeCopy, and friends for building larger branch-free logic.
  • Go 1.24 added subtle.WithDataIndependentTiming(f), which enables architecture-level data-independent timing (PSTATE.DIT on Arm64 with FEAT_DIT) while f runs — because on modern CPUs even individual instructions can be data-dependent in latency. Its documentation carries the crucial disclaimer: it does not make variable-time code constant-time. The algorithm has to be branch-free first; the CPU flag only hardens the instructions underneath it.

The takeaways that generalize

The Keyczar bug is seventeen years old and still gets reintroduced constantly, because == is the natural thing to type and it passes every functional test. The durable lessons:

  1. Any comparison against a secret-derived value is a comparison against a secret. MAC tags, password-reset tokens, API keys, webhook signatures — if an attacker supplies one side and times the answer, early exit is an oracle.
  2. Don't reason about exploitability from your own ping times. The defender imagines Internet jitter; the attacker buys a VM in your availability zone and filters at the 5th percentile. 200ns at 1,000 samples is the published floor from 2009, on 2009 hardware.
  3. Use the stdlib primitive, and know what it doesn't cover. compare_digest and ConstantTimeCompare fix the comparison. They don't fix a data-dependent code path that runs before the comparison — a parse that bails early, a cache lookup that hits only for valid IDs. The comparison is just the most common place the branch hides.

References

timing-attacksconstant-timehmacside-channelscryptography