Internet-Draft xwing August 2024
Connolly, et al. Expires 14 February 2025 [Page]
Workgroup:
Crypto Forum
Internet-Draft:
draft-connolly-cfrg-xwing-kem-04
Published:
Intended Status:
Informational
Expires:
Authors:
D. Connolly
SandboxAQ
P. Schwabe
MPI-SP & Radboud University
B. E. Westerbaan
Cloudflare

X-Wing: general-purpose hybrid post-quantum KEM

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/.

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.

1. Introduction

1.1. 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.2. 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.

  • 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.3. 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.4. Not an authenticated KEM

In particular, X-Wing is not, borrowing the language of [RFC9180], an authenticated KEM.

1.5. Comparisons

1.5.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.

1.5.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.

    • 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.Encaps(pk_M) MUST perform the encapsulation key check of [MLKEM] §7.2 and raise an error if it fails.

    • 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.

      ML-KEM-768.Encaps_internal(pk_M) MUST perform the encapsulation key check of [MLKEM] §7.2 and raise an error if it fails.

  • 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 0900000000000000000000000000000000000000000000000000000000000000.

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

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.

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()

Encapsulate() returns the 32 byte shared secret ss and the 1120 byte ciphertext ct.

Note that Encapsulate() may raise an error if the ML-KEM encapsulation does not pass the check of [MLKEM] §7.2.

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.

  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, 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.

Encap() is Encapsulate() from Section 5.4, where an ML-KEM encapsulation key check failure causes an HPKE EncapError.

Decap() is Decapsulate() from Section 5.5.

X-Wing is not an authenticated KEM: it does not support AuthEncap() and AuthDecap(), see Section 1.4.

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.

On ML-KEM encapsulation key check failure, the server MUST abort with an illegal_parameter alert.

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

  • 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:

26287 (please)

Description:

X-Wing

DTLS-OK:

Y

Recommended:

Y

Reference:

This document

Comment:

PQ/T hybrid of X25519 and ML-KEM-768

8. References

8.1. Normative References

[RFC2119]
Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, , <https://www.rfc-editor.org/rfc/rfc2119>.
[RFC8174]
Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, , <https://www.rfc-editor.org/rfc/rfc8174>.

8.2. Informative References

[FIPS202]
National Institute of Standards and Technology, "FIPS 202: SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions", n.d., <https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.202.pdf>.
[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, , <https://datatracker.ietf.org/doc/html/draft-stebila-tls-hybrid-design-03>.
[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, , <https://datatracker.ietf.org/doc/html/draft-driscoll-pqt-hybrid-terminology-02>.
[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, , <https://datatracker.ietf.org/doc/html/draft-ounsworth-cfrg-kem-combiners-05>.
[KSMW]
Kraemer, J., Struck, P., and M. Weishaupl, "Binding Security of Implicitly-Rejecting KEMs and Application to BIKE and HQC", n.d., <https://eprint.iacr.org/2024/1233>.
[MLKEM]
National Institute of Standards and Technology, "FIPS 203: Module-Lattice-Based Key-Encapsulation Mechanism Standard", n.d., <https://nvlpubs.nist.gov/nistpubs/fips/nist.fips.203.pdf>.
[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., <https://eprint.iacr.org/2024/039>.
[RFC7748]
Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves for Security", RFC 7748, DOI 10.17487/RFC7748, , <https://www.rfc-editor.org/rfc/rfc7748>.
[RFC9180]
Barnes, R., Bhargavan, K., Lipp, B., and C. Wood, "Hybrid Public Key Encryption", RFC 9180, DOI 10.17487/RFC9180, , <https://www.rfc-editor.org/rfc/rfc9180>.
[SCHMIEG]
Schmieg, S., "Unbindable Kemmy Schmidt: ML-KEM is neither MAL-BIND-K-CT nor MAL-BIND-K-PK", n.d., <https://eprint.iacr.org/2024/523>.
[TLSIANA]
Salowey, J. A. and S. Turner, "IANA Registry Updates for TLS and DTLS", Work in Progress, Internet-Draft, draft-ietf-tls-rfc8447bis-09, , <https://datatracker.ietf.org/doc/html/draft-ietf-tls-rfc8447bis-09>.
[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, , <https://datatracker.ietf.org/doc/html/draft-westerbaan-cfrg-hpke-xyber768d00-03>.
[XYBERTLS]
Westerbaan, B. and D. Stebila, "X25519Kyber768Draft00 hybrid post-quantum key agreement", Work in Progress, Internet-Draft, draft-tls-westerbaan-xyber768d00-03, , <https://datatracker.ietf.org/doc/html/draft-tls-westerbaan-xyber768d00-03>.

Appendix A. Implementations

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'')

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

# 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
        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
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):
        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]
            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]))
    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 <self, other> 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)
    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):
    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(
        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
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
  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
  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
  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.

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-03

  • Mandate ML-KEM encapsulation key check, and stipulate effect on TLS and HPKE integration.

  • Add provisional TLS codepoint.

E.2. Since draft-connolly-cfrg-xwing-kem-02

  • Use seed as private key.

  • Expand on caching decapsulation key values.

  • Expand on binding properties.

E.3. 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.4. 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
Peter Schwabe
MPI-SP & Radboud University
Bas Westerbaan
Cloudflare