Cairn
guides · cross-cutting lens, not tied to one category

↩ back to Guides

Constant-Time vs. Data-Dependent Execution

Four of this site's own pages already prove the same shape, without any of them naming it as one. Brian Kernighan's Algorithm clears one set bit per iteration, so its own loop runs popcount(x) times — two 32-bit inputs of the identical size can take anywhere from 0 to 32 iterations depending on which specific bits happen to be set. SWAR Popcount answers the exact same question in five fixed shift-mask-add steps, every time, for every input — its own meta line already says so: "independent of input." Bitonic Sort does the same thing for sorting: the exact sequence of index pairs it compares is "fixed by the array's length alone, computed before a single element is inspected," measured identical across sorted, reverse-sorted, and random input of the same size. For a popcount or a sort, which side of that line an algorithm lands on is just a design tradeoff. This page exists because two other pages on this site show it stop being cosmetic: HMAC's own Pitfalls section names a tag comparison that "leaks timing," and the modPow routine reused across eight of this site's Number Theory and Cryptography pages hides the textbook starting point for real power-analysis attacks on RSA in one unremarkable-looking if statement. Same shape, higher stakes.

Two kinds of "depends on the input"

Every Big-O number on this site already describes how running time grows with input size — bigger n, more work. That's not what this page is about. Hold n perfectly fixed — say, always a 32-bit integer, always a 16-byte tag — and ask a narrower question: do two inputs of that same size always cost the same number of operations, or can the specific values inside them change the count? Brian Kernighan's loop says no: x = 0xFFFFFFFF costs 32 iterations, x = 0 costs zero, both are ordinary 32-bit integers. SWAR Popcount says yes, always, on purpose.

Most of the time, letting the operation count ride on the data is free performance, not a problem — insertion sort, Timsort, and quicksort's own adaptive behavior all exist because exploiting easy input is a legitimate way to go faster, and nobody's nearly-sorted array is a secret anyone's trying to protect. The moment one of the inputs is a secret — a cryptographic key, a password, a tag meant to prove possession of one — the same data-dependence turns into a side channel: anyone who can measure how long (or how much power, or how many cache misses) an operation took can work backward toward the secret value, one observation at a time, without the algorithm ever handing it over directly.

Try it: counting bits two ways

This is the harmless version of the pattern, made visible. Pick a 32-bit integer (or draw a batch of random ones) and watch Kernighan's own iteration count bounce around with how many bits happen to be set, while SWAR's five-step count never moves. Both routines below are the exact mechanisms those two pages already built and measured — y = y & (y - 1) cleared once per set bit for Kernighan, the same five 0x55555555/0x33333333/ 0x0F0F0F0F/0x00FF00FF/0x0000FFFF fold steps for SWAR — reproduced here, not reapproximated, so the counts match those pages' own exactly.

value 0 (binary 0) — Kernighan: 0 iteration(s) · SWAR: 5 step(s), always
Try a value with no bits set (0), all bits set (4294967295), and one bit set (1) — then draw 8 random ones to see Kernighan's count spread out while SWAR's stays flat.

Removing one slow op isn't removing the leak

It's tempting to think "data-dependent" is just a property of loops-that-count-bits, and anything that avoids an obviously-variable operation is safe. Binary GCD is the clean counter-example, already sitting on this site. Its whole reason to exist, per its own intro, is hardware "with no fast integer divider" — it replaces every division with "one of three cheaper primitives": a bit test, a shift, or a subtraction, so that "embedded and constant-time bignum routines… deliberately avoid a variable-latency division instruction." That's real, and it's exactly the right instinct — division is a classic variable-latency operation on real hardware. But look at the reference implementation on that page: a while (b !== 0) loop nesting two more while loops inside it, each one running for as many bits as the input happens to have trailing zeros, or as many subtraction steps as the input happens to need. Removing one variable-latency instruction left the total iteration count exactly as data-dependent as before — Binary GCD never claims otherwise, but it's a real trap for anyone skimming "avoids division" as "constant-time."

The sharper example is the one quietly running underneath a third of this site's own Cryptography and Number Theory pages. Modular Exponentiation's own modPow — reused, by its own admission, in Miller–Rabin, RSA Encryption (and from there RSA Digital Signature), OAEP, Lucas's Theorem, Modular Inverse via Fermat, Baby-Step Giant-Step, and Tonelli–Shanks — walks the secret exponent one bit at a time:

while (exp > 0n) {
  if (exp & 1n) result = (result * base) % mod;   // <- only runs on a 1-bit
  base = (base * base) % mod;
  exp >>= 1n;
}

