CVE-2025-8556 — Cryptographic Issues in Cloudflare’s CIRCL FourQ Implementation

FourQ, Cloudflare’s CIRCL

CIRCL, Cloudflare’s cryptography library, offers a basic implementation of the FourQ curve, as well as a Diffie-Hellman implementation named Curve4Q that provides shared-secret functionality.

FourQ is an elliptic curve with 128-bit security, developed by Microsoft Research and defined by a twisted Edwards curve equation.

The curve is defined over a two-dimensional extension of the prime field defined by the Mersenne prime $p=2^{127}-1$, the curve twist parameter $a=-1$ and $d$ set to a quadratic non-residue in $F_{p^2}$.

Simply put — much as the complex numbers are an extension field of the real numbers, the FourQ curve is defined over an extension of a prime field, its elements being of the form $a+bi$ where $a$ and $b$ are integers $modp$.

In addition, the FourQ curve defines two endomorphisms — structure-preserving functions — which serve as “shortcuts” to perform computations on the curve more efficiently.

These endomorphisms, along with the curve’s other characteristics, make it fast and suitable for use-cases where computational resources are scarce, such as embedded systems.

Invalid point attacks

A certain class of attacks on elliptic-curve implementations lets an attacker force the server to perform a calculation that discloses information about the secret key used.

This kind of attack is often called an invalid-curve or invalid-point attack, and stems from insufficient validation of the points used in the calculation.

Elliptic-Curve Diffie-Hellman (ECDH) involves each side taking a secret scalar $k$ and multiplying it by a fixed generator point $G$ to compute the point $Q=k\cdot G$. Each side transmits its $Q$ point and receives the other side’s, multiplying it by its own $k$ scalar. Since scalar multiplication on elliptic curves is commutative, both sides end up with the same point.

// Shared calculates a shared key k from Alice's secret and Bob's public key.
// Returns true on success.
func Shared(shared, secret, public *Key) bool {
    var P, Q fourq.Point
    ok := P.Unmarshal((*[Size]byte)(public))
    Q.ScalarMult((*[Size]byte)(secret), &P)
    Q.Marshal((*[Size]byte)(shared))
    ok = ok && Q.IsOnCurve()
    return ok
}

An example from CIRCL’s Curve4Q implementation (pre-remediation) shows a shared secret being calculated by taking a public point (P) and a secret scalar as input and multiplying them.

The issue arises when the computation is done without first verifying that the other side’s point is a valid point on the curve. To be secure, all points on an elliptic curve must be members of an $N$-torsion subgroup, where $N$ is the order of the curve — the total number of points on it. Put more clearly: if we consider a point being added to itself a “step”, then every point on the curve should take the same number of steps to lead back to the identity point.

So if one multiplies a certain point $Q$ by the secret scalar $k$, and the point is valid and on the expected curve, the result should land on any of the $N$ points of the curve. For the curve to be considered secure, its order $N$ must be either prime or the product of a large prime and a small cofactor.

This is what makes the discrete-logarithm problem hard with respect to scalar multiplication, creating a “trap-door” function: easy to perform the multiplication, hard to reverse it.

If an attacker can force the server to perform the scalar multiplication of its secret $k$ with an invalid point $\widehat{Q}$ that is not on the curve, they may choose $\widehat{Q}$ so that it belongs to a curve with a smooth (many small factors) subgroup order $\widehat{N}$.

As a result, instead of $k\cdot Q$ computing any possible point on the original curve, it lands on any of a much smaller set of points. If the subgroup order of $\widehat{Q}$ is only 400 points, the attacker can trivially brute-force 400 values of $k$ to find the server’s secret $k$ modulo 400.

Repeated for multiple invalid points with different subgroup orders, and combined with the Chinese Remainder Theorem, the attacker eventually recovers the server’s full secret $k$.

Degenerate-curve attacks on Edwards curves

The attack above applies to a form of elliptic curve called Weierstrass curves. While Edwards curves are birationally equivalent to Weierstrass curves — a curve such as FourQ can be represented with Weierstrass formulas — the invalid-curve attack as presented does not generalize to Edwards curves.

