| blob | bdb126fcf87ab1eb0bd31a62cfde1860e9efcef0 |
1 /*\r
2 * SHA-512 algorithm as described at\r
3 * \r
4 * http://csrc.nist.gov/cryptval/shs.html\r
5 */\r
6 \r
7 #include "ssh.h"\r
8 \r
9 #define BLKSIZE 128\r
10 \r
11 /*\r
12 * Arithmetic implementations. Note that AND, XOR and NOT can\r
13 * overlap destination with one source, but the others can't.\r
14 */\r
15 #define add(r,x,y) ( r.lo = y.lo + x.lo, \\r
16 r.hi = y.hi + x.hi + ((uint32)r.lo < (uint32)y.lo) )\r
17 #define rorB(r,x,y) ( r.lo = ((uint32)x.hi >> ((y)-32)) | ((uint32)x.lo << (64-(y))), \\r
18 r.hi = ((uint32)x.lo >> ((y)-32)) | ((uint32)x.hi << (64-(y))) )\r
19 #define rorL(r,x,y) ( r.lo = ((uint32)x.lo >> (y)) | ((uint32)x.hi << (32-(y))), \\r
20 r.hi = ((uint32)x.hi >> (y)) | ((uint32)x.lo << (32-(y))) )\r
21 #define shrB(r,x,y) ( r.lo = (uint32)x.hi >> ((y)-32), r.hi = 0 )\r
22 #define shrL(r,x,y) ( r.lo = ((uint32)x.lo >> (y)) | ((uint32)x.hi << (32-(y))), \\r
23 r.hi = (uint32)x.hi >> (y) )\r
24 #define and(r,x,y) ( r.lo = x.lo & y.lo, r.hi = x.hi & y.hi )\r
25 #define xor(r,x,y) ( r.lo = x.lo ^ y.lo, r.hi = x.hi ^ y.hi )\r
26 #define not(r,x) ( r.lo = ~x.lo, r.hi = ~x.hi )\r
27 #define INIT(h,l) { h, l }\r
28 #define BUILD(r,h,l) ( r.hi = h, r.lo = l )\r
29 #define EXTRACT(h,l,r) ( h = r.hi, l = r.lo )\r
30 \r
31 /* ----------------------------------------------------------------------\r
32 * Core SHA512 algorithm: processes 16-doubleword blocks into a\r
33 * message digest.\r
34 */\r
35 \r
36 #define Ch(r,t,x,y,z) ( not(t,x), and(r,t,z), and(t,x,y), xor(r,r,t) )\r
37 #define Maj(r,t,x,y,z) ( and(r,x,y), and(t,x,z), xor(r,r,t), \\r
38 and(t,y,z), xor(r,r,t) )\r
39 #define bigsigma0(r,t,x) ( rorL(r,x,28), rorB(t,x,34), xor(r,r,t), \\r
40 rorB(t,x,39), xor(r,r,t) )\r
41 #define bigsigma1(r,t,x) ( rorL(r,x,14), rorL(t,x,18), xor(r,r,t), \\r
42 rorB(t,x,41), xor(r,r,t) )\r
43 #define smallsigma0(r,t,x) ( rorL(r,x,1), rorL(t,x,8), xor(r,r,t), \\r
44 shrL(t,x,7), xor(r,r,t) )\r
45 #define smallsigma1(r,t,x) ( rorL(r,x,19), rorB(t,x,61), xor(r,r,t), \\r
46 shrL(t,x,6), xor(r,r,t) )\r
47 \r
48 static void SHA512_Core_Init(SHA512_State *s) {\r
49 static const uint64 iv[] = {\r
50 INIT(0x6a09e667, 0xf3bcc908),\r
51 INIT(0xbb67ae85, 0x84caa73b),\r
52 INIT(0x3c6ef372, 0xfe94f82b),\r
53 INIT(0xa54ff53a, 0x5f1d36f1),\r
54 INIT(0x510e527f, 0xade682d1),\r
55 INIT(0x9b05688c, 0x2b3e6c1f),\r
56 INIT(0x1f83d9ab, 0xfb41bd6b),\r
57 INIT(0x5be0cd19, 0x137e2179),\r
58 };\r
59 int i;\r
60 for (i = 0; i < 8; i++)\r
61 s->h[i] = iv[i];\r
62 }\r
63 \r
64 static void SHA512_Block(SHA512_State *s, uint64 *block) {\r
65 uint64 w[80];\r
66 uint64 a,b,c,d,e,f,g,h;\r
67 static const uint64 k[] = {\r
68 INIT(0x428a2f98, 0xd728ae22), INIT(0x71374491, 0x23ef65cd),\r
69 INIT(0xb5c0fbcf, 0xec4d3b2f), INIT(0xe9b5dba5, 0x8189dbbc),\r
70 INIT(0x3956c25b, 0xf348b538), INIT(0x59f111f1, 0xb605d019),\r
71 INIT(0x923f82a4, 0xaf194f9b), INIT(0xab1c5ed5, 0xda6d8118),\r
72 INIT(0xd807aa98, 0xa3030242), INIT(0x12835b01, 0x45706fbe),\r
73 INIT(0x243185be, 0x4ee4b28c), INIT(0x550c7dc3, 0xd5ffb4e2),\r
74 INIT(0x72be5d74, 0xf27b896f), INIT(0x80deb1fe, 0x3b1696b1),\r
75 INIT(0x9bdc06a7, 0x25c71235), INIT(0xc19bf174, 0xcf692694),\r
76 INIT(0xe49b69c1, 0x9ef14ad2), INIT(0xefbe4786, 0x384f25e3),\r
77 INIT(0x0fc19dc6, 0x8b8cd5b5), INIT(0x240ca1cc, 0x77ac9c65),\r
78 INIT(0x2de92c6f, 0x592b0275), INIT(0x4a7484aa, 0x6ea6e483),\r
79 INIT(0x5cb0a9dc, 0xbd41fbd4), INIT(0x76f988da, 0x831153b5),\r
80 INIT(0x983e5152, 0xee66dfab), INIT(0xa831c66d, 0x2db43210),\r
81 INIT(0xb00327c8, 0x98fb213f), INIT(0xbf597fc7, 0xbeef0ee4),\r
82 INIT(0xc6e00bf3, 0x3da88fc2), INIT(0xd5a79147, 0x930aa725),\r
83 INIT(0x06ca6351, 0xe003826f), INIT(0x14292967, 0x0a0e6e70),\r
84 INIT(0x27b70a85, 0x46d22ffc), INIT(0x2e1b2138, 0x5c26c926),\r
85 INIT(0x4d2c6dfc, 0x5ac42aed), INIT(0x53380d13, 0x9d95b3df),\r
86 INIT(0x650a7354, 0x8baf63de), INIT(0x766a0abb, 0x3c77b2a8),\r
87 INIT(0x81c2c92e, 0x47edaee6), INIT(0x92722c85, 0x1482353b),\r
88 INIT(0xa2bfe8a1, 0x4cf10364), INIT(0xa81a664b, 0xbc423001),\r
89 INIT(0xc24b8b70, 0xd0f89791), INIT(0xc76c51a3, 0x0654be30),\r
90 INIT(0xd192e819, 0xd6ef5218), INIT(0xd6990624, 0x5565a910),\r
91 INIT(0xf40e3585, 0x5771202a), INIT(0x106aa070, 0x32bbd1b8),\r
92 INIT(0x19a4c116, 0xb8d2d0c8), INIT(0x1e376c08, 0x5141ab53),\r
93 INIT(0x2748774c, 0xdf8eeb99), INIT(0x34b0bcb5, 0xe19b48a8),\r
94 INIT(0x391c0cb3, 0xc5c95a63), INIT(0x4ed8aa4a, 0xe3418acb),\r
95 INIT(0x5b9cca4f, 0x7763e373), INIT(0x682e6ff3, 0xd6b2b8a3),\r
96 INIT(0x748f82ee, 0x5defb2fc), INIT(0x78a5636f, 0x43172f60),\r
97 INIT(0x84c87814, 0xa1f0ab72), INIT(0x8cc70208, 0x1a6439ec),\r
98 INIT(0x90befffa, 0x23631e28), INIT(0xa4506ceb, 0xde82bde9),\r
99 INIT(0xbef9a3f7, 0xb2c67915), INIT(0xc67178f2, 0xe372532b),\r
100 INIT(0xca273ece, 0xea26619c), INIT(0xd186b8c7, 0x21c0c207),\r
101 INIT(0xeada7dd6, 0xcde0eb1e), INIT(0xf57d4f7f, 0xee6ed178),\r
102 INIT(0x06f067aa, 0x72176fba), INIT(0x0a637dc5, 0xa2c898a6),\r
103 INIT(0x113f9804, 0xbef90dae), INIT(0x1b710b35, 0x131c471b),\r
104 INIT(0x28db77f5, 0x23047d84), INIT(0x32caab7b, 0x40c72493),\r
105 INIT(0x3c9ebe0a, 0x15c9bebc), INIT(0x431d67c4, 0x9c100d4c),\r
106 INIT(0x4cc5d4be, 0xcb3e42b6), INIT(0x597f299c, 0xfc657e2a),\r
107 INIT(0x5fcb6fab, 0x3ad6faec), INIT(0x6c44198c, 0x4a475817),\r
108 };\r
109 \r
110 int t;\r
111 \r
112 for (t = 0; t < 16; t++)\r
113 w[t] = block[t];\r
114 \r
115 for (t = 16; t < 80; t++) {\r
116 uint64 p, q, r, tmp;\r
117 smallsigma1(p, tmp, w[t-2]);\r
118 smallsigma0(q, tmp, w[t-15]);\r
119 add(r, p, q);\r
120 add(p, r, w[t-7]);\r
121 add(w[t], p, w[t-16]);\r
122 }\r
123 \r
124 a = s->h[0]; b = s->h[1]; c = s->h[2]; d = s->h[3];\r
125 e = s->h[4]; f = s->h[5]; g = s->h[6]; h = s->h[7];\r
126 \r
127 for (t = 0; t < 80; t+=8) {\r
128 uint64 tmp, p, q, r;\r
129 \r
130 #define ROUND(j,a,b,c,d,e,f,g,h) \\r
131 bigsigma1(p, tmp, e); \\r
132 Ch(q, tmp, e, f, g); \\r
133 add(r, p, q); \\r
134 add(p, r, k[j]) ; \\r
135 add(q, p, w[j]); \\r
136 add(r, q, h); \\r
137 bigsigma0(p, tmp, a); \\r
138 Maj(tmp, q, a, b, c); \\r
139 add(q, tmp, p); \\r
140 add(p, r, d); \\r
141 d = p; \\r
142 add(h, q, r);\r
143 \r
144 ROUND(t+0, a,b,c,d,e,f,g,h);\r
145 ROUND(t+1, h,a,b,c,d,e,f,g);\r
146 ROUND(t+2, g,h,a,b,c,d,e,f);\r
147 ROUND(t+3, f,g,h,a,b,c,d,e);\r
148 ROUND(t+4, e,f,g,h,a,b,c,d);\r
149 ROUND(t+5, d,e,f,g,h,a,b,c);\r
150 ROUND(t+6, c,d,e,f,g,h,a,b);\r
151 ROUND(t+7, b,c,d,e,f,g,h,a);\r
152 }\r
153 \r
154 {\r
155 uint64 tmp;\r
156 #define UPDATE(state, local) ( tmp = state, add(state, tmp, local) )\r
157 UPDATE(s->h[0], a); UPDATE(s->h[1], b);\r
158 UPDATE(s->h[2], c); UPDATE(s->h[3], d);\r
159 UPDATE(s->h[4], e); UPDATE(s->h[5], f);\r
160 UPDATE(s->h[6], g); UPDATE(s->h[7], h);\r
161 }\r
162 }\r
163 \r
164 /* ----------------------------------------------------------------------\r
165 * Outer SHA512 algorithm: take an arbitrary length byte string,\r
166 * convert it into 16-doubleword blocks with the prescribed padding\r
167 * at the end, and pass those blocks to the core SHA512 algorithm.\r
168 */\r
169 \r
170 void SHA512_Init(SHA512_State *s) {\r
171 int i;\r
172 SHA512_Core_Init(s);\r
173 s->blkused = 0;\r
174 for (i = 0; i < 4; i++)\r
175 s->len[i] = 0;\r
176 }\r
177 \r
178 void SHA512_Bytes(SHA512_State *s, const void *p, int len) {\r
179 unsigned char *q = (unsigned char *)p;\r
180 uint64 wordblock[16];\r
181 uint32 lenw = len;\r
182 int i;\r
183 \r
184 /*\r
185 * Update the length field.\r
186 */\r
187 for (i = 0; i < 4; i++) {\r
188 s->len[i] += lenw;\r
189 lenw = (s->len[i] < lenw);\r
190 }\r
191 \r
192 if (s->blkused && s->blkused+len < BLKSIZE) {\r
193 /*\r
194 * Trivial case: just add to the block.\r
195 */\r
196 memcpy(s->block + s->blkused, q, len);\r
197 s->blkused += len;\r
198 } else {\r
199 /*\r
200 * We must complete and process at least one block.\r
201 */\r
202 while (s->blkused + len >= BLKSIZE) {\r
203 memcpy(s->block + s->blkused, q, BLKSIZE - s->blkused);\r
204 q += BLKSIZE - s->blkused;\r
205 len -= BLKSIZE - s->blkused;\r
206 /* Now process the block. Gather bytes big-endian into words */\r
207 for (i = 0; i < 16; i++) {\r
208 uint32 h, l;\r
209 h = ( ((uint32)s->block[i*8+0]) << 24 ) |\r
210 ( ((uint32)s->block[i*8+1]) << 16 ) |\r
211 ( ((uint32)s->block[i*8+2]) << 8 ) |\r
212 ( ((uint32)s->block[i*8+3]) << 0 );\r
213 l = ( ((uint32)s->block[i*8+4]) << 24 ) |\r
214 ( ((uint32)s->block[i*8+5]) << 16 ) |\r
215 ( ((uint32)s->block[i*8+6]) << 8 ) |\r
216 ( ((uint32)s->block[i*8+7]) << 0 );\r
217 BUILD(wordblock[i], h, l);\r
218 }\r
219 SHA512_Block(s, wordblock);\r
220 s->blkused = 0;\r
221 }\r
222 memcpy(s->block, q, len);\r
223 s->blkused = len;\r
224 }\r
225 }\r
226 \r
227 void SHA512_Final(SHA512_State *s, unsigned char *digest) {\r
228 int i;\r
229 int pad;\r
230 unsigned char c[BLKSIZE];\r
231 uint32 len[4];\r
232 \r
233 if (s->blkused >= BLKSIZE-16)\r
234 pad = (BLKSIZE-16) + BLKSIZE - s->blkused;\r
235 else\r
236 pad = (BLKSIZE-16) - s->blkused;\r
237 \r
238 for (i = 4; i-- ;) {\r
239 uint32 lenhi = s->len[i];\r
240 uint32 lenlo = i > 0 ? s->len[i-1] : 0;\r
241 len[i] = (lenhi << 3) | (lenlo >> (32-3));\r
242 }\r
243 \r
244 memset(c, 0, pad);\r
245 c[0] = 0x80;\r
246 SHA512_Bytes(s, &c, pad);\r
247 \r
248 for (i = 0; i < 4; i++) {\r
249 c[i*4+0] = (len[3-i] >> 24) & 0xFF;\r
250 c[i*4+1] = (len[3-i] >> 16) & 0xFF;\r
251 c[i*4+2] = (len[3-i] >> 8) & 0xFF;\r
252 c[i*4+3] = (len[3-i] >> 0) & 0xFF;\r
253 }\r
254 \r
255 SHA512_Bytes(s, &c, 16);\r
256 \r
257 for (i = 0; i < 8; i++) {\r
258 uint32 h, l;\r
259 EXTRACT(h, l, s->h[i]);\r
260 digest[i*8+0] = (h >> 24) & 0xFF;\r
261 digest[i*8+1] = (h >> 16) & 0xFF;\r
262 digest[i*8+2] = (h >> 8) & 0xFF;\r
263 digest[i*8+3] = (h >> 0) & 0xFF;\r
264 digest[i*8+4] = (l >> 24) & 0xFF;\r
265 digest[i*8+5] = (l >> 16) & 0xFF;\r
266 digest[i*8+6] = (l >> 8) & 0xFF;\r
267 digest[i*8+7] = (l >> 0) & 0xFF;\r
268 }\r
269 }\r
270 \r
271 void SHA512_Simple(const void *p, int len, unsigned char *output) {\r
272 SHA512_State s;\r
273 \r
274 SHA512_Init(&s);\r
275 SHA512_Bytes(&s, p, len);\r
276 SHA512_Final(&s, output);\r
277 }\r
278 \r
279 #ifdef TEST\r
280 \r
281 #include <stdio.h>\r
282 #include <stdlib.h>\r
283 #include <assert.h>\r
284 \r
285 int main(void) {\r
286 unsigned char digest[64];\r
287 int i, j, errors;\r
288 \r
289 struct {\r
290 const char *teststring;\r
291 unsigned char digest512[64];\r
292 } tests[] = {\r
293 { "abc", {\r
294 0xdd, 0xaf, 0x35, 0xa1, 0x93, 0x61, 0x7a, 0xba,\r
295 0xcc, 0x41, 0x73, 0x49, 0xae, 0x20, 0x41, 0x31,\r
296 0x12, 0xe6, 0xfa, 0x4e, 0x89, 0xa9, 0x7e, 0xa2,\r
297 0x0a, 0x9e, 0xee, 0xe6, 0x4b, 0x55, 0xd3, 0x9a,\r
298 0x21, 0x92, 0x99, 0x2a, 0x27, 0x4f, 0xc1, 0xa8,\r
299 0x36, 0xba, 0x3c, 0x23, 0xa3, 0xfe, 0xeb, 0xbd,\r
300 0x45, 0x4d, 0x44, 0x23, 0x64, 0x3c, 0xe8, 0x0e,\r
301 0x2a, 0x9a, 0xc9, 0x4f, 0xa5, 0x4c, 0xa4, 0x9f,\r
302 } },\r
303 { "abcdefghbcdefghicdefghijdefghijkefghijklfghijklmghijklmn"\r
304 "hijklmnoijklmnopjklmnopqklmnopqrlmnopqrsmnopqrstnopqrstu", {\r
305 0x8e, 0x95, 0x9b, 0x75, 0xda, 0xe3, 0x13, 0xda,\r
306 0x8c, 0xf4, 0xf7, 0x28, 0x14, 0xfc, 0x14, 0x3f,\r
307 0x8f, 0x77, 0x79, 0xc6, 0xeb, 0x9f, 0x7f, 0xa1,\r
308 0x72, 0x99, 0xae, 0xad, 0xb6, 0x88, 0x90, 0x18,\r
309 0x50, 0x1d, 0x28, 0x9e, 0x49, 0x00, 0xf7, 0xe4,\r
310 0x33, 0x1b, 0x99, 0xde, 0xc4, 0xb5, 0x43, 0x3a,\r
311 0xc7, 0xd3, 0x29, 0xee, 0xb6, 0xdd, 0x26, 0x54,\r
312 0x5e, 0x96, 0xe5, 0x5b, 0x87, 0x4b, 0xe9, 0x09,\r
313 } },\r
314 { NULL, {\r
315 0xe7, 0x18, 0x48, 0x3d, 0x0c, 0xe7, 0x69, 0x64,\r
316 0x4e, 0x2e, 0x42, 0xc7, 0xbc, 0x15, 0xb4, 0x63,\r
317 0x8e, 0x1f, 0x98, 0xb1, 0x3b, 0x20, 0x44, 0x28,\r
318 0x56, 0x32, 0xa8, 0x03, 0xaf, 0xa9, 0x73, 0xeb,\r
319 0xde, 0x0f, 0xf2, 0x44, 0x87, 0x7e, 0xa6, 0x0a,\r
320 0x4c, 0xb0, 0x43, 0x2c, 0xe5, 0x77, 0xc3, 0x1b,\r
321 0xeb, 0x00, 0x9c, 0x5c, 0x2c, 0x49, 0xaa, 0x2e,\r
322 0x4e, 0xad, 0xb2, 0x17, 0xad, 0x8c, 0xc0, 0x9b, \r
323 } },\r
324 };\r
325 \r
326 errors = 0;\r
327 \r
328 for (i = 0; i < sizeof(tests) / sizeof(*tests); i++) {\r
329 if (tests[i].teststring) {\r
330 SHA512_Simple(tests[i].teststring,\r
331 strlen(tests[i].teststring), digest);\r
332 } else {\r
333 SHA512_State s;\r
334 int n;\r
335 SHA512_Init(&s);\r
336 for (n = 0; n < 1000000 / 40; n++)\r
337 SHA512_Bytes(&s, "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",\r
338 40);\r
339 SHA512_Final(&s, digest);\r
340 }\r
341 for (j = 0; j < 64; j++) {\r
342 if (digest[j] != tests[i].digest512[j]) {\r
343 fprintf(stderr,\r
344 "\"%s\" digest512 byte %d should be 0x%02x, is 0x%02x\n",\r
345 tests[i].teststring, j, tests[i].digest512[j],\r
346 digest[j]);\r
347 errors++;\r
348 }\r
349 }\r
350 \r
351 }\r
352 \r
353 printf("%d errors\n", errors);\r
354 \r
355 return 0;\r
356 }\r
357 \r
358 #endif\r