[SEC] Validation of Curve25519 points

[pornin]

(Tags: nbc-audit-2020-0, difficulty:high, severity:does-not-spark-joy, bug)

In libp2p/crypto/curve25519.nim, lines 40 to 54, an array of twelve 32-byte values is defined: these are the "forbidden curve values", i.e. 32-byte encodings that correspond to points of low order on either Curve25519 or its quadratic twist. There are three somewhat related issues with this array:

1. The last byte of the last value is wrong; it is given as "25" instead of the expected "255".
2. Actually, the last five values of the array are wrong, for a different reason.
3. The ForbiddenCurveValues is used to validate key pairs that the code generates itself, and not to validate incoming public keys from remote peers with which some ECDH key exchange is to be performed.

To understand what is going on here, I need a bit of maths:

Curve25519 basics

Curve25519 is, in practice, a pair of elliptic curves which are quadratic twists of each other. Curve25519 "proper" has order 8r for a 252-bit prime r; the quadratic twist has order 4r' for another 252-bit prime r'. An input value is a sequence of 32 bytes, which encode the X coordinate of a point, i.e. an element of the base field (integers modulo p = 2^255-19). Each encoding can either be for a point (technically, a pair of points) on Curve25519, or a point on the twist; there is no encoding that matches points on both curves, and no encoding with no matching point on any curve.

Notwithstanding, "correct" points are public keys generated by multiplying a conventional base point B by the secret key. The secret key is chosen as a random 255-bit integer (it is a 'scalar'), which is "clamped": its three low bits are cleared (so it is a multiple of 8) and its 254th bit is set (so the integer must be in the 2^254..2^255-8 range); the base point B is on Curve25519 (not the twist), and has order exactly r. Therefore, correct public keys are exactly the encodings of points of order r on the non-twist curve.

ForbiddenCurveValues incarnates a specific, small subset of incorrect points. These are the points of low order on either curve, i.e. points with order 2, 4 or 8 on the non-twist curve, and points of order 2 or 4 on the twist. All other points have order either r or r' (depending on which curve they fall), or a multiple thereof.

Wrong values in the table

The first issue is a simple typo: the last byte of the last value is miswritten as "25" instead of "255". This problem, is, in fact, superseded by another one, which the second issue: due to a historical confusion, some of the values are wrong. Specifically:

• The list of values in ForbiddenCurveValues is exactly (modulo the typo in the last byte of the last value) the list of integers in http://cr.yp.to/ecdh.html#validate. These are 256-bit integers, encoded in little endian.
• BearSSL, however, implements Curve25519 as specified by RFC 7748, which specifies (section 5) that points are encoded over exactly 255 bits, not 256; the top bit MUST be ignored.

The consequence is that ForbiddenCurveValues uses an interpretation of the top bit of the last byte that differs from what BearSSL code does. For instance, suppose that an encoded point is ED:FF:FF:...:FF. ForbiddenCurveValues sees nothing wrong about it: as a 256-bit integer, it is equal to 2^256-19, which, when reduced modulo 2^255-19, yields 19 (which would be the X coordinate for a point of order 8r on the non-twist curve). In the RFC 7748 interpretation, though, the top bit is ignored, and the 255-bit value is now equal to 2^255-19, i.e. 0 in the base field, and the point is a low-order point (its order is 2).

What that implies is that some values in ForbiddenCurveValues, specifically those such that the top bit is 1, are wrong. If we call the 12 "forbidden values" f0 to f11, then:

• f0 to f6 are correct (that is, they are encodings of points which would be decoded as low-order points with RFC 7748 interpretation).
• f7 and f9 are encodings of some points on the twisted curve; correctly generated public keys (by multiplying B with a scalar) cannot be either of these points.
• f8 and f10 are encodings of points of the non-twisted curve, with orders 8r and 2r, respectively. Though they are on the non-twisted curve, they are not multiples of B (since B has order r) and thus cannot be obtained as correctly generated public keys.
• f11 has the typo, and the value in the table happens to be for a point on the twisted curve. If the typo were corrected, this would yield a point on the non-twisted curve, of order 4r, thus again never equal to a correctly generated public key.

All of this means that the wrong values in ForbiddenCurveValues will not lead to rejection of any correct public key. On the other hand, it may imply lack of rejection of some incorrect public keys, which brings us to the third issue.

Lack of use of the table on incoming points

The third issue is that the ForbiddenCurveValues is not actually applied on incoming public keys. It is applied only on key pairs generated by the code itself, key pairs which are, by definition, not adversarial. Therefore, that table is not very useful. The key pair generator produces a random scalar and multiplies B. Since B is on the non-twisted curve and has order r, this can only generate a point of order r on the right curve, or, conceptually, the "point-at-infinity", which is the neutral element on the curve and gets encoded as 0; the latter case occurs when the scalar, after clamping, happens to be a multiple of r, which will happen with probability about 2^(-249), i.e. never. Thus, in the ForbiddenCurveValues table as it is currently used in curve25519.nim, only the first value may ever be matched, and even that will not happen in practice.

On the other hand, incoming public keys will not be matched against the list of low-order points. It must be said that this is not a problem when Curve25519 is used for an ECDH key exchange as part of either TLS or Noise; in the case of Noise, this is specifically stated in the Noise specification, which recommends not to validate points:

Alternatively, implementations are allowed to detect inputs that produce an all-zeros output and signal an error instead. This behavior is discouraged because it adds complexity and implementation variance, and does not improve security. This behavior is allowed because it might match the behavior of some software.

Summary

The table has wrong entries. The wrong entries do not induce any non-negligible effect, because:

• The wrong entries will not reject any correct public keys.
• Even if they did, the probability of hitting such an entry would be negligible.
• In any case, the table is not applied on the incoming points, which might be maliciously crafted, but on key pairs locally generated, which by definition are not maliciously crafted.
• Filtering out low-order points is not useful for use within the Noise protocol, which is the only use of Curve25519 in nim-libp2p.

Thus, this is not a serious vulnerability, but it definitely does not spark joy.

Recommendation

Since the table has wrong entries and is not useful with the use of Curve25519 in Noise, it would be simplest and cleanest to just remove it. Alternatively, retaining the table could be useful for some other (as yet unspecified) protocols that would require so-called "contributory behaviour" and thus would need filtering out of low-order points, but, in that case, the table contents would have to be fixed and the table would have to be applied where it matters, i.e. on incoming public points from peers, not on points generated locally.

[sinkingsugar]

thank you! I think this historically came from some go implementation but indeed I never really did any scrutiny. All in favor for simplicity and its removal!

[sinkingsugar]

Fixes in https://github.com/status-im/nim-libp2p/pull/298

[eschorn1]

I have reviewed https://github.com/status-im/nim-libp2p/pull/298/files and observe the removal of the forbidden curve values and associated logic. This addresses the finding and thus this issued can be closed. Thank you!