phpseclib — non-constant-time X25519 scalar multiplication permits full private-key recovery

The pure-PHP X25519 scalar multiplication in phpseclib is not constant-time. Field addition and subtraction each perform a data-dependent conditional modular reduction, so the cost of each Montgomery-ladder step is a linear function of that step's reduction count which is a quantity determined by the secret scalar's prefix.

An observer with per-ladder-step resolution recovers the 251-bit clamped private scalar. This is a per-step leak, not an aggregate one: an instrumented code proof-of-concept recovers 20/20 test keys from 32 observed operations, and an observer that counts libgmp calls instead of timing them recovers a key from a single operation.

This is not a low-order-input issue. Recovery works with the RFC 7748 base point u = 9, with no attacker-chosen input at all. Rejecting low-order public values does not close it.

2. Affected component

Confirmed on phpseclib 3.0.56 (338 files under phpseclib/,sha256(sorted(relpath NUL file_sha256 LF)) = cc7250b611f520e809131aab0931503457c44d8cbfb10d535251c6fec5f62a2b). The code appears unchanged across the 3.0 series wherever Curve25519 is supported, please confirm the affected range.

file:line	role
Math/PrimeField/Integer.php:189	add() — conditional subtract($modulo) when the sum ≥ p
Math/PrimeField/Integer.php:207	subtract() — conditional add($modulo) when the result is negative
Crypt/EC/BaseCurves/Montgomery.php:229–234	ladder branch on the secret bit, selecting argument order of doubleAndAddPoint
Crypt/EC/Formats/Keys/MontgomeryPrivate.php:66	multiplyPoint(getBasePoint(), dA) — no engine check of any kind
Crypt/EC/Formats/Keys/PKCS8.php:194–200	the same derivation, correctly gated on ext-sodium — the pattern MontgomeryPrivate is missing

3. Technical description

Operation counts in the ladder are already constant — 10 field multiplications, 4 additions and 4 subtractions per step, 2560 multiplications per 256-step ladder. Operand values are not. Each PrimeField\Integer::add() / subtract() takes a data-dependent branch costing ~0.85–1.0 µs on the GMP engine, against a ~32 µs step period, so per-step cost is α + β·c where c is that step's conditional-reduction count. Measured across 20 keys: R² = 0.91–0.98, β = 838–920 ns.

c depends on the whole scalar prefix, not on the current bit, so per-step thresholding is useless — it saturates at ~93% per bit for u = p−1 and at chance for u = 9, and recovers 0/20 keys either way, because the bit string is a prefix-XOR in which one flipped step inverts the entire tail. Conditioning on the prefix removes the ambiguity: a beam search replays both branches from each candidate ladder state, reads off the exact c for each, and scores against the observation. The victim's public key adjudicates the small residual search.

Two facts bound the problem and are worth stating precisely, because they determine whether a fix is needed at all:

• Aggregate observation is provably useless. The adjacent-bit transition count T(k) has exact entropy H(T) = 4.0357 bits over clamped scalars, so a noiseless transition-count oracle still leaves ~2^247 candidates. The summed reduction count Σc is richer (~6.6–6.9 bits) and still leaves ~2^244. Any measurement that collapses the call to one number is safe. Per-step measurement is not.
• The libgmp call counts are exactly determined. Per ladder step, __gmpz_add = 4 + csub, __gmpz_sub = 4 + cadd, __gmpz_mul = __gmpz_mod = 10. Verified by differencing gdb breakpoint counts against phpseclib's own doubleAndAddPoint — 27/27 steps exact, extended independently to 64/64 and 38/38 by our two reviewers. An observer that only counts these calls needs no timing, no calibration and no repetition.

Results, 20 keys × 3 sampling seeds, 800 traces per path collected from 800 distinct PHP processes (so the observations are cross-process, as real requests would be):

observer	path	observations needed	exact 251-bit recovery
timing	key load, u = 9	32	20/20 keys, 95% CI [83.9%, 100%]
timing	ECDH, u = p−1	32	18/20 keys, 95% CI [69.9%, 96.8%]
timing	either	8	18–23% of trials
libgmp call counts	either	1	20/20 keys; tolerates 20–30% of per-step counts being wrong

The model underlying the decoder is validated against the pinned implementation: 254/254 (key, peer) outputs match the real DH::computeSecret, and all four RFC 7748 §6.1 vectors match both phpseclib and the published constants.