Weierstrass addition ($x_1\ne x_2$):

Edwards addition:

The reason is that while addition with the Weierstrass formulas is independent of the curve parameters, the Edwards addition formulas depend on both parameters $a$ and $d$, which makes it very difficult to pass arbitrary points — points not on the curve — and have the server add them correctly.

Looking closer at the Edwards addition formula, the curve parameters ($a$ and $d$) are coefficients of the $x$ variable. So if we fix $x$ to 0, the curve parameters cancel out and we are left with a less generalized invalid-point attack that does work on all Edwards curves.

Concretely: if we pass in a point of the form $(0,y)$, multiplying it by the secret value $k$ computes $(0,y^k)$. So if we select a $y$ such that the point $(0,y)$ has a small multiplicative subgroup order and receive $(0,y^k)$, solving the discrete-logarithm problem to recover $k$ becomes trivial.

CVE-2025-8556

Given the invalid-curve attacks above, the main adversarial threat to an ECC implementation lies in performing computations on invalid points — points not on the graph. Points should always be validated before being relied upon for any computation.

At minimum, unmarshalling a point — loading a byte-array of the right length and converting it to a point on the curve — should ensure the loaded point is indeed valid, simply by checking that the curve equation holds.

For added security, the point should also be validated before use in any of the basic computations: addition, doubling, scalar multiplication.

Auditing CIRCL’s FourQ implementation, we pinpointed 7 issues related to these security primitives and to the testing code, which incorrectly demonstrated some security proofs. Below are the 4 major points we raised, which were addressed to some extent by the fixes to CIRCL.

Incorrect point validation in Point.Unmarshal

A missing step. The IETF spec for FourQ accounts for ambiguity in the unmarshalling process by conjugating the point’s $x$ value — if neither the unmarshalled point nor its conjugate is a valid point on the curve, the point is invalid. The IETF spec gives the following pseudocode:

if -x^2+y^2 != 1+d*x^2*y^2:   # Check curve equation with x
     x = conj(x)
if -x^2+y^2 != 1+d*x^2*y^2:   # ... or its conjugate
     return FAILED
return P = (x, y)

The CIRCL implementation fails to re-validate that the point is on the curve after conjugating its $x$ value:

if !P.IsOnCurve() {
    fpNeg(&P.X[1], &P.X[1])
}
return true

Faulty point comparison in pointR1.isEqual

Per the IETF spec, the CIRCL code uses several representations of projected coordinates: in addition to the $x$ and $y$ values, each point also carries $Z$, $T_a$ and $T_b$ values, where $Z\cdot T_a\cdot T_b\equiv x\cdot y$.

The issue: if $Z$ is set to 0 — invalid in the projected representation — the isEqual check always returns true. Several checks in the code were affected, including faulty tests.

Lack of point validation in pointR1.ClearCofactor

Since the FourQ curve has a cofactor of 392 — its order is not prime but a prime multiplied by 392 — to ensure the point used for computation is an $N$-torsion point, the cofactor must be cleared by multiplying the point by 392 before any further scalar multiplications. If clearing the cofactor yields the neutral point, the input point is invalid.

The CIRCL implementation deviates from the spec by failing to perform this verification after clearing the cofactor.

Lack of point validation in pointR1.ScalarMult

The scalar-multiplication implementation on pointR1 assumes the projected values are valid and that the point is indeed on the curve. As a result of the previous unmarshalling issue, it’s possible to load a point that isn’t on the curve and then compute on it, exposing the implementation to the degenerate-curve attacks described above.

Fixing the unmarshalling issue prevents this, as does the change to the Curve4Q code that performs the DH computation. Still, to conform with more stringent security measures, it would be advisable to validate that the input point is on the curve before performing the scalar multiplication.

References

• eprint.iacr.org/2015/1233.pdf
• ietf.org/archive/id/draft-ladd-cfrg-4q-01.txt
• eprint.iacr.org/2015/565.pdf