md4c.c revision 116182
175374Sbp/* MD4C.C - RSA Data Security, Inc., MD4 message-digest algorithm 275374Sbp */ 375374Sbp 475374Sbp/* Copyright (C) 1990-2, RSA Data Security, Inc. All rights reserved. 575374Sbp 675374Sbp License to copy and use this software is granted provided that it 775374Sbp is identified as the "RSA Data Security, Inc. MD4 Message-Digest 875374Sbp Algorithm" in all material mentioning or referencing this software 975374Sbp or this function. 1075374Sbp 1175374Sbp License is also granted to make and use derivative works provided 1275374Sbp that such works are identified as "derived from the RSA Data 1375374Sbp Security, Inc. MD4 Message-Digest Algorithm" in all material 1475374Sbp mentioning or referencing the derived work. 1575374Sbp 1675374Sbp RSA Data Security, Inc. makes no representations concerning either 1775374Sbp the merchantability of this software or the suitability of this 1875374Sbp software for any particular purpose. It is provided "as is" 1975374Sbp without express or implied warranty of any kind. 2075374Sbp 2175374Sbp These notices must be retained in any copies of any part of this 2275374Sbp documentation and/or software. 2375374Sbp */ 2475374Sbp 25116182Sobrien#include <sys/cdefs.h> 26116182Sobrien__FBSDID("$FreeBSD: head/sys/kern/md4c.c 116182 2003-06-11 00:56:59Z obrien $"); 27116182Sobrien 2875374Sbp#include <sys/param.h> 2975374Sbp#include <sys/systm.h> 3075374Sbp#include <sys/md4.h> 3175374Sbp 3275374Sbptypedef unsigned char *POINTER; 3375374Sbptypedef u_int16_t UINT2; 3475374Sbptypedef u_int32_t UINT4; 3575374Sbp 3675374Sbp#define PROTO_LIST(list) list 3775374Sbp 3875374Sbp/* Constants for MD4Transform routine. 3975374Sbp */ 4075374Sbp#define S11 3 4175374Sbp#define S12 7 4275374Sbp#define S13 11 4375374Sbp#define S14 19 4475374Sbp#define S21 3 4575374Sbp#define S22 5 4675374Sbp#define S23 9 4775374Sbp#define S24 13 4875374Sbp#define S31 3 4975374Sbp#define S32 9 5075374Sbp#define S33 11 5175374Sbp#define S34 15 5275374Sbp 5375374Sbpstatic void MD4Transform PROTO_LIST ((UINT4 [4], const unsigned char [64])); 5475374Sbpstatic void Encode PROTO_LIST 5575374Sbp ((unsigned char *, UINT4 *, unsigned int)); 5675374Sbpstatic void Decode PROTO_LIST 5775374Sbp ((UINT4 *, const unsigned char *, unsigned int)); 5875374Sbp 5975374Sbpstatic unsigned char PADDING[64] = { 6075374Sbp 0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6175374Sbp 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6275374Sbp 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 6375374Sbp}; 6475374Sbp 6575374Sbp/* F, G and H are basic MD4 functions. 6675374Sbp */ 6775374Sbp#define F(x, y, z) (((x) & (y)) | ((~x) & (z))) 6875374Sbp#define G(x, y, z) (((x) & (y)) | ((x) & (z)) | ((y) & (z))) 6975374Sbp#define H(x, y, z) ((x) ^ (y) ^ (z)) 7075374Sbp 7175374Sbp/* ROTATE_LEFT rotates x left n bits. 7275374Sbp */ 7375374Sbp#define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n)))) 7475374Sbp 7575374Sbp/* FF, GG and HH are transformations for rounds 1, 2 and 3 */ 7675374Sbp/* Rotation is separate from addition to prevent recomputation */ 7775374Sbp#define FF(a, b, c, d, x, s) { \ 7875374Sbp (a) += F ((b), (c), (d)) + (x); \ 7975374Sbp (a) = ROTATE_LEFT ((a), (s)); \ 8075374Sbp } 8175374Sbp#define GG(a, b, c, d, x, s) { \ 8275374Sbp (a) += G ((b), (c), (d)) + (x) + (UINT4)0x5a827999; \ 8375374Sbp (a) = ROTATE_LEFT ((a), (s)); \ 8475374Sbp } 8575374Sbp#define HH(a, b, c, d, x, s) { \ 8675374Sbp (a) += H ((b), (c), (d)) + (x) + (UINT4)0x6ed9eba1; \ 8775374Sbp (a) = ROTATE_LEFT ((a), (s)); \ 8875374Sbp } 8975374Sbp 9075374Sbp/* MD4 initialization. Begins an MD4 operation, writing a new context. 9175374Sbp */ 9275374Sbpvoid MD4Init (context) 9375374SbpMD4_CTX *context; /* context */ 9475374Sbp{ 9575374Sbp context->count[0] = context->count[1] = 0; 9675374Sbp 9775374Sbp /* Load magic initialization constants. 9875374Sbp */ 9975374Sbp context->state[0] = 0x67452301; 10075374Sbp context->state[1] = 0xefcdab89; 10175374Sbp context->state[2] = 0x98badcfe; 10275374Sbp context->state[3] = 0x10325476; 10375374Sbp} 10475374Sbp 10575374Sbp/* MD4 block update operation. Continues an MD4 message-digest 10675374Sbp operation, processing another message block, and updating the 10775374Sbp context. 10875374Sbp */ 10975374Sbpvoid MD4Update (context, input, inputLen) 11075374SbpMD4_CTX *context; /* context */ 11175374Sbpconst unsigned char *input; /* input block */ 11275374Sbpunsigned int inputLen; /* length of input block */ 11375374Sbp{ 11475374Sbp unsigned int i, index, partLen; 11575374Sbp 11675374Sbp /* Compute number of bytes mod 64 */ 11775374Sbp index = (unsigned int)((context->count[0] >> 3) & 0x3F); 11875374Sbp /* Update number of bits */ 11975374Sbp if ((context->count[0] += ((UINT4)inputLen << 3)) 12075374Sbp < ((UINT4)inputLen << 3)) 12175374Sbp context->count[1]++; 12275374Sbp context->count[1] += ((UINT4)inputLen >> 29); 12375374Sbp 12475374Sbp partLen = 64 - index; 12575374Sbp /* Transform as many times as possible. 12675374Sbp */ 12775374Sbp if (inputLen >= partLen) { 12875374Sbp bcopy(input, &context->buffer[index], partLen); 12975374Sbp MD4Transform (context->state, context->buffer); 13075374Sbp 13175374Sbp for (i = partLen; i + 63 < inputLen; i += 64) 13275374Sbp MD4Transform (context->state, &input[i]); 13375374Sbp 13475374Sbp index = 0; 13575374Sbp } 13675374Sbp else 13775374Sbp i = 0; 13875374Sbp 13975374Sbp /* Buffer remaining input */ 14075374Sbp bcopy(&input[i], &context->buffer[index], inputLen-i); 14175374Sbp} 14275374Sbp 14375374Sbp/* MD4 padding. */ 14475374Sbpvoid MD4Pad (context) 14575374SbpMD4_CTX *context; /* context */ 14675374Sbp{ 14775374Sbp unsigned char bits[8]; 14875374Sbp unsigned int index, padLen; 14975374Sbp 15075374Sbp /* Save number of bits */ 15175374Sbp Encode (bits, context->count, 8); 15275374Sbp 15375374Sbp /* Pad out to 56 mod 64. 15475374Sbp */ 15575374Sbp index = (unsigned int)((context->count[0] >> 3) & 0x3f); 15675374Sbp padLen = (index < 56) ? (56 - index) : (120 - index); 15775374Sbp MD4Update (context, PADDING, padLen); 15875374Sbp 15975374Sbp /* Append length (before padding) */ 16075374Sbp MD4Update (context, bits, 8); 16175374Sbp} 16275374Sbp 16375374Sbp/* MD4 finalization. Ends an MD4 message-digest operation, writing the 16475374Sbp the message digest and zeroizing the context. 16575374Sbp */ 16675374Sbpvoid MD4Final (digest, context) 16775374Sbpunsigned char digest[16]; /* message digest */ 16875374SbpMD4_CTX *context; /* context */ 16975374Sbp{ 17075374Sbp /* Do padding */ 17175374Sbp MD4Pad (context); 17275374Sbp 17375374Sbp /* Store state in digest */ 17475374Sbp Encode (digest, context->state, 16); 17575374Sbp 17675374Sbp /* Zeroize sensitive information. 17775374Sbp */ 17875374Sbp bzero((POINTER)context, sizeof (*context)); 17975374Sbp} 18075374Sbp 18175374Sbp/* MD4 basic transformation. Transforms state based on block. 18275374Sbp */ 18375374Sbpstatic void MD4Transform (state, block) 18475374SbpUINT4 state[4]; 18575374Sbpconst unsigned char block[64]; 18675374Sbp{ 18775374Sbp UINT4 a = state[0], b = state[1], c = state[2], d = state[3], x[16]; 18875374Sbp 18975374Sbp Decode (x, block, 64); 19075374Sbp 19175374Sbp /* Round 1 */ 19275374Sbp FF (a, b, c, d, x[ 0], S11); /* 1 */ 19375374Sbp FF (d, a, b, c, x[ 1], S12); /* 2 */ 19475374Sbp FF (c, d, a, b, x[ 2], S13); /* 3 */ 19575374Sbp FF (b, c, d, a, x[ 3], S14); /* 4 */ 19675374Sbp FF (a, b, c, d, x[ 4], S11); /* 5 */ 19775374Sbp FF (d, a, b, c, x[ 5], S12); /* 6 */ 19875374Sbp FF (c, d, a, b, x[ 6], S13); /* 7 */ 19975374Sbp FF (b, c, d, a, x[ 7], S14); /* 8 */ 20075374Sbp FF (a, b, c, d, x[ 8], S11); /* 9 */ 20175374Sbp FF (d, a, b, c, x[ 9], S12); /* 10 */ 20275374Sbp FF (c, d, a, b, x[10], S13); /* 11 */ 20375374Sbp FF (b, c, d, a, x[11], S14); /* 12 */ 20475374Sbp FF (a, b, c, d, x[12], S11); /* 13 */ 20575374Sbp FF (d, a, b, c, x[13], S12); /* 14 */ 20675374Sbp FF (c, d, a, b, x[14], S13); /* 15 */ 20775374Sbp FF (b, c, d, a, x[15], S14); /* 16 */ 20875374Sbp 20975374Sbp /* Round 2 */ 21075374Sbp GG (a, b, c, d, x[ 0], S21); /* 17 */ 21175374Sbp GG (d, a, b, c, x[ 4], S22); /* 18 */ 21275374Sbp GG (c, d, a, b, x[ 8], S23); /* 19 */ 21375374Sbp GG (b, c, d, a, x[12], S24); /* 20 */ 21475374Sbp GG (a, b, c, d, x[ 1], S21); /* 21 */ 21575374Sbp GG (d, a, b, c, x[ 5], S22); /* 22 */ 21675374Sbp GG (c, d, a, b, x[ 9], S23); /* 23 */ 21775374Sbp GG (b, c, d, a, x[13], S24); /* 24 */ 21875374Sbp GG (a, b, c, d, x[ 2], S21); /* 25 */ 21975374Sbp GG (d, a, b, c, x[ 6], S22); /* 26 */ 22075374Sbp GG (c, d, a, b, x[10], S23); /* 27 */ 22175374Sbp GG (b, c, d, a, x[14], S24); /* 28 */ 22275374Sbp GG (a, b, c, d, x[ 3], S21); /* 29 */ 22375374Sbp GG (d, a, b, c, x[ 7], S22); /* 30 */ 22475374Sbp GG (c, d, a, b, x[11], S23); /* 31 */ 22575374Sbp GG (b, c, d, a, x[15], S24); /* 32 */ 22675374Sbp 22775374Sbp /* Round 3 */ 22875374Sbp HH (a, b, c, d, x[ 0], S31); /* 33 */ 22975374Sbp HH (d, a, b, c, x[ 8], S32); /* 34 */ 23075374Sbp HH (c, d, a, b, x[ 4], S33); /* 35 */ 23175374Sbp HH (b, c, d, a, x[12], S34); /* 36 */ 23275374Sbp HH (a, b, c, d, x[ 2], S31); /* 37 */ 23375374Sbp HH (d, a, b, c, x[10], S32); /* 38 */ 23475374Sbp HH (c, d, a, b, x[ 6], S33); /* 39 */ 23575374Sbp HH (b, c, d, a, x[14], S34); /* 40 */ 23675374Sbp HH (a, b, c, d, x[ 1], S31); /* 41 */ 23775374Sbp HH (d, a, b, c, x[ 9], S32); /* 42 */ 23875374Sbp HH (c, d, a, b, x[ 5], S33); /* 43 */ 23975374Sbp HH (b, c, d, a, x[13], S34); /* 44 */ 24075374Sbp HH (a, b, c, d, x[ 3], S31); /* 45 */ 24175374Sbp HH (d, a, b, c, x[11], S32); /* 46 */ 24275374Sbp HH (c, d, a, b, x[ 7], S33); /* 47 */ 24375374Sbp HH (b, c, d, a, x[15], S34); /* 48 */ 24475374Sbp 24575374Sbp state[0] += a; 24675374Sbp state[1] += b; 24775374Sbp state[2] += c; 24875374Sbp state[3] += d; 24975374Sbp 25075374Sbp /* Zeroize sensitive information. 25175374Sbp */ 25275374Sbp bzero((POINTER)x, sizeof (x)); 25375374Sbp} 25475374Sbp 25575374Sbp/* Encodes input (UINT4) into output (unsigned char). Assumes len is 25675374Sbp a multiple of 4. 25775374Sbp */ 25875374Sbpstatic void Encode (output, input, len) 25975374Sbpunsigned char *output; 26075374SbpUINT4 *input; 26175374Sbpunsigned int len; 26275374Sbp{ 26375374Sbp unsigned int i, j; 26475374Sbp 26575374Sbp for (i = 0, j = 0; j < len; i++, j += 4) { 26675374Sbp output[j] = (unsigned char)(input[i] & 0xff); 26775374Sbp output[j+1] = (unsigned char)((input[i] >> 8) & 0xff); 26875374Sbp output[j+2] = (unsigned char)((input[i] >> 16) & 0xff); 26975374Sbp output[j+3] = (unsigned char)((input[i] >> 24) & 0xff); 27075374Sbp } 27175374Sbp} 27275374Sbp 27375374Sbp/* Decodes input (unsigned char) into output (UINT4). Assumes len is 27475374Sbp a multiple of 4. 27575374Sbp */ 27675374Sbpstatic void Decode (output, input, len) 27775374Sbp 27875374SbpUINT4 *output; 27975374Sbpconst unsigned char *input; 28075374Sbpunsigned int len; 28175374Sbp{ 28275374Sbp unsigned int i, j; 28375374Sbp 28475374Sbp for (i = 0, j = 0; j < len; i++, j += 4) 28575374Sbp output[i] = ((UINT4)input[j]) | (((UINT4)input[j+1]) << 8) | 28675374Sbp (((UINT4)input[j+2]) << 16) | (((UINT4)input[j+3]) << 24); 28775374Sbp} 288