Negative controls are clean — wrong public key, shuffled trace, wrong peer value, foreign key: 0/20 in every case. Nothing derived from the private key reaches the decoder; its inputs are the observation vector, the peer value, the victim's public key, and the public clamping constants.

5. Impact

In the instrumented, local model, recovery of the clamped scalar gives a permanent compromise of the X25519 private key. Clamping is applied on every call, so the recovered value is what every past and future operation with that key uses.

6. Restrictions

Required for exploitation:

1. A reused / long-lived X25519 private key. Ephemeral X25519 — the normal TLS and SSH case — defeats this outright. phpseclib's own SSH path generates a fresh scalar per exchange and is not affected.
2. Knowledge of the victim's public key. It adjudicates the decoder's residual search; without it no candidate can be selected. This is normally public, but it is a precondition, not a convenience.
3. The pure-PHP path must actually run. Measured across four extension configurations:
   • EC::loadFormat('MontgomeryPrivate', $raw32) runs the ladder in every configuration — but the format declares IS_INVISIBLE (MontgomeryPrivate.php:40), so PublicKeyLoader::load skips it and nothing inside phpseclib calls it. An application must name the format explicitly.
   • PKCS8 / PublicKeyLoader::load / EC::createKey run the ladder only when ext-sodium is absent — PKCS8.php:194 gates on sodium_crypto_box_publickey_from_secretkey. OpenSSL does not help here.
   • DH::computeSecret runs the ladder only under EC::forceEngine('PHP'), or when both openssl_pkey_derive (DH.php:325) and sodium_crypto_scalarmult (EC/PrivateKey.php:75) are unavailable. ext-sodium is bundled and enabled by default in PHP 7.2+, so the reachable configurations are a minority — though disable_functions hardening and --disable-sodium builds do occur, particularly in shared hosting.
4. An observer with per-ladder-step resolution, i.e. one that can distinguish ~0.9 µs within a ~32 µs step, or count libgmp entry-point calls. In practice that means local co-residency (e.g. a Flush+Reload spy on the shared libgmp.so mapping — __gmpz_add / __gmpz_sub are the correct targets; __gmpn_* are not, being size-dispatched internals).

Not demonstrated — stated so it is not found rather than disclosed:

• We did not build a co-resident spy. Per-step observations in the PoC come from a small hrtime() hook inside Montgomery::multiplyPoint (one file differs from the pinned tree; Math/PrimeField/Integer.php, which carries the leak, is byte-identical). This models an observer with intra-call resolution; it is not itself an attacker capability. We note that the requisite primitives are present on ordinary hardware — on our test host clflush and rdtscp work, with 187–312 cycle cached/flushed separation — but building and validating a spy is separate work we have not done.
• Perfect step segmentation is assumed. A real observer must recover step boundaries and separate the ladder from the surrounding modular inversion.
• A single host and configuration. All timing figures are from one 2-vCPU shared VM (PHP 8.3.6, GMP 6.3.0). A noisier host needs more observations; recovery holds within roughly 25–30% additional noise beyond this host's residual.
• We have not identified an affected deployed caller.

Accordingly we report this as a hardening issue and demonstrated side channel, not as a completed remote exploit.

8. Suggested remediation

1. Constant-time, fixed-width field arithmetic, or delegate to a vetted native provider. This is the actual fix. Removing the ladder's bit branch is not sufficient while Integer.php:189 and :207 remain operand-dependent.
2. Gate MontgomeryPrivate.php:66 the way PKCS8.php:194–200 already is. That is a one-block change and it closes the only entry point that is un-gated in every configuration. Keep the $curve instanceof Curve25519 guard — MontgomeryPrivate also accepts Curve448 keys.
3. Consider an OpenSSL arm alongside the sodium arm in PKCS8::loadECDH, or fail closed, so stacks without ext-sodium do not fall through to the ladder.
4. Separately, and unrelated to this channel: the pure-PHP path returns an all-zero 32-byte shared secret for low-order peer inputs. Rejecting the full canonicalised low-order set and adding a constant-time all-zero check is correct hygiene for contributory behaviour — but it does not mitigate the timing channel, since recovery works with u = 9.

Contact

George Stergiopoulos Assistant Professor of cybersecurity Athens University of Economics and Business, Greece E: [email protected] | s: https://www.aueb.gr/en/faculty_page/stergiopoulos-georgios