ba-cybersecurity.comResearch by Nobuo Otoi

The problem

CA/Browser Forum servercert pull request #683 (draft ballot, 22 Oct 2026) adds to Section 6.1.6 of the TLS Baseline Requirements the requirement that a CA "ensure that the public key does not correspond to a Private Key whose private scalar is less than 256". It follows the eMudhra incident (Mozilla Bugzilla 2083449), in which certificates were issued for keys whose private scalar was a small integer, recoverable by comparing the public key with k·G for k = 1..255.

"Less than 256" describes integers, not the keys that search finds. For every k in 1..255 two further scalars are recovered at the same cost, at most 255 group operations, and neither is less than 256: d = n − k, whose public key −k·G has the same x-coordinate as k·G, and d = k⁻¹ mod n, whose public key Q satisfies k·Q = G. A CA that applies the sentence as written accepts both.

How it was shown

Both families were built from the eight real eMudhra public keys and checked against the sentence: the x-only search recovers the scalars 4, 56, 66, 115, 155, 156, 230 and 237, and for each of them the keys n − k and k⁻¹ mod n pass the draft sentence yet are recovered in at most 255 operations. A self-contained Python script reproduces every number (python3 verify.py, about two seconds, no dependencies).

A one-sentence replacement was proposed: neither the private scalar d nor n − d is less than 2^16, and no integer k less than 2^16 satisfies k·Q = ±G. The bound 2^16 matches the default of zlint's lint and costs about the same as the draft's check; the three clauses reject at most 4·(2^16 − 1) of the n − 1 possible scalars, so an honestly generated key is rejected with probability below 2^−366.

In Lean 4 (core library only; axioms propext and Quot.sound; no sorry) the scalar clause is proved to hold exactly for the keys an x-only search of that size recovers, and the draft clause is shown to be a strict special case. The negation family is already handled by zlint's e_ecdsa_small_private_key lint; the ballot text, which is what a CA is audited against, does not say so, and the inverse family was covered by no text or linter checked (zlint, paranoid_crypto, badkeys, pkilint, pkimetal, as of 5 Nov 2026).

Check it by hand

CA/B servercert PR #683 · Bugzilla 2083449 · verify.py

Response

The observation and the proposed sentence were posted as a comment on the ballot pull request on 5 Nov 2026 (JST), with the preprint and the proof. The same day, the Server Certificate Working Group replied that under the Forum's IPR rules it can only entertain such suggestions from members or interested parties, and pointed to the interested-party process. Another Forum participant replied that these keys are indeed as easy to attack, but that in their view the Baseline Requirements should require checks only for failure scenarios seen in the real world, and that no key of either family has been seen outside security exercises.

As of 6 Nov 2026 the pull request is open and the draft sentence is unchanged.

Links