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     smemclr(&s, sizeof(s));
 310 }
 311
 312 void SHA384_Simple(const void *p, int len, unsigned char *output) {
 313     SHA512_State s;
 314
 315     SHA384_Init(&s);
 316     SHA512_Bytes(&s, p, len);
 317     SHA384_Final(&s, output);
 318     smemclr(&s, sizeof(s));
 319 }
 320
 321 /*
 322  * Thin abstraction for things where hashes are pluggable.
 323  */
 324
 325 static void *sha512_init(void)
 326 {
 327     SHA512_State *s;
 328
 329     s = snew(SHA512_State);
 330     SHA512_Init(s);
 331     return s;
 332 }
 333
 334 static void *sha512_copy(const void *vold)
 335 {
 336     const SHA512_State *old = (const SHA512_State *)vold;
 337     SHA512_State *s;
 338
 339     s = snew(SHA512_State);
 340     *s = *old;
 341     return s;
 342 }
 343
 344 static void sha512_free(void *handle)
 345 {
 346     SHA512_State *s = handle;
 347
 348     smemclr(s, sizeof(*s));
 349     sfree(s);
 350 }
 351
 352 static void sha512_bytes(void *handle, const void *p, int len)
 353 {
 354     SHA512_State *s = handle;
 355
 356     SHA512_Bytes(s, p, len);
 357 }
 358
 359 static void sha512_final(void *handle, unsigned char *output)
 360 {
 361     SHA512_State *s = handle;
 362
 363     SHA512_Final(s, output);
 364     sha512_free(s);
 365 }
 366
 367 const struct ssh_hash ssh_sha512 = {
 368     sha512_init, sha512_copy, sha512_bytes, sha512_final, sha512_free,
 369     64, "SHA-512"
 370 };
 371
 372 static void *sha384_init(void)
 373 {
 374     SHA512_State *s;
 375
 376     s = snew(SHA512_State);
 377     SHA384_Init(s);
 378     return s;
 379 }
 380
 381 static void sha384_final(void *handle, unsigned char *output)
 382 {
 383     SHA512_State *s = handle;
 384
 385     SHA384_Final(s, output);
 386     smemclr(s, sizeof(*s));
 387     sfree(s);
 388 }
 389
 390 const struct ssh_hash ssh_sha384 = {
 391     sha384_init, sha512_copy, sha512_bytes, sha384_final, sha512_free,
 392     48, "SHA-384"
 393 };
 394
 395 #ifdef TEST
 396
 397 #include <stdio.h>
 398 #include <stdlib.h>
 399 #include <assert.h>
 400
 401 int main(void) {
 402     unsigned char digest[64];
 403     int i, j, errors;
 404
 405     struct {
 406         const char *teststring;
 407         unsigned char digest512[64];
 408     } tests[] = {
 409         { "abc", {
 410             0xdd, 0xaf, 0x35, 0xa1, 0x93, 0x61, 0x7a, 0xba,
 411             0xcc, 0x41, 0x73, 0x49, 0xae, 0x20, 0x41, 0x31,
 412             0x12, 0xe6, 0xfa, 0x4e, 0x89, 0xa9, 0x7e, 0xa2,
 413             0x0a, 0x9e, 0xee, 0xe6, 0x4b, 0x55, 0xd3, 0x9a,
 414             0x21, 0x92, 0x99, 0x2a, 0x27, 0x4f, 0xc1, 0xa8,
 415             0x36, 0xba, 0x3c, 0x23, 0xa3, 0xfe, 0xeb, 0xbd,
 416             0x45, 0x4d, 0x44, 0x23, 0x64, 0x3c, 0xe8, 0x0e,
 417             0x2a, 0x9a, 0xc9, 0x4f, 0xa5, 0x4c, 0xa4, 0x9f,
 418         } },
 419         { "abcdefghbcdefghicdefghijdefghijkefghijklfghijklmghijklmn"
 420         "hijklmnoijklmnopjklmnopqklmnopqrlmnopqrsmnopqrstnopqrstu", {
 421             0x8e, 0x95, 0x9b, 0x75, 0xda, 0xe3, 0x13, 0xda,
 422             0x8c, 0xf4, 0xf7, 0x28, 0x14, 0xfc, 0x14, 0x3f,
 423             0x8f, 0x77, 0x79, 0xc6, 0xeb, 0x9f, 0x7f, 0xa1,
 424             0x72, 0x99, 0xae, 0xad, 0xb6, 0x88, 0x90, 0x18,
 425             0x50, 0x1d, 0x28, 0x9e, 0x49, 0x00, 0xf7, 0xe4,
 426             0x33, 0x1b, 0x99, 0xde, 0xc4, 0xb5, 0x43, 0x3a,
 427             0xc7, 0xd3, 0x29, 0xee, 0xb6, 0xdd, 0x26, 0x54,
 428             0x5e, 0x96, 0xe5, 0x5b, 0x87, 0x4b, 0xe9, 0x09,
 429         } },
 430         { NULL, {
 431             0xe7, 0x18, 0x48, 0x3d, 0x0c, 0xe7, 0x69, 0x64,
 432             0x4e, 0x2e, 0x42, 0xc7, 0xbc, 0x15, 0xb4, 0x63,
 433             0x8e, 0x1f, 0x98, 0xb1, 0x3b, 0x20, 0x44, 0x28,
 434             0x56, 0x32, 0xa8, 0x03, 0xaf, 0xa9, 0x73, 0xeb,
 435             0xde, 0x0f, 0xf2, 0x44, 0x87, 0x7e, 0xa6, 0x0a,
 436             0x4c, 0xb0, 0x43, 0x2c, 0xe5, 0x77, 0xc3, 0x1b,
 437             0xeb, 0x00, 0x9c, 0x5c, 0x2c, 0x49, 0xaa, 0x2e,
 438             0x4e, 0xad, 0xb2, 0x17, 0xad, 0x8c, 0xc0, 0x9b,
 439         } },
 440     };
 441
 442     errors = 0;
 443
 444     for (i = 0; i < sizeof(tests) / sizeof(*tests); i++) {
 445         if (tests[i].teststring) {
 446             SHA512_Simple(tests[i].teststring,
 447                           strlen(tests[i].teststring), digest);
 448         } else {
 449             SHA512_State s;
 450             int n;
 451             SHA512_Init(&s);
 452             for (n = 0; n < 1000000 / 40; n++)
 453                 SHA512_Bytes(&s, "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
 454                              40);
 455             SHA512_Final(&s, digest);
 456         }
 457         for (j = 0; j < 64; j++) {
 458             if (digest[j] != tests[i].digest512[j]) {
 459                 fprintf(stderr,
 460                         "\"%s\" digest512 byte %d should be 0x%02x, is 0x%02x\n",
 461                         tests[i].teststring, j, tests[i].digest512[j],
 462                         digest[j]);
 463                 errors++;
 464             }
 465         }
 466
 467     }
 468
 469     printf("%d errors\n", errors);
 470
 471     return 0;
 472 }
 473
 474 #endif