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