1 #include <stdint.h>
2 #include <stdio.h>
3 #include <string.h>
4 #include <assert.h>
5
6 #define DEBUG 0
7
8 /*
9 * For code size reasons, this doesn't even try to support
10 * input sizes >= 2^32 bits = 2^29 bytes
11 */
12 struct sha256_state {
13 uint32_t iv[8]; /* a, b, c, d, e, f, g, h */
14 uint32_t w[64]; /* Fill in first 16 with ntohl(input) */
15 uint32_t bytes;
16 };
17
18 /* Rotate right macro. GCC can usually get this right. */
19 #define ROTR(x,s) ((x)>>(s) | (x)<<(32-(s)))
20
21 #if 1
22 /*
23 * An implementation of SHA-256 for register-starved architectures like
24 * x86 or perhaps the MSP430. (Although the latter's lack of a multi-bit
25 * shifter will doom its performance no matter what.)
26 * This code is also quite small.
27 *
28 * If you have 12 32-bit registers to work with, loading the 8 state
29 * variables into registers is probably faster. If you have 28 registers
30 * or so, you can put the input block into registers as well.
31 *
32 * The key idea is to notice that each round consumes one word from the
33 * key schedule w[i], computes a new a, and shifts all the other state
34 * variables down one position, discarding the old h.
35 *
36 * So if we store the state vector in reverse order h..a, immediately
37 * before w[i], then a single base pointer can be incremented to advance
38 * to the next round.
39 */
40 void
sha256_transform(uint32_t p[76])41 sha256_transform(uint32_t p[76])
42 {
43 static uint32_t const k[64] = {
44 0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b,
45 0x59f111f1, 0x923f82a4, 0xab1c5ed5, 0xd807aa98, 0x12835b01,
46 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7,
47 0xc19bf174, 0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc,
48 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da, 0x983e5152,
49 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147,
50 0x06ca6351, 0x14292967, 0x27b70a85, 0x2e1b2138, 0x4d2c6dfc,
51 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
52 0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819,
53 0xd6990624, 0xf40e3585, 0x106aa070, 0x19a4c116, 0x1e376c08,
54 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f,
55 0x682e6ff3, 0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208,
56 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2
57 };
58 /*
59 * Look, ma, only 6 local variables including p!
60 * Too bad they're so overloaded it's impossible to give them
61 * meaningful names.
62 */
63 register uint32_t const *kp;
64 register uint32_t a, s, t, u;
65
66 /* Step 1: Expand the 16 words of w[], at p[8..23] into 64 words */
67 for (u = 8; u < 8+64-16; u++) {
68 /* w[i] = s1(w[i-2]) + w[i-7] + s0(w[i-15]) + w[i-16] */
69 /* Form s0(x) = (x >>> 7) ^ (x >>> 18) ^ (x >> 3) */
70 s = t = p[u+1];
71 s = ROTR(s, 18-7);
72 s ^= t;
73 s = ROTR(s, 7);
74 s ^= t >> 3;
75 /* Form s1(x) = (x >>> 17) ^ (x >>> 19) ^ (x >> 10) */
76 a = t = p[u+14];
77 a = ROTR(a, 19-17);
78 a ^= t;
79 a = ROTR(a, 17);
80 a ^= t >> 10;
81
82 p[u+16] = s + a + p[u] + p[u+9];
83 }
84
85 /* Step 2: Copy the initial values of d, c, b, a out of the way */
86 p[72] = p[4];
87 p[73] = p[5];
88 p[74] = p[6];
89 p[75] = a = p[7];
90
91 /*
92 * Step 3: The big loop.
93 * We maintain p[0..7] = h..a, and p[8] is w[i]
94 */
95 kp = k;
96
97 do {
98 /* T1 = h + S1(e) + Ch(e,f,g) + k[i] + w[i] */
99 /* Form Ch(e,f,g) = g ^ (e & (f ^ g)) */
100 s = t = p[1]; /* g */
101 s ^= p[2]; /* f ^ g */
102 s &= u = p[3]; /* e & (f ^ g) */
103 s ^= t;
104 /* Form S1(e) = (e >>> 6) ^ (e >>> 11) ^ (e >>> 25) */
105 t = u;
106 u = ROTR(u, 25-11);
107 u ^= t;
108 u = ROTR(u, 11-6);
109 u ^= t;
110 u = ROTR(u, 6);
111 s += u;
112 /* Now add other things to t1 */
113 s += p[0] + p[8] + *kp; /* h + w[i] + kp[i] */
114 /* Round function: e = d + T1 */
115 p[4] += s;
116 /* a = t1 + (t2 = S0(a) + Maj(a,b,c) */
117 /* Form S0(a) = (a >>> 2) ^ (a >>> 13) ^ (a >>> 22) */
118 t = a;
119 t = ROTR(t, 22-13);
120 t ^= a;
121 t = ROTR(t, 13-2);
122 t ^= a;
123 t = ROTR(t, 2);
124 s += t;
125 /* Form Maj(a,b,c) = (a & b) + (c & (a ^ b)) */
126 t = a;
127 u = p[6]; /* b */
128 a ^= u; /* a ^ b */
129 u &= t; /* a & b */
130 a &= p[5]; /* c & (a + b) */
131 s += u;
132 a += s; /* Sum final result into a */
133
134 /* Now store new a on top of w[i] and shift... */
135 p[8] = a;
136 p++;
137 #if DEBUG
138 /* If debugging, print out the state variables each round */
139 printf("%2u:", kp-k);
140 for (t = 8; t--; )
141 printf(" %08x", p[t]);
142 putchar('\n');
143 #endif
144 } while (++kp != k+64);
145
146 /* Now, do the final summation. */
147 p -= 64;
148 /*
149 * Now, the final h..a are in p[64..71], and the initial values
150 * are in p[0..7]. Except that p[4..7] got trashed in the loop
151 * above, so use the copies we made.
152 */
153 p[0] += p[64];
154 p[1] += p[65];
155 p[2] += p[66];
156 p[3] += p[67];
157 p[4] = p[68] + p[72];
158 p[5] = p[69] + p[73];
159 p[6] = p[70] + p[74];
160 p[7] = a + p[75];
161 }
162
163 #else
164
165 /* A space-optimized ARM assembly implementation */
166 void sha256_transform(uint32_t p[8+64]);
167
168 #endif
169
170 /* Initial values H0..H7 for SHA-256, and SHA-224. */
171 static uint32_t const sha256_iv[8] = {
172 0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a,
173 0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19
174 };
175 #if 0
176 static uint32_t const sha224_iv[8] = {
177 0xc1059ed8, 0x367cd507, 0x3070dd17, 0xf70e5939,
178 0xffc00b31, 0x68581511, 0x64f98fa7, 0xbefa4fa4
179 };
180 #endif
181
182 void
sha256_begin(struct sha256_state * s)183 sha256_begin(struct sha256_state *s)
184 {
185 memcpy(s->iv, sha256_iv, sizeof sha256_iv);
186 s->bytes = 0;
187 }
188
189 #include <netinet/in.h> /* For ntohl, htonl */
190
191 void
sha256_hash(unsigned char const * data,size_t len,struct sha256_state * s)192 sha256_hash(unsigned char const *data, size_t len, struct sha256_state *s)
193 {
194 unsigned space = 64 - (unsigned)s->bytes % 64;
195 unsigned i;
196
197 s->bytes += len;
198
199 while (len >= space) {
200 memcpy((unsigned char *)s->w + 64 - space, data, space);
201 len -= space;
202 space = 64;
203 for (i = 0; i < 16; i++)
204 s->w[i] = ntohl(s->w[i]);
205 sha256_transform(s->iv);
206 }
207 memcpy((unsigned char *)s->w + 64 - space, data, len);
208 }
209
210 void
sha256_end(unsigned char hash[32],struct sha256_state * s)211 sha256_end(unsigned char hash[32], struct sha256_state *s)
212 {
213 static unsigned char const padding[64] = { 0x80, 0, 0 /* ,... */ };
214 uint32_t bytes = s->bytes;
215 unsigned i;
216
217 /* Add trailing bit padding. */
218 sha256_hash(padding, 64 - ((bytes+8) & 63), s);
219 assert(s->bytes % 64 == 56);
220
221 /* Byte-swap and hash final block */
222 for (i = 0; i < 14; i++)
223 s->w[i] = ntohl(s->w[i]);
224 s->w[14] = 0; /* We don't even try */
225 s->w[15] = s->bytes << 3;
226 sha256_transform(s->iv);
227
228 for (i = 0; i < 8; i++)
229 s->iv[i] = htonl(s->iv[i]);
230 memcpy(hash, s->iv, sizeof s->iv);
231 memset(s, 0, sizeof *s); /* Good cryptographic hygiene */
232 }
233
234 void
sha256(unsigned char hash[32],const unsigned char * data,size_t len)235 sha256(unsigned char hash[32], const unsigned char *data, size_t len)
236 {
237 struct sha256_state s;
238 sha256_begin(&s);
239 sha256_hash(data, len, &s);
240 sha256_end(hash, &s);
241 }
242