1/*-
2 * Copyright (c) 2001, 2002 Allan Saddi <allan@saddi.com>
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 *    notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 *    notice, this list of conditions and the following disclaimer in the
12 *    documentation and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
15 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
18 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
20 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
21 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
22 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
23 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
24 * SUCH DAMAGE.
25 *
26 *	$Id: sha256.c,v 1.3 2007/03/25 11:33:41 patthoyts Exp $
27 */
28
29/*
30 * Define WORDS_BIGENDIAN if compiling on a big-endian architecture.
31 *
32 * Define SHA256_TEST to test the implementation using the NIST's
33 * sample messages. The output should be:
34 *
35 *   ba7816bf 8f01cfea 414140de 5dae2223 b00361a3 96177a9c b410ff61 f20015ad
36 *   248d6a61 d20638b8 e5c02693 0c3e6039 a33ce459 64ff2167 f6ecedd4 19db06c1
37 *   cdc76e5c 9914fb92 81a1c7e2 84d73e67 f1809a48 a497200e 046d39cc c7112cd0
38 */
39
40#ifdef HAVE_CONFIG_H
41#include <config.h>
42#endif /* HAVE_CONFIG_H */
43
44#if HAVE_INTTYPES_H
45# include <inttypes.h>
46#else
47# if HAVE_STDINT_H
48#  include <stdint.h>
49# endif
50#endif
51
52#include <string.h>
53#include <stdlib.h>
54
55#include "sha256.h"
56
57#ifndef lint
58static const char rcsid[] =
59	"$Id: sha256.c,v 1.3 2007/03/25 11:33:41 patthoyts Exp $";
60#endif /* !lint */
61
62#if TCL_BYTE_ORDER==1234
63#else
64#define WORDS_BIGENDIAN
65#endif
66
67
68#define ROTL(x, n) (((x) << (n)) | ((x) >> (32 - (n))))
69#define ROTR(x, n) (((x) >> (n)) | ((x) << (32 - (n))))
70
71#define Ch(x, y, z) ((z) ^ ((x) & ((y) ^ (z))))
72#define Maj(x, y, z) (((x) & ((y) | (z))) | ((y) & (z)))
73#define SIGMA0(x) (ROTR((x), 2) ^ ROTR((x), 13) ^ ROTR((x), 22))
74#define SIGMA1(x) (ROTR((x), 6) ^ ROTR((x), 11) ^ ROTR((x), 25))
75#define sigma0(x) (ROTR((x), 7) ^ ROTR((x), 18) ^ ((x) >> 3))
76#define sigma1(x) (ROTR((x), 17) ^ ROTR((x), 19) ^ ((x) >> 10))
77
78#define DO_ROUND() { \
79  t1 = h + SIGMA1(e) + Ch(e, f, g) + *(Kp++) + *(W++); \
80  t2 = SIGMA0(a) + Maj(a, b, c); \
81  h = g; \
82  g = f; \
83  f = e; \
84  e = d + t1; \
85  d = c; \
86  c = b; \
87  b = a; \
88  a = t1 + t2; \
89}
90
91static const uint32_t K[64] = {
92  0x428a2f98L, 0x71374491L, 0xb5c0fbcfL, 0xe9b5dba5L,
93  0x3956c25bL, 0x59f111f1L, 0x923f82a4L, 0xab1c5ed5L,
94  0xd807aa98L, 0x12835b01L, 0x243185beL, 0x550c7dc3L,
95  0x72be5d74L, 0x80deb1feL, 0x9bdc06a7L, 0xc19bf174L,
96  0xe49b69c1L, 0xefbe4786L, 0x0fc19dc6L, 0x240ca1ccL,
97  0x2de92c6fL, 0x4a7484aaL, 0x5cb0a9dcL, 0x76f988daL,
98  0x983e5152L, 0xa831c66dL, 0xb00327c8L, 0xbf597fc7L,
99  0xc6e00bf3L, 0xd5a79147L, 0x06ca6351L, 0x14292967L,
100  0x27b70a85L, 0x2e1b2138L, 0x4d2c6dfcL, 0x53380d13L,
101  0x650a7354L, 0x766a0abbL, 0x81c2c92eL, 0x92722c85L,
102  0xa2bfe8a1L, 0xa81a664bL, 0xc24b8b70L, 0xc76c51a3L,
103  0xd192e819L, 0xd6990624L, 0xf40e3585L, 0x106aa070L,
104  0x19a4c116L, 0x1e376c08L, 0x2748774cL, 0x34b0bcb5L,
105  0x391c0cb3L, 0x4ed8aa4aL, 0x5b9cca4fL, 0x682e6ff3L,
106  0x748f82eeL, 0x78a5636fL, 0x84c87814L, 0x8cc70208L,
107  0x90befffaL, 0xa4506cebL, 0xbef9a3f7L, 0xc67178f2L
108};
109
110#ifndef RUNTIME_ENDIAN
111#ifdef WORDS_BIGENDIAN
112
113#define BYTESWAP(x) (x)
114#define BYTESWAP64(x) (x)
115
116#else /* !WORDS_BIGENDIAN */
117
118#define BYTESWAP(x) ((ROTR((x), 8) & 0xff00ff00L) | \
119		     (ROTL((x), 8) & 0x00ff00ffL))
120
121#define BYTESWAP64(x) _byteswap64(x)
122
123static
124#ifndef _MSC_VER
125 inline
126#endif
127uint64_t _byteswap64(uint64_t x)
128{
129  uint32_t a = x >> 32;
130  uint32_t b = (uint32_t) x;
131  return ((uint64_t) BYTESWAP(b) << 32) | (uint64_t) BYTESWAP(a);
132}
133
134#endif /* WORDS_BIGENDIAN */
135#else /* !RUNTIME_ENDIAN */
136
137static int littleEndian;
138
139#define BYTESWAP(x) _byteswap(x)
140#define BYTESWAP64(x) _byteswap64(x)
141
142#define _BYTESWAP(x) ((ROTR((x), 8) & 0xff00ff00L) | \
143		      (ROTL((x), 8) & 0x00ff00ffL))
144#define _BYTESWAP64(x) __byteswap64(x)
145
146static inline uint64_t __byteswap64(uint64_t x)
147{
148  uint32_t a = x >> 32;
149  uint32_t b = (uint32_t) x;
150  return ((uint64_t) _BYTESWAP(b) << 32) | (uint64_t) _BYTESWAP(a);
151}
152
153static inline uint32_t _byteswap(uint32_t x)
154{
155  if (!littleEndian)
156    return x;
157  else
158    return _BYTESWAP(x);
159}
160
161static inline uint64_t _byteswap64(uint64_t x)
162{
163  if (!littleEndian)
164    return x;
165  else
166    return _BYTESWAP64(x);
167}
168
169static inline void setEndian(void)
170{
171  union {
172    uint32_t w;
173    uint8_t b[4];
174  } endian;
175
176  endian.w = 1L;
177  littleEndian = endian.b[0] != 0;
178}
179
180#endif /* !RUNTIME_ENDIAN */
181
182static const uint8_t padding[64] = {
183  0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
184  0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
185  0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
186  0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
187  0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
188  0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
189  0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
190  0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00
191};
192
193void
194SHA256Init (SHA256Context *sc)
195{
196#ifdef RUNTIME_ENDIAN
197  setEndian ();
198#endif /* RUNTIME_ENDIAN */
199
200  sc->totalLength = 0;
201  sc->hash[0] = 0x6a09e667;
202  sc->hash[1] = 0xbb67ae85;
203  sc->hash[2] = 0x3c6ef372;
204  sc->hash[3] = 0xa54ff53a;
205  sc->hash[4] = 0x510e527f;
206  sc->hash[5] = 0x9b05688c;
207  sc->hash[6] = 0x1f83d9ab;
208  sc->hash[7] = 0x5be0cd19;
209  sc->bufferLength = 0;
210}
211
212void
213SHA224Init (SHA256Context *sc)
214{
215#ifdef RUNTIME_ENDIAN
216  setEndian ();
217#endif /* RUNTIME_ENDIAN */
218
219  sc->totalLength = 0;
220  sc->hash[0] = 0xc1059ed8;
221  sc->hash[1] = 0x367cd507;
222  sc->hash[2] = 0x3070dd17;
223  sc->hash[3] = 0xf70e5939;
224  sc->hash[4] = 0xffc00b31;
225  sc->hash[5] = 0x68581511;
226  sc->hash[6] = 0x64f98fa7;
227  sc->hash[7] = 0xbefa4fa4;
228  sc->bufferLength = 0;
229}
230
231static void
232burnStack (int size)
233{
234  char buf[128];
235
236  memset (buf, 0, sizeof (buf));
237  size -= sizeof (buf);
238  if (size > 0)
239    burnStack (size);
240}
241
242static void
243SHA256Guts (SHA256Context *sc, const uint32_t *cbuf)
244{
245  uint32_t buf[64];
246  uint32_t *W, *W2, *W7, *W15, *W16;
247  uint32_t a, b, c, d, e, f, g, h;
248  uint32_t t1, t2;
249  const uint32_t *Kp;
250  int i;
251
252  W = buf;
253
254  for (i = 15; i >= 0; i--) {
255    *(W++) = BYTESWAP(*cbuf);
256    cbuf++;
257  }
258
259  W16 = &buf[0];
260  W15 = &buf[1];
261  W7 = &buf[9];
262  W2 = &buf[14];
263
264  for (i = 47; i >= 0; i--) {
265    *(W++) = sigma1(*W2) + *(W7++) + sigma0(*W15) + *(W16++);
266    W2++;
267    W15++;
268  }
269
270  a = sc->hash[0];
271  b = sc->hash[1];
272  c = sc->hash[2];
273  d = sc->hash[3];
274  e = sc->hash[4];
275  f = sc->hash[5];
276  g = sc->hash[6];
277  h = sc->hash[7];
278
279  Kp = K;
280  W = buf;
281
282#ifndef SHA256_UNROLL
283#define SHA256_UNROLL 1
284#endif /* !SHA256_UNROLL */
285
286#if SHA256_UNROLL == 1
287  for (i = 63; i >= 0; i--)
288    DO_ROUND();
289#elif SHA256_UNROLL == 2
290  for (i = 31; i >= 0; i--) {
291    DO_ROUND(); DO_ROUND();
292  }
293#elif SHA256_UNROLL == 4
294  for (i = 15; i >= 0; i--) {
295    DO_ROUND(); DO_ROUND(); DO_ROUND(); DO_ROUND();
296  }
297#elif SHA256_UNROLL == 8
298  for (i = 7; i >= 0; i--) {
299    DO_ROUND(); DO_ROUND(); DO_ROUND(); DO_ROUND();
300    DO_ROUND(); DO_ROUND(); DO_ROUND(); DO_ROUND();
301  }
302#elif SHA256_UNROLL == 16
303  for (i = 3; i >= 0; i--) {
304    DO_ROUND(); DO_ROUND(); DO_ROUND(); DO_ROUND();
305    DO_ROUND(); DO_ROUND(); DO_ROUND(); DO_ROUND();
306    DO_ROUND(); DO_ROUND(); DO_ROUND(); DO_ROUND();
307    DO_ROUND(); DO_ROUND(); DO_ROUND(); DO_ROUND();
308  }
309#elif SHA256_UNROLL == 32
310  for (i = 1; i >= 0; i--) {
311    DO_ROUND(); DO_ROUND(); DO_ROUND(); DO_ROUND();
312    DO_ROUND(); DO_ROUND(); DO_ROUND(); DO_ROUND();
313    DO_ROUND(); DO_ROUND(); DO_ROUND(); DO_ROUND();
314    DO_ROUND(); DO_ROUND(); DO_ROUND(); DO_ROUND();
315    DO_ROUND(); DO_ROUND(); DO_ROUND(); DO_ROUND();
316    DO_ROUND(); DO_ROUND(); DO_ROUND(); DO_ROUND();
317    DO_ROUND(); DO_ROUND(); DO_ROUND(); DO_ROUND();
318    DO_ROUND(); DO_ROUND(); DO_ROUND(); DO_ROUND();
319  }
320#elif SHA256_UNROLL == 64
321  DO_ROUND(); DO_ROUND(); DO_ROUND(); DO_ROUND();
322  DO_ROUND(); DO_ROUND(); DO_ROUND(); DO_ROUND();
323  DO_ROUND(); DO_ROUND(); DO_ROUND(); DO_ROUND();
324  DO_ROUND(); DO_ROUND(); DO_ROUND(); DO_ROUND();
325  DO_ROUND(); DO_ROUND(); DO_ROUND(); DO_ROUND();
326  DO_ROUND(); DO_ROUND(); DO_ROUND(); DO_ROUND();
327  DO_ROUND(); DO_ROUND(); DO_ROUND(); DO_ROUND();
328  DO_ROUND(); DO_ROUND(); DO_ROUND(); DO_ROUND();
329  DO_ROUND(); DO_ROUND(); DO_ROUND(); DO_ROUND();
330  DO_ROUND(); DO_ROUND(); DO_ROUND(); DO_ROUND();
331  DO_ROUND(); DO_ROUND(); DO_ROUND(); DO_ROUND();
332  DO_ROUND(); DO_ROUND(); DO_ROUND(); DO_ROUND();
333  DO_ROUND(); DO_ROUND(); DO_ROUND(); DO_ROUND();
334  DO_ROUND(); DO_ROUND(); DO_ROUND(); DO_ROUND();
335  DO_ROUND(); DO_ROUND(); DO_ROUND(); DO_ROUND();
336  DO_ROUND(); DO_ROUND(); DO_ROUND(); DO_ROUND();
337#else
338#error "SHA256_UNROLL must be 1, 2, 4, 8, 16, 32, or 64!"
339#endif
340
341  sc->hash[0] += a;
342  sc->hash[1] += b;
343  sc->hash[2] += c;
344  sc->hash[3] += d;
345  sc->hash[4] += e;
346  sc->hash[5] += f;
347  sc->hash[6] += g;
348  sc->hash[7] += h;
349}
350
351void
352SHA256Update (SHA256Context *sc, const void *data, uint32_t len)
353{
354  uint32_t bufferBytesLeft;
355  uint32_t bytesToCopy;
356  int needBurn = 0;
357
358  /* gcc 4 complains that the following construction has an invalid lvalue:
359   *   ((uint8_t *) data) += bytesToCopy;
360   * apparently they have decided that assigment to cast values is a bad idea
361   * so we have to do the cast now as a work around -- assholes.
362   */
363  uint8_t *dataPtr = (uint8_t *)data;
364
365#ifdef SHA256_FAST_COPY
366  if (sc->bufferLength) {
367    bufferBytesLeft = 64L - sc->bufferLength;
368
369    bytesToCopy = bufferBytesLeft;
370    if (bytesToCopy > len)
371      bytesToCopy = len;
372
373    memcpy (&sc->buffer.bytes[sc->bufferLength], dataPtr, bytesToCopy);
374
375    sc->totalLength += bytesToCopy * 8L;
376
377    sc->bufferLength += bytesToCopy;
378    dataPtr += bytesToCopy;
379    len -= bytesToCopy;
380
381    if (sc->bufferLength == 64L) {
382      SHA256Guts (sc, sc->buffer.words);
383      needBurn = 1;
384      sc->bufferLength = 0L;
385    }
386  }
387
388  while (len > 63L) {
389    sc->totalLength += 512L;
390
391    SHA256Guts (sc, dataPtr);
392    needBurn = 1;
393
394    dataPtr += 64L;
395    len -= 64L;
396  }
397
398  if (len) {
399    memcpy (&sc->buffer.bytes[sc->bufferLength], dataPtr, len);
400
401    sc->totalLength += len * 8L;
402
403    sc->bufferLength += len;
404  }
405#else /* SHA256_FAST_COPY */
406  while (len) {
407    bufferBytesLeft = 64L - sc->bufferLength;
408
409    bytesToCopy = bufferBytesLeft;
410    if (bytesToCopy > len)
411      bytesToCopy = len;
412
413    memcpy (&sc->buffer.bytes[sc->bufferLength], dataPtr, bytesToCopy);
414
415    sc->totalLength += bytesToCopy * 8L;
416
417    sc->bufferLength += bytesToCopy;
418
419    dataPtr += bytesToCopy;
420    len -= bytesToCopy;
421
422    if (sc->bufferLength == 64L) {
423      SHA256Guts (sc, sc->buffer.words);
424      needBurn = 1;
425      sc->bufferLength = 0L;
426    }
427  }
428#endif /* SHA256_FAST_COPY */
429
430  if (needBurn)
431    burnStack (sizeof (uint32_t[74]) + sizeof (uint32_t *[6]) + sizeof (int));
432}
433
434void
435SHA256Final (
436SHA256Context *sc, uint8_t hash[SHA256_HASH_SIZE])
437{
438  uint32_t bytesToPad;
439  uint64_t lengthPad;
440  int i;
441
442  bytesToPad = 120L - sc->bufferLength;
443  if (bytesToPad > 64L)
444    bytesToPad -= 64L;
445
446  lengthPad = BYTESWAP64(sc->totalLength);
447
448  SHA256Update (sc, padding, bytesToPad);
449  SHA256Update (sc, &lengthPad, 8L);
450
451  if (hash) {
452    for (i = 0; i < SHA256_HASH_WORDS; i++) {
453#ifdef SHA256_FAST_COPY
454      *((uint32_t *) hash) = BYTESWAP(sc->hash[i]);
455#else /* SHA256_FAST_COPY */
456      hash[0] = (uint8_t) (sc->hash[i] >> 24);
457      hash[1] = (uint8_t) (sc->hash[i] >> 16);
458      hash[2] = (uint8_t) (sc->hash[i] >> 8);
459      hash[3] = (uint8_t) sc->hash[i];
460#endif /* SHA256_FAST_COPY */
461      hash += 4;
462    }
463  }
464}
465
466#ifdef SHA256_TEST
467
468#include <stdio.h>
469#include <stdlib.h>
470#include <string.h>
471
472int
473main (int argc, char *argv[])
474{
475  SHA256Context foo;
476  uint8_t hash[SHA256_HASH_SIZE];
477  char buf[1000];
478  int i;
479
480  SHA256Init (&foo);
481  SHA256Update (&foo, "abc", 3);
482  SHA256Final (&foo, hash);
483
484  for (i = 0; i < SHA256_HASH_SIZE;) {
485    printf ("%02x", hash[i++]);
486    if (!(i % 4))
487      printf (" ");
488  }
489  printf ("\n");
490
491  SHA256Init (&foo);
492  SHA256Update (&foo,
493		"abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq",
494		56);
495  SHA256Final (&foo, hash);
496
497  for (i = 0; i < SHA256_HASH_SIZE;) {
498    printf ("%02x", hash[i++]);
499    if (!(i % 4))
500      printf (" ");
501  }
502  printf ("\n");
503
504  SHA256Init (&foo);
505  memset (buf, 'a', sizeof (buf));
506  for (i = 0; i < 1000; i++)
507    SHA256Update (&foo, buf, sizeof (buf));
508  SHA256Final (&foo, hash);
509
510  for (i = 0; i < SHA256_HASH_SIZE;) {
511    printf ("%02x", hash[i++]);
512    if (!(i % 4))
513      printf (" ");
514  }
515  printf ("\n");
516
517  exit (0);
518}
519
520#endif /* SHA256_TEST */
521