sshsh512.c

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