GNU libmicrohttpd  0.9.62
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros Groups
sha256.c
Go to the documentation of this file.
1 /* sha256.c
2 
3  The sha256 hash function.
4  See http://csrc.nist.gov/publications/fips/fips180-2/fips180-2.pdf
5 
6  Copyright (C) 2001 Niels Möller
7  Copyright (C) 2018 Christian Grothoff (extraction of minimal subset
8  from GNU Nettle to work with GNU libmicrohttpd)
9 
10  This file is part of GNU Nettle.
11 
12  GNU Nettle is free software: you can redistribute it and/or
13  modify it under the terms of either:
14 
15  * the GNU Lesser General Public License as published by the Free
16  Software Foundation; either version 3 of the License, or (at your
17  option) any later version.
18 
19  or
20 
21  * the GNU General Public License as published by the Free
22  Software Foundation; either version 2 of the License, or (at your
23  option) any later version.
24 
25  or both in parallel, as here.
26 
27  GNU Nettle is distributed in the hope that it will be useful,
28  but WITHOUT ANY WARRANTY; without even the implied warranty of
29  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
30  General Public License for more details.
31 
32  You should have received copies of the GNU General Public License and
33  the GNU Lesser General Public License along with this program. If
34  not, see http://www.gnu.org/licenses/.
35 */
36 
37 /* Modelled after the sha1.c code by Peter Gutmann. */
38 
39 #include <assert.h>
40 #include <stdlib.h>
41 #include <string.h>
42 #include <stdint.h>
43 
44 #include "sha256.h"
45 
46 
47 /* Generated by the shadata program. */
48 static const uint32_t
49 K[64] =
50 {
51  0x428a2f98UL, 0x71374491UL, 0xb5c0fbcfUL, 0xe9b5dba5UL,
52  0x3956c25bUL, 0x59f111f1UL, 0x923f82a4UL, 0xab1c5ed5UL,
53  0xd807aa98UL, 0x12835b01UL, 0x243185beUL, 0x550c7dc3UL,
54  0x72be5d74UL, 0x80deb1feUL, 0x9bdc06a7UL, 0xc19bf174UL,
55  0xe49b69c1UL, 0xefbe4786UL, 0x0fc19dc6UL, 0x240ca1ccUL,
56  0x2de92c6fUL, 0x4a7484aaUL, 0x5cb0a9dcUL, 0x76f988daUL,
57  0x983e5152UL, 0xa831c66dUL, 0xb00327c8UL, 0xbf597fc7UL,
58  0xc6e00bf3UL, 0xd5a79147UL, 0x06ca6351UL, 0x14292967UL,
59  0x27b70a85UL, 0x2e1b2138UL, 0x4d2c6dfcUL, 0x53380d13UL,
60  0x650a7354UL, 0x766a0abbUL, 0x81c2c92eUL, 0x92722c85UL,
61  0xa2bfe8a1UL, 0xa81a664bUL, 0xc24b8b70UL, 0xc76c51a3UL,
62  0xd192e819UL, 0xd6990624UL, 0xf40e3585UL, 0x106aa070UL,
63  0x19a4c116UL, 0x1e376c08UL, 0x2748774cUL, 0x34b0bcb5UL,
64  0x391c0cb3UL, 0x4ed8aa4aUL, 0x5b9cca4fUL, 0x682e6ff3UL,
65  0x748f82eeUL, 0x78a5636fUL, 0x84c87814UL, 0x8cc70208UL,
66  0x90befffaUL, 0xa4506cebUL, 0xbef9a3f7UL, 0xc67178f2UL,
67 };
68 
69 
70 /* A block, treated as a sequence of 32-bit words. */
71 #define SHA256_DATA_LENGTH 16
72 
73 /* The SHA256 functions. The Choice function is the same as the SHA1
74  function f1, and the majority function is the same as the SHA1 f3
75  function. They can be optimized to save one boolean operation each
76  - thanks to Rich Schroeppel, rcs@cs.arizona.edu for discovering
77  this */
78 
79 /* #define Choice(x,y,z) ( ( (x) & (y) ) | ( ~(x) & (z) ) ) */
80 #define Choice(x,y,z) ( (z) ^ ( (x) & ( (y) ^ (z) ) ) )
81 /* #define Majority(x,y,z) ( ((x) & (y)) ^ ((x) & (z)) ^ ((y) & (z)) ) */
82 #define Majority(x,y,z) ( ((x) & (y)) ^ ((z) & ((x) ^ (y))) )
83 
84 #define S0(x) (ROTL32(30,(x)) ^ ROTL32(19,(x)) ^ ROTL32(10,(x)))
85 #define S1(x) (ROTL32(26,(x)) ^ ROTL32(21,(x)) ^ ROTL32(7,(x)))
86 
87 #define s0(x) (ROTL32(25,(x)) ^ ROTL32(14,(x)) ^ ((x) >> 3))
88 #define s1(x) (ROTL32(15,(x)) ^ ROTL32(13,(x)) ^ ((x) >> 10))
89 
90 /* The initial expanding function. The hash function is defined over an
91  64-word expanded input array W, where the first 16 are copies of the input
92  data, and the remaining 64 are defined by
93 
94  W[ t ] = s1(W[t-2]) + W[t-7] + s0(W[i-15]) + W[i-16]
95 
96  This implementation generates these values on the fly in a circular
97  buffer - thanks to Colin Plumb, colin@nyx10.cs.du.edu for this
98  optimization.
99 */
100 
101 #define EXPAND(W,i) \
102 ( W[(i) & 15 ] += (s1(W[((i)-2) & 15]) + W[((i)-7) & 15] + s0(W[((i)-15) & 15])) )
103 
104 /* The prototype SHA sub-round. The fundamental sub-round is:
105 
106  T1 = h + S1(e) + Choice(e,f,g) + K[t] + W[t]
107  T2 = S0(a) + Majority(a,b,c)
108  a' = T1+T2
109  b' = a
110  c' = b
111  d' = c
112  e' = d + T1
113  f' = e
114  g' = f
115  h' = g
116 
117  but this is implemented by unrolling the loop 8 times and renaming
118  the variables
119  ( h, a, b, c, d, e, f, g ) = ( a, b, c, d, e, f, g, h ) each
120  iteration. */
121 
122 /* It's crucial that DATA is only used once, as that argument will
123  * have side effects. */
124 #define ROUND(a,b,c,d,e,f,g,h,k,data) do { \
125  h += S1(e) + Choice(e,f,g) + k + data; \
126  d += h; \
127  h += S0(a) + Majority(a,b,c); \
128  } while (0)
129 
130 
131 /* Reads a 32-bit integer, in network, big-endian, byte order */
132 #define READ_UINT32(p) \
133 ( (((uint32_t) (p)[0]) << 24) \
134  | (((uint32_t) (p)[1]) << 16) \
135  | (((uint32_t) (p)[2]) << 8) \
136  | ((uint32_t) (p)[3]))
137 
138 #define WRITE_UINT32(p, i) \
139 do { \
140  (p)[0] = ((i) >> 24) & 0xff; \
141  (p)[1] = ((i) >> 16) & 0xff; \
142  (p)[2] = ((i) >> 8) & 0xff; \
143  (p)[3] = (i) & 0xff; \
144 } while(0)
145 
146 #define WRITE_UINT64(p, i) \
147 do { \
148  (p)[0] = ((i) >> 56) & 0xff; \
149  (p)[1] = ((i) >> 48) & 0xff; \
150  (p)[2] = ((i) >> 40) & 0xff; \
151  (p)[3] = ((i) >> 32) & 0xff; \
152  (p)[4] = ((i) >> 24) & 0xff; \
153  (p)[5] = ((i) >> 16) & 0xff; \
154  (p)[6] = ((i) >> 8) & 0xff; \
155  (p)[7] = (i) & 0xff; \
156 } while(0)
157 
158 /* The masking of the right shift is needed to allow n == 0 (using
159  just 32 - n and 64 - n results in undefined behaviour). Most uses
160  of these macros use a constant and non-zero rotation count. */
161 #define ROTL32(n,x) (((x)<<(n)) | ((x)>>((-(n)&31))))
162 
163 static void
164 _nettle_sha256_compress(uint32_t *state, const uint8_t *input, const uint32_t *k)
165 {
166  uint32_t data[SHA256_DATA_LENGTH];
167  uint32_t A, B, C, D, E, F, G, H; /* Local vars */
168  unsigned i;
169  uint32_t *d;
170 
171  for (i = 0; i < SHA256_DATA_LENGTH; i++, input+= 4)
172  {
173  data[i] = READ_UINT32(input);
174  }
175 
176  /* Set up first buffer and local data buffer */
177  A = state[0];
178  B = state[1];
179  C = state[2];
180  D = state[3];
181  E = state[4];
182  F = state[5];
183  G = state[6];
184  H = state[7];
185 
186  /* Heavy mangling */
187  /* First 16 subrounds that act on the original data */
188 
189  for (i = 0, d = data; i<16; i+=8, k += 8, d+= 8)
190  {
191  ROUND(A, B, C, D, E, F, G, H, k[0], d[0]);
192  ROUND(H, A, B, C, D, E, F, G, k[1], d[1]);
193  ROUND(G, H, A, B, C, D, E, F, k[2], d[2]);
194  ROUND(F, G, H, A, B, C, D, E, k[3], d[3]);
195  ROUND(E, F, G, H, A, B, C, D, k[4], d[4]);
196  ROUND(D, E, F, G, H, A, B, C, k[5], d[5]);
197  ROUND(C, D, E, F, G, H, A, B, k[6], d[6]);
198  ROUND(B, C, D, E, F, G, H, A, k[7], d[7]);
199  }
200 
201  for (; i<64; i += 16, k+= 16)
202  {
203  ROUND(A, B, C, D, E, F, G, H, k[ 0], EXPAND(data, 0));
204  ROUND(H, A, B, C, D, E, F, G, k[ 1], EXPAND(data, 1));
205  ROUND(G, H, A, B, C, D, E, F, k[ 2], EXPAND(data, 2));
206  ROUND(F, G, H, A, B, C, D, E, k[ 3], EXPAND(data, 3));
207  ROUND(E, F, G, H, A, B, C, D, k[ 4], EXPAND(data, 4));
208  ROUND(D, E, F, G, H, A, B, C, k[ 5], EXPAND(data, 5));
209  ROUND(C, D, E, F, G, H, A, B, k[ 6], EXPAND(data, 6));
210  ROUND(B, C, D, E, F, G, H, A, k[ 7], EXPAND(data, 7));
211  ROUND(A, B, C, D, E, F, G, H, k[ 8], EXPAND(data, 8));
212  ROUND(H, A, B, C, D, E, F, G, k[ 9], EXPAND(data, 9));
213  ROUND(G, H, A, B, C, D, E, F, k[10], EXPAND(data, 10));
214  ROUND(F, G, H, A, B, C, D, E, k[11], EXPAND(data, 11));
215  ROUND(E, F, G, H, A, B, C, D, k[12], EXPAND(data, 12));
216  ROUND(D, E, F, G, H, A, B, C, k[13], EXPAND(data, 13));
217  ROUND(C, D, E, F, G, H, A, B, k[14], EXPAND(data, 14));
218  ROUND(B, C, D, E, F, G, H, A, k[15], EXPAND(data, 15));
219  }
220 
221  /* Update state */
222  state[0] += A;
223  state[1] += B;
224  state[2] += C;
225  state[3] += D;
226  state[4] += E;
227  state[5] += F;
228  state[6] += G;
229  state[7] += H;
230 }
231 
232 
233 #define COMPRESS(ctx, data) (_nettle_sha256_compress((ctx)->state, (data), K))
234 
235 /* Initialize the SHA values */
236 
237 void
238 sha256_init (void *ctx_)
239 {
240  /* Initial values, also generated by the shadata program. */
241  static const uint32_t H0[_SHA256_DIGEST_LENGTH] =
242  {
243  0x6a09e667UL, 0xbb67ae85UL, 0x3c6ef372UL, 0xa54ff53aUL,
244  0x510e527fUL, 0x9b05688cUL, 0x1f83d9abUL, 0x5be0cd19UL,
245  };
246  struct sha256_ctx *ctx = ctx_;
247 
248  memcpy(ctx->state, H0, sizeof(H0));
249 
250  /* Initialize bit count */
251  ctx->count = 0;
252 
253  /* Initialize buffer */
254  ctx->index = 0;
255 }
256 
257 
258 /* Takes the compression function f as argument. NOTE: also clobbers
259  length and data. */
260 #define MD_UPDATE(ctx, length, data, f, incr) \
261  do { \
262  if ((ctx)->index) \
263  { \
264  /* Try to fill partial block */ \
265  unsigned __md_left = sizeof((ctx)->block) - (ctx)->index; \
266  if ((length) < __md_left) \
267  { \
268  memcpy((ctx)->block + (ctx)->index, (data), (length)); \
269  (ctx)->index += (length); \
270  goto __md_done; /* Finished */ \
271  } \
272  else \
273  { \
274  memcpy((ctx)->block + (ctx)->index, (data), __md_left); \
275  \
276  f((ctx), (ctx)->block); \
277  (incr); \
278  \
279  (data) += __md_left; \
280  (length) -= __md_left; \
281  } \
282  } \
283  while ((length) >= sizeof((ctx)->block)) \
284  { \
285  f((ctx), (data)); \
286  (incr); \
287  \
288  (data) += sizeof((ctx)->block); \
289  (length) -= sizeof((ctx)->block); \
290  } \
291  memcpy ((ctx)->block, (data), (length)); \
292  (ctx)->index = (length); \
293  __md_done: \
294  ; \
295  } while (0)
296 
297 /* Pads the block to a block boundary with the bit pattern 1 0*,
298  leaving size octets for the length field at the end. If needed,
299  compresses the block and starts a new one. */
300 #define MD_PAD(ctx, size, f) \
301  do { \
302  unsigned __md_i; \
303  __md_i = (ctx)->index; \
304  \
305  /* Set the first char of padding to 0x80. This is safe since there \
306  is always at least one byte free */ \
307  \
308  assert(__md_i < sizeof((ctx)->block)); \
309  (ctx)->block[__md_i++] = 0x80; \
310  \
311  if (__md_i > (sizeof((ctx)->block) - (size))) \
312  { /* No room for length in this block. Process it and \
313  pad with another one */ \
314  memset((ctx)->block + __md_i, 0, sizeof((ctx)->block) - __md_i); \
315  \
316  f((ctx), (ctx)->block); \
317  __md_i = 0; \
318  } \
319  memset((ctx)->block + __md_i, 0, \
320  sizeof((ctx)->block) - (size) - __md_i); \
321  \
322  } while (0)
323 
324 
325 void
326 sha256_update (void *ctx_,
327  const uint8_t *data,
328  size_t length)
329 {
330  struct sha256_ctx *ctx = ctx_;
331  MD_UPDATE (ctx, length, data, COMPRESS, ctx->count++);
332 }
333 
334 
335 
336 void
337 _nettle_write_be32(size_t length, uint8_t *dst,
338  const uint32_t *src)
339 {
340  size_t i;
341  size_t words;
342  unsigned leftover;
343 
344  words = length / 4;
345  leftover = length % 4;
346 
347  for (i = 0; i < words; i++, dst += 4)
348  WRITE_UINT32(dst, src[i]);
349 
350  if (leftover)
351  {
352  uint32_t word;
353  unsigned j = leftover;
354 
355  word = src[i];
356 
357  switch (leftover)
358  {
359  default:
360  abort();
361  case 3:
362  dst[--j] = (word >> 8) & 0xff;
363  /* Fall through */
364  case 2:
365  dst[--j] = (word >> 16) & 0xff;
366  /* Fall through */
367  case 1:
368  dst[--j] = (word >> 24) & 0xff;
369  }
370  }
371 }
372 
373 
374 static void
376  size_t length,
377  uint8_t *digest)
378 {
379  uint64_t bit_count;
380 
381  assert(length <= SHA256_DIGEST_SIZE);
382 
383  MD_PAD(ctx, 8, COMPRESS);
384 
385  /* There are 512 = 2^9 bits in one block */
386  bit_count = (ctx->count << 9) | (ctx->index << 3);
387 
388  /* This is slightly inefficient, as the numbers are converted to
389  big-endian format, and will be converted back by the compression
390  function. It's probably not worth the effort to fix this. */
391  WRITE_UINT64(ctx->block + (SHA256_BLOCK_SIZE - 8), bit_count);
392  COMPRESS(ctx, ctx->block);
393 
394  _nettle_write_be32(length, digest, ctx->state);
395 }
396 
397 void
398 sha256_digest (void *ctx_,
399  uint8_t *digest)
400 {
401  struct sha256_ctx *ctx = ctx_;
402 
403  sha256_write_digest (ctx,
405  digest);
406  sha256_init (ctx);
407 }
static void sha256_write_digest(struct sha256_ctx *ctx, size_t length, uint8_t *digest)
Definition: sha256.c:375
void * data
Definition: microhttpd.h:2709
#define ROUND(a, b, c, d, e, f, g, h, k, data)
Definition: sha256.c:124
uint8_t block[SHA256_BLOCK_SIZE]
Definition: sha256.h:49
#define MD_PAD(ctx, size, f)
Definition: sha256.c:300
#define SHA256_DIGEST_SIZE
Definition: sha256.h:39
void sha256_update(void *ctx_, const uint8_t *data, size_t length)
Definition: sha256.c:326
void sha256_digest(void *ctx_, uint8_t *digest)
Definition: sha256.c:398
static void _nettle_sha256_compress(uint32_t *state, const uint8_t *input, const uint32_t *k)
Definition: sha256.c:164
void _nettle_write_be32(size_t length, uint8_t *dst, const uint32_t *src)
Definition: sha256.c:337
#define COMPRESS(ctx, data)
Definition: sha256.c:233
#define SHA256_DATA_LENGTH
Definition: sha256.c:71
#define READ_UINT32(p)
Definition: sha256.c:132
#define EXPAND(W, i)
Definition: sha256.c:101
#define MD_UPDATE(ctx, length, data, f, incr)
Definition: sha256.c:260
static const uint32_t K[64]
Definition: sha256.c:49
uint64_t count
Definition: sha256.h:48
#define WRITE_UINT64(p, i)
Definition: sha256.c:146
void sha256_init(void *ctx_)
Definition: sha256.c:238
#define SHA256_BLOCK_SIZE
Definition: sha256.h:40
#define _SHA256_DIGEST_LENGTH
Definition: sha256.h:43
uint32_t state[_SHA256_DIGEST_LENGTH]
Definition: sha256.h:47
#define WRITE_UINT32(p, i)
Definition: sha256.c:138
unsigned int index
Definition: sha256.h:50