GHSA-q97c-8qh3-fpc6

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).

## 7. 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: geostergiop@aueb.gr | s: https://www.aueb.gr/en/faculty_page/stergiopoulos-georgios