The x-wing crate currently implements draft-connolly-cfrg-xwing-kem-06 (AFAICT there are no breaking changes between that and the current draft -10). That draft uses the X25519 function from Section 5 of RFC 7748, and the standard basepoint from Section 6.1. However, there is another part of Section 6.1 that affects Xwing:
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).
The Xwing draft makes no mention of this, and thus inherently embeds the MAY in its specification, The x-wing crate does not implement this check, and thus permits decapsulation of ciphertexts with non-contributory behaviour on the X25519 side.
However, this is incompatible with Section 4.2 of draft-irtf-cfrg-hybrid-kems-12, which 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.
The Xwing defined using this draft (in Section 4.2 of draft-irtf-cfrg-concrete-hybrid-kems-04, which claims to be identical to draft-connolly-cfrg-xwing-kem-10) therefore does reject non-contributory behaviour (although it is currently inconsistent; Section 3.1.2 says that RandomScalar is the identity function for Curve25519, which violates the MUST NOT of draft-irtf-cfrg-hybrid-kems-12).
Now, for an honestly-generated key the chance of encountering this divergence is negligible:
- The Curve25519 scalar within a decapsulation key is a subslice of the output of
PRG(seed) (via GenerateKeyPair 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 (once it is fixed for the concrete instantiation as I noted above).
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 @FiloSottile exercising this specific edge case in age test vectors (hybrid_identity, hybrid_low_order, the test case generator). So the probability of encountering this divergence is non-negligible, and we need to deal with it.
I'm going to discuss what to do about the drafts themselves with CFRG. However, as many people have already shipped Xwing, I expect many existing implementations will be allowing non-contributory behaviour, so there will likely be domains in which it is required that x-wing behave the way it currently does. So I'm thinking that the simplest fix to x-wing is:
- Ensure it never generates the zero scalar anywhere on encapsulation (which is allowed by the MAY in RFC 7748).
- Add a flag to the
DecapsulationKey constructors (or alternate constructors) that enables the caller to select whether or not non-contributory behaviour is rejected at decapsulation time.
The
x-wingcrate currently implementsdraft-connolly-cfrg-xwing-kem-06(AFAICT there are no breaking changes between that and the current draft-10). That draft uses the X25519 function from Section 5 of RFC 7748, and the standard basepoint from Section 6.1. However, there is another part of Section 6.1 that affects Xwing:The Xwing draft makes no mention of this, and thus inherently embeds the MAY in its specification, The
x-wingcrate does not implement this check, and thus permits decapsulation of ciphertexts with non-contributory behaviour on the X25519 side.However, this is incompatible with Section 4.2 of
draft-irtf-cfrg-hybrid-kems-12, which states:The Xwing defined using this draft (in Section 4.2 of
draft-irtf-cfrg-concrete-hybrid-kems-04, which claims to be identical todraft-connolly-cfrg-xwing-kem-10) therefore does reject non-contributory behaviour (although it is currently inconsistent; Section 3.1.2 says thatRandomScalaris the identity function for Curve25519, which violates the MUST NOT ofdraft-irtf-cfrg-hybrid-kems-12).Now, for an honestly-generated key the chance of encountering this divergence is negligible:
PRG(seed)(viaGenerateKeyPairandexpandDecapsKeyG).RandomScalar(random(32))(viaprepareEncapsG), which is constrained by the MUST NOT on the output ofRandomScalar(once it is fixed for the concrete instantiation as I noted above).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 @FiloSottile exercising this specific edge case in age test vectors (
hybrid_identity,hybrid_low_order, the test case generator). So the probability of encountering this divergence is non-negligible, and we need to deal with it.I'm going to discuss what to do about the drafts themselves with CFRG. However, as many people have already shipped Xwing, I expect many existing implementations will be allowing non-contributory behaviour, so there will likely be domains in which it is required that
x-wingbehave the way it currently does. So I'm thinking that the simplest fix tox-wingis:DecapsulationKeyconstructors (or alternate constructors) that enables the caller to select whether or not non-contributory behaviour is rejected at decapsulation time.