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