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