Pohlig–Hellman and the smooth-order reduction
Pohlig–Hellman is the reason a curve order is published as h · n with n prime, and the reason a protocol that skips point validation can be broken by an attacker who simply hands it the wrong curve.
- Problem
- Discrete logarithm in a group of composite, partly smooth order
- Cost
- O(Σi ei(log n + √pi)) for n = ∏ piei
- Requires
- The factorisation of the group order — normally public
- Deployed consequence
- Invalid-curve attacks, small-subgroup confinement attacks
- Defence
- Prime-order subgroup, cofactor handling, point validation
The problem instance
Given P of order n = ∏ piei and Q = kP, recover k. Unlike the setting for rho, the order is not prime, and its factorisation is known — for a standardised curve it is printed in the specification.
The mechanism
The group decomposes by the Chinese remainder theorem, and so does the logarithm. For each prime power piei, project into the subgroup of that order by multiplying through by the cofactor:
Within a prime-power subgroup the logarithm is recovered one pi-adic digit at a time: write k ≡ d0 + d1pi + … and determine each digit by a discrete logarithm in a group of order pi, solved with rho or baby-step giant-step at cost √pi. The total is O(Σ ei(log n + √pi)) group operations.
Why this shapes curve standards
Every standardised curve publishes its group order as h · n, with n a large prime and h a small cofactor: h = 1 for the NIST prime curves and secp256k1, h = 8 for Curve25519, h = 4 for Curve448. Cryptographic operations are confined to the order-n subgroup precisely so that Pohlig–Hellman has nothing to work with.
The cofactor is not free. In a group with h = 8, an attacker who can get a peer to compute with a point of order 8 learns the secret scalar modulo 8. That is only three bits, but it is three bits per protocol run against a static key, and it composes with other leakage. Hence cofactor clearing, or the ristretto255-style construction that removes the cofactor from the abstraction entirely.
Invalid-curve attacks: the real version
The damaging deployed form of this attack does not need the target's curve to have a smooth order — it supplies a different curve that does. Short Weierstrass point arithmetic over Fp for y2 = x3 + ax + b never uses b. So a point that does not lie on the intended curve lies on some other curve with the same a, and the victim's scalar multiplication computes happily in that group.
- The attacker searches for a curve E' with the same a whose order has a small prime factor q, and finds a point R of order q on it.
- The attacker sends R as a public key. The victim computes dR with its long-term secret d and returns or reveals something derived from it.
- Because R has order q, brute force over q candidates yields d mod q.
- Repeat with different small primes until the CRT reconstruction pins down d — typically a few dozen queries.
Real instances have been found in TLS libraries, in Bluetooth pairing, and in JSON Web Encryption implementations. The defence is unglamorous and absolute: validate that a received point satisfies the curve equation, is not the identity, and lies in the correct subgroup, before any secret-dependent arithmetic. Curve models whose arithmetic uses every parameter — Montgomery and twisted Edwards forms — reduce the exposure but do not replace validation, because they leave the twist reachable.
The boundary
On a prime-order curve with validated inputs, Pohlig–Hellman contributes nothing: there is one prime factor and the reduction is the identity. Its residual relevance is entirely in the surrounding engineering — cofactors, twists, missing validation, and protocols that reuse a static key across many attacker-chosen inputs.
It is worth stating what this means for review practice. Asking "is the curve strong?" is the wrong question for this attack class; the right questions are whether every received point is validated, whether the cofactor is cleared, and whether the same private scalar is ever applied to more than a handful of attacker-supplied group elements.
Primary sources
- S. Pohlig and M. Hellman, "An improved algorithm for computing logarithms over GF(p) and its cryptographic significance", IEEE Trans. Inf. Theory 24 (1978)
- I. Biehl, B. Meyer and V. Müller, "Differential fault attacks on elliptic curve cryptosystems", CRYPTO 2000 — the origin of the invalid-curve attack
- T. Jager, J. Schwenk and J. Somorovsky, "Practical invalid curve attacks on TLS-ECDH", ESORICS 2015
- D. J. Bernstein and T. Lange, "SafeCurves: choosing safe curves for elliptic-curve cryptography"