wpa_supplicant_node: wpa_supplicant_node: md4-internal.c Source File

00001 /*
00002  * MD4 hash implementation
00003  * Copyright (c) 2006, Jouni Malinen <j@w1.fi>
00004  *
00005  * This program is free software; you can redistribute it and/or modify
00006  * it under the terms of the GNU General Public License version 2 as
00007  * published by the Free Software Foundation.
00008  *
00009  * Alternatively, this software may be distributed under the terms of BSD
00010  * license.
00011  *
00012  * See README and COPYING for more details.
00013  */
00014 
00015 #include "includes.h"
00016 
00017 #include "common.h"
00018 #include "crypto.h"
00019 
00020 #define MD4_BLOCK_LENGTH                64
00021 #define MD4_DIGEST_LENGTH               16
00022 
00023 typedef struct MD4Context {
00024         u32 state[4];                   /* state */
00025         u64 count;                      /* number of bits, mod 2^64 */
00026         u8 buffer[MD4_BLOCK_LENGTH];    /* input buffer */
00027 } MD4_CTX;
00028 
00029 
00030 static void MD4Init(MD4_CTX *ctx);
00031 static void MD4Update(MD4_CTX *ctx, const unsigned char *input, size_t len);
00032 static void MD4Final(unsigned char digest[MD4_DIGEST_LENGTH], MD4_CTX *ctx);
00033 
00034 
00035 int md4_vector(size_t num_elem, const u8 *addr[], const size_t *len, u8 *mac)
00036 {
00037         MD4_CTX ctx;
00038         size_t i;
00039 
00040         MD4Init(&ctx);
00041         for (i = 0; i < num_elem; i++)
00042                 MD4Update(&ctx, addr[i], len[i]);
00043         MD4Final(mac, &ctx);
00044         return 0;
00045 }
00046 
00047 
00048 /* ===== start - public domain MD4 implementation ===== */
00049 /*      $OpenBSD: md4.c,v 1.7 2005/08/08 08:05:35 espie Exp $   */
00050 
00051 /*
00052  * This code implements the MD4 message-digest algorithm.
00053  * The algorithm is due to Ron Rivest.  This code was
00054  * written by Colin Plumb in 1993, no copyright is claimed.
00055  * This code is in the public domain; do with it what you wish.
00056  * Todd C. Miller modified the MD5 code to do MD4 based on RFC 1186.
00057  *
00058  * Equivalent code is available from RSA Data Security, Inc.
00059  * This code has been tested against that, and is equivalent,
00060  * except that you don't need to include two pages of legalese
00061  * with every copy.
00062  *
00063  * To compute the message digest of a chunk of bytes, declare an
00064  * MD4Context structure, pass it to MD4Init, call MD4Update as
00065  * needed on buffers full of bytes, and then call MD4Final, which
00066  * will fill a supplied 16-byte array with the digest.
00067  */
00068 
00069 #define MD4_DIGEST_STRING_LENGTH        (MD4_DIGEST_LENGTH * 2 + 1)
00070 
00071 
00072 static void
00073 MD4Transform(u32 state[4], const u8 block[MD4_BLOCK_LENGTH]);
00074 
00075 #define PUT_64BIT_LE(cp, value) do {                                    \
00076         (cp)[7] = (value) >> 56;                                        \
00077         (cp)[6] = (value) >> 48;                                        \
00078         (cp)[5] = (value) >> 40;                                        \
00079         (cp)[4] = (value) >> 32;                                        \
00080         (cp)[3] = (value) >> 24;                                        \
00081         (cp)[2] = (value) >> 16;                                        \
00082         (cp)[1] = (value) >> 8;                                         \
00083         (cp)[0] = (value); } while (0)
00084 
00085 #define PUT_32BIT_LE(cp, value) do {                                    \
00086         (cp)[3] = (value) >> 24;                                        \
00087         (cp)[2] = (value) >> 16;                                        \
00088         (cp)[1] = (value) >> 8;                                         \
00089         (cp)[0] = (value); } while (0)
00090 
00091 static u8 PADDING[MD4_BLOCK_LENGTH] = {
00092         0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
00093         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
00094         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
00095 };
00096 
00097 /*
00098  * Start MD4 accumulation.
00099  * Set bit count to 0 and buffer to mysterious initialization constants.
00100  */
00101 static void MD4Init(MD4_CTX *ctx)
00102 {
00103         ctx->count = 0;
00104         ctx->state[0] = 0x67452301;
00105         ctx->state[1] = 0xefcdab89;
00106         ctx->state[2] = 0x98badcfe;
00107         ctx->state[3] = 0x10325476;
00108 }
00109 
00110 /*
00111  * Update context to reflect the concatenation of another buffer full
00112  * of bytes.
00113  */
00114 static void MD4Update(MD4_CTX *ctx, const unsigned char *input, size_t len)
00115 {
00116         size_t have, need;
00117 
00118         /* Check how many bytes we already have and how many more we need. */
00119         have = (size_t)((ctx->count >> 3) & (MD4_BLOCK_LENGTH - 1));
00120         need = MD4_BLOCK_LENGTH - have;
00121 
00122         /* Update bitcount */
00123         ctx->count += (u64)len << 3;
00124 
00125         if (len >= need) {
00126                 if (have != 0) {
00127                         os_memcpy(ctx->buffer + have, input, need);
00128                         MD4Transform(ctx->state, ctx->buffer);
00129                         input += need;
00130                         len -= need;
00131                         have = 0;
00132                 }
00133 
00134                 /* Process data in MD4_BLOCK_LENGTH-byte chunks. */
00135                 while (len >= MD4_BLOCK_LENGTH) {
00136                         MD4Transform(ctx->state, input);
00137                         input += MD4_BLOCK_LENGTH;
00138                         len -= MD4_BLOCK_LENGTH;
00139                 }
00140         }
00141 
00142         /* Handle any remaining bytes of data. */
00143         if (len != 0)
00144                 os_memcpy(ctx->buffer + have, input, len);
00145 }
00146 
00147 /*
00148  * Pad pad to 64-byte boundary with the bit pattern
00149  * 1 0* (64-bit count of bits processed, MSB-first)
00150  */
00151 static void MD4Pad(MD4_CTX *ctx)
00152 {
00153         u8 count[8];
00154         size_t padlen;
00155 
00156         /* Convert count to 8 bytes in little endian order. */
00157         PUT_64BIT_LE(count, ctx->count);
00158 
00159         /* Pad out to 56 mod 64. */
00160         padlen = MD4_BLOCK_LENGTH -
00161             ((ctx->count >> 3) & (MD4_BLOCK_LENGTH - 1));
00162         if (padlen < 1 + 8)
00163                 padlen += MD4_BLOCK_LENGTH;
00164         MD4Update(ctx, PADDING, padlen - 8);            /* padlen - 8 <= 64 */
00165         MD4Update(ctx, count, 8);
00166 }
00167 
00168 /*
00169  * Final wrapup--call MD4Pad, fill in digest and zero out ctx.
00170  */
00171 static void MD4Final(unsigned char digest[MD4_DIGEST_LENGTH], MD4_CTX *ctx)
00172 {
00173         int i;
00174 
00175         MD4Pad(ctx);
00176         if (digest != NULL) {
00177                 for (i = 0; i < 4; i++)
00178                         PUT_32BIT_LE(digest + i * 4, ctx->state[i]);
00179                 os_memset(ctx, 0, sizeof(*ctx));
00180         }
00181 }
00182 
00183 
00184 /* The three core functions - F1 is optimized somewhat */
00185 
00186 /* #define F1(x, y, z) (x & y | ~x & z) */
00187 #define F1(x, y, z) (z ^ (x & (y ^ z)))
00188 #define F2(x, y, z) ((x & y) | (x & z) | (y & z))
00189 #define F3(x, y, z) (x ^ y ^ z)
00190 
00191 /* This is the central step in the MD4 algorithm. */
00192 #define MD4STEP(f, w, x, y, z, data, s) \
00193         ( w += f(x, y, z) + data,  w = w<<s | w>>(32-s) )
00194 
00195 /*
00196  * The core of the MD4 algorithm, this alters an existing MD4 hash to
00197  * reflect the addition of 16 longwords of new data.  MD4Update blocks
00198  * the data and converts bytes into longwords for this routine.
00199  */
00200 static void
00201 MD4Transform(u32 state[4], const u8 block[MD4_BLOCK_LENGTH])
00202 {
00203         u32 a, b, c, d, in[MD4_BLOCK_LENGTH / 4];
00204 
00205 #if BYTE_ORDER == LITTLE_ENDIAN
00206         os_memcpy(in, block, sizeof(in));
00207 #else
00208         for (a = 0; a < MD4_BLOCK_LENGTH / 4; a++) {
00209                 in[a] = (u32)(
00210                     (u32)(block[a * 4 + 0]) |
00211                     (u32)(block[a * 4 + 1]) <<  8 |
00212                     (u32)(block[a * 4 + 2]) << 16 |
00213                     (u32)(block[a * 4 + 3]) << 24);
00214         }
00215 #endif
00216 
00217         a = state[0];
00218         b = state[1];
00219         c = state[2];
00220         d = state[3];
00221 
00222         MD4STEP(F1, a, b, c, d, in[ 0],  3);
00223         MD4STEP(F1, d, a, b, c, in[ 1],  7);
00224         MD4STEP(F1, c, d, a, b, in[ 2], 11);
00225         MD4STEP(F1, b, c, d, a, in[ 3], 19);
00226         MD4STEP(F1, a, b, c, d, in[ 4],  3);
00227         MD4STEP(F1, d, a, b, c, in[ 5],  7);
00228         MD4STEP(F1, c, d, a, b, in[ 6], 11);
00229         MD4STEP(F1, b, c, d, a, in[ 7], 19);
00230         MD4STEP(F1, a, b, c, d, in[ 8],  3);
00231         MD4STEP(F1, d, a, b, c, in[ 9],  7);
00232         MD4STEP(F1, c, d, a, b, in[10], 11);
00233         MD4STEP(F1, b, c, d, a, in[11], 19);
00234         MD4STEP(F1, a, b, c, d, in[12],  3);
00235         MD4STEP(F1, d, a, b, c, in[13],  7);
00236         MD4STEP(F1, c, d, a, b, in[14], 11);
00237         MD4STEP(F1, b, c, d, a, in[15], 19);
00238 
00239         MD4STEP(F2, a, b, c, d, in[ 0] + 0x5a827999,  3);
00240         MD4STEP(F2, d, a, b, c, in[ 4] + 0x5a827999,  5);
00241         MD4STEP(F2, c, d, a, b, in[ 8] + 0x5a827999,  9);
00242         MD4STEP(F2, b, c, d, a, in[12] + 0x5a827999, 13);
00243         MD4STEP(F2, a, b, c, d, in[ 1] + 0x5a827999,  3);
00244         MD4STEP(F2, d, a, b, c, in[ 5] + 0x5a827999,  5);
00245         MD4STEP(F2, c, d, a, b, in[ 9] + 0x5a827999,  9);
00246         MD4STEP(F2, b, c, d, a, in[13] + 0x5a827999, 13);
00247         MD4STEP(F2, a, b, c, d, in[ 2] + 0x5a827999,  3);
00248         MD4STEP(F2, d, a, b, c, in[ 6] + 0x5a827999,  5);
00249         MD4STEP(F2, c, d, a, b, in[10] + 0x5a827999,  9);
00250         MD4STEP(F2, b, c, d, a, in[14] + 0x5a827999, 13);
00251         MD4STEP(F2, a, b, c, d, in[ 3] + 0x5a827999,  3);
00252         MD4STEP(F2, d, a, b, c, in[ 7] + 0x5a827999,  5);
00253         MD4STEP(F2, c, d, a, b, in[11] + 0x5a827999,  9);
00254         MD4STEP(F2, b, c, d, a, in[15] + 0x5a827999, 13);
00255 
00256         MD4STEP(F3, a, b, c, d, in[ 0] + 0x6ed9eba1,  3);
00257         MD4STEP(F3, d, a, b, c, in[ 8] + 0x6ed9eba1,  9);
00258         MD4STEP(F3, c, d, a, b, in[ 4] + 0x6ed9eba1, 11);
00259         MD4STEP(F3, b, c, d, a, in[12] + 0x6ed9eba1, 15);
00260         MD4STEP(F3, a, b, c, d, in[ 2] + 0x6ed9eba1,  3);
00261         MD4STEP(F3, d, a, b, c, in[10] + 0x6ed9eba1,  9);
00262         MD4STEP(F3, c, d, a, b, in[ 6] + 0x6ed9eba1, 11);
00263         MD4STEP(F3, b, c, d, a, in[14] + 0x6ed9eba1, 15);
00264         MD4STEP(F3, a, b, c, d, in[ 1] + 0x6ed9eba1,  3);
00265         MD4STEP(F3, d, a, b, c, in[ 9] + 0x6ed9eba1,  9);
00266         MD4STEP(F3, c, d, a, b, in[ 5] + 0x6ed9eba1, 11);
00267         MD4STEP(F3, b, c, d, a, in[13] + 0x6ed9eba1, 15);
00268         MD4STEP(F3, a, b, c, d, in[ 3] + 0x6ed9eba1,  3);
00269         MD4STEP(F3, d, a, b, c, in[11] + 0x6ed9eba1,  9);
00270         MD4STEP(F3, c, d, a, b, in[ 7] + 0x6ed9eba1, 11);
00271         MD4STEP(F3, b, c, d, a, in[15] + 0x6ed9eba1, 15);
00272 
00273         state[0] += a;
00274         state[1] += b;
00275         state[2] += c;
00276         state[3] += d;
00277 }
00278 /* ===== end - public domain MD4 implementation ===== */