Add Poly1305 MAC
[libgcrypt.git] / cipher / sha256.c
1 /* sha256.c - SHA256 hash function
2  * Copyright (C) 2003, 2006, 2008, 2009 Free Software Foundation, Inc.
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 /*  Test vectors:
22
23     "abc"
24     SHA224: 23097d22 3405d822 8642a477 bda255b3 2aadbce4 bda0b3f7 e36c9da7
25     SHA256: ba7816bf 8f01cfea 414140de 5dae2223 b00361a3 96177a9c b410ff61 f20015ad
26
27     "abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq"
28     SHA224: 75388b16 512776cc 5dba5da1 fd890150 b0c6455c b4f58b19 52522525
29     SHA256: 248d6a61 d20638b8 e5c02693 0c3e6039 a33ce459 64ff2167 f6ecedd4 19db06c1
30
31     "a" one million times
32     SHA224: 20794655 980c91d8 bbb4c1ea 97618a4b f03f4258 1948b2ee 4ee7ad67
33     SHA256: cdc76e5c 9914fb92 81a1c7e2 84d73e67 f1809a48 a497200e 046d39cc c7112cd0
34
35  */
36
37
38 #include <config.h>
39 #include <stdio.h>
40 #include <stdlib.h>
41 #include <string.h>
42
43 #include "g10lib.h"
44 #include "bithelp.h"
45 #include "bufhelp.h"
46 #include "cipher.h"
47 #include "hash-common.h"
48
49
50 /* USE_SSSE3 indicates whether to compile with Intel SSSE3 code. */
51 #undef USE_SSSE3
52 #if defined(__x86_64__) && defined(HAVE_COMPATIBLE_GCC_AMD64_PLATFORM_AS) && \
53     defined(HAVE_GCC_INLINE_ASM_SSSE3) && \
54     defined(HAVE_INTEL_SYNTAX_PLATFORM_AS)
55 # define USE_SSSE3 1
56 #endif
57
58 /* USE_AVX indicates whether to compile with Intel AVX code. */
59 #undef USE_AVX
60 #if defined(__x86_64__) && defined(HAVE_COMPATIBLE_GCC_AMD64_PLATFORM_AS) && \
61     defined(HAVE_GCC_INLINE_ASM_AVX) && \
62     defined(HAVE_INTEL_SYNTAX_PLATFORM_AS)
63 # define USE_AVX 1
64 #endif
65
66 /* USE_AVX2 indicates whether to compile with Intel AVX2/BMI2 code. */
67 #undef USE_AVX2
68 #if defined(__x86_64__) && defined(HAVE_COMPATIBLE_GCC_AMD64_PLATFORM_AS) && \
69     defined(HAVE_GCC_INLINE_ASM_AVX2) && defined(HAVE_GCC_INLINE_ASM_BMI2) && \
70     defined(HAVE_INTEL_SYNTAX_PLATFORM_AS)
71 # define USE_AVX2 1
72 #endif
73
74
75 typedef struct {
76   gcry_md_block_ctx_t bctx;
77   u32  h0,h1,h2,h3,h4,h5,h6,h7;
78 #ifdef USE_SSSE3
79   unsigned int use_ssse3:1;
80 #endif
81 #ifdef USE_AVX
82   unsigned int use_avx:1;
83 #endif
84 #ifdef USE_AVX2
85   unsigned int use_avx2:1;
86 #endif
87 } SHA256_CONTEXT;
88
89
90 static unsigned int
91 transform (void *c, const unsigned char *data, size_t nblks);
92
93
94 static void
95 sha256_init (void *context, unsigned int flags)
96 {
97   SHA256_CONTEXT *hd = context;
98   unsigned int features = _gcry_get_hw_features ();
99
100   (void)flags;
101
102   hd->h0 = 0x6a09e667;
103   hd->h1 = 0xbb67ae85;
104   hd->h2 = 0x3c6ef372;
105   hd->h3 = 0xa54ff53a;
106   hd->h4 = 0x510e527f;
107   hd->h5 = 0x9b05688c;
108   hd->h6 = 0x1f83d9ab;
109   hd->h7 = 0x5be0cd19;
110
111   hd->bctx.nblocks = 0;
112   hd->bctx.nblocks_high = 0;
113   hd->bctx.count = 0;
114   hd->bctx.blocksize = 64;
115   hd->bctx.bwrite = transform;
116
117 #ifdef USE_SSSE3
118   hd->use_ssse3 = (features & HWF_INTEL_SSSE3) != 0;
119 #endif
120 #ifdef USE_AVX
121   /* AVX implementation uses SHLD which is known to be slow on non-Intel CPUs.
122    * Therefore use this implementation on Intel CPUs only. */
123   hd->use_avx = (features & HWF_INTEL_AVX) && (features & HWF_INTEL_CPU);
124 #endif
125 #ifdef USE_AVX2
126   hd->use_avx2 = (features & HWF_INTEL_AVX2) && (features & HWF_INTEL_BMI2);
127 #endif
128   (void)features;
129 }
130
131
132 static void
133 sha224_init (void *context, unsigned int flags)
134 {
135   SHA256_CONTEXT *hd = context;
136   unsigned int features = _gcry_get_hw_features ();
137
138   (void)flags;
139
140   hd->h0 = 0xc1059ed8;
141   hd->h1 = 0x367cd507;
142   hd->h2 = 0x3070dd17;
143   hd->h3 = 0xf70e5939;
144   hd->h4 = 0xffc00b31;
145   hd->h5 = 0x68581511;
146   hd->h6 = 0x64f98fa7;
147   hd->h7 = 0xbefa4fa4;
148
149   hd->bctx.nblocks = 0;
150   hd->bctx.nblocks_high = 0;
151   hd->bctx.count = 0;
152   hd->bctx.blocksize = 64;
153   hd->bctx.bwrite = transform;
154
155 #ifdef USE_SSSE3
156   hd->use_ssse3 = (features & HWF_INTEL_SSSE3) != 0;
157 #endif
158 #ifdef USE_AVX
159   /* AVX implementation uses SHLD which is known to be slow on non-Intel CPUs.
160    * Therefore use this implementation on Intel CPUs only. */
161   hd->use_avx = (features & HWF_INTEL_AVX) && (features & HWF_INTEL_CPU);
162 #endif
163 #ifdef USE_AVX2
164   hd->use_avx2 = (features & HWF_INTEL_AVX2) && (features & HWF_INTEL_BMI2);
165 #endif
166   (void)features;
167 }
168
169
170 /*
171   Transform the message X which consists of 16 32-bit-words. See FIPS
172   180-2 for details.  */
173 #define S0(x) (ror ((x), 7) ^ ror ((x), 18) ^ ((x) >> 3))       /* (4.6) */
174 #define S1(x) (ror ((x), 17) ^ ror ((x), 19) ^ ((x) >> 10))     /* (4.7) */
175 #define R(a,b,c,d,e,f,g,h,k,w) do                                 \
176           {                                                       \
177             t1 = (h) + Sum1((e)) + Cho((e),(f),(g)) + (k) + (w);  \
178             t2 = Sum0((a)) + Maj((a),(b),(c));                    \
179             h = g;                                                \
180             g = f;                                                \
181             f = e;                                                \
182             e = d + t1;                                           \
183             d = c;                                                \
184             c = b;                                                \
185             b = a;                                                \
186             a = t1 + t2;                                          \
187           } while (0)
188
189 /* (4.2) same as SHA-1's F1.  */
190 static inline u32
191 Cho (u32 x, u32 y, u32 z)
192 {
193   return (z ^ (x & (y ^ z)));
194 }
195
196 /* (4.3) same as SHA-1's F3 */
197 static inline u32
198 Maj (u32 x, u32 y, u32 z)
199 {
200   return ((x & y) | (z & (x|y)));
201 }
202
203 /* (4.4) */
204 static inline u32
205 Sum0 (u32 x)
206 {
207   return (ror (x, 2) ^ ror (x, 13) ^ ror (x, 22));
208 }
209
210 /* (4.5) */
211 static inline u32
212 Sum1 (u32 x)
213 {
214   return (ror (x, 6) ^ ror (x, 11) ^ ror (x, 25));
215 }
216
217
218 static unsigned int
219 transform_blk (void *ctx, const unsigned char *data)
220 {
221   SHA256_CONTEXT *hd = ctx;
222   static const u32 K[64] = {
223     0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5,
224     0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
225     0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3,
226     0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
227     0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc,
228     0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
229     0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7,
230     0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
231     0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13,
232     0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
233     0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3,
234     0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
235     0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5,
236     0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
237     0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208,
238     0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2
239   };
240
241   u32 a,b,c,d,e,f,g,h,t1,t2;
242   u32 w[64];
243   int i;
244
245   a = hd->h0;
246   b = hd->h1;
247   c = hd->h2;
248   d = hd->h3;
249   e = hd->h4;
250   f = hd->h5;
251   g = hd->h6;
252   h = hd->h7;
253
254   for (i=0; i < 16; i++)
255     w[i] = buf_get_be32(data + i * 4);
256   for (; i < 64; i++)
257     w[i] = S1(w[i-2]) + w[i-7] + S0(w[i-15]) + w[i-16];
258
259   for (i=0; i < 64;)
260     {
261 #if 0
262       R(a,b,c,d,e,f,g,h,K[i],w[i]);
263       i++;
264 #else
265       t1 = h + Sum1 (e) + Cho (e, f, g) + K[i] + w[i];
266       t2 = Sum0 (a) + Maj (a, b, c);
267       d += t1;
268       h  = t1 + t2;
269
270       t1 = g + Sum1 (d) + Cho (d, e, f) + K[i+1] + w[i+1];
271       t2 = Sum0 (h) + Maj (h, a, b);
272       c += t1;
273       g  = t1 + t2;
274
275       t1 = f + Sum1 (c) + Cho (c, d, e) + K[i+2] + w[i+2];
276       t2 = Sum0 (g) + Maj (g, h, a);
277       b += t1;
278       f  = t1 + t2;
279
280       t1 = e + Sum1 (b) + Cho (b, c, d) + K[i+3] + w[i+3];
281       t2 = Sum0 (f) + Maj (f, g, h);
282       a += t1;
283       e  = t1 + t2;
284
285       t1 = d + Sum1 (a) + Cho (a, b, c) + K[i+4] + w[i+4];
286       t2 = Sum0 (e) + Maj (e, f, g);
287       h += t1;
288       d  = t1 + t2;
289
290       t1 = c + Sum1 (h) + Cho (h, a, b) + K[i+5] + w[i+5];
291       t2 = Sum0 (d) + Maj (d, e, f);
292       g += t1;
293       c  = t1 + t2;
294
295       t1 = b + Sum1 (g) + Cho (g, h, a) + K[i+6] + w[i+6];
296       t2 = Sum0 (c) + Maj (c, d, e);
297       f += t1;
298       b  = t1 + t2;
299
300       t1 = a + Sum1 (f) + Cho (f, g, h) + K[i+7] + w[i+7];
301       t2 = Sum0 (b) + Maj (b, c, d);
302       e += t1;
303       a  = t1 + t2;
304
305       i += 8;
306 #endif
307     }
308
309   hd->h0 += a;
310   hd->h1 += b;
311   hd->h2 += c;
312   hd->h3 += d;
313   hd->h4 += e;
314   hd->h5 += f;
315   hd->h6 += g;
316   hd->h7 += h;
317
318   return /*burn_stack*/ 74*4+32;
319 }
320 #undef S0
321 #undef S1
322 #undef R
323
324
325 #ifdef USE_SSSE3
326 unsigned int _gcry_sha256_transform_amd64_ssse3(const void *input_data,
327                                                 u32 state[8], size_t num_blks);
328 #endif
329
330 #ifdef USE_AVX
331 unsigned int _gcry_sha256_transform_amd64_avx(const void *input_data,
332                                               u32 state[8], size_t num_blks);
333 #endif
334
335 #ifdef USE_AVX2
336 unsigned int _gcry_sha256_transform_amd64_avx2(const void *input_data,
337                                                u32 state[8], size_t num_blks);
338 #endif
339
340
341 static unsigned int
342 transform (void *ctx, const unsigned char *data, size_t nblks)
343 {
344   SHA256_CONTEXT *hd = ctx;
345   unsigned int burn;
346
347 #ifdef USE_AVX2
348   if (hd->use_avx2)
349     return _gcry_sha256_transform_amd64_avx2 (data, &hd->h0, nblks)
350            + 4 * sizeof(void*);
351 #endif
352
353 #ifdef USE_AVX
354   if (hd->use_avx)
355     return _gcry_sha256_transform_amd64_avx (data, &hd->h0, nblks)
356            + 4 * sizeof(void*);
357 #endif
358
359 #ifdef USE_SSSE3
360   if (hd->use_ssse3)
361     return _gcry_sha256_transform_amd64_ssse3 (data, &hd->h0, nblks)
362            + 4 * sizeof(void*);
363 #endif
364
365   do
366     {
367       burn = transform_blk (hd, data);
368       data += 64;
369     }
370   while (--nblks);
371
372   return burn;
373 }
374
375
376 /*
377    The routine finally terminates the computation and returns the
378    digest.  The handle is prepared for a new cycle, but adding bytes
379    to the handle will the destroy the returned buffer.  Returns: 32
380    bytes with the message the digest.  */
381 static void
382 sha256_final(void *context)
383 {
384   SHA256_CONTEXT *hd = context;
385   u32 t, th, msb, lsb;
386   byte *p;
387   unsigned int burn;
388
389   _gcry_md_block_write (hd, NULL, 0); /* flush */;
390
391   t = hd->bctx.nblocks;
392   if (sizeof t == sizeof hd->bctx.nblocks)
393     th = hd->bctx.nblocks_high;
394   else
395     th = hd->bctx.nblocks >> 32;
396
397   /* multiply by 64 to make a byte count */
398   lsb = t << 6;
399   msb = (th << 6) | (t >> 26);
400   /* add the count */
401   t = lsb;
402   if ((lsb += hd->bctx.count) < t)
403     msb++;
404   /* multiply by 8 to make a bit count */
405   t = lsb;
406   lsb <<= 3;
407   msb <<= 3;
408   msb |= t >> 29;
409
410   if (hd->bctx.count < 56)
411     { /* enough room */
412       hd->bctx.buf[hd->bctx.count++] = 0x80; /* pad */
413       while (hd->bctx.count < 56)
414         hd->bctx.buf[hd->bctx.count++] = 0;  /* pad */
415     }
416   else
417     { /* need one extra block */
418       hd->bctx.buf[hd->bctx.count++] = 0x80; /* pad character */
419       while (hd->bctx.count < 64)
420         hd->bctx.buf[hd->bctx.count++] = 0;
421       _gcry_md_block_write (hd, NULL, 0);  /* flush */;
422       memset (hd->bctx.buf, 0, 56 ); /* fill next block with zeroes */
423     }
424   /* append the 64 bit count */
425   buf_put_be32(hd->bctx.buf + 56, msb);
426   buf_put_be32(hd->bctx.buf + 60, lsb);
427   burn = transform (hd, hd->bctx.buf, 1);
428   _gcry_burn_stack (burn);
429
430   p = hd->bctx.buf;
431 #define X(a) do { *(u32*)p = be_bswap32(hd->h##a); p += 4; } while(0)
432   X(0);
433   X(1);
434   X(2);
435   X(3);
436   X(4);
437   X(5);
438   X(6);
439   X(7);
440 #undef X
441 }
442
443 static byte *
444 sha256_read (void *context)
445 {
446   SHA256_CONTEXT *hd = context;
447
448   return hd->bctx.buf;
449 }
450
451
452 \f
453 /*
454      Self-test section.
455  */
456
457
458 static gpg_err_code_t
459 selftests_sha224 (int extended, selftest_report_func_t report)
460 {
461   const char *what;
462   const char *errtxt;
463
464   what = "short string";
465   errtxt = _gcry_hash_selftest_check_one
466     (GCRY_MD_SHA224, 0,
467      "abc", 3,
468      "\x23\x09\x7d\x22\x34\x05\xd8\x22\x86\x42\xa4\x77\xbd\xa2\x55\xb3"
469      "\x2a\xad\xbc\xe4\xbd\xa0\xb3\xf7\xe3\x6c\x9d\xa7", 28);
470   if (errtxt)
471     goto failed;
472
473   if (extended)
474     {
475       what = "long string";
476       errtxt = _gcry_hash_selftest_check_one
477         (GCRY_MD_SHA224, 0,
478          "abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq", 56,
479          "\x75\x38\x8b\x16\x51\x27\x76\xcc\x5d\xba\x5d\xa1\xfd\x89\x01\x50"
480          "\xb0\xc6\x45\x5c\xb4\xf5\x8b\x19\x52\x52\x25\x25", 28);
481       if (errtxt)
482         goto failed;
483
484       what = "one million \"a\"";
485       errtxt = _gcry_hash_selftest_check_one
486         (GCRY_MD_SHA224, 1,
487          NULL, 0,
488          "\x20\x79\x46\x55\x98\x0c\x91\xd8\xbb\xb4\xc1\xea\x97\x61\x8a\x4b"
489          "\xf0\x3f\x42\x58\x19\x48\xb2\xee\x4e\xe7\xad\x67", 28);
490       if (errtxt)
491         goto failed;
492     }
493
494   return 0; /* Succeeded. */
495
496  failed:
497   if (report)
498     report ("digest", GCRY_MD_SHA224, what, errtxt);
499   return GPG_ERR_SELFTEST_FAILED;
500 }
501
502 static gpg_err_code_t
503 selftests_sha256 (int extended, selftest_report_func_t report)
504 {
505   const char *what;
506   const char *errtxt;
507
508   what = "short string";
509   errtxt = _gcry_hash_selftest_check_one
510     (GCRY_MD_SHA256, 0,
511      "abc", 3,
512      "\xba\x78\x16\xbf\x8f\x01\xcf\xea\x41\x41\x40\xde\x5d\xae\x22\x23"
513      "\xb0\x03\x61\xa3\x96\x17\x7a\x9c\xb4\x10\xff\x61\xf2\x00\x15\xad", 32);
514   if (errtxt)
515     goto failed;
516
517   if (extended)
518     {
519       what = "long string";
520       errtxt = _gcry_hash_selftest_check_one
521         (GCRY_MD_SHA256, 0,
522          "abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq", 56,
523          "\x24\x8d\x6a\x61\xd2\x06\x38\xb8\xe5\xc0\x26\x93\x0c\x3e\x60\x39"
524          "\xa3\x3c\xe4\x59\x64\xff\x21\x67\xf6\xec\xed\xd4\x19\xdb\x06\xc1",
525          32);
526       if (errtxt)
527         goto failed;
528
529       what = "one million \"a\"";
530       errtxt = _gcry_hash_selftest_check_one
531         (GCRY_MD_SHA256, 1,
532          NULL, 0,
533          "\xcd\xc7\x6e\x5c\x99\x14\xfb\x92\x81\xa1\xc7\xe2\x84\xd7\x3e\x67"
534          "\xf1\x80\x9a\x48\xa4\x97\x20\x0e\x04\x6d\x39\xcc\xc7\x11\x2c\xd0",
535          32);
536       if (errtxt)
537         goto failed;
538     }
539
540   return 0; /* Succeeded. */
541
542  failed:
543   if (report)
544     report ("digest", GCRY_MD_SHA256, what, errtxt);
545   return GPG_ERR_SELFTEST_FAILED;
546 }
547
548
549 /* Run a full self-test for ALGO and return 0 on success.  */
550 static gpg_err_code_t
551 run_selftests (int algo, int extended, selftest_report_func_t report)
552 {
553   gpg_err_code_t ec;
554
555   switch (algo)
556     {
557     case GCRY_MD_SHA224:
558       ec = selftests_sha224 (extended, report);
559       break;
560     case GCRY_MD_SHA256:
561       ec = selftests_sha256 (extended, report);
562       break;
563     default:
564       ec = GPG_ERR_DIGEST_ALGO;
565       break;
566
567     }
568   return ec;
569 }
570
571
572
573 \f
574 static byte asn224[19] = /* Object ID is 2.16.840.1.101.3.4.2.4 */
575   { 0x30, 0x2D, 0x30, 0x0d, 0x06, 0x09, 0x60, 0x86, 0x48,
576     0x01, 0x65, 0x03, 0x04, 0x02, 0x04, 0x05, 0x00, 0x04,
577     0x1C
578   };
579
580 static gcry_md_oid_spec_t oid_spec_sha224[] =
581   {
582     /* From RFC3874, Section 4 */
583     { "2.16.840.1.101.3.4.2.4" },
584     { NULL },
585   };
586
587 static byte asn256[19] = /* Object ID is  2.16.840.1.101.3.4.2.1 */
588   { 0x30, 0x31, 0x30, 0x0d, 0x06, 0x09, 0x60, 0x86,
589     0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x01, 0x05,
590     0x00, 0x04, 0x20 };
591
592 static gcry_md_oid_spec_t oid_spec_sha256[] =
593   {
594     /* According to the OpenPGP draft rfc2440-bis06 */
595     { "2.16.840.1.101.3.4.2.1" },
596     /* PKCS#1 sha256WithRSAEncryption */
597     { "1.2.840.113549.1.1.11" },
598
599     { NULL },
600   };
601
602 gcry_md_spec_t _gcry_digest_spec_sha224 =
603   {
604     GCRY_MD_SHA224, {0, 1},
605     "SHA224", asn224, DIM (asn224), oid_spec_sha224, 28,
606     sha224_init, _gcry_md_block_write, sha256_final, sha256_read,
607     sizeof (SHA256_CONTEXT),
608     run_selftests
609   };
610
611 gcry_md_spec_t _gcry_digest_spec_sha256 =
612   {
613     GCRY_MD_SHA256, {0, 1},
614     "SHA256", asn256, DIM (asn256), oid_spec_sha256, 32,
615     sha256_init, _gcry_md_block_write, sha256_final, sha256_read,
616     sizeof (SHA256_CONTEXT),
617     run_selftests
618   };