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