The squaring on the third line runs once per bit, same as always — that part's genuinely constant. The multiply on the first line only runs when the current exponent bit is 1, which means the total number of multiplications performed is exactly the exponent's own Hamming weight — the same quantity Kernighan's loop above counts, just reused as a private key's bit pattern instead of a demo integer. This is the textbook starting point for real power-analysis and timing attacks against RSA and elliptic-curve implementations: an attacker who can watch power draw or timing across enough operations with the same secret exponent can recover which bits were 1 and which were 0, a little at a time. None of this site's own modPow copies are hardened against that — they're teaching code, written to show the square-and-multiply trick itself, the same way this page's own demos below are written to show the leak rather than to resist one.

Try it: a comparison that leaks, and one that doesn't

HMAC's own Pitfalls section names this exact failure for the one place a hash-based scheme actually compares a secret-derived value against an attacker-supplied guess: "a verifier that compares tags byte-by-byte with a naive loop leaks timing… The fix is a constant-time comparison (XOR every byte pair and OR the results together, only branching once at the very end)." That page states the fix but doesn't demonstrate it. This widget does, by counting — not timing — how many bytes each comparison actually inspects before it's done, which sidesteps every wall-clock measurement problem other benchmarks on this site have run into and shows the identical fact a real timing attack would exploit, deterministically. The "valid tag" below is a fixed, made-up 16-byte sequence; move the slider to control how many of its leading bytes your guess gets right.

comparisonbytes inspectedresult
naive (early-exit on first mismatch)
constant-time (XOR-OR, branch once at the end)

Which of the site's own entries land on which side

entryshapewhy
Brian Kernighan's Algorithmdata-dependentexactly popcount(x) iterations — 0 to 32, depending on the value
SWAR Popcountfixedfive shift-mask-add steps, every input, no branch and no loop
Binary GCDdata-dependentavoids one variable-latency division instruction, but its own nested loops still run for however many trailing-zero shifts and subtractions the input happens to need
Modular Exponentiation (and everything reusing its modPow: Miller–Rabin, RSA Encryption, RSA Digital Signature, OAEP, Lucas's Theorem, Modular Inverse via Fermat, Baby-Step Giant-Step, Tonelli–Shanks)data-dependentone extra multiply per set bit in the exponent — the textbook square-and-multiply timing/power leak
HMAC's own naive tag comparison (named, not shipped, in its Pitfalls)data-dependentearly-exit loop stops at the first mismatched byte
HMAC's own named fix: XOR-OR constant-time comparisonfixedinspects every byte regardless of where — or whether — a mismatch occurs
Bitonic Sortfixedcomparator schedule fixed by array length alone, identical across sorted, reverse-sorted, and random input
Quicksort, Insertion Sort, Timsort, and most of the rest of this site's comparison sortsdata-dependent, deliberatelyexploit easy structure in the input for real speed — fine, because nothing being sorted here is ever a secret
AES's own SubBytes table lookupfixed instruction count, not fixed memory-access patternthe exact same number of lookups every time (see AES's own Complexity section), but the byte-value-dependent table address is a real, published cache-timing side channel — a third shape neither row above has, where "fixed-shape" at the instruction level still leaks

Pitfalls

Data-dependent timing is only a vulnerability when one side of the comparison must stay secret from whoever can measure the time. Nothing above makes Kernighan's algorithm, Binary GCD, or any sorting algorithm on this site "insecure" — none of them are ever handed a secret to guard. The property only turns into a side channel on the pages here that actually do: a private exponent inside modPow, a valid tag behind an HMAC comparison, and — a different shape again — a secret byte behind AES's own SBOX[byte] lookup.

"Constant-time" means constant in the number of operations and their order, not in wall-clock milliseconds. A real attacker measures wall-clock (or power, or cache state), and plenty of other effects — branch prediction, out-of-order execution, cache layout, even this page's own Math.random()-seeded draws — can smuggle a data-dependent signal back in even when the algorithm as written is fixed-shape. AES is the concrete case: its own round count never varies, yet real published attacks (named on its own Pitfalls section) have recovered keys purely from which cache line a table lookup touches — "fixed-shape" at the instruction level is necessary for constant-time code, not sufficient. The widgets above count operations, not milliseconds, deliberately: it's the one measurement this environment can make honestly (see the same choice made for a step-counted benchmark elsewhere on this site), but it understates how many other places a real side channel can hide in an actual CPU.

None of this site's own cryptographic reference implementations are hardened against the leaks this page demonstrates. HMAC's page names the fix in prose without shipping it; Modular Exponentiation and everything built on its modPow use the textbook square-and-multiply shape precisely because that's the clearest way to teach how the algorithm works; AES's own reference implementation uses a plain array-indexed S-box for the same reason, not a bitsliced or hardware-backed one. That's the right tradeoff for a page whose job is explaining the mechanism — it would be the wrong one for anything handling a real secret.