The security level of an elliptic curve cryptosystem is determined by the cryptanalytic algorithm that is the least expensive for an attacker to implement. There are several algorithms to consider.
prime-order: shank's baby step giant step, pollard rho, pollard kangaroo/lambda,
non-prime order: Pohlig-Hellman
The order m of the elliptic curve is divisible by the order n of the group associated with the generator; that is, for each elliptic curve group, m = n * c for some number c. The number c is called the "cofactor". [...] It is possible and desirable to use a cofactor equal to 1.
When the cofactor of a group is not equal to 1, there are a number of attacks that are possible against ECDH. See VW1996, AV1996, and LL1997.
bad public keys:
The elliptic curve group operation does not explicitly incorporate the parameter b from the curve equation. This opens the possibility that a malicious attacker could learn information about an ECDH private key by submitting a bogus public key BMM2000. An attacker can craft an elliptic curve group G' that has identical parameters to a group G that is being used in an ECDH protocol, except that b is different. An attacker can submit a point on G' into a run of the ECDH protocol that is using group G, and gain information from the fact that the group operations using the private key of the device under attack are effectively taking place in G' instead of G.
on verifying public keys:
This sort of attack is thwarted if an ECDH implementation does not assume that each pair of coordinates in Zp is actually a point on the appropriate elliptic curve.
point compression doesn't thwart this attack?
These considerations also apply when ECDH is used with compact representation
security levels:
The ~224-bit security level of curve448 is a trade-off between performance and paranoia. Large quantum computers, if ever created, will break both curve25519 and curve448, and reasonable projections of the abilities of classical computers conclude that curve25519 is perfectly safe. However, some designs have relaxed performance requirements and wish to hedge against some amount of analytical advance against elliptic curves and thus curve448 is also provided.
contributory behavior:
Protocol designers using Diffie-Hellman over the curves defined in this document must not assume "contributory behaviour". Specially, contributory behaviour means that both parties' private keys contribute to the resulting shared key. Since curve25519 and curve448 have cofactors of 8 and 4 (respectively), an input point of small order will eliminate any contribution from the other party's private key. This situation can be detected by checking for the all- zero output, which implementations MAY do, as specified in Section 6. However, a large number of existing implementations do not do this.
Both MAY check, without leaking extra information about the value of K, whether K is the all-zero value and abort if so (see below). Alice and Bob can then use a key-derivation function that includes K, K_A, and K_B to derive a symmetric key. The check for the all-zero value results from the fact that the X25519 function produces that value if it operates on an input corresponding to a point with small order, where the order divides the cofactor of the curve (see Section 7). The check may be performed by ORing all the bytes together and checking whether the result is zero, as this eliminates standard side-channels in software implementations.
weird call out, perhaps directed to SAS protocols:
Designers using these curves should be aware that for each public key, there are several publicly computable public keys that are equivalent to it, i.e., they produce the same shared secrets. Thus using a public key as an identifier and knowledge of a shared secret as proof of ownership (without including the public keys in the key derivation) might lead to subtle vulnerabilities.
distinguishability, who cares:
Designers should also be aware that implementations of these curves might not use the Montgomery ladder as specified in this document, but could use generic, elliptic-curve libraries instead. These implementations could reject points on the twist and could reject non-minimal field elements. While not recommended, such implementations will interoperate with the Montgomery ladder specified here but may be trivially distinguishable from it. For example, sending a non-canonical value or a point on the twist may cause such implementations to produce an observable error while an implementation that follows the design in this text would successfully produce a shared key.
RFC 8031: Curve25519 and Curve448 for the Internet Key Exchange Protocol Version 2 (IKEv2) Key Agreement
Curve25519 and Curve448 are designed to facilitate the production of high-performance constant-time implementations. Implementors are encouraged to use a constant-time implementation of the functions. This point is of crucial importance, especially if the implementation chooses to reuse its ephemeral key pair in many key exchanges for performance reasons.
NIST lol:
While the NIST curves are advertised as being chosen verifiably at random, there is no explanation for the seeds used to generate them. In contrast, the process used to pick Curve25519 and Curve448 is fully documented and rigid enough so that independent verification can and has been done. This is widely seen as a security advantage because it prevents the generating party from maliciously manipulating the parameters.
Most users of Curve25519 believe that they don't have to validate public keys. I used to believe that too until I saw what could go wrong.
What is the solution? Curve25519 suggests blacklisting the known bad public keys, but a better solution is to check the shared value and to raise exception if it is zero. You can also bind the exchanged public keys to the shared keys, i.e., instead of using H(abG) as the shared keys, you should use H(aG || bG || abG). If you exchange more than public keys -- TLS exchanges nonces, certs, and other info -- you should include them too. If you are implementing Curve25519 yourself, instead of encoding the point at infinity as zero, perhaps you should raise an exception. I cannot come up with any protocols which need to encode the point at infinity.
there are other points that one can send, besides the point 0, any point in the subgroup would do. But since X25519 multiplies by 8, they all result in the all zero shared secret I believe.
I hate this "contributory behavior is optional and not needed for standard DH" line. -- Matthew Green
While analyzing Signal with Markus, I noticed that Signal’s Curve25519-based ECDH doesn’t validate public keys, and in particular will accept the 0 point as a public key—leading to a shared secret equivalent to 0 regardless of the value of the private key scalar. In contrast, libsodium will return an error if the shared secret happens to be 0, and Wire now performs this verification as well, after we reported that it was missing in our report.
If Moxie, Trevor, and DJB argue that public keys shouldn’t be validated, then the debate is over. Really? Thai Duong has a different take, Matt Green is skeptical, and I am too.
The first thing you learn in any infosec class is to reject invalid inputs, and check return values for errors, even if there’s no obvious exploit in sight. Doing this is sometimes called “defense in depth” or “best practice”.
The point of Diffie-Hellman is that both key shares should equally contribute to the shared secret, so that the protocol doesn’t allow key control, a desirable attribute of any authenticated key agreement protocol, as discussed in this MQV paper. If the protocol allows a peer to force the shared secret to be zero, or more generally to lie in a subgroup, then the said peer can surreptitiously weaken the protocol’s security (objection: “but why would a peer be malicious?”).
checking NIST public keys:
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.
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:
ECC Full Public-Key Validation Routine in section 5.6.2.3.2, and, 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:
- Verify that the public key is not the “point at infinity”, represented as O.
- 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.
- Verify that y2 = x3 + ax + b where a and b are the coefficients of the curve equation. (This is the check that most JOSE libraries implemented).
- 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?
More recently, reading about Matrix as part of writing my book, I realized that their authentication protocol was broken, leading to a break of their end-to-end encryption.