md5.c

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