std.ecdh: P-256 and P-384 key exchange, constant time

Status: built. Not independently reviewed (#209). #207’s PR 3 of 5 (docs/tls-parity.md §3.2), for the self-contained TLS client (#197): the key exchange OpenSSL’s ClientHello offers beside X25519, which a server can ask for with a HelloRetryRequest. Unlike std.ecdsa, whose inputs are all public, a key exchange multiplies by a secret scalar. So everything the scalar touches runs the same instructions and the same memory accesses whatever its value. Building that found the LLVM backend undoing it (§3), and added a builtin to the language to stop it (docs/value-barrier.md).

Updated (#380, docs/p256-fast.md): P-256 no longer runs on std.bigmod. public_key is a sum of 65 entries of a table of the generator, and shared is this document’s ladder on std.p256’s straight-line field; the checks, the codes and P-384 are as described here. §2’s reductions still serve P-384 and RSA. §5 is corrected below.

1. What is built

The API.

• public_key answers scalar × G as an uncompressed point, 04 || x || y. That is the key share a ClientHello sends.
• shared answers the x coordinate of scalar × peer, which is TLS’s shared secret (RFC 8446 §7.4.2).
• The scalar is the curve’s size in bytes, big-endian, in [1, n). A random string outside that range is refused (ecdh-scalar-range), so the caller draws again. The chance of that is under 2^-32 for P-256 and under 2^-190 for P-384.
• work is work_len() words (77 KB), which is more than a region holds, so the caller allocates it with box_slice.

The peer’s point is checked before use, as SEC 1 §3.2.2.1 asks:

• its encoding: exactly 04 || x || y, since TLS 1.3 sends points uncompressed (RFC 8446 §4.2.8.2);
• both coordinates below p;
• the curve equation.

Each failure has its own tag. P-256 and P-384 have cofactor 1, so a point that passes, multiplied by a scalar in [1, n), cannot give the point at infinity. ecdh-result-infinity is checked anyway, and no input reaches it.

2. Constant time

The scalar multiplication walks the scalar four bits at a time, highest first:

• a table of 0 to 15 times the point, built first;
• for each window, four doublings, then the addition of the table entry the window names.
• The additions and doublings are complete: Renes, Costello and Batina’s formulas for a = -3 (eprint 2015/1060, algorithms 4 and 6), in projective coordinates. They are right for every input, the point at infinity and P + P included. So no branch handles a special case, and a window of zero adds the point at infinity like any other entry.
• The entry is chosen by reading all sixteen, each ORed in under a mask that is all ones for the one wanted. No address depends on the window.

That is P-256’s 64 windows, or P-384’s 96, of identical work.

std.bigmod’s reductions were branches. Now they are masks:

• mont_mul and add end with a subtraction of n when the value is at least n. That was if compare_n(...) >= 0, which branched on the value and stopped at the first limb that differed. Now ct_reduce computes the borrow of x − n over every limb, then subtracts n & mask.
• sub added n back behind if under == 1. Now it adds n & mask, where the mask is made from the borrow.
• subtract_n took its borrow from an if d < 0. Now it is the sign bit.

RSA and ECDSA verification run on the same code, and their tests pass unchanged (§6 has the cost).

What stays variable time, all of it on public values:

• the checks on the peer’s point;
• the test that the result is not at infinity;
• the inversion’s exponent, which is p − 2;
• the scalar’s range check, which compares every byte and branches only on the answer.

3. What the timing test found

scripts/ecdh_timing.py is scripts/gcm_timing.py’s dudect test over ecdh.shared (tests/programs/ecdh_timing.cho): a fixed scalar against random ones, under one peer point.

The first run failed. A scalar of 1 against random scalars gave |t| = 13.2 on P-256 and 9.5 on P-384. Scalar 1 ran 1.3% faster. A fixed random scalar against random scalars gave no signal. That is what a leak through the reductions looks like: with scalar 1 the accumulator stays at infinity, (0 : 1 : 0), whose zero coordinates rarely need a reduction.

Neither the source nor the branch audit’s first reading showed it. scripts/chacha20_branches.py listed a js in ct_reduce and a jns in select. Read in the disassembly, both test a mask the source only ever ANDs with:

• ct_reduce: test %r9,%r9; js around the load of n’s limb. clang -O2 saw that under - 1 is 0 or -1, rewrote w[n + i] & m as a select, and unswitched the loop on it.
• select: test %r14,%r14; jns, the same rewrite of w[from + j] & m. The window’s table index was a branch.

No spelling of the mask survives that, because LLVM can prove any of them is 0 or -1 (docs/value-barrier.md §2). So the masks now go through value_barrier, which the LLVM backend emits as an empty asm the optimiser cannot see through.

After it:

• The audit: scripts/chacha20_branches.py over bigmod.{mont_mul, ct_reduce, add, sub} and ecdh.{select, add_points, double_point, multiply} finds every remaining conditional jump compares a loop counter or k. mont_mul’s one js tests the sign of k, the public limb count.
• The timing test, 20,000 samples a test (max |t|):

One test still fails: Cranelift, P-384, scalar 1. A second run of 3,000 samples gave |t| = 6.2. Scalar 1 runs 0.3% faster there (100,000 cycles of 30.5 million), and a scalar under 2^32 shows the same direction more weakly (|t| = 2.8).

It is not a branch or a memory access:

• the audit of the Cranelift object finds only loop counters;
• valgrind --tool=callgrind counts 172,602,288 instructions for scalar 1 and for two random scalars, identical to the instruction;
• every index is a loop counter or a table position read for all sixteen entries.

What is left depends on the operands’ values. With scalar 1 the accumulator’s X and Z stay zero for nearly the whole ladder, so most limbs multiplied and stored are zero. That is consistent with data-dependent power and so frequency (Hertzbleed, Wang et al., USENIX Security 2022): rdtsc counts at a constant rate, so a core that clocks higher on cheaper data finishes in fewer ticks. Cranelift’s code spills more and runs 2.8 times as long, which would show it more. This is consistent with the evidence, not proven: the instruction count rules out the software explanations, and nothing here measures power.

What it means for TLS. The client draws a fresh scalar for every connection (RFC 8446 §4.2.8) and uses it once. A statistical attack needs many timings of one scalar, and a peer gets one. It also needs inputs that keep the accumulator near zero, which a random scalar does not give. The default backend, LLVM, stays below 4.5 throughout. The result is reported, not excused: by this test’s own threshold, Cranelift’s P-384 ladder is not clean.

Corrected (#208, docs/tls-assurance.md §6.1): on the Xeon. On an Apple M4 Max, scalar 1 fails on both backends, LLVM’s P-256 at |t| = 16.19, and with Arm’s data-independent-timing bit set LLVM’s falls to 1.84 (P-256) and 2.15 (P-384). That is the CPU’s data-dependent timing, which neither backend asks the CPU to turn off.

4. Correctness

Every case runs through tests/programs/ecdh_driver.cho (crates/cancho/tests/conformance/ecdh.rs):

Mutants: scripts/ecdh_mutants.py runs 16 mutants, and 16 are killed. #381: 17, all killed, on the 64-bit limbs; the select mutant re-anchored (it no longer applied after #397), P-384 points with a wrong first byte added to the evidence (P-256’s are now refused in std.p256_pt and never reached std.ecdh‘s check), and modulus_bits’ unsigned top limb added.

• In ecdh.cho: the addition and doubling formulas, the windows, the table, the select, the point at infinity, the curve equation and the on-curve check, the scalar’s range, the public key’s y, and the point’s first byte.
• In bigmod.cho: the reduction’s mask, its carry limb, and the add-back of a negative difference.

Two mutants first survived. The carry-limb mutant survived the ECDH evidence and RSA’s and ECDSA’s tests too, because no modulus in any of them is a multiple of 30 bits long. That is what bigmod_powers.txt is for. The first-byte mutant survived because the script’s evidence had no correctly sized point with a wrong first byte; the refusals were added to it.

5. Cost

One core of the Xeon in docs/chacha20.md §6, LLVM backend, the time of one shared:

Corrected (#380): P-256 is now 138 µs a shared and 35 µs a public_key on an M4 (755 and 768 µs before), 5.5 and 22 times faster; docs/p256-fast.md §9 has the machines and the loads. P-384 is as above. The timing test for the new code is docs/p256-fast.md §8.3.

TLS spends one public_key and one shared per handshake on the group the server picks. X25519 stays the share a ClientHello sends first, as OpenSSL’s does (docs/tls-parity.md §2), so P-256 and P-384 cost only when a server asks for them with a HelloRetryRequest. A generic Montgomery multiplication did not use the NIST primes’ special form, as docs/ecdsa.md §5.4 says; it was where the cost was, and for P-256 it is now used (docs/p256-fast.md §4.2).

6. What the change to std.bigmod cost

RSA and ECDSA verification use the same mul, add and sub, so the masked reductions cost them too. Measured with scripts/rsa_bench.py and scripts/ecdsa_bench.py on the LLVM backend, main before this PR against after:

RSA’s changes are within the run-to-run variation of about 10% that docs/rsa.md §5.5 reports. RSA’s time is in mont_mul’s inner loop, which did not change, so the extra pass of ct_reduce is small next to it. ECDSA does relatively more additions and subtractions, each now with a full pass, and pays about 10%. A TLS handshake verifies one or two signatures, so this is around 0.2 ms.

7. Not done here

• std.x25519 and std.field25519 onto value_barrier. Their audit is clean today only because LLVM happens not to see through their masks (docs/value-barrier.md §4). Moving them is a change with its own timing run. Done (#316, review finding A-1), with that run: docs/value-barrier.md §4.
• The scalar’s range check rejects instead of reducing. A TLS client can simply draw again.