sshsh512.c

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