md5.c

00001 /*
00002  * Copyright (c) 2007, Cameron Rich
00003  * 
00004  * All rights reserved.
00005  * 
00006  * Redistribution and use in source and binary forms, with or without 
00007  * modification, are permitted provided that the following conditions are met:
00008  *
00009  * * Redistributions of source code must retain the above copyright notice, 
00010  *   this list of conditions and the following disclaimer.
00011  * * Redistributions in binary form must reproduce the above copyright notice, 
00012  *   this list of conditions and the following disclaimer in the documentation 
00013  *   and/or other materials provided with the distribution.
00014  * * Neither the name of the axTLS project nor the names of its contributors 
00015  *   may be used to endorse or promote products derived from this software 
00016  *   without specific prior written permission.
00017  *
00018  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
00019  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
00020  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
00021  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
00022  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
00023  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
00024  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
00025  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
00026  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
00027  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
00028  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00029  */
00030 
00031 /**
00032  * This file implements the MD5 algorithm as defined in RFC1321
00033  */
00034 
00035 #include <string.h>
00036 #include "os_port.h"
00037 #include "crypto.h "
00038 
00039 /* Constants for MD5Transform routine.
00040  */
00041 #define S11 7
00042 #define S12 12
00043 #define S13 17
00044 #define S14 22
00045 #define S21 5
00046 #define S22 9
00047 #define S23 14
00048 #define S24 20
00049 #define S31 4
00050 #define S32 11
00051 #define S33 16
00052 #define S34 23
00053 #define S41 6
00054 #define S42 10
00055 #define S43 15
00056 #define S44 21
00057 
00058 /* ----- static functions ----- */
00059 static void MD5Transform(uint32_t state[4], const uint8_t block[64]);
00060 static void Encode(uint8_t *output, uint32_t *input, uint32_t len);
00061 static void Decode(uint32_t *output, const uint8_t *input, uint32_t len);
00062 
00063 static const uint8_t PADDING[64] = 
00064 {
00065     0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
00066     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
00067     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
00068 };
00069 
00070 /* F, G, H and I are basic MD5 functions.
00071  */
00072 #define F(x, y, z) (((x) & (y)) | ((~x) & (z)))
00073 #define G(x, y, z) (((x) & (z)) | ((y) & (~z)))
00074 #define H(x, y, z) ((x) ^ (y) ^ (z))
00075 #define I(x, y, z) ((y) ^ ((x) | (~z)))
00076 
00077 /* ROTATE_LEFT rotates x left n bits.  */
00078 #define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n))))
00079 
00080 /* FF, GG, HH, and II transformations for rounds 1, 2, 3, and 4.
00081    Rotation is separate from addition to prevent recomputation.  */
00082 #define FF(a, b, c, d, x, s, ac) { \
00083     (a) += F ((b), (c), (d)) + (x) + (uint32_t)(ac); \
00084     (a) = ROTATE_LEFT ((a), (s)); \
00085     (a) += (b); \
00086   }
00087 #define GG(a, b, c, d, x, s, ac) { \
00088     (a) += G ((b), (c), (d)) + (x) + (uint32_t)(ac); \
00089     (a) = ROTATE_LEFT ((a), (s)); \
00090     (a) += (b); \
00091   }
00092 #define HH(a, b, c, d, x, s, ac) { \
00093     (a) += H ((b), (c), (d)) + (x) + (uint32_t)(ac); \
00094     (a) = ROTATE_LEFT ((a), (s)); \
00095     (a) += (b); \
00096   }
00097 #define II(a, b, c, d, x, s, ac) { \
00098     (a) += I ((b), (c), (d)) + (x) + (uint32_t)(ac); \
00099     (a) = ROTATE_LEFT ((a), (s)); \
00100     (a) += (b); \
00101   }
00102 
00103 /**
00104  * MD5 initialization - begins an MD5 operation, writing a new ctx.
00105  */
00106 EXP_FUNC void STDCALL MD5_Init(MD5_CTX *ctx)
00107 {
00108     ctx->count[0] = ctx->count[1] = 0;
00109 
00110     /* Load magic initialization constants.
00111      */
00112     ctx->state[0] = 0x67452301;
00113     ctx->state[1] = 0xefcdab89;
00114     ctx->state[2] = 0x98badcfe;
00115     ctx->state[3] = 0x10325476;
00116 }
00117 
00118 /**
00119  * Accepts an array of octets as the next portion of the message.
00120  */
00121 EXP_FUNC void STDCALL MD5_Update(MD5_CTX *ctx, const uint8_t * msg, int len)
00122 {
00123     uint32_t x;
00124     int i, partLen;
00125 
00126     /* Compute number of bytes mod 64 */
00127     x = (uint32_t)((ctx->count[0] >> 3) & 0x3F);
00128 
00129     /* Update number of bits */
00130     if ((ctx->count[0] += ((uint32_t)len << 3)) < ((uint32_t)len << 3))
00131         ctx->count[1]++;
00132     ctx->count[1] += ((uint32_t)len >> 29);
00133 
00134     partLen = 64 - x;
00135 
00136     /* Transform as many times as possible.  */
00137     if (len >= partLen) 
00138     {
00139         memcpy(&ctx->buffer[x], msg, partLen);
00140         MD5Transform(ctx->state, ctx->buffer);
00141 
00142         for (i = partLen; i + 63 < len; i += 64)
00143             MD5Transform(ctx->state, &msg[i]);
00144 
00145         x = 0;
00146     }
00147     else
00148         i = 0;
00149 
00150     /* Buffer remaining input */
00151     memcpy(&ctx->buffer[x], &msg[i], len-i);
00152 }
00153 
00154 /**
00155  * Return the 128-bit message digest into the user's array
00156  */
00157 EXP_FUNC void STDCALL MD5_Final(uint8_t *digest, MD5_CTX *ctx)
00158 {
00159     uint8_t bits[8];
00160     uint32_t x, padLen;
00161 
00162     /* Save number of bits */
00163     Encode(bits, ctx->count, 8);
00164 
00165     /* Pad out to 56 mod 64.
00166      */
00167     x = (uint32_t)((ctx->count[0] >> 3) & 0x3f);
00168     padLen = (x < 56) ? (56 - x) : (120 - x);
00169     MD5_Update(ctx, PADDING, padLen);
00170 
00171     /* Append length (before padding) */
00172     MD5_Update(ctx, bits, 8);
00173 
00174     /* Store state in digest */
00175     Encode(digest, ctx->state, MD5_SIZE);
00176 }
00177 
00178 /**
00179  * MD5 basic transformation. Transforms state based on block.
00180  */
00181 static void MD5Transform(uint32_t state[4], const uint8_t block[64])
00182 {
00183     uint32_t a = state[0], b = state[1], c = state[2], 
00184              d = state[3], x[MD5_SIZE];
00185 
00186     Decode(x, block, 64);
00187 
00188     /* Round 1 */
00189     FF (a, b, c, d, x[ 0], S11, 0xd76aa478); /* 1 */
00190     FF (d, a, b, c, x[ 1], S12, 0xe8c7b756); /* 2 */
00191     FF (c, d, a, b, x[ 2], S13, 0x242070db); /* 3 */
00192     FF (b, c, d, a, x[ 3], S14, 0xc1bdceee); /* 4 */
00193     FF (a, b, c, d, x[ 4], S11, 0xf57c0faf); /* 5 */
00194     FF (d, a, b, c, x[ 5], S12, 0x4787c62a); /* 6 */
00195     FF (c, d, a, b, x[ 6], S13, 0xa8304613); /* 7 */
00196     FF (b, c, d, a, x[ 7], S14, 0xfd469501); /* 8 */
00197     FF (a, b, c, d, x[ 8], S11, 0x698098d8); /* 9 */
00198     FF (d, a, b, c, x[ 9], S12, 0x8b44f7af); /* 10 */
00199     FF (c, d, a, b, x[10], S13, 0xffff5bb1); /* 11 */
00200     FF (b, c, d, a, x[11], S14, 0x895cd7be); /* 12 */
00201     FF (a, b, c, d, x[12], S11, 0x6b901122); /* 13 */
00202     FF (d, a, b, c, x[13], S12, 0xfd987193); /* 14 */
00203     FF (c, d, a, b, x[14], S13, 0xa679438e); /* 15 */
00204     FF (b, c, d, a, x[15], S14, 0x49b40821); /* 16 */
00205 
00206     /* Round 2 */
00207     GG (a, b, c, d, x[ 1], S21, 0xf61e2562); /* 17 */
00208     GG (d, a, b, c, x[ 6], S22, 0xc040b340); /* 18 */
00209     GG (c, d, a, b, x[11], S23, 0x265e5a51); /* 19 */
00210     GG (b, c, d, a, x[ 0], S24, 0xe9b6c7aa); /* 20 */
00211     GG (a, b, c, d, x[ 5], S21, 0xd62f105d); /* 21 */
00212     GG (d, a, b, c, x[10], S22,  0x2441453); /* 22 */
00213     GG (c, d, a, b, x[15], S23, 0xd8a1e681); /* 23 */
00214     GG (b, c, d, a, x[ 4], S24, 0xe7d3fbc8); /* 24 */
00215     GG (a, b, c, d, x[ 9], S21, 0x21e1cde6); /* 25 */
00216     GG (d, a, b, c, x[14], S22, 0xc33707d6); /* 26 */
00217     GG (c, d, a, b, x[ 3], S23, 0xf4d50d87); /* 27 */
00218     GG (b, c, d, a, x[ 8], S24, 0x455a14ed); /* 28 */
00219     GG (a, b, c, d, x[13], S21, 0xa9e3e905); /* 29 */
00220     GG (d, a, b, c, x[ 2], S22, 0xfcefa3f8); /* 30 */
00221     GG (c, d, a, b, x[ 7], S23, 0x676f02d9); /* 31 */
00222     GG (b, c, d, a, x[12], S24, 0x8d2a4c8a); /* 32 */
00223 
00224     /* Round 3 */
00225     HH (a, b, c, d, x[ 5], S31, 0xfffa3942); /* 33 */
00226     HH (d, a, b, c, x[ 8], S32, 0x8771f681); /* 34 */
00227     HH (c, d, a, b, x[11], S33, 0x6d9d6122); /* 35 */
00228     HH (b, c, d, a, x[14], S34, 0xfde5380c); /* 36 */
00229     HH (a, b, c, d, x[ 1], S31, 0xa4beea44); /* 37 */
00230     HH (d, a, b, c, x[ 4], S32, 0x4bdecfa9); /* 38 */
00231     HH (c, d, a, b, x[ 7], S33, 0xf6bb4b60); /* 39 */
00232     HH (b, c, d, a, x[10], S34, 0xbebfbc70); /* 40 */
00233     HH (a, b, c, d, x[13], S31, 0x289b7ec6); /* 41 */
00234     HH (d, a, b, c, x[ 0], S32, 0xeaa127fa); /* 42 */
00235     HH (c, d, a, b, x[ 3], S33, 0xd4ef3085); /* 43 */
00236     HH (b, c, d, a, x[ 6], S34,  0x4881d05); /* 44 */
00237     HH (a, b, c, d, x[ 9], S31, 0xd9d4d039); /* 45 */
00238     HH (d, a, b, c, x[12], S32, 0xe6db99e5); /* 46 */
00239     HH (c, d, a, b, x[15], S33, 0x1fa27cf8); /* 47 */
00240     HH (b, c, d, a, x[ 2], S34, 0xc4ac5665); /* 48 */
00241 
00242     /* Round 4 */
00243     II (a, b, c, d, x[ 0], S41, 0xf4292244); /* 49 */
00244     II (d, a, b, c, x[ 7], S42, 0x432aff97); /* 50 */
00245     II (c, d, a, b, x[14], S43, 0xab9423a7); /* 51 */
00246     II (b, c, d, a, x[ 5], S44, 0xfc93a039); /* 52 */
00247     II (a, b, c, d, x[12], S41, 0x655b59c3); /* 53 */
00248     II (d, a, b, c, x[ 3], S42, 0x8f0ccc92); /* 54 */
00249     II (c, d, a, b, x[10], S43, 0xffeff47d); /* 55 */
00250     II (b, c, d, a, x[ 1], S44, 0x85845dd1); /* 56 */
00251     II (a, b, c, d, x[ 8], S41, 0x6fa87e4f); /* 57 */
00252     II (d, a, b, c, x[15], S42, 0xfe2ce6e0); /* 58 */
00253     II (c, d, a, b, x[ 6], S43, 0xa3014314); /* 59 */
00254     II (b, c, d, a, x[13], S44, 0x4e0811a1); /* 60 */
00255     II (a, b, c, d, x[ 4], S41, 0xf7537e82); /* 61 */
00256     II (d, a, b, c, x[11], S42, 0xbd3af235); /* 62 */
00257     II (c, d, a, b, x[ 2], S43, 0x2ad7d2bb); /* 63 */
00258     II (b, c, d, a, x[ 9], S44, 0xeb86d391); /* 64 */
00259 
00260     state[0] += a;
00261     state[1] += b;
00262     state[2] += c;
00263     state[3] += d;
00264 }
00265 
00266 /**
00267  * Encodes input (uint32_t) into output (uint8_t). Assumes len is
00268  *   a multiple of 4.
00269  */
00270 static void Encode(uint8_t *output, uint32_t *input, uint32_t len)
00271 {
00272     uint32_t i, j;
00273 
00274     for (i = 0, j = 0; j < len; i++, j += 4) 
00275     {
00276         output[j] = (uint8_t)(input[i] & 0xff);
00277         output[j+1] = (uint8_t)((input[i] >> 8) & 0xff);
00278         output[j+2] = (uint8_t)((input[i] >> 16) & 0xff);
00279         output[j+3] = (uint8_t)((input[i] >> 24) & 0xff);
00280     }
00281 }
00282 
00283 /**
00284  *  Decodes input (uint8_t) into output (uint32_t). Assumes len is
00285  *   a multiple of 4.
00286  */
00287 static void Decode(uint32_t *output, const uint8_t *input, uint32_t len)
00288 {
00289     uint32_t i, j;
00290 
00291     for (i = 0, j = 0; j < len; i++, j += 4)
00292         output[i] = ((uint32_t)input[j]) | (((uint32_t)input[j+1]) << 8) |
00293             (((uint32_t)input[j+2]) << 16) | (((uint32_t)input[j+3]) << 24);
00294 }