stun/sha1.c

   1 /*
   2  * SHA1 hash implementation and interface functions
   3  * Copyright (c) 2003-2005, Jouni Malinen <j@w1.fi>
   4  *
   5  * This program is free software; you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License version 2 as
   7  * published by the Free Software Foundation.
   8  *
   9  * Alternatively, this software may be distributed under the terms of BSD
  10  * license.
  11  *
  12  * See README and COPYING for more details.
  13  */
  14
  15 #include "sha1.h"
  16
  17 #include <string.h>
  18
  19
  20 /* ===== start - public domain SHA1 implementation ===== */
  21
  22 /*
  23 SHA-1 in C
  24 By Steve Reid <sreid@sea-to-sky.net>
  25 100% Public Domain
  26
  27 -----------------
  28 Modified 7/98
  29 By James H. Brown <jbrown@burgoyne.com>
  30 Still 100% Public Domain
  31
  32 Corrected a problem which generated improper hash values on 16 bit machines
  33 Routine SHA1Update changed from
  34         void SHA1Update(SHA1_CTX* context, unsigned char* data, unsigned int
  35 len)
  36 to
  37         void SHA1Update(SHA1_CTX* context, unsigned char* data, unsigned
  38 long len)
  39
  40 The 'len' parameter was declared an int which works fine on 32 bit machines.
  41 However, on 16 bit machines an int is too small for the shifts being done
  42 against
  43 it.  This caused the hash function to generate incorrect values if len was
  44 greater than 8191 (8K - 1) due to the 'len << 3' on line 3 of SHA1Update().
  45
  46 Since the file IO in main() reads 16K at a time, any file 8K or larger would
  47 be guaranteed to generate the wrong hash (e.g. Test Vector #3, a million
  48 "a"s).
  49
  50 I also changed the declaration of variables i & j in SHA1Update to
  51 unsigned long from unsigned int for the same reason.
  52
  53 These changes should make no difference to any 32 bit implementations since
  54 an
  55 int and a long are the same size in those environments.
  56
  57 --
  58 I also corrected a few compiler warnings generated by Borland C.
  59 1. Added #include <process.h> for exit() prototype
  60 2. Removed unused variable 'j' in SHA1Final
  61 3. Changed exit(0) to return(0) at end of main.
  62
  63 ALL changes I made can be located by searching for comments containing 'JHB'
  64 -----------------
  65 Modified 8/98
  66 By Steve Reid <sreid@sea-to-sky.net>
  67 Still 100% public domain
  68
  69 1- Removed #include <process.h> and used return() instead of exit()
  70 2- Fixed overwriting of finalcount in SHA1Final() (discovered by Chris Hall)
  71 3- Changed email address from steve@edmweb.com to sreid@sea-to-sky.net
  72
  73 -----------------
  74 Modified 4/01
  75 By Saul Kravitz <Saul.Kravitz@celera.com>
  76 Still 100% PD
  77 Modified to run on Compaq Alpha hardware.
  78
  79 -----------------
  80 Modified 4/01
  81 By Jouni Malinen <j@w1.fi>
  82 Minor changes to match the coding style used in Dynamics.
  83
  84 Modified September 24, 2004
  85 By Jouni Malinen <j@w1.fi>
  86 Fixed alignment issue in SHA1Transform when SHA1HANDSOFF is defined.
  87
  88 */
  89
  90 /*
  91 Test Vectors (from FIPS PUB 180-1)
  92 "abc"
  93   A9993E36 4706816A BA3E2571 7850C26C 9CD0D89D
  94 "abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq"
  95   84983E44 1C3BD26E BAAE4AA1 F95129E5 E54670F1
  96 A million repetitions of "a"
  97   34AA973C D4C4DAA4 F61EEB2B DBAD2731 6534016F
  98 */
  99
 100 #define rol(value, bits) (((value) << (bits)) | ((value) >> (32 - (bits))))
 101
 102 /* blk0() and blk() perform the initial expand. */
 103 /* I got the idea of expanding during the round function from SSLeay */
 104 #define blk0(i) (block->l[i] = blk0_endiansafe (block->l[i]))
 105
 106 #define blk(i) (block->l[i & 15] = rol(block->l[(i + 13) & 15] ^ \
 107         block->l[(i + 8) & 15] ^ block->l[(i + 2) & 15] ^ block->l[i & 15], 1))
 108
 109 /* (R0+R1), R2, R3, R4 are the different operations used in SHA1 */
 110 #define R0(v,w,x,y,z,i) \
 111         z += ((w & (x ^ y)) ^ y) + blk0(i) + 0x5A827999 + rol(v, 5); \
 112         w = rol(w, 30);
 113 #define R1(v,w,x,y,z,i) \
 114         z += ((w & (x ^ y)) ^ y) + blk(i) + 0x5A827999 + rol(v, 5); \
 115         w = rol(w, 30);
 116 #define R2(v,w,x,y,z,i) \
 117         z += (w ^ x ^ y) + blk(i) + 0x6ED9EBA1 + rol(v, 5); w = rol(w, 30);
 118 #define R3(v,w,x,y,z,i) \
 119         z += (((w | x) & y) | (w & x)) + blk(i) + 0x8F1BBCDC + rol(v, 5); \
 120         w = rol(w, 30);
 121 #define R4(v,w,x,y,z,i) \
 122         z += (w ^ x ^ y) + blk(i) + 0xCA62C1D6 + rol(v, 5); \
 123         w=rol(w, 30);
 124
 125 static void SHA1Transform(uint32_t state[5], const unsigned char buffer[64]);
 126 /* Hash a single 512-bit block. This is the core of the algorithm. */
 127
 128 static int am_big_endian(void)
 129 {
 130   long one= 1;
 131   return !(*((char *)(&one)));
 132 }
 133
 134 static uint32_t blk0_endiansafe (uint32_t l)
 135 {
 136   if (am_big_endian ())
 137     return l;
 138   else
 139     return (rol(l, 24) & 0xFF00FF00) | (rol(l, 8) & 0x00FF00FF);
 140 }
 141
 142 static void SHA1Transform(uint32_t state[5], const unsigned char buffer[64])
 143 {
 144   uint32_t a, b, c, d, e;
 145   typedef union {
 146     uint8_t c[64];
 147     uint32_t l[16];
 148   } CHAR64LONG16;
 149   CHAR64LONG16* block;
 150   uint8_t workspace[64];
 151   block = (CHAR64LONG16 *) workspace;
 152   memcpy(block, buffer, 64);
 153
 154   /* Copy context->state[] to working vars */
 155   a = state[0];
 156   b = state[1];
 157   c = state[2];
 158   d = state[3];
 159   e = state[4];
 160   /* 4 rounds of 20 operations each. Loop unrolled. */
 161   R0(a,b,c,d,e, 0); R0(e,a,b,c,d, 1); R0(d,e,a,b,c, 2); R0(c,d,e,a,b, 3);
 162   R0(b,c,d,e,a, 4); R0(a,b,c,d,e, 5); R0(e,a,b,c,d, 6); R0(d,e,a,b,c, 7);
 163   R0(c,d,e,a,b, 8); R0(b,c,d,e,a, 9); R0(a,b,c,d,e,10); R0(e,a,b,c,d,11);
 164   R0(d,e,a,b,c,12); R0(c,d,e,a,b,13); R0(b,c,d,e,a,14); R0(a,b,c,d,e,15);
 165   R1(e,a,b,c,d,16); R1(d,e,a,b,c,17); R1(c,d,e,a,b,18); R1(b,c,d,e,a,19);
 166   R2(a,b,c,d,e,20); R2(e,a,b,c,d,21); R2(d,e,a,b,c,22); R2(c,d,e,a,b,23);
 167   R2(b,c,d,e,a,24); R2(a,b,c,d,e,25); R2(e,a,b,c,d,26); R2(d,e,a,b,c,27);
 168   R2(c,d,e,a,b,28); R2(b,c,d,e,a,29); R2(a,b,c,d,e,30); R2(e,a,b,c,d,31);
 169   R2(d,e,a,b,c,32); R2(c,d,e,a,b,33); R2(b,c,d,e,a,34); R2(a,b,c,d,e,35);
 170   R2(e,a,b,c,d,36); R2(d,e,a,b,c,37); R2(c,d,e,a,b,38); R2(b,c,d,e,a,39);
 171   R3(a,b,c,d,e,40); R3(e,a,b,c,d,41); R3(d,e,a,b,c,42); R3(c,d,e,a,b,43);
 172   R3(b,c,d,e,a,44); R3(a,b,c,d,e,45); R3(e,a,b,c,d,46); R3(d,e,a,b,c,47);
 173   R3(c,d,e,a,b,48); R3(b,c,d,e,a,49); R3(a,b,c,d,e,50); R3(e,a,b,c,d,51);
 174   R3(d,e,a,b,c,52); R3(c,d,e,a,b,53); R3(b,c,d,e,a,54); R3(a,b,c,d,e,55);
 175   R3(e,a,b,c,d,56); R3(d,e,a,b,c,57); R3(c,d,e,a,b,58); R3(b,c,d,e,a,59);
 176   R4(a,b,c,d,e,60); R4(e,a,b,c,d,61); R4(d,e,a,b,c,62); R4(c,d,e,a,b,63);
 177   R4(b,c,d,e,a,64); R4(a,b,c,d,e,65); R4(e,a,b,c,d,66); R4(d,e,a,b,c,67);
 178   R4(c,d,e,a,b,68); R4(b,c,d,e,a,69); R4(a,b,c,d,e,70); R4(e,a,b,c,d,71);
 179   R4(d,e,a,b,c,72); R4(c,d,e,a,b,73); R4(b,c,d,e,a,74); R4(a,b,c,d,e,75);
 180   R4(e,a,b,c,d,76); R4(d,e,a,b,c,77); R4(c,d,e,a,b,78); R4(b,c,d,e,a,79);
 181   /* Add the working vars back into context.state[] */
 182   state[0] += a;
 183   state[1] += b;
 184   state[2] += c;
 185   state[3] += d;
 186   state[4] += e;
 187   /* Wipe variables */
 188   a = b = c = d = e = 0;
 189   memset(block, 0, 64);
 190 }
 191
 192
 193 /* SHA1Init - Initialize new context */
 194
 195 void SHA1Init(SHA1_CTX* context)
 196 {
 197   /* SHA1 initialization constants */
 198   context->state[0] = 0x67452301;
 199   context->state[1] = 0xEFCDAB89;
 200   context->state[2] = 0x98BADCFE;
 201   context->state[3] = 0x10325476;
 202   context->state[4] = 0xC3D2E1F0;
 203   context->count[0] = context->count[1] = 0;
 204 }
 205
 206
 207 /* Run your data through this. */
 208
 209 void SHA1Update(SHA1_CTX* context, const void *_data, uint32_t len)
 210 {
 211   uint32_t i, j;
 212   const unsigned char *data = _data;
 213
 214   j = (context->count[0] >> 3) & 63;
 215   if ((context->count[0] += len << 3) < (len << 3))
 216     context->count[1]++;
 217   context->count[1] += (len >> 29);
 218   if ((j + len) > 63) {
 219     memcpy(&context->buffer[j], data, (i = 64-j));
 220     SHA1Transform(context->state, context->buffer);
 221     for ( ; i + 63 < len; i += 64) {
 222       SHA1Transform(context->state, &data[i]);
 223     }
 224     j = 0;
 225   }
 226   else i = 0;
 227   memcpy(&context->buffer[j], &data[i], len - i);
 228 }
 229
 230
 231 /* Add padding and return the message digest. */
 232
 233 void SHA1Final(unsigned char digest[20], SHA1_CTX* context)
 234 {
 235   uint32_t i;
 236   unsigned char finalcount[8];
 237
 238   for (i = 0; i < 8; i++) {
 239     finalcount[i] = (unsigned char)
 240         ((context->count[(i >= 4 ? 0 : 1)] >>
 241             ((3-(i & 3)) * 8) ) & 255);  /* Endian independent */
 242   }
 243   SHA1Update(context, (unsigned char *) "\200", 1);
 244   while ((context->count[0] & 504) != 448) {
 245     SHA1Update(context, (unsigned char *) "\0", 1);
 246   }
 247   SHA1Update(context, finalcount, 8);  /* Should cause a SHA1Transform()
 248                                               */
 249   for (i = 0; i < 20; i++) {
 250     digest[i] = (unsigned char)
 251         ((context->state[i >> 2] >> ((3 - (i & 3)) * 8)) &
 252             255);
 253   }
 254   /* Wipe variables */
 255   i = 0;
 256   memset(context->buffer, 0, 64);
 257   memset(context->state, 0, 20);
 258   memset(context->count, 0, 8);
 259   memset(finalcount, 0, 8);
 260 }
 261
 262 /* ===== end - public domain SHA1 implementation ===== */
 263
 264
 265 void HMACInit(HMAC_CTX* context, const uint8_t *key, size_t key_len)
 266 {
 267   unsigned char ipad[64]; /* padding - key XORd with ipad */
 268   unsigned char tk[20];
 269   size_t i;
 270
 271   /* if key is longer than 64 bytes reset it to key = SHA1(key) */
 272   if (key_len > 64) {
 273     sha1_vector(1, &key, &key_len, tk);
 274     key = tk;
 275     key_len = 20;
 276   }
 277
 278   /* start out by storing key in ipad */
 279   memset(ipad, 0, sizeof(ipad));
 280   memcpy(ipad, key, key_len);
 281
 282   /* XOR key with ipad values */
 283   for (i = 0; i < 64; i++)
 284     ipad[i] ^= 0x36;
 285
 286   /* Store the key in our context */
 287   memcpy(context->key, key, key_len);
 288   context->key_len = key_len;
 289
 290   SHA1Init (&context->context);
 291   SHA1Update (&context->context, ipad, sizeof(ipad));
 292 }
 293
 294 void HMACUpdate(HMAC_CTX *context, const void *data, uint32_t len)
 295 {
 296   SHA1Update (&context->context, data, len);
 297 }
 298
 299 void HMACFinal(unsigned char digest[20], HMAC_CTX *context)
 300 {
 301
 302   unsigned char opad[64]; /* padding - key XORd with opad */
 303   unsigned char sha1_digest[SHA1_MAC_LEN];
 304   const uint8_t *_addr[2];
 305   size_t _len[2];
 306   size_t i;
 307
 308   SHA1Final (sha1_digest, &context->context);
 309
 310   memset(opad, 0, sizeof(opad));
 311   memcpy(opad, context->key, context->key_len);
 312
 313   /* XOR key with opad values */
 314   for (i = 0; i < 64; i++)
 315     opad[i] ^= 0x5c;
 316
 317   /* perform outer SHA1 */
 318   _addr[0] = opad;
 319   _len[0] = 64;
 320   _addr[1] = sha1_digest;
 321   _len[1] = SHA1_MAC_LEN;
 322   sha1_vector(2, _addr, _len, digest);
 323 }
 324
 325
 326 /**
 327  * hmac_sha1_vector:
 328  * @key: Key for HMAC operations
 329  * @key_len: Length of the key in bytes
 330  * @num_elem: Number of elements in the data vector
 331  * @addr: Pointers to the data areas
 332  * @len: Lengths of the data blocks
 333  * @mac: Buffer for the hash (20 bytes)
 334  *
 335  * HMAC-SHA1 over data vector (RFC 2104)
 336  */
 337 void hmac_sha1_vector(const uint8_t *key, size_t key_len, size_t num_elem,
 338     const uint8_t *addr[], const size_t *len, uint8_t *mac)
 339 {
 340   unsigned char k_pad[64]; /* padding - key XORd with ipad/opad */
 341   unsigned char tk[20];
 342   const uint8_t *_addr[6];
 343   size_t _len[6], i;
 344
 345   if (num_elem > 5) {
 346     /*
 347      * Fixed limit on the number of fragments to avoid having to
 348      * allocate memory (which could fail).
 349      */
 350     return;
 351   }
 352
 353   /* if key is longer than 64 bytes reset it to key = SHA1(key) */
 354   if (key_len > 64) {
 355     sha1_vector(1, &key, &key_len, tk);
 356     key = tk;
 357     key_len = 20;
 358   }
 359
 360   /* the HMAC_SHA1 transform looks like:
 361    *
 362    * SHA1(K XOR opad, SHA1(K XOR ipad, text))
 363    *
 364    * where K is an n byte key
 365    * ipad is the byte 0x36 repeated 64 times
 366    * opad is the byte 0x5c repeated 64 times
 367    * and text is the data being protected */
 368
 369   /* start out by storing key in ipad */
 370   memset(k_pad, 0, sizeof(k_pad));
 371   memcpy(k_pad, key, key_len);
 372   /* XOR key with ipad values */
 373   for (i = 0; i < 64; i++)
 374     k_pad[i] ^= 0x36;
 375
 376   /* perform inner SHA1 */
 377   _addr[0] = k_pad;
 378   _len[0] = 64;
 379   for (i = 0; i < num_elem; i++) {
 380     _addr[i + 1] = addr[i];
 381     _len[i + 1] = len[i];
 382   }
 383   sha1_vector(1 + num_elem, _addr, _len, mac);
 384
 385   memset(k_pad, 0, sizeof(k_pad));
 386   memcpy(k_pad, key, key_len);
 387   /* XOR key with opad values */
 388   for (i = 0; i < 64; i++)
 389     k_pad[i] ^= 0x5c;
 390
 391   /* perform outer SHA1 */
 392   _addr[0] = k_pad;
 393   _len[0] = 64;
 394   _addr[1] = mac;
 395   _len[1] = SHA1_MAC_LEN;
 396   sha1_vector(2, _addr, _len, mac);
 397 }
 398
 399
 400 /**
 401  * hmac_sha1:
 402  * @key: Key for HMAC operations
 403  * @key_len: Length of the key in bytes
 404  * @data: Pointers to the data area
 405  * @data_len: Length of the data area
 406  * @mac: Buffer for the hash (20 bytes)
 407  *
 408  * HMAC-SHA1 over data buffer (RFC 2104)
 409  */
 410 void hmac_sha1(const uint8_t *key, size_t key_len,
 411     const uint8_t *data, size_t data_len, uint8_t *mac)
 412 {
 413   hmac_sha1_vector(key, key_len, 1, &data, &data_len, mac);
 414 }
 415
 416
 417 /**
 418  * sha1_prf:
 419  * @key: Key for PRF
 420  * @key_len: Length of the key in bytes
 421  * @label: A unique label for each purpose of the PRF
 422  * @data: Extra data to bind into the key
 423  * @data_len: Length of the data
 424  * @buf: Buffer for the generated pseudo-random key
 425  * @buf_len: Number of bytes of key to generate
 426  *
 427  * SHA1-based Pseudo-Random Function (PRF) (IEEE 802.11i, 8.5.1.1)
 428  *
 429  * This function is used to derive new, cryptographically separate keys from a
 430  * given key (e.g., PMK in IEEE 802.11i).
 431  */
 432 void sha1_prf(const uint8_t *key, size_t key_len, const char *label,
 433     const uint8_t *data, size_t data_len, uint8_t *buf, size_t buf_len)
 434 {
 435   uint8_t counter = 0;
 436   size_t pos, plen;
 437   uint8_t hash[SHA1_MAC_LEN];
 438   size_t label_len = strlen(label) + 1;
 439   const unsigned char *addr[3];
 440   size_t len[3];
 441
 442   addr[0] = (uint8_t *) label;
 443   len[0] = label_len;
 444   addr[1] = data;
 445   len[1] = data_len;
 446   addr[2] = &counter;
 447   len[2] = 1;
 448
 449   pos = 0;
 450   while (pos < buf_len) {
 451     plen = buf_len - pos;
 452     if (plen >= SHA1_MAC_LEN) {
 453       hmac_sha1_vector(key, key_len, 3, addr, len, &buf[pos]);
 454       pos += SHA1_MAC_LEN;
 455     } else {
 456       hmac_sha1_vector(key, key_len, 3, addr, len, hash);
 457       memcpy(&buf[pos], hash, plen);
 458       break;
 459     }
 460     counter++;
 461   }
 462 }
 463
 464 /**
 465  * sha1_vector:
 466  * @num_elem: Number of elements in the data vector
 467  * @addr: Pointers to the data areas
 468  * @len: Lengths of the data blocks
 469  * @mac: Buffer for the hash
 470  *
 471  * SHA-1 hash for data vector
 472  */
 473 void sha1_vector(size_t num_elem, const uint8_t *addr[], const size_t *len,
 474     uint8_t *mac)
 475 {
 476   SHA1_CTX ctx;
 477   size_t i;
 478
 479   SHA1Init(&ctx);
 480   for (i = 0; i < num_elem; i++)
 481     SHA1Update(&ctx, addr[i], len[i]);
 482   SHA1Final(mac, &ctx);
 483 }
 484