An Illustrated Guide to Elliptic Curve Cryptography Validation

[coderman]

https://research.nccgroup.com/2021/11/18/an-illustrated-guide-to-elliptic-curve-cryptography-validation/

[Paul Bottinelli](https://research.nccgroup.com/author/pbottine/)  [Cryptography](https://research.nccgroup.com/category/cryptography/), [Research](https://research.nccgroup.com/category/research/), [Tutorial/Study Guide](https://research.nccgroup.com/category/tutorial-study-guide/)  November 18, 2021 12 Minutes

Elliptic Curve Cryptography (ECC) has become the de facto standard for protecting modern communications. ECC is widely used to perform asymmetric cryptography operations, such as to establish shared secrets or for digital signatures. However, insufficient validation of public keys and parameters is still a frequent cause of confusion, leading to serious vulnerabilities, such as leakage of secret keys, signature malleability or interoperability issues.

The purpose of this blog post is to provide an illustrated description of the typical failures related to elliptic curve validation and how to avoid them in a clear and accessible way. Even though a number of standards[1](https://research.nccgroup.com/2021/11/18/an-illustrated-guide-to-elliptic-curve-cryptography-validation/#sec),[2](https://research.nccgroup.com/2021/11/18/an-illustrated-guide-to-elliptic-curve-cryptography-validation/#nist) mandate these checks, implementations frequently fail to perform them.

While this blog post describes some of the necessary concepts behind elliptic curve arithmetic and cryptographic protocols, it does not cover elliptic curve cryptography in detail, which has already been done extensively. The following blog posts are good resources on the topic: [A (Relatively Easy To Understand) Primer on Elliptic Curve Cryptography](https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/) by Nick Sullivan and [Elliptic Curve Cryptography: a gentle introduction](https://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/) by Andrea Corbellini.

In elliptic curve cryptography, public keys are frequently sent between parties, for example to establish shared secrets using [Elliptic curve Diffie–Hellman (ECDH)](https://en.wikipedia.org/wiki/Elliptic-curve_Diffie%E2%80%93Hellman). The goal of public key validation is to ensure that keys are legitimate (by providing assurance that there is an existing, associated private key) and to circumvent attacks leading to the leakage of some information about the private key of a legitimate user.

Issues related to public key validation seem to routinely occur in two general areas. First, transmitting public keys using digital communication requires to convert them to bytes. However, converting these bytes back to an elliptic curve point is a common source of issues, notably due to [canonicalization](https://en.wikipedia.org/wiki/Canonicalization). Second, once public keys have been decoded, some mathematical subtleties of the elliptic curve operations may also lead to different types of attacks. We will discuss these subtleties in the remainder of this blog post.

TL;DR

In general[3](https://research.nccgroup.com/2021/11/18/an-illustrated-guide-to-elliptic-curve-cryptography-validation/#general), vulnerabilities may arise when applications fail to check that:

- The point coordinates are lower than the field modulus.
- The coordinates correspond to a valid curve point.
- The point is not the point at infinity.
- The point is in the correct subgroup.

An Illustrated Guide to Validating ECC Curve Points

Elliptic curves are curves given by an equation of the form [y^2 = x^3 + ax + b] (called short Weierstrass form). Elliptic curve cryptography deals with the group of points on that elliptic curve, namely, a set of [(x, y)] values satisfying the curve equation.

These values, called coordinates (more specifically, affine coordinates), are defined over a field. For use in Cryptography, we work with coordinates defined over a finite field. For the purpose of this blog post, we will concentrate our efforts on the field of integers modulo [p], with [p] a prime number (and [p > 3]), which we call the field modulus. Elements of this field can take any value between  and [p - 1] . In the following figure, the white squares depict valid field elements while grey squares represent the elements that are larger than the field modulus.

Mathematically, a value larger than the field modulus is equivalent to its reduced form (that is, in the  to [p-1] range, see [congruence classes](https://en.wikipedia.org/wiki/Modular_arithmetic#Congruence_classes)), but in practice these ambiguities may lead to complex issues[4](https://research.nccgroup.com/2021/11/18/an-illustrated-guide-to-elliptic-curve-cryptography-validation/#zcash).

In ECC, a public key is simply a point on the curve. Since curve points are generally first encoded to byte arrays before being transmitted, the first step when receiving an encoded curve point is to decode it. This is what we identified earlier as the first area of confusion and potential source of vulnerabilities. Specifically, what happens when the integer representation of the coordinates we decoded are larger than the field modulus?

This is the first common source of issues and the reason for our first validation rules:

> Check that the point coordinates are lower than the field modulus.

What can go wrong? If the recipient does not enforce that coordinates are lower than the field modulus, some elliptic curve point operations may be incorrectly computed. Additionally, different implementations may have diverging interpretations of the validity of a point, possibly leading to interoperability issues, which can be a critical issue in consensus-driven deployments.

In the figure below, this means that the point coordinates should be rejected if they are not in the white area in the bi-dimensional plane.

Since both coordinates are elements of this finite field, it might seem that an elliptic curve point could theoretically take any value in the white area above. However, not all pairs of [(x, y)] values in this plane are valid curve points; remember that they need to satisfy the curve equation [y^2 = x^3 + ax + b] in order to be on the curve. We represent the valid curve point in blue in the figure below[5](https://research.nccgroup.com/2021/11/18/an-illustrated-guide-to-elliptic-curve-cryptography-validation/#arbitrary). The number of points on the curve is referred to as the curve order.

This is another common source of issues and where our second validation rule arises:

> Check that the point coordinates correspond to a valid curve point (i.e. that the coordinates satisfy the curve equation).

What can go wrong? If the recipient of a public key fails to verify that the point is on the curve, an attacker may be able to perform a so-called invalid curve attack[6](https://research.nccgroup.com/2021/11/18/an-illustrated-guide-to-elliptic-curve-cryptography-validation/#invalid). Some point operations being independent of the value of [b] in the elliptic curve equation, a malicious peer may carefully select a different curve (by varying the value of [b]) in which the security is reduced (namely, the discrete logarithm problem is easier than on the original curve). By then sending a point on that new curve (and provided the legitimate peer fails to verify that the point coordinates satisfy the curve equation), the attacker may eventually recover the legitimate peer’s secret.

In practice, curve points are rarely sent as pairs of coordinates, which we call uncompressed. Indeed, the [y]-coordinate can be recovered by solving the curve equation for a given [x], which is why point compression was developed. Point compression reduces the amount of data to be transmitted by (almost) half, at the cost of a few more operations necessary to solve the curve equation. However, solving the equation for a given [x] may have different outcomes. It can either result in:

- no solutions (in case [y^2] does not have a square root in the field, i.e. is not a quadratic residue), in which case the point should be rejected; or
- two solutions, [(x, y)] and [(x, -y)], due to the fact that [y^2 = (-y)^2]. However, all coordinates must lie in the [0 \ldots p-1] range, which are all positive numbers. Since we’re working in the field of integers modulo [p], that negative [y]-coordinate is actually equivalent to the field element [p - y], which lies in the correct range.

Hence, when compressing a point, an additional byte of data is used to distinguish the correct [y]-coordinate. Specifically, point encoding (following Section 2.3.3 of [SEC 1](https://www.secg.org/sec1-v2.pdf), works by prepending a byte to the coordinate(s) specifying which encoding rule is used, as follows:

- Compressed point: 0x02 || x if y is even and 0x03 || x if y is odd;
- Uncompressed point: 0x04 || x || y.[7](https://research.nccgroup.com/2021/11/18/an-illustrated-guide-to-elliptic-curve-cryptography-validation/#hybrid)

Any other value for the first byte should result in the curve point being ignored. Point compression has a significant benefit in that it ensures that the point is on the curve, since in case there is no solution, implementation should reject the point.

Now, the careful reader may have realized that the set of points in the figure above is incomplete. In order for this set to form a group (in the [mathematical sense](https://en.wikipedia.org/wiki/Group_(mathematics))), and be useful in cryptography, it needs to be supplemented with an additional element, the point at infinity. This point, also called neutral element or additive identity, is the element [\mathcal{O}] such that for any point [P] on our elliptic curve, [P + \mathcal{O} = \mathcal{O} + P = P]. The figure below shows the previous set of points on our arbitrary curve with the addition of the point at infinity, which we (artificially) positioned slightly outside our plane, in the bottom left corner.

Since the point at infinity is not on the curve, it does not have well-defined [x] and [y] coordinates like other curve points. As such, its representation had to be constructed artificially[8](https://research.nccgroup.com/2021/11/18/an-illustrated-guide-to-elliptic-curve-cryptography-validation/#structure). Standards (such as [SEC 1: Elliptic Curve Cryptography](https://www.secg.org/sec1-v2.pdf)) define the encoding of the point at infinity to be a single octet of value zero. Confusingly, implementations sometimes also use other encodings for the point at infinity, such as a number of zero bytes equal to the size of the coordinates.

Implementations sometimes fail to properly distinguish the point at infinity, and this is where our third validation rule comes from:

> Check that the point is not the point at infinity.

What can go wrong? Since multiplying the point at infinity by any scalar results in the point at infinity, an adversary may force the result of a key agreement to be zero if the legitimate recipient fails to check that the point received is not the point at infinity. This goes against the principle of contributory behavior, where some protocols require that both parties contribute to the outcome of an operation such as a key exchange. Failure to enforce this check may have additional negative consequences in other protocols.

Recall that the curve order, say [N], corresponds to the number of points on the curve. To make matters more complicated, the group of points on an elliptic curve may be further divided into multiple subgroups. [Lagrange’s theorem](https://en.wikipedia.org/wiki/Lagrange%27s_theorem_(group_theory)) tells us that any subgroup of the group of points on the elliptic curve has an order dividing the order of the original group. Namely, the size (i.e. the number of points) of every subgroup divides the total number of points on the curve.

In cryptography, to ensure that the discrete logarithm problem is hard, curves are selected in such a way that they consist of one subgroup with large, prime order, say [n], in which all computations are performed. Some curves (such as the NIST curves[9](https://research.nccgroup.com/2021/11/18/an-illustrated-guide-to-elliptic-curve-cryptography-validation/#nistp), or the curve secp256k1[10](https://research.nccgroup.com/2021/11/18/an-illustrated-guide-to-elliptic-curve-cryptography-validation/#secp256k1) used in bitcoin) were carefully designed such that [n = N], namely the prime order group in which we perform operations is the full group of points on the elliptic curve. In contrast, the popular Curve25519 has curve order [N = 8n], which means that points on this curve can belong to the large prime-order subgroup of size [n], or to a subgroup with a much smaller order, of size 2, 4 or 8, for example[11](https://research.nccgroup.com/2021/11/18/an-illustrated-guide-to-elliptic-curve-cryptography-validation/#taming). The value [h] such that [h = N/n] is called the cofactor, it can be thought of as the ratio between the total number of points on the curve and the size of the prime-order subgroup in which cryptographic operations are performed.

To illustrate this notion, consider the figure below in which we have further subdivided our fictitious set of elliptic curve points into two groups. When performing operations on elliptic curve points, we want to stick with operations on points in the larger, prime-order subgroup, identified by the blue points below.

And this is where our last validation rule comes from:

> Check that the point is in the correct subgroup.

This can be achieved by checking that [nP = \mathcal{O}]. Indeed, a consequence of Lagrange’s theorem is that any group element multiplied by the order of that group is equal to the neutral element. If [P] were in the small subgroup, multiplying it by [n] would not equal [\mathcal{O}]. This highlights another possible method for checking that the point belongs to the correct subgroup; one could also check that [hP \neq \mathcal{O}]. Contrary to the previous validation rules, this check is considerably more expensive since it requires a point multiplication, and as such is sometimes (detrimentally) skipped for efficiency purposes.

What can go wrong? A malicious party sending a point in the orange subgroup, for example as part of an ECDH key agreement protocol, would result in the honest party performing operations limited to that small subgroup. Thus, if the recipient of a public key failed to check that the point was in the correct subgroup, the attacker could perform a so-called small subgroup attack (also known as subgroup confinement attacks) and learn information about the legitimate party’s private key[12](https://research.nccgroup.com/2021/11/18/an-illustrated-guide-to-elliptic-curve-cryptography-validation/#small).

Does that apply to all curves?

While the presentation above is fairly generic and applies in a general sense to all curves, some curves and associated constructions were created to prevent some of these issues by design.

NIST curves (e.g. P-256) and the Bitcoin curve (secp256k1)

These curves have a cofactor value of 1 (namely, [h = 1]). As such, there is only one large subgroup of prime order and all curve points belong to that group. Hence, once the first 3 steps in our validation procedure have been performed, the last step is superfluous.

Curve25519

Curve25519, proposed by Daniel J. Bernstein and specified in [RFC 7748](https://datatracker.ietf.org/doc/html/rfc7748), is a popular curve which is notably used in TLS 1.3 for key agreement.

Although Curve25519 has a cofactor of 8, some functions using this curve were designed to prevent cofactor-related issues. For example, the X25519 function used to perform key agreement using Curve25519 mandates specific checks and performs key agreement using only [x]-coordinates, such that invalid curve attacks are avoided. Additionally, the governing RFC states in [Section 5](https://datatracker.ietf.org/doc/html/rfc7748#section-5) that

> Implementations MUST accept non-canonical values and process them as if they had been reduced modulo the field prime. The non-canonical values are 2^255 – 19 through 2^255 – 1 for X25519.

This seems to address most issues discussed in this post. However, there has been some debate[13](https://research.nccgroup.com/2021/11/18/an-illustrated-guide-to-elliptic-curve-cryptography-validation/#debate) over the claimed optional nature of these checks.

With the popularity of Curve25519 and the desire for cryptographers to design more exotic protocols with it, the cofactor value of 8 resurfaced as a potential source of problems. [Ristretto](https://ristretto.group/) was designed as a solution to the cofactor pitfalls. Ristretto is an abstraction layer, on top of Curve25519, which essentially restricts curve points to a prime-order subgroup.

Double-Odd Elliptic Curves

Finally, a strong contender in the secure-by-design curve category is the [Double-Odd](https://doubleodd.group/) family of elliptic curves, recently proposed by Thomas Pornin. These curves specify a strict and economical encoding, preventing issues with canonicalization and, even though their cofactor is not trivial, a prime order group is defined on them, similar in spirit to Ristretto’s approach, preventing subgroup confinement attacks.

Conclusion

With the ubiquitous use of elliptic curve cryptography, failure to validate elliptic curve points can be a critical issue which is sadly still commonly uncovered during cryptography reviews. While standards and academic publications provide ample directions to correctly validate curve points, implementations still frequently fail to follow these steps. For example, a vulnerability nicknamed [Curveball](https://msrc.microsoft.com/update-guide/vulnerability/CVE-2020-0601) was reported in January 2020, which allowed attacker to perform spoofing attacks in Microsoft Windows by crafting public points. Recently, we also uncovered a critical vulnerability in a number of open-source ECDSA libraries, in which the verification function failed to check that the signature was non-zero, allowing attackers to forge signatures on arbitrary messages, see the technical advisory [Arbitrary Signature Forgery in Stark Bank ECDSA Libraries](https://research.nccgroup.com/2021/11/08/technical-advisory-arbitrary-signature-forgery-in-stark-bank-ecdsa-libraries/).

This illustrated guide will hopefully serve as an accessible reference on why and how point validation should be performed.

Thank you

The author would like to thank Eric Schorn and Giacomo Pope for their detailed review and helpful feedback.

---------------------------------------------------------------

References

- [Standards for efficient cryptography, SEC 1: Elliptic Curve Cryptography](https://www.secg.org/sec1-v2.pdf), Section 3.2.2.1 Elliptic Curve Public Key Validation Primitive.
- [NIST Special Publication 800-56A](https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-56Ar3.pdf), Section 5.6.2.3.2 FFC Partial Public-Key Validation Routine and 5.6.2.3.3 ECC Full Public-Key Validation Routine.
- That is, unless using an elliptic curve that was designed specifically to address these potential issues, we will come back to that at the end of this blog post.
- Specifically, implementations may handle values that are larger than the field modulus in different ways. They may reject non-reduced values (i.e., non-canonical encodings), accept non-reduced values and reduce them modulo the prime order, or accept non-reduced values and discard the most significant bit(s). An interesting example happened with the cryptocurrency Zcash, where different implementations had distinct interpretations regarding the validity of curve points. Some details can be found in a [blog post](https://hdevalence.ca/blog/2020-10-04-its-25519am) by Henry de Valence, as well as in a public report following a [cryptography review](https://research.nccgroup.com/wp-content/uploads/2020/09/NCC_Group_Zcash_ZCHX006_Report_2020-09-03_v2.0.pdf) performed by NCC Group.
- Note that this figure does not represent an actual elliptic curve; it is just an arbitrary diagram designed for illustrative purposes.
- Ingrid Biehl, Bernd Meyer and Volker Müller. “Differential Fault Attacks on Elliptic Curve Cryptosystems”. In: Advances in Cryptology – CRYPTO 2000, 20th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 2000, Proceedings. 2000, pp. 131–146.
- Note that there is a hybrid form starting in 0x06 defined in [ANSI X9.62](https://standards.globalspec.com/std/1955141/ANSI%20X9.62), but this format is very rarely used in practice.
- Note that some curves and alternate point representations (for instance, when working in projective coordinates) may allow the point at infinity to have a well-defined representation.
- Standardized in [FIPS PUB 186-4: Digital Signature Standard (DSS)](https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf).
- Standardized in [SEC 2: Recommended Elliptic Curve Domain Parameters](http://www.secg.org/sec2-v2.pdf).
- The paper [Taming the many EdDSAs](https://eprint.iacr.org/2020/1244.pdf) provides some very interesting discussions around ambiguities in the Ed25519 signature verification equations (which is based on Curve25519). These ambiguities led to different interpretations of the validity of signatures, which resulted in implementations returning different validity results for some signatures, which could be critical in consensus-driven applications.
- Chae Hoon Lim and Pil Joong Lee. “A Key Recovery Attack on Discrete Log-based Schemes Using a Prime Order Subgroup”. In: Advances in Cryptology – CRYPTO ’97, 17th Annual International Cryptology Conference, Santa Barbara, California, USA, August 17-21, 1997, Proceedings. 1997, pp. 249–263.
- See https://moderncrypto.org/mail-archive/curves/2017/000896.html.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: text/html
Size: 37000 bytes
Desc: not available
URL: <https://lists.cpunks.org/pipermail/cypherpunks/attachments/20211201/5afc545b/attachment.txt>