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

[Peter Schwabe <[e-mail]>]

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]