src/TortoisePlink/SSHSH512.C

   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 + (r.lo < y.lo) )\r
  17 #define rorB(r,x,y) ( r.lo = (x.hi >> ((y)-32)) | (x.lo << (64-(y))), \\r
  18                       r.hi = (x.lo >> ((y)-32)) | (x.hi << (64-(y))) )\r
  19 #define rorL(r,x,y) ( r.lo = (x.lo >> (y)) | (x.hi << (32-(y))), \\r
  20                       r.hi = (x.hi >> (y)) | (x.lo << (32-(y))) )\r
  21 #define shrB(r,x,y) ( r.lo = x.hi >> ((y)-32), r.hi = 0 )\r
  22 #define shrL(r,x,y) ( r.lo = (x.lo >> (y)) | (x.hi << (32-(y))), \\r
  23                       r.hi = 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