polycratia

A constant-time test needs a known leak it is required to find

· 9 min read

A timing harness that reports no significant difference has told you one of two things and given you no way to separate them: either the routine under test is constant-time, or the measurement never had the resolution to see anything. Both exit zero. Both print nothing alarming. The way out is to drop a routine that definitely leaks into the same run, and refuse to believe any other result until the harness has caught that one.

I ran into this while building ctsafe, a small C++17 header for comparisons that do not leak through timing and erasure the optimizer is not allowed to delete. The comparison side is testable in the ordinary way: you assert that equals returns the right answer. What you cannot assert in the ordinary way is how long it took, and that is the entire property.

In a timing harness, every failure is a pass#

Most tests I write fail loudly and pass quietly. A timing test flips that around. The statistic is a hypothesis test: two classes of input, one operation, and the question of whether the two timing distributions differ. The null hypothesis says they do not. Failing to reject the null is not evidence for it, it is the absence of evidence against it, and on a terminal those two are the same colour.

The reason this is dangerous rather than merely pedantic shows up when you enumerate the ways a timing harness can be wrong, and watch which direction each one pushes the result:

  • The benchmark result is never consumed, so at -O2 the call is removed entirely. Passes.
  • The call is loop-invariant and gets hoisted out of the measurement loop. Passes.
  • The two input classes differ in a field the routine never reads. Passes.
  • The sample count is too low for the effect size. Passes.
  • The machine has frequency scaling, noisy neighbours, or an interrupt storm, and a few cycles of difference disappear into the jitter. Passes.
  • The build is instrumented (a sanitizer, a coverage counter, a debug allocator) and every operation now costs so much that the leak is a rounding error on top. Passes.
  • The clock is coarser than the effect. Passes.

Not one bug in that category turns the suite red. A harness that has quietly stopped measuring anything looks, from the outside, identical to a codebase where every routine is perfect. For a security control, that is a bad property to have.

The control has to leak, and the run has to depend on it#

So make timing in ctsafe does not only measure ctsafe. It also measures memcmp, which leaks by construction: it returns as soon as two bytes differ, which is the whole reason the library exists. memcmp is the control of known leak. If the harness cannot find the leak in memcmp, it has not passed. It was blind, and it says so instead of reporting a clean run.

That inverts the reporting relationship. The control is not one case among many that happens to be expected-fail. It is a precondition: when the control comes out insignificant, the verdict on everything else is void, and the run reports that it was void.

The measurement itself follows dudect's approach. Each case times one operation over two classes of input. The class is drawn at random immediately before each measurement rather than in blocks, so thermal drift, scheduler pressure and frequency changes land on both classes instead of correlating with one. The slow tail gets cropped at a hundred successively tighter percentiles, because the far tail is the operating system and not the routine; Welch's t-test is applied to each crop, and the largest absolute t across all of them is the verdict. Above ten, the case fails.

Stripped to the decision it makes, the crop-and-test loop has this shape. It is a sketch for the argument, not the repository's file: ctsafe's version lives in tests/timing.hpp and tests/timing_ctsafe.cpp:

cpp
double welch_t(const stats& a, const stats& b) {
    const double va = a.variance() / a.n, vb = b.variance() / b.n;
    return (a.mean() - b.mean()) / std::sqrt(va + vb);
}

double max_abs_t(const std::vector<sample>& all) {
    double t_max = 0.0;
    for (int p = 0; p < 100; ++p) {
        const double cut = crop_threshold(all, p);
        stats a, b;
        for (const sample& s : all) {
            if (s.cycles > cut) continue;   // the tail is the scheduler, not the routine
            (s.klass == 0 ? a : b).push(s.cycles);
        }
        t_max = std::max(t_max, std::fabs(welch_t(a, b)));
    }
    return t_max;
}

And the gate that the whole run hangs from:

