md5.c

   1 /*
   2  * Heirloom mailx - a mail user agent derived from Berkeley Mail.
   3  *
   4  * Copyright (c) 2000-2004 Gunnar Ritter, Freiburg i. Br., Germany.
   5  */
   6 /*
   7  * Derived from RFC 1321:
   8  */
   9 /* MD5C.C - RSA Data Security, Inc., MD5 message-digest algorithm
  10  */
  11
  12 /* Copyright (C) 1991-2, RSA Data Security, Inc. Created 1991. All
  13 rights reserved.
  14
  15 License to copy and use this software is granted provided that it
  16 is identified as the "RSA Data Security, Inc. MD5 Message-Digest
  17 Algorithm" in all material mentioning or referencing this software
  18 or this function.
  19
  20 License is also granted to make and use derivative works provided
  21 that such works are identified as "derived from the RSA Data
  22 Security, Inc. MD5 Message-Digest Algorithm" in all material
  23 mentioning or referencing the derived work.
  24
  25 RSA Data Security, Inc. makes no representations concerning either
  26 the merchantability of this software or the suitability of this
  27 software for any particular purpose. It is provided "as is"
  28 without express or implied warranty of any kind.
  29
  30 These notices must be retained in any copies of any part of this
  31 documentation and/or software.
  32  */
  33
  34 /*      Sccsid @(#)md5.c        1.8 (gritter) 3/4/06    */
  35
  36 #include "rcv.h"
  37 #include "md5.h"
  38
  39 /*
  40  * Constants for MD5Transform routine.
  41  */
  42 #define S11 7
  43 #define S12 12
  44 #define S13 17
  45 #define S14 22
  46 #define S21 5
  47 #define S22 9
  48 #define S23 14
  49 #define S24 20
  50 #define S31 4
  51 #define S32 11
  52 #define S33 16
  53 #define S34 23
  54 #define S41 6
  55 #define S42 10
  56 #define S43 15
  57 #define S44 21
  58
  59 static void MD5Transform(md5_type state[], unsigned char block[]);
  60 static void Encode(unsigned char *output, md5_type *input, unsigned int len);
  61 static void Decode(md5_type *output, unsigned char *input, unsigned int len);
  62
  63 static unsigned char PADDING[64] = {
  64   0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  65   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  66   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
  67 };
  68
  69 /*
  70  * F, G, H and I are basic MD5 functions.
  71  */
  72 #define F(x, y, z)      ((x) & (y) | ~(x) & (z))
  73 #define G(x, y, z)      ((x) & (z) | (y) & ~(z))
  74 #define H(x, y, z)      ((x) ^ (y) ^ (z))
  75 #define I(x, y, z)      ((y) ^ ((x) | ~(z)&0xffffffff))
  76
  77 /*
  78  * ROTATE_LEFT rotates x left n bits.
  79  */
  80 #define ROTATE_LEFT(x, n)       ((x)<<(n) & 0xffffffff | (x) >> 32-(n))
  81
  82 /*
  83  * FF, GG, HH, and II transformations for rounds 1, 2, 3, and 4.
  84  * Rotation is separate from addition to prevent recomputation.
  85  */
  86 #define FF(a, b, c, d, x, s, ac) { \
  87         (a) = (a) + F((b), (c), (d)) + (x) + ((ac)&0xffffffff) & 0xffffffff; \
  88         (a) = ROTATE_LEFT((a), (s)); \
  89         (a) = (a) + (b) & 0xffffffff; \
  90 }
  91
  92 #define GG(a, b, c, d, x, s, ac) { \
  93         (a) = (a) + G((b), (c), (d)) + (x) + ((ac)&0xffffffff) & 0xffffffff; \
  94         (a) = ROTATE_LEFT((a), (s)); \
  95         (a) = (a) + (b) & 0xffffffff; \
  96 }
  97
  98 #define HH(a, b, c, d, x, s, ac) { \
  99         (a) = (a) + H((b), (c), (d)) + (x) + ((ac)&0xffffffff) & 0xffffffff; \
 100         (a) = ROTATE_LEFT((a), (s)); \
 101         (a) = (a) + (b) & 0xffffffff; \
 102 }
 103
 104 #define II(a, b, c, d, x, s, ac) { \
 105         (a) = (a) + I((b), (c), (d)) + (x) + ((ac)&0xffffffff) & 0xffffffff; \
 106         (a) = ROTATE_LEFT((a), (s)); \
 107         (a) = (a) + (b) & 0xffffffff; \
 108 }
 109
 110 /*
 111  * MD5 initialization. Begins an MD5 operation, writing a new context.
 112  */
 113 void
 114 MD5Init (
 115     MD5_CTX *context    /* context */
 116 )
 117 {
 118         context->count[0] = context->count[1] = 0;
 119         /*
 120          * Load magic initialization constants.
 121          */
 122         context->state[0] = 0x67452301;
 123         context->state[1] = 0xefcdab89;
 124         context->state[2] = 0x98badcfe;
 125         context->state[3] = 0x10325476;
 126 }
 127
 128 /*
 129  * MD5 block update operation. Continues an MD5 message-digest
 130  * operation, processing another message block, and updating the
 131  * context.
 132  */
 133 void
 134 MD5Update (
 135     MD5_CTX *context,           /* context */
 136     unsigned char *input,               /* input block */
 137     unsigned int inputLen               /* length of input block */
 138 )
 139 {
 140         unsigned int i, index, partLen;
 141
 142         /* Compute number of bytes mod 64 */
 143         index = context->count[0]>>3 & 0x3F;
 144
 145         /* Update number of bits */
 146         if ((context->count[0] = context->count[0] + (inputLen<<3) & 0xffffffff)
 147                         < (inputLen<<3 & 0xffffffff))
 148         context->count[1] = context->count[1] + 1 & 0xffffffff;
 149         context->count[1] = context->count[1] + (inputLen>>29) & 0xffffffff;
 150
 151         partLen = 64 - index;
 152
 153         /*
 154          * Transform as many times as possible.
 155          */
 156         if (inputLen >= partLen) {
 157                 memcpy(&context->buffer[index], input, partLen);
 158                 MD5Transform(context->state, context->buffer);
 159
 160                 for (i = partLen; i + 63 < inputLen; i += 64)
 161                         MD5Transform(context->state, &input[i]);
 162
 163                 index = 0;
 164         } else
 165                 i = 0;
 166
 167         /* Buffer remaining input */
 168         memcpy(&context->buffer[index], &input[i], inputLen-i);
 169 }
 170
 171 /*
 172  * MD5 finalization. Ends an MD5 message-digest operation, writing the
 173  * the message digest and zeroizing the context.
 174  */
 175 void
 176 MD5Final (
 177     unsigned char digest[16],   /* message digest */
 178     MD5_CTX *context            /* context */
 179 )
 180 {
 181         unsigned char   bits[8];
 182         unsigned int    index, padLen;
 183
 184         /* Save number of bits */
 185         Encode(bits, context->count, 8);
 186
 187         /*
 188          * Pad out to 56 mod 64.
 189          */
 190         index = context->count[0]>>3 & 0x3f;
 191         padLen = index < 56 ? 56 - index : 120 - index;
 192         MD5Update(context, PADDING, padLen);
 193
 194         /* Append length (before padding) */
 195         MD5Update(context, bits, 8);
 196         /* Store state in digest */
 197         Encode(digest, context->state, 16);
 198
 199         /*
 200          * Zeroize sensitive information.
 201          */
 202         memset(context, 0, sizeof *context);
 203 }
 204
 205 /* MD5 basic transformation. Transforms state based on block.
 206  */
 207 static void
 208 MD5Transform(md5_type state[4], unsigned char block[64])
 209 {
 210         md5_type        a = state[0], b = state[1], c = state[2], d = state[3],
 211                                 x[16];
 212
 213         Decode(x, block, 64);
 214
 215         /* Round 1 */
 216         FF(a, b, c, d, x[ 0], S11, 0xd76aa478); /* 1 */
 217         FF(d, a, b, c, x[ 1], S12, 0xe8c7b756); /* 2 */
 218         FF(c, d, a, b, x[ 2], S13, 0x242070db); /* 3 */
 219         FF(b, c, d, a, x[ 3], S14, 0xc1bdceee); /* 4 */
 220         FF(a, b, c, d, x[ 4], S11, 0xf57c0faf); /* 5 */
 221         FF(d, a, b, c, x[ 5], S12, 0x4787c62a); /* 6 */
 222         FF(c, d, a, b, x[ 6], S13, 0xa8304613); /* 7 */
 223         FF(b, c, d, a, x[ 7], S14, 0xfd469501); /* 8 */
 224         FF(a, b, c, d, x[ 8], S11, 0x698098d8); /* 9 */
 225         FF(d, a, b, c, x[ 9], S12, 0x8b44f7af); /* 10 */
 226         FF(c, d, a, b, x[10], S13, 0xffff5bb1); /* 11 */
 227         FF(b, c, d, a, x[11], S14, 0x895cd7be); /* 12 */
 228         FF(a, b, c, d, x[12], S11, 0x6b901122); /* 13 */
 229         FF(d, a, b, c, x[13], S12, 0xfd987193); /* 14 */
 230         FF(c, d, a, b, x[14], S13, 0xa679438e); /* 15 */
 231         FF(b, c, d, a, x[15], S14, 0x49b40821); /* 16 */
 232
 233         /* Round 2 */
 234         GG(a, b, c, d, x[ 1], S21, 0xf61e2562); /* 17 */
 235         GG(d, a, b, c, x[ 6], S22, 0xc040b340); /* 18 */
 236         GG(c, d, a, b, x[11], S23, 0x265e5a51); /* 19 */
 237         GG(b, c, d, a, x[ 0], S24, 0xe9b6c7aa); /* 20 */
 238         GG(a, b, c, d, x[ 5], S21, 0xd62f105d); /* 21 */
 239         GG(d, a, b, c, x[10], S22,  0x2441453); /* 22 */
 240         GG(c, d, a, b, x[15], S23, 0xd8a1e681); /* 23 */
 241         GG(b, c, d, a, x[ 4], S24, 0xe7d3fbc8); /* 24 */
 242         GG(a, b, c, d, x[ 9], S21, 0x21e1cde6); /* 25 */
 243         GG(d, a, b, c, x[14], S22, 0xc33707d6); /* 26 */
 244         GG(c, d, a, b, x[ 3], S23, 0xf4d50d87); /* 27 */
 245         GG(b, c, d, a, x[ 8], S24, 0x455a14ed); /* 28 */
 246         GG(a, b, c, d, x[13], S21, 0xa9e3e905); /* 29 */
 247         GG(d, a, b, c, x[ 2], S22, 0xfcefa3f8); /* 30 */
 248         GG(c, d, a, b, x[ 7], S23, 0x676f02d9); /* 31 */
 249         GG(b, c, d, a, x[12], S24, 0x8d2a4c8a); /* 32 */
 250
 251         /* Round 3 */
 252         HH(a, b, c, d, x[ 5], S31, 0xfffa3942); /* 33 */
 253         HH(d, a, b, c, x[ 8], S32, 0x8771f681); /* 34 */
 254         HH(c, d, a, b, x[11], S33, 0x6d9d6122); /* 35 */
 255         HH(b, c, d, a, x[14], S34, 0xfde5380c); /* 36 */
 256         HH(a, b, c, d, x[ 1], S31, 0xa4beea44); /* 37 */
 257         HH(d, a, b, c, x[ 4], S32, 0x4bdecfa9); /* 38 */
 258         HH(c, d, a, b, x[ 7], S33, 0xf6bb4b60); /* 39 */
 259         HH(b, c, d, a, x[10], S34, 0xbebfbc70); /* 40 */
 260         HH(a, b, c, d, x[13], S31, 0x289b7ec6); /* 41 */
 261         HH(d, a, b, c, x[ 0], S32, 0xeaa127fa); /* 42 */
 262         HH(c, d, a, b, x[ 3], S33, 0xd4ef3085); /* 43 */
 263         HH(b, c, d, a, x[ 6], S34,  0x4881d05); /* 44 */
 264         HH(a, b, c, d, x[ 9], S31, 0xd9d4d039); /* 45 */
 265         HH(d, a, b, c, x[12], S32, 0xe6db99e5); /* 46 */
 266         HH(c, d, a, b, x[15], S33, 0x1fa27cf8); /* 47 */
 267         HH(b, c, d, a, x[ 2], S34, 0xc4ac5665); /* 48 */
 268
 269         /* Round 4 */
 270         II(a, b, c, d, x[ 0], S41, 0xf4292244); /* 49 */
 271         II(d, a, b, c, x[ 7], S42, 0x432aff97); /* 50 */
 272         II(c, d, a, b, x[14], S43, 0xab9423a7); /* 51 */
 273         II(b, c, d, a, x[ 5], S44, 0xfc93a039); /* 52 */
 274         II(a, b, c, d, x[12], S41, 0x655b59c3); /* 53 */
 275         II(d, a, b, c, x[ 3], S42, 0x8f0ccc92); /* 54 */
 276         II(c, d, a, b, x[10], S43, 0xffeff47d); /* 55 */
 277         II(b, c, d, a, x[ 1], S44, 0x85845dd1); /* 56 */
 278         II(a, b, c, d, x[ 8], S41, 0x6fa87e4f); /* 57 */
 279         II(d, a, b, c, x[15], S42, 0xfe2ce6e0); /* 58 */
 280         II(c, d, a, b, x[ 6], S43, 0xa3014314); /* 59 */
 281         II(b, c, d, a, x[13], S44, 0x4e0811a1); /* 60 */
 282         II(a, b, c, d, x[ 4], S41, 0xf7537e82); /* 61 */
 283         II(d, a, b, c, x[11], S42, 0xbd3af235); /* 62 */
 284         II(c, d, a, b, x[ 2], S43, 0x2ad7d2bb); /* 63 */
 285         II(b, c, d, a, x[ 9], S44, 0xeb86d391); /* 64 */
 286
 287         state[0] = state[0] + a & 0xffffffff;
 288         state[1] = state[1] + b & 0xffffffff;
 289         state[2] = state[2] + c & 0xffffffff;
 290         state[3] = state[3] + d & 0xffffffff;
 291
 292         /*
 293          * Zeroize sensitive information.
 294          */
 295         memset(x, 0, sizeof x);
 296 }
 297
 298 /*
 299  * Encodes input (md5_type) into output (unsigned char). Assumes len is
 300  * a multiple of 4.
 301  */
 302 static void
 303 Encode(unsigned char *output, md5_type *input, unsigned int len)
 304 {
 305         unsigned int i, j;
 306
 307         for (i = 0, j = 0; j < len; i++, j += 4) {
 308                 output[j] = input[i] & 0xff;
 309                 output[j+1] = input[i]>>8 & 0xff;
 310                 output[j+2] = input[i]>>16 & 0xff;
 311                 output[j+3] = input[i]>> 24 & 0xff;
 312         }
 313 }
 314
 315 /*
 316  * Decodes input (unsigned char) into output (md5_type). Assumes len is
 317  * a multiple of 4.
 318  */
 319 static void
 320 Decode(md5_type *output, unsigned char *input, unsigned int len)
 321 {
 322         unsigned int    i, j;
 323
 324         for (i = 0, j = 0; j < len; i++, j += 4)
 325                 output[i] = ((md5_type)input[j] |
 326                         (md5_type)input[j+1] << 8 |
 327                         (md5_type)input[j+2] << 16 |
 328                         (md5_type)input[j+3] << 24) & 0xffffffff;
 329 }