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