1 /* Based on the public domain implementation in
2 * crypto_hash/keccakc512/simple/ from http://bench.cr.yp.to/supercop.html
3 * by Ronny Van Keer
4 * and the public domain "TweetFips202" implementation
5 * from https://twitter.com/tweetfips202
6 * by Gilles Van Assche, Daniel J. Bernstein, and Peter Schwabe */
7
8 #include <stddef.h>
9 #include <stdint.h>
10
11 #include "kyber512r3_params.h"
12 #include "kyber512r3_fips202.h"
13
14 #define NROUNDS 24
15 #define ROL(a, offset) (((a) << (offset)) ^ ((a) >> (64 - (offset))))
16
17 /*************************************************
18 * Name: load64
19 *
20 * Description: Load 8 bytes into uint64_t in little-endian order
21 *
22 * Arguments: - const uint8_t *x: pointer to input byte array
23 *
24 * Returns the loaded 64-bit unsigned integer
25 **************************************************/
load64(const uint8_t * x)26 static uint64_t load64(const uint8_t *x) {
27 uint64_t r = 0;
28 for (size_t i = 0; i < 8; ++i) {
29 r |= (uint64_t)x[i] << 8 * i;
30 }
31
32 return r;
33 }
34
35 /*************************************************
36 * Name: store64
37 *
38 * Description: Store a 64-bit integer to a byte array in little-endian order
39 *
40 * Arguments: - uint8_t *x: pointer to the output byte array
41 * - uint64_t u: input 64-bit unsigned integer
42 **************************************************/
store64(uint8_t * x,uint64_t u)43 static void store64(uint8_t *x, uint64_t u) {
44 for (size_t i = 0; i < 8; ++i) {
45 x[i] = (uint8_t) (u >> 8 * i);
46 }
47 }
48
49 /* Keccak round constants */
50 static const uint64_t KeccakF_RoundConstants[NROUNDS] = {
51 0x0000000000000001ULL, 0x0000000000008082ULL,
52 0x800000000000808aULL, 0x8000000080008000ULL,
53 0x000000000000808bULL, 0x0000000080000001ULL,
54 0x8000000080008081ULL, 0x8000000000008009ULL,
55 0x000000000000008aULL, 0x0000000000000088ULL,
56 0x0000000080008009ULL, 0x000000008000000aULL,
57 0x000000008000808bULL, 0x800000000000008bULL,
58 0x8000000000008089ULL, 0x8000000000008003ULL,
59 0x8000000000008002ULL, 0x8000000000000080ULL,
60 0x000000000000800aULL, 0x800000008000000aULL,
61 0x8000000080008081ULL, 0x8000000000008080ULL,
62 0x0000000080000001ULL, 0x8000000080008008ULL,
63 };
64
65 /*************************************************
66 * Name: KeccakF1600_StatePermute
67 *
68 * Description: The Keccak F1600 Permutation
69 *
70 * Arguments: - uint64_t *state: pointer to input/output Keccak state
71 **************************************************/
KeccakF1600_StatePermute(uint64_t * state)72 static void KeccakF1600_StatePermute(uint64_t *state) {
73 int round;
74
75 uint64_t Aba, Abe, Abi, Abo, Abu;
76 uint64_t Aga, Age, Agi, Ago, Agu;
77 uint64_t Aka, Ake, Aki, Ako, Aku;
78 uint64_t Ama, Ame, Ami, Amo, Amu;
79 uint64_t Asa, Ase, Asi, Aso, Asu;
80
81 /* copyFromState(A, state) */
82 Aba = state[0];
83 Abe = state[1];
84 Abi = state[2];
85 Abo = state[3];
86 Abu = state[4];
87 Aga = state[5];
88 Age = state[6];
89 Agi = state[7];
90 Ago = state[8];
91 Agu = state[9];
92 Aka = state[10];
93 Ake = state[11];
94 Aki = state[12];
95 Ako = state[13];
96 Aku = state[14];
97 Ama = state[15];
98 Ame = state[16];
99 Ami = state[17];
100 Amo = state[18];
101 Amu = state[19];
102 Asa = state[20];
103 Ase = state[21];
104 Asi = state[22];
105 Aso = state[23];
106 Asu = state[24];
107
108 for (round = 0; round < NROUNDS; round += 2) {
109 uint64_t BCa, BCe, BCi, BCo, BCu;
110 uint64_t Da, De, Di, Do, Du;
111 uint64_t Eba, Ebe, Ebi, Ebo, Ebu;
112 uint64_t Ega, Ege, Egi, Ego, Egu;
113 uint64_t Eka, Eke, Eki, Eko, Eku;
114 uint64_t Ema, Eme, Emi, Emo, Emu;
115 uint64_t Esa, Ese, Esi, Eso, Esu;
116
117 /* prepareTheta */
118 BCa = Aba ^ Aga ^ Aka ^ Ama ^ Asa;
119 BCe = Abe ^ Age ^ Ake ^ Ame ^ Ase;
120 BCi = Abi ^ Agi ^ Aki ^ Ami ^ Asi;
121 BCo = Abo ^ Ago ^ Ako ^ Amo ^ Aso;
122 BCu = Abu ^ Agu ^ Aku ^ Amu ^ Asu;
123
124 /* thetaRhoPiChiIotaPrepareTheta(round , A, E) */
125 Da = BCu ^ ROL(BCe, 1);
126 De = BCa ^ ROL(BCi, 1);
127 Di = BCe ^ ROL(BCo, 1);
128 Do = BCi ^ ROL(BCu, 1);
129 Du = BCo ^ ROL(BCa, 1);
130
131 Aba ^= Da;
132 BCa = Aba;
133 Age ^= De;
134 BCe = ROL(Age, 44);
135 Aki ^= Di;
136 BCi = ROL(Aki, 43);
137 Amo ^= Do;
138 BCo = ROL(Amo, 21);
139 Asu ^= Du;
140 BCu = ROL(Asu, 14);
141 Eba = BCa ^ ((~BCe) & BCi);
142 Eba ^= KeccakF_RoundConstants[round];
143 Ebe = BCe ^ ((~BCi) & BCo);
144 Ebi = BCi ^ ((~BCo) & BCu);
145 Ebo = BCo ^ ((~BCu) & BCa);
146 Ebu = BCu ^ ((~BCa) & BCe);
147
148 Abo ^= Do;
149 BCa = ROL(Abo, 28);
150 Agu ^= Du;
151 BCe = ROL(Agu, 20);
152 Aka ^= Da;
153 BCi = ROL(Aka, 3);
154 Ame ^= De;
155 BCo = ROL(Ame, 45);
156 Asi ^= Di;
157 BCu = ROL(Asi, 61);
158 Ega = BCa ^ ((~BCe) & BCi);
159 Ege = BCe ^ ((~BCi) & BCo);
160 Egi = BCi ^ ((~BCo) & BCu);
161 Ego = BCo ^ ((~BCu) & BCa);
162 Egu = BCu ^ ((~BCa) & BCe);
163
164 Abe ^= De;
165 BCa = ROL(Abe, 1);
166 Agi ^= Di;
167 BCe = ROL(Agi, 6);
168 Ako ^= Do;
169 BCi = ROL(Ako, 25);
170 Amu ^= Du;
171 BCo = ROL(Amu, 8);
172 Asa ^= Da;
173 BCu = ROL(Asa, 18);
174 Eka = BCa ^ ((~BCe) & BCi);
175 Eke = BCe ^ ((~BCi) & BCo);
176 Eki = BCi ^ ((~BCo) & BCu);
177 Eko = BCo ^ ((~BCu) & BCa);
178 Eku = BCu ^ ((~BCa) & BCe);
179
180 Abu ^= Du;
181 BCa = ROL(Abu, 27);
182 Aga ^= Da;
183 BCe = ROL(Aga, 36);
184 Ake ^= De;
185 BCi = ROL(Ake, 10);
186 Ami ^= Di;
187 BCo = ROL(Ami, 15);
188 Aso ^= Do;
189 BCu = ROL(Aso, 56);
190 Ema = BCa ^ ((~BCe) & BCi);
191 Eme = BCe ^ ((~BCi) & BCo);
192 Emi = BCi ^ ((~BCo) & BCu);
193 Emo = BCo ^ ((~BCu) & BCa);
194 Emu = BCu ^ ((~BCa) & BCe);
195
196 Abi ^= Di;
197 BCa = ROL(Abi, 62);
198 Ago ^= Do;
199 BCe = ROL(Ago, 55);
200 Aku ^= Du;
201 BCi = ROL(Aku, 39);
202 Ama ^= Da;
203 BCo = ROL(Ama, 41);
204 Ase ^= De;
205 BCu = ROL(Ase, 2);
206 Esa = BCa ^ ((~BCe) & BCi);
207 Ese = BCe ^ ((~BCi) & BCo);
208 Esi = BCi ^ ((~BCo) & BCu);
209 Eso = BCo ^ ((~BCu) & BCa);
210 Esu = BCu ^ ((~BCa) & BCe);
211
212 /* prepareTheta */
213 BCa = Eba ^ Ega ^ Eka ^ Ema ^ Esa;
214 BCe = Ebe ^ Ege ^ Eke ^ Eme ^ Ese;
215 BCi = Ebi ^ Egi ^ Eki ^ Emi ^ Esi;
216 BCo = Ebo ^ Ego ^ Eko ^ Emo ^ Eso;
217 BCu = Ebu ^ Egu ^ Eku ^ Emu ^ Esu;
218
219 /* thetaRhoPiChiIotaPrepareTheta(round+1, E, A) */
220 Da = BCu ^ ROL(BCe, 1);
221 De = BCa ^ ROL(BCi, 1);
222 Di = BCe ^ ROL(BCo, 1);
223 Do = BCi ^ ROL(BCu, 1);
224 Du = BCo ^ ROL(BCa, 1);
225
226 Eba ^= Da;
227 BCa = Eba;
228 Ege ^= De;
229 BCe = ROL(Ege, 44);
230 Eki ^= Di;
231 BCi = ROL(Eki, 43);
232 Emo ^= Do;
233 BCo = ROL(Emo, 21);
234 Esu ^= Du;
235 BCu = ROL(Esu, 14);
236 Aba = BCa ^ ((~BCe) & BCi);
237 Aba ^= KeccakF_RoundConstants[round + 1];
238 Abe = BCe ^ ((~BCi) & BCo);
239 Abi = BCi ^ ((~BCo) & BCu);
240 Abo = BCo ^ ((~BCu) & BCa);
241 Abu = BCu ^ ((~BCa) & BCe);
242
243 Ebo ^= Do;
244 BCa = ROL(Ebo, 28);
245 Egu ^= Du;
246 BCe = ROL(Egu, 20);
247 Eka ^= Da;
248 BCi = ROL(Eka, 3);
249 Eme ^= De;
250 BCo = ROL(Eme, 45);
251 Esi ^= Di;
252 BCu = ROL(Esi, 61);
253 Aga = BCa ^ ((~BCe) & BCi);
254 Age = BCe ^ ((~BCi) & BCo);
255 Agi = BCi ^ ((~BCo) & BCu);
256 Ago = BCo ^ ((~BCu) & BCa);
257 Agu = BCu ^ ((~BCa) & BCe);
258
259 Ebe ^= De;
260 BCa = ROL(Ebe, 1);
261 Egi ^= Di;
262 BCe = ROL(Egi, 6);
263 Eko ^= Do;
264 BCi = ROL(Eko, 25);
265 Emu ^= Du;
266 BCo = ROL(Emu, 8);
267 Esa ^= Da;
268 BCu = ROL(Esa, 18);
269 Aka = BCa ^ ((~BCe) & BCi);
270 Ake = BCe ^ ((~BCi) & BCo);
271 Aki = BCi ^ ((~BCo) & BCu);
272 Ako = BCo ^ ((~BCu) & BCa);
273 Aku = BCu ^ ((~BCa) & BCe);
274
275 Ebu ^= Du;
276 BCa = ROL(Ebu, 27);
277 Ega ^= Da;
278 BCe = ROL(Ega, 36);
279 Eke ^= De;
280 BCi = ROL(Eke, 10);
281 Emi ^= Di;
282 BCo = ROL(Emi, 15);
283 Eso ^= Do;
284 BCu = ROL(Eso, 56);
285 Ama = BCa ^ ((~BCe) & BCi);
286 Ame = BCe ^ ((~BCi) & BCo);
287 Ami = BCi ^ ((~BCo) & BCu);
288 Amo = BCo ^ ((~BCu) & BCa);
289 Amu = BCu ^ ((~BCa) & BCe);
290
291 Ebi ^= Di;
292 BCa = ROL(Ebi, 62);
293 Ego ^= Do;
294 BCe = ROL(Ego, 55);
295 Eku ^= Du;
296 BCi = ROL(Eku, 39);
297 Ema ^= Da;
298 BCo = ROL(Ema, 41);
299 Ese ^= De;
300 BCu = ROL(Ese, 2);
301 Asa = BCa ^ ((~BCe) & BCi);
302 Ase = BCe ^ ((~BCi) & BCo);
303 Asi = BCi ^ ((~BCo) & BCu);
304 Aso = BCo ^ ((~BCu) & BCa);
305 Asu = BCu ^ ((~BCa) & BCe);
306 }
307
308 /* copyToState(state, A) */
309 state[0] = Aba;
310 state[1] = Abe;
311 state[2] = Abi;
312 state[3] = Abo;
313 state[4] = Abu;
314 state[5] = Aga;
315 state[6] = Age;
316 state[7] = Agi;
317 state[8] = Ago;
318 state[9] = Agu;
319 state[10] = Aka;
320 state[11] = Ake;
321 state[12] = Aki;
322 state[13] = Ako;
323 state[14] = Aku;
324 state[15] = Ama;
325 state[16] = Ame;
326 state[17] = Ami;
327 state[18] = Amo;
328 state[19] = Amu;
329 state[20] = Asa;
330 state[21] = Ase;
331 state[22] = Asi;
332 state[23] = Aso;
333 state[24] = Asu;
334 }
335
336 /*************************************************
337 * Name: keccak_absorb
338 *
339 * Description: Absorb step of Keccak;
340 * non-incremental, starts by zeroeing the state.
341 *
342 * Arguments: - uint64_t *s: pointer to (uninitialized) output Keccak state
343 * - uint32_t r: rate in bytes (e.g., 168 for SHAKE128)
344 * - const uint8_t *m: pointer to input to be absorbed into s
345 * - size_t mlen: length of input in bytes
346 * - uint8_t p: domain-separation byte for different
347 * Keccak-derived functions
348 **************************************************/
keccak_absorb(uint64_t * s,uint32_t r,const uint8_t * m,size_t mlen,uint8_t p)349 static void keccak_absorb(uint64_t *s, uint32_t r, const uint8_t *m, size_t mlen, uint8_t p) {
350 size_t i;
351 uint8_t t[200];
352
353 /* Zero state */
354 for (i = 0; i < 25; ++i) {
355 s[i] = 0;
356 }
357
358 while (mlen >= r) {
359 for (i = 0; i < r / 8; ++i) {
360 s[i] ^= load64(m + 8 * i);
361 }
362
363 KeccakF1600_StatePermute(s);
364 mlen -= r;
365 m += r;
366 }
367
368 for (i = 0; i < r; ++i) {
369 t[i] = 0;
370 }
371 for (i = 0; i < mlen; ++i) {
372 t[i] = m[i];
373 }
374 t[i] = p;
375 t[r - 1] |= 128;
376 for (i = 0; i < r / 8; ++i) {
377 s[i] ^= load64(t + 8 * i);
378 }
379 }
380
381 /*************************************************
382 * Name: keccak_squeezeblocks
383 *
384 * Description: Squeeze step of Keccak. Squeezes full blocks of r bytes each.
385 * Modifies the state. Can be called multiple times to keep
386 * squeezing, i.e., is incremental.
387 *
388 * Arguments: - uint8_t *h: pointer to output blocks
389 * - size_t nblocks: number of blocks to be
390 * squeezed (written to h)
391 * - uint64_t *s: pointer to input/output Keccak state
392 * - uint32_t r: rate in bytes (e.g., 168 for SHAKE128)
393 **************************************************/
keccak_squeezeblocks(uint8_t * h,size_t nblocks,uint64_t * s,uint32_t r)394 static void keccak_squeezeblocks(uint8_t *h, size_t nblocks, uint64_t *s, uint32_t r) {
395 while (nblocks > 0) {
396 KeccakF1600_StatePermute(s);
397 for (size_t i = 0; i < (r >> 3); i++) {
398 store64(h + 8 * i, s[i]);
399 }
400 h += r;
401 nblocks--;
402 }
403 }
404
405 /*************************************************
406 * Name: shake128_absorb
407 *
408 * Description: Absorb step of the SHAKE128 XOF.
409 * non-incremental, starts by zeroeing the state.
410 *
411 * Arguments: - uint64_t *s: pointer to (uninitialized) output Keccak state
412 * - const uint8_t *input: pointer to input to be absorbed
413 * into s
414 * - size_t inlen: length of input in bytes
415 **************************************************/
shake128_absorb(shake128ctx * state,const uint8_t * input,size_t inlen)416 void shake128_absorb(shake128ctx *state, const uint8_t *input, size_t inlen) {
417 keccak_absorb(state->ctx, S2N_KYBER_512_R3_SHAKE128_RATE, input, inlen, 0x1F);
418 }
419
420 /*************************************************
421 * Name: shake128_squeezeblocks
422 *
423 * Description: Squeeze step of SHAKE128 XOF. Squeezes full blocks of
424 * SHAKE128_RATE bytes each. Modifies the state. Can be called
425 * multiple times to keep squeezing, i.e., is incremental.
426 *
427 * Arguments: - uint8_t *output: pointer to output blocks
428 * - size_t nblocks: number of blocks to be squeezed
429 * (written to output)
430 * - shake128ctx *state: pointer to input/output Keccak state
431 **************************************************/
shake128_squeezeblocks(uint8_t * output,size_t nblocks,shake128ctx * state)432 void shake128_squeezeblocks(uint8_t *output, size_t nblocks, shake128ctx *state) {
433 keccak_squeezeblocks(output, nblocks, state->ctx, S2N_KYBER_512_R3_SHAKE128_RATE);
434 }
435
436 /*************************************************
437 * Name: shake256_absorb
438 *
439 * Description: Absorb step of the SHAKE256 XOF.
440 * non-incremental, starts by zeroeing the state.
441 *
442 * Arguments: - shake256ctx *state: pointer to (uninitialized) output Keccak state
443 * - const uint8_t *input: pointer to input to be absorbed
444 * into s
445 * - size_t inlen: length of input in bytes
446 **************************************************/
shake256_absorb(shake256ctx * state,const uint8_t * input,size_t inlen)447 void shake256_absorb(shake256ctx *state, const uint8_t *input, size_t inlen) {
448 keccak_absorb(state->ctx, S2N_KYBER_512_R3_SHAKE256_RATE, input, inlen, 0x1F);
449 }
450
451 /*************************************************
452 * Name: shake256_squeezeblocks
453 *
454 * Description: Squeeze step of SHAKE256 XOF. Squeezes full blocks of
455 * SHAKE256_RATE bytes each. Modifies the state. Can be called
456 * multiple times to keep squeezing, i.e., is incremental.
457 *
458 * Arguments: - uint8_t *output: pointer to output blocks
459 * - size_t nblocks: number of blocks to be squeezed
460 * (written to output)
461 * - shake256ctx *state: pointer to input/output Keccak state
462 **************************************************/
shake256_squeezeblocks(uint8_t * output,size_t nblocks,shake256ctx * state)463 void shake256_squeezeblocks(uint8_t *output, size_t nblocks, shake256ctx *state) {
464 keccak_squeezeblocks(output, nblocks, state->ctx, S2N_KYBER_512_R3_SHAKE256_RATE);
465 }
466
467 /*************************************************
468 * Name: shake256
469 *
470 * Description: SHAKE256 XOF with non-incremental API
471 *
472 * Arguments: - uint8_t *output: pointer to output
473 * - size_t outlen: requested output length in bytes
474 * - const uint8_t *input: pointer to input
475 * - size_t inlen: length of input in bytes
476 **************************************************/
shake256(uint8_t * output,size_t outlen,const uint8_t * input,size_t inlen)477 void shake256(uint8_t *output, size_t outlen, const uint8_t *input, size_t inlen) {
478 size_t nblocks = outlen / S2N_KYBER_512_R3_SHAKE256_RATE;
479 uint8_t t[S2N_KYBER_512_R3_SHAKE256_RATE];
480 shake256ctx s;
481
482 shake256_absorb(&s, input, inlen);
483 shake256_squeezeblocks(output, nblocks, &s);
484
485 output += nblocks * S2N_KYBER_512_R3_SHAKE256_RATE;
486 outlen -= nblocks * S2N_KYBER_512_R3_SHAKE256_RATE;
487
488 if (outlen) {
489 shake256_squeezeblocks(t, 1, &s);
490 for (size_t i = 0; i < outlen; ++i) {
491 output[i] = t[i];
492 }
493 }
494 }
495
496 /*************************************************
497 * Name: sha3_256
498 *
499 * Description: SHA3-256 with non-incremental API
500 *
501 * Arguments: - uint8_t *output: pointer to output
502 * - const uint8_t *input: pointer to input
503 * - size_t inlen: length of input in bytes
504 **************************************************/
sha3_256(uint8_t * output,const uint8_t * input,size_t inlen)505 void sha3_256(uint8_t *output, const uint8_t *input, size_t inlen) {
506 uint64_t s[25];
507 uint8_t t[S2N_KYBER_512_R3_SHA3_256_RATE];
508
509 /* Absorb input */
510 keccak_absorb(s, S2N_KYBER_512_R3_SHA3_256_RATE, input, inlen, 0x06);
511
512 /* Squeeze output */
513 keccak_squeezeblocks(t, 1, s, S2N_KYBER_512_R3_SHA3_256_RATE);
514
515 for (size_t i = 0; i < 32; i++) {
516 output[i] = t[i];
517 }
518 }
519
520 /*************************************************
521 * Name: sha3_512
522 *
523 * Description: SHA3-512 with non-incremental API
524 *
525 * Arguments: - uint8_t *output: pointer to output
526 * - const uint8_t *input: pointer to input
527 * - size_t inlen: length of input in bytes
528 **************************************************/
sha3_512(uint8_t * output,const uint8_t * input,size_t inlen)529 void sha3_512(uint8_t *output, const uint8_t *input, size_t inlen) {
530 uint64_t s[25];
531 uint8_t t[S2N_KYBER_512_R3_SHA3_512_RATE];
532
533 /* Absorb input */
534 keccak_absorb(s, S2N_KYBER_512_R3_SHA3_512_RATE, input, inlen, 0x06);
535
536 /* Squeeze output */
537 keccak_squeezeblocks(t, 1, s, S2N_KYBER_512_R3_SHA3_512_RATE);
538
539 for (size_t i = 0; i < 64; i++) {
540 output[i] = t[i];
541 }
542 }
543