draft-connolly-cfrg-xwing-kem-01.txt   draft-connolly-cfrg-xwing-kem-02.txt 
Crypto Forum D. Connolly Crypto Forum D. Connolly
Internet-Draft SandboxAQ Internet-Draft SandboxAQ
Intended status: Informational P. Schwabe Intended status: Informational P. Schwabe
Expires: 25 July 2024 MPI-SP & Radboud University Expires: 27 September 2024 MPI-SP & Radboud University
B. E. Westerbaan B. E. Westerbaan
Cloudflare Cloudflare
22 January 2024 26 March 2024
X-Wing: general-purpose hybrid post-quantum KEM X-Wing: general-purpose hybrid post-quantum KEM
draft-connolly-cfrg-xwing-kem-01 draft-connolly-cfrg-xwing-kem-02
Abstract Abstract
This memo defines X-Wing, a general-purpose post-quantum/traditional This memo defines X-Wing, a general-purpose post-quantum/traditional
hybrid key encapsulation mechanism (PQ/T KEM) built on X25519 and ML- hybrid key encapsulation mechanism (PQ/T KEM) built on X25519 and ML-
KEM-768. KEM-768.
About This Document About This Document
This note is to be removed before publishing as an RFC. This note is to be removed before publishing as an RFC.
skipping to change at page 2, line 10 skipping to change at page 2, line 10
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/. Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
This Internet-Draft will expire on 25 July 2024. This Internet-Draft will expire on 27 September 2024.
Copyright Notice Copyright Notice
Copyright (c) 2024 IETF Trust and the persons identified as the Copyright (c) 2024 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents (https://trustee.ietf.org/ Provisions Relating to IETF Documents (https://trustee.ietf.org/
license-info) in effect on the date of publication of this document. license-info) in effect on the date of publication of this document.
Please review these documents carefully, as they describe your rights Please review these documents carefully, as they describe your rights
skipping to change at page 2, line 33 skipping to change at page 2, line 33
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1. Warning: ML-KEM-768 has not been standardised . . . . . . 3 1.1. Warning: ML-KEM-768 has not been standardised . . . . . . 3
1.2. Motivation . . . . . . . . . . . . . . . . . . . . . . . 3 1.2. Motivation . . . . . . . . . . . . . . . . . . . . . . . 3
1.3. Design goals . . . . . . . . . . . . . . . . . . . . . . 3 1.3. Design goals . . . . . . . . . . . . . . . . . . . . . . 3
1.4. Not an interactive key-agreement . . . . . . . . . . . . 4 1.4. Not an interactive key-agreement . . . . . . . . . . . . 4
1.5. Not an authenticated KEM . . . . . . . . . . . . . . . . 4 1.5. Not an authenticated KEM . . . . . . . . . . . . . . . . 4
1.6. Comparisons . . . . . . . . . . . . . . . . . . . . . . . 4 1.6. Comparisons . . . . . . . . . . . . . . . . . . . . . . . 4
1.6.1. With HPKE X25519Kyber768Draft00 . . . . . . . . . . . 4 1.6.1. With HPKE X25519Kyber768Draft00 . . . . . . . . . . . 4
1.6.2. With generic combiner . . . . . . . . . . . . . . . . 4 1.6.2. With generic combiner . . . . . . . . . . . . . . . . 5
2. Requirements Notation . . . . . . . . . . . . . . . . . . . . 5 2. Requirements Notation . . . . . . . . . . . . . . . . . . . . 5
3. Conventions and Definitions . . . . . . . . . . . . . . . . . 5 3. Conventions and Definitions . . . . . . . . . . . . . . . . . 5
4. Cryptographic Dependencies . . . . . . . . . . . . . . . . . 5 4. Cryptographic Dependencies . . . . . . . . . . . . . . . . . 5
5. X-Wing Construction . . . . . . . . . . . . . . . . . . . . . 6 5. X-Wing Construction . . . . . . . . . . . . . . . . . . . . . 6
5.1. Encoding and sizes . . . . . . . . . . . . . . . . . . . 6 5.1. Encoding and sizes . . . . . . . . . . . . . . . . . . . 6
5.2. Key generation . . . . . . . . . . . . . . . . . . . . . 7 5.2. Key generation . . . . . . . . . . . . . . . . . . . . . 7
5.2.1. Key derivation . . . . . . . . . . . . . . . . . . . 7 5.2.1. Key derivation . . . . . . . . . . . . . . . . . . . 7
5.3. Combiner . . . . . . . . . . . . . . . . . . . . . . . . 7 5.3. Combiner . . . . . . . . . . . . . . . . . . . . . . . . 7
5.4. Encapsulation . . . . . . . . . . . . . . . . . . . . . . 8 5.4. Encapsulation . . . . . . . . . . . . . . . . . . . . . . 8
5.4.1. Derandomized . . . . . . . . . . . . . . . . . . . . 8 5.4.1. Derandomized . . . . . . . . . . . . . . . . . . . . 8
5.5. Decapsulation . . . . . . . . . . . . . . . . . . . . . . 9 5.5. Decapsulation . . . . . . . . . . . . . . . . . . . . . . 9
5.6. Use in HPKE . . . . . . . . . . . . . . . . . . . . . . . 9 5.6. Use in HPKE . . . . . . . . . . . . . . . . . . . . . . . 9
5.7. Use in TLS 1.3 . . . . . . . . . . . . . . . . . . . . . 10 5.7. Use in TLS 1.3 . . . . . . . . . . . . . . . . . . . . . 10
6. Security Considerations . . . . . . . . . . . . . . . . . . . 10 6. Security Considerations . . . . . . . . . . . . . . . . . . . 10
7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10
8. TODO . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 8. TODO . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
9. References . . . . . . . . . . . . . . . . . . . . . . . . . 11 9. References . . . . . . . . . . . . . . . . . . . . . . . . . 11
9.1. Normative References . . . . . . . . . . . . . . . . . . 11 9.1. Normative References . . . . . . . . . . . . . . . . . . 11
9.2. Informative References . . . . . . . . . . . . . . . . . 11 9.2. Informative References . . . . . . . . . . . . . . . . . 11
Appendix A. Test vectors # TODO: replace with test vectors that Appendix A. Implementations . . . . . . . . . . . . . . . . . . 13
re-use ML-KEM, X25519 values . . . . . . . . . . . . . . 13 Appendix B. Machine-readable specification . . . . . . . . . . . 13
Appendix B. Acknowledgments . . . . . . . . . . . . . . . . . . 22 B.1. xwing.py . . . . . . . . . . . . . . . . . . . . . . . . 13
Appendix C. Change log . . . . . . . . . . . . . . . . . . . . . 22 B.2. x25519.py . . . . . . . . . . . . . . . . . . . . . . . . 15
C.1. Since draft-connolly-cfrg-xwing-kem-00 . . . . . . . . . 22 B.3. mlkem.py . . . . . . . . . . . . . . . . . . . . . . . . 16
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 22 Appendix C. Test vectors # TODO: replace with test vectors that
re-use ML-KEM, X25519 values . . . . . . . . . . . . . . 23
Appendix D. Acknowledgments . . . . . . . . . . . . . . . . . . 32
Appendix E. Change log . . . . . . . . . . . . . . . . . . . . . 32
E.1. Since draft-connolly-cfrg-xwing-kem-01 . . . . . . . . . 32
E.2. Since draft-connolly-cfrg-xwing-kem-00 . . . . . . . . . 33
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 33
1. Introduction 1. Introduction
1.1. Warning: ML-KEM-768 has not been standardised 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 uses ML-KEM-768, which has not been standardised yet. Thus
X-Wing is not finished, yet, and should not be used, yet. X-Wing is not finished, yet, and should not be used, yet.
1.2. Motivation 1.2. Motivation
skipping to change at page 3, line 41 skipping to change at page 3, line 47
By making concrete choices, we can simplify and improve many aspects By making concrete choices, we can simplify and improve many aspects
of X-Wing. of X-Wing.
* Simplicity of definition. Because all shared secrets and cipher * Simplicity of definition. Because all shared secrets and cipher
texts are fixed length, we do not need to encode the length. texts are fixed length, we do not need to encode the length.
Using SHA3-256, we do not need HMAC-based construction. For the 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 concrete choice of ML-KEM-768, we do not need to mix in its
ciphertext, see Section 6. ciphertext, see Section 6.
* Security analysis. Because ML-KEM-768 already assumes QROM, we do * Security analysis. Because ML-KEM-768 already assumes the Quantum
not need to complicate the analysis of X-Wing by considering Random Oracle Model (QROM), we do not need to complicate the
stronger models. analysis of X-Wing by considering stronger models.
* Performance. Not having to mix in the ML-KEM-768 ciphertext is a * Performance. Not having to mix in the ML-KEM-768 ciphertext is a
nice performance benefit. Furthermore, by using SHA3-256 in the nice performance benefit. Furthermore, by using SHA3-256 in the
combiner, which matches the hashing in ML-KEM-768, this hash can combiner, which matches the hashing in ML-KEM-768, this hash can
be computed in one go on platforms where two-way Keccak is be computed in one go on platforms where two-way Keccak is
available. available.
We aim for "128 bits" security (NIST PQC level 1). Although at the 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 moment there is no peer-reviewed evidence that ML-KEM-512 does not
reach this level, we would like to hedge against future cryptanalytic reach this level, we would like to hedge against future cryptanalytic
skipping to change at page 6, line 11 skipping to change at page 6, line 16
(ss_M, ct_M), an ephemeral 32 byte shared key ss_M, and a (ss_M, ct_M), an ephemeral 32 byte shared key ss_M, and a
fixed-length encapsulation (ciphertext) of that key ct_M for fixed-length encapsulation (ciphertext) of that key ct_M for
encapsulation key pk_M. encapsulation key pk_M.
- ML-KEM-768.Decap(ct_M, sk_M): Deterministic algorithm using the - ML-KEM-768.Decap(ct_M, sk_M): Deterministic algorithm using the
decapsulation key sk_M to recover the shared key from ct_M. decapsulation key sk_M to recover the shared key from ct_M.
To generate deterministic test vectors, we also use To generate deterministic test vectors, we also use
- ML-KEM-768.KeyGenDerand(seed): Same as ML-KEM-768.KeyGen(), but - ML-KEM-768.KeyGenDerand(seed): Same as ML-KEM-768.KeyGen(), but
derandomized as follows. seed is 64 bytes. seed[0:32] is used derandomized as follows. seed[0:32] is used for d in line 1 of
for z (line 1 algorithm 15), and seed[32:64] is used for d algorithm 12 from [MLKEM] and seed is 64 bytes. seed[32:64] is
(line 1 algorithm 12). used for z in line 1 of algorithm 15.
- ML-KEM-768.EncapsDerand(pk_M, seed): Same as ML-KEM- - ML-KEM-768.EncapsDerand(pk_M, seed): Same as ML-KEM-
768.Encaps() but derandomized as follows. seed is 32 bytes and 768.Encaps() but derandomized as follows. seed is 32 bytes and
used for m (line 1 algorithm 16). used for m in line of 1 algorithm 16.
* X25519 elliptic curve Diffie-Hellman key-exchange defined in * X25519 elliptic curve Diffie-Hellman key-exchange defined in
Section 5 of [RFC7748]: Section 5 of [RFC7748]:
- X25519(k,u): takes 32 byte strings k and u representing a - X25519(k,u): takes 32 byte strings k and u representing a
Curve25519 scalar and curvepoint respectively, and returns the Curve25519 scalar and curvepoint respectively, and returns the
32 byte string representing their scalar multiplication. 32 byte string representing their scalar multiplication.
- X25519_BASE: the 32 byte string representing the standard base - X25519_BASE: the 32 byte string representing the standard base
point of Curve25519. In hex it is given by point of Curve25519. In hex it is given by 0900000000000000000
09000000000000000000000000000000000000000000. 000000000000000000000000000000000000000000000.
Note that 9 is the standard basepoint for X25519, cf Section 6.1 of Note that 9 is the standard basepoint for X25519, cf Section 6.1 of
[RFC7748]. [RFC7748].
* Symmetric cryptography. * Symmetric cryptography.
- SHAKE128(message, outlen): The extendable-output function (XOF) - SHAKE128(message, outlen): The extendable-output function (XOF)
defined in Section 6.2 of [FIPS202]. defined in Section 6.2 of [FIPS202].
- SHA3-256(message): The hash defined in defined in Section 6.1 - SHA3-256(message): The hash defined in Section 6.1 of
of [FIPS202]. [FIPS202].
5. X-Wing Construction 5. X-Wing Construction
5.1. Encoding and sizes 5.1. Encoding and sizes
X-Wing encapsulation key, decapsulation key, ciphertexts and shared X-Wing encapsulation key, decapsulation key, ciphertexts and shared
secrets are all fixed length byte strings. secrets are all fixed length byte strings.
Decapsulation key (private): 2464 bytes Decapsulation key (private): 2464 bytes
skipping to change at page 7, line 4 skipping to change at page 7, line 10
5.1. Encoding and sizes 5.1. Encoding and sizes
X-Wing encapsulation key, decapsulation key, ciphertexts and shared X-Wing encapsulation key, decapsulation key, ciphertexts and shared
secrets are all fixed length byte strings. secrets are all fixed length byte strings.
Decapsulation key (private): 2464 bytes Decapsulation key (private): 2464 bytes
Encapsulation key (public): 1216 bytes Encapsulation key (public): 1216 bytes
Ciphertext: 1120 bytes Ciphertext: 1120 bytes
Shared secret: 32 bytes Shared secret: 32 bytes
5.2. Key generation 5.2. Key generation
An X-Wing keypair (decapsulation key, encapsulation key) is generated An X-Wing keypair (decapsulation key, encapsulation key) is generated
as follows. as follows.
def GenerateKeyPair(): def GenerateKeyPair():
(pk_M, sk_M) = ML-KEM-768.KeyGen() (pk_M, sk_M) = ML-KEM-768.KeyGen()
sk_X = random(32) sk_X = random(32)
pk_X = X25519(sk_X, X25519_BASE) pk_X = X25519(sk_X, X25519_BASE)
return concat(sk_M, sk_X, pk_X), concat(pk_M, pk_X) return concat(sk_M, sk_X, pk_X), concat(pk_M, pk_X)
GenerateKeyPair() returns the 2464 byte secret encapsulation key sk GenerateKeyPair() returns the 2464 byte secret decapsulation key sk
and the 1216 byte decapsulation key pk. 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 5.2.1. Key derivation
For testing, it is convenient to have a deterministic version of key For testing, it is convenient to have a deterministic version of key
generation. An X-Wing implementation MAY provide the following generation. An X-Wing implementation MAY provide the following
derandomized variant of key generation. derandomized variant of key generation.
def GenerateKeyPairDerand(seed): def GenerateKeyPairDerand(seed):
(pk_M, sk_M) = ML-KEM-768.KeyGenDerand(seed[0:64]) (pk_M, sk_M) = ML-KEM-768.KeyGenDerand(seed[0:64])
sk_X = seed[64:96] sk_X = seed[64:96]
skipping to change at page 8, line 12 skipping to change at page 8, line 21
pk_X pk_X
)) ))
where XWingLabel is the following 6 byte ASCII string where XWingLabel is the following 6 byte ASCII string
XWingLabel = concat( XWingLabel = concat(
"\./", "\./",
"/^\", "/^\",
) )
In hex XWingLabel is given by 5c2e2f2f5e5c.
5.4. Encapsulation 5.4. Encapsulation
Given an X-Wing encapsulation key pk, encapsulation proceeds as Given an X-Wing encapsulation key pk, encapsulation proceeds as
follows. follows.
def Encapsulate(pk): def Encapsulate(pk):
pk_M = pk[0:1184] pk_M = pk[0:1184]
pk_X = pk[1184:1216] pk_X = pk[1184:1216]
ek_X = random(32) ek_X = random(32)
ct_X = X25519(ek_X, X25519_BASE) ct_X = X25519(ek_X, X25519_BASE)
skipping to change at page 8, line 40 skipping to change at page 9, line 5
Encapsulate() returns the 32 byte shared secret ss and the 1120 byte Encapsulate() returns the 32 byte shared secret ss and the 1120 byte
ciphertext ct. ciphertext ct.
5.4.1. Derandomized 5.4.1. Derandomized
For testing, it is convenient to have a deterministic version of For testing, it is convenient to have a deterministic version of
encapsulation. An X-Wing implementation MAY provide the following encapsulation. An X-Wing implementation MAY provide the following
derandomized function. derandomized function.
def EncapsulateDerand(pk, seed): def EncapsulateDerand(pk, eseed):
pk_M = pk[0:1184] pk_M = pk[0:1184]
pk_X = pk[1184:1216] pk_X = pk[1184:1216]
ek_X = seed[32:64] ek_X = eseed[32:64]
ct_X = X25519(ek_X, X25519_BASE) ct_X = X25519(ek_X, X25519_BASE)
ss_X = X25519(ek_X, pk_X) ss_X = X25519(ek_X, pk_X)
(ss_M, ct_M) = ML-KEM-768.EncapsDerand(pk_M, seed[0:32]) (ss_M, ct_M) = ML-KEM-768.EncapsDerand(pk_M, eseed[0:32])
ss = Combiner(ss_M, ss_X, ct_X, pk_X) ss = Combiner(ss_M, ss_X, ct_X, pk_X)
ct = concat(ct_M, ct_X) ct = concat(ct_M, ct_X)
return (ss, ct) return (ss, ct)
pk is a 1216 byte X-Wing encapsulation key resulting from pk is a 1216 byte X-Wing encapsulation key resulting from
GeneratePublicKey() seed MUST be 64 bytes. GeneratePublicKey() eseed MUST be 64 bytes.
EncapsulateDerand() returns the 32 byte shared secret ss and the 1120 EncapsulateDerand() returns the 32 byte shared secret ss and the 1120
byte ciphertext ct. byte ciphertext ct.
5.5. Decapsulation 5.5. Decapsulation
def Decapsulate(ct, sk): def Decapsulate(ct, sk):
ct_M = ct[0:1088] ct_M = ct[0:1088]
ct_X = ct[1088:1120] ct_X = ct[1088:1120]
sk_M = sk[0:2400] sk_M = sk[0:2400]
skipping to change at page 10, line 24 skipping to change at page 10, line 40
Informally, X-Wing is secure if SHA3 is secure, and either X25519 is Informally, X-Wing is secure if SHA3 is secure, and either X25519 is
secure, or ML-KEM-768 is secure. secure, or ML-KEM-768 is secure.
More precisely, if SHA3-256, SHA3-512, SHAKE-128, and SHAKE-256 may 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 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 is bounded by the IND-CCA security of ML-KEM-768, and the gap-CDH
security of Curve25519, see [PROOF]. security of Curve25519, see [PROOF].
The security of X-Wing relies crucially on the specifics of the The security of X-Wing relies crucially on the specifics of the
Fujisaki-Okamoto transformation used in ML-KEM-768. In particular, Fujisaki-Okamoto transformation used in ML-KEM-768: the X-Wing
the X-Wing combiner cannot be assumed to be secure, when used with combiner cannot be assumed to be secure, when used with different
different KEMs. KEMs. In particular it is not known to be safe to leave out the
post-quantum ciphertext from the combiner in the general case.
7. IANA Considerations 7. IANA Considerations
This document requests/registers a new entry to the "HPKE KEM This document requests/registers a new entry to the "HPKE KEM
Identifiers" registry. Identifiers" registry.
Value: TBD (please) Value: TBD (please)
KEM: X-Wing KEM: X-Wing
Nsecret: 32 Nsecret: 32
Nenc: 1120 Nenc: 1120
Npk: 1216 Npk: 1216
Nsk: 2464 Nsk: 2464
Auth: no Auth: no
skipping to change at page 12, line 16 skipping to change at page 12, line 28
D, F., "Terminology for Post-Quantum Traditional Hybrid D, F., "Terminology for Post-Quantum Traditional Hybrid
Schemes", Work in Progress, Internet-Draft, draft- Schemes", Work in Progress, Internet-Draft, draft-
driscoll-pqt-hybrid-terminology-02, 7 March 2023, driscoll-pqt-hybrid-terminology-02, 7 March 2023,
<https://datatracker.ietf.org/doc/html/draft-driscoll-pqt- <https://datatracker.ietf.org/doc/html/draft-driscoll-pqt-
hybrid-terminology-02>. hybrid-terminology-02>.
[I-D.ounsworth-cfrg-kem-combiners] [I-D.ounsworth-cfrg-kem-combiners]
Ounsworth, M., Wussler, A., and S. Kousidis, "Combiner Ounsworth, M., Wussler, A., and S. Kousidis, "Combiner
function for hybrid key encapsulation mechanisms (Hybrid function for hybrid key encapsulation mechanisms (Hybrid
KEMs)", Work in Progress, Internet-Draft, draft-ounsworth- KEMs)", Work in Progress, Internet-Draft, draft-ounsworth-
cfrg-kem-combiners-04, 8 July 2023, cfrg-kem-combiners-05, 31 January 2024,
<https://datatracker.ietf.org/doc/html/draft-ounsworth- <https://datatracker.ietf.org/doc/html/draft-ounsworth-
cfrg-kem-combiners-04>. cfrg-kem-combiners-05>.
[MLKEM] National Institute of Standards and Technology, "FIPS 203 [MLKEM] National Institute of Standards and Technology, "FIPS 203
(Initial Draft): Module-Lattice-Based Key-Encapsulation (Initial Draft): Module-Lattice-Based Key-Encapsulation
Mechanism Standard", n.d., Mechanism Standard", n.d.,
<https://csrc.nist.gov/pubs/fips/203/ipd>. <https://csrc.nist.gov/pubs/fips/203/ipd>.
[PROOF] Barbosa, M., Connolly, D., Duarte, J., Kaiser, A., [PROOF] Barbosa, M., Connolly, D., Duarte, J., Kaiser, A.,
Schwabe, P., Varner, K., and B. E. Westerbraan, "X-Wing: Schwabe, P., Varner, K., and B. E. Westerbraan, "X-Wing:
The Hybrid KEM You’ve Been Looking For", n.d., The Hybrid KEM You’ve Been Looking For", n.d.,
<https://eprint.iacr.org/2024/039>. <https://eprint.iacr.org/2024/039>.
skipping to change at page 13, line 11 skipping to change at page 13, line 24
Internet-Draft, draft-westerbaan-cfrg-hpke-xyber768d00-02, Internet-Draft, draft-westerbaan-cfrg-hpke-xyber768d00-02,
4 May 2023, <https://datatracker.ietf.org/doc/html/draft- 4 May 2023, <https://datatracker.ietf.org/doc/html/draft-
westerbaan-cfrg-hpke-xyber768d00-02>. westerbaan-cfrg-hpke-xyber768d00-02>.
[XYBERTLS] Westerbaan, B. and D. Stebila, "X25519Kyber768Draft00 [XYBERTLS] Westerbaan, B. and D. Stebila, "X25519Kyber768Draft00
hybrid post-quantum key agreement", Work in Progress, hybrid post-quantum key agreement", Work in Progress,
Internet-Draft, draft-tls-westerbaan-xyber768d00-03, 24 Internet-Draft, draft-tls-westerbaan-xyber768d00-03, 24
September 2023, <https://datatracker.ietf.org/doc/html/ September 2023, <https://datatracker.ietf.org/doc/html/
draft-tls-westerbaan-xyber768d00-03>. draft-tls-westerbaan-xyber768d00-03>.
Appendix A. Test vectors # TODO: replace with test vectors that re-use 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'')
assert len(XWingLabel) == 6
assert binascii.hexlify(XWingLabel) == b'5c2e2f2f5e5c'
def GenerateKeyPairDerand(seed):
assert len(seed) == 96
pkM, skM = mlkem.KeyGen(seed[0:64], mlkem.params768)
skX = seed[64:96]
pkX = x25519.X(skX, x25519.BASE)
return skM + skX + pkX, 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) == 2464
ctM = ct[0:1088]
ctX = ct[1088:1120]
skM = sk[0:2400]
skX = sk[2400:2432]
pkX = sk[2432:2464]
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)
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)
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 ML-KEM, X25519 values
seed seed
7f9c2ba4e88f827d616045507605853ed73b8093f6efbc88eb1a6eacfa66ef263cb1eea9 7f9c2ba4e88f827d616045507605853ed73b8093f6efbc88eb1a6eacfa66ef263cb1eea9
88004b93103cfb0aeefd2a686e01fa4a58e8a3639ca8a1e3f9ae57e235b8cc873c23dc62 88004b93103cfb0aeefd2a686e01fa4a58e8a3639ca8a1e3f9ae57e235b8cc873c23dc62
b8d260169afa2f75ab916a58d974918835d25e6a435085b2 b8d260169afa2f75ab916a58d974918835d25e6a435085b2
sk sk
24c59d1c7603e7b74bc7aa1bc2cb3a214b3cfaebb63bd85b65408427c498ba394371bb27 24c59d1c7603e7b74bc7aa1bc2cb3a214b3cfaebb63bd85b65408427c498ba394371bb27
1f92a3b506b81d54a95a7c0ddfbaa1519553d6f3cd5a601b7db6b0e91a5149468f1f68ad 1f92a3b506b81d54a95a7c0ddfbaa1519553d6f3cd5a601b7db6b0e91a5149468f1f68ad
26478bf3c6670e093ac4c49e7a90ba46595de94c50e04129a811a841b39534a87f0ae7b1 26478bf3c6670e093ac4c49e7a90ba46595de94c50e04129a811a841b39534a87f0ae7b1
skipping to change at page 22, line 22 skipping to change at page 32, line 30
2f8c0db076364a97d7acaf0f238c912fd56403593a8b2526884737790a887d9a8382fab3 2f8c0db076364a97d7acaf0f238c912fd56403593a8b2526884737790a887d9a8382fab3
d2967803d0a1e62b610289af4ea26c66ef29c4832a4b48ffa225d5be2401656753a9ed00 d2967803d0a1e62b610289af4ea26c66ef29c4832a4b48ffa225d5be2401656753a9ed00
c45a057efc666abaecfaeef972643de281f5d6a6ef43ed2fbba963a95c8d36461323d51d c45a057efc666abaecfaeef972643de281f5d6a6ef43ed2fbba963a95c8d36461323d51d
18f92e58e4de1b4edd1d93ba14ea6adc3b8b63e71d0edc92555f3f962e68fbf42a0fc04c 18f92e58e4de1b4edd1d93ba14ea6adc3b8b63e71d0edc92555f3f962e68fbf42a0fc04c
b7da107203468589655f1b3b979ccc2efee6f10f0ec631c040e4436b8acaa4716708bf96 b7da107203468589655f1b3b979ccc2efee6f10f0ec631c040e4436b8acaa4716708bf96
d2db8108a36117d10664cb2a3e3af672a10b0de5c2a284e6b9de37533bd181bc14fa0490 d2db8108a36117d10664cb2a3e3af672a10b0de5c2a284e6b9de37533bd181bc14fa0490
35d5050b5526ba59f893a1778103b6e2d946090c0eba049e5c1ad843a3121d539564866a 35d5050b5526ba59f893a1778103b6e2d946090c0eba049e5c1ad843a3121d539564866a
f5647437 f5647437
ss 1e037823ddbf1875756d86a3374b2d2347d5b7f3c84d229ecc5960523cdaa8b4 ss 1e037823ddbf1875756d86a3374b2d2347d5b7f3c84d229ecc5960523cdaa8b4
Appendix B. Acknowledgments Appendix D. Acknowledgments
TODO acknowledge. TODO acknowledge.
Appendix C. Change log Appendix E. Change log
*RFC Editor's Note:* Please remove this section prior to *RFC Editor's Note:* Please remove this section prior to
publication of a final version of this document. publication of a final version of this document.
C.1. Since draft-connolly-cfrg-xwing-kem-00 E.1. 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.2. Since draft-connolly-cfrg-xwing-kem-00
* A copy of the X25519 public key is now included in the X-Wing * A copy of the X25519 public key is now included in the X-Wing
decapsulation (private) key, so that decapsulation does not decapsulation (private) key, so that decapsulation does not
require separate access to the X-Wing public key. See #2. require separate access to the X-Wing public key. See #2.
Authors' Addresses Authors' Addresses
Deirdre Connolly Deirdre Connolly
SandboxAQ SandboxAQ
Email: durumcrustulum@gmail.com Email: durumcrustulum@gmail.com
 End of changes. 26 change blocks. 
38 lines changed or deleted 532 lines changed or added

This html diff was produced by rfcdiff 1.45. The latest version is available from http://tools.ietf.org/tools/rfcdiff/