Crypto Forum D. Connolly Internet-Draft SandboxAQ Intended status: Informational P. Schwabe Expires: 14 February 2025 MPI-SP & Radboud University B. E. Westerbaan Cloudflare 13 August 2024 X-Wing: general-purpose hybrid post-quantum KEM draft-connolly-cfrg-xwing-kem-03 Abstract This memo defines X-Wing, a general-purpose post-quantum/traditional hybrid key encapsulation mechanism (PQ/T KEM) built on X25519 and ML- KEM-768. About This Document This note is to be removed before publishing as an RFC. The latest revision of this draft can be found at https://dconnolly.github.io/draft-connolly-cfrg-xwing-kem/draft- connolly-cfrg-xwing-kem.html. Status information for this document may be found at https://datatracker.ietf.org/doc/draft-connolly-cfrg- xwing-kem/. Discussion of this document takes place on the Crypto Forum Research Group mailing list (mailto:cfrg@ietf.org), which is archived at https://mailarchive.ietf.org/arch/search/?email_list=cfrg. Subscribe at https://www.ietf.org/mailman/listinfo/cfrg/. Source for this draft and an issue tracker can be found at https://github.com/dconnolly/draft-connolly-cfrg-xwing-kem. Status of This Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet- Drafts is at https://datatracker.ietf.org/drafts/current/. Connolly, et al. Expires 14 February 2025 [Page 1] Internet-Draft xwing August 2024 Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." This Internet-Draft will expire on 14 February 2025. Copyright Notice Copyright (c) 2024 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/ license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1. Warning: ML-KEM-768 has not been standardised . . . . . . 3 1.2. Motivation . . . . . . . . . . . . . . . . . . . . . . . 3 1.3. Design goals . . . . . . . . . . . . . . . . . . . . . . 3 1.4. Not an interactive key-agreement . . . . . . . . . . . . 4 1.5. Not an authenticated KEM . . . . . . . . . . . . . . . . 4 1.6. Comparisons . . . . . . . . . . . . . . . . . . . . . . . 4 1.6.1. With HPKE X25519Kyber768Draft00 . . . . . . . . . . . 4 1.6.2. With generic combiner . . . . . . . . . . . . . . . . 5 2. Requirements Notation . . . . . . . . . . . . . . . . . . . . 5 3. Conventions and Definitions . . . . . . . . . . . . . . . . . 5 4. Cryptographic Dependencies . . . . . . . . . . . . . . . . . 5 5. X-Wing Construction . . . . . . . . . . . . . . . . . . . . . 6 5.1. Encoding and sizes . . . . . . . . . . . . . . . . . . . 7 5.2. Key generation . . . . . . . . . . . . . . . . . . . . . 7 5.2.1. Key derivation . . . . . . . . . . . . . . . . . . . 7 5.3. Combiner . . . . . . . . . . . . . . . . . . . . . . . . 8 5.4. Encapsulation . . . . . . . . . . . . . . . . . . . . . . 8 5.4.1. Derandomized . . . . . . . . . . . . . . . . . . . . 9 5.5. Decapsulation . . . . . . . . . . . . . . . . . . . . . . 9 5.5.1. Keeping expanded decapsulation key around . . . . . . 9 5.6. Use in HPKE . . . . . . . . . . . . . . . . . . . . . . . 10 5.7. Use in TLS 1.3 . . . . . . . . . . . . . . . . . . . . . 11 6. Security Considerations . . . . . . . . . . . . . . . . . . . 11 6.1. Binding properties . . . . . . . . . . . . . . . . . . . 11 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 12 8. TODO . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 9. References . . . . . . . . . . . . . . . . . . . . . . . . . 13 Connolly, et al. Expires 14 February 2025 [Page 2] Internet-Draft xwing August 2024 9.1. Normative References . . . . . . . . . . . . . . . . . . 13 9.2. Informative References . . . . . . . . . . . . . . . . . 13 Appendix A. Implementations . . . . . . . . . . . . . . . . . . 15 Appendix B. Machine-readable specification . . . . . . . . . . . 15 B.1. xwing.py . . . . . . . . . . . . . . . . . . . . . . . . 15 B.2. x25519.py . . . . . . . . . . . . . . . . . . . . . . . . 16 B.3. mlkem.py . . . . . . . . . . . . . . . . . . . . . . . . 18 Appendix C. Test vectors # TODO: replace with test vectors that re-use ML-KEM, X25519 values . . . . . . . . . . . . . . 25 Appendix D. Acknowledgments . . . . . . . . . . . . . . . . . . 29 Appendix E. Change log . . . . . . . . . . . . . . . . . . . . . 30 E.1. Since draft-connolly-cfrg-xwing-kem-02 . . . . . . . . . 30 E.2. Since draft-connolly-cfrg-xwing-kem-01 . . . . . . . . . 30 E.3. Since draft-connolly-cfrg-xwing-kem-00 . . . . . . . . . 30 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 30 1. Introduction 1.1. Warning: ML-KEM-768 has not been standardised X-Wing uses ML-KEM-768, which has not been standardised yet. Thus X-Wing is not finished, yet, and should not be used, yet. 1.2. Motivation There are many choices that can be made when specifying a hybrid KEM: the constituent KEMs; their security levels; the combiner; and the hash within, to name but a few. Having too many similar options are a burden to the ecosystem. The aim of X-Wing is to provide a concrete, simple choice for post- quantum hybrid KEM, that should be suitable for the vast majority of use cases. 1.3. Design goals By making concrete choices, we can simplify and improve many aspects of X-Wing. * Simplicity of definition. Because all shared secrets and cipher texts are fixed length, we do not need to encode the length. Using SHA3-256, we do not need HMAC-based construction. For the concrete choice of ML-KEM-768, we do not need to mix in its ciphertext, see Section 6. * Security analysis. Because ML-KEM-768 already assumes the Quantum Random Oracle Model (QROM), we do not need to complicate the analysis of X-Wing by considering stronger models. Connolly, et al. Expires 14 February 2025 [Page 3] Internet-Draft xwing August 2024 * Performance. Not having to mix in the ML-KEM-768 ciphertext is a nice performance benefit. Furthermore, by using SHA3-256 in the combiner, which matches the hashing in ML-KEM-768, this hash can be computed in one go on platforms where two-way Keccak is available. We aim for "128 bits" security (NIST PQC level 1). Although at the moment there is no peer-reviewed evidence that ML-KEM-512 does not reach this level, we would like to hedge against future cryptanalytic improvements, and feel ML-KEM-768 provides a comfortable margin. We aim for X-Wing to be usable for most applications, including specifically HPKE [RFC9180]. 1.4. Not an interactive key-agreement Traditionally most protocols use a Diffie-Hellman (DH) style non- interactive key-agreement. In many cases, a DH key agreement can be replaced by the interactive key-agreement afforded by a KEM without change in the protocol flow. One notable example is TLS [HYBRID] [XYBERTLS]. However, not all uses of DH can be replaced in a straight-forward manner by a plain KEM. 1.5. Not an authenticated KEM In particular, X-Wing is not, borrowing the language of [RFC9180], an _authenticated_ KEM. 1.6. Comparisons 1.6.1. With HPKE X25519Kyber768Draft00 X-Wing is most similar to HPKE's X25519Kyber768Draft00 [XYBERHPKE]. The key differences are: * X-Wing uses the final version of ML-KEM-768. * X-Wing hashes the shared secrets, to be usable outside of HPKE. * X-Wing has a simpler combiner by flattening DHKEM(X25519) into the final hash. * X-Wing does not hash in the ML-KEM-768 ciphertext. There is also a different KEM called X25519Kyber768Draft00 [XYBERTLS] which is used in TLS. This one should not be used outside of TLS, as it assumes the presence of the TLS transcript to ensure non malleability. Connolly, et al. Expires 14 February 2025 [Page 4] Internet-Draft xwing August 2024 1.6.2. With generic combiner The generic combiner of [I-D.ounsworth-cfrg-kem-combiners] can be instantiated with ML-KEM-768 and DHKEM(X25519). That achieves similar security, but: * X-Wing is more performant, not hashing in the ML-KEM-768 ciphertext, and flattening the DHKEM construction, with the same level of security. * X-Wing has a fixed 32 byte shared secret, instead of a variable shared secret. * X-Wing does not accept the optional counter and fixedInfo arguments. 2. Requirements Notation The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here. 3. Conventions and Definitions This document is consistent with all terminology defined in [I-D.driscoll-pqt-hybrid-terminology]. The following terms are used throughout this document to describe the operations, roles, and behaviors of HPKE: * concat(x0, ..., xN): returns the concatenation of byte strings. concat(0x01, 0x0203, 0x040506) = 0x010203040506. * random(n): return a pseudorandom byte string of length n bytes produced by a cryptographically-secure random number generator. 4. Cryptographic Dependencies X-Wing relies on the following primitives: * ML-KEM-768 post-quantum key-encapsulation mechanism (KEM) [MLKEM]: - ML-KEM-768.KeyGen(): Randomized algorithm to generate an ML- KEM-768 key pair (pk_M, sk_M) of an encapsulation key pk_M and decapsulation key sk_M. Note that ML-KEM-768.KeyGen() returns the keys in reverse order of GenerateKeyPair() defined below. Connolly, et al. Expires 14 February 2025 [Page 5] Internet-Draft xwing August 2024 - ML-KEM-768.Encaps(pk_M): Randomized algorithm to generate (ss_M, ct_M), an ephemeral 32 byte shared key ss_M, and a fixed-length encapsulation (ciphertext) of that key ct_M for encapsulation key pk_M. - ML-KEM-768.Decap(ct_M, sk_M): Deterministic algorithm using the decapsulation key sk_M to recover the shared key from ct_M. To generate deterministic test vectors, we also use - ML-KEM-768.KeyGen_internal(d, z): Algorithm to generate an ML- KEM-768 key pair (pk_M, sk_M) of an encapsulation key pk_M and decapsulation key sk_M. Note that ML-KEM-768.KeyGen() returns the keys in reverse order of GenerateKeyPair() defined below. d and z are both 32 byte strings. - ML-KEM-768.Encaps_internal(pk_M, m): Algorithm to generate (ss_M, ct_M), an ephemeral 32 byte shared key ss_M, and a fixed-length encapsulation (ciphertext) of that key ct_M for encapsulation key pk_M. m is a 32 byte string. * X25519 elliptic curve Diffie-Hellman key-exchange defined in Section 5 of [RFC7748]: - X25519(k,u): takes 32 byte strings k and u representing a Curve25519 scalar and curvepoint respectively, and returns the 32 byte string representing their scalar multiplication. - X25519_BASE: the 32 byte string representing the standard base point of Curve25519. In hex it is given by 0900000000000000000 000000000000000000000000000000000000000000000. Note that 9 is the standard basepoint for X25519, cf Section 6.1 of [RFC7748]. * Symmetric cryptography. - SHAKE128(message, outlen): The extendable-output function (XOF) defined in Section 6.2 of [FIPS202]. - SHA3-256(message): The hash defined in Section 6.1 of [FIPS202]. 5. X-Wing Construction Connolly, et al. Expires 14 February 2025 [Page 6] Internet-Draft xwing August 2024 5.1. Encoding and sizes X-Wing encapsulation key, decapsulation key, ciphertexts and shared secrets are all fixed length byte strings. Decapsulation key (private): 32 bytes Encapsulation key (public): 1216 bytes Ciphertext: 1120 bytes Shared secret: 32 bytes 5.2. Key generation An X-Wing keypair (decapsulation key, encapsulation key) is generated as follows. def expandDecapsulationKey(sk): expanded = SHAKE128(sk, 96) (pk_M, sk_M) = ML-KEM-768.KeyGen_internal(expanded[0:32], expanded[32:64]) sk_X = expanded[64:96] pk_X = X25519(sk_X, X25519_BASE) return (sk_M, sk_X, pk_M, pk_X) def GenerateKeyPair(): sk = random(32) (sk_M, sk_X, pk_M, pk_X) = expandDecapsulationKey(sk) return sk, concat(pk_M, pk_X) GenerateKeyPair() returns the 32 byte secret decapsulation key sk and the 1216 byte encapsulation key pk. Here and in the balance of the document for clarity we use the M and Xsubscripts for ML-KEM-768 and X25519 components respectively. 5.2.1. Key derivation For testing, it is convenient to have a deterministic version of key generation. An X-Wing implementation MAY provide the following derandomized variant of key generation. def GenerateKeyPairDerand(sk): sk_M, sk_X, pk_M, pk_X = expandDecapsulationKey(sk) return sk, concat(pk_M, pk_X) seed must be 32 bytes. Connolly, et al. Expires 14 February 2025 [Page 7] Internet-Draft xwing August 2024 GenerateKeyPairDerand() returns the 32 byte secret encapsulation key sk and the 32 byte decapsulation key pk. 5.3. Combiner Given 32 byte strings ss_M, ss_X, ct_X, pk_X, representing the ML- KEM-768 shared secret, X25519 shared secret, X25519 ciphertext (ephemeral public key) and X25519 public key respectively, the 32 byte combined shared secret is given by: def Combiner(ss_M, ss_X, ct_X, pk_X): return SHA3-256(concat( XWingLabel, ss_M, ss_X, ct_X, pk_X )) where XWingLabel is the following 6 byte ASCII string XWingLabel = concat( "\./", "/^\", ) In hex XWingLabel is given by 5c2e2f2f5e5c. 5.4. Encapsulation Given an X-Wing encapsulation key pk, encapsulation proceeds as follows. def Encapsulate(pk): pk_M = pk[0:1184] pk_X = pk[1184:1216] ek_X = random(32) ct_X = X25519(ek_X, X25519_BASE) ss_X = X25519(ek_X, pk_X) (ss_M, ct_M) = ML-KEM-768.Encaps(pk_M) ss = Combiner(ss_M, ss_X, ct_X, pk_X) ct = concat(ct_M, ct_X) return (ss, ct) pk is a 1216 byte X-Wing encapsulation key resulting from GeneratePublicKey() Connolly, et al. Expires 14 February 2025 [Page 8] Internet-Draft xwing August 2024 Encapsulate() returns the 32 byte shared secret ss and the 1120 byte ciphertext ct. 5.4.1. Derandomized For testing, it is convenient to have a deterministic version of encapsulation. An X-Wing implementation MAY provide the following derandomized function. def EncapsulateDerand(pk, eseed): pk_M = pk[0:1184] pk_X = pk[1184:1216] ek_X = eseed[32:64] ct_X = X25519(ek_X, X25519_BASE) ss_X = X25519(ek_X, pk_X) (ss_M, ct_M) = ML-KEM-768.EncapsDerand(pk_M, eseed[0:32]) ss = Combiner(ss_M, ss_X, ct_X, pk_X) ct = concat(ct_M, ct_X) return (ss, ct) pk is a 1216 byte X-Wing encapsulation key resulting from GeneratePublicKey() eseed MUST be 64 bytes. EncapsulateDerand() returns the 32 byte shared secret ss and the 1120 byte ciphertext ct. 5.5. Decapsulation def Decapsulate(ct, sk): (sk_M, sk_X, pk_M, pk_X) = expandDecapsulationKey(sk) ct_M = ct[0:1088] ct_X = ct[1088:1120] ss_M = ML-KEM-768.Decapsulate(ct_M, sk_M) ss_X = X25519(sk_X, ct_X) return Combiner(ss_M, ss_X, ct_X, pk_X) ct is the 1120 byte ciphertext resulting from Encapsulate() sk is a 32 byte X-Wing decapsulation key resulting from GenerateKeyPair() Decapsulate() returns the 32 byte shared secret. 5.5.1. Keeping expanded decapsulation key around For efficiency, an implementation MAY cache the result of expandDecapsulationKey. This is useful in two cases: 1. If multiple ciphertexts for the same key are decapsulated. Connolly, et al. Expires 14 February 2025 [Page 9] Internet-Draft xwing August 2024 2. If a ciphertext is decapsulated for a key that has just been generated. This happen on the client-side for TLS. A typical API pattern to achieve this optimization is to have an opaque decapsulation key object that hides the cached values. For instance, such an API could have the following functions. 1. UnpackDecapsulationKey(sk) takes a decapsulation key, and returns an opaque object that contains the expanded decapsulation key. 2. Decapsulate(ct, esk) takes a ciphertext and an expanded decapsulation key. 3. GenerateKeyPair() returns an encapsulation key and an expanded decapsulation key. 4. PackDecapsulationKey(sk) takes an expanded decapsulation key, and returns the packed decapsulation key. The expanded decapsulation key could cache more computation, such as the expanded matrix A in ML-KEM. Any such expanded decapsulation key MUST NOT be transmitted between implementations, as this could break the security analysis of X-Wing. In particular, the MAL-BIND-K-PK and MAL-BIND-K-CT binding properties of X-Wing do not hold when transmitting the regular ML-KEM decapsulation key. 5.6. Use in HPKE X-Wing satisfies the HPKE KEM interface as follows. The SerializePublicKey, DeserializePublicKey, SerializePrivateKey and DeserializePrivateKey are the identity functions, as X-Wing keys are fixed-length byte strings, see Section 5.1. DeriveKeyPair() is given by def DeriveKeyPair(ikm): return GenerateKeyPairDerand(SHAKE128(ikm, 96)) where the HPKE private key and public key are the X-Wing decapsulation key and encapsulation key respectively. The argument ikm to DeriveKeyPair() SHOULD be at least 32 octets in length. (This is contrary to [RFC9180] which stipulates it should be at least Nsk=2432 octets in length.) Connolly, et al. Expires 14 February 2025 [Page 10] Internet-Draft xwing August 2024 Encap() is Encapsulate() from Section 5.4. Decap() is Decapsulate() from Section 5.5. X-Wing is not an authenticated KEM: it does not support AuthEncap() and AuthDecap(), see Section 1.5. Nsecret, Nenc, Npk, and Nsk are defined in Section 7. 5.7. Use in TLS 1.3 For the client's share, the key_exchange value contains the X-Wing encapsulation key. For the server's share, the key_exchange value contains the X-Wing ciphertext. 6. Security Considerations Informally, X-Wing is secure if SHA3 is secure, and either X25519 is secure, or ML-KEM-768 is secure. More precisely, if SHA3-256, SHA3-512, SHAKE-128, and SHAKE-256 may be modelled as a random oracle, then the IND-CCA security of X-Wing is bounded by the IND-CCA security of ML-KEM-768, and the gap-CDH security of Curve25519, see [PROOF]. The security of X-Wing relies crucially on the specifics of the Fujisaki-Okamoto transformation used in ML-KEM-768: the X-Wing combiner cannot be assumed to be secure, when used with different KEMs. In particular it is not known to be safe to leave out the post-quantum ciphertext from the combiner in the general case. 6.1. Binding properties Some protocols rely on further properties of the KEM. X-Wing satisfies the binding properties MAL-BIND-K-PK and MAL-BIND-K-CT (TODO: reference to proof). This implies [KSMW] X-Wing also satisfies * MAL-BIND-K,CT-PK * MAL-BIND-K,PK-CT * LEAK-BIND-K-PK * LEAK-BIND-K-CT Connolly, et al. Expires 14 February 2025 [Page 11] Internet-Draft xwing August 2024 * LEAK-BIND-K,CT-PK * LEAK-BIND-K,PK-CT * HON-BIND-K-PK * HON-BIND-K-CT * HON-BIND-K,CT-PK * HON-BIND-K,PK-CT In contrast, ML-KEM on its own does not achieve MAL-BIND-K-PK, MAL- BIND-K-CT, nor MAL-BIND-K,PK-CT. [SCHMIEG] 7. IANA Considerations This document requests/registers a new entry to the "HPKE KEM Identifiers" registry. Value: TBD (please) KEM: X-Wing Nsecret: 32 Nenc: 1120 Npk: 1216 Nsk: 32 Auth: no Reference: This document Furthermore, this document requests/registers a new entry to the TLS Named Group (or Supported Group) registry, according to the procedures in Section 6 of [TLSIANA]. Value: TBD (please) Description: X-Wing DTLS-OK: Y Recommended: Y Connolly, et al. Expires 14 February 2025 [Page 12] Internet-Draft xwing August 2024 Reference: This document Comment: PQ/T hybrid of X25519 and ML-KEM-768 8. TODO * Which validation do we want to require? 9. References 9.1. Normative References [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, . [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, May 2017, . 9.2. Informative References [FIPS202] National Institute of Standards and Technology, "FIPS 202: SHA-3 Standard: Permutation-Based Hash and Extendable- Output Functions", n.d., . [HYBRID] Stebila, D., Fluhrer, S., and S. Gueron, "Hybrid key exchange in TLS 1.3", Work in Progress, Internet-Draft, draft-stebila-tls-hybrid-design-03, 12 February 2020, . [I-D.driscoll-pqt-hybrid-terminology] D, F., "Terminology for Post-Quantum Traditional Hybrid Schemes", Work in Progress, Internet-Draft, draft- driscoll-pqt-hybrid-terminology-02, 7 March 2023, . Connolly, et al. Expires 14 February 2025 [Page 13] Internet-Draft xwing August 2024 [I-D.ounsworth-cfrg-kem-combiners] Ounsworth, M., Wussler, A., and S. Kousidis, "Combiner function for hybrid key encapsulation mechanisms (Hybrid KEMs)", Work in Progress, Internet-Draft, draft-ounsworth- cfrg-kem-combiners-05, 31 January 2024, . [KSMW] Kraemer, J., Struck, P., and M. Weishaupl, "Binding Security of Implicitly-Rejecting KEMs and Application to BIKE and HQC", n.d., . [MLKEM] National Institute of Standards and Technology, "FIPS 203: Module-Lattice-Based Key-Encapsulation Mechanism Standard", n.d., . [PROOF] Barbosa, M., Connolly, D., Duarte, J., Kaiser, A., Schwabe, P., Varner, K., and B. E. Westerbraan, "X-Wing: The Hybrid KEM You’ve Been Looking For", n.d., . [RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves for Security", RFC 7748, DOI 10.17487/RFC7748, January 2016, . [RFC9180] Barnes, R., Bhargavan, K., Lipp, B., and C. Wood, "Hybrid Public Key Encryption", RFC 9180, DOI 10.17487/RFC9180, February 2022, . [SCHMIEG] Schmieg, S., "Unbindable Kemmy Schmidt: ML-KEM is neither MAL-BIND-K-CT nor MAL-BIND-K-PK", n.d., . [TLSIANA] Salowey, J. A. and S. Turner, "IANA Registry Updates for TLS and DTLS", Work in Progress, Internet-Draft, draft- ietf-tls-rfc8447bis-09, 30 April 2024, . [XYBERHPKE] Westerbaan, B. and C. A. Wood, "X25519Kyber768Draft00 hybrid post-quantum KEM for HPKE", Work in Progress, Internet-Draft, draft-westerbaan-cfrg-hpke-xyber768d00-03, 14 May 2024, . Connolly, et al. Expires 14 February 2025 [Page 14] Internet-Draft xwing August 2024 [XYBERTLS] Westerbaan, B. and D. Stebila, "X25519Kyber768Draft00 hybrid post-quantum key agreement", Work in Progress, Internet-Draft, draft-tls-westerbaan-xyber768d00-03, 24 September 2023, . Appendix A. Implementations * Go - CIRCL (https://github.com/cloudflare/circl/pull/471) - Filippo (https://github.com/FiloSottile/mlkem768) * Rust - xwing-kem.rs (https://github.com/rugo/xwing-kem.rs]) Note: implements the older -00 version of this memo at the time of writing. Appendix B. Machine-readable specification For the convenience of implementors, we provide a reference specification in Python. This is a specification; not production ready code: it should not be deployed as-is, as it leaks the private key by its runtime. B.1. xwing.py # WARNING This is a specification of X-Wing; not a production-ready # implementation. It is slow and does not run in constant time. # Requires the CryptoDome for SHAKE, and pytest for testing. To install, run # # pip install pycryptodome pytest import binascii import hashlib import mlkem import x25519 XWingLabel = br""" \./ /^\ """.replace(b'\n', b'').replace(b' ', b'') Connolly, et al. Expires 14 February 2025 [Page 15] Internet-Draft xwing August 2024 assert len(XWingLabel) == 6 assert binascii.hexlify(XWingLabel) == b'5c2e2f2f5e5c' def expandDecapsulationKey(seed): expanded = hashlib.shake_128(seed).digest(length=96) pkM, skM = mlkem.KeyGen(expanded[0:64], mlkem.params768) skX = expanded[64:96] pkX = x25519.X(skX, x25519.BASE) return skM, skX, pkM, pkX def GenerateKeyPairDerand(seed): assert len(seed) == 32 skM, skX, pkM, pkX = expandDecapsulationKey(seed) return seed, pkM + pkX def Combiner(ssM, ssX, ctX, pkX): return hashlib.sha3_256( XWingLabel + ssM + ssX + ctX + pkX ).digest() def EncapsulateDerand(pk, eseed): assert len(eseed) == 64 assert len(pk) == 1216 pkM = pk[0:1184] pkX = pk[1184:1216] ekX = eseed[32:64] ctX = x25519.X(ekX, x25519.BASE) ssX = x25519.X(ekX, pkX) ctM, ssM = mlkem.Enc(pkM, eseed[0:32], mlkem.params768) ss = Combiner(ssM, ssX, ctX, pkX) return ss, ctM + ctX def Decapsulate(ct, sk): assert len(ct) == 1120 assert len(sk) == 32 ctM = ct[0:1088] ctX = ct[1088:1120] skM, skX, pkM, pkX = expandDecapsulationKey(sk) ssM = mlkem.Dec(skM, ctM, mlkem.params768) ssX = x25519.X(skX, ctX) return Combiner(ssM, ssX, ctX, pkX) B.2. x25519.py Connolly, et al. Expires 14 February 2025 [Page 16] Internet-Draft xwing August 2024 # WARNING This is a specification of X25519; not a production-ready # implementation. It is slow and does not run in constant time. p = 2**255 - 19 a24 = 121665 BASE = b'\x09' + b'\x00'*31 def decode(bs): return sum(bs[i] << 8*i for i in range(32)) % p def decodeScalar(k): bs = list(k) bs[0] &= 248 bs[31] &= 127 bs[31] |= 64 return decode(bs) # See rfc7748 §5. def X(k, u): assert len(k) == 32 assert len(u) == 32 k = decodeScalar(k) u = decode(u) x1, x2, x3, z2, z3, swap = u, 1, u, 0, 1, 0 for t in range(255, -1, -1): kt = (k >> t) & 1 swap ^= kt if swap == 1: x3, x2 = x2, x3 z3, z2 = z2, z3 swap = kt A = x2 + z2 AA = (A*A) % p B = x2 - z2 BB = (B*B) % p E = AA - BB C = x3 + z3 D = x3 - z3 DA = (D*A) % p CB = (C*B) % p x3 = DA + CB x3 = (x3 * x3) % p z3 = DA - CB z3 = (x1 * z3 * z3) % p Connolly, et al. Expires 14 February 2025 [Page 17] Internet-Draft xwing August 2024 x2 = (AA * BB) % p z2 = (E * (AA + (a24 * E) % p)) % p if swap == 1: x3, x2 = x2, x3 z2, z3 = z3, z2 ret = (x2 * pow(z2, p-2, p)) % p return bytes((ret >> 8*i) & 255 for i in range(32)) B.3. mlkem.py # WARNING This is a specification of Kyber; not a production ready # implementation. It is slow and does not run in constant time. # Requires the CryptoDome for SHAKE. To install, run # # pip install pycryptodome pytest from Crypto.Hash import SHAKE128, SHAKE256 import io import hashlib import functools import collections from math import floor q = 3329 nBits = 8 zeta = 17 eta2 = 2 n = 2**nBits inv2 = (q+1)//2 # inverse of 2 params = collections.namedtuple('params', ('k', 'du', 'dv', 'eta1')) params512 = params(k = 2, du = 10, dv = 4, eta1 = 3) params768 = params(k = 3, du = 10, dv = 4, eta1 = 2) params1024 = params(k = 4, du = 11, dv = 5, eta1 = 2) def smod(x): r = x % q if r > (q-1)//2: r -= q return r # Rounds to nearest integer with ties going up Connolly, et al. Expires 14 February 2025 [Page 18] Internet-Draft xwing August 2024 def Round(x): return int(floor(x + 0.5)) def Compress(x, d): return Round((2**d / q) * x) % (2**d) def Decompress(y, d): assert 0 <= y and y <= 2**d return Round((q / 2**d) * y) def BitsToWords(bs, w): assert len(bs) % w == 0 return [sum(bs[i+j] * 2**j for j in range(w)) for i in range(0, len(bs), w)] def WordsToBits(bs, w): return sum([[(b >> i) % 2 for i in range(w)] for b in bs], []) def Encode(a, w): return bytes(BitsToWords(WordsToBits(a, w), 8)) def Decode(a, w): return BitsToWords(WordsToBits(a, 8), w) def brv(x): """ Reverses a 7-bit number """ return int(''.join(reversed(bin(x)[2:].zfill(nBits-1))), 2) class Poly: def __init__(self, cs=None): self.cs = (0,)*n if cs is None else tuple(cs) assert len(self.cs) == n def __add__(self, other): return Poly((a+b) % q for a,b in zip(self.cs, other.cs)) def __neg__(self): return Poly(q-a for a in self.cs) def __sub__(self, other): return self + -other def __str__(self): return f"Poly({self.cs}" def __eq__(self, other): return self.cs == other.cs def NTT(self): Connolly, et al. Expires 14 February 2025 [Page 19] Internet-Draft xwing August 2024 cs = list(self.cs) layer = n // 2 zi = 0 while layer >= 2: for offset in range(0, n-layer, 2*layer): zi += 1 z = pow(zeta, brv(zi), q) for j in range(offset, offset+layer): t = (z * cs[j + layer]) % q cs[j + layer] = (cs[j] - t) % q cs[j] = (cs[j] + t) % q layer //= 2 return Poly(cs) def RefNTT(self): # Slower, but simpler, version of the NTT. cs = [0]*n for i in range(0, n, 2): for j in range(n // 2): z = pow(zeta, (2*brv(i//2)+1)*j, q) cs[i] = (cs[i] + self.cs[2*j] * z) % q cs[i+1] = (cs[i+1] + self.cs[2*j+1] * z) % q return Poly(cs) def InvNTT(self): cs = list(self.cs) layer = 2 zi = n//2 while layer < n: for offset in range(0, n-layer, 2*layer): zi -= 1 z = pow(zeta, brv(zi), q) for j in range(offset, offset+layer): t = (cs[j+layer] - cs[j]) % q cs[j] = (inv2*(cs[j] + cs[j+layer])) % q cs[j+layer] = (inv2 * z * t) % q layer *= 2 return Poly(cs) def MulNTT(self, other): """ Computes self o other, the multiplication of self and other in the NTT domain. """ cs = [None]*n for i in range(0, n, 2): a1 = self.cs[i] a2 = self.cs[i+1] Connolly, et al. Expires 14 February 2025 [Page 20] Internet-Draft xwing August 2024 b1 = other.cs[i] b2 = other.cs[i+1] z = pow(zeta, 2*brv(i//2)+1, q) cs[i] = (a1 * b1 + z * a2 * b2) % q cs[i+1] = (a2 * b1 + a1 * b2) % q return Poly(cs) def Compress(self, d): return Poly(Compress(c, d) for c in self.cs) def Decompress(self, d): return Poly(Decompress(c, d) for c in self.cs) def Encode(self, d): return Encode(self.cs, d) def sampleUniform(stream): cs = [] while True: b = stream.read(3) d1 = b[0] + 256*(b[1] % 16) d2 = (b[1] >> 4) + 16*b[2] assert d1 + 2**12 * d2 == b[0] + 2**8 * b[1] + 2**16*b[2] for d in [d1, d2]: if d >= q: continue cs.append(d) if len(cs) == n: return Poly(cs) def CBD(a, eta): assert len(a) == 64*eta b = WordsToBits(a, 8) cs = [] for i in range(n): cs.append((sum(b[:eta]) - sum(b[eta:2*eta])) % q) b = b[2*eta:] return Poly(cs) def XOF(seed, j, i): h = SHAKE128.new() h.update(seed + bytes([j, i])) return h def PRF1(seed, nonce): assert len(seed) == 32 h = SHAKE256.new() h.update(seed + bytes([nonce])) Connolly, et al. Expires 14 February 2025 [Page 21] Internet-Draft xwing August 2024 return h def PRF2(seed, msg): assert len(seed) == 32 h = SHAKE256.new() h.update(seed + msg) return h.read(32) def G(seed): h = hashlib.sha3_512(seed).digest() return h[:32], h[32:] def H(msg): return hashlib.sha3_256(msg).digest() class Vec: def __init__(self, ps): self.ps = tuple(ps) def NTT(self): return Vec(p.NTT() for p in self.ps) def InvNTT(self): return Vec(p.InvNTT() for p in self.ps) def DotNTT(self, other): """ Computes the dot product in NTT domain. """ return sum((a.MulNTT(b) for a, b in zip(self.ps, other.ps)), Poly()) def __add__(self, other): return Vec(a+b for a,b in zip(self.ps, other.ps)) def Compress(self, d): return Vec(p.Compress(d) for p in self.ps) def Decompress(self, d): return Vec(p.Decompress(d) for p in self.ps) def Encode(self, d): return Encode(sum((p.cs for p in self.ps), ()), d) def __eq__(self, other): return self.ps == other.ps def EncodeVec(vec, w): return Encode(sum([p.cs for p in vec.ps], ()), w) def DecodeVec(bs, k, w): cs = Decode(bs, w) Connolly, et al. Expires 14 February 2025 [Page 22] Internet-Draft xwing August 2024 return Vec(Poly(cs[n*i:n*(i+1)]) for i in range(k)) def DecodePoly(bs, w): return Poly(Decode(bs, w)) class Matrix: def __init__(self, cs): """ Samples the matrix uniformly from seed rho """ self.cs = tuple(tuple(row) for row in cs) def MulNTT(self, vec): """ Computes matrix multiplication A*vec in the NTT domain. """ return Vec(Vec(row).DotNTT(vec) for row in self.cs) def T(self): """ Returns transpose of matrix """ k = len(self.cs) return Matrix((self.cs[j][i] for j in range(k)) for i in range(k)) def sampleMatrix(rho, k): return Matrix([[sampleUniform(XOF(rho, j, i)) for j in range(k)] for i in range(k)]) def sampleNoise(sigma, eta, offset, k): return Vec(CBD(PRF1(sigma, i+offset).read(64*eta), eta) for i in range(k)) def constantTimeSelectOnEquality(a, b, ifEq, ifNeq): # WARNING! In production code this must be done in a # data-independent constant-time manner, which this implementation # is not. In fact, many more lines of code in this # file are not constant-time. return ifEq if a == b else ifNeq def InnerKeyGen(seed, params): assert len(seed) == 32 rho, sigma = G(seed + bytes([params.k])) A = sampleMatrix(rho, params.k) s = sampleNoise(sigma, params.eta1, 0, params.k) e = sampleNoise(sigma, params.eta1, params.k, params.k) sHat = s.NTT() eHat = e.NTT() tHat = A.MulNTT(sHat) + eHat pk = EncodeVec(tHat, 12) + rho sk = EncodeVec(sHat, 12) return (pk, sk) def InnerEnc(pk, msg, seed, params): Connolly, et al. Expires 14 February 2025 [Page 23] Internet-Draft xwing August 2024 assert len(msg) == 32 tHat = DecodeVec(pk[:-32], params.k, 12) if EncodeVec(tHat, 12) != pk[:-32]: raise Exception("ML-KEM public key not normalized") rho = pk[-32:] A = sampleMatrix(rho, params.k) r = sampleNoise(seed, params.eta1, 0, params.k) e1 = sampleNoise(seed, eta2, params.k, params.k) e2 = sampleNoise(seed, eta2, 2*params.k, 1).ps[0] rHat = r.NTT() u = A.T().MulNTT(rHat).InvNTT() + e1 m = Poly(Decode(msg, 1)).Decompress(1) v = tHat.DotNTT(rHat).InvNTT() + e2 + m c1 = u.Compress(params.du).Encode(params.du) c2 = v.Compress(params.dv).Encode(params.dv) return c1 + c2 def InnerDec(sk, ct, params): split = params.du * params.k * n // 8 c1, c2 = ct[:split], ct[split:] u = DecodeVec(c1, params.k, params.du).Decompress(params.du) v = DecodePoly(c2, params.dv).Decompress(params.dv) sHat = DecodeVec(sk, params.k, 12) return (v - sHat.DotNTT(u.NTT()).InvNTT()).Compress(1).Encode(1) def KeyGen(seed, params): assert len(seed) == 64 z = seed[32:] pk, sk2 = InnerKeyGen(seed[:32], params) h = H(pk) return (pk, sk2 + pk + h + z) def Enc(pk, seed, params): assert len(seed) == 32 K, r = G(seed + H(pk)) ct = InnerEnc(pk, seed, r, params) return (ct, K) def Dec(sk, ct, params): sk2 = sk[:12 * params.k * n//8] pk = sk[12 * params.k * n//8 : 24 * params.k * n//8 + 32] h = sk[24 * params.k * n//8 + 32 : 24 * params.k * n//8 + 64] z = sk[24 * params.k * n//8 + 64 : 24 * params.k * n//8 + 96] m2 = InnerDec(sk, ct, params) K2, r2 = G(m2 + h) ct2 = InnerEnc(pk, m2, r2, params) return constantTimeSelectOnEquality( Connolly, et al. Expires 14 February 2025 [Page 24] Internet-Draft xwing August 2024 ct2, ct, K2, # if ct == ct2 PRF2(z, ct), # if ct != ct2 ) Appendix C. Test vectors # TODO: replace with test vectors that re-use ML-KEM, X25519 values seed 7f9c2ba4e88f827d616045507605853ed73b8093f6efbc88eb1a6eacfa66ef26 sk 7f9c2ba4e88f827d616045507605853ed73b8093f6efbc88eb1a6eacfa66ef26 pk ec367a5c586f3817a98698b5fc4082907a8873909a7e79ce5d18c84d425362c7956aeb61 0b9b68949107335ba676142aadd93ed27211c57c2d319c805a01204f5c2948158759f063 27825379ac8428113e59c215a582a50d0c89505390ecf868e9270cf96c4fa0f94793b599 8b38a1e3c9039bf4147695c08413a7e190b5d9a8c22a4759bda51fd11064a21c4dadc3bc 28510697f3a442205214a6cd3f54a9ba45a309437d372654e2c6226e8640810128597abe 9042932be6af1eb71a6ef156a9baa4c0c05764a8314fc1565d1825a5eb3604f278bc175b 0666af85a13d97c650a571564eca080a36727bf76460c81a842895e87c9d4fc9c57fc6b1 49692eed526fb632cd476232a9f3035b4c96d6a14f8cf92e2735a766c7a168e6034369b6 c17750afcc483af5654b82439f6b9a136cb4f47986dab4c427327675061d7b130572e207 1f22339a997cf1e1618133ac8b8acd1d7177943c0d1971c84fc48cce7c4c00b95a9f7741 4c4c07fb3b0c6d51144d36cc8be4ae9b236f89accdd4336bcff11f4fc997ef13c01bb45d 4001b1949749ebf14e469788ebdbbeced68ba149ca81aab111d0756f1074b7e60031da43 7709027c4676edc35318a74b1308a8f2b6aef905668bb031a6403ab7a328ba74b9231866 e287424b42acd1d69b6eab657f2340f433717e581a048ac9be5196fedc36ec212de48149 bbec9e07ccc8b1f50293e78e469079a3d3588ae146c1859ced376dc13040c4535f253cb4 0a61b8be95b8b6606d2f607c1035a23566ade289391829ae61cacd36d247a3a864bab43b 23198481f10f9a5b25b64cb6314baaa0282c59792fe987687b06cb23b397302962cacb9f 7327301310c7e66b9f5aab93b0f9ba9b5633a1db72fa637c4f6611ca9117788bb335b80d d0c989af6b0d8fc9b5c3707a1d848b220a3002b612c294a004c4b52ad1b4b57619d960a6 59646622a73de9a55de1191dcf8253b50bb2d6e0bed3ab12c4bb81b2826afec87dabccb5 6b74bdd4c844005097ac94cafea715a57b6e20b49e49869bfdc8015e37a0b3f942f9467b 7c749f76c951623340660bbd88c16dfbf5176ca855689bbf7287391935b71eda6ef8bab6 a2ea6e3095a1f2719d10b205130982942c1bbad0bb6c1901879587ac3a290ff20043010e 181337eb2a20eda44b24e07f12255bbe78279adc51de276d2e602b72dc1ed7489240ab2c 4e672b527082e363b0b5f51ffbbb79d724435484ca0c7874aff654d61a254eb7ae420b4d 0a9958a48144e013972cda7f8adcc7c36206725221a79426e7c798e99cb645198c506194 c3da36415501ea6bccb377921f0172cf9634232b211d626074020cdec29c4d59248c4056 88f15d6bc556f72bb01d11ae0b2167d33bb2389a2d6dec911a3513fc680d21a265c3f3b1 90e983d5bab1ae471802024edfd96a2cd51176261107c29f5050ab52ca7210db8668bb80 064744cb4236e3ac6df26477c8d80ac9a60ca8796f95c5acd960b2f541027c2378ac1570 8070acfa528a8473248458cb3cf23108949369009b523a945fc70cf3c3add61c4fbbdba9 1d74c954682182d30071e71648f1b266ea343ab97547c9a3462969ca911a67667e1cb884 67942eea1ae5d06ac215e64de876fda67c22f74ffe26ff8b56cf606ff799d4a89bb6cee3 f79506960abcda4e65d8197e0c992244dae91c21068915647f844f49 eseed 3cb1eea988004b93103cfb0aeefd2a686e01fa4a58e8a3639ca8a1e3f9ae57e235b8cc87 3c23dc62b8d260169afa2f75ab916a58d974918835d25e6a435085b2 Connolly, et al. Expires 14 February 2025 [Page 25] Internet-Draft xwing August 2024 ct b45085dc0c2abecd811415924ade853ae88c8dcf8007e6d79bae036648290472989d6f21 87bc6d39d0f739d315fc03cd8a373ad8927b0db7d419385c9b867b351815a95e7f0f915e 7356eacce50d328a572565c538b282dc539e4d4b106ba5add0656efb8bd670a32e89fb64 2eae8235fdc181b2a3ae21d5f3374ce6955484c4fa9dd0a8e454f73e840fa5085070d107 89e3cc1f6b4274fad17c041c23a8c512e3be23962de5028f427273f5a53dcf43425e9183 d304abf22b306fb6add4c89a7b54fa93d50393882bad23e06c58c03cbb765a9d1324be9f e7b399b7a0f7486b8b03fe186dc5e9ee9738f48e7ef3127a6db992097263dbc51fb227df ab0aae2758d8cfd8573c227e19d245503518ee7f533976236075d50f95b5bd101c670714 209f264c01e31b80295fea54f42e1c62856042bafbe72e1ef8abe12f58b02e4eb6378bc0 e13339395b6faf95e2738c509975bc1806d1cbad3e586cfa2ba09b2bde20dfb0aaba2cdb 583ae33c812109a1095adc697befcbd0be0aafee1e41979be026747c918646d38874320a af404f28cda6d6d7a7a5386f487983a69064b8bc1fc0a2998a55bb442cfa9b61581263b3 3f5ae25c4a1efdd890c3fae4481995eaabf1d4a27addc239b99bb8aefec73a9f9c158190 26d35d48e11de426f7f113e8fe843db011934c8052300cca9fc870f390648ab47ff54362 9949c5459fae763871e949a4d2f61caf9f6afcfbc00e5b71f85c791ae04d4db90ed09811 382a8a2a9707f76cbeaa371eb64d2a8d82e1f65b42e0928e5afa288062ca0b28317c9b36 b27f14161d84d71db377efc6f0f2d7b57594e8fc432c2dbcbc4f55fc3563894a5be4ad40 a2aa34ca48db0df5b6d8ae51777bf7c6925a40e651629351e86480594f438ee3a34daa7a 2581e0f573489e71b23bf76dcf8fd3d9c29ca6bcc699753d54b876adb0c0514ae887e102 9ef195fc3cddb51d03cb518f8dad5044e2299f601b961fa38da47d1e940b58e864cf5dbe 85a21dafc40b2355144307d09bd2bf8b1c762e7bd5e27308d903e165ecc6176b74564329 bf37e1ce9257d113897c0099aaa17937735dd13931c5742f5cceaec475c1886bfef42252 a7ad66f4d4b925faec8e1a9ce0623a895e9c00c57781e66404311720bb94ff0c019081f9 b846d72451179308f17d4c7ac324a5bbbb914411840364b9b65f6e189c60ef842c155df1 f96b84f03521803d3cb7016629b4c8159fb0ad3ce1da5e49ceba56f6881be8432200c86e 291a4cd3b5ea9001e99b418b9d44a3fa0cedb6acf3feef30df4307480967e765530d6183 add3a198d796a4535abbd8be92d8c2f9ec4217fd459326f0f090764b57207d4cb108af34 abf120c182011e66393edf2f446f606acb5b0ad5afb4ea5866e4d4158280885bd0ad4dec ed058ced8035afc85d1e03c00b7c23b4e74abe8ba12b86a027064bf88443aadb38c82bc6 21b6880d3e88f6c3bcb03a015d1cc306f7d575ee778cd1b52902be555b4e02b74cfd310b d83ab4c81f97fc12e56f17576740ce2a32fc5145030145cfb97e63e0e41d354274a079d3 e6fb2e15 ss 555a071a8b7520ae95f8e635de8a5f87dbddcbef900576aad29ecdda5459c15a seed badfd6dfaac359a5efbb7bcc4b59d538df9a04302e10c8bc1cbf1a0b3a5120ea sk badfd6dfaac359a5efbb7bcc4b59d538df9a04302e10c8bc1cbf1a0b3a5120ea pk 8b92541ff9b60f49baf1282229853e3249427656bda5440c6f258df3db3382c2b5674590 fd713397954b785694807938653603666b103ea8709b002a420a7bee64161015631c6c32 e7c6a53d525eb44940733667447439d830280e7ba75f501958a09ce8e3b7d0038a7bbc22 e7025700686662f128ce0771d92a8c8af4cf2a414c11b19c695b234bb447471c67aa5a94 bad89e192563bb33662fda91d24845f0e3b08eac79d03635fe81610e80bb8bcb92fc05cc 5a12c7d7a5340a81c031d55a6b81b7469ca14c72cf2634b686cac7060a759700d0188511 9a557a3a23487a5432dce5932f3a3b0c85972b5caf711c5f21066ff7011743d16a22da06 b7e8ba22d390746034617b2f47c0c392f926a9665ba89244f5b30a1e9388c2a4749c9b70 c7ba3a2c18c32481373a35acf8157a561613ddb693040b8f319876a7c165ab53aee1b407 1d782f84e6cb415565ed4c0c00222e1a5c41bd8485eb40a4053183f2753f1c5243a53662 Connolly, et al. Expires 14 February 2025 [Page 26] Internet-Draft xwing August 2024 4f940029307d5d984934d05ce623066bc29ea6b93a3da99c927218f366ae98e168b30c53 6dec49f108c9f353073e347137604597053f20a03abd71280d235022a03c9d0a43ee2934 0845ca51f848056ca98506b91f61b26b9582a0556748a56f36d115a0365da0390b22db09 d8c1029d3494ce811878e68e56295c38712c16f098f89b5a5953b568e7618af069a63c0f 39ca70f73a0f2cbb150a64884e2c3d491b5013689741715b02227176d767715060da0439 f39698283428e4b939f9fbbde627ce1be73c19fb54d082b7399383b5ac44e1205dfae12e 6672601a4cc89a3a80677447e4c53b127b05c528a0e95cb512eb9dc8799ec00c38e427bf 5ff94775877b87109c69b0bd367223bfe6a65f8b889eeb7a2ad80ea6001654d350cd6654 20d34f80d99fef72cb124089331585d6c5bd6d057f8e319352db71878196e6587d2d018f 1496043bac9fd9106d53c30510b6abefd80d3d6319f1cbb5937b3d808706f888c2c07840 d3a0c53565603909073660b83fc318c775b34909001054b82f9a0cc8155a3b002a12a414 bad1a69dc2aa1aa489af7965a16989148467539352dd1794356473a3aca6668b5cd006ab 972236d7484536ec1029d845fb386c9e4a539e593bfb225f558459e28274fccb0a05ac47 528b459171c76764a47ed8b461f3124c174aa0c51778299a0a299882a63e88510d9adb47 9c30b47950974b9556cef689bf5006354c4fe11684a9d057f09c213ea63c32228ce5657f 336a88bda34fff435d5a682a44312da5bc8d8a6b7bfc1a60fab9ce7a268c00dc040f04d0 b651adf4e31ad6b36981b7a1ccd666a80b0f89928b81b686ce3c6b18e4a921c0a4f4d26b f0cb568db77908424b47d8031bb860c19a1f5eb131e838aa5e628bf29b2dfadc0c6e6c8d cb8277b783b61b69a303007f3a49018f3592c505618f3c3aeaf775995c6097671ea0cab7 633c612a24a144dc81abc28fcc62b2b69a1e93d8b6e93ca81a2b9cd49bc1b5373af699aa efac7ba66c110198ad91555b9a46ac19322870322e16ec8cfee384c241bc21e28d5a48af 52d68f37a8bb0669b7b1630889083f5e6bcd99007183014304553ed8d602a3b12df2b26e 846c4f1a04eed59a7f1855399a47636186d461695ee4ff1f2558e47c05824395bb484b68 6c33a4dbc1d068a4423693afc0154b88c241340fa9bf6623011dea34 eseed 17cda7cfad765f5623474d368ccca8af0007cd9f5e4c849f167a580b14aabdefaee7eef4 7cb0fca9767be1fda69419dfb927e9df07348b196691abaeb580b32d ct 04f8b82b60ce1b47119f9b199c02a0be5b709394e6171c8b272509371681701c4d99bc4b ee7f16772bb596271f8c80ed215cf777ce1507785a7506b3cc8a9ee516f0f3a90f4af6cf f30115a944dc2856b6ec40ff9678dcfd81563ea5db1a4d269c8f1a7fdfbb9f6b44bdaee6 a7126a143097e758463ad827298990b34170f655591e640a3b9db75610918534b3741283 e2a0c50c716a8263e8dda9db348e7bab6d1a249f27fb899d05a3bc1cbb2ab0f7b1a378b1 803bb83af411cf434fba3cd28bcb19ebedb675111359a3aa8575d3868e945fbada53bc9e 555a0988820a39728b35930762b28509efc7bfd8d046cca32a9896c8071d56c8a508a26b dcd58e64696e15813ab66dabbfedb0d6bfa2078cf98131142765c6f9f54a501da1518a9a 33206ee0fc7145c3cbca30e8b92354b21cecf6e5aced0ce9909a4204f3b007119dcdb303 f1ff5a3352b78dff6f42a4ffcabe220938665316044fe533f01000e54f8e03f912b7b526 3d329cfed70dfcf5059fb795426be342b6a849940469579d0f464aa9bba2dbe170c3532f 0d8ece7bd71b993ca07c09ad010f4966525bdc43a1e2db0bd1b05aad5f70ded58df621ee 73503f15037e42a130ab2962fcde2b1f10a518ed3c4cd37d1f1ba5e6f21231f4ff2f3925 b5536186c57ae4efcbaef6ff59c261f1b61cc759c44863efe438b2ca3ad150adfcd5b7cb df15ea8d2d7213d362a6364e558c94454425f5705844b2e0fdaa4965aa082c6b2e0e8256 ce530752f79697af3fd5fd2c42a5bd64633106be2b26f370253c92e8212e9dfcad3ca10c cb69e0c8ebe6607c98bf0c75329949601133e554bf86cfecbc6c2093062655b6be07311c e7aaf48d24ea4448c45838af1fdf564c8af1a5948ff26d3e61ab3edf6c89570c78ceda20 42eeae695143b592313d2c010b0911c796a6c90bba167a3705c5f7ccaab2ff21ed8ca281 949b5b16f8a09be2ed7736903a85c20cf7f6bd48797a20f5225fe90c9ee10a81f8acfd6a Connolly, et al. Expires 14 February 2025 [Page 27] Internet-Draft xwing August 2024 81747dbe63753b5e594507e14e0a228ea99d4ae51d8caac0dc2f769989c967ebc80dc44c 9e2f140ec29eab1d372f2370b0f66779337578b91354140c2998f19028c1e5f7634e94bf d470f3fbd9ab3f853093262bd403fbb18c1d28d8ac1b90f7b3e99936868bc0ce192ac338 cf32baf87aeb9b71de977502c77230d4881ad30998c24b767790f16cc56c41e1781debb5 c6f9d37b27120a3f225bfdf64ed65807fe988ea2c3001f711070a8354ba92468b115445a f1bd8a9942287f4ffccaacaa715c34bc24901687f257808e48d7a2b6c49f4dbe46fc6288 19f09f89ac553da58e06e03553b30cdd3b715d4367b768da472fc2e734a47ab79ea9e30a d475a4de23321f8c6c9551e57629180cdde9923a90add52165195c7e670bd5989558307e aa0e6513d0225ba1fa213b319c378649bba7a1ddc146b5528d9230f0bc13c2922565d01c e23b57c6058dcc0a3153bdd6c2f0fa5394fb0a506cded4ab50a587a63cec6db3393790e0 de35c4c309d88a41c91bdf6e0e03200693c9651e469aee6f91c98bea4127ae66312f4ae3 ea155b67 ss d99c3cd6cde624a73b2f80d9be695c5ab804a42fcca392bc2fd8504b81b2bf6e seed ef58538b8d23f87732ea63b02b4fa0f4873360e2841928cd60dd4cee8cc0d4c9 sk ef58538b8d23f87732ea63b02b4fa0f4873360e2841928cd60dd4cee8cc0d4c9 pk 9512abd457939c591d51687e8bc2ac7beace759bccb208b113729902d98543479384ac62 7ca21424304ad9281119f3460c975b6c3612812c5bd1f2422e3773a5c21c6d3862d6c377 7ee31822a5718402543cf06476171cbf5895332a444e06c35a4c217d57768574a89dc0a5 8c8160efd847d0861579c278648b92a863b65c688eb41c1adf453d9494cf14f60c339c0b 3e51a937d16cc1491314e013d8cacde2bcbf05d5994658579c834be29b5f6a1a601e2455 2a46822cf99838a57154916415dc54ea3363d751ced5b01160677417c81be3ba67c9b190 bf29c85567b3051b17d6d75b97b883b043c442da3994910296a44f17a187bb51367fc887 56baab782a45550b3e1c733bbac4b8a668b0ab586f64450d6a05219047785c1956a08620 7ac0a636d4bb398abf1649adf0e2069bb7ad063273575ac7947cc25beb768312464874c4 f2091a3c434d93867943b0a3ebc22962aa2b6d5b284e0133f3309fde0c848c5436dd4772 b1bcb81793affee19ab76c598d76b851282ac13ccfc7d4c6a56b2c336c70bc87221dc163 c5518ebb3a5807e918033aacc2a3ad5e555131bb6d61c6b1446882a19c36bf142b7e7375 a6893799b835a1a755383184c0027dbbfc193e546c9389cc53216280ab9c39323d11d468 ca255e0af805712932656bba50f92528d435cca903d6981a1c2b4c9cb30cbdb4bd5f1a5e d84855ad076a18477f202bc699a412c4471a98d9b5974935a5151ef3167c7f8baccfd943 2504bc7c6081491887d872c25fa7a6dd80cb3946832e828cf3406a1a0522ab3b63bdfb10 2d13ac2f193e7e7c82f6ec3804e2220c83bd83eb1bd0d65e175c81e7e176b3f6116d6140 ac409ba4a30d1ef61e7fa0bb88ac209588c75bfa01aab803f55a8f77dc6eee6c0bf34c2c 99e9aa846a2a590a757182ca8fd7536c0920e39a4fa3f763ea307f67172bacd6c2bc8937 856b0eb56959bcfac111f964620081b7d380d3000f27f88a26da2db8f12493f641b09c9f 65a563ebb913e267b1132ba46734cb111cb230d39f1bface22666b42529a01041bccd132 bb0852995ccd273c384748a78848c284f5447eecaf9fa6c244977b676a1d2c26a8dc65c7 974c89482189f4d545fd57348c6b670853cc6b383773925eaf336103aa5da5609b4da3c9 1ce54d2832974f3c445b5424a6182ca792b76de08e96518abaa94afc51646169301ce497 22c13b5a1bc2ecac1a2408589531cc371a6064268db2bb8be783790efb00e38037cbc294 e8820c4a9694785b3a8653320dfa296741b9658c6c7c41c91b0875d205191238b28ca860 a48231f0733d87254ad5572d11e2955645589f0b19651a943ee20c1c7387b706083e0937 11eb099f4c32e4f26f4ee9ad3e74aeb4624c42c030cd66ad4087cb0cfa5f33323a286379 c2090df78b1b04f1cc0cf931f6d6a49bcc6540e4c59373c6ebe64ca38886d75451e2192b fd20a7aeb528dcf1437665294099c09b2560d66ca900d33dea091d1c9a346c66731941cf 57522b6fe33f0a27085e23b72e689990f14622111506dc14e2427db9285fbc82a90f9a23 Connolly, et al. Expires 14 February 2025 [Page 28] Internet-Draft xwing August 2024 510746fd6caaf8418b59d622e16ca1edd1c1a452b48b0ab62a7369bd1722d3413a868b1c 6ccdf2e301ec1f272ba68a1b5e02d743257be8ba94e9eb0f3ec27ce36306ca7b11ab3568 86212ddf193c9915762936f787a3bf665fc381c954c3bb0297da7836 eseed 22a96188d032675c8ac850933c7aff1533b94c834adbb69c6115bad4692d8619f90b0cdf 8a7b9c264029ac185b70b83f2801f2f4b3f70c593ea3aeeb613a7f1b ct 5dae4188bb92ba700d830d8dc6aaf6ef699dcd48ac93c3f5b1e4b0ffc22cf21dfcb51be2 2532844f061bf3b9393c96dad49050bc9244584675c6919232893288f7218ba84d77f21b 84cdccc514c147b54372b60bd8ee81c3dc96f0bee2eeadddca79e3d483f7d9e71fed01f5 d6399ad9d7ede107b859b0f4031ea1376691ce6bfe36d1a211ceee3361035117e12ec81e 3ab6362cfb7b87a0262279a2efd632a704dcea32fa1036a49e631d6d253ef49be6b46b78 44b963bc05e7ca76b203594a2fa5f2812659a5e7aa74531128343f086c80cc69f3cd90ef 4fecf1336f796b0c1c3d15cc54b4b7ee653f4c3b1e3cf97a4c1b223da34e90d6905974ab 4e544ce2af8fdbefe8d5a3e8479ee07afb4ef546dc86d22e62081a27c14613ec1d284f85 0e96c4b4a8283f5b307d4f43776f86d9e5a7dbcf3073d468ed6f8cb82f8a0b13947703fd 15c6911c31379e1d1ccc11560044554a4403cad162a4d86ef22be6a794a240af90e8367a ffbe4f84c8a4cd76934c1aea726efbf156108de461a276ac34baabc8bdb33085ce5dd9b6 d89ef66f06c0590ae7a0cb8fd79a16ee4bdf48aa9788093e6e2f6fa63e837aa80072c2fb e5503a22b9cfff87d67b4f7508885966e8b5332299fe95f6e023d813e8e44f79d271eb72 5687d2dd5e06c0fd34cf5ce9108709960a4d23ef8e8f3d3ba65f5ff8bb57d07c6398ba46 f7a81eba115fa2132066c96fbd1f7bce0749d1f961516c2d86b6f98f3b6f5d4a0dbb530c d7c59f4cad1554dd434bf44be5559614aa1b72ef41b179d667827c458b4196675dd538e2 88bdaebfbe57f13d65ed6cfcf38b5017dcd38c60a8dec0685944c86535b6a3c8a206bace a9d26b4d34cf1d28b4e6aead08f5ba668c0e8bd032ace996f112f7ae5d176ac0bccc2ff8 b25e15ff7b7350e045d41b499179c1a754184fffaff17fa97025437bf590eb142e472d17 a331e0a54045928a73ed641ac57f1b88b1392198949e625d0b2c5e7e9d721d02d609eca5 8a3fd830e6daa97ed59cd5466e356203fbe33e5947bf8ece898ecd2740ded4bb9e563355 4fbe4a72b5564207099e13937bac1e7d7abfa843e95f6293282db0cd1dcd5cf1f3333d98 2343bcd6de04e9f6ded75b7f395b97790c564fc6be98ef5e18d9ab26c193d6ea2afb4a57 71255745b727b8734bc06111b4a1d589d56a176cc5f5ea84d36f0402a9830aa5d7029bc6 5e3042dc85c66bc8a5c848690f8a847ad4ee837fd8eb01d5b5e29c5781afbd321351073f 73b2fc7517f87e4a72e0206212ae393a7ce82a8144d4ab3b7eadd2efed21a6913ea298a0 813d1b26c61a0f93623fa587b12bbacd163a76365023b2fc2b09aeea255dedca9d94b17a c0577435cc627d53992fafe73b956443b2ac1b8f9572c8b3f648f4e1b6427f90b45709f6 c18d87e9e8f4d85e747abd90d7889ba92a27620f2ef6e674ec2f289da1b4e1c9ade96235 82ff69aaad4f7131382fc15b0f2132ab0df74d769421d1d1677619cff13f1c2097bc6b09 8a7bbca0111658f0fa64de6b6e1c3c8e03db5971a445992227c825590688d203523f5271 61137334 ss 3c111a7476821d18c4c05192298a881c46de82a25035e1fbc1ec399cd5a29924 Appendix D. Acknowledgments TODO acknowledge. Connolly, et al. Expires 14 February 2025 [Page 29] Internet-Draft xwing August 2024 Appendix E. Change log *RFC Editor's Note:* Please remove this section prior to publication of a final version of this document. E.1. Since draft-connolly-cfrg-xwing-kem-02 * Use seed as private key. * Expand on caching decapsulation key values. * Expand on binding properties. E.2. Since draft-connolly-cfrg-xwing-kem-01 * Add list of implementations. * Miscellaneous editorial improvements. * Add Python reference specification. * Correct definition of ML-KEM-768.KeyGenDerand(seed). E.3. Since draft-connolly-cfrg-xwing-kem-00 * A copy of the X25519 public key is now included in the X-Wing decapsulation (private) key, so that decapsulation does not require separate access to the X-Wing public key. See #2. Authors' Addresses Deirdre Connolly SandboxAQ Email: durumcrustulum@gmail.com Peter Schwabe MPI-SP & Radboud University Email: peter@cryptojedi.org Bas Westerbaan Cloudflare Email: bas@cloudflare.com Connolly, et al. Expires 14 February 2025 [Page 30]