So how *do* you validate (NIST) ECDH public keys?

Updated 20th July 2017 to clarify notation for the point of infinity. A previous version used the symbol 0 (zero) rather than O, which may have been confusing.

Updated 28th May 2020: in step 4 of the full validation check, n is the order of the prime sub-group defined by the generator point G, not the order of the curve itself. This is critical for security if you are performing this check because small-order points will satisfy the order of the curve (which is h * n), but not the order of G.

In the wake of the recent critical security vulnerabilities in some JOSE/JWT libraries around ECDH public key validation, a number of implementations scrambled to implement specific validation of public keys to eliminate these attacks. But how do we know whether these checks are sufficient? Is there any guidance on what checks should be performed? The answer is yes, but it can be a bit hard tracking down exactly what validation needs to be done in which cases. For modern elliptic curve schemes like X25519 and Ed25519, there is some debate over whether validation should be performed at all in the basic primitive implementations, as the curve eliminates some of the issues while high-level protocols can be designed to eliminate others. However, for the NIST standard curves used in JOSE, the question is more clear cut: it is absolutely critical that public keys are correctly validated, as evidenced by the linked security alert.

NIST publishes guidance on approved ECDH (and normal DH) key agreement protocols, including advice on how to validate public keys, in SP 800-56A (revision 2). For ECDH keys it defines two validation procedures:

1. ECC Full Public-Key Validation Routine in section 5.6.2.3.2, and,
2. ECC Partial Public-Key Validation Routine in section 5.6.2.3.3.

The two routines are identical in the first 3 validation steps, but the Full routine includes a 4th check. The full checks (for curves defined over a prime finite field, as is the case for all the JOSE curves) are:

1. Verify that the public key is not the “point at infinity”, represented as O.
2. Verify that the affine x and y coordinates of the point represented by the public key are in the range [0, p – 1] where p is the prime defining the finite field.
3. Verify that y² = x³ + ax + b where a and b are the coefficients of the curve equation. (This is the check that most JOSE libraries implemented).
4. Verify that nQ = O (the point at infinity), where n is the order of the curve order of the sub-group defined by the generator point G, and Q is the public key point.

This last check is relatively expensive (the same cost as the ECDH agreement we want to perform in the first place), which is why there is a partial validation routine that leaves it out. Sections 5.6.2.2.1 and 5.6.2.2.2 describe when each check should be performed. However, for an ECC ephemeral public key, 5.6.2.2.2 says that the recipient can perform either check. This is a bit confusing: if I can perform either check, when should I ever perform the full check?

The story gets a bit convoluted here. As Trevor Perrin points out, SP 800-56A only defines elliptic curve DH primitives for Cofactor Diffie-Hellman (ECC CDH) or ECC MQV (which we won’t discuss here). In both of these primitives it is safe to drop the final check. However, JOSE uses non-cofactor ECDH, in which the cofactor is not involved in the scalar point multiplication. In this form, it is essential that the final step is performed to get full validation. However, the plot takes another twist at this point. Another standard, SEC 1: Elliptic Curve Cryptography from the Standards for Efficient Cryptography Group defines the same steps for public key validation, but includes this note in Section 3.2.2.1:

In Step 4, it may not be necessary to compute the point nQ. For example, if h = 1, then nQ = O is implied by the checks in Steps 2 and 3, because this property holds for all points Q ∈ E.

All of the NIST standard curves used in JOSE define h = 1. It is therefore safe to only perform Partial validation for both static and ephemeral public keys received using the NIST prime field standard curves. Note that in this case the normal ECDH multiplication P = dQ is equivalent to the cofactor DH form, P = hdQ.

Note: for other curves, such as those defined over binary fields, the checks are different! Please verify what checks you need to perform for your chosen primitives.

In short, if you are doing ECDH key agreement with NIST curves, be really careful how you validate public keys that you receive. I recommend a detailed reading of all sections SP 800-56A and the SEC 1 report.

Addendum (18th May, 2017): These checks (or at least some of them) were added to Oracle/OpenJDK 1.6.0_101, 1.7.0_85 and 1.8.0_51 to resolve CVE-2015-2613. You could rely on this, instead of performing the checks yourself (after all, if someone hasn’t patched critical security issues in their JRE for >2 years, will they patch their JWT library?). However, it is still worth performing these checks yourself as JCE is a pluggable architecture, so you may end up using a KeyAgreement implementation that doesn’t do the checks.

For completeness, this is the code I am using (Java) to validate ECDH public keys:

// Step 1: Verify public key is not point at infinity. 
if (ECPoint.POINT_INFINITY.equals(publicKey.getW())) {
    return false;
}

final BigInteger x = publicKey.getW().getAffineX();
final BigInteger y = publicKey.getW().getAffineY();
final BigInteger p = ((ECFieldFp) curveParams.getField()).getP();

// Step 2: Verify x and y are in range [0,p-1]
if (x.compareTo(BigInteger.ZERO) < 0 || x.compareTo(p) >= 0
        || y.compareTo(BigInteger.ZERO) < 0 || y.compareTo(p) >= 0) {
    return false;
}

final BigInteger a = curveParams.getA();
final BigInteger b = curveParams.getB();

// Step 3: Verify that y^2 == x^3 + ax + b (mod p)
final BigInteger ySquared = y.modPow(TWO, p);
final BigInteger xCubedPlusAXPlusB = x.modPow(THREE, p).add(a.multiply(x)).add(b).mod(p);
if (!ySquared.equals(xCubedPlusAXPlusB)) {
    return false;
}

// Step 4: Verify that nQ = 0, where n is the order of the curve and Q is the public key.
// As per http://www.secg.org/sec1-v2.pdf section 3.2.2:
// "In Step 4, it may not be necessary to compute the point nQ. For example, if h = 1, then nQ = O is implied
// by the checks in Steps 2 and 3, because this property holds for all points Q ∈ E"
// All the NIST curves used here define h = 1.
assert curve.getParameters().getCofactor() == 1;