Home | History | Annotate | Download | only in crypto
      1 /*
      2  * MD5 hash implementation and interface functions
      3  * Copyright (c) 2003-2005, Jouni Malinen <j (at) 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 "includes.h"
     16 
     17 #include "common.h"
     18 #include "md5.h"
     19 #include "crypto.h"
     20 
     21 
     22 /**
     23  * hmac_md5_vector - HMAC-MD5 over data vector (RFC 2104)
     24  * @key: Key for HMAC operations
     25  * @key_len: Length of the key in bytes
     26  * @num_elem: Number of elements in the data vector
     27  * @addr: Pointers to the data areas
     28  * @len: Lengths of the data blocks
     29  * @mac: Buffer for the hash (16 bytes)
     30  */
     31 void hmac_md5_vector(const u8 *key, size_t key_len, size_t num_elem,
     32 		     const u8 *addr[], const size_t *len, u8 *mac)
     33 {
     34 	u8 k_pad[64]; /* padding - key XORd with ipad/opad */
     35 	u8 tk[16];
     36 	const u8 *_addr[6];
     37 	size_t i, _len[6];
     38 
     39 	if (num_elem > 5) {
     40 		/*
     41 		 * Fixed limit on the number of fragments to avoid having to
     42 		 * allocate memory (which could fail).
     43 		 */
     44 		return;
     45 	}
     46 
     47         /* if key is longer than 64 bytes reset it to key = MD5(key) */
     48         if (key_len > 64) {
     49 		md5_vector(1, &key, &key_len, tk);
     50 		key = tk;
     51 		key_len = 16;
     52         }
     53 
     54 	/* the HMAC_MD5 transform looks like:
     55 	 *
     56 	 * MD5(K XOR opad, MD5(K XOR ipad, text))
     57 	 *
     58 	 * where K is an n byte key
     59 	 * ipad is the byte 0x36 repeated 64 times
     60 	 * opad is the byte 0x5c repeated 64 times
     61 	 * and text is the data being protected */
     62 
     63 	/* start out by storing key in ipad */
     64 	os_memset(k_pad, 0, sizeof(k_pad));
     65 	os_memcpy(k_pad, key, key_len);
     66 
     67 	/* XOR key with ipad values */
     68 	for (i = 0; i < 64; i++)
     69 		k_pad[i] ^= 0x36;
     70 
     71 	/* perform inner MD5 */
     72 	_addr[0] = k_pad;
     73 	_len[0] = 64;
     74 	for (i = 0; i < num_elem; i++) {
     75 		_addr[i + 1] = addr[i];
     76 		_len[i + 1] = len[i];
     77 	}
     78 	md5_vector(1 + num_elem, _addr, _len, mac);
     79 
     80 	os_memset(k_pad, 0, sizeof(k_pad));
     81 	os_memcpy(k_pad, key, key_len);
     82 	/* XOR key with opad values */
     83 	for (i = 0; i < 64; i++)
     84 		k_pad[i] ^= 0x5c;
     85 
     86 	/* perform outer MD5 */
     87 	_addr[0] = k_pad;
     88 	_len[0] = 64;
     89 	_addr[1] = mac;
     90 	_len[1] = MD5_MAC_LEN;
     91 	md5_vector(2, _addr, _len, mac);
     92 }
     93 
     94 
     95 /**
     96  * hmac_md5 - HMAC-MD5 over data buffer (RFC 2104)
     97  * @key: Key for HMAC operations
     98  * @key_len: Length of the key in bytes
     99  * @data: Pointers to the data area
    100  * @data_len: Length of the data area
    101  * @mac: Buffer for the hash (16 bytes)
    102  */
    103 void hmac_md5(const u8 *key, size_t key_len, const u8 *data, size_t data_len,
    104 	      u8 *mac)
    105 {
    106 	hmac_md5_vector(key, key_len, 1, &data, &data_len, mac);
    107 }
    108 
    109 
    110 #ifdef INTERNAL_MD5
    111 
    112 struct MD5Context {
    113 	u32 buf[4];
    114 	u32 bits[2];
    115 	u8 in[64];
    116 };
    117 
    118 #ifndef CONFIG_CRYPTO_INTERNAL
    119 static void MD5Init(struct MD5Context *context);
    120 static void MD5Update(struct MD5Context *context, unsigned char const *buf,
    121 			  unsigned len);
    122 static void MD5Final(unsigned char digest[16], struct MD5Context *context);
    123 #endif /* CONFIG_CRYPTO_INTERNAL */
    124 static void MD5Transform(u32 buf[4], u32 const in[16]);
    125 
    126 
    127 typedef struct MD5Context MD5_CTX;
    128 
    129 
    130 /**
    131  * md5_vector - MD5 hash for data vector
    132  * @num_elem: Number of elements in the data vector
    133  * @addr: Pointers to the data areas
    134  * @len: Lengths of the data blocks
    135  * @mac: Buffer for the hash
    136  */
    137 void md5_vector(size_t num_elem, const u8 *addr[], const size_t *len, u8 *mac)
    138 {
    139 	MD5_CTX ctx;
    140 	size_t i;
    141 
    142 	MD5Init(&ctx);
    143 	for (i = 0; i < num_elem; i++)
    144 		MD5Update(&ctx, addr[i], len[i]);
    145 	MD5Final(mac, &ctx);
    146 }
    147 
    148 
    149 /* ===== start - public domain MD5 implementation ===== */
    150 /*
    151  * This code implements the MD5 message-digest algorithm.
    152  * The algorithm is due to Ron Rivest.  This code was
    153  * written by Colin Plumb in 1993, no copyright is claimed.
    154  * This code is in the public domain; do with it what you wish.
    155  *
    156  * Equivalent code is available from RSA Data Security, Inc.
    157  * This code has been tested against that, and is equivalent,
    158  * except that you don't need to include two pages of legalese
    159  * with every copy.
    160  *
    161  * To compute the message digest of a chunk of bytes, declare an
    162  * MD5Context structure, pass it to MD5Init, call MD5Update as
    163  * needed on buffers full of bytes, and then call MD5Final, which
    164  * will fill a supplied 16-byte array with the digest.
    165  */
    166 
    167 #ifndef WORDS_BIGENDIAN
    168 #define byteReverse(buf, len)	/* Nothing */
    169 #else
    170 /*
    171  * Note: this code is harmless on little-endian machines.
    172  */
    173 static void byteReverse(unsigned char *buf, unsigned longs)
    174 {
    175     u32 t;
    176     do {
    177 	t = (u32) ((unsigned) buf[3] << 8 | buf[2]) << 16 |
    178 	    ((unsigned) buf[1] << 8 | buf[0]);
    179 	*(u32 *) buf = t;
    180 	buf += 4;
    181     } while (--longs);
    182 }
    183 #endif
    184 
    185 /*
    186  * Start MD5 accumulation.  Set bit count to 0 and buffer to mysterious
    187  * initialization constants.
    188  */
    189 void MD5Init(struct MD5Context *ctx)
    190 {
    191     ctx->buf[0] = 0x67452301;
    192     ctx->buf[1] = 0xefcdab89;
    193     ctx->buf[2] = 0x98badcfe;
    194     ctx->buf[3] = 0x10325476;
    195 
    196     ctx->bits[0] = 0;
    197     ctx->bits[1] = 0;
    198 }
    199 
    200 /*
    201  * Update context to reflect the concatenation of another buffer full
    202  * of bytes.
    203  */
    204 void MD5Update(struct MD5Context *ctx, unsigned char const *buf, unsigned len)
    205 {
    206     u32 t;
    207 
    208     /* Update bitcount */
    209 
    210     t = ctx->bits[0];
    211     if ((ctx->bits[0] = t + ((u32) len << 3)) < t)
    212 	ctx->bits[1]++;		/* Carry from low to high */
    213     ctx->bits[1] += len >> 29;
    214 
    215     t = (t >> 3) & 0x3f;	/* Bytes already in shsInfo->data */
    216 
    217     /* Handle any leading odd-sized chunks */
    218 
    219     if (t) {
    220 	unsigned char *p = (unsigned char *) ctx->in + t;
    221 
    222 	t = 64 - t;
    223 	if (len < t) {
    224 	    os_memcpy(p, buf, len);
    225 	    return;
    226 	}
    227 	os_memcpy(p, buf, t);
    228 	byteReverse(ctx->in, 16);
    229 	MD5Transform(ctx->buf, (u32 *) ctx->in);
    230 	buf += t;
    231 	len -= t;
    232     }
    233     /* Process data in 64-byte chunks */
    234 
    235     while (len >= 64) {
    236 	os_memcpy(ctx->in, buf, 64);
    237 	byteReverse(ctx->in, 16);
    238 	MD5Transform(ctx->buf, (u32 *) ctx->in);
    239 	buf += 64;
    240 	len -= 64;
    241     }
    242 
    243     /* Handle any remaining bytes of data. */
    244 
    245     os_memcpy(ctx->in, buf, len);
    246 }
    247 
    248 /*
    249  * Final wrapup - pad to 64-byte boundary with the bit pattern
    250  * 1 0* (64-bit count of bits processed, MSB-first)
    251  */
    252 void MD5Final(unsigned char digest[16], struct MD5Context *ctx)
    253 {
    254     unsigned count;
    255     unsigned char *p;
    256 
    257     /* Compute number of bytes mod 64 */
    258     count = (ctx->bits[0] >> 3) & 0x3F;
    259 
    260     /* Set the first char of padding to 0x80.  This is safe since there is
    261        always at least one byte free */
    262     p = ctx->in + count;
    263     *p++ = 0x80;
    264 
    265     /* Bytes of padding needed to make 64 bytes */
    266     count = 64 - 1 - count;
    267 
    268     /* Pad out to 56 mod 64 */
    269     if (count < 8) {
    270 	/* Two lots of padding:  Pad the first block to 64 bytes */
    271 	os_memset(p, 0, count);
    272 	byteReverse(ctx->in, 16);
    273 	MD5Transform(ctx->buf, (u32 *) ctx->in);
    274 
    275 	/* Now fill the next block with 56 bytes */
    276 	os_memset(ctx->in, 0, 56);
    277     } else {
    278 	/* Pad block to 56 bytes */
    279 	os_memset(p, 0, count - 8);
    280     }
    281     byteReverse(ctx->in, 14);
    282 
    283     /* Append length in bits and transform */
    284     ((u32 *) ctx->in)[14] = ctx->bits[0];
    285     ((u32 *) ctx->in)[15] = ctx->bits[1];
    286 
    287     MD5Transform(ctx->buf, (u32 *) ctx->in);
    288     byteReverse((unsigned char *) ctx->buf, 4);
    289     os_memcpy(digest, ctx->buf, 16);
    290     os_memset(ctx, 0, sizeof(ctx));	/* In case it's sensitive */
    291 }
    292 
    293 /* The four core functions - F1 is optimized somewhat */
    294 
    295 /* #define F1(x, y, z) (x & y | ~x & z) */
    296 #define F1(x, y, z) (z ^ (x & (y ^ z)))
    297 #define F2(x, y, z) F1(z, x, y)
    298 #define F3(x, y, z) (x ^ y ^ z)
    299 #define F4(x, y, z) (y ^ (x | ~z))
    300 
    301 /* This is the central step in the MD5 algorithm. */
    302 #define MD5STEP(f, w, x, y, z, data, s) \
    303 	( w += f(x, y, z) + data,  w = w<<s | w>>(32-s),  w += x )
    304 
    305 /*
    306  * The core of the MD5 algorithm, this alters an existing MD5 hash to
    307  * reflect the addition of 16 longwords of new data.  MD5Update blocks
    308  * the data and converts bytes into longwords for this routine.
    309  */
    310 static void MD5Transform(u32 buf[4], u32 const in[16])
    311 {
    312     register u32 a, b, c, d;
    313 
    314     a = buf[0];
    315     b = buf[1];
    316     c = buf[2];
    317     d = buf[3];
    318 
    319     MD5STEP(F1, a, b, c, d, in[0] + 0xd76aa478, 7);
    320     MD5STEP(F1, d, a, b, c, in[1] + 0xe8c7b756, 12);
    321     MD5STEP(F1, c, d, a, b, in[2] + 0x242070db, 17);
    322     MD5STEP(F1, b, c, d, a, in[3] + 0xc1bdceee, 22);
    323     MD5STEP(F1, a, b, c, d, in[4] + 0xf57c0faf, 7);
    324     MD5STEP(F1, d, a, b, c, in[5] + 0x4787c62a, 12);
    325     MD5STEP(F1, c, d, a, b, in[6] + 0xa8304613, 17);
    326     MD5STEP(F1, b, c, d, a, in[7] + 0xfd469501, 22);
    327     MD5STEP(F1, a, b, c, d, in[8] + 0x698098d8, 7);
    328     MD5STEP(F1, d, a, b, c, in[9] + 0x8b44f7af, 12);
    329     MD5STEP(F1, c, d, a, b, in[10] + 0xffff5bb1, 17);
    330     MD5STEP(F1, b, c, d, a, in[11] + 0x895cd7be, 22);
    331     MD5STEP(F1, a, b, c, d, in[12] + 0x6b901122, 7);
    332     MD5STEP(F1, d, a, b, c, in[13] + 0xfd987193, 12);
    333     MD5STEP(F1, c, d, a, b, in[14] + 0xa679438e, 17);
    334     MD5STEP(F1, b, c, d, a, in[15] + 0x49b40821, 22);
    335 
    336     MD5STEP(F2, a, b, c, d, in[1] + 0xf61e2562, 5);
    337     MD5STEP(F2, d, a, b, c, in[6] + 0xc040b340, 9);
    338     MD5STEP(F2, c, d, a, b, in[11] + 0x265e5a51, 14);
    339     MD5STEP(F2, b, c, d, a, in[0] + 0xe9b6c7aa, 20);
    340     MD5STEP(F2, a, b, c, d, in[5] + 0xd62f105d, 5);
    341     MD5STEP(F2, d, a, b, c, in[10] + 0x02441453, 9);
    342     MD5STEP(F2, c, d, a, b, in[15] + 0xd8a1e681, 14);
    343     MD5STEP(F2, b, c, d, a, in[4] + 0xe7d3fbc8, 20);
    344     MD5STEP(F2, a, b, c, d, in[9] + 0x21e1cde6, 5);
    345     MD5STEP(F2, d, a, b, c, in[14] + 0xc33707d6, 9);
    346     MD5STEP(F2, c, d, a, b, in[3] + 0xf4d50d87, 14);
    347     MD5STEP(F2, b, c, d, a, in[8] + 0x455a14ed, 20);
    348     MD5STEP(F2, a, b, c, d, in[13] + 0xa9e3e905, 5);
    349     MD5STEP(F2, d, a, b, c, in[2] + 0xfcefa3f8, 9);
    350     MD5STEP(F2, c, d, a, b, in[7] + 0x676f02d9, 14);
    351     MD5STEP(F2, b, c, d, a, in[12] + 0x8d2a4c8a, 20);
    352 
    353     MD5STEP(F3, a, b, c, d, in[5] + 0xfffa3942, 4);
    354     MD5STEP(F3, d, a, b, c, in[8] + 0x8771f681, 11);
    355     MD5STEP(F3, c, d, a, b, in[11] + 0x6d9d6122, 16);
    356     MD5STEP(F3, b, c, d, a, in[14] + 0xfde5380c, 23);
    357     MD5STEP(F3, a, b, c, d, in[1] + 0xa4beea44, 4);
    358     MD5STEP(F3, d, a, b, c, in[4] + 0x4bdecfa9, 11);
    359     MD5STEP(F3, c, d, a, b, in[7] + 0xf6bb4b60, 16);
    360     MD5STEP(F3, b, c, d, a, in[10] + 0xbebfbc70, 23);
    361     MD5STEP(F3, a, b, c, d, in[13] + 0x289b7ec6, 4);
    362     MD5STEP(F3, d, a, b, c, in[0] + 0xeaa127fa, 11);
    363     MD5STEP(F3, c, d, a, b, in[3] + 0xd4ef3085, 16);
    364     MD5STEP(F3, b, c, d, a, in[6] + 0x04881d05, 23);
    365     MD5STEP(F3, a, b, c, d, in[9] + 0xd9d4d039, 4);
    366     MD5STEP(F3, d, a, b, c, in[12] + 0xe6db99e5, 11);
    367     MD5STEP(F3, c, d, a, b, in[15] + 0x1fa27cf8, 16);
    368     MD5STEP(F3, b, c, d, a, in[2] + 0xc4ac5665, 23);
    369 
    370     MD5STEP(F4, a, b, c, d, in[0] + 0xf4292244, 6);
    371     MD5STEP(F4, d, a, b, c, in[7] + 0x432aff97, 10);
    372     MD5STEP(F4, c, d, a, b, in[14] + 0xab9423a7, 15);
    373     MD5STEP(F4, b, c, d, a, in[5] + 0xfc93a039, 21);
    374     MD5STEP(F4, a, b, c, d, in[12] + 0x655b59c3, 6);
    375     MD5STEP(F4, d, a, b, c, in[3] + 0x8f0ccc92, 10);
    376     MD5STEP(F4, c, d, a, b, in[10] + 0xffeff47d, 15);
    377     MD5STEP(F4, b, c, d, a, in[1] + 0x85845dd1, 21);
    378     MD5STEP(F4, a, b, c, d, in[8] + 0x6fa87e4f, 6);
    379     MD5STEP(F4, d, a, b, c, in[15] + 0xfe2ce6e0, 10);
    380     MD5STEP(F4, c, d, a, b, in[6] + 0xa3014314, 15);
    381     MD5STEP(F4, b, c, d, a, in[13] + 0x4e0811a1, 21);
    382     MD5STEP(F4, a, b, c, d, in[4] + 0xf7537e82, 6);
    383     MD5STEP(F4, d, a, b, c, in[11] + 0xbd3af235, 10);
    384     MD5STEP(F4, c, d, a, b, in[2] + 0x2ad7d2bb, 15);
    385     MD5STEP(F4, b, c, d, a, in[9] + 0xeb86d391, 21);
    386 
    387     buf[0] += a;
    388     buf[1] += b;
    389     buf[2] += c;
    390     buf[3] += d;
    391 }
    392 /* ===== end - public domain MD5 implementation ===== */
    393 
    394 #endif /* INTERNAL_MD5 */
    395