Last updated: 2026-11-15
Constant-Time Arithmetic and the --constant-time Check
For new readers
A program that computes with a secret key can give the key away through how long it takes, even when it never prints it. PatLang 2.0 answers this at two levels. Its integers modulo n promise that every operation's time depends on the modulus alone, never on the secret value; and the compiler has a mode that reads a whole program and reports every place where its timing could still depend on a secret. With both in place, X25519 key exchange and Ed25519 signatures are written in PatLang and pass the standard test vectors.
Kocher showed in 1996 that measuring how long private-key operations take can reveal fixed Diffie-Hellman exponents and RSA keys1. The usual defence is to write cryptographic code so that its sequence of operations, the memory it touches and the branches it takes are the same whatever the secret is. Doing that by hand is easy to get wrong, and a compiler that rewrites arithmetic can quietly undo it. PatLang builds the property into one class, modint, and checks the rest of the program against it. The arithmetic of the class itself is covered in Numbers in PatLang 2.0.branch timing leaks bits of the secret
What the language promises FoundationalKnowledge that endures for decades โ core principles
A modint's residue is secret, and its modulus is not. Section 1.14 of the specification states:
+,-,*,/, unary-,==,!=, the bit operators,rotlandrotron modints of modulus n take time that depends on n alone, never on the residues. The inverse behind/is found in a number of steps fixed by n.pow(m, k)takes time that depends on n, on the sign of k and on the size of its representation (64 bits for an int, its number of limbs for a bigint), never on the bits of k.mod_makeof a modint takes time that depends on the two moduli alone.- Whether the program stops, on a missing inverse or a shift count out of range, may depend on the values.
- Converting between modints and other values, by
mod_makeof an integer,mod_valueor printing, may take time that depends on the value converted. Those are the points where a secret enters or leaves the class.
How the runtime keeps the promise Applied / MethodologicalKnowledge with a 5โ10 year half-life โ stable practice
A modint's block holds its residue as fixed-width 32-bit limbs, after a header worked out from n when the value is made. The number of limbs depends on n alone, so every loop over them runs the same number of times for every residue, and every choice inside a loop is made with a mask, never a branch. The reduction depends on the shape of n:branchless code runs in constant time
| Modulus | Multiplication | Inversion |
|---|---|---|
| Odd n | Montgomery multiplication2 | The binary algorithm GMP uses in mpn_sec_invert, in 2ย รย bits(n) steps |
| n = 2k | A mask of the low k bits | Newton's iteration |
| Any other even n | A fixed shift-and-subtract reduction | The two methods above, joined by the Chinese remainder theorem |
pow is a ladder over the exponent's limbs, doing the same multiplications whatever each bit is.
Most of a modint operation's time was once spent checking that its two operands shared a modulus: two values each made by mod_make(x, n) held separate bigints for n, and comparing them took 13 of the 24 microseconds an addition modulo 2255ย โย 19 took. The runtime now compares the header words and limbs already in the two blocks. An addition takes about 7.5 microseconds, a multiplication about 11, and one X25519 key agreement about 95 milliseconds, down from 174.
The check FoundationalKnowledge that endures for decades โ core principles
v2.exe SRC.patlang --constant-time
The command builds nothing. It follows every function the program can reach, the runtime's included, in the IR as it stands before the ownership stage, and reports each place where the time taken can depend on a modint's residue. Each report is one line naming the function and what it does with the secret. With none, it prints v2: no value-dependent branch or access and exits 0; with any, it exits 1.
Two versions of one secret-exponent power show the difference. The first multiplies only when the exponent's bit is 1:
make a function called leaky_pow takes g, exponent returns acc
require (type_of(g) == "modint") and (list_len(exponent) == 32)
let acc = mod_make(1, g)
let i = 255
while i >= 0 do
let acc = acc * acc
if cv_bit(exponent, i, g) == 1 then
let acc = acc * g
end
let i = i - 1
end
ensure mod_modulus(acc) == mod_modulus(g)
return acc
end
v2 constant-time: leaky_pow: a branch decides on a secret
v2 error: 1 places where the time can depend on a modint's residue
The second multiplies on every step, by 1 + bit * (g - 1), which is g when the bit is 1 and 1 when it is 0:
make a function called clean_pow takes g, exponent returns acc
require (type_of(g) == "modint") and (list_len(exponent) == 32)
let acc = mod_make(1, g)
let i = 255
while i >= 0 do
let bit = cv_bit(exponent, i, g)
let acc = acc * acc * (1 + bit * (g - 1))
let i = i - 1
end
ensure mod_modulus(acc) == mod_modulus(g)
return acc
end
v2: no value-dependent branch or access
Both take the exponent's bits as modints, from the curve library's cv_bit, so the bit itself is secret and the leaky version's if branches on it.branch timing reveals bits
What it follows
- Secrets. A modint's residue is secret. So is a word read from a modint's block, or from any block a secret was stored in, and any value computed from a secret. The modulus, and what the runtime computes from it alone, is public. A call is followed with its arguments' secrecy, so a function is reported only where a secret actually reaches it.
- Classes and small values. For each value the check knows the classes it may have and, for a bool or a small int, the values it may hold, and it follows only the instructions those allow. A test of a modint's class therefore does not lead it into the string or list code beside it.
- One pass per kind. A call whose argument may be of several classes is followed once for each kind (an int, a modint, a value that holds values, anything else), each with the secrecy that kind can carry, so a callee's
requirerules out the kinds it does not take. - Marks from the runtime. Three primitives that do nothing at run time,
ct_secret,ct_publicandct_reveal, mark what the IR cannot show: where a modint's block is made, what is computed from the modulus, and a residue leaving the class. Freeing memory reads only the block's size, and is marked public. The compiler keeps no list of runtime function names for any of this. - Lists. A list's length, count and room, and an element's type word, are public, since they depend on how the list was used and not on a residue.
What it reports
- A branch (
if,while,and,or,match) deciding on a secret, except one whose one side stops the program. - An address computed from a secret, as a list, string or memory index.
+,-,*,/,%or unary-on a secret integer, whose time depends on whether the result leaves theintclass.- The machine's division on a secret.
- A secret passed to a closure call or an external function, which the check cannot follow.
mod_valueor printing of a modint, where the residue leaves the class.
What it does not know
An element read from a list, a vec or another cell is known only as some value, of any class. Arithmetic on it might be string or list arithmetic as far as the check can tell, and a secret reaching that code is reported. A program settles an element's class by reading it through mod_make(x, shape), whose require admits only integers and modints; the SHA-512 and Curve25519 libraries do this. Lists of lists of secrets are still reported.
That rule came from the check's first run on the curve library, which produced hundreds of reports over an hour, all from values read out of lists. Three changes brought it to about four minutes and none: marking list headers public, following each kind of argument separately, and reading elements through mod_make. Tracking which classes each block held, tried first, made eight times as many summaries and still lost the classes. On the small examples above the check takes about 160 seconds, most of it following the runtime's public code. Since the interpreter runs the same runtime routines, a program's modint operations are covered on both engines.
Cryptography written in PatLang Applied / MethodologicalKnowledge with a 5โ10 year half-life โ stable practice
Two libraries in self_hosting/v2/lib/ are written on modints with no choice made by a secret:
sha512.patlang: SHA-512 on words modulo 264, checked against the FIPS 180-4 digests3.curve25519.patlang: X25519 by the Montgomery ladder of RFC 77484, and Ed25519 key making, signing and verifying by RFC 80325, in extended coordinates. Every scalar bit is a modint, and the ladders pick their points by arithmetic on it.
| Test | Result |
|---|---|
| RFC 7748's X25519 outputs and its 1,000-iteration case | Pass |
| RFC 7748's 1,000,000-iteration case | Pass: k ends as the RFC's 7c3911e0โฆ665424, on 14 November 2026, three days after the run started, at about 180 ms an iteration with a checkpoint every 1,000 |
| All 518 X25519 cases from Project Wycheproof | Pass |
| RFC 8032's keys and signatures | Pass |
| Wycheproof's Ed25519 verification cases | 117 valid accepted, 64 invalid rejected, the 29 marked acceptable all accepted |
--constant-time on X25519, Ed25519 key making and signing | No value-dependent step |
The million-iteration tool saves k, u and the count to two files in turn and resumes from the later valid one. A run stopped at 2,000 and resumed reaches the same k at 3,000 as a run straight through, which is what makes a multi-day run of a test vector worth starting.
Attacking what was built Applied / MethodologicalKnowledge with a 5โ10 year half-life โ stable practice
self_hosting/v2/examples/ has programs that use these libraries to attack two protocols. v2 has no random source yet, so keys come from a hash of a fixed phrase and every run prints the same thing.
handshake_attacks sets up Alice and Bob, who have pinned each other's Ed25519 identity keys and agree a session key over X25519, each signing the two ephemeral keys and their own role name. Mallory controls the wire.
| Attempt | Outcome |
|---|---|
| A man in the middle when nothing is signed | Succeeds: Mallory holds both session keys |
| The same with signatures | Refused: Bob signed the keys he saw, which are not the ones Alice saw |
| Bob's reply replayed from an earlier handshake | Refused: it signs the old ephemeral key |
| Alice's own signature reflected back as Bob's | Refused, because the role name differs |
| A public key of small order | X25519 gives all zeros for every secret key, and the handshake refuses a zero shared secret |
| An outsider without the group's bootstrap secret | Shares a key with Alice, then fails the HMAC-SHA-256 key confirmation that mixes the secret in |
trust_attacks runs the package-trust checks from Packages, resolution and trust with this Ed25519 as the verifier. Mallory makes fifteen attempts to get a trojan release installed, and each is refused with the error the design names for it, from manifest-mismatch and bad-signature to revoked and epoch-mismatch, with two exceptions. A signature with the group order L added to S is among those refused, since the verifier requires Sย <ย L as RFC 8032 section 5.1.7 says. The exceptions sit where the design already places its trust: a counterfeit group, refused by a consumer who pinned the real group's genesis hash but accepted by one who pins on first use; and a release signed with a leaked key, backdated to before the key's revocation, alongside a genuine member's signature.see how trust is established in packages
See also
Integers modulo n covers the class's arithmetic. Packages, resolution and trust covers the trust design these libraries were written for, and the choice it leaves open between PatLang's own verifier and the operating system's. The v2 IR and its readers describes the IR the check reads.
Kocher, P. C. (1996). Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems. In N. Koblitz (Ed.), Advances in Cryptology โ CRYPTO '96 (Lecture Notes in Computer Science, Vol. 1109, pp. 104โ113). Springer. https://doi.org/10.1007/3-540-68697-5_9 โฉ
Montgomery, P. L. (1985). Modular multiplication without trial division. Mathematics of Computation, 44(170), 519โ521. https://doi.org/10.1090/S0025-5718-1985-0777282-X โฉ
National Institute of Standards and Technology. (2015). Secure Hash Standard (SHS) (FIPS PUB 180-4). U.S. Department of Commerce. https://doi.org/10.6028/NIST.FIPS.180-4 โฉ
Langley, A., Hamburg, M., & Turner, S. (2016). Elliptic curves for security (RFC 7748). Internet Engineering Task Force. https://doi.org/10.17487/RFC7748 โฉ
Josefsson, S., & Liusvaara, I. (2017). Edwards-curve digital signature algorithm (EdDSA) (RFC 8032). Internet Engineering Task Force. https://doi.org/10.17487/RFC8032 โฉ
Graduate Attributes
Directly developed
- Critical Thinker: Readers compare two code implementations to see how one leaks timing information while the other avoids it.
- Digitally Fluent: Readers interpret compiler output to identify specific functions where secret-dependent timing occurs.
Modelled on this page
- Subject Specialist: Technical details of limb masking and header comparison explain how constant-time arithmetic is achieved.
- Researcher: Performance metrics and iteration counts are provided to substantiate claims about execution speed.
- Reflective: The evolution of the check tool is described through failed attempts and the reasons for discarding them.
University of Reading Graduate Attributes framework.