Constant time (ct)

kola has already turned several "please don't forget" rules into "otherwise it does not compile". Forget to consume a resource and you get a compile error (linearity). Touch the outside world and the signature has to say so (effects). State a promise as a contract and it is either proven or checked at run time. This chapter applies the same approach to one more property: the running time of cryptographic code must not depend on a secret. The property is called constant time, and the ct fn modifier enforces it.

Why you cannot branch on a secret

Consider a naive password check that compares one character at a time and returns at the first mismatch. A guess that is wrong in its first character is rejected slightly faster than one that matches the first three. By measuring that difference, an attacker recovers the secret one character at a time. This is a timing attack.

A cache attack is a close relative. The processor keeps recently used memory in a small, fast cache, so reading an address that is already cached takes measurably less time. If a memory address is chosen by a secret (an index into the S-box, the lookup table at the heart of AES, say), the state of the cache afterwards reveals which address was read, and with it part of the secret. Cryptographers settled on a rule in response: code over secret data must take the same time and touch the same addresses whatever the secret's value. In practice that means no branching on a secret, no indexing by a secret and no dividing by one. kola has the compiler check that rule, the way it checks effects and linearity.

ct fn: every parameter is a secret

ct goes before fn, next to pub, and is part of the signature: pub ct fn f(...) -> T !{}. It is independent of the effect row. !{} is about authority (no I/O, no allocation, no blocking) and ct is about time, so the two combine freely.

Inside a ct fn, every parameter is treated as secret, and secrecy propagates through every expression that uses it. The checker then refuses everything that would make time or memory access depend on a secret value:

branching on it: if, match, while, and the left operand of && and || (short-circuiting decides whether the right side runs);
a loop whose trip count depends on it;
indexing or slicing by it (xs[i], xs[a..b]), because the address leaks through the cache;
/ and %, because hardware division takes variable time and also traps on zero;
checked + - *, because the overflow trap is a branch on the secret;
a secret shift amount in << or >> (shifting a secret value by a public amount is fine);
an early return, break or continue inside a secret-dependent branch;
? and .unwrap() on a secret Option or Result, which are conditional exits or traps;
calling a function that is not ct. Like an effect, ct is contagious: a ct fn may call only other ct functions and the widen, narrow and wrap builtins.

What remains is what cryptographic code actually uses: the bitwise operators & | ^ ~, the wrapping arithmetic +% -% *%, shifts by a public amount, indexing by a public index (a loop counter or a literal), mask-and-select, and .len, which is public because an array's length says nothing about its contents.

The basic toolkit is a mask-select and a comparison that produces a mask, built from bitwise and wrapping operations only:

ct fn ct_select(mask: u64, a: u64, b: u64) -> u64 !{} {
    b ^ (mask & (a ^ b))
}

ct fn ct_eq_mask(x: u64, y: u64) -> u64 !{} {
    let d = x ^ y;
    let nz = d | (0u64 -% d);
    (nz >> 63) -% 1u64
}

test select_picks_by_mask {
    assert ct_eq_mask(7u64, 7u64) == 0xFFFFFFFFFFFFFFFFu64;
    assert ct_eq_mask(7u64, 8u64) == 0u64;
    let m = ct_eq_mask(3u64, 3u64);
    assert ct_select(m, 100u64, 200u64) == 100u64;
}

The secret never decides a jump or an address. It only takes part in arithmetic whose result is chosen by a mask.

The select idiom: an if that does not branch

One construct looks like a branch and is not one. A two-armed if expression whose arms are statement-free expressions built from literals, locals and non-trapping operators is a select. The compiler computes both arms and picks one with a mask, without a jump. Computing a carry bit is the standard example:

ct fn ct_add_carry(a: u64, b: u64) -> u64 !{} {
    let t = a +% b;
    if t < a { 1u64 } else { 0u64 }
}

