sshsh256.c

   1 /*
   2  * SHA-256 algorithm as described at
   3  *
   4  *   http://csrc.nist.gov/cryptval/shs.html
   5  */
   6
   7 #include "ssh.h"
   8
   9 /* ----------------------------------------------------------------------
  10  * Core SHA256 algorithm: processes 16-word blocks into a message digest.
  11  */
  12
  13 #define ror(x,y) ( ((x) << (32-y)) | (((uint32)(x)) >> (y)) )
  14 #define shr(x,y) ( (((uint32)(x)) >> (y)) )
  15 #define Ch(x,y,z) ( ((x) & (y)) ^ (~(x) & (z)) )
  16 #define Maj(x,y,z) ( ((x) & (y)) ^ ((x) & (z)) ^ ((y) & (z)) )
  17 #define bigsigma0(x) ( ror((x),2) ^ ror((x),13) ^ ror((x),22) )
  18 #define bigsigma1(x) ( ror((x),6) ^ ror((x),11) ^ ror((x),25) )
  19 #define smallsigma0(x) ( ror((x),7) ^ ror((x),18) ^ shr((x),3) )
  20 #define smallsigma1(x) ( ror((x),17) ^ ror((x),19) ^ shr((x),10) )
  21
  22 void SHA256_Core_Init(SHA256_State *s) {
  23     s->h[0] = 0x6a09e667;
  24     s->h[1] = 0xbb67ae85;
  25     s->h[2] = 0x3c6ef372;
  26     s->h[3] = 0xa54ff53a;
  27     s->h[4] = 0x510e527f;
  28     s->h[5] = 0x9b05688c;
  29     s->h[6] = 0x1f83d9ab;
  30     s->h[7] = 0x5be0cd19;
  31 }
  32
  33 void SHA256_Block(SHA256_State *s, uint32 *block) {
  34     uint32 w[80];
  35     uint32 a,b,c,d,e,f,g,h;
  36     static const int k[] = {
  37         0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5,
  38         0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
  39         0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3,
  40         0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
  41         0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc,
  42         0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
  43         0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7,
  44         0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
  45         0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13,
  46         0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
  47         0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3,
  48         0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
  49         0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5,
  50         0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
  51         0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208,
  52         0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2,
  53     };
  54
  55     int t;
  56
  57     for (t = 0; t < 16; t++)
  58         w[t] = block[t];
  59
  60     for (t = 16; t < 64; t++)
  61         w[t] = smallsigma1(w[t-2]) + w[t-7] + smallsigma0(w[t-15]) + w[t-16];
  62
  63     a = s->h[0]; b = s->h[1]; c = s->h[2]; d = s->h[3];
  64     e = s->h[4]; f = s->h[5]; g = s->h[6]; h = s->h[7];
  65
  66     for (t = 0; t < 64; t+=8) {
  67         uint32 t1, t2;
  68
  69 #define ROUND(j,a,b,c,d,e,f,g,h) \
  70         t1 = h + bigsigma1(e) + Ch(e,f,g) + k[j] + w[j]; \
  71         t2 = bigsigma0(a) + Maj(a,b,c); \
  72         d = d + t1; h = t1 + t2;
  73
  74         ROUND(t+0, a,b,c,d,e,f,g,h);
  75         ROUND(t+1, h,a,b,c,d,e,f,g);
  76         ROUND(t+2, g,h,a,b,c,d,e,f);
  77         ROUND(t+3, f,g,h,a,b,c,d,e);
  78         ROUND(t+4, e,f,g,h,a,b,c,d);
  79         ROUND(t+5, d,e,f,g,h,a,b,c);
  80         ROUND(t+6, c,d,e,f,g,h,a,b);
  81         ROUND(t+7, b,c,d,e,f,g,h,a);
  82     }
  83
  84     s->h[0] += a; s->h[1] += b; s->h[2] += c; s->h[3] += d;
  85     s->h[4] += e; s->h[5] += f; s->h[6] += g; s->h[7] += h;
  86 }
  87
  88 /* ----------------------------------------------------------------------
  89  * Outer SHA256 algorithm: take an arbitrary length byte string,
  90  * convert it into 16-word blocks with the prescribed padding at
  91  * the end, and pass those blocks to the core SHA256 algorithm.
  92  */
  93
  94 #define BLKSIZE 64
  95
  96 void SHA256_Init(SHA256_State *s) {
  97     SHA256_Core_Init(s);
  98     s->blkused = 0;
  99     s->lenhi = s->lenlo = 0;
 100 }
 101
 102 void SHA256_Bytes(SHA256_State *s, const void *p, int len) {
 103     unsigned char *q = (unsigned char *)p;
 104     uint32 wordblock[16];
 105     uint32 lenw = len;
 106     int i;
 107
 108     /*
 109      * Update the length field.
 110      */
 111     s->lenlo += lenw;
 112     s->lenhi += (s->lenlo < lenw);
 113
 114     if (s->blkused && s->blkused+len < BLKSIZE) {
 115         /*
 116          * Trivial case: just add to the block.
 117          */
 118         memcpy(s->block + s->blkused, q, len);
 119         s->blkused += len;
 120     } else {
 121         /*
 122          * We must complete and process at least one block.
 123          */
 124         while (s->blkused + len >= BLKSIZE) {
 125             memcpy(s->block + s->blkused, q, BLKSIZE - s->blkused);
 126             q += BLKSIZE - s->blkused;
 127             len -= BLKSIZE - s->blkused;
 128             /* Now process the block. Gather bytes big-endian into words */
 129             for (i = 0; i < 16; i++) {
 130                 wordblock[i] =
 131                     ( ((uint32)s->block[i*4+0]) << 24 ) |
 132                     ( ((uint32)s->block[i*4+1]) << 16 ) |
 133                     ( ((uint32)s->block[i*4+2]) <<  8 ) |
 134                     ( ((uint32)s->block[i*4+3]) <<  0 );
 135             }
 136             SHA256_Block(s, wordblock);
 137             s->blkused = 0;
 138         }
 139         memcpy(s->block, q, len);
 140         s->blkused = len;
 141     }
 142 }
 143
 144 void SHA256_Final(SHA256_State *s, unsigned char *digest) {
 145     int i;
 146     int pad;
 147     unsigned char c[64];
 148     uint32 lenhi, lenlo;
 149
 150     if (s->blkused >= 56)
 151         pad = 56 + 64 - s->blkused;
 152     else
 153         pad = 56 - s->blkused;
 154
 155     lenhi = (s->lenhi << 3) | (s->lenlo >> (32-3));
 156     lenlo = (s->lenlo << 3);
 157
 158     memset(c, 0, pad);
 159     c[0] = 0x80;
 160     SHA256_Bytes(s, &c, pad);
 161
 162     c[0] = (lenhi >> 24) & 0xFF;
 163     c[1] = (lenhi >> 16) & 0xFF;
 164     c[2] = (lenhi >>  8) & 0xFF;
 165     c[3] = (lenhi >>  0) & 0xFF;
 166     c[4] = (lenlo >> 24) & 0xFF;
 167     c[5] = (lenlo >> 16) & 0xFF;
 168     c[6] = (lenlo >>  8) & 0xFF;
 169     c[7] = (lenlo >>  0) & 0xFF;
 170
 171     SHA256_Bytes(s, &c, 8);
 172
 173     for (i = 0; i < 8; i++) {
 174         digest[i*4+0] = (s->h[i] >> 24) & 0xFF;
 175         digest[i*4+1] = (s->h[i] >> 16) & 0xFF;
 176         digest[i*4+2] = (s->h[i] >>  8) & 0xFF;
 177         digest[i*4+3] = (s->h[i] >>  0) & 0xFF;
 178     }
 179 }
 180
 181 void SHA256_Simple(const void *p, int len, unsigned char *output) {
 182     SHA256_State s;
 183
 184     SHA256_Init(&s);
 185     SHA256_Bytes(&s, p, len);
 186     SHA256_Final(&s, output);
 187     smemclr(&s, sizeof(s));
 188 }
 189
 190 /*
 191  * Thin abstraction for things where hashes are pluggable.
 192  */
 193
 194 static void *sha256_init(void)
 195 {
 196     SHA256_State *s;
 197
 198     s = snew(SHA256_State);
 199     SHA256_Init(s);
 200     return s;
 201 }
 202
 203 static void *sha256_copy(const void *vold)
 204 {
 205     const SHA256_State *old = (const SHA256_State *)vold;
 206     SHA256_State *s;
 207
 208     s = snew(SHA256_State);
 209     *s = *old;
 210     return s;
 211 }
 212
 213 static void sha256_free(void *handle)
 214 {
 215     SHA256_State *s = handle;
 216
 217     smemclr(s, sizeof(*s));
 218     sfree(s);
 219 }
 220
 221 static void sha256_bytes(void *handle, const void *p, int len)
 222 {
 223     SHA256_State *s = handle;
 224
 225     SHA256_Bytes(s, p, len);
 226 }
 227
 228 static void sha256_final(void *handle, unsigned char *output)
 229 {
 230     SHA256_State *s = handle;
 231
 232     SHA256_Final(s, output);
 233     sha256_free(s);
 234 }
 235
 236 const struct ssh_hash ssh_sha256 = {
 237     sha256_init, sha256_copy, sha256_bytes, sha256_final, sha256_free,
 238     32, "SHA-256"
 239 };
 240
 241 /* ----------------------------------------------------------------------
 242  * The above is the SHA-256 algorithm itself. Now we implement the
 243  * HMAC wrapper on it.
 244  */
 245
 246 static void *sha256_make_context(void *cipher_ctx)
 247 {
 248     return snewn(3, SHA256_State);
 249 }
 250
 251 static void sha256_free_context(void *handle)
 252 {
 253     smemclr(handle, 3 * sizeof(SHA256_State));
 254     sfree(handle);
 255 }
 256
 257 static void sha256_key_internal(void *handle, unsigned char *key, int len)
 258 {
 259     SHA256_State *keys = (SHA256_State *)handle;
 260     unsigned char foo[64];
 261     int i;
 262
 263     memset(foo, 0x36, 64);
 264     for (i = 0; i < len && i < 64; i++)
 265         foo[i] ^= key[i];
 266     SHA256_Init(&keys[0]);
 267     SHA256_Bytes(&keys[0], foo, 64);
 268
 269     memset(foo, 0x5C, 64);
 270     for (i = 0; i < len && i < 64; i++)
 271         foo[i] ^= key[i];
 272     SHA256_Init(&keys[1]);
 273     SHA256_Bytes(&keys[1], foo, 64);
 274
 275     smemclr(foo, 64);                  /* burn the evidence */
 276 }
 277
 278 static void sha256_key(void *handle, unsigned char *key)
 279 {
 280     sha256_key_internal(handle, key, 32);
 281 }
 282
 283 static void hmacsha256_start(void *handle)
 284 {
 285     SHA256_State *keys = (SHA256_State *)handle;
 286
 287     keys[2] = keys[0];                /* structure copy */
 288 }
 289
 290 static void hmacsha256_bytes(void *handle, unsigned char const *blk, int len)
 291 {
 292     SHA256_State *keys = (SHA256_State *)handle;
 293     SHA256_Bytes(&keys[2], (void *)blk, len);
 294 }
 295
 296 static void hmacsha256_genresult(void *handle, unsigned char *hmac)
 297 {
 298     SHA256_State *keys = (SHA256_State *)handle;
 299     SHA256_State s;
 300     unsigned char intermediate[32];
 301
 302     s = keys[2];                       /* structure copy */
 303     SHA256_Final(&s, intermediate);
 304     s = keys[1];                       /* structure copy */
 305     SHA256_Bytes(&s, intermediate, 32);
 306     SHA256_Final(&s, hmac);
 307 }
 308
 309 static void sha256_do_hmac(void *handle, unsigned char *blk, int len,
 310                          unsigned long seq, unsigned char *hmac)
 311 {
 312     unsigned char seqbuf[4];
 313
 314     PUT_32BIT_MSB_FIRST(seqbuf, seq);
 315     hmacsha256_start(handle);
 316     hmacsha256_bytes(handle, seqbuf, 4);
 317     hmacsha256_bytes(handle, blk, len);
 318     hmacsha256_genresult(handle, hmac);
 319 }
 320
 321 static void sha256_generate(void *handle, unsigned char *blk, int len,
 322                           unsigned long seq)
 323 {
 324     sha256_do_hmac(handle, blk, len, seq, blk + len);
 325 }
 326
 327 static int hmacsha256_verresult(void *handle, unsigned char const *hmac)
 328 {
 329     unsigned char correct[32];
 330     hmacsha256_genresult(handle, correct);
 331     return smemeq(correct, hmac, 32);
 332 }
 333
 334 static int sha256_verify(void *handle, unsigned char *blk, int len,
 335                        unsigned long seq)
 336 {
 337     unsigned char correct[32];
 338     sha256_do_hmac(handle, blk, len, seq, correct);
 339     return smemeq(correct, blk + len, 32);
 340 }
 341
 342 const struct ssh_mac ssh_hmac_sha256 = {
 343     sha256_make_context, sha256_free_context, sha256_key,
 344     sha256_generate, sha256_verify,
 345     hmacsha256_start, hmacsha256_bytes,
 346     hmacsha256_genresult, hmacsha256_verresult,
 347     "hmac-sha2-256", "hmac-sha2-256-etm@openssh.com",
 348     32, 32,
 349     "HMAC-SHA-256"
 350 };
 351
 352 #ifdef TEST
 353
 354 #include <stdio.h>
 355 #include <stdlib.h>
 356 #include <assert.h>
 357
 358 int main(void) {
 359     unsigned char digest[32];
 360     int i, j, errors;
 361
 362     struct {
 363         const char *teststring;
 364         unsigned char digest[32];
 365     } tests[] = {
 366         { "abc", {
 367             0xba, 0x78, 0x16, 0xbf, 0x8f, 0x01, 0xcf, 0xea,
 368             0x41, 0x41, 0x40, 0xde, 0x5d, 0xae, 0x22, 0x23,
 369             0xb0, 0x03, 0x61, 0xa3, 0x96, 0x17, 0x7a, 0x9c,
 370             0xb4, 0x10, 0xff, 0x61, 0xf2, 0x00, 0x15, 0xad,
 371         } },
 372         { "abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq", {
 373             0x24, 0x8d, 0x6a, 0x61, 0xd2, 0x06, 0x38, 0xb8,
 374             0xe5, 0xc0, 0x26, 0x93, 0x0c, 0x3e, 0x60, 0x39,
 375             0xa3, 0x3c, 0xe4, 0x59, 0x64, 0xff, 0x21, 0x67,
 376             0xf6, 0xec, 0xed, 0xd4, 0x19, 0xdb, 0x06, 0xc1,
 377         } },
 378     };
 379
 380     errors = 0;
 381
 382     for (i = 0; i < sizeof(tests) / sizeof(*tests); i++) {
 383         SHA256_Simple(tests[i].teststring,
 384                       strlen(tests[i].teststring), digest);
 385         for (j = 0; j < 32; j++) {
 386             if (digest[j] != tests[i].digest[j]) {
 387                 fprintf(stderr,
 388                         "\"%s\" digest byte %d should be 0x%02x, is 0x%02x\n",
 389                         tests[i].teststring, j, tests[i].digest[j], digest[j]);
 390                 errors++;
 391             }
 392         }
 393     }
 394
 395     printf("%d errors\n", errors);
 396
 397     return 0;
 398 }
 399
 400 #endif