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.
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.
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.
0) — Kernighan: 0 iteration(s) · SWAR: 5 step(s), alwaysIt'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.
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.
| comparison | bytes inspected | result |
|---|---|---|
| naive (early-exit on first mismatch) | ||
| constant-time (XOR-OR, branch once at the end) |
| entry | shape | why |
|---|---|---|
| Brian Kernighan's Algorithm | data-dependent | exactly popcount(x) iterations — 0 to 32, depending on the value |
| SWAR Popcount | fixed | five shift-mask-add steps, every input, no branch and no loop |
| Binary GCD | data-dependent | avoids 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-dependent | one 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-dependent | early-exit loop stops at the first mismatched byte |
| HMAC's own named fix: XOR-OR constant-time comparison | fixed | inspects every byte regardless of where — or whether — a mismatch occurs |
| Bitonic Sort | fixed | comparator 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 sorts | data-dependent, deliberately | exploit easy structure in the input for real speed — fine, because nothing being sorted here is ever a secret |
AES's own SubBytes table lookup | fixed instruction count, not fixed memory-access pattern | the 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 |
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.