md5_utils.c

   1 /*
   2  *  Copyright (c) 2010 The VP8 project authors. All Rights Reserved.
   3  *
   4  *  Use of this source code is governed by a BSD-style license
   5  *  that can be found in the LICENSE file in the root of the source
   6  *  tree. An additional intellectual property rights grant can be found
   7  *  in the file PATENTS.  All contributing project authors may
   8  *  be found in the AUTHORS file in the root of the source tree.
   9  */
  10
  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 "md5_utils.h"
  36 #include <string.h>
  37
  38 /* Constants for md5_transform routine.
  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
  57 static void md5_transform(uint32_t state[4], const uint8_t block[64]);
  58 static void Encode(uint8_t *output, const uint32_t *input, unsigned int len);
  59 static void Decode(uint32_t *output, const uint8_t *input, unsigned int len);
  60 #define md5_memset memset
  61 #define md5_memcpy memcpy
  62
  63 static unsigned char PADDING[64] =
  64 {
  65     0x80, 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, 0, 0, 0, 0,
  67     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 #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)))
  76
  77 /* ROTATE_LEFT rotates x left n bits.
  78  */
  79 #define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n))))
  80
  81 /* FF, GG, HH, and II transformations for rounds 1, 2, 3, and 4.
  82 Rotation is separate from addition to prevent recomputation.
  83  */
  84 #define FF(a, b, c, d, x, s, ac) { \
  85         (a) += F ((b), (c), (d)) + (x) + (uint32_t)(ac); \
  86         (a) = ROTATE_LEFT ((a), (s)); \
  87         (a) += (b); \
  88     }
  89 #define GG(a, b, c, d, x, s, ac) { \
  90         (a) += G ((b), (c), (d)) + (x) + (uint32_t)(ac); \
  91         (a) = ROTATE_LEFT ((a), (s)); \
  92         (a) += (b); \
  93     }
  94 #define HH(a, b, c, d, x, s, ac) { \
  95         (a) += H ((b), (c), (d)) + (x) + (uint32_t)(ac); \
  96         (a) = ROTATE_LEFT ((a), (s)); \
  97         (a) += (b); \
  98     }
  99 #define II(a, b, c, d, x, s, ac) { \
 100         (a) += I ((b), (c), (d)) + (x) + (uint32_t)(ac); \
 101         (a) = ROTATE_LEFT ((a), (s)); \
 102         (a) += (b); \
 103     }
 104
 105 /* MD5 initialization. Begins an MD5 operation, writing a new context.
 106  */
 107 void md5_init(md5_ctx_t *context)
 108 {
 109     context->count[0] = context->count[1] = 0;
 110     /* Load magic initialization constants.
 111     */
 112     context->state[0] = 0x67452301;
 113     context->state[1] = 0xefcdab89;
 114     context->state[2] = 0x98badcfe;
 115     context->state[3] = 0x10325476;
 116 }
 117
 118 /* MD5 block update operation. Continues an MD5 message-digest
 119   operation, processing another message block, and updating the
 120   context.
 121  */
 122 void md5_update(md5_ctx_t *context, const uint8_t *input, unsigned int input_len)
 123 {
 124     unsigned int i, index, part_len;
 125
 126     /* Compute number of bytes mod 64 */
 127     index = (unsigned int)((context->count[0] >> 3) & 0x3F);
 128
 129     /* Update number of bits */
 130     if ((context->count[0] += ((uint32_t)input_len << 3))
 131         < ((uint32_t)input_len << 3))
 132         context->count[1]++;
 133
 134     context->count[1] += ((uint32_t)input_len >> 29);
 135
 136     part_len = 64 - index;
 137
 138     /* Transform as many times as possible. */
 139     if (input_len >= part_len)
 140     {
 141         memcpy(&context->buffer[index], input, part_len);
 142         md5_transform(context->state, context->buffer);
 143
 144         for (i = part_len; i + 63 < input_len; i += 64)
 145             md5_transform(context->state, &input[i]);
 146
 147         index = 0;
 148     }
 149     else
 150         i = 0;
 151
 152     /* Buffer remaining input */
 153     memcpy(&context->buffer[index], &input[i], input_len - i);
 154 }
 155
 156 /* MD5 finalization. Ends an MD5 message-digest operation, writing the
 157   the message digest and zeroizing the context.
 158  */
 159 void md5_finalize(md5_ctx_t *context, uint8_t digest[16])
 160 {
 161     unsigned char bits[8];
 162     unsigned int index, pad_len;
 163
 164     /* Save number of bits */
 165     Encode(bits, context->count, 8);
 166
 167     /* Pad out to 56 mod 64.
 168     */
 169     index = (unsigned int)((context->count[0] >> 3) & 0x3f);
 170     pad_len = (index < 56) ? (56 - index) : (120 - index);
 171     md5_update(context, PADDING, pad_len);
 172
 173     /* Append length (before padding) */
 174     md5_update(context, bits, 8);
 175     /* Store state in digest */
 176     Encode(digest, context->state, 16);
 177
 178     /* Zeroize sensitive information.
 179     */
 180     memset(context, 0, sizeof(*context));
 181 }
 182
 183 /* MD5 basic transformation. Transforms state based on block.
 184  */
 185 static void md5_transform(uint32_t state[4], const uint8_t block[64])
 186 {
 187     uint32_t a = state[0], b = state[1], c = state[2], d = state[3], x[16];
 188
 189     Decode(x, block, 64);
 190
 191     /* Round 1 */
 192     FF(a, b, c, d, x[ 0], S11, 0xd76aa478);  /* 1 */
 193     FF(d, a, b, c, x[ 1], S12, 0xe8c7b756);  /* 2 */
 194     FF(c, d, a, b, x[ 2], S13, 0x242070db);  /* 3 */
 195     FF(b, c, d, a, x[ 3], S14, 0xc1bdceee);  /* 4 */
 196     FF(a, b, c, d, x[ 4], S11, 0xf57c0faf);  /* 5 */
 197     FF(d, a, b, c, x[ 5], S12, 0x4787c62a);  /* 6 */
 198     FF(c, d, a, b, x[ 6], S13, 0xa8304613);  /* 7 */
 199     FF(b, c, d, a, x[ 7], S14, 0xfd469501);  /* 8 */
 200     FF(a, b, c, d, x[ 8], S11, 0x698098d8);  /* 9 */
 201     FF(d, a, b, c, x[ 9], S12, 0x8b44f7af);  /* 10 */
 202     FF(c, d, a, b, x[10], S13, 0xffff5bb1);  /* 11 */
 203     FF(b, c, d, a, x[11], S14, 0x895cd7be);  /* 12 */
 204     FF(a, b, c, d, x[12], S11, 0x6b901122);  /* 13 */
 205     FF(d, a, b, c, x[13], S12, 0xfd987193);  /* 14 */
 206     FF(c, d, a, b, x[14], S13, 0xa679438e);  /* 15 */
 207     FF(b, c, d, a, x[15], S14, 0x49b40821);  /* 16 */
 208
 209     /* Round 2 */
 210     GG(a, b, c, d, x[ 1], S21, 0xf61e2562);  /* 17 */
 211     GG(d, a, b, c, x[ 6], S22, 0xc040b340);  /* 18 */
 212     GG(c, d, a, b, x[11], S23, 0x265e5a51);  /* 19 */
 213     GG(b, c, d, a, x[ 0], S24, 0xe9b6c7aa);  /* 20 */
 214     GG(a, b, c, d, x[ 5], S21, 0xd62f105d);  /* 21 */
 215     GG(d, a, b, c, x[10], S22,  0x2441453);  /* 22 */
 216     GG(c, d, a, b, x[15], S23, 0xd8a1e681);  /* 23 */
 217     GG(b, c, d, a, x[ 4], S24, 0xe7d3fbc8);  /* 24 */
 218     GG(a, b, c, d, x[ 9], S21, 0x21e1cde6);  /* 25 */
 219     GG(d, a, b, c, x[14], S22, 0xc33707d6);  /* 26 */
 220     GG(c, d, a, b, x[ 3], S23, 0xf4d50d87);  /* 27 */
 221     GG(b, c, d, a, x[ 8], S24, 0x455a14ed);  /* 28 */
 222     GG(a, b, c, d, x[13], S21, 0xa9e3e905);  /* 29 */
 223     GG(d, a, b, c, x[ 2], S22, 0xfcefa3f8);  /* 30 */
 224     GG(c, d, a, b, x[ 7], S23, 0x676f02d9);  /* 31 */
 225     GG(b, c, d, a, x[12], S24, 0x8d2a4c8a);  /* 32 */
 226
 227     /* Round 3 */
 228     HH(a, b, c, d, x[ 5], S31, 0xfffa3942);  /* 33 */
 229     HH(d, a, b, c, x[ 8], S32, 0x8771f681);  /* 34 */
 230     HH(c, d, a, b, x[11], S33, 0x6d9d6122);  /* 35 */
 231     HH(b, c, d, a, x[14], S34, 0xfde5380c);  /* 36 */
 232     HH(a, b, c, d, x[ 1], S31, 0xa4beea44);  /* 37 */
 233     HH(d, a, b, c, x[ 4], S32, 0x4bdecfa9);  /* 38 */
 234     HH(c, d, a, b, x[ 7], S33, 0xf6bb4b60);  /* 39 */
 235     HH(b, c, d, a, x[10], S34, 0xbebfbc70);  /* 40 */
 236     HH(a, b, c, d, x[13], S31, 0x289b7ec6);  /* 41 */
 237     HH(d, a, b, c, x[ 0], S32, 0xeaa127fa);  /* 42 */
 238     HH(c, d, a, b, x[ 3], S33, 0xd4ef3085);  /* 43 */
 239     HH(b, c, d, a, x[ 6], S34,  0x4881d05);  /* 44 */
 240     HH(a, b, c, d, x[ 9], S31, 0xd9d4d039);  /* 45 */
 241     HH(d, a, b, c, x[12], S32, 0xe6db99e5);  /* 46 */
 242     HH(c, d, a, b, x[15], S33, 0x1fa27cf8);  /* 47 */
 243     HH(b, c, d, a, x[ 2], S34, 0xc4ac5665);  /* 48 */
 244
 245     /* Round 4 */
 246     II(a, b, c, d, x[ 0], S41, 0xf4292244);  /* 49 */
 247     II(d, a, b, c, x[ 7], S42, 0x432aff97);  /* 50 */
 248     II(c, d, a, b, x[14], S43, 0xab9423a7);  /* 51 */
 249     II(b, c, d, a, x[ 5], S44, 0xfc93a039);  /* 52 */
 250     II(a, b, c, d, x[12], S41, 0x655b59c3);  /* 53 */
 251     II(d, a, b, c, x[ 3], S42, 0x8f0ccc92);  /* 54 */
 252     II(c, d, a, b, x[10], S43, 0xffeff47d);  /* 55 */
 253     II(b, c, d, a, x[ 1], S44, 0x85845dd1);  /* 56 */
 254     II(a, b, c, d, x[ 8], S41, 0x6fa87e4f);  /* 57 */
 255     II(d, a, b, c, x[15], S42, 0xfe2ce6e0);  /* 58 */
 256     II(c, d, a, b, x[ 6], S43, 0xa3014314);  /* 59 */
 257     II(b, c, d, a, x[13], S44, 0x4e0811a1);  /* 60 */
 258     II(a, b, c, d, x[ 4], S41, 0xf7537e82);  /* 61 */
 259     II(d, a, b, c, x[11], S42, 0xbd3af235);  /* 62 */
 260     II(c, d, a, b, x[ 2], S43, 0x2ad7d2bb);  /* 63 */
 261     II(b, c, d, a, x[ 9], S44, 0xeb86d391);  /* 64 */
 262
 263     state[0] += a;
 264     state[1] += b;
 265     state[2] += c;
 266     state[3] += d;
 267
 268     /* Zeroize sensitive information.
 269     */
 270     memset(x, 0, sizeof(x));
 271 }
 272
 273 /* Encodes input (uint32_t) into output (unsigned char). Assumes len is
 274   a multiple of 4.
 275  */
 276 static void Encode(uint8_t *output, const uint32_t *input, unsigned int len)
 277 {
 278     unsigned int i, j;
 279
 280     for (i = 0, j = 0; j < len; i++, j += 4)
 281     {
 282         output[j] = (unsigned char)(input[i] & 0xff);
 283         output[j+1] = (unsigned char)((input[i] >> 8) & 0xff);
 284         output[j+2] = (unsigned char)((input[i] >> 16) & 0xff);
 285         output[j+3] = (unsigned char)((input[i] >> 24) & 0xff);
 286     }
 287 }
 288
 289 /* Decodes input (unsigned char) into output (uint32_t). Assumes len is
 290   a multiple of 4.
 291  */
 292 static void Decode(uint32_t *output, const uint8_t *input, unsigned int len)
 293 {
 294     unsigned int i, j;
 295
 296     for (i = 0, j = 0; j < len; i++, j += 4)
 297         output[i] = ((uint32_t)input[j]) | (((uint32_t)input[j+1]) << 8) |
 298                     (((uint32_t)input[j+2]) << 16) | (((uint32_t)input[j+3]) << 24);
 299 }