On most processors this becomes a conditional move, an instruction that picks one of two values without jumping. It is a defined lowering rule rather than a hope that the C compiler happens to emit one: the same predicate decides both whether the checker accepts the if and how the backends lower it, so the two cannot disagree. As soon as an arm contains a call, a statement, an index, a shift or checked arithmetic, the if is a real branch again and the checker refuses it.

pub parameters: public data inside a ct fn

Some inputs are genuinely public: an offset, a length, a round number. Mark such a parameter pub, and inside the ct fn it starts out public, so you may branch and index on it. A byte codec typically has this shape, with secret data at public offsets:

ct fn ct_load(b: [u64; 4], pub i: usize) -> u64 !{} {
    b[i]
}

pub is checked at the call, not taken on trust. If one ct fn passes a secret into another's pub parameter, the caller is refused, because the callee will branch and index on that argument as if it were public:

ct fn rd(t: [u64; 4], pub off: usize) -> u64 !{} { t[off] }

ct fn caller_bad(secret: usize, t: [u64; 4]) -> u64 !{} {
    rd(t, secret)
}

error[card §6b]: [ct fn `caller_bad`] secret-derived argument passed to `pub` parameter `off` of ct fn `rd` — the callee branches/indexes on it as public data
  --> a.kl:4:5
   |
 4 |     rd(t, secret)
   |     ^^^^^^^^^^^^^
   = help: pass only public values (loop counters, lengths, literals) here, or drop the callee's `pub` marker and make it handle secret data

A parameter that is or contains a Secret[T] (below) cannot be marked pub: "public" and "must not be revealed" cannot both be true of one value. A public companion gets its own parameter.

When the compiler refuses

A naive S-box lookup by a secret byte is the case ct exists for:

ct fn ct_sbox_naive(secret_byte: u8) -> u8 !{} {
    let table: [u8; 4] = [10u8, 20u8, 30u8, 40u8];
    table[secret_byte]
}

error[card §6b]: [ct fn `ct_sbox_naive`] index/slice bound depends on a secret ct-fn parameter — a secret-dependent memory address leaks through cache-timing (the AES S-box class)
  --> b.kl:3:5
   |
 3 |     table[secret_byte]
   |     ^^^^^^^^^^^^^^^^^^
   = help: index by a public loop counter and use mask/select to pick the wanted entry (an oblivious linear scan), never by the secret directly

Whatever the table holds, the address read depends on the secret. The repair is an oblivious scan: read every entry with a public counter, and let the secret take part only in a comparison whose result is a mask for the select.

ct fn ct_eq_u8(a: u8, b: u8) -> u8 !{} {
    let d = a ^ b;
    let nz = d | (0u8 -% d);
    (nz >> 7) -% 1u8
}

ct fn ct_sel_u8(mask: u8, a: u8, b: u8) -> u8 !{} {
    b ^ (mask & (a ^ b))
}

ct fn ct_sbox_scan(secret_byte: u8) -> u8 !{} {
    let table: [u8; 4] = [10u8, 20u8, 30u8, 40u8];
    let mut acc: u8 = 0u8;
    let mut i: u8 = 0u8;
    while i < 4u8 {                          // public counter: always 4 iterations
        let m = ct_eq_u8(i, secret_byte);    // the secret only produces a mask
        acc = ct_sel_u8(m, table[i], acc);   // public index, branchless pick
        i = i +% 1u8;
    }
    acc
}

The scan is slower than the lookup, but its time does not depend on the secret, which is what you are paying for. For small tables (up to a few hundred entries) it is the standard defense.

Ordinary checked arithmetic over a secret is another common refusal, since its overflow trap is a branch. The repair is the wrapping operator:

ct fn ct_add_bad(secret: u64, k: u64) -> u64 !{} { secret + k }

error[card §6b]: [ct fn `ct_add_bad`] checked `+` traps on overflow — a secret-dependent operand makes the trap a secret-dependent branch
  --> c.kl:1:52
   |
 1 | ct fn ct_add_bad(secret: u64, k: u64) -> u64 !{} { secret + k }
   |                                                    ^^^^^^^^^^
   = help: use the wrapping form (`+%`) — card §2

