X25519, and the field arithmetic it shares with Ed25519

Status: built. Not independently reviewed. Sub-issue 3 (#200) of the self-contained TLS 1.3 client (#197). The client’s key exchange is X25519 alone (docs/tls-pure.md §3.3), and X25519 handles a secret scalar. So this slice is as much about how it computes as what: a field module with no branch on data, shared with std.ed25519, which moved onto it. Moving Ed25519 onto it found two bugs in Ed25519 that predate this work (§4.2) and made it 31 to 37 times faster (§6).

Update (#381): std.x25519 no longer uses the field this document describes. It runs on std.field25519_51, five limbs of 51 bits on the mul_wide and add_carry builtins, 10 to 23 times faster (Cranelift on a loaded x86-64 to LLVM on arm64) (docs/wide-multiply.md §10). §2, §3.1 and §6 below describe std.field25519, which std.ed25519 still uses; §5’s mutants of the X25519 ladder now run against the new field.

1. What was built

One copy of the field. Before this, Ed25519’s field arithmetic was private to std/ed25519.cho: a byte-oriented bit-serial bignum, with gf_add/gf_mul/gf_invert over 32-byte buffers (docs/ed25519.md §2). #200 asked for it to be extracted, not copied. It could not be extracted as it was, because it branched on its data (docs/ed25519.md §6: “every branch here … is an ordinary conditional”). So it was replaced: gf_*, bn_modpow and the two exponent tables are gone from std/ed25519.cho, and both curves use std.field25519. The duplication check (crates/cancho/tests/conformance/duplication.rs) has no exception for it.

2. Representation

An element is a [int] of 16 limbs of 16 bits, least significant first. That is TweetNaCl’s representation, chosen over the faster radix-2^25.5 one for the size of its bounds:

• After carry, a limb is in [0, 2^16), or slightly outside it for limb 0, which takes the folded carry.
• Inputs to mul may be sums or differences of up to four reduced elements (Ed25519’s point_add makes those), so a limb is under 2^19 in magnitude.
• A product of two such limbs is under 2^38, a column of 16 is under 2^42, and folding the top half down as × 38 (2^256 = 38 mod p) gives under 2^48.

A signed 64-bit int holds every intermediate with 15 bits to spare. The arithmetic is written wrapping_* anyway, so that no overflow test is emitted on a secret limb (docs/chacha20.md §2’s reason).

Ed25519’s constants d and √−1 became 16-limb tables. They were converted from the byte tables they replace by a script, and d was also checked against TweetNaCl’s D. A point is one [int] of 64: X, Y, Z, T at offsets 0, 16, 32, 48.

Scratch, not arenas. mul and the rest take a scratch slice the caller owns. An arena is a malloc (docs/hkdf.md §2), and one scalar multiplication does about 2,800 field multiplications.

3. Secrets

The X25519 scalar is secret, and so is everything the ladder computes from it. The rule is the one from docs/chacha20.md §3: no branch and no memory index depends on a secret.

• The ladder walks all 255 bits whatever they are. A bit decides only cswap, a masked XOR (mask = 0 − bit). Clamping is done bit by bit as the ladder reads the scalar (scalar_bit), so the caller’s scalar is never written. The index i >> 3 is the loop counter, which is public.
• The field. Every loop bound is a constant. invert and pow2523 follow fixed exponents, so their if bit != 2 && bit != 4 tests the loop counter, not data. pack reduces with two trial subtractions, each kept or dropped by cswap_at.
• The result. The all-zero check ORs every output byte, and refuses only after that. The result is what the caller gets, so it is public.

3.1 Checked with Valgrind, not only by reading

docs/chacha20.md §3 read the object code. That shows where the conditional jumps are, but not what they depend on. This slice used the ctgrind method instead:

1. The secret bytes are marked undefined for Valgrind’s Memcheck.
2. The function is called.
3. Memcheck reports every conditional jump, and every memory access whose address, that depends on an undefined value.

Arithmetic on undefined values is not reported, which is exactly the constant-time distinction. The harness (tests/ct/ctgrind.c) calls the cancho functions directly from an object cancho build --emit obj made. A slice is a pointer and an i64 length, an int an i64, and capabilities and regions are no argument at all (crates/cancho-codegen-llvm/src/emit.rs, leaves_into).

scripts/curve25519_ctgrind.sh target/release/cancho

What this does not show:

• Timing on real hardware, since no dudect-style statistical test was run. #208 runs one, over X25519 and the AEAD.
• Instructions whose own timing depends on their operands. 64-bit imul is constant-time on current x86 cores, and the field uses nothing else that varies.
• The Cranelift backend’s code. The harness uses the default (LLVM) object.

The claim is exactly that, on the LLVM backend for x86-64, no branch and no memory index in X25519 depends on the scalar.

4. Checked, not assumed

tests/programs/curve25519_driver.cho drives std.x25519 and std.ed25519 from standard input. crates/cancho/tests/conformance/x25519.rs runs it in cargo test.

4.1 RFC 7748

tests/vectors/rfc7748.txt has 8 rows, all passing on both backends:

• §5.2’s two scalar multiplications. The second has the top bit of u set, which must be ignored.
• §5.2’s iterated test at 1 and at 1,000 iterations.
• §6.1’s Diffie-Hellman example: both public keys, and the shared secret computed from each side.

The RFC’s text is not reachable from the machine this was written on. The values were written down from it and kept only after OpenSSL (through pyca/cryptography) gave each of them; for the iterations, OpenSSL was run the same number of times.

The 1,000,000-iteration vector is RFC 7748’s last one. It takes about 19 minutes at this speed, so it is not in cargo test. It was run by hand (echo "I 1000000" | curve25519_driver, 1,157 seconds) and gave 7c3911e0ab2586fd864497297e575e6f3bc601c0883c30df5f4dd2d24f665424. OpenSSL, run the same million times through pyca/cryptography (87 seconds), gives the same bytes. A first draft of this section quoted the value from memory with its last bytes wrong (…887424); the two independent computations settled it.

4.2 Wycheproof

The two Ed25519 bugs, both older than this slice:

1. A signature that is not 64 bytes trapped verify (SIGILL, status 132). It read sig[32..64] without checking the length, and Wycheproof’s truncated signatures reach that. verify now returns 0 for a key that is not 32 bytes or a signature that is not 64.
2. An R with x = 0 and the sign bit set was accepted (case 151). RFC 8032 §5.1.3 step 4 says decoding fails when x = 0 and the sign bit is 1. The old code, and the first port, negated zero to get zero and went on. OpenSSL refuses it. point_unpack now refuses it.

docs/ed25519.md §5 is corrected in place to say so.

4.3 Against OpenSSL

scripts/curve25519_differential.py checks against OpenSSL (pyca/cryptography):

• X25519: a random scalar with a random 32-byte u (non-canonical, p and up, one round in fifty), and the public key of a random scalar.
• Ed25519: a random seed and message. The public key and the signature must equal OpenSSL’s, OpenSSL’s signature must verify here, and with one random bit flipped it must be refused by both.

The existing Ed25519 tests pass unchanged: tests/accept/ed25519.cho (three OpenSSL keypairs), tests/accept/ed25519_long.cho, and backends::the_two_backends_agree_on_ed25519.

5. Mutants

scripts/curve25519_mutants.py builds 21 mutants of the three files as local modules beside the driver. It runs each against the RFC 7748 table, every Wycheproof X25519 and Ed25519 case, tests/accept/ed25519.cho’s signatures, and 300 differential rounds. 21 mutants, 19 killed, 2 survive, and neither is a missing test:

• X25519, “the final swap left out”: equivalent. After the ladder, swap holds bit 0 of the scalar. Clamping always clears bit 0, so the final cswap RFC 7748 writes is always a no-op here.
• Ed25519, “point_equal compares x only”: not reachable through verify by any input that can be constructed. Two points with the same x differ only in the sign of y. To make verify’s equation hold up to that sign, a forger would have to choose R after seeing H(R || A || M). The full comparison stays, because it costs two multiplications and the shortcut is a bug waiting for a caller other than verify.

The 19 that are killed:

• field25519: the carry’s fold as 37; the product’s fold as 19; one carry instead of two; a 15-limb cswap; the inversion’s exponent; pack keeping the unreduced value; one trial subtraction instead of two; unpack keeping the top bit; pow2523’s exponent.
• x25519: a24 as 121666; bit 254 not set; the low three bits not cleared; the zero secret accepted; z3 not multiplied by x1.
• ed25519: the ladder’s swap back left out; the second square-root candidate never tried; the sign bit ignored; x = 0 with the sign bit accepted; a signature of any length passed on.

python3 scripts/curve25519_mutants.py target/release/cancho     # about a minute

6. Cost

One core of an Intel Xeon at 2.80 GHz, median of 5, the time being the difference between 1 call and many (tests/programs/ed25519_bench.cho, timed by scripts/curve25519_bench.py):

#200’s gate asked that Ed25519 not slow down by more than 5%; it is 31 to 35 times faster. X25519 is about 28 times slower than OpenSSL’s assembly. A TLS handshake does two X25519 operations (the key share and the shared secret), so about 2.2 ms against the 0.6 ms a whole OpenSSL handshake takes (docs/tls-nonblocking.md §8.1). The next step, if it matters, is 10 limbs of 25.5 bits: 100 products a multiplication instead of 256, at the cost of tighter bounds.

7. Not done here

• The 1,000,000-iteration RFC vector in CI (§4.1). It is too slow for cargo test at this speed. It was run once by hand, and it agrees with OpenSSL.
• A statistical timing test. That is #208. §3.1 is a data-flow check, not a timing measurement.
• Constant-time Ed25519 signing. The field and the point ladder are now branch-free, but the scalar arithmetic mod L (bn_*) still branches on the secret scalar (§3.1’s third row). docs/ed25519.md §6 is corrected to say exactly that.
• An independent review. That is #209.