Description

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

Mitigation

Aliases

References