xwing.go raw
1 // Package xwing implements the X-Wing PQ/T hybrid KEM
2 //
3 // https://datatracker.ietf.org/doc/draft-connolly-cfrg-xwing-kem
4 //
5 // Implements the final version (-05).
6 package xwing
7
8 import (
9 cryptoRand "crypto/rand"
10 "errors"
11 "io"
12
13 "github.com/cloudflare/circl/dh/x25519"
14 "github.com/cloudflare/circl/internal/sha3"
15 "github.com/cloudflare/circl/kem"
16 "github.com/cloudflare/circl/kem/mlkem/mlkem768"
17 )
18
19 // An X-Wing private key.
20 type PrivateKey struct {
21 seed [32]byte
22 m mlkem768.PrivateKey
23 x x25519.Key
24 xpk x25519.Key
25 }
26
27 // An X-Wing public key.
28 type PublicKey struct {
29 m mlkem768.PublicKey
30 x x25519.Key
31 }
32
33 const (
34 // Size of a seed of a keypair
35 SeedSize = 32
36
37 // Size of an X-Wing public key
38 PublicKeySize = 1216
39
40 // Size of an X-Wing private key
41 PrivateKeySize = 32
42
43 // Size of the seed passed to EncapsulateTo
44 EncapsulationSeedSize = 64
45
46 // Size of the established shared key
47 SharedKeySize = 32
48
49 // Size of an X-Wing ciphertext.
50 CiphertextSize = 1120
51 )
52
53 func combiner(
54 out []byte,
55 ssm *[mlkem768.SharedKeySize]byte,
56 ssx *x25519.Key,
57 ctx *x25519.Key,
58 pkx *x25519.Key,
59 ) {
60 h := sha3.New256()
61 _, _ = h.Write(ssm[:])
62 _, _ = h.Write(ssx[:])
63 _, _ = h.Write(ctx[:])
64 _, _ = h.Write(pkx[:])
65
66 // \./
67 // /^\
68 _, _ = h.Write([]byte(`\.//^\`))
69
70 _, _ = h.Read(out[:])
71 }
72
73 // Packs sk to buf.
74 //
75 // Panics if buf is not of size PrivateKeySize
76 func (sk *PrivateKey) Pack(buf []byte) {
77 if len(buf) != PrivateKeySize {
78 panic(kem.ErrPrivKeySize)
79 }
80 copy(buf, sk.seed[:])
81 }
82
83 // Packs pk to buf.
84 //
85 // Panics if buf is not of size PublicKeySize.
86 func (pk *PublicKey) Pack(buf []byte) {
87 if len(buf) != PublicKeySize {
88 panic(kem.ErrPubKeySize)
89 }
90 pk.m.Pack(buf[:mlkem768.PublicKeySize])
91 copy(buf[mlkem768.PublicKeySize:], pk.x[:])
92 }
93
94 // DeriveKeyPair derives a public/private keypair deterministically
95 // from the given seed.
96 //
97 // Panics if seed is not of length SeedSize.
98 func DeriveKeyPair(seed []byte) (*PrivateKey, *PublicKey) {
99 var (
100 sk PrivateKey
101 pk PublicKey
102 )
103
104 deriveKeyPair(seed, &sk, &pk)
105
106 return &sk, &pk
107 }
108
109 func deriveKeyPair(seed []byte, sk *PrivateKey, pk *PublicKey) {
110 if len(seed) != SeedSize {
111 panic(kem.ErrSeedSize)
112 }
113
114 var seedm [mlkem768.KeySeedSize]byte
115
116 copy(sk.seed[:], seed)
117
118 h := sha3.NewShake256()
119 _, _ = h.Write(seed)
120 _, _ = h.Read(seedm[:])
121 _, _ = h.Read(sk.x[:])
122
123 pkm, skm := mlkem768.NewKeyFromSeed(seedm[:])
124 sk.m = *skm
125 pk.m = *pkm
126
127 x25519.KeyGen(&pk.x, &sk.x)
128 sk.xpk = pk.x
129 }
130
131 // DeriveKeyPairPacked derives a keypair like DeriveKeyPair, and
132 // returns them packed.
133 func DeriveKeyPairPacked(seed []byte) ([]byte, []byte) {
134 sk, pk := DeriveKeyPair(seed)
135 var (
136 ppk [PublicKeySize]byte
137 psk [PrivateKeySize]byte
138 )
139 pk.Pack(ppk[:])
140 sk.Pack(psk[:])
141 return psk[:], ppk[:]
142 }
143
144 // GenerateKeyPair generates public and private keys using entropy from rand.
145 // If rand is nil, crypto/rand.Reader will be used.
146 func GenerateKeyPair(rand io.Reader) (*PrivateKey, *PublicKey, error) {
147 var seed [SeedSize]byte
148 if rand == nil {
149 rand = cryptoRand.Reader
150 }
151 _, err := io.ReadFull(rand, seed[:])
152 if err != nil {
153 return nil, nil, err
154 }
155 sk, pk := DeriveKeyPair(seed[:])
156 return sk, pk, nil
157 }
158
159 // GenerateKeyPairPacked generates a keypair like GenerateKeyPair, and
160 // returns them packed.
161 func GenerateKeyPairPacked(rand io.Reader) ([]byte, []byte, error) {
162 sk, pk, err := GenerateKeyPair(rand)
163 if err != nil {
164 return nil, nil, err
165 }
166 var (
167 ppk [PublicKeySize]byte
168 psk [PrivateKeySize]byte
169 )
170 pk.Pack(ppk[:])
171 sk.Pack(psk[:])
172 return psk[:], ppk[:], nil
173 }
174
175 // Encapsulate generates a shared key and ciphertext that contains it
176 // for the public key pk using randomness from seed.
177 //
178 // seed may be nil, in which case crypto/rand.Reader is used.
179 //
180 // Warning: note that the order of the returned ss and ct matches the
181 // X-Wing standard, which is the reverse of the Circl KEM API.
182 //
183 // Returns ErrPubKey if ML-KEM encapsulation key check fails.
184 //
185 // Panics if pk is not of size PublicKeySize, or randomness could not
186 // be read from crypto/rand.Reader.
187 func Encapsulate(pk, seed []byte) (ss, ct []byte, err error) {
188 var pub PublicKey
189 if err := pub.Unpack(pk); err != nil {
190 return nil, nil, err
191 }
192 ct = make([]byte, CiphertextSize)
193 ss = make([]byte, SharedKeySize)
194 pub.EncapsulateTo(ct, ss, seed)
195 return ss, ct, nil
196 }
197
198 // Decapsulate computes the shared key which is encapsulated in ct
199 // for the private key sk.
200 //
201 // Panics if sk or ct are not of length PrivateKeySize and CiphertextSize
202 // respectively.
203 func Decapsulate(ct, sk []byte) (ss []byte) {
204 var priv PrivateKey
205 priv.Unpack(sk)
206 ss = make([]byte, SharedKeySize)
207 priv.DecapsulateTo(ss, ct)
208 return ss
209 }
210
211 // Raised when passing a byte slice of the wrong size for the shared
212 // secret to the EncapsulateTo or DecapsulateTo functions.
213 var ErrSharedKeySize = errors.New("wrong size for shared key")
214
215 // EncapsulateTo generates a shared key and ciphertext that contains it
216 // for the public key using randomness from seed and writes the shared key
217 // to ss and ciphertext to ct.
218 //
219 // Panics if ss, ct or seed are not of length SharedKeySize, CiphertextSize
220 // and EncapsulationSeedSize respectively.
221 //
222 // seed may be nil, in which case crypto/rand.Reader is used to generate one.
223 func (pk *PublicKey) EncapsulateTo(ct, ss, seed []byte) {
224 if seed == nil {
225 seed = make([]byte, EncapsulationSeedSize)
226 if _, err := cryptoRand.Read(seed[:]); err != nil {
227 panic(err)
228 }
229 } else {
230 if len(seed) != EncapsulationSeedSize {
231 panic(kem.ErrSeedSize)
232 }
233 }
234
235 if len(ct) != CiphertextSize {
236 panic(kem.ErrCiphertextSize)
237 }
238
239 if len(ss) != SharedKeySize {
240 panic(ErrSharedKeySize)
241 }
242
243 var (
244 seedm [32]byte
245 ekx x25519.Key
246 ctx x25519.Key
247 ssx x25519.Key
248 ssm [mlkem768.SharedKeySize]byte
249 )
250
251 copy(seedm[:], seed[:32])
252 copy(ekx[:], seed[32:])
253
254 x25519.KeyGen(&ctx, &ekx)
255 // A peer public key with low order points results in an all-zeroes
256 // shared secret. Ignored for now pending clarification in the spec,
257 // https://github.com/dconnolly/draft-connolly-cfrg-xwing-kem/issues/28
258 x25519.Shared(&ssx, &ekx, &pk.x)
259 pk.m.EncapsulateTo(ct[:mlkem768.CiphertextSize], ssm[:], seedm[:])
260
261 combiner(ss, &ssm, &ssx, &ctx, &pk.x)
262 copy(ct[mlkem768.CiphertextSize:], ctx[:])
263 }
264
265 // DecapsulateTo computes the shared key which is encapsulated in ct
266 // for the private key.
267 //
268 // Panics if ct or ss are not of length CiphertextSize and SharedKeySize
269 // respectively.
270 func (sk *PrivateKey) DecapsulateTo(ss, ct []byte) {
271 if len(ct) != CiphertextSize {
272 panic(kem.ErrCiphertextSize)
273 }
274 if len(ss) != SharedKeySize {
275 panic(ErrSharedKeySize)
276 }
277
278 ctm := ct[:mlkem768.CiphertextSize]
279
280 var (
281 ssm [mlkem768.SharedKeySize]byte
282 ssx x25519.Key
283 ctx x25519.Key
284 )
285
286 copy(ctx[:], ct[mlkem768.CiphertextSize:])
287
288 sk.m.DecapsulateTo(ssm[:], ctm)
289 // A peer public key with low order points results in an all-zeroes
290 // shared secret. Ignored for now pending clarification in the spec,
291 // https://github.com/dconnolly/draft-connolly-cfrg-xwing-kem/issues/28
292 x25519.Shared(&ssx, &sk.x, &ctx)
293 combiner(ss, &ssm, &ssx, &ctx, &sk.xpk)
294 }
295
296 // Unpacks pk from buf.
297 //
298 // Panics if buf is not of size PublicKeySize.
299 //
300 // Returns ErrPubKey if pk fails the ML-KEM encapsulation key check.
301 func (pk *PublicKey) Unpack(buf []byte) error {
302 if len(buf) != PublicKeySize {
303 panic(kem.ErrPubKeySize)
304 }
305
306 copy(pk.x[:], buf[mlkem768.PublicKeySize:])
307 return pk.m.Unpack(buf[:mlkem768.PublicKeySize])
308 }
309
310 // Unpacks sk from buf.
311 //
312 // Panics if buf is not of size PrivateKeySize.
313 func (sk *PrivateKey) Unpack(buf []byte) {
314 var pk PublicKey
315 deriveKeyPair(buf, sk, &pk)
316 }
317