1/* MD5C.C - RSA Data Security, Inc., MD5 message-digest algorithm
2 */
3
4/* Function names changed to avoid namespace collisions: Rob Siemborski */
5
6/* Copyright (C) 1991-2, RSA Data Security, Inc. Created 1991. All
7rights reserved.
8
9License to copy and use this software is granted provided that it
10is identified as the "RSA Data Security, Inc. MD5 Message-Digest
11Algorithm" in all material mentioning or referencing this software
12or this function.
13
14License is also granted to make and use derivative works provided
15that such works are identified as "derived from the RSA Data
16Security, Inc. MD5 Message-Digest Algorithm" in all material
17mentioning or referencing the derived work.
18
19RSA Data Security, Inc. makes no representations concerning either
20the merchantability of this software or the suitability of this
21software for any particular purpose. It is provided "as is"
22without express or implied warranty of any kind.
23
24These notices must be retained in any copies of any part of this
25documentation and/or software.
26*/
27
28#include <config.h>
29#include "md5global.h"
30#include "md5.h"
31#include "hmac-md5.h"
32
33#ifndef WIN32
34# include <arpa/inet.h>
35#endif
36
37/* Constants for MD5Transform routine.
38*/
39
40#define S11 7
41#define S12 12
42#define S13 17
43#define S14 22
44#define S21 5
45#define S22 9
46#define S23 14
47#define S24 20
48#define S31 4
49#define S32 11
50#define S33 16
51#define S34 23
52#define S41 6
53#define S42 10
54#define S43 15
55#define S44 21
56
57static void MD5Transform PROTO_LIST ((UINT4 [4], const unsigned char [64]));
58static void Encode PROTO_LIST
59       ((unsigned char *, UINT4 *, unsigned int));
60static void Decode PROTO_LIST
61       ((UINT4 *, const unsigned char *, unsigned int));
62static void MD5_memcpy PROTO_LIST ((POINTER, const POINTER, unsigned int));
63static void MD5_memset PROTO_LIST ((POINTER, int, unsigned int));
64
65static unsigned char PADDING[64] = {
66       0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
67       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
68};
69
70/* F, G, H and I are basic MD5 functions.
71
72        */
73#ifdef I
74/* This might be defined via NANA */
75#undef I
76#endif
77
78#define F(x, y, z) (((x) & (y)) | ((~x) & (z)))
79#define G(x, y, z) (((x) & (z)) | ((y) & (~z)))
80#define H(x, y, z) ((x) ^ (y) ^ (z))
81#define I(x, y, z) ((y) ^ ((x) | (~z)))
82
83/* ROTATE_LEFT rotates x left n bits.
84
85        */
86
87#define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n))))
88
89/* FF, GG, HH, and II transformations for rounds 1, 2, 3, and 4.
90Rotation is separate from addition to prevent recomputation.
91*/
92
93#define FF(a, b, c, d, x, s, ac) { (a) += F ((b), (c), (d)) + (x) + (UINT4)(ac); (a) = ROTATE_LEFT ((a), (s));        (a) += (b);        }
94#define GG(a, b, c, d, x, s, ac) {        (a) += G ((b), (c), (d)) + (x) + (UINT4)(ac);        (a) = ROTATE_LEFT ((a), (s));        (a) += (b);         }
95#define HH(a, b, c, d, x, s, ac) {        (a) += H ((b), (c), (d)) + (x) + (UINT4)(ac);        (a) = ROTATE_LEFT ((a), (s));        (a) += (b);        }
96#define II(a, b, c, d, x, s, ac) {        (a) += I ((b), (c), (d)) + (x) + (UINT4)(ac);        (a) = ROTATE_LEFT ((a), (s));        (a) += (b);        }
97
98/* MD5 initialization. Begins an MD5 operation, writing a new context.
99*/
100
101void _sasl_MD5Init (context)
102MD5_CTX *context; /* context */
103{
104       context->count[0] = context->count[1] = 0;
105
106       /* Load magic initialization constants. */
107       context->state[0] = 0x67452301;
108       context->state[1] = 0xefcdab89;
109       context->state[2] = 0x98badcfe;
110       context->state[3] = 0x10325476;
111}
112
113/* MD5 block update operation. Continues an MD5 message-digest
114       operation, processing another message block, and updating the context.
115*/
116
117void _sasl_MD5Update (context, input, inputLen)
118MD5_CTX *context; /* context */
119const unsigned char *input; /* input block */
120unsigned int inputLen; /* length of input block */
121{
122       unsigned int i, index, partLen;
123
124         /* Compute number of bytes mod 64 */
125         index = (unsigned int)((context->count[0] >> 3) & 0x3F);
126
127         /* Update number of bits */
128         if ((context->count[0] += ((UINT4)inputLen << 3))
129          < ((UINT4)inputLen << 3))
130        context->count[1]++;
131         context->count[1] += ((UINT4)inputLen >> 29);
132
133       partLen = 64 - index;
134
135         /* Transform as many times as possible.
136
137*/
138		if (inputLen >= partLen) {
139			MD5_memcpy((POINTER)&context->buffer[index], input, partLen);
140			MD5Transform(context->state, context->buffer);
141
142			for (i = partLen; i + 63 < inputLen; i += 64)
143			MD5Transform (context->state, &input[i]);
144
145			index = 0;
146		}
147		else
148			i = 0;
149
150		/* Buffer remaining input */
151		MD5_memcpy((POINTER)&context->buffer[index], (POINTER)&input[i], inputLen-i);
152}
153
154/* MD5 finalization. Ends an MD5 message-digest operation, writing the
155       the message digest and zeroizing the context.
156*/
157
158void _sasl_MD5Final (digest, context)
159unsigned char digest[16]; /* message digest */
160MD5_CTX *context; /* context */
161{
162       unsigned char bits[8];
163       unsigned int index, padLen;
164
165         /* Save number of bits */
166         Encode (bits, context->count, 8);
167
168         /* Pad out to 56 mod 64. */
169	 index = (unsigned int)((context->count[0] >> 3) & 0x3f);
170	 padLen = (index < 56) ? (56 - index) : (120 - index);
171	 _sasl_MD5Update (context, PADDING, padLen);
172
173         /* Append length (before padding) */
174         _sasl_MD5Update (context, bits, 8);
175
176         /* Store state in digest */
177         Encode (digest, context->state, 16);
178
179         /* Zeroize sensitive information. */
180       MD5_memset ((POINTER)context, 0, sizeof (*context));
181}
182
183/* MD5 basic transformation. Transforms state based on block. */
184
185static void MD5Transform (state, block)
186UINT4 state[4];
187const unsigned char block[64];
188{
189       UINT4 a = state[0], b = state[1], c = state[2], d = state[3], x[16];
190
191       Decode (x, block, 64);
192
193         /* Round 1 */
194         FF (a, b, c, d, x[ 0], S11, 0xd76aa478); /* 1 */
195         FF (d, a, b, c, x[ 1], S12, 0xe8c7b756); /* 2 */
196         FF (c, d, a, b, x[ 2], S13, 0x242070db); /* 3 */
197         FF (b, c, d, a, x[ 3], S14, 0xc1bdceee); /* 4 */
198         FF (a, b, c, d, x[ 4], S11, 0xf57c0faf); /* 5 */
199         FF (d, a, b, c, x[ 5], S12, 0x4787c62a); /* 6 */
200         FF (c, d, a, b, x[ 6], S13, 0xa8304613); /* 7 */
201         FF (b, c, d, a, x[ 7], S14, 0xfd469501); /* 8 */
202         FF (a, b, c, d, x[ 8], S11, 0x698098d8); /* 9 */
203         FF (d, a, b, c, x[ 9], S12, 0x8b44f7af); /* 10 */
204         FF (c, d, a, b, x[10], S13, 0xffff5bb1); /* 11 */
205         FF (b, c, d, a, x[11], S14, 0x895cd7be); /* 12 */
206         FF (a, b, c, d, x[12], S11, 0x6b901122); /* 13 */
207         FF (d, a, b, c, x[13], S12, 0xfd987193); /* 14 */
208         FF (c, d, a, b, x[14], S13, 0xa679438e); /* 15 */
209         FF (b, c, d, a, x[15], S14, 0x49b40821); /* 16 */
210
211        /* Round 2 */
212         GG (a, b, c, d, x[ 1], S21, 0xf61e2562); /* 17 */
213         GG (d, a, b, c, x[ 6], S22, 0xc040b340); /* 18 */
214         GG (c, d, a, b, x[11], S23, 0x265e5a51); /* 19 */
215         GG (b, c, d, a, x[ 0], S24, 0xe9b6c7aa); /* 20 */
216         GG (a, b, c, d, x[ 5], S21, 0xd62f105d); /* 21 */
217         GG (d, a, b, c, x[10], S22,  0x2441453); /* 22 */
218         GG (c, d, a, b, x[15], S23, 0xd8a1e681); /* 23 */
219         GG (b, c, d, a, x[ 4], S24, 0xe7d3fbc8); /* 24 */
220         GG (a, b, c, d, x[ 9], S21, 0x21e1cde6); /* 25 */
221         GG (d, a, b, c, x[14], S22, 0xc33707d6); /* 26 */
222         GG (c, d, a, b, x[ 3], S23, 0xf4d50d87); /* 27 */
223	 GG (b, c, d, a, x[ 8], S24, 0x455a14ed); /* 28 */
224	 GG (a, b, c, d, x[13], S21, 0xa9e3e905); /* 29 */
225	 GG (d, a, b, c, x[ 2], S22, 0xfcefa3f8); /* 30 */
226	 GG (c, d, a, b, x[ 7], S23, 0x676f02d9); /* 31 */
227	 GG (b, c, d, a, x[12], S24, 0x8d2a4c8a); /* 32 */
228
229         /* Round 3 */
230         HH (a, b, c, d, x[ 5], S31, 0xfffa3942); /* 33 */
231         HH (d, a, b, c, x[ 8], S32, 0x8771f681); /* 34 */
232         HH (c, d, a, b, x[11], S33, 0x6d9d6122); /* 35 */
233         HH (b, c, d, a, x[14], S34, 0xfde5380c); /* 36 */
234         HH (a, b, c, d, x[ 1], S31, 0xa4beea44); /* 37 */
235         HH (d, a, b, c, x[ 4], S32, 0x4bdecfa9); /* 38 */
236         HH (c, d, a, b, x[ 7], S33, 0xf6bb4b60); /* 39 */
237         HH (b, c, d, a, x[10], S34, 0xbebfbc70); /* 40 */
238         HH (a, b, c, d, x[13], S31, 0x289b7ec6); /* 41 */
239         HH (d, a, b, c, x[ 0], S32, 0xeaa127fa); /* 42 */
240         HH (c, d, a, b, x[ 3], S33, 0xd4ef3085); /* 43 */
241         HH (b, c, d, a, x[ 6], S34,  0x4881d05); /* 44 */
242         HH (a, b, c, d, x[ 9], S31, 0xd9d4d039); /* 45 */
243         HH (d, a, b, c, x[12], S32, 0xe6db99e5); /* 46 */
244         HH (c, d, a, b, x[15], S33, 0x1fa27cf8); /* 47 */
245         HH (b, c, d, a, x[ 2], S34, 0xc4ac5665); /* 48 */
246
247         /* Round 4 */
248         II (a, b, c, d, x[ 0], S41, 0xf4292244); /* 49 */
249         II (d, a, b, c, x[ 7], S42, 0x432aff97); /* 50 */
250         II (c, d, a, b, x[14], S43, 0xab9423a7); /* 51 */
251         II (b, c, d, a, x[ 5], S44, 0xfc93a039); /* 52 */
252         II (a, b, c, d, x[12], S41, 0x655b59c3); /* 53 */
253         II (d, a, b, c, x[ 3], S42, 0x8f0ccc92); /* 54 */
254         II (c, d, a, b, x[10], S43, 0xffeff47d); /* 55 */
255         II (b, c, d, a, x[ 1], S44, 0x85845dd1); /* 56 */
256         II (a, b, c, d, x[ 8], S41, 0x6fa87e4f); /* 57 */
257         II (d, a, b, c, x[15], S42, 0xfe2ce6e0); /* 58 */
258         II (c, d, a, b, x[ 6], S43, 0xa3014314); /* 59 */
259         II (b, c, d, a, x[13], S44, 0x4e0811a1); /* 60 */
260         II (a, b, c, d, x[ 4], S41, 0xf7537e82); /* 61 */
261         II (d, a, b, c, x[11], S42, 0xbd3af235); /* 62 */
262         II (c, d, a, b, x[ 2], S43, 0x2ad7d2bb); /* 63 */
263         II (b, c, d, a, x[ 9], S44, 0xeb86d391); /* 64 */
264
265       state[0] += a;
266       state[1] += b;
267       state[2] += c;
268       state[3] += d;
269
270         /* Zeroize sensitive information.
271	 */
272       MD5_memset ((POINTER)x, 0, sizeof (x));
273}
274
275/* Encodes input (UINT4) into output (unsigned char). Assumes len is
276       a multiple of 4.
277
278        */
279
280static void Encode (output, input, len)
281unsigned char *output;
282UINT4 *input;
283unsigned int len;
284{
285       unsigned int i, j;
286
287       for (i = 0, j = 0; j < len; i++, j += 4) {
288       output[j] = (unsigned char)(input[i] & 0xff);
289       output[j+1] = (unsigned char)((input[i] >> 8) & 0xff);
290       output[j+2] = (unsigned char)((input[i] >> 16) & 0xff);
291       output[j+3] = (unsigned char)((input[i] >> 24) & 0xff);
292       }
293}
294
295/* Decodes input (unsigned char) into output (UINT4). Assumes len is
296       a multiple of 4.
297
298        */
299
300static void Decode (output, input, len)
301UINT4 *output;
302const unsigned char *input;
303unsigned int len;
304{
305       unsigned int i, j;
306
307       for (i = 0, j = 0; j < len; i++, j += 4)
308       output[i] = ((UINT4)input[j]) | (((UINT4)input[j+1]) << 8) | (((UINT4)input[j+2]) << 16)
309       | (((UINT4)input[j+3]) << 24);
310}
311
312/* Note: Replace "for loop" with standard memcpy if possible.
313
314        */
315
316static void MD5_memcpy(POINTER output, const POINTER input, unsigned int len)
317{
318       unsigned int i;
319
320       for (i = 0; i < len; i++)
321	      output[i] = input[i];
322}
323
324/* Note: Replace "for loop" with standard memset if possible.
325*/
326
327static void MD5_memset (output, value, len)
328POINTER output;
329int value;
330unsigned int len;
331{
332       unsigned int i;
333
334       for (i = 0; i < len; i++)
335       ((char *)output)[i] = (char)value;
336}
337
338void _sasl_hmac_md5_init(HMAC_MD5_CTX *hmac,
339			 const unsigned char *key,
340			 int key_len)
341{
342  unsigned char k_ipad[65];    /* inner padding -
343				* key XORd with ipad
344				*/
345  unsigned char k_opad[65];    /* outer padding -
346				* key XORd with opad
347				*/
348  unsigned char tk[16];
349  int i;
350  /* if key is longer than 64 bytes reset it to key=MD5(key) */
351  if (key_len > 64) {
352
353    MD5_CTX      tctx;
354
355    _sasl_MD5Init(&tctx);
356    _sasl_MD5Update(&tctx, key, key_len);
357    _sasl_MD5Final(tk, &tctx);
358
359    key = tk;
360    key_len = 16;
361  }
362
363  /*
364   * the HMAC_MD5 transform looks like:
365   *
366   * MD5(K XOR opad, MD5(K XOR ipad, text))
367   *
368   * where K is an n byte key
369   * ipad is the byte 0x36 repeated 64 times
370   * opad is the byte 0x5c repeated 64 times
371   * and text is the data being protected
372   */
373
374  /* start out by storing key in pads */
375  MD5_memset((POINTER)k_ipad, '\0', sizeof k_ipad);
376  MD5_memset((POINTER)k_opad, '\0', sizeof k_opad);
377  MD5_memcpy( k_ipad, (POINTER)key, key_len);
378  MD5_memcpy( k_opad, (POINTER)key, key_len);
379
380  /* XOR key with ipad and opad values */
381  for (i=0; i<64; i++) {
382    k_ipad[i] ^= 0x36;
383    k_opad[i] ^= 0x5c;
384  }
385
386  _sasl_MD5Init(&hmac->ictx);                   /* init inner context */
387  _sasl_MD5Update(&hmac->ictx, k_ipad, 64);     /* apply inner pad */
388
389  _sasl_MD5Init(&hmac->octx);                   /* init outer context */
390  _sasl_MD5Update(&hmac->octx, k_opad, 64);     /* apply outer pad */
391
392  /* scrub the pads and key context (if used) */
393  MD5_memset((POINTER)&k_ipad, 0, sizeof(k_ipad));
394  MD5_memset((POINTER)&k_opad, 0, sizeof(k_opad));
395  MD5_memset((POINTER)&tk, 0, sizeof(tk));
396
397  /* and we're done. */
398}
399
400/* The precalc and import routines here rely on the fact that we pad
401 * the key out to 64 bytes and use that to initialize the md5
402 * contexts, and that updating an md5 context with 64 bytes of data
403 * leaves nothing left over; all of the interesting state is contained
404 * in the state field, and none of it is left over in the count and
405 * buffer fields.  So all we have to do is save the state field; we
406 * can zero the others when we reload it.  Which is why the decision
407 * was made to pad the key out to 64 bytes in the first place. */
408void _sasl_hmac_md5_precalc(HMAC_MD5_STATE *state,
409			    const unsigned char *key,
410			    int key_len)
411{
412  HMAC_MD5_CTX hmac;
413  unsigned lupe;
414
415  _sasl_hmac_md5_init(&hmac, key, key_len);
416  for (lupe = 0; lupe < 4; lupe++) {
417    state->istate[lupe] = htonl(hmac.ictx.state[lupe]);
418    state->ostate[lupe] = htonl(hmac.octx.state[lupe]);
419  }
420  MD5_memset((POINTER)&hmac, 0, sizeof(hmac));
421}
422
423
424void _sasl_hmac_md5_import(HMAC_MD5_CTX *hmac,
425		     HMAC_MD5_STATE *state)
426{
427  unsigned lupe;
428  MD5_memset((POINTER)hmac, 0, sizeof(HMAC_MD5_CTX));
429  for (lupe = 0; lupe < 4; lupe++) {
430    hmac->ictx.state[lupe] = ntohl(state->istate[lupe]);
431    hmac->octx.state[lupe] = ntohl(state->ostate[lupe]);
432  }
433  /* Init the counts to account for our having applied
434   * 64 bytes of key; this works out to 0x200 (64 << 3; see
435   * MD5Update above...) */
436  hmac->ictx.count[0] = hmac->octx.count[0] = 0x200;
437}
438
439void _sasl_hmac_md5_final(unsigned char digest[HMAC_MD5_SIZE],
440			  HMAC_MD5_CTX *hmac)
441{
442  _sasl_MD5Final(digest, &hmac->ictx);  /* Finalize inner md5 */
443  _sasl_MD5Update(&hmac->octx, digest, 16); /* Update outer ctx */
444  _sasl_MD5Final(digest, &hmac->octx); /* Finalize outer md5 */
445}
446
447
448void _sasl_hmac_md5(text, text_len, key, key_len, digest)
449const unsigned char* text; /* pointer to data stream */
450int text_len; /* length of data stream */
451const unsigned char* key; /* pointer to authentication key */
452int key_len; /* length of authentication key */
453unsigned char *digest; /* caller digest to be filled in */
454{
455  MD5_CTX context;
456
457  unsigned char k_ipad[65];    /* inner padding -
458				* key XORd with ipad
459				*/
460  unsigned char k_opad[65];    /* outer padding -
461				* key XORd with opad
462				*/
463  unsigned char tk[16];
464  int i;
465  /* if key is longer than 64 bytes reset it to key=MD5(key) */
466  if (key_len > 64) {
467
468    MD5_CTX      tctx;
469
470    _sasl_MD5Init(&tctx);
471    _sasl_MD5Update(&tctx, key, key_len);
472    _sasl_MD5Final(tk, &tctx);
473
474    key = tk;
475    key_len = 16;
476  }
477
478  /*
479   * the HMAC_MD5 transform looks like:
480   *
481   * MD5(K XOR opad, MD5(K XOR ipad, text))
482   *
483   * where K is an n byte key
484   * ipad is the byte 0x36 repeated 64 times
485   * opad is the byte 0x5c repeated 64 times
486   * and text is the data being protected
487   */
488
489  /* start out by storing key in pads */
490  MD5_memset(k_ipad, '\0', sizeof k_ipad);
491  MD5_memset(k_opad, '\0', sizeof k_opad);
492  MD5_memcpy( k_ipad, (POINTER)key, key_len);
493  MD5_memcpy( k_opad, (POINTER)key, key_len);
494
495  /* XOR key with ipad and opad values */
496  for (i=0; i<64; i++) {
497    k_ipad[i] ^= 0x36;
498    k_opad[i] ^= 0x5c;
499  }
500  /*
501   * perform inner MD5
502   */
503
504  _sasl_MD5Init(&context);                   /* init context for 1st
505					       * pass */
506  _sasl_MD5Update(&context, k_ipad, 64);      /* start with inner pad */
507  _sasl_MD5Update(&context, text, text_len); /* then text of datagram */
508  _sasl_MD5Final(digest, &context);          /* finish up 1st pass */
509
510  /*
511   * perform outer MD5
512   */
513  _sasl_MD5Init(&context);                   /* init context for 2nd
514					* pass */
515  _sasl_MD5Update(&context, k_opad, 64);     /* start with outer pad */
516  _sasl_MD5Update(&context, digest, 16);     /* then results of 1st
517					* hash */
518  _sasl_MD5Final(digest, &context);          /* finish up 2nd pass */
519
520}
521