A loop bounded by a secret is refused for the same reason, even when its body contains no branch: the number of iterations is itself the leak. Bound the loop by a public count and decide inside the body with mask and select. Because these rules live in the checker, removing a constant-time protection means changing a signature, which a reviewer sees, rather than making a quiet edit to a body.

From source to machine code

The checker establishes the property in the source. A select in the source is not yet a branchless instruction sequence, though. An optimizing compiler such as gcc or clang is free to turn a mask-select back into a branch on the secret, there is no flag that forbids it, and real crypto libraries have been broken this way. So the guarantee also depends on which backend compiles the ct fn.

kola's own backend, which builds executables without a C compiler (kola build --link uses it first on x86-64 and AArch64), compiles ct functions under a check. Before and after optimizing, it computes for each function which parameter values and memory contents reach a branch condition, a load or store address, or a division operand. If optimization made that set grow for a ct fn, the function is compiled again without optimization. A select becomes a conditional move, and the later stages that pick machine instructions add no branch of their own.

When a program is built through the C backend instead, its ct functions are compiled by the C compiler with everything else, and the guarantee holds at the source level only. For that case there is a separate tool, heterobuild. It splits one file in two: the ct functions are compiled by kola's own backend into one object file (compiled machine code that is not yet a complete program), the rest by the C backend into another, and the linker joins the two into an executable. It handles a single self-contained file (no use std::... yet) and currently emits native objects only on AArch64 (Linux ELF and macOS Mach-O); on other hosts it says so and stops. You can confirm the split with nm, the standard tool that lists the symbols in an object file: the ct function is defined (T) in the constant-time object and only referenced (U) from the C one.

A ct fn with a hand-written hw implementation (see Contracts and SPEC-CARD §8) is covered too: kola pack check disassembles the leg and refuses one that contains a conditional or indirect jump.

What ct does not cover

ct is a guarantee about instructions: the machine code contains no branch, memory access or division that depends on a secret. That closes the classic timing attacks, the ones exploited over the network that still break careless crypto code. It is not protection against everything.

SIMD lanes: the ct ones and the ones refused here

SIMD (single instruction, multiple data) types hold several numbers side by side in one wide register, called lanes, and one operation works on all lanes at once. std has two families of them, on opposite sides of the line this chapter draws. u32x4 and u32x8 (four and eight u32 lanes) offer only bitwise & | ^, wrapping +% -% *% and shifts by a literal count. There is no run-time shift amount and no ==, nothing that could branch or address by a lane's value. That operation set is constant-time by construction, so these types are usable inside a ct fn:

ct fn ct_xor4(a: &[u32], b: &[u32], out: &mut [u32]) !{} {
    let va = u32x4::load(a, 0);
    let vb = u32x4::load(b, 0);
    u32x4::store(out, 0, va ^ vb);
}

test ct_simd_lanes_work {
    let a = [0xFFu32, 0u32, 0xFFu32, 0u32];
    let b = [1u32, 2u32, 3u32, 4u32];
    let mut out = [0u32; 4];
    ct_xor4(&a, &b, &mut out);
    assert out[0] == 0xFEu32;
    assert out[1] == 2u32;
}

The other family, the media lanes i16x8, u8x16 and i32x4 and their 256-bit twins i16x16, u8x32 and i32x8, exists for codecs: saturating arithmetic, min and max, comparisons that produce masks, byte shuffles. These are data-dependent by design (a byte shuffle is a table lookup), so every media operation is refused inside a ct fn, like any other non-ct call:

ct fn ct_media_bad(a: i16x8, b: i16x8) -> i16x8 !{} {
    i16x8::sat_add(a, b)
}

