Constant-Time Comparison in Credential Checks

A login check ends in a comparison. If that comparison returns early on the first differing byte, the time it takes to reject a candidate is a function of how many leading bytes the candidate got right. An attacker who can measure that difference can recover a secret one byte at a time, reducing a search space of $256^n$ to $256n$ attempts. The attack is old, it has been demonstrated over a network against real systems, and the defence is a comparison whose running time depends only on the length of its inputs.

Where the leak comes from

The textbook equality loop is short and the compiler is free to transform it:

int check(const uint8_t *a, const uint8_t *b, size_t n) {
    for (size_t i = 0; i < n; i++)
        if (a[i] != b[i])
            return 0;        /* exits early: time depends on match length */
    return 1;
}

Each iteration costs a load, a compare, and a predictable branch. When the branch is mispredicted the pipeline flushes, and the cost of the flush is visible in the total. On a modern out-of-order core the penalty for a misprediction is on the order of a dozen to twenty cycles, while a correctly predicted iteration is a few cycles. A one-byte-at-a-time oracle therefore does not need to resolve a single cycle: it needs to distinguish “exit after byte 3” from “exit after byte 4”, which is a difference of several cycles accumulated over a function that already takes hundreds.

Two amplifiers make this practical rather than theoretical. The first is repetition: a target that can be queried thousands of times per second can be averaged, and the noise, which is roughly Gaussian, shrinks as the square root of the sample count. The second is that the attacker controls the placement of the first wrong byte. Testing candidate byte value $v$ at position $i$ means sending a prefix of $i$ correct bytes followed by $v$; if the comparison survives to position $i+1$, $v$ was right. Each position costs at most 256 probes, so a 32-byte token is recovered in a few thousand requests rather than $2^{256}$.

Kocher’s 1996 paper established the class for modular exponentiation. Brumley and Boneh later showed that OpenSSL’s RSA decryption leaked enough through network timing to recover private keys, which settled the question of whether a network’s jitter is a sufficient barrier. It is not, given enough samples.

What constant time actually means here

“Constant time” in this context does not mean the function takes an identical number of cycles on every input. It means the sequence of instructions and the memory addresses touched do not depend on the secret data. A comparison that always reads all $n$ bytes and folds the result into an accumulator satisfies that property; the loop count is public, the branch is gone, and the value of the secret only ever appears as data in registers, never as a control-flow decision or an array index.

The standard formulation accumulates the difference:

int ct_equal(const uint8_t *a, const uint8_t *b, size_t n) {
    uint8_t diff = 0;
    for (size_t i = 0; i < n; i++)
        diff |= (uint8_t)(a[i] ^ b[i]);   /* OR of XORs: no early exit */
    return diff == 0;                      /* single branch on the aggregate */
}

The |= of ^ is the primitive that every library reimplements. It is branch-free in the loop body, and the compiler will usually keep it that way because the accumulator is live across iterations. It is not guaranteed to. A compiler that recognises the pattern, or an optimiser that decides a vectorised reduction is faster, can reintroduce a data-dependent path; that is why production code calls a library routine compiled with the assumption disabled, or uses a construct the compiler cannot legally reshape. Go’s crypto/subtle.ConstantTimeCompare, OpenSSL’s CRYPTO_memcmp, and similar functions exist precisely because the property is a property of the emitted machine code, not of the source text.

There is a second subtlety in the return. diff == 0 produces a branch, but it branches on the aggregate rather than on individual bytes, so the timing reveals only the final verdict, which the caller learns anyway. The value returned must still be normalised if it feeds a secret computation; a boolean is fine for an authentication decision.

The comparisons a login path actually needs

Not every comparison in an authentication system handles a secret. Sorting out which ones do is most of the work.

