nish/crypto/x25519

The X25519 Diffie-Hellman function of RFC 7748.

import {
  X25519_SIZE,
  x25519,
  x25519Base,
} from "nish/crypto/x25519";
import { X25519_SIZE, x25519, x25519Base } from "nish/crypto/x25519";
import { timingSafeEqual } from "nish/crypto/ct";
import { Secret, expose, secret, wipe } from "nish:secret";

const isZero = (s: u8[]): boolean => timingSafeEqual(s, new Array<u8>(X25519_SIZE))

const raw: u8[] = new Array<u8>(X25519_SIZE)
crypto.getRandomValues(raw)                              // any 32 bytes are a private key
const mine: Secret<u8[]> = secret(raw)
const myPublic: u8[] | null = x25519Base(mine)           // 32 bytes, sent to the peer
const peerPublic: u8[] = new Array<u8>(X25519_SIZE)      // the peer's 32 bytes, received
const shared: Secret<u8[]> | null = x25519(mine, peerPublic)
wipe(mine)
if (shared !== null) {
  if (!expose(shared, isZero)) {                         // a low-order peer key gives zero
    // derive keys from `shared` inside `expose`
  }
  wipe(shared)
}

Written from the specification (RFC 7748 §4.1, §5 and §6.1), in this module's own structure: nothing here is ported from another implementation. The radix-2^25.5 limbs and the shape of the inversion chain are the ideas D. J. Bernstein's "Curve25519: new Diffie-Hellman speed records" (PKC 2006) describes; the code is this module's.

The field

An element of GF(p), p = 2^255 - 19, is ten signed limbs in i64, alternately 26 and 25 bits wide, so limb i sits at bit ceil(25.5 * i) (0, 26, 51, 77, …, 230) and the ten of them span exactly 255 bits. Two things make that layout pay:

  • The product of the limbs at i and j lands exactly on the limb at i + j, except when both are odd, where it lands one bit above and is doubled to make up for it. A product that runs past limb 9 wraps to limb i + j - 10 times 19, because 2^255 = 19 (mod p). So a multiplication is a hundred i64 products and no wide arithmetic.
  • The limbs are signed, and >> on an i64 is an arithmetic shift, so a subtraction needs no bias and a carry is a floor division that works the same on a negative limb.

Signed i64 overflow is undefined behaviour in this language (only wrappingAdd, wrappingSub and wrappingMul from nish:unsafe define a wrap, at the site that calls one), so the limb bounds below are not a nicety: each function states what it accepts and what it answers, and f25519Mul says why its sums fit.

Constant time, by construction, and in part by disassembly

Nothing branches on, or indexes by, a secret: the ladder swaps with a mask and runs all 255 steps whatever the scalar, and the final reduction subtracts p by adding a carry bit times 19 rather than by comparing. Every if and every loop bound here is on a public quantity — a limb number, a bit position or an input length.

WP34 N6's disassembly check (tests/ct-asm.js) verifies the part a secret flows through: tests/cases/ct_asm_x25519 holds copies of the field arithmetic, f25519Swap, the encodings and both halves of the ladder, and the check reads each one's clang -O2 machine code for x86-64 and aarch64 and finds no branch on a secret and no load or store at an address the scalar bit or a limb reaches. The rolled loops (the ladder's 255 steps, the inversion's square chains, the encodings) are read whole, back edge included.

They are copies because a case compiles to one module. tests/run.js holds each to this module's text, with the early returns dropped (each guards a public length, but is a branch) and every index unchecked, so a change here that the copies miss fails that check. What stays outside the check is the allocation and wiping around the work in x25519Ladder, f25519Decode and f25519Encode, whose branches are all on public positions. Weekly, tests/ct-timing.js times the fixture's functions on real x86-64 and aarch64 hardware as well.

Loop bounds are literals

A field element is always ten limbs and an encoding always 32 bytes, and each function that indexes one opens with an early return for a shorter array. That cannot happen — every element is made here, and x25519 checks its arguments' lengths before anything else — but it is what lets the compiler prove the loops after it, which count to the literal 10 or 32, in range and drop their bounds checks. (A named constant as the bound, or a panic as the guard, does not prove them.)

Keys are `Secret`s

Keys are Secrets (nish:secret, docs/LANGUAGE.md "Secrets"). x25519 takes the scalar as a Secret<u8[]> and answers the shared secret as one; x25519Base answers the public key as plain bytes. The ladder runs inside exposeWith, and the clamped copy and every ladder element are wiped before it returns (ECC-2, docs/security/crypto-ecc.md).

The field is shared with Ed25519

nish/crypto/ed25519 works over the same GF(p), so the f25519 functions are exported for it to import rather than written twice; they are the module's internals, with the bounds each one states, not an API for programs. Ed25519's square root needs z^(2^252 - 3), which shares its first 250 bits with the inversion's exponent, so that part of the chain is f25519Pow250, which both call.

Names carry the f25519 / x25519 prefix because a std/ module's private functions share the importing program's flat symbol namespace (docs/wp26-stdlib.md §3e).

Functions

x25519

X25519 (RFC 7748 §5): the u-coordinate of scalar * u on curve25519, as 32 little-endian bytes, held as the Secret it is.

scalar is clamped as §5 says — bits 0, 1, 2 and 255 cleared, bit 254 set — on a copy, which is wiped, so the caller's key is not changed. The top bit of u is ignored, and a u of p or more is taken modulo p. The answer is always canonical (below p).

Answers null unless both arguments are exactly X25519_SIZE bytes. An all-zero answer is returned, not refused: it is what a low-order u gives, and RFC 7748 §6.1 leaves checking for it to the protocol. nish/net/tls makes that check on both sides of its handshake; any other caller doing a key exchange must refuse an all-zero answer itself — inside expose, with timingSafeEqual against 32 zero bytes, as the module's example does.

const x25519: (
  scalar: Secret<u8[]>,
  u: u8[],
) => Secret<u8[]> | null
scalarSecret<u8[]>required

The private key, 32 bytes, clamped on a copy.

uu8[]required

The peer's u-coordinate (its public key), 32 bytes.

returnsSecret<u8[]> | null

The shared secret, 32 bytes and possibly all zero, or null for an argument of the wrong length.

x25519Base

x25519(scalar, 9): the public key for the private key scalar, since 9 is curve25519's base point (RFC 7748 §4.1, §6.1), and public, so plain bytes. Answers null unless scalar is X25519_SIZE bytes.

const x25519Base: (scalar: Secret<u8[]>) => u8[] | null
scalarSecret<u8[]>required

The private key, 32 bytes.

returnsu8[] | null

The public key, 32 bytes, or null for a key of the wrong length.

Constants

32

X25519_SIZE: i32

The length in bytes of a scalar, a u-coordinate and an X25519 output.