error[card §6b]: [ct fn `ct_media_bad`] ct fn calls non-ct fn `sat_add` — a `ct` fn may only call other `ct` fns or the `widen`/`narrow`/`wrap` builtins
  --> d.kl:2:5
   |
 2 |     i16x8::sat_add(a, b)
   |     ^^^^^^^^^^^^^^^^^^^^
   = help: mark `sat_add` itself `ct fn` once it is verified constant-time, or inline the operation

In practice the two families do not compete: a cipher's inner loop uses u32x4 because it has to be ct anyway, and a video codec uses the media lanes because it carries no secrets. Because the compiler enforces the split, a later edit that swaps a media operation into a ct fn stops at that line. More on both families in SIMD.

Secret[T]: a box for secret data

ct fn covers the computation. Secret[T] covers the data on either side of it: a key, a derived secret, anything that must never be printed, written to a log or read by more code than necessary. It is a built-in, opaque, linear resource, not a library struct with a private field (kola has no field privacy, so such a struct would expose its payload). The operations are few:

test wrap_expose_wipe_roundtrip {
    let s = Secret::wrap(0xC0FFEEu64);   // box a data value
    let v = Secret::expose(&s);          // the one read path, easy to grep for
    Secret::wipe(s);                     // consume and scrub
    assert v == 0xC0FFEEu64;
}

test secret_eq_is_constant_time {
    let a = Secret::wrap([1u8, 2u8, 3u8, 4u8]);
    let b = Secret::wrap([1u8, 2u8, 3u8, 4u8]);
    let same = Secret::eq(&a, &b);       // constant-time comparison
    Secret::wipe(a);
    Secret::wipe(b);
    assert same;
}

Secret::wrap(x) boxes a value. Secret::expose(&s) is the only way to read it; everywhere else the value stays secret to the ct checker. Secret::wipe(s) consumes the box and scrubs it with volatile writes, writes the compiler is not allowed to remove. Secret::eq(&a, &b) compares byte secrets in constant time. A plain zeroing loop is not a scrub: the compiler sees that nothing reads the zeros afterwards, removes the loop as a dead store, and the bytes stay in memory.

Because a Secret is a resource, one that goes out of scope without a wipe is a compile error. And a Secret cannot be turned into text at all; putting one in an f"..." hole is refused:

error[card §2]: a `Secret` cannot be rendered as text
  --> s2.kl:4:25
   |
 4 |     log::info(f"secret={s}");
   |                         ^
   = help: a secret is un-str-ifiable by design; expose + format the specific field you intend to reveal

A secret whose length is known only at run time is a Secret[Vec[u8]]. Secret::wrap(v) moves the Vec in, so the box becomes the buffer's only owner, and wipe scrubs the whole capacity. The box owns the buffer from the wrap onward, not its history: a backing the Vec abandoned while growing, or a copy you made earlier, is still yours to deal with, so build the buffer at its final size and wrap it before anything reads it. For a stream of secrets, Secret::wipe_into(s) scrubs the box and hands back the same buffer, empty, for reuse. A reference cannot be boxed (Secret[&r [u8]] is refused, since scrubbing a pointer leaves the bytes behind it). For bytes you were only lent, such as a buffer passed in as a parameter, Secret::wipe_bytes(b) scrubs them where they live. Nothing makes that call mandatory, so for borrowed bytes "boxed" and "scrubbed" are separate questions.

In std::crypto, the entry points that take long-lived keys take the box: ed25519::public_key and sign, x25519::x25519 and pubkey_gen, p256::ecdh and p384::ecdh, ECDSA signing, ML-KEM keygen and decaps, ML-DSA signing, and the X.509 builder's signing key. The bulk encryption loops (AES-GCM, ChaCha20-Poly1305) take bare arrays on purpose: a record key is expanded once and used for every packet, and an expose per record would buy nothing. Wherever you do call expose, expose late, use the value at once, and let the exposed binding die in the narrowest scope you can.

The normative reference is SPEC-CARD §6b (kola help spec-card), and the Secret and SIMD sections of STD-CARD.