Keccak: Add SHAKE Extendable-Output Functions
[libgcrypt.git] / cipher / keccak.c
1 /* keccak.c - SHA3 hash functions
2  * Copyright (C) 2015  g10 Code GmbH
3  *
4  * This file is part of Libgcrypt.
5  *
6  * Libgcrypt is free software; you can redistribute it and/or modify
7  * it under the terms of the GNU Lesser general Public License as
8  * published by the Free Software Foundation; either version 2.1 of
9  * the License, or (at your option) any later version.
10  *
11  * Libgcrypt is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public
17  * License along with this program; if not, see <http://www.gnu.org/licenses/>.
18  */
19
20
21 #include <config.h>
22 #include <string.h>
23 #include "g10lib.h"
24 #include "bithelp.h"
25 #include "bufhelp.h"
26 #include "cipher.h"
27 #include "hash-common.h"
28
29
30
31 /* USE_64BIT indicates whether to use 64-bit generic implementation.
32  * USE_32BIT indicates whether to use 32-bit generic implementation. */
33 #undef USE_64BIT
34 #if defined(__x86_64__) || SIZEOF_UNSIGNED_LONG == 8
35 # define USE_64BIT 1
36 #else
37 # define USE_32BIT 1
38 #endif
39
40
41 /* USE_64BIT_BMI2 indicates whether to compile with 64-bit Intel BMI2 code. */
42 #undef USE_64BIT_BMI2
43 #if defined(USE_64BIT) && defined(HAVE_GCC_INLINE_ASM_BMI2)
44 # define USE_64BIT_BMI2 1
45 #endif
46
47
48 /* USE_64BIT_SHLD indicates whether to compile with 64-bit Intel SHLD code. */
49 #undef USE_64BIT_SHLD
50 #if defined(USE_64BIT) && defined (__GNUC__) && defined(__x86_64__)
51 # define USE_64BIT_SHLD 1
52 #endif
53
54
55 /* USE_32BIT_BMI2 indicates whether to compile with 32-bit Intel BMI2 code. */
56 #undef USE_32BIT_BMI2
57 #if defined(USE_32BIT) && defined(HAVE_GCC_INLINE_ASM_BMI2)
58 # define USE_32BIT_BMI2 1
59 #endif
60
61
62 #ifdef USE_64BIT
63 # define NEED_COMMON64 1
64 #endif
65
66 #ifdef USE_32BIT
67 # define NEED_COMMON32BI 1
68 #endif
69
70
71 #define SHA3_DELIMITED_SUFFIX 0x06
72 #define SHAKE_DELIMITED_SUFFIX 0x1F
73
74
75 typedef struct
76 {
77   union {
78 #ifdef NEED_COMMON64
79     u64 state64[25];
80 #endif
81 #ifdef NEED_COMMON32BI
82     u32 state32bi[50];
83 #endif
84   } u;
85 } KECCAK_STATE;
86
87
88 typedef struct
89 {
90   unsigned int (*permute)(KECCAK_STATE *hd);
91   unsigned int (*absorb)(KECCAK_STATE *hd, int pos, const byte *lanes,
92                          unsigned int nlanes, int blocklanes);
93   unsigned int (*extract) (KECCAK_STATE *hd, unsigned int pos, byte *outbuf,
94                            unsigned int outlen);
95 } keccak_ops_t;
96
97
98 typedef struct KECCAK_CONTEXT_S
99 {
100   KECCAK_STATE state;
101   unsigned int outlen;
102   unsigned int blocksize;
103   unsigned int count;
104   unsigned int suffix;
105   const keccak_ops_t *ops;
106 } KECCAK_CONTEXT;
107
108
109
110 #ifdef NEED_COMMON64
111
112 static const u64 round_consts_64bit[24] =
113 {
114   U64_C(0x0000000000000001), U64_C(0x0000000000008082),
115   U64_C(0x800000000000808A), U64_C(0x8000000080008000),
116   U64_C(0x000000000000808B), U64_C(0x0000000080000001),
117   U64_C(0x8000000080008081), U64_C(0x8000000000008009),
118   U64_C(0x000000000000008A), U64_C(0x0000000000000088),
119   U64_C(0x0000000080008009), U64_C(0x000000008000000A),
120   U64_C(0x000000008000808B), U64_C(0x800000000000008B),
121   U64_C(0x8000000000008089), U64_C(0x8000000000008003),
122   U64_C(0x8000000000008002), U64_C(0x8000000000000080),
123   U64_C(0x000000000000800A), U64_C(0x800000008000000A),
124   U64_C(0x8000000080008081), U64_C(0x8000000000008080),
125   U64_C(0x0000000080000001), U64_C(0x8000000080008008)
126 };
127
128 static unsigned int
129 keccak_extract64(KECCAK_STATE *hd, unsigned int pos, byte *outbuf,
130                  unsigned int outlen)
131 {
132   unsigned int i;
133
134   /* NOTE: when pos == 0, hd and outbuf may point to same memory (SHA-3). */
135
136   for (i = pos; i < pos + outlen / 8 + !!(outlen % 8); i++)
137     {
138       u64 tmp = hd->u.state64[i];
139       buf_put_le64(outbuf, tmp);
140       outbuf += 8;
141     }
142
143   return 0;
144 }
145
146 #endif /* NEED_COMMON64 */
147
148
149 #ifdef NEED_COMMON32BI
150
151 static const u32 round_consts_32bit[2 * 24] =
152 {
153   0x00000001UL, 0x00000000UL, 0x00000000UL, 0x00000089UL,
154   0x00000000UL, 0x8000008bUL, 0x00000000UL, 0x80008080UL,
155   0x00000001UL, 0x0000008bUL, 0x00000001UL, 0x00008000UL,
156   0x00000001UL, 0x80008088UL, 0x00000001UL, 0x80000082UL,
157   0x00000000UL, 0x0000000bUL, 0x00000000UL, 0x0000000aUL,
158   0x00000001UL, 0x00008082UL, 0x00000000UL, 0x00008003UL,
159   0x00000001UL, 0x0000808bUL, 0x00000001UL, 0x8000000bUL,
160   0x00000001UL, 0x8000008aUL, 0x00000001UL, 0x80000081UL,
161   0x00000000UL, 0x80000081UL, 0x00000000UL, 0x80000008UL,
162   0x00000000UL, 0x00000083UL, 0x00000000UL, 0x80008003UL,
163   0x00000001UL, 0x80008088UL, 0x00000000UL, 0x80000088UL,
164   0x00000001UL, 0x00008000UL, 0x00000000UL, 0x80008082UL
165 };
166
167 static unsigned int
168 keccak_extract32bi(KECCAK_STATE *hd, unsigned int pos, byte *outbuf,
169                    unsigned int outlen)
170 {
171   unsigned int i;
172   u32 x0;
173   u32 x1;
174   u32 t;
175
176   /* NOTE: when pos == 0, hd and outbuf may point to same memory (SHA-3). */
177
178   for (i = pos; i < pos + outlen / 8 + !!(outlen % 8); i++)
179     {
180       x0 = hd->u.state32bi[i * 2 + 0];
181       x1 = hd->u.state32bi[i * 2 + 1];
182
183       t = (x0 & 0x0000FFFFUL) + (x1 << 16);
184       x1 = (x0 >> 16) + (x1 & 0xFFFF0000UL);
185       x0 = t;
186       t = (x0 ^ (x0 >> 8)) & 0x0000FF00UL; x0 = x0 ^ t ^ (t << 8);
187       t = (x0 ^ (x0 >> 4)) & 0x00F000F0UL; x0 = x0 ^ t ^ (t << 4);
188       t = (x0 ^ (x0 >> 2)) & 0x0C0C0C0CUL; x0 = x0 ^ t ^ (t << 2);
189       t = (x0 ^ (x0 >> 1)) & 0x22222222UL; x0 = x0 ^ t ^ (t << 1);
190       t = (x1 ^ (x1 >> 8)) & 0x0000FF00UL; x1 = x1 ^ t ^ (t << 8);
191       t = (x1 ^ (x1 >> 4)) & 0x00F000F0UL; x1 = x1 ^ t ^ (t << 4);
192       t = (x1 ^ (x1 >> 2)) & 0x0C0C0C0CUL; x1 = x1 ^ t ^ (t << 2);
193       t = (x1 ^ (x1 >> 1)) & 0x22222222UL; x1 = x1 ^ t ^ (t << 1);
194
195       buf_put_le32(&outbuf[0], x0);
196       buf_put_le32(&outbuf[4], x1);
197       outbuf += 8;
198     }
199
200   return 0;
201 }
202
203 static inline void
204 keccak_absorb_lane32bi(u32 *lane, u32 x0, u32 x1)
205 {
206   u32 t;
207
208   t = (x0 ^ (x0 >> 1)) & 0x22222222UL; x0 = x0 ^ t ^ (t << 1);
209   t = (x0 ^ (x0 >> 2)) & 0x0C0C0C0CUL; x0 = x0 ^ t ^ (t << 2);
210   t = (x0 ^ (x0 >> 4)) & 0x00F000F0UL; x0 = x0 ^ t ^ (t << 4);
211   t = (x0 ^ (x0 >> 8)) & 0x0000FF00UL; x0 = x0 ^ t ^ (t << 8);
212   t = (x1 ^ (x1 >> 1)) & 0x22222222UL; x1 = x1 ^ t ^ (t << 1);
213   t = (x1 ^ (x1 >> 2)) & 0x0C0C0C0CUL; x1 = x1 ^ t ^ (t << 2);
214   t = (x1 ^ (x1 >> 4)) & 0x00F000F0UL; x1 = x1 ^ t ^ (t << 4);
215   t = (x1 ^ (x1 >> 8)) & 0x0000FF00UL; x1 = x1 ^ t ^ (t << 8);
216   lane[0] ^= (x0 & 0x0000FFFFUL) + (x1 << 16);
217   lane[1] ^= (x0 >> 16) + (x1 & 0xFFFF0000UL);
218 }
219
220 #endif /* NEED_COMMON32BI */
221
222
223 /* Construct generic 64-bit implementation. */
224 #ifdef USE_64BIT
225
226 # define ANDN64(x, y) (~(x) & (y))
227 # define ROL64(x, n) (((x) << ((unsigned int)n & 63)) | \
228                       ((x) >> ((64 - (unsigned int)(n)) & 63)))
229
230 # define KECCAK_F1600_PERMUTE_FUNC_NAME keccak_f1600_state_permute64
231 # include "keccak_permute_64.h"
232
233 # undef ANDN64
234 # undef ROL64
235 # undef KECCAK_F1600_PERMUTE_FUNC_NAME
236
237 static unsigned int
238 keccak_absorb_lanes64(KECCAK_STATE *hd, int pos, const byte *lanes,
239                       unsigned int nlanes, int blocklanes)
240 {
241   unsigned int burn = 0;
242
243   while (nlanes)
244     {
245       hd->u.state64[pos] ^= buf_get_le64(lanes);
246       lanes += 8;
247       nlanes--;
248
249       if (++pos == blocklanes)
250         {
251           burn = keccak_f1600_state_permute64(hd);
252           pos = 0;
253         }
254     }
255
256   return burn;
257 }
258
259 static const keccak_ops_t keccak_generic64_ops =
260 {
261   .permute = keccak_f1600_state_permute64,
262   .absorb = keccak_absorb_lanes64,
263   .extract = keccak_extract64,
264 };
265
266 #endif /* USE_64BIT */
267
268
269 /* Construct 64-bit Intel SHLD implementation. */
270 #ifdef USE_64BIT_SHLD
271
272 # define ANDN64(x, y) (~(x) & (y))
273 # define ROL64(x, n) ({ \
274                         u64 tmp = (x); \
275                         asm ("shldq %1, %0, %0" \
276                              : "+r" (tmp) \
277                              : "J" ((n) & 63) \
278                              : "cc"); \
279                         tmp; })
280
281 # define KECCAK_F1600_PERMUTE_FUNC_NAME keccak_f1600_state_permute64_shld
282 # include "keccak_permute_64.h"
283
284 # undef ANDN64
285 # undef ROL64
286 # undef KECCAK_F1600_PERMUTE_FUNC_NAME
287
288 static unsigned int
289 keccak_absorb_lanes64_shld(KECCAK_STATE *hd, int pos, const byte *lanes,
290                            unsigned int nlanes, int blocklanes)
291 {
292   unsigned int burn = 0;
293
294   while (nlanes)
295     {
296       hd->u.state64[pos] ^= buf_get_le64(lanes);
297       lanes += 8;
298       nlanes--;
299
300       if (++pos == blocklanes)
301         {
302           burn = keccak_f1600_state_permute64_shld(hd);
303           pos = 0;
304         }
305     }
306
307   return burn;
308 }
309
310 static const keccak_ops_t keccak_shld_64_ops =
311 {
312   .permute = keccak_f1600_state_permute64_shld,
313   .absorb = keccak_absorb_lanes64_shld,
314   .extract = keccak_extract64,
315 };
316
317 #endif /* USE_64BIT_SHLD */
318
319
320 /* Construct 64-bit Intel BMI2 implementation. */
321 #ifdef USE_64BIT_BMI2
322
323 # define ANDN64(x, y) ({ \
324                         u64 tmp; \
325                         asm ("andnq %2, %1, %0" \
326                              : "=r" (tmp) \
327                              : "r0" (x), "rm" (y)); \
328                         tmp; })
329
330 # define ROL64(x, n) ({ \
331                         u64 tmp; \
332                         asm ("rorxq %2, %1, %0" \
333                              : "=r" (tmp) \
334                              : "rm0" (x), "J" (64 - ((n) & 63))); \
335                         tmp; })
336
337 # define KECCAK_F1600_PERMUTE_FUNC_NAME keccak_f1600_state_permute64_bmi2
338 # include "keccak_permute_64.h"
339
340 # undef ANDN64
341 # undef ROL64
342 # undef KECCAK_F1600_PERMUTE_FUNC_NAME
343
344 static unsigned int
345 keccak_absorb_lanes64_bmi2(KECCAK_STATE *hd, int pos, const byte *lanes,
346                            unsigned int nlanes, int blocklanes)
347 {
348   unsigned int burn = 0;
349
350   while (nlanes)
351     {
352       hd->u.state64[pos] ^= buf_get_le64(lanes);
353       lanes += 8;
354       nlanes--;
355
356       if (++pos == blocklanes)
357         {
358           burn = keccak_f1600_state_permute64_bmi2(hd);
359           pos = 0;
360         }
361     }
362
363   return burn;
364 }
365
366 static const keccak_ops_t keccak_bmi2_64_ops =
367 {
368   .permute = keccak_f1600_state_permute64_bmi2,
369   .absorb = keccak_absorb_lanes64_bmi2,
370   .extract = keccak_extract64,
371 };
372
373 #endif /* USE_64BIT_BMI2 */
374
375
376 /* Construct generic 32-bit implementation. */
377 #ifdef USE_32BIT
378
379 # define ANDN32(x, y) (~(x) & (y))
380 # define ROL32(x, n) (((x) << ((unsigned int)n & 31)) | \
381                       ((x) >> ((32 - (unsigned int)(n)) & 31)))
382
383 # define KECCAK_F1600_PERMUTE_FUNC_NAME keccak_f1600_state_permute32bi
384 # include "keccak_permute_32.h"
385
386 # undef ANDN32
387 # undef ROL32
388 # undef KECCAK_F1600_PERMUTE_FUNC_NAME
389
390 static unsigned int
391 keccak_absorb_lanes32bi(KECCAK_STATE *hd, int pos, const byte *lanes,
392                         unsigned int nlanes, int blocklanes)
393 {
394   unsigned int burn = 0;
395
396   while (nlanes)
397     {
398       keccak_absorb_lane32bi(&hd->u.state32bi[pos * 2],
399                              buf_get_le32(lanes + 0),
400                              buf_get_le32(lanes + 4));
401       lanes += 8;
402       nlanes--;
403
404       if (++pos == blocklanes)
405         {
406           burn = keccak_f1600_state_permute32bi(hd);
407           pos = 0;
408         }
409     }
410
411   return burn;
412 }
413
414 static const keccak_ops_t keccak_generic32bi_ops =
415 {
416   .permute = keccak_f1600_state_permute32bi,
417   .absorb = keccak_absorb_lanes32bi,
418   .extract = keccak_extract32bi,
419 };
420
421 #endif /* USE_32BIT */
422
423
424 /* Construct 32-bit Intel BMI2 implementation. */
425 #ifdef USE_32BIT_BMI2
426
427 # define ANDN32(x, y) ({ \
428                         u32 tmp; \
429                         asm ("andnl %2, %1, %0" \
430                              : "=r" (tmp) \
431                              : "r0" (x), "rm" (y)); \
432                         tmp; })
433
434 # define ROL32(x, n) ({ \
435                         u32 tmp; \
436                         asm ("rorxl %2, %1, %0" \
437                              : "=r" (tmp) \
438                              : "rm0" (x), "J" (32 - ((n) & 31))); \
439                         tmp; })
440
441 # define KECCAK_F1600_PERMUTE_FUNC_NAME keccak_f1600_state_permute32bi_bmi2
442 # include "keccak_permute_32.h"
443
444 # undef ANDN32
445 # undef ROL32
446 # undef KECCAK_F1600_PERMUTE_FUNC_NAME
447
448 static inline u32 pext(u32 x, u32 mask)
449 {
450   u32 tmp;
451   asm ("pextl %2, %1, %0" : "=r" (tmp) : "r0" (x), "rm" (mask));
452   return tmp;
453 }
454
455 static inline u32 pdep(u32 x, u32 mask)
456 {
457   u32 tmp;
458   asm ("pdepl %2, %1, %0" : "=r" (tmp) : "r0" (x), "rm" (mask));
459   return tmp;
460 }
461
462 static inline void
463 keccak_absorb_lane32bi_bmi2(u32 *lane, u32 x0, u32 x1)
464 {
465   x0 = pdep(pext(x0, 0x55555555), 0x0000ffff) | (pext(x0, 0xaaaaaaaa) << 16);
466   x1 = pdep(pext(x1, 0x55555555), 0x0000ffff) | (pext(x1, 0xaaaaaaaa) << 16);
467
468   lane[0] ^= (x0 & 0x0000FFFFUL) + (x1 << 16);
469   lane[1] ^= (x0 >> 16) + (x1 & 0xFFFF0000UL);
470 }
471
472 static unsigned int
473 keccak_absorb_lanes32bi_bmi2(KECCAK_STATE *hd, int pos, const byte *lanes,
474                              unsigned int nlanes, int blocklanes)
475 {
476   unsigned int burn = 0;
477
478   while (nlanes)
479     {
480       keccak_absorb_lane32bi_bmi2(&hd->u.state32bi[pos * 2],
481                                   buf_get_le32(lanes + 0),
482                                   buf_get_le32(lanes + 4));
483       lanes += 8;
484       nlanes--;
485
486       if (++pos == blocklanes)
487         {
488           burn = keccak_f1600_state_permute32bi_bmi2(hd);
489           pos = 0;
490         }
491     }
492
493   return burn;
494 }
495
496 static unsigned int
497 keccak_extract32bi_bmi2(KECCAK_STATE *hd, unsigned int pos, byte *outbuf,
498                         unsigned int outlen)
499 {
500   unsigned int i;
501   u32 x0;
502   u32 x1;
503   u32 t;
504
505   /* NOTE: when pos == 0, hd and outbuf may point to same memory (SHA-3). */
506
507   for (i = pos; i < pos + outlen / 8 + !!(outlen % 8); i++)
508     {
509       x0 = hd->u.state32bi[i * 2 + 0];
510       x1 = hd->u.state32bi[i * 2 + 1];
511
512       t = (x0 & 0x0000FFFFUL) + (x1 << 16);
513       x1 = (x0 >> 16) + (x1 & 0xFFFF0000UL);
514       x0 = t;
515
516       x0 = pdep(pext(x0, 0xffff0001), 0xaaaaaaab) | pdep(x0 >> 1, 0x55555554);
517       x1 = pdep(pext(x1, 0xffff0001), 0xaaaaaaab) | pdep(x1 >> 1, 0x55555554);
518
519       buf_put_le32(&outbuf[0], x0);
520       buf_put_le32(&outbuf[4], x1);
521       outbuf += 8;
522     }
523
524   return 0;
525 }
526
527 static const keccak_ops_t keccak_bmi2_32bi_ops =
528 {
529   .permute = keccak_f1600_state_permute32bi_bmi2,
530   .absorb = keccak_absorb_lanes32bi_bmi2,
531   .extract = keccak_extract32bi_bmi2,
532 };
533
534 #endif /* USE_32BIT */
535
536
537 static void
538 keccak_write (void *context, const void *inbuf_arg, size_t inlen)
539 {
540   KECCAK_CONTEXT *ctx = context;
541   const size_t bsize = ctx->blocksize;
542   const size_t blocklanes = bsize / 8;
543   const byte *inbuf = inbuf_arg;
544   unsigned int nburn, burn = 0;
545   unsigned int count, i;
546   unsigned int pos, nlanes;
547
548   count = ctx->count;
549
550   if (inlen && (count % 8))
551     {
552       byte lane[8] = { 0, };
553
554       /* Complete absorbing partial input lane. */
555
556       pos = count / 8;
557
558       for (i = count % 8; inlen && i < 8; i++)
559         {
560           lane[i] = *inbuf++;
561           inlen--;
562           count++;
563         }
564
565       if (count == bsize)
566         count = 0;
567
568       nburn = ctx->ops->absorb(&ctx->state, pos, lane, 1,
569                                (count % 8) ? -1 : blocklanes);
570       burn = nburn > burn ? nburn : burn;
571     }
572
573   /* Absorb full input lanes. */
574
575   pos = count / 8;
576   nlanes = inlen / 8;
577   if (nlanes > 0)
578     {
579       nburn = ctx->ops->absorb(&ctx->state, pos, inbuf, nlanes, blocklanes);
580       burn = nburn > burn ? nburn : burn;
581       inlen -= nlanes * 8;
582       inbuf += nlanes * 8;
583       count += nlanes * 8;
584       count = count % bsize;
585     }
586
587   if (inlen)
588     {
589       byte lane[8] = { 0, };
590
591       /* Absorb remaining partial input lane. */
592
593       pos = count / 8;
594
595       for (i = count % 8; inlen && i < 8; i++)
596         {
597           lane[i] = *inbuf++;
598           inlen--;
599           count++;
600         }
601
602       nburn = ctx->ops->absorb(&ctx->state, pos, lane, 1, -1);
603       burn = nburn > burn ? nburn : burn;
604
605       gcry_assert(count < bsize);
606     }
607
608   ctx->count = count;
609
610   if (burn)
611     _gcry_burn_stack (burn);
612 }
613
614
615 static void
616 keccak_init (int algo, void *context, unsigned int flags)
617 {
618   KECCAK_CONTEXT *ctx = context;
619   KECCAK_STATE *hd = &ctx->state;
620   unsigned int features = _gcry_get_hw_features ();
621
622   (void)flags;
623   (void)features;
624
625   memset (hd, 0, sizeof *hd);
626
627   ctx->count = 0;
628
629   /* Select generic implementation. */
630 #ifdef USE_64BIT
631   ctx->ops = &keccak_generic64_ops;
632 #elif defined USE_32BIT
633   ctx->ops = &keccak_generic32bi_ops;
634 #endif
635
636   /* Select optimized implementation based in hw features. */
637   if (0) {}
638 #ifdef USE_64BIT_BMI2
639   else if (features & HWF_INTEL_BMI2)
640     ctx->ops = &keccak_bmi2_64_ops;
641 #endif
642 #ifdef USE_32BIT_BMI2
643   else if (features & HWF_INTEL_BMI2)
644     ctx->ops = &keccak_bmi2_32bi_ops;
645 #endif
646 #ifdef USE_64BIT_SHLD
647   else if (features & HWF_INTEL_FAST_SHLD)
648     ctx->ops = &keccak_shld_64_ops;
649 #endif
650
651   /* Set input block size, in Keccak terms this is called 'rate'. */
652
653   switch (algo)
654     {
655     case GCRY_MD_SHA3_224:
656       ctx->suffix = SHA3_DELIMITED_SUFFIX;
657       ctx->blocksize = 1152 / 8;
658       ctx->outlen = 224 / 8;
659       break;
660     case GCRY_MD_SHA3_256:
661       ctx->suffix = SHA3_DELIMITED_SUFFIX;
662       ctx->blocksize = 1088 / 8;
663       ctx->outlen = 256 / 8;
664       break;
665     case GCRY_MD_SHA3_384:
666       ctx->suffix = SHA3_DELIMITED_SUFFIX;
667       ctx->blocksize = 832 / 8;
668       ctx->outlen = 384 / 8;
669       break;
670     case GCRY_MD_SHA3_512:
671       ctx->suffix = SHA3_DELIMITED_SUFFIX;
672       ctx->blocksize = 576 / 8;
673       ctx->outlen = 512 / 8;
674       break;
675     case GCRY_MD_SHAKE128:
676       ctx->suffix = SHAKE_DELIMITED_SUFFIX;
677       ctx->blocksize = 1344 / 8;
678       ctx->outlen = 0;
679       break;
680     case GCRY_MD_SHAKE256:
681       ctx->suffix = SHAKE_DELIMITED_SUFFIX;
682       ctx->blocksize = 1088 / 8;
683       ctx->outlen = 0;
684       break;
685     default:
686       BUG();
687     }
688 }
689
690 static void
691 sha3_224_init (void *context, unsigned int flags)
692 {
693   keccak_init (GCRY_MD_SHA3_224, context, flags);
694 }
695
696 static void
697 sha3_256_init (void *context, unsigned int flags)
698 {
699   keccak_init (GCRY_MD_SHA3_256, context, flags);
700 }
701
702 static void
703 sha3_384_init (void *context, unsigned int flags)
704 {
705   keccak_init (GCRY_MD_SHA3_384, context, flags);
706 }
707
708 static void
709 sha3_512_init (void *context, unsigned int flags)
710 {
711   keccak_init (GCRY_MD_SHA3_512, context, flags);
712 }
713
714 static void
715 shake128_init (void *context, unsigned int flags)
716 {
717   keccak_init (GCRY_MD_SHAKE128, context, flags);
718 }
719
720 static void
721 shake256_init (void *context, unsigned int flags)
722 {
723   keccak_init (GCRY_MD_SHAKE256, context, flags);
724 }
725
726 /* The routine final terminates the computation and
727  * returns the digest.
728  * The handle is prepared for a new cycle, but adding bytes to the
729  * handle will the destroy the returned buffer.
730  * Returns: 64 bytes representing the digest.  When used for sha384,
731  * we take the leftmost 48 of those bytes.
732  */
733 static void
734 keccak_final (void *context)
735 {
736   KECCAK_CONTEXT *ctx = context;
737   KECCAK_STATE *hd = &ctx->state;
738   const size_t bsize = ctx->blocksize;
739   const byte suffix = ctx->suffix;
740   unsigned int nburn, burn = 0;
741   unsigned int lastbytes;
742   byte lane[8];
743
744   lastbytes = ctx->count;
745
746   /* Do the padding and switch to the squeezing phase */
747
748   /* Absorb the last few bits and add the first bit of padding (which
749      coincides with the delimiter in delimited suffix) */
750   buf_put_le64(lane, (u64)suffix << ((lastbytes % 8) * 8));
751   nburn = ctx->ops->absorb(&ctx->state, lastbytes / 8, lane, 1, -1);
752   burn = nburn > burn ? nburn : burn;
753
754   /* Add the second bit of padding. */
755   buf_put_le64(lane, (u64)0x80 << (((bsize - 1) % 8) * 8));
756   nburn = ctx->ops->absorb(&ctx->state, (bsize - 1) / 8, lane, 1, -1);
757   burn = nburn > burn ? nburn : burn;
758
759   if (suffix == SHA3_DELIMITED_SUFFIX)
760     {
761       /* Switch to the squeezing phase. */
762       nburn = ctx->ops->permute(hd);
763       burn = nburn > burn ? nburn : burn;
764
765       /* Squeeze out the SHA3 digest. */
766       nburn = ctx->ops->extract(hd, 0, (void *)hd, ctx->outlen);
767       burn = nburn > burn ? nburn : burn;
768     }
769   else
770     {
771       /* Output for SHAKE can now be read with md_extract(). */
772
773       ctx->count = 0;
774     }
775
776   wipememory(lane, sizeof(lane));
777   if (burn)
778     _gcry_burn_stack (burn);
779 }
780
781
782 static byte *
783 keccak_read (void *context)
784 {
785   KECCAK_CONTEXT *ctx = (KECCAK_CONTEXT *) context;
786   KECCAK_STATE *hd = &ctx->state;
787   return (byte *)&hd->u;
788 }
789
790
791 static void
792 keccak_extract (void *context, void *out, size_t outlen)
793 {
794   KECCAK_CONTEXT *ctx = context;
795   KECCAK_STATE *hd = &ctx->state;
796   const size_t bsize = ctx->blocksize;
797   unsigned int nburn, burn = 0;
798   byte *outbuf = out;
799   unsigned int nlanes;
800   unsigned int nleft;
801   unsigned int count;
802   unsigned int i;
803   byte lane[8];
804
805   count = ctx->count;
806
807   while (count && outlen && (outlen < 8 || count % 8))
808     {
809       /* Extract partial lane. */
810       nburn = ctx->ops->extract(hd, count / 8, lane, 8);
811       burn = nburn > burn ? nburn : burn;
812
813       for (i = count % 8; outlen && i < 8; i++)
814         {
815           *outbuf++ = lane[i];
816           outlen--;
817           count++;
818         }
819
820       gcry_assert(count <= bsize);
821
822       if (count == bsize)
823         count = 0;
824     }
825
826   if (outlen >= 8 && count)
827     {
828       /* Extract tail of partial block. */
829       nlanes = outlen / 8;
830       nleft = (bsize - count) / 8;
831       nlanes = nlanes < nleft ? nlanes : nleft;
832
833       nburn = ctx->ops->extract(hd, count / 8, outbuf, nlanes * 8);
834       burn = nburn > burn ? nburn : burn;
835       outlen -= nlanes * 8;
836       outbuf += nlanes * 8;
837       count += nlanes * 8;
838
839       gcry_assert(count <= bsize);
840
841       if (count == bsize)
842         count = 0;
843     }
844
845   while (outlen >= bsize)
846     {
847       gcry_assert(count == 0);
848
849       /* Squeeze more. */
850       nburn = ctx->ops->permute(hd);
851       burn = nburn > burn ? nburn : burn;
852
853       /* Extract full block. */
854       nburn = ctx->ops->extract(hd, 0, outbuf, bsize);
855       burn = nburn > burn ? nburn : burn;
856
857       outlen -= bsize;
858       outbuf += bsize;
859     }
860
861   if (outlen)
862     {
863       gcry_assert(outlen < bsize);
864
865       if (count == 0)
866         {
867           /* Squeeze more. */
868           nburn = ctx->ops->permute(hd);
869           burn = nburn > burn ? nburn : burn;
870         }
871
872       if (outlen >= 8)
873         {
874           /* Extract head of partial block. */
875           nlanes = outlen / 8;
876           nburn = ctx->ops->extract(hd, count / 8, outbuf, nlanes * 8);
877           burn = nburn > burn ? nburn : burn;
878           outlen -= nlanes * 8;
879           outbuf += nlanes * 8;
880           count += nlanes * 8;
881
882           gcry_assert(count < bsize);
883         }
884
885       if (outlen)
886         {
887           /* Extract head of partial lane. */
888           nburn = ctx->ops->extract(hd, count / 8, lane, 8);
889           burn = nburn > burn ? nburn : burn;
890
891           for (i = count % 8; outlen && i < 8; i++)
892             {
893               *outbuf++ = lane[i];
894               outlen--;
895               count++;
896             }
897
898           gcry_assert(count < bsize);
899         }
900     }
901
902   ctx->count = count;
903
904   if (burn)
905     _gcry_burn_stack (burn);
906 }
907
908
909 \f
910 /*
911      Self-test section.
912  */
913
914
915 static gpg_err_code_t
916 selftests_keccak (int algo, int extended, selftest_report_func_t report)
917 {
918   const char *what;
919   const char *errtxt;
920   const char *short_hash;
921   const char *long_hash;
922   const char *one_million_a_hash;
923   int hash_len;
924
925   switch (algo)
926   {
927     default:
928       BUG();
929
930     case GCRY_MD_SHA3_224:
931       short_hash =
932         "\xe6\x42\x82\x4c\x3f\x8c\xf2\x4a\xd0\x92\x34\xee\x7d\x3c\x76\x6f"
933         "\xc9\xa3\xa5\x16\x8d\x0c\x94\xad\x73\xb4\x6f\xdf";
934       long_hash =
935         "\x54\x3e\x68\x68\xe1\x66\x6c\x1a\x64\x36\x30\xdf\x77\x36\x7a\xe5"
936         "\xa6\x2a\x85\x07\x0a\x51\xc1\x4c\xbf\x66\x5c\xbc";
937       one_million_a_hash =
938         "\xd6\x93\x35\xb9\x33\x25\x19\x2e\x51\x6a\x91\x2e\x6d\x19\xa1\x5c"
939         "\xb5\x1c\x6e\xd5\xc1\x52\x43\xe7\xa7\xfd\x65\x3c";
940       hash_len = 28;
941       break;
942
943     case GCRY_MD_SHA3_256:
944       short_hash =
945         "\x3a\x98\x5d\xa7\x4f\xe2\x25\xb2\x04\x5c\x17\x2d\x6b\xd3\x90\xbd"
946         "\x85\x5f\x08\x6e\x3e\x9d\x52\x5b\x46\xbf\xe2\x45\x11\x43\x15\x32";
947       long_hash =
948         "\x91\x6f\x60\x61\xfe\x87\x97\x41\xca\x64\x69\xb4\x39\x71\xdf\xdb"
949         "\x28\xb1\xa3\x2d\xc3\x6c\xb3\x25\x4e\x81\x2b\xe2\x7a\xad\x1d\x18";
950       one_million_a_hash =
951         "\x5c\x88\x75\xae\x47\x4a\x36\x34\xba\x4f\xd5\x5e\xc8\x5b\xff\xd6"
952         "\x61\xf3\x2a\xca\x75\xc6\xd6\x99\xd0\xcd\xcb\x6c\x11\x58\x91\xc1";
953       hash_len = 32;
954       break;
955
956     case GCRY_MD_SHA3_384:
957       short_hash =
958         "\xec\x01\x49\x82\x88\x51\x6f\xc9\x26\x45\x9f\x58\xe2\xc6\xad\x8d"
959         "\xf9\xb4\x73\xcb\x0f\xc0\x8c\x25\x96\xda\x7c\xf0\xe4\x9b\xe4\xb2"
960         "\x98\xd8\x8c\xea\x92\x7a\xc7\xf5\x39\xf1\xed\xf2\x28\x37\x6d\x25";
961       long_hash =
962         "\x79\x40\x7d\x3b\x59\x16\xb5\x9c\x3e\x30\xb0\x98\x22\x97\x47\x91"
963         "\xc3\x13\xfb\x9e\xcc\x84\x9e\x40\x6f\x23\x59\x2d\x04\xf6\x25\xdc"
964         "\x8c\x70\x9b\x98\xb4\x3b\x38\x52\xb3\x37\x21\x61\x79\xaa\x7f\xc7";
965       one_million_a_hash =
966         "\xee\xe9\xe2\x4d\x78\xc1\x85\x53\x37\x98\x34\x51\xdf\x97\xc8\xad"
967         "\x9e\xed\xf2\x56\xc6\x33\x4f\x8e\x94\x8d\x25\x2d\x5e\x0e\x76\x84"
968         "\x7a\xa0\x77\x4d\xdb\x90\xa8\x42\x19\x0d\x2c\x55\x8b\x4b\x83\x40";
969       hash_len = 48;
970       break;
971
972     case GCRY_MD_SHA3_512:
973       short_hash =
974         "\xb7\x51\x85\x0b\x1a\x57\x16\x8a\x56\x93\xcd\x92\x4b\x6b\x09\x6e"
975         "\x08\xf6\x21\x82\x74\x44\xf7\x0d\x88\x4f\x5d\x02\x40\xd2\x71\x2e"
976         "\x10\xe1\x16\xe9\x19\x2a\xf3\xc9\x1a\x7e\xc5\x76\x47\xe3\x93\x40"
977         "\x57\x34\x0b\x4c\xf4\x08\xd5\xa5\x65\x92\xf8\x27\x4e\xec\x53\xf0";
978       long_hash =
979         "\xaf\xeb\xb2\xef\x54\x2e\x65\x79\xc5\x0c\xad\x06\xd2\xe5\x78\xf9"
980         "\xf8\xdd\x68\x81\xd7\xdc\x82\x4d\x26\x36\x0f\xee\xbf\x18\xa4\xfa"
981         "\x73\xe3\x26\x11\x22\x94\x8e\xfc\xfd\x49\x2e\x74\xe8\x2e\x21\x89"
982         "\xed\x0f\xb4\x40\xd1\x87\xf3\x82\x27\x0c\xb4\x55\xf2\x1d\xd1\x85";
983       one_million_a_hash =
984         "\x3c\x3a\x87\x6d\xa1\x40\x34\xab\x60\x62\x7c\x07\x7b\xb9\x8f\x7e"
985         "\x12\x0a\x2a\x53\x70\x21\x2d\xff\xb3\x38\x5a\x18\xd4\xf3\x88\x59"
986         "\xed\x31\x1d\x0a\x9d\x51\x41\xce\x9c\xc5\xc6\x6e\xe6\x89\xb2\x66"
987         "\xa8\xaa\x18\xac\xe8\x28\x2a\x0e\x0d\xb5\x96\xc9\x0b\x0a\x7b\x87";
988       hash_len = 64;
989       break;
990
991     case GCRY_MD_SHAKE128:
992       short_hash =
993         "\x58\x81\x09\x2d\xd8\x18\xbf\x5c\xf8\xa3\xdd\xb7\x93\xfb\xcb\xa7"
994         "\x40\x97\xd5\xc5\x26\xa6\xd3\x5f\x97\xb8\x33\x51\x94\x0f\x2c\xc8";
995       long_hash =
996         "\x7b\x6d\xf6\xff\x18\x11\x73\xb6\xd7\x89\x8d\x7f\xf6\x3f\xb0\x7b"
997         "\x7c\x23\x7d\xaf\x47\x1a\x5a\xe5\x60\x2a\xdb\xcc\xef\x9c\xcf\x4b";
998       one_million_a_hash =
999         "\x9d\x22\x2c\x79\xc4\xff\x9d\x09\x2c\xf6\xca\x86\x14\x3a\xa4\x11"
1000         "\xe3\x69\x97\x38\x08\xef\x97\x09\x32\x55\x82\x6c\x55\x72\xef\x58";
1001       hash_len = 32;
1002       break;
1003
1004     case GCRY_MD_SHAKE256:
1005       short_hash =
1006         "\x48\x33\x66\x60\x13\x60\xa8\x77\x1c\x68\x63\x08\x0c\xc4\x11\x4d"
1007         "\x8d\xb4\x45\x30\xf8\xf1\xe1\xee\x4f\x94\xea\x37\xe7\x8b\x57\x39";
1008       long_hash =
1009         "\x98\xbe\x04\x51\x6c\x04\xcc\x73\x59\x3f\xef\x3e\xd0\x35\x2e\xa9"
1010         "\xf6\x44\x39\x42\xd6\x95\x0e\x29\xa3\x72\xa6\x81\xc3\xde\xaf\x45";
1011       one_million_a_hash =
1012         "\x35\x78\xa7\xa4\xca\x91\x37\x56\x9c\xdf\x76\xed\x61\x7d\x31\xbb"
1013         "\x99\x4f\xca\x9c\x1b\xbf\x8b\x18\x40\x13\xde\x82\x34\xdf\xd1\x3a";
1014       hash_len = 32;
1015       break;
1016   }
1017
1018   what = "short string";
1019   errtxt = _gcry_hash_selftest_check_one (algo, 0, "abc", 3, short_hash,
1020                                           hash_len);
1021   if (errtxt)
1022     goto failed;
1023
1024   if (extended)
1025     {
1026       what = "long string";
1027       errtxt = _gcry_hash_selftest_check_one
1028         (algo, 0,
1029         "abcdefghbcdefghicdefghijdefghijkefghijklfghijklmghijklmn"
1030         "hijklmnoijklmnopjklmnopqklmnopqrlmnopqrsmnopqrstnopqrstu", 112,
1031         long_hash, hash_len);
1032       if (errtxt)
1033         goto failed;
1034
1035       what = "one million \"a\"";
1036       errtxt = _gcry_hash_selftest_check_one (algo, 1, NULL, 0,
1037                                               one_million_a_hash, hash_len);
1038       if (errtxt)
1039         goto failed;
1040     }
1041
1042   return 0; /* Succeeded. */
1043
1044 failed:
1045   if (report)
1046     report ("digest", algo, what, errtxt);
1047   return GPG_ERR_SELFTEST_FAILED;
1048 }
1049
1050
1051 /* Run a full self-test for ALGO and return 0 on success.  */
1052 static gpg_err_code_t
1053 run_selftests (int algo, int extended, selftest_report_func_t report)
1054 {
1055   gpg_err_code_t ec;
1056
1057   switch (algo)
1058     {
1059     case GCRY_MD_SHA3_224:
1060     case GCRY_MD_SHA3_256:
1061     case GCRY_MD_SHA3_384:
1062     case GCRY_MD_SHA3_512:
1063     case GCRY_MD_SHAKE128:
1064     case GCRY_MD_SHAKE256:
1065       ec = selftests_keccak (algo, extended, report);
1066       break;
1067     default:
1068       ec = GPG_ERR_DIGEST_ALGO;
1069       break;
1070     }
1071
1072   return ec;
1073 }
1074
1075
1076
1077 \f
1078 static byte sha3_224_asn[] = { 0x30 };
1079 static gcry_md_oid_spec_t oid_spec_sha3_224[] =
1080   {
1081     { "2.16.840.1.101.3.4.2.7" },
1082     /* PKCS#1 sha3_224WithRSAEncryption */
1083     { "?" },
1084     { NULL }
1085   };
1086 static byte sha3_256_asn[] = { 0x30 };
1087 static gcry_md_oid_spec_t oid_spec_sha3_256[] =
1088   {
1089     { "2.16.840.1.101.3.4.2.8" },
1090     /* PKCS#1 sha3_256WithRSAEncryption */
1091     { "?" },
1092     { NULL }
1093   };
1094 static byte sha3_384_asn[] = { 0x30 };
1095 static gcry_md_oid_spec_t oid_spec_sha3_384[] =
1096   {
1097     { "2.16.840.1.101.3.4.2.9" },
1098     /* PKCS#1 sha3_384WithRSAEncryption */
1099     { "?" },
1100     { NULL }
1101   };
1102 static byte sha3_512_asn[] = { 0x30 };
1103 static gcry_md_oid_spec_t oid_spec_sha3_512[] =
1104   {
1105     { "2.16.840.1.101.3.4.2.10" },
1106     /* PKCS#1 sha3_512WithRSAEncryption */
1107     { "?" },
1108     { NULL }
1109   };
1110 static byte shake128_asn[] = { 0x30 };
1111 static gcry_md_oid_spec_t oid_spec_shake128[] =
1112   {
1113     { "2.16.840.1.101.3.4.2.11" },
1114     /* PKCS#1 shake128WithRSAEncryption */
1115     { "?" },
1116     { NULL }
1117   };
1118 static byte shake256_asn[] = { 0x30 };
1119 static gcry_md_oid_spec_t oid_spec_shake256[] =
1120   {
1121     { "2.16.840.1.101.3.4.2.12" },
1122     /* PKCS#1 shake256WithRSAEncryption */
1123     { "?" },
1124     { NULL }
1125   };
1126
1127 gcry_md_spec_t _gcry_digest_spec_sha3_224 =
1128   {
1129     GCRY_MD_SHA3_224, {0, 1},
1130     "SHA3-224", sha3_224_asn, DIM (sha3_224_asn), oid_spec_sha3_224, 28,
1131     sha3_224_init, keccak_write, keccak_final, keccak_read, NULL,
1132     sizeof (KECCAK_CONTEXT),
1133     run_selftests
1134   };
1135 gcry_md_spec_t _gcry_digest_spec_sha3_256 =
1136   {
1137     GCRY_MD_SHA3_256, {0, 1},
1138     "SHA3-256", sha3_256_asn, DIM (sha3_256_asn), oid_spec_sha3_256, 32,
1139     sha3_256_init, keccak_write, keccak_final, keccak_read, NULL,
1140     sizeof (KECCAK_CONTEXT),
1141     run_selftests
1142   };
1143 gcry_md_spec_t _gcry_digest_spec_sha3_384 =
1144   {
1145     GCRY_MD_SHA3_384, {0, 1},
1146     "SHA3-384", sha3_384_asn, DIM (sha3_384_asn), oid_spec_sha3_384, 48,
1147     sha3_384_init, keccak_write, keccak_final, keccak_read, NULL,
1148     sizeof (KECCAK_CONTEXT),
1149     run_selftests
1150   };
1151 gcry_md_spec_t _gcry_digest_spec_sha3_512 =
1152   {
1153     GCRY_MD_SHA3_512, {0, 1},
1154     "SHA3-512", sha3_512_asn, DIM (sha3_512_asn), oid_spec_sha3_512, 64,
1155     sha3_512_init, keccak_write, keccak_final, keccak_read, NULL,
1156     sizeof (KECCAK_CONTEXT),
1157     run_selftests
1158   };
1159 gcry_md_spec_t _gcry_digest_spec_shake128 =
1160   {
1161     GCRY_MD_SHAKE128, {0, 1},
1162     "SHAKE128", shake128_asn, DIM (shake128_asn), oid_spec_shake128, 0,
1163     shake128_init, keccak_write, keccak_final, NULL, keccak_extract,
1164     sizeof (KECCAK_CONTEXT),
1165     run_selftests
1166   };
1167 gcry_md_spec_t _gcry_digest_spec_shake256 =
1168   {
1169     GCRY_MD_SHAKE256, {0, 1},
1170     "SHAKE256", shake256_asn, DIM (shake256_asn), oid_spec_shake256, 0,
1171     shake256_init, keccak_write, keccak_final, NULL, keccak_extract,
1172     sizeof (KECCAK_CONTEXT),
1173     run_selftests
1174   };