cpp
const double control = max_abs_t(measure_memcmp());
if (control <= kThreshold) {
    std::fprintf(stderr,
                 "blind: control did not leak (|t| = %.1f); no verdict\n",
                 control);
    return 2;      // not a pass, and not the same exit code as a pass
}

Two details matter more than they look. The control is measured with the same statistic and the same threshold as everything else, so it calibrates the actual instrument rather than sitting beside it as a separate sanity check that could drift away. And a case that lands on the wrong side of the line gets measured again with a different seed, because one run is one sample of a noisy process, and a borderline result is a reason to look again rather than a verdict.

The binary is built at -O2 and without sanitizers, for the same reason. The property under test is a property of optimized code: a comparison that is constant-time at -O0 and short-circuited at -O2 is a bug, not a pass. An instrumented build changes the cost of everything enough to hide what you came to look for.

The erase half has the identical problem, and needs a different answer#

The other bug ctsafe exists to fix is the memset at the end of a function that the compiler is free to delete, because the buffer is dead afterwards. The test you would naturally write reads the buffer back and asserts zeroes, and reading it back is precisely the case the optimizer is not permitted to remove. The test makes the bug unreproducible by observing it. Nothing in that test says anything about the real situation, where a function clears a buffer and then returns without anyone looking.

No positive control is available there in the same way, so the repository does the other thing: make disasm compiles three functions that differ only in how they clear a buffer nothing touches afterwards, at each optimization level, and counts the instructions. And ctsafe::erase_backend_name() reports at runtime which routine the build actually landed on, SecureZeroMemory, explicit_bzero, memset_s, or stores through a volatile pointer, because a guarantee you have to guess at is not one.

The usage side stays boring on purpose:

cpp
#include "ctsafe/ctsafe.hpp"

ctsafe::mask accepted =
    ctsafe::mask_from_bool(ctsafe::equals(expected_tag, presented_tag));
ctsafe::copy_if(accepted, session_key, derived_key, 32);

ctsafe::erase_object(session);

Boring is what I wanted. The interesting work sits in being able to tell whether it is true.

This is a reconciliation instinct, not a cryptography one#

I did not pick up this habit from cryptography. I got it from years of payment reconciliation, where a job reporting zero breaks is the most suspicious output in the system. Zero breaks means either the two ledgers agree or the job did not read one of them: failed to fetch the statement, parsed an empty file, silently filtered every row, matched on a key that is null on both sides. A clean reconciliation and a broken reconciliation produce the same report. So you make the job prove it did work: assert it consumed rows, and keep something in the data that has to come out as a break.

A constant-time harness is the same class of monitor. Its healthy state is silence, and every failure mode makes it quieter still. Any monitor shaped like that needs a way to demonstrate it can still speak.

What I would do differently#

I would put the control in the verdict line from the start, rather than adding it once I got suspicious of a clean run. When the control is a case in a list, someone eventually skips it, filters it, or marks it expected-fail and stops reading it. When it is the gate, the run cannot proceed without it.

I would keep the control's leak crude. There is a temptation to use a subtly leaky routine so the control also calibrates sensitivity near the threshold, but then a faint control is ambiguous in exactly the way the control exists to remove. An early-return comparison over sixteen bytes differing in the first one is about as loud as a leak gets, and a harness that cannot see it has nothing to say about anything quieter.

And I would be careful about treating this as a pass/fail gate on shared CI runners. It is a measurement, not a unit test: the reseed-on-borderline rule is there because one run is one sample, and a noisy host produces false alarms as well as blind runs that look like clean ones, which is the worse kind and probably the more common one. The control at least turns the second kind into an explicit result instead of a green check.

Close#

The harness's job is not to prove that a routine is constant-time. No amount of not-rejecting a null hypothesis does that. Its job is to be capable of failing, and then to fail on the things that are actually broken. Only the control speaks to the first half, and it has to be in every run, because the run where the harness went blind will look exactly like all the others.

react

$ new-project --brief

or email hey@polycratia.com