Brief

In early 2025, while working on a project which required us to perform a broad audit of OSS elliptic curve implementations – we discovered several cryptographic issues in Cloudflare's CIRCL library – specifically with the implementation of the FourQ elliptic curve.

We reported the issues through Cloudflare's HackerOne bug bounty plan in March 2025, and subsequently contacted Cloudflare directly, after having received a lukewarm and laconic response from the HackerOne triage team.

Once the team at Cloudflare stepped in the issues were appropriately acknowledged and fixed.

FourQ, Cloudflare's CIRCL

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

FourQ is an elliptic curve with 128-bit security, developed by Microsoft Research and is 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 nonresidue in \(F_{p^2}\).

Simply put, much like 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 in the integers\(\mod p\).

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

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

Invalid point attacks

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

This type of attack is often called an invalid curve or invalid point attack, and stems from insufficient validation of the points used to perform the calculation.

Elliptic Curve Diffie-Hellman or ECDH involves each side taking a secret scalar \(k\) and multiplying it with a fixed generator point \(G\) to compute the point \(Q = k*G\). Each side transmits its \(Q\) point, and receives the other side's \(Q\) point, multiplying it by his own \(k\) scalar. Since scalar multiplication in elliptic curves is commutative – both sides will 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 as input a public point (P) and a secret scalar, 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. The reason is that in order 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 amount of points on the curve.
Put more clearly – if we consider a point being added to itself a "step", then every point on the curve should have the same amount of "steps" required to lead back to the identity point, or the "starting" point.

Meaning if one multiplies a certain point \(Q\) by the secret scalar \(k\), if the point is valid and on the expected curve, the result should land in any of the \(N\) points on the curve. For the curve to be considered secure, it must have an order \(N\) which is either a prime number, or composed from a large prime number and a small cofactor.

This is what makes the discrete logarithm problem difficult with regards to scalar multiplication, thus creating a "trap-door" function where it is easy to perform the multiplication, but hard to reverse it.

If an attacker is able to force the server to perform the scalar multiplication of his secret \(k\) with an invalid point \(\widehat{Q}\) which is not on the curve – he may choose \(\widehat{Q}\) such that it belongs to a curve with a smooth (composed of many small factors) subgroup order \(\widehat{N}\).

As a result – instead of \(k*Q\) computing any possible point on the original curve, it will instead land in any of a smaller set of points.
For instance, the subgroup order of \(\widehat{Q}\) is only 400 points, the attacker will be able to trivially brute-force 400 values of \(k\) to find the server's secret \(k\) value, modulo 400.

If repeated for multiple invalid points, with different subgroup orders, and in combination with the Chinese Remainder Theorem, the attacker will eventually be able to extract the server's secret \(k\) value.

Degenerate curve attacks on Edwards curves

The above attack is applicable on a form of elliptic curves called Weierstrass curves. While Edwards curves are birationally equivalent to Weierstrass curves, meaning a curve such as FourQ may be represented using Weierstrass formulas – the invalid curve attack as presented in the previous section does not generalize to Edwards curve.

The reason for this is that while addition using the Weierstrass formulas is independent of the curve parameters, Edwards addition formulas are dependent on both curve parameters \(a\) and \(d\), which makes it impossible (or more accurately very difficult) to pass arbitrary points, i.e. points which are not on the curve and have the server perform addition on them correctly.

If we take a closer look at the Edwards addition formula, we see that the curve parameters (\(a\) and \(d\)) are coefficients of the \(x\) variable – meaning if we affix \(x\) to 0, the curve parameters cancel out and we are left with a less generalized invalid point attack which does work on all Edwards curves.

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

CVE-2015-8556

In consideration of the invalid curve attacks presented above, the main adversarial threat to ECC implementation lies with performing computations on invalid points – points which are not on the graph. As such – points should always be validated before being relied upon for any computation.

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

For added security – the point should also be validated before being used in any of the basic computations – addition, doubling/scalar multiplication.

While auditing CIRCL's FourQ implementation we pinpointed 7 total issues related to these security primitives, as well as to the testing code – which incorrectly demonstrated some security proofs.

Below is a short description of the 4 major points we raised, and were to some extent addressed by the fixes to CIRCL.

Incorrect point validation in Point.Unmarshal

The issue here is a missing step – the IETF spec for FourQ accounts for some ambiguity in the unmarshalling process by conjugating the point's \(x\) value – if not the unmarshalled point nor its conjugate are valid points on the curve – the unmarshalled point is invalid.

The IETF spec contains 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 the point being 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

The CIRCL code, as per the IETF spec, uses several representations of projected coordinates – this means that in addition to the \(x\) and \(y\) value, each point also has an additional \(Z\), \(Ta\) and \(Tb\) values, where \(Z * Ta * Tb \equiv x * y\).

The issue here is that if \(Z\) is set to 0 – which is invalid in the context of the projected representation – the isEqual check always returns true.

Several checks in the code were affected by the issue, including faulty tests.

Lack of point validation in pointR1.ClearCofactor

Since the FourQ curve has a cofactor of 392 – meanings its order is not a prime number but rather a prime number multiplied by 392 – in order to ensure that the point being used for computation is an \(N\)-torsion point, the cofactor must be cleared by multiplying the point by 392 prior to any additional scalar multiplications.
If we end up with the neutral point as a result of clearing the cofactor – 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 that the projected values are valid, and that the point is indeed on the curve.
As a result of the previous issue with unmarshalling, it's as possible to load a point which isn't on the curve, and then perform computations on it, which exposes the implementation to the degenerate curve attacks described above.

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

References