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 #include <string.h>
  17
  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
 266 /**
 267  * hmac_sha1_vector:
 268  * @key: Key for HMAC operations
 269  * @key_len: Length of the key in bytes
 270  * @num_elem: Number of elements in the data vector
 271  * @addr: Pointers to the data areas
 272  * @len: Lengths of the data blocks
 273  * @mac: Buffer for the hash (20 bytes)
 274  *
 275  * HMAC-SHA1 over data vector (RFC 2104)
 276  */
 277 void hmac_sha1_vector(const uint8_t *key, size_t key_len, size_t num_elem,
 278     const uint8_t *addr[], const size_t *len, uint8_t *mac)
 279 {
 280   unsigned char k_pad[64]; /* padding - key XORd with ipad/opad */
 281   unsigned char tk[20];
 282   const uint8_t *_addr[6];
 283   size_t _len[6], i;
 284
 285   if (num_elem > 5) {
 286     /*
 287      * Fixed limit on the number of fragments to avoid having to
 288      * allocate memory (which could fail).
 289      */
 290     return;
 291   }
 292
 293   /* if key is longer than 64 bytes reset it to key = SHA1(key) */
 294   if (key_len > 64) {
 295     sha1_vector(1, &key, &key_len, tk);
 296     key = tk;
 297     key_len = 20;
 298   }
 299
 300   /* the HMAC_SHA1 transform looks like:
 301    *
 302    * SHA1(K XOR opad, SHA1(K XOR ipad, text))
 303    *
 304    * where K is an n byte key
 305    * ipad is the byte 0x36 repeated 64 times
 306    * opad is the byte 0x5c repeated 64 times
 307    * and text is the data being protected */
 308
 309   /* start out by storing key in ipad */
 310   memset(k_pad, 0, sizeof(k_pad));
 311   memcpy(k_pad, key, key_len);
 312   /* XOR key with ipad values */
 313   for (i = 0; i < 64; i++)
 314     k_pad[i] ^= 0x36;
 315
 316   /* perform inner SHA1 */
 317   _addr[0] = k_pad;
 318   _len[0] = 64;
 319   for (i = 0; i < num_elem; i++) {
 320     _addr[i + 1] = addr[i];
 321     _len[i + 1] = len[i];
 322   }
 323   sha1_vector(1 + num_elem, _addr, _len, mac);
 324
 325   memset(k_pad, 0, sizeof(k_pad));
 326   memcpy(k_pad, key, key_len);
 327   /* XOR key with opad values */
 328   for (i = 0; i < 64; i++)
 329     k_pad[i] ^= 0x5c;
 330
 331   /* perform outer SHA1 */
 332   _addr[0] = k_pad;
 333   _len[0] = 64;
 334   _addr[1] = mac;
 335   _len[1] = SHA1_MAC_LEN;
 336   sha1_vector(2, _addr, _len, mac);
 337 }
 338
 339
 340 /**
 341  * hmac_sha1:
 342  * @key: Key for HMAC operations
 343  * @key_len: Length of the key in bytes
 344  * @data: Pointers to the data area
 345  * @data_len: Length of the data area
 346  * @mac: Buffer for the hash (20 bytes)
 347  *
 348  * HMAC-SHA1 over data buffer (RFC 2104)
 349  */
 350 void hmac_sha1(const uint8_t *key, size_t key_len,
 351     const uint8_t *data, size_t data_len, uint8_t *mac)
 352 {
 353   hmac_sha1_vector(key, key_len, 1, &data, &data_len, mac);
 354 }
 355
 356
 357 /**
 358  * sha1_prf:
 359  * @key: Key for PRF
 360  * @key_len: Length of the key in bytes
 361  * @label: A unique label for each purpose of the PRF
 362  * @data: Extra data to bind into the key
 363  * @data_len: Length of the data
 364  * @buf: Buffer for the generated pseudo-random key
 365  * @buf_len: Number of bytes of key to generate
 366  *
 367  * SHA1-based Pseudo-Random Function (PRF) (IEEE 802.11i, 8.5.1.1)
 368  *
 369  * This function is used to derive new, cryptographically separate keys from a
 370  * given key (e.g., PMK in IEEE 802.11i).
 371  */
 372 void sha1_prf(const uint8_t *key, size_t key_len, const char *label,
 373     const uint8_t *data, size_t data_len, uint8_t *buf, size_t buf_len)
 374 {
 375   uint8_t counter = 0;
 376   size_t pos, plen;
 377   uint8_t hash[SHA1_MAC_LEN];
 378   size_t label_len = strlen(label) + 1;
 379   const unsigned char *addr[3];
 380   size_t len[3];
 381
 382   addr[0] = (uint8_t *) label;
 383   len[0] = label_len;
 384   addr[1] = data;
 385   len[1] = data_len;
 386   addr[2] = &counter;
 387   len[2] = 1;
 388
 389   pos = 0;
 390   while (pos < buf_len) {
 391     plen = buf_len - pos;
 392     if (plen >= SHA1_MAC_LEN) {
 393       hmac_sha1_vector(key, key_len, 3, addr, len, &buf[pos]);
 394       pos += SHA1_MAC_LEN;
 395     } else {
 396       hmac_sha1_vector(key, key_len, 3, addr, len, hash);
 397       memcpy(&buf[pos], hash, plen);
 398       break;
 399     }
 400     counter++;
 401   }
 402 }
 403
 404 /**
 405  * sha1_vector:
 406  * @num_elem: Number of elements in the data vector
 407  * @addr: Pointers to the data areas
 408  * @len: Lengths of the data blocks
 409  * @mac: Buffer for the hash
 410  *
 411  * SHA-1 hash for data vector
 412  */
 413 void sha1_vector(size_t num_elem, const uint8_t *addr[], const size_t *len,
 414     uint8_t *mac)
 415 {
 416   SHA1_CTX ctx;
 417   size_t i;
 418
 419   SHA1Init(&ctx);
 420   for (i = 0; i < num_elem; i++)
 421     SHA1Update(&ctx, addr[i], len[i]);
 422   SHA1Final(mac, &ctx);
 423 }
 424