The digest comparison after a password KDF needs it. The stored digest is a secret-derived value, and the candidate digest is computed from an attacker-supplied password; an early-exit comparison here hands the attacker the digest itself, one byte at a time, without ever knowing the password. That is enough to forge a session for that account in a system that stores digests as bearer-equivalent values, and enough to mount an offline attack on a much smaller space than the password’s.

The lookup that finds the record does not, in the usual design, need a constant-time comparison of the username. Usernames are not secrets in most systems, and the index lookup is a hash-table or B-tree probe whose timing depends on the key’s hash and position regardless. What it does need is to not leak whether the account exists, which is a different problem: the response time for a nonexistent user must not be conspicuously shorter than for an existing one with a wrong password. The usual remedy is to run the KDF anyway against a fixed dummy record when the user is unknown, so both paths pay the same cost. This is enumeration resistance, and it is a timing property of the whole handler rather than of one comparison.

API keys, session identifiers, password reset tokens, and one-time codes are all secrets compared against a stored value. All need constant-time comparison. The reset token deserves emphasis because it is often checked in a path that also looks up a row by token, and the row lookup itself is a comparison performed by the database. Storing a hash of the token and looking up by that hash moves the secret comparison out of the query planner’s hands and into a constant-time digest comparison, at the cost of one extra hash per verification.

Some comparisons need more than equality. A check like “is this value less than the stored threshold” is inherently order-revealing, and a constant-time version requires computing the comparison arithmetically rather than branching. That is standard in cryptographic code and rare in application code, and it is worth recognising when a threshold check sits on a secret.

Attacks that survive a correct comparison

Fixing the equality function does not fix the handler. Three leaks commonly remain.

Length. ct_equal above runs for n bytes, where n is a public length. If the function is called with a length derived from the attacker’s input, the loop count is attacker-visible. Comparing fixed-width values, or comparing a fixed-length digest of variable-length input, removes the dependence. A MAC over the presented token is the general form: the comparison is between two fixed-width tags, and the length is a constant.

Allocation and parsing. A verifier that decodes a base64 token before comparing it does work proportional to the decoded length, and may fail at the first invalid character. Both are observable. The same applies to JSON parsing, to string trimming, and to any regular expression whose matching time depends on the input.

Caching. A comparison that misses a cache line on the first access and hits on the second has a timing profile that depends on what was compared before. This is a real effect on secrets that are accessed rarely, and it is one of the reasons cryptographic code prefers to keep key material in registers and to avoid table lookups indexed by secret bits.

The general lesson from the timing literature is that constant-time primitives are necessary and not sufficient. What has to be constant is the observable behaviour of the entire operation, including the paths that handle malformed input. A verification handler whose error messages differ by type, whose response body differs in length, or whose failure path skips a database write is an oracle regardless of how its inner comparison is implemented.

Measuring the property rather than assuming it

The only reliable way to know whether a compiled function is constant time is to inspect the generated code and to test it under conditions that expose the difference.

At the source level, the pattern to look for is a loop whose trip count is independent of data and whose body has no branch on secret values. At the assembly level, the pattern to look for is the absence of conditional jumps between the entry and the return other than the final aggregate test. Tools exist for the second check: dudect-style statistical tests feed two input classes and compare cycle counts across many samples, and valgrind’s memcheck can be run in a mode that reports branches conditioned on uninitialised data, which catches the common case where a secret was never marked as such.

A statistical test is the honest instrument because it measures the property that matters. If the distribution of cycle counts for “first byte wrong” is indistinguishable from “last byte wrong” at the available sample size, the leak is below the noise floor for an attacker with the same measurement access. If it is distinguishable, no amount of source-level reasoning about the loop is worth anything.

The relationship to the rest of the login path is worth keeping straight. Constant-time comparison protects a secret that is already stored and already correct; it does not make a weak password stronger, and it does not help if the attacker can read the record outright. It closes a specific side channel in a specific operation. The stored record’s cost per guess is set by the password hashing parameters, and the number of guesses an attacker gets is set by rate limiting. Each of the three controls covers a case the other two do not.