md4c.c revision 22993
172339Sabial/* MD4C.C - RSA Data Security, Inc., MD4 message-digest algorithm 272339Sabial * $Id$ 372339Sabial */ 472339Sabial 572339Sabial/* Copyright (C) 1990-2, RSA Data Security, Inc. All rights reserved. 672339Sabial 772339Sabial License to copy and use this software is granted provided that it 872339Sabial is identified as the "RSA Data Security, Inc. MD4 Message-Digest 972339Sabial Algorithm" in all material mentioning or referencing this software 1072339Sabial or this function. 1172339Sabial 1272339Sabial License is also granted to make and use derivative works provided 1372339Sabial that such works are identified as "derived from the RSA Data 1472339Sabial Security, Inc. MD4 Message-Digest Algorithm" in all material 1572339Sabial mentioning or referencing the derived work. 1672339Sabial 1772339Sabial RSA Data Security, Inc. makes no representations concerning either 1872339Sabial the merchantability of this software or the suitability of this 1972339Sabial software for any particular purpose. It is provided "as is" 2072339Sabial without express or implied warranty of any kind. 2172339Sabial 2272339Sabial These notices must be retained in any copies of any part of this 2372339Sabial documentation and/or software. 2472339Sabial */ 2572339Sabial 2672339Sabial#include <sys/types.h> 2772339Sabial#include <string.h> 2872339Sabial#include "md4.h" 2972339Sabial 3072339Sabialtypedef unsigned char *POINTER; 3172339Sabialtypedef u_int16_t UINT2; 3272339Sabialtypedef u_int32_t UINT4; 3372339Sabial 3472339Sabial#define PROTO_LIST(list) list 3572339Sabial 3672339Sabial/* Constants for MD4Transform routine. 3772339Sabial */ 3872339Sabial#define S11 3 3972339Sabial#define S12 7 4072339Sabial#define S13 11 4172339Sabial#define S14 19 4272339Sabial#define S21 3 4372339Sabial#define S22 5 4472339Sabial#define S23 9 4572339Sabial#define S24 13 4672339Sabial#define S31 3 4772339Sabial#define S32 9 4872339Sabial#define S33 11 4972339Sabial#define S34 15 5072339Sabial 5172339Sabialstatic void MD4Transform PROTO_LIST ((UINT4 [4], const unsigned char [64])); 5272339Sabialstatic void Encode PROTO_LIST 5372339Sabial ((unsigned char *, UINT4 *, unsigned int)); 5472339Sabialstatic void Decode PROTO_LIST 5572339Sabial ((UINT4 *, const unsigned char *, unsigned int)); 5672339Sabial 5772339Sabialstatic unsigned char PADDING[64] = { 5872339Sabial 0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5972339Sabial 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6072339Sabial 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 6172339Sabial}; 6272339Sabial 6372339Sabial/* F, G and H are basic MD4 functions. 6472339Sabial */ 6572339Sabial#define F(x, y, z) (((x) & (y)) | ((~x) & (z))) 6672339Sabial#define G(x, y, z) (((x) & (y)) | ((x) & (z)) | ((y) & (z))) 6772339Sabial#define H(x, y, z) ((x) ^ (y) ^ (z)) 6872339Sabial 6972339Sabial/* ROTATE_LEFT rotates x left n bits. 7072339Sabial */ 7172339Sabial#define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n)))) 7272339Sabial 7372339Sabial/* FF, GG and HH are transformations for rounds 1, 2 and 3 */ 7472339Sabial/* Rotation is separate from addition to prevent recomputation */ 7572339Sabial#define FF(a, b, c, d, x, s) { \ 7672339Sabial (a) += F ((b), (c), (d)) + (x); \ 7772339Sabial (a) = ROTATE_LEFT ((a), (s)); \ 7872339Sabial } 7972339Sabial#define GG(a, b, c, d, x, s) { \ 8072339Sabial (a) += G ((b), (c), (d)) + (x) + (UINT4)0x5a827999; \ 8172339Sabial (a) = ROTATE_LEFT ((a), (s)); \ 8272339Sabial } 8372339Sabial#define HH(a, b, c, d, x, s) { \ 8472339Sabial (a) += H ((b), (c), (d)) + (x) + (UINT4)0x6ed9eba1; \ 8572339Sabial (a) = ROTATE_LEFT ((a), (s)); \ 8672339Sabial } 8772339Sabial 8872339Sabial/* MD4 initialization. Begins an MD4 operation, writing a new context. 8972339Sabial */ 9072339Sabialvoid MD4Init (context) 9172339SabialMD4_CTX *context; /* context */ 9272339Sabial{ 9372339Sabial context->count[0] = context->count[1] = 0; 9472339Sabial 9572339Sabial /* Load magic initialization constants. 9672339Sabial */ 9772339Sabial context->state[0] = 0x67452301; 9872339Sabial context->state[1] = 0xefcdab89; 9972339Sabial context->state[2] = 0x98badcfe; 10072339Sabial context->state[3] = 0x10325476; 10172339Sabial} 10272339Sabial 10372339Sabial/* MD4 block update operation. Continues an MD4 message-digest 10472339Sabial operation, processing another message block, and updating the 10572339Sabial context. 10672339Sabial */ 10772339Sabialvoid MD4Update (context, input, inputLen) 10872339SabialMD4_CTX *context; /* context */ 10972339Sabialconst unsigned char *input; /* input block */ 11072339Sabialunsigned int inputLen; /* length of input block */ 11172339Sabial{ 11272339Sabial unsigned int i, index, partLen; 11372339Sabial 11472339Sabial /* Compute number of bytes mod 64 */ 11572339Sabial index = (unsigned int)((context->count[0] >> 3) & 0x3F); 11672339Sabial /* Update number of bits */ 11772339Sabial if ((context->count[0] += ((UINT4)inputLen << 3)) 11872339Sabial < ((UINT4)inputLen << 3)) 11972339Sabial context->count[1]++; 12072339Sabial context->count[1] += ((UINT4)inputLen >> 29); 12172339Sabial 12272339Sabial partLen = 64 - index; 12372339Sabial /* Transform as many times as possible. 12472339Sabial */ 12572339Sabial if (inputLen >= partLen) { 12672339Sabial memcpy 12772339Sabial ((POINTER)&context->buffer[index], (POINTER)input, partLen); 12872339Sabial MD4Transform (context->state, context->buffer); 12972339Sabial 13072339Sabial for (i = partLen; i + 63 < inputLen; i += 64) 13172339Sabial MD4Transform (context->state, &input[i]); 13272339Sabial 13372339Sabial index = 0; 13472339Sabial } 13572339Sabial else 13672339Sabial i = 0; 13772339Sabial 13872339Sabial /* Buffer remaining input */ 13972339Sabial memcpy 14072339Sabial ((POINTER)&context->buffer[index], (POINTER)&input[i], 14172339Sabial inputLen-i); 14272339Sabial} 14372339Sabial 14472339Sabial/* MD4 finalization. Ends an MD4 message-digest operation, writing the 14572339Sabial the message digest and zeroizing the context. 14672339Sabial */ 14772339Sabialvoid MD4Final (digest, context) 14872339Sabialunsigned char digest[16]; /* message digest */ 14972339SabialMD4_CTX *context; /* context */ 15072339Sabial{ 15172339Sabial unsigned char bits[8]; 15272339Sabial unsigned int index, padLen; 15372339Sabial 15472339Sabial /* Save number of bits */ 15572339Sabial Encode (bits, context->count, 8); 15672339Sabial 15772339Sabial /* Pad out to 56 mod 64. 15872339Sabial */ 15972339Sabial index = (unsigned int)((context->count[0] >> 3) & 0x3f); 16072339Sabial padLen = (index < 56) ? (56 - index) : (120 - index); 16172339Sabial MD4Update (context, PADDING, padLen); 16272339Sabial 16372339Sabial /* Append length (before padding) */ 16472339Sabial MD4Update (context, bits, 8); 16572339Sabial /* Store state in digest */ 16672339Sabial Encode (digest, context->state, 16); 16772339Sabial 16872339Sabial /* Zeroize sensitive information. 16972339Sabial */ 17072339Sabial memset ((POINTER)context, 0, sizeof (*context)); 17172339Sabial} 17272339Sabial 17372339Sabial/* MD4 basic transformation. Transforms state based on block. 17472339Sabial */ 17572339Sabialstatic void MD4Transform (state, block) 17672339SabialUINT4 state[4]; 17772339Sabialconst unsigned char block[64]; 17872339Sabial{ 17972339Sabial UINT4 a = state[0], b = state[1], c = state[2], d = state[3], x[16]; 18072339Sabial 18172339Sabial Decode (x, block, 64); 18272339Sabial 18372339Sabial /* Round 1 */ 18472339Sabial FF (a, b, c, d, x[ 0], S11); /* 1 */ 18572339Sabial FF (d, a, b, c, x[ 1], S12); /* 2 */ 18672339Sabial FF (c, d, a, b, x[ 2], S13); /* 3 */ 18772339Sabial FF (b, c, d, a, x[ 3], S14); /* 4 */ 18872339Sabial FF (a, b, c, d, x[ 4], S11); /* 5 */ 18972339Sabial FF (d, a, b, c, x[ 5], S12); /* 6 */ 19072339Sabial FF (c, d, a, b, x[ 6], S13); /* 7 */ 19172339Sabial FF (b, c, d, a, x[ 7], S14); /* 8 */ 19272339Sabial FF (a, b, c, d, x[ 8], S11); /* 9 */ 19372339Sabial FF (d, a, b, c, x[ 9], S12); /* 10 */ 19472339Sabial FF (c, d, a, b, x[10], S13); /* 11 */ 19572339Sabial FF (b, c, d, a, x[11], S14); /* 12 */ 19672339Sabial FF (a, b, c, d, x[12], S11); /* 13 */ 19772339Sabial FF (d, a, b, c, x[13], S12); /* 14 */ 19872339Sabial FF (c, d, a, b, x[14], S13); /* 15 */ 19972339Sabial FF (b, c, d, a, x[15], S14); /* 16 */ 20072339Sabial 20172339Sabial /* Round 2 */ 20272339Sabial GG (a, b, c, d, x[ 0], S21); /* 17 */ 20372339Sabial GG (d, a, b, c, x[ 4], S22); /* 18 */ 20472339Sabial GG (c, d, a, b, x[ 8], S23); /* 19 */ 20572339Sabial GG (b, c, d, a, x[12], S24); /* 20 */ 20672339Sabial GG (a, b, c, d, x[ 1], S21); /* 21 */ 20772339Sabial GG (d, a, b, c, x[ 5], S22); /* 22 */ 20872339Sabial GG (c, d, a, b, x[ 9], S23); /* 23 */ 20972339Sabial GG (b, c, d, a, x[13], S24); /* 24 */ 21072339Sabial GG (a, b, c, d, x[ 2], S21); /* 25 */ 21172339Sabial GG (d, a, b, c, x[ 6], S22); /* 26 */ 21272339Sabial GG (c, d, a, b, x[10], S23); /* 27 */ 21372339Sabial GG (b, c, d, a, x[14], S24); /* 28 */ 21472339Sabial GG (a, b, c, d, x[ 3], S21); /* 29 */ 21572339Sabial GG (d, a, b, c, x[ 7], S22); /* 30 */ 21672339Sabial GG (c, d, a, b, x[11], S23); /* 31 */ 21772339Sabial GG (b, c, d, a, x[15], S24); /* 32 */ 21872339Sabial 21972339Sabial /* Round 3 */ 22072339Sabial HH (a, b, c, d, x[ 0], S31); /* 33 */ 22172339Sabial HH (d, a, b, c, x[ 8], S32); /* 34 */ 22272339Sabial HH (c, d, a, b, x[ 4], S33); /* 35 */ 22372339Sabial HH (b, c, d, a, x[12], S34); /* 36 */ 22472339Sabial HH (a, b, c, d, x[ 2], S31); /* 37 */ 22572339Sabial HH (d, a, b, c, x[10], S32); /* 38 */ 22672339Sabial HH (c, d, a, b, x[ 6], S33); /* 39 */ 22772339Sabial HH (b, c, d, a, x[14], S34); /* 40 */ 22872339Sabial HH (a, b, c, d, x[ 1], S31); /* 41 */ 22972339Sabial HH (d, a, b, c, x[ 9], S32); /* 42 */ 23072339Sabial HH (c, d, a, b, x[ 5], S33); /* 43 */ 23172339Sabial HH (b, c, d, a, x[13], S34); /* 44 */ 23272339Sabial HH (a, b, c, d, x[ 3], S31); /* 45 */ 23372339Sabial HH (d, a, b, c, x[11], S32); /* 46 */ 23472339Sabial HH (c, d, a, b, x[ 7], S33); /* 47 */ 23572339Sabial HH (b, c, d, a, x[15], S34); /* 48 */ 23672339Sabial 23772339Sabial state[0] += a; 23872339Sabial state[1] += b; 23972339Sabial state[2] += c; 24072339Sabial state[3] += d; 24172339Sabial 24272339Sabial /* Zeroize sensitive information. 24372339Sabial */ 24472339Sabial memset ((POINTER)x, 0, sizeof (x)); 24572339Sabial} 24672339Sabial 24772339Sabial/* Encodes input (UINT4) into output (unsigned char). Assumes len is 24872339Sabial a multiple of 4. 24972339Sabial */ 25072339Sabialstatic void Encode (output, input, len) 25172339Sabialunsigned char *output; 25272339SabialUINT4 *input; 25372339Sabialunsigned int len; 25472339Sabial{ 25572339Sabial unsigned int i, j; 25672339Sabial 25772339Sabial for (i = 0, j = 0; j < len; i++, j += 4) { 25872339Sabial output[j] = (unsigned char)(input[i] & 0xff); 25972339Sabial output[j+1] = (unsigned char)((input[i] >> 8) & 0xff); 26072339Sabial output[j+2] = (unsigned char)((input[i] >> 16) & 0xff); 26172339Sabial output[j+3] = (unsigned char)((input[i] >> 24) & 0xff); 26272339Sabial } 26372339Sabial} 26472339Sabial 26572339Sabial/* Decodes input (unsigned char) into output (UINT4). Assumes len is 26672339Sabial a multiple of 4. 26772339Sabial */ 26872339Sabialstatic void Decode (output, input, len) 26972339Sabial 27072339SabialUINT4 *output; 27172339Sabialconst unsigned char *input; 27272339Sabialunsigned int len; 27372339Sabial{ 27472339Sabial unsigned int i, j; 27572339Sabial 27672339Sabial for (i = 0, j = 0; j < len; i++, j += 4) 27772339Sabial output[i] = ((UINT4)input[j]) | (((UINT4)input[j+1]) << 8) | 27872339Sabial (((UINT4)input[j+2]) << 16) | (((UINT4)input[j+3]) << 24); 27972339Sabial} 28072339Sabial