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

[Jack Grigg <[e-mail]>]

My concern is not about whether X-Wing is contributory or not. I do not
particularly care about the classical side of the hybrid, and I don't have
a strongly-held opinion on whether CFRG should require non-contributory
behaviour in X25519 be accepted or rejected.

My concern is about the ambiguity in the set of valid ciphertexts. If some
entities will accept as valid ciphertexts that others reject, it makes
designing some protocols that use those ciphertexts much harder.

We had the same problem in Zcash with Ed25519 signatures having wildly
inconsistent validity criteria [0], forcing us to define our own
verification profile for consensus-critical applications [1]. We could do
that because Ed25519 was a leaf primitive used directly, so wrapping
existing Ed25519 implementations was (while not trivial) feasible.

In the case of X-Wing, the problem is that this ambiguity exists internally
to the hybrid. There is no specified way to control the behaviour, and the
X25519 shared secret inaccessible for introspection outside of an X-Wing
implementation. It might be possible to detect the case externally from the
inputs to Decap (or more likely, to HPKE.Open), but that would require
parsing values at a layer where they should be opaque, which is brittle and
error-prone. It also doesn't help override the internal behaviour of the
X-wing implementation (and would probably also require APIs that are not
exposed by most X-Wing impls).

For my specific use case, the current state of the draft means that anyone
wanting to implement PQ age ciphertext decryption has to roll the dice on
whether e.g. Apple's X-Wing impl is compatible (an example, I haven't
checked it), and if it isn't then they have to manually re-implement
X-Wing. That is brittle, error-prone, and a significant barrier to adoption.

Cheers,
Jack

[0] https://hdevalence.ca/blog/2020-10-04-its-25519am/
[1] https://zips.z.cash/zip-0215

On Thu, 16 Jul 2026, 8:11 am Peter Schwabe, <[e-mail]> wrote:

> Dear Jack,
>
> If your main concern is about X-Wing being contributory (or not), isn't
> that resolved by ML-KEM being contributory?
>
> All the best,
>
> Peter
>
>
> Jack Grigg <[e-mail]> wrote:
> >  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
>
> > _______________________________________________
> > CFRG mailing list -- [e-mail]
> > To unsubscribe send an email to [e-mail]
>
>