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