[CFRG] Nailing down non-contributory behaviour in the hybrid-kems drafts

[Jack Grigg <[e-mail]>]

 Hi all,

While implementing a protocol using X-Wing (specifically post-quantum
support in age encryption [0] using HPKE), I encountered an incompatibility
between two different X-Wing implementations that led me down the
hybrid-kems rabbit hole, and I uncovered several inconsistencies in the
drafts that should be resolved.

The core problem stems from Section 6.1 of RFC 7748 [1], which placed a MAY
on checking for non-contributory behaviour:

> Both now share K = X25519(a, X25519(b, 9)) = X25519(b, X25519(a, 9)) as a
shared secret.  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).
> [...]
> 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](https://www.rfc-editor.org/info/rfc7748/#section-7))

Neither the original X-Wing draft [2], nor the ePrint it is based on [3]
mentioned this, and thus inherently embedded the MAY in its specification.
This has led to different X-Wing implementations implementing different
behaviour, likely based on whatever their existing X25519 implementation
made most convenient to do.

However, this is seemingly incompatible with the current draft
specification for X-Wing (aka MLKEM768-X25519) in
draft-irtf-cfrg-concrete-hybrid-kems-04 [4]. Specifically, Section 4.2 of
draft-irtf-cfrg-hybrid-kems-12 [5] states:

> A scalar value of zero MUST NOT be used as a private key: it does not
correspond to a meaningful Diffie-Hellman exchange and, for some curves
such as P-256, is explicitly forbidden by the relevant standards and would
yield a point-at-infinity encoding that departs from the fixed-size model
used here. RandomScalar MUST NOT return a zero scalar; for the groups of
interest this occurs only with negligible probability.

A strict reading of the above could be interpreted as allowing
non-contributory behaviour, because AFAICT there's nothing in the current
text that actually does the identity check on the nominal group shared
secret. However, I think these MUST NOTs imply it was the authors'
intentions to require rejection of non-contributory behaviour. Indeed, if
you read the specifications of expandDecapsKeyG and prepareEncapsG [6] with
those MUST NOTs enforced, then it is impossible to produce a ciphertext
that would have non-contributory behaviour, and thus an implementation
could quite justifiably reject those that do.

Further supporting evidence for rejecting non-contributory behaviour in
IETF KEMs is found in RFC 9180 [7], which makes this a MUST for the X25519
DHKEM (which its update draft [8] preserves).

Now, for an honestly-generated key and ciphertext, the chance of
encountering this divergence is cryptographically negligible:
- The Curve25519 scalar within a decapsulation key is a subslice of the
output of PRG(seed) (via GenerateKeyPair [9] and expandDecapsKeyG).
- The ephemeral Curve25519 scalar used within encapsulation is the output
of RandomScalar(random(32)) (via prepareEncapsG), which is constrained by
the MUST NOT on the output of RandomScalar.

However, for an adversarial ciphertext, there is nothing preventing the
adversary from using zero as the ephemeral Curve25519 scalar, or a point of
small order as the ephemeral public key. Indeed, I encountered this issue
due to this specific edge case being exercised in age test vectors. So the
probability of encountering this divergence is non-negligible, and the
specs should handle it.

My suggested fix is to alter the definition of ElementToSharedSecret [10]
to something like:

>  ElementToSharedSecret(P) -> ss: Extract a shared secret from an element
of the group (e.g., by taking the X coordinate of an elliptic curve point),
aborting if a valid shared secret cannot be extracted.

and then for the Curve25519 Nominal Group defined in Section 3.1.2
of draft-irtf-cfrg-concrete-hybrid-kems-04 [11], change its
ElementToSharedSecret specification to:

> ElementToSharedSecret(p) -> ss: Aborts if P is the all-zero value,
otherwise outputs P.

However, that does then raise the question of whether X-Wing is being
assumed as purely an implicitly-rejecting KEM (due to how its ML-KEM
component behaves). I don't believe it was ever valid to assume this, due
to the MAY in the X25519 component meaning that X25519 implementations can
explicitly abort, and thus so might X-Wing. However, if this is a
widely-held and relied-upon assumption, then it would imply that a
compatible X-Wing spec would instead need to require that
expandDecapsKeyG MUST NOT check whether the shared secret is the all-zero
value, in order to prevent the abort. I myself would prefer that X-Wing
follow the RFC 9180 precedent and reject non-contributory behaviour.

---

Regardless of how the above is addressed, at least one other fix is
necessary. The Curve25519 Nominal Group specifies its RandomScalar as:

> RandomScalar(seed) -> k: Implemented by the identity function, i.e., by
returning the seed.

This trivially violates the MUST NOT from draft-irtf-cfrg-hybrid-kems-12;
the all-zero seed produces the forbidden zero scalar. This should be
similarly updated to:

> RandomScalar(seed) -> k: Aborts if seed is the all-zero value, otherwise
returns the seed.

Cheers,
Jack

[0] https://c2sp.org/age#mlkem768x25519-recipient-stanza
[1] https://www.rfc-editor.org/info/rfc7748/#section-6.1
[2] https://datatracker.ietf.org/doc/html/draft-connolly-cfrg-xwing-kem-10
[3] https://eprint.iacr.org/2024/039
[4]
https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-concrete-hybrid-kems-04#name-mlkem768-x25519
[5]
https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hybrid-kems-12#section-4.2-4
[6]
https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hybrid-kems-12#name-using-a-nominal-group
[7] https://www.rfc-editor.org/info/rfc9180/#section-7.1.4
[8]
https://datatracker.ietf.org/doc/html/draft-ietf-hpke-hpke-04#name-validation-of-inputs-and-ou
[9]
https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hybrid-kems-12#name-key-generation
[10]
https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hybrid-kems-12#section-4.2-3.3.1
[11]
https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-concrete-hybrid-kems-04#name-curve25519-nominal-group