md4c.c revision 139804
1179193Sjb/* MD4C.C - RSA Data Security, Inc., MD4 message-digest algorithm 2179193Sjb */ 3179193Sjb 4179193Sjb/*- 5179193Sjb Copyright (C) 1990-2, RSA Data Security, Inc. All rights reserved. 6179193Sjb 7179193Sjb License to copy and use this software is granted provided that it 8179193Sjb is identified as the "RSA Data Security, Inc. MD4 Message-Digest 9179193Sjb Algorithm" in all material mentioning or referencing this software 10179193Sjb or this function. 11179193Sjb 12179193Sjb License is also granted to make and use derivative works provided 13179193Sjb that such works are identified as "derived from the RSA Data 14179193Sjb Security, Inc. MD4 Message-Digest Algorithm" in all material 15179193Sjb mentioning or referencing the derived work. 16179193Sjb 17179193Sjb RSA Data Security, Inc. makes no representations concerning either 18179193Sjb the merchantability of this software or the suitability of this 19179193Sjb software for any particular purpose. It is provided "as is" 20179469Sjb without express or implied warranty of any kind. 21179469Sjb 22179193Sjb These notices must be retained in any copies of any part of this 23179193Sjb documentation and/or software. 24179193Sjb */ 25265234Spfg 26265234Spfg#include <sys/cdefs.h> 27265234Spfg__FBSDID("$FreeBSD: head/sys/kern/md4c.c 139804 2005-01-06 23:35:40Z imp $"); 28179193Sjb 29179193Sjb#include <sys/param.h> 30179193Sjb#include <sys/systm.h> 31179193Sjb#include <sys/md4.h> 32179193Sjb 33179193Sjbtypedef unsigned char *POINTER; 34179193Sjbtypedef u_int16_t UINT2; 35179193Sjbtypedef u_int32_t UINT4; 36179193Sjb 37179193Sjb#define PROTO_LIST(list) list 38179193Sjb 39179193Sjb/* Constants for MD4Transform routine. 40179193Sjb */ 41179193Sjb#define S11 3 42179193Sjb#define S12 7 43179193Sjb#define S13 11 44179193Sjb#define S14 19 45179193Sjb#define S21 3 46179193Sjb#define S22 5 47179193Sjb#define S23 9 48179193Sjb#define S24 13 49179193Sjb#define S31 3 50179193Sjb#define S32 9 51179193Sjb#define S33 11 52179193Sjb#define S34 15 53179193Sjb 54179193Sjbstatic void MD4Transform PROTO_LIST ((UINT4 [4], const unsigned char [64])); 55179193Sjbstatic void Encode PROTO_LIST 56179193Sjb ((unsigned char *, UINT4 *, unsigned int)); 57179193Sjbstatic void Decode PROTO_LIST 58179193Sjb ((UINT4 *, const unsigned char *, unsigned int)); 59179193Sjb 60179193Sjbstatic unsigned char PADDING[64] = { 61179193Sjb 0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 62179193Sjb 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 63179193Sjb 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 64179193Sjb}; 65179193Sjb 66179193Sjb/* F, G and H are basic MD4 functions. 67179193Sjb */ 68179193Sjb#define F(x, y, z) (((x) & (y)) | ((~x) & (z))) 69179193Sjb#define G(x, y, z) (((x) & (y)) | ((x) & (z)) | ((y) & (z))) 70179198Sjb#define H(x, y, z) ((x) ^ (y) ^ (z)) 71179198Sjb 72179198Sjb/* ROTATE_LEFT rotates x left n bits. 73179193Sjb */ 74179193Sjb#define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n)))) 75179193Sjb 76179193Sjb/* FF, GG and HH are transformations for rounds 1, 2 and 3 */ 77179198Sjb/* Rotation is separate from addition to prevent recomputation */ 78179193Sjb#define FF(a, b, c, d, x, s) { \ 79179193Sjb (a) += F ((b), (c), (d)) + (x); \ 80179198Sjb (a) = ROTATE_LEFT ((a), (s)); \ 81179193Sjb } 82179193Sjb#define GG(a, b, c, d, x, s) { \ 83179198Sjb (a) += G ((b), (c), (d)) + (x) + (UINT4)0x5a827999; \ 84179193Sjb (a) = ROTATE_LEFT ((a), (s)); \ 85179198Sjb } 86179193Sjb#define HH(a, b, c, d, x, s) { \ 87179193Sjb (a) += H ((b), (c), (d)) + (x) + (UINT4)0x6ed9eba1; \ 88179193Sjb (a) = ROTATE_LEFT ((a), (s)); \ 89179193Sjb } 90179198Sjb 91179193Sjb/* MD4 initialization. Begins an MD4 operation, writing a new context. 92179193Sjb */ 93179198Sjbvoid MD4Init (context) 94179193SjbMD4_CTX *context; /* context */ 95179198Sjb{ 96179193Sjb context->count[0] = context->count[1] = 0; 97179193Sjb 98179198Sjb /* Load magic initialization constants. 99179193Sjb */ 100179198Sjb context->state[0] = 0x67452301; 101179193Sjb context->state[1] = 0xefcdab89; 102179193Sjb context->state[2] = 0x98badcfe; 103179198Sjb context->state[3] = 0x10325476; 104179193Sjb} 105179198Sjb 106179193Sjb/* MD4 block update operation. Continues an MD4 message-digest 107179193Sjb operation, processing another message block, and updating the 108179198Sjb context. 109179193Sjb */ 110179193Sjbvoid MD4Update (context, input, inputLen) 111179193SjbMD4_CTX *context; /* context */ 112179193Sjbconst unsigned char *input; /* input block */ 113179198Sjbunsigned int inputLen; /* length of input block */ 114179198Sjb{ 115179469Sjb unsigned int i, index, partLen; 116179198Sjb 117254268Smarkj /* Compute number of bytes mod 64 */ 118179198Sjb index = (unsigned int)((context->count[0] >> 3) & 0x3F); 119179198Sjb /* Update number of bits */ 120179198Sjb if ((context->count[0] += ((UINT4)inputLen << 3)) 121179198Sjb < ((UINT4)inputLen << 3)) 122179198Sjb context->count[1]++; 123179198Sjb context->count[1] += ((UINT4)inputLen >> 29); 124179198Sjb 125192853Ssson partLen = 64 - index; 126179198Sjb /* Transform as many times as possible. 127179198Sjb */ 128179198Sjb if (inputLen >= partLen) { 129179198Sjb bcopy(input, &context->buffer[index], partLen); 130179198Sjb MD4Transform (context->state, context->buffer); 131179198Sjb 132179198Sjb for (i = partLen; i + 63 < inputLen; i += 64) 133179193Sjb MD4Transform (context->state, &input[i]); 134179193Sjb 135179193Sjb index = 0; 136179193Sjb } 137179193Sjb else 138179193Sjb i = 0; 139179193Sjb 140179193Sjb /* Buffer remaining input */ 141179193Sjb bcopy(&input[i], &context->buffer[index], inputLen-i); 142179193Sjb} 143179193Sjb 144179193Sjb/* MD4 padding. */ 145179193Sjbvoid MD4Pad (context) 146179193SjbMD4_CTX *context; /* context */ 147179193Sjb{ 148179193Sjb unsigned char bits[8]; 149179193Sjb unsigned int index, padLen; 150179193Sjb 151179193Sjb /* Save number of bits */ 152179193Sjb Encode (bits, context->count, 8); 153179193Sjb 154179193Sjb /* Pad out to 56 mod 64. 155179193Sjb */ 156264796Smarkj index = (unsigned int)((context->count[0] >> 3) & 0x3f); 157179193Sjb padLen = (index < 56) ? (56 - index) : (120 - index); 158179193Sjb MD4Update (context, PADDING, padLen); 159179193Sjb 160237817Spfg /* Append length (before padding) */ 161179193Sjb MD4Update (context, bits, 8); 162179193Sjb} 163179193Sjb 164179193Sjb/* MD4 finalization. Ends an MD4 message-digest operation, writing the 165179193Sjb the message digest and zeroizing the context. 166179193Sjb */ 167179193Sjbvoid MD4Final (digest, context) 168179193Sjbunsigned char digest[16]; /* message digest */ 169179193SjbMD4_CTX *context; /* context */ 170179193Sjb{ 171179193Sjb /* Do padding */ 172179193Sjb MD4Pad (context); 173179193Sjb 174179193Sjb /* Store state in digest */ 175179193Sjb Encode (digest, context->state, 16); 176179193Sjb 177179193Sjb /* Zeroize sensitive information. 178179193Sjb */ 179179193Sjb bzero((POINTER)context, sizeof (*context)); 180179193Sjb} 181179193Sjb 182179193Sjb/* MD4 basic transformation. Transforms state based on block. 183179193Sjb */ 184179193Sjbstatic void MD4Transform (state, block) 185248983SpfgUINT4 state[4]; 186179193Sjbconst unsigned char block[64]; 187179193Sjb{ 188179193Sjb UINT4 a = state[0], b = state[1], c = state[2], d = state[3], x[16]; 189179193Sjb 190179193Sjb Decode (x, block, 64); 191179193Sjb 192179193Sjb /* Round 1 */ 193179193Sjb FF (a, b, c, d, x[ 0], S11); /* 1 */ 194179193Sjb FF (d, a, b, c, x[ 1], S12); /* 2 */ 195179193Sjb FF (c, d, a, b, x[ 2], S13); /* 3 */ 196179193Sjb FF (b, c, d, a, x[ 3], S14); /* 4 */ 197179193Sjb FF (a, b, c, d, x[ 4], S11); /* 5 */ 198179193Sjb FF (d, a, b, c, x[ 5], S12); /* 6 */ 199179193Sjb FF (c, d, a, b, x[ 6], S13); /* 7 */ 200179193Sjb FF (b, c, d, a, x[ 7], S14); /* 8 */ 201179198Sjb FF (a, b, c, d, x[ 8], S11); /* 9 */ 202179193Sjb FF (d, a, b, c, x[ 9], S12); /* 10 */ 203179198Sjb FF (c, d, a, b, x[10], S13); /* 11 */ 204179198Sjb FF (b, c, d, a, x[11], S14); /* 12 */ 205179193Sjb FF (a, b, c, d, x[12], S11); /* 13 */ 206179193Sjb FF (d, a, b, c, x[13], S12); /* 14 */ 207248983Spfg FF (c, d, a, b, x[14], S13); /* 15 */ 208179193Sjb FF (b, c, d, a, x[15], S14); /* 16 */ 209179198Sjb 210179198Sjb /* Round 2 */ 211179193Sjb GG (a, b, c, d, x[ 0], S21); /* 17 */ 212179193Sjb GG (d, a, b, c, x[ 4], S22); /* 18 */ 213179193Sjb GG (c, d, a, b, x[ 8], S23); /* 19 */ 214179193Sjb GG (b, c, d, a, x[12], S24); /* 20 */ 215179193Sjb GG (a, b, c, d, x[ 1], S21); /* 21 */ 216179193Sjb GG (d, a, b, c, x[ 5], S22); /* 22 */ 217179198Sjb GG (c, d, a, b, x[ 9], S23); /* 23 */ 218179193Sjb GG (b, c, d, a, x[13], S24); /* 24 */ 219179198Sjb GG (a, b, c, d, x[ 2], S21); /* 25 */ 220179193Sjb GG (d, a, b, c, x[ 6], S22); /* 26 */ 221179193Sjb GG (c, d, a, b, x[10], S23); /* 27 */ 222179193Sjb GG (b, c, d, a, x[14], S24); /* 28 */ 223179193Sjb GG (a, b, c, d, x[ 3], S21); /* 29 */ 224179193Sjb GG (d, a, b, c, x[ 7], S22); /* 30 */ 225179193Sjb GG (c, d, a, b, x[11], S23); /* 31 */ 226179193Sjb GG (b, c, d, a, x[15], S24); /* 32 */ 227179193Sjb 228179193Sjb /* Round 3 */ 229179193Sjb HH (a, b, c, d, x[ 0], S31); /* 33 */ 230179193Sjb HH (d, a, b, c, x[ 8], S32); /* 34 */ 231179193Sjb HH (c, d, a, b, x[ 4], S33); /* 35 */ 232179193Sjb HH (b, c, d, a, x[12], S34); /* 36 */ 233179193Sjb HH (a, b, c, d, x[ 2], S31); /* 37 */ 234268572Spfg HH (d, a, b, c, x[10], S32); /* 38 */ 235179193Sjb HH (c, d, a, b, x[ 6], S33); /* 39 */ 236179198Sjb HH (b, c, d, a, x[14], S34); /* 40 */ 237179198Sjb HH (a, b, c, d, x[ 1], S31); /* 41 */ 238179198Sjb HH (d, a, b, c, x[ 9], S32); /* 42 */ 239179198Sjb HH (c, d, a, b, x[ 5], S33); /* 43 */ 240242723Sjhibbits HH (b, c, d, a, x[13], S34); /* 44 */ 241179198Sjb HH (a, b, c, d, x[ 3], S31); /* 45 */ 242179198Sjb HH (d, a, b, c, x[11], S32); /* 46 */ 243254309Smarkj HH (c, d, a, b, x[ 7], S33); /* 47 */ 244254813Smarkj HH (b, c, d, a, x[15], S34); /* 48 */ 245179198Sjb 246179193Sjb state[0] += a; 247179193Sjb state[1] += b; 248179193Sjb state[2] += c; 249179193Sjb state[3] += d; 250179193Sjb 251179193Sjb /* Zeroize sensitive information. 252179193Sjb */ 253179193Sjb bzero((POINTER)x, sizeof (x)); 254179193Sjb} 255179193Sjb 256179193Sjb/* Encodes input (UINT4) into output (unsigned char). Assumes len is 257179193Sjb a multiple of 4. 258179193Sjb */ 259179193Sjbstatic void Encode (output, input, len) 260179193Sjbunsigned char *output; 261179193SjbUINT4 *input; 262179193Sjbunsigned int len; 263179193Sjb{ 264179193Sjb unsigned int i, j; 265179193Sjb 266179193Sjb for (i = 0, j = 0; j < len; i++, j += 4) { 267179193Sjb output[j] = (unsigned char)(input[i] & 0xff); 268179193Sjb output[j+1] = (unsigned char)((input[i] >> 8) & 0xff); 269179193Sjb output[j+2] = (unsigned char)((input[i] >> 16) & 0xff); 270179193Sjb output[j+3] = (unsigned char)((input[i] >> 24) & 0xff); 271179193Sjb } 272179193Sjb} 273179193Sjb 274179193Sjb/* Decodes input (unsigned char) into output (UINT4). Assumes len is 275179193Sjb a multiple of 4. 276179193Sjb */ 277179193Sjbstatic void Decode (output, input, len) 278179193Sjb 279179193SjbUINT4 *output; 280179193Sjbconst unsigned char *input; 281179198Sjbunsigned int len; 282179198Sjb{ 283179198Sjb unsigned int i, j; 284179198Sjb 285179198Sjb for (i = 0, j = 0; j < len; i++, j += 4) 286179198Sjb output[i] = ((UINT4)input[j]) | (((UINT4)input[j+1]) << 8) | 287179198Sjb (((UINT4)input[j+2]) << 16) | (((UINT4)input[j+3]) << 24); 288179198Sjb} 289179198Sjb