1 /* sha256.h
2 *
3 * The sha256 hash function.
4 */
5
6 /* nettle, low-level cryptographics library
7 *
8 * Copyright (C) 2001 Niels M�ller
9 *
10 * This program is free software; you can redistribute it and/or
11 * modify it under the terms of the GNU General Public License as
12 * published by the Free Software Foundation; either version 2 of the
13 * License, or (at your option) any later version.
14 *
15 * The nettle library is distributed in the hope that it will be useful, but
16 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
17 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
18 * License for more details.
19 *
20 * You should have received a copy of the GNU Lesser General Public License
21 * along with the nettle library; see the file COPYING.LIB. If not, write to
22 * the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
23 * MA 02111-1307, USA.
24 */
25
26 /* Modelled after the sha1.c code by Peter Gutmann. */
27
28 /* This has been modified in order to fit in mhash.
29 * --nmav.
30 */
31
32 #include "libdefs.h"
33
34 #ifdef ENABLE_SHA256
35
36 #include "mhash_sha256.h"
37 #include "mhash_sha1.h"
38
39 /* A block, treated as a sequence of 32-bit words. */
40 #define SHA256_DATA_LENGTH 16
41
42 #define ROTR(n,x) ((x)>>(n) | ((x)<<(32-(n))))
43 #define SHR(n,x) ((x)>>(n))
44
45 /* The SHA256 functions. The Choice function is the same as the SHA1
46 function f1, and the majority function is the same as the SHA1 f3
47 function. They can be optimized to save one boolean operation each
48 - thanks to Rich Schroeppel, rcs@cs.arizona.edu for discovering
49 this */
50
51 /* #define Choice(x,y,z) ( ( (x) & (y) ) | ( ~(x) & (z) ) ) */
52 #define Choice(x,y,z) ( (z) ^ ( (x) & ( (y) ^ (z) ) ) )
53 /* #define Majority(x,y,z) ( ((x) & (y)) ^ ((x) & (z)) ^ ((y) & (z)) ) */
54 #define Majority(x,y,z) ( ((x) & (y)) ^ ((z) & ((x) ^ (y))) )
55
56 #define S0(x) (ROTR(2,(x)) ^ ROTR(13,(x)) ^ ROTR(22,(x)))
57 #define S1(x) (ROTR(6,(x)) ^ ROTR(11,(x)) ^ ROTR(25,(x)))
58
59 #define s0(x) (ROTR(7,(x)) ^ ROTR(18,(x)) ^ SHR(3,(x)))
60 #define s1(x) (ROTR(17,(x)) ^ ROTR(19,(x)) ^ SHR(10,(x)))
61
62 /* Generated by the shadata program. */
63 static __const mutils_word32 K[64] = {
64 0x428a2f98UL, 0x71374491UL, 0xb5c0fbcfUL, 0xe9b5dba5UL,
65 0x3956c25bUL, 0x59f111f1UL, 0x923f82a4UL, 0xab1c5ed5UL,
66 0xd807aa98UL, 0x12835b01UL, 0x243185beUL, 0x550c7dc3UL,
67 0x72be5d74UL, 0x80deb1feUL, 0x9bdc06a7UL, 0xc19bf174UL,
68 0xe49b69c1UL, 0xefbe4786UL, 0xfc19dc6UL, 0x240ca1ccUL,
69 0x2de92c6fUL, 0x4a7484aaUL, 0x5cb0a9dcUL, 0x76f988daUL,
70 0x983e5152UL, 0xa831c66dUL, 0xb00327c8UL, 0xbf597fc7UL,
71 0xc6e00bf3UL, 0xd5a79147UL, 0x6ca6351UL, 0x14292967UL,
72 0x27b70a85UL, 0x2e1b2138UL, 0x4d2c6dfcUL, 0x53380d13UL,
73 0x650a7354UL, 0x766a0abbUL, 0x81c2c92eUL, 0x92722c85UL,
74 0xa2bfe8a1UL, 0xa81a664bUL, 0xc24b8b70UL, 0xc76c51a3UL,
75 0xd192e819UL, 0xd6990624UL, 0xf40e3585UL, 0x106aa070UL,
76 0x19a4c116UL, 0x1e376c08UL, 0x2748774cUL, 0x34b0bcb5UL,
77 0x391c0cb3UL, 0x4ed8aa4aUL, 0x5b9cca4fUL, 0x682e6ff3UL,
78 0x748f82eeUL, 0x78a5636fUL, 0x84c87814UL, 0x8cc70208UL,
79 0x90befffaUL, 0xa4506cebUL, 0xbef9a3f7UL, 0xc67178f2UL,
80 };
81
82 /* The initial expanding function. The hash function is defined over an
83 64-word expanded input array W, where the first 16 are copies of the input
84 data, and the remaining 64 are defined by
85
86 W[ t ] = s1(W[t-2] + W[t-7] + s0(W[i-15] + W[i-16]
87
88 This implementation generates these values on the fly in a circular
89 buffer - thanks to Colin Plumb, colin@nyx10.cs.du.edu for this
90 optimization.
91 */
92
93 #define EXPAND(W,i) \
94 ( W[(i) & 15 ] += (s1(W[((i)-2) & 15]) + W[((i)-7) & 15] + s0(W[((i)-15) & 15])) )
95
96 /* The prototype SHA sub-round. The fundamental sub-round is:
97
98 T1 = h + S1(e) + Choice(e,f,g) + K[t] + W[t]
99 T2 = S0(a) + Majority(a,b,c)
100 a' = T1+T2
101 b' = a
102 c' = b
103 d' = c
104 e' = d + T1
105 f' = e
106 g' = f
107 h' = g
108
109 but this is implemented by unrolling the loop 8 times and renaming
110 the variables
111 ( h, a, b, c, d, e, f, g ) = ( a, b, c, d, e, f, g, h ) each
112 iteration. This code is then replicated 8, using the next 8 values
113 from the W[] array each time */
114
115 /* FIXME: We can probably reorder this to optimize away at least one
116 * of T1 and T2. It's crucial that DATA is only used once, as that
117 * argument will have side effects. */
118 #define ROUND(a,b,c,d,e,f,g,h,k,data) do { \
119 mutils_word32 T1 = h + S1(e) + Choice(e,f,g) + k + data; \
120 mutils_word32 T2 = S0(a) + Majority(a,b,c); \
121 d += T1; \
122 h = T1 + T2; \
123 } while (0)
124
125 /* Initialize the SHA values */
126
sha256_init(struct sha256_ctx * ctx)127 void sha256_init(struct sha256_ctx *ctx)
128 {
129 /* Initial values, also generated by the shadata program. */
130 static __const mutils_word32 H0[_SHA256_DIGEST_LENGTH] = {
131 0x6a09e667UL, 0xbb67ae85UL, 0x3c6ef372UL, 0xa54ff53aUL,
132 0x510e527fUL, 0x9b05688cUL, 0x1f83d9abUL, 0x5be0cd19UL,
133 };
134
135 mutils_memcpy(ctx->state, H0, sizeof(H0));
136
137 /* Initialize bit count */
138 ctx->count_low = ctx->count_high = 0;
139
140 /* Initialize buffer */
141 ctx->index = 0;
142 }
143
144 /* Perform the SHA transformation. Note that this code, like MD5, seems to
145 break some optimizing compilers due to the complexity of the expressions
146 and the size of the basic block. It may be necessary to split it into
147 sections, e.g. based on the four subrounds
148
149 Note that this function destroys the data area */
150
sha256_transform(mutils_word32 * state,mutils_word32 * data)151 static void sha256_transform(mutils_word32 *state, mutils_word32 *data)
152 {
153 mutils_word32 A, B, C, D, E, F, G, H; /* Local vars */
154 mutils_word8 i;
155 __const mutils_word32 *k;
156 mutils_word32 *d;
157
158 /* Set up first buffer and local data buffer */
159 A = state[0];
160 B = state[1];
161 C = state[2];
162 D = state[3];
163 E = state[4];
164 F = state[5];
165 G = state[6];
166 H = state[7];
167
168 /* Heavy mangling */
169 /* First 16 subrounds that act on the original data */
170
171 for (i = 0, k = K, d = data; i < 16; i += 8, k += 8, d += 8) {
172 ROUND(A, B, C, D, E, F, G, H, k[0], d[0]);
173 ROUND(H, A, B, C, D, E, F, G, k[1], d[1]);
174 ROUND(G, H, A, B, C, D, E, F, k[2], d[2]);
175 ROUND(F, G, H, A, B, C, D, E, k[3], d[3]);
176 ROUND(E, F, G, H, A, B, C, D, k[4], d[4]);
177 ROUND(D, E, F, G, H, A, B, C, k[5], d[5]);
178 ROUND(C, D, E, F, G, H, A, B, k[6], d[6]);
179 ROUND(B, C, D, E, F, G, H, A, k[7], d[7]);
180 }
181
182 for (; i < 64; i += 16, k += 16) {
183 ROUND(A, B, C, D, E, F, G, H, k[0], EXPAND(data, 0));
184 ROUND(H, A, B, C, D, E, F, G, k[1], EXPAND(data, 1));
185 ROUND(G, H, A, B, C, D, E, F, k[2], EXPAND(data, 2));
186 ROUND(F, G, H, A, B, C, D, E, k[3], EXPAND(data, 3));
187 ROUND(E, F, G, H, A, B, C, D, k[4], EXPAND(data, 4));
188 ROUND(D, E, F, G, H, A, B, C, k[5], EXPAND(data, 5));
189 ROUND(C, D, E, F, G, H, A, B, k[6], EXPAND(data, 6));
190 ROUND(B, C, D, E, F, G, H, A, k[7], EXPAND(data, 7));
191 ROUND(A, B, C, D, E, F, G, H, k[8], EXPAND(data, 8));
192 ROUND(H, A, B, C, D, E, F, G, k[9], EXPAND(data, 9));
193 ROUND(G, H, A, B, C, D, E, F, k[10], EXPAND(data, 10));
194 ROUND(F, G, H, A, B, C, D, E, k[11], EXPAND(data, 11));
195 ROUND(E, F, G, H, A, B, C, D, k[12], EXPAND(data, 12));
196 ROUND(D, E, F, G, H, A, B, C, k[13], EXPAND(data, 13));
197 ROUND(C, D, E, F, G, H, A, B, k[14], EXPAND(data, 14));
198 ROUND(B, C, D, E, F, G, H, A, k[15], EXPAND(data, 15));
199 }
200
201 /* Update state */
202 state[0] += A;
203 state[1] += B;
204 state[2] += C;
205 state[3] += D;
206 state[4] += E;
207 state[5] += F;
208 state[6] += G;
209 state[7] += H;
210 }
211
sha256_block(struct sha256_ctx * ctx,__const mutils_word8 * block)212 static void sha256_block(struct sha256_ctx *ctx, __const mutils_word8 *block)
213 {
214 mutils_word32 data[SHA256_DATA_LENGTH];
215 mutils_word16 i;
216
217 /* Update block count */
218 if (!++ctx->count_low)
219 ++ctx->count_high;
220
221 /* Endian independent conversion */
222 for (i = 0; i < SHA256_DATA_LENGTH; i++, block += 4)
223 data[i] = STRING2INT(block);
224
225 sha256_transform(ctx->state, data);
226 }
227
228 void
sha256_update(struct sha256_ctx * ctx,__const mutils_word8 * buffer,mutils_word32 length)229 sha256_update(struct sha256_ctx *ctx, __const mutils_word8 *buffer, mutils_word32 length)
230 {
231 mutils_word32 left;
232
233 if (ctx->index) { /* Try to fill partial block */
234 left = SHA256_DATA_SIZE - ctx->index;
235 if (length < left) {
236 mutils_memcpy(ctx->block + ctx->index, buffer, length);
237 ctx->index += length;
238 return; /* Finished */
239 } else {
240 mutils_memcpy(ctx->block + ctx->index, buffer, left);
241 sha256_block(ctx, ctx->block);
242 buffer += left;
243 length -= left;
244 }
245 }
246 while (length >= SHA256_DATA_SIZE) {
247 sha256_block(ctx, buffer);
248 buffer += SHA256_DATA_SIZE;
249 length -= SHA256_DATA_SIZE;
250 }
251 /* Buffer leftovers */
252 /* NOTE: The corresponding sha1 code checks for the special case length == 0.
253 * That seems supoptimal, as I suspect it increases the number of branches. */
254
255 mutils_memcpy(ctx->block, buffer, length);
256 ctx->index = length;
257 }
258
259 /* Final wrapup - pad to SHA1_DATA_SIZE-byte boundary with the bit pattern
260 1 0* (64-bit count of bits processed, MSB-first) */
261
sha256_final(struct sha256_ctx * ctx)262 void sha256_final(struct sha256_ctx *ctx)
263 {
264 mutils_word32 data[SHA256_DATA_LENGTH];
265 mutils_word32 i;
266 mutils_word32 words;
267
268 i = ctx->index;
269
270 /* Set the first char of padding to 0x80. This is safe since there is
271 always at least one byte free */
272
273 /* assert(i < SHA256_DATA_SIZE);
274 */
275 ctx->block[i++] = 0x80;
276
277 /* Fill rest of word */
278 for (; i & 3; i++)
279 ctx->block[i] = 0;
280
281 /* i is now a multiple of the word size 4 */
282 words = i >> 2;
283 for (i = 0; i < words; i++)
284 data[i] = STRING2INT(ctx->block + 4 * i);
285
286 if (words > (SHA256_DATA_LENGTH - 2)) { /* No room for length in this block. Process it and
287 * pad with another one */
288 for (i = words; i < SHA256_DATA_LENGTH; i++)
289 data[i] = 0;
290 sha256_transform(ctx->state, data);
291 for (i = 0; i < (SHA256_DATA_LENGTH - 2); i++)
292 data[i] = 0;
293 } else
294 for (i = words; i < SHA256_DATA_LENGTH - 2; i++)
295 data[i] = 0;
296
297 /* There are 512 = 2^9 bits in one block */
298 data[SHA256_DATA_LENGTH - 2] =
299 (ctx->count_high << 9) | (ctx->count_low >> 23);
300 data[SHA256_DATA_LENGTH - 1] =
301 (ctx->count_low << 9) | (ctx->index << 3);
302 sha256_transform(ctx->state, data);
303 }
304
sha256_digest(__const struct sha256_ctx * ctx,mutils_word8 * s)305 void sha256_digest(__const struct sha256_ctx *ctx, mutils_word8 *s)
306 {
307 mutils_word32 i;
308
309 if (s!=NULL)
310 for (i = 0; i < _SHA256_DIGEST_LENGTH; i++) {
311 *s++ = ctx->state[i] >> 24;
312 *s++ = 0xff & (ctx->state[i] >> 16);
313 *s++ = 0xff & (ctx->state[i] >> 8);
314 *s++ = 0xff & ctx->state[i];
315 }
316 }
317
318 #endif /* ENABLE_SHA256 */
319