md4.c

   1 /*
   2    Copyright (c) 1995-1998 by Cisco systems, Inc.
   3
   4    Permission to use, copy, modify, and distribute this software for
   5    any purpose and without fee is hereby granted, provided that this
   6    copyright and permission notice appear on all copies of the
   7    software and supporting documentation, the name of Cisco Systems,
   8    Inc. not be used in advertising or publicity pertaining to
   9    distribution of the program without specific prior permission, and
  10    notice be given in supporting documentation that modification,
  11    copying and distribution is by permission of Cisco Systems, Inc.
  12
  13    Cisco Systems, Inc. makes no representations about the suitability
  14    of this software for any purpose.  THIS SOFTWARE IS PROVIDED ``AS
  15    IS'' AND WITHOUT ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING,
  16    WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
  17    FITNESS FOR A PARTICULAR PURPOSE.
  18 */
  19
  20 /* MD4C.C - RSA Data Security, Inc., MD4 message-digest algorithm
  21  * $Id$
  22  */
  23
  24 /* Copyright (C) 1990-2, RSA Data Security, Inc. All rights reserved.
  25
  26    License to copy and use this software is granted provided that it
  27    is identified as the "RSA Data Security, Inc. MD4 Message-Digest
  28    Algorithm" in all material mentioning or referencing this software
  29    or this function.
  30
  31    License is also granted to make and use derivative works provided
  32    that such works are identified as "derived from the RSA Data
  33    Security, Inc. MD4 Message-Digest Algorithm" in all material
  34    mentioning or referencing the derived work.
  35
  36    RSA Data Security, Inc. makes no representations concerning either
  37    the merchantability of this software or the suitability of this
  38    software for any particular purpose. It is provided "as is"
  39    without express or implied warranty of any kind.
  40
  41    These notices must be retained in any copies of any part of this
  42    documentation and/or software.
  43  */
  44
  45
  46 #include <string.h>
  47 #include "md4.h"
  48 /*
  49 #include "master.h"
  50 #include <ciscolib.h>
  51 */
  52
  53 typedef unsigned char *POINTER;
  54 typedef unsigned short int UINT2;
  55 typedef unsigned long int UINT4;
  56
  57 #define PROTO_LIST(list) ()
  58 #define const
  59
  60 /* Constants for MD4Transform routine.
  61  */
  62 #define S11 3
  63 #define S12 7
  64 #define S13 11
  65 #define S14 19
  66 #define S21 3
  67 #define S22 5
  68 #define S23 9
  69 #define S24 13
  70 #define S31 3
  71 #define S32 9
  72 #define S33 11
  73 #define S34 15
  74
  75 static void MD4Transform PROTO_LIST ((UINT4 [4], const unsigned char [64]));
  76 static void Encode PROTO_LIST
  77   ((unsigned char *, UINT4 *, unsigned int));
  78 static void Decode PROTO_LIST
  79   ((UINT4 *, const unsigned char *, unsigned int));
  80
  81 static unsigned char PADDING[64] = {
  82   0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  83   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  84   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
  85 };
  86
  87 /* F, G and H are basic MD4 functions.
  88  */
  89 #define F(x, y, z) (((x) & (y)) | ((~x) & (z)))
  90 #define G(x, y, z) (((x) & (y)) | ((x) & (z)) | ((y) & (z)))
  91 #define H(x, y, z) ((x) ^ (y) ^ (z))
  92
  93 /* ROTATE_LEFT rotates x left n bits.
  94  */
  95 #define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n))))
  96
  97 /* FF, GG and HH are transformations for rounds 1, 2 and 3 */
  98 /* Rotation is separate from addition to prevent recomputation */
  99 #define FF(a, b, c, d, x, s) { \
 100     (a) += F ((b), (c), (d)) + (x); \
 101     (a) = ROTATE_LEFT ((a), (s)); \
 102   }
 103 #define GG(a, b, c, d, x, s) { \
 104     (a) += G ((b), (c), (d)) + (x) + (UINT4)0x5a827999; \
 105     (a) = ROTATE_LEFT ((a), (s)); \
 106   }
 107 #define HH(a, b, c, d, x, s) { \
 108     (a) += H ((b), (c), (d)) + (x) + (UINT4)0x6ed9eba1; \
 109     (a) = ROTATE_LEFT ((a), (s)); \
 110   }
 111
 112 /* MD4 initialization. Begins an MD4 operation, writing a new context.
 113  */
 114 void MD4Init (context)
 115 MD4_CTX *context;                                        /* context */
 116 {
 117   context->count[0] = context->count[1] = 0;
 118
 119   /* Load magic initialization constants.
 120    */
 121   context->state[0] = 0x67452301;
 122   context->state[1] = 0xefcdab89;
 123   context->state[2] = 0x98badcfe;
 124   context->state[3] = 0x10325476;
 125 }
 126
 127 /* MD4 block update operation. Continues an MD4 message-digest
 128      operation, processing another message block, and updating the
 129      context.
 130  */
 131 void MD4Update (context, input, inputLen)
 132 MD4_CTX *context;                                        /* context */
 133 const unsigned char *input;                                /* input block */
 134 unsigned int inputLen;                     /* length of input block */
 135 {
 136   unsigned int i, index, partLen;
 137
 138   /* Compute number of bytes mod 64 */
 139   index = (unsigned int)((context->count[0] >> 3) & 0x3F);
 140   /* Update number of bits */
 141   if ((context->count[0] += ((UINT4)inputLen << 3))
 142       < ((UINT4)inputLen << 3))
 143     context->count[1]++;
 144   context->count[1] += ((UINT4)inputLen >> 29);
 145
 146   partLen = 64 - index;
 147   /* Transform as many times as possible.
 148    */
 149   if (inputLen >= partLen) {
 150     memcpy
 151       ((POINTER)&context->buffer[index], (POINTER)input, partLen);
 152     MD4Transform (context->state, context->buffer);
 153
 154     for (i = partLen; i + 63 < inputLen; i += 64)
 155       MD4Transform (context->state, &input[i]);
 156
 157     index = 0;
 158   }
 159   else
 160     i = 0;
 161
 162   /* Buffer remaining input */
 163   memcpy
 164     ((POINTER)&context->buffer[index], (POINTER)&input[i],
 165      inputLen-i);
 166 }
 167
 168 /* MD4 finalization. Ends an MD4 message-digest operation, writing the
 169      the message digest and zeroizing the context.
 170  */
 171 void MD4Final (digest, context)
 172 unsigned char digest[16];                         /* message digest */
 173 MD4_CTX *context;                                        /* context */
 174 {
 175   unsigned char bits[8];
 176   unsigned int index, padLen;
 177
 178   /* Save number of bits */
 179   Encode (bits, context->count, 8);
 180
 181   /* Pad out to 56 mod 64.
 182    */
 183   index = (unsigned int)((context->count[0] >> 3) & 0x3f);
 184   padLen = (index < 56) ? (56 - index) : (120 - index);
 185   MD4Update (context, PADDING, padLen);
 186
 187   /* Append length (before padding) */
 188   MD4Update (context, bits, 8);
 189   /* Store state in digest */
 190   Encode (digest, context->state, 16);
 191
 192   /* Zeroize sensitive information.
 193    */
 194   memset ((POINTER)context, 0, sizeof (*context));
 195 }
 196
 197 /* MD4 basic transformation. Transforms state based on block.
 198  */
 199 static void MD4Transform (state, block)
 200 UINT4 state[4];
 201 const unsigned char block[64];
 202 {
 203   UINT4 a = state[0], b = state[1], c = state[2], d = state[3], x[16];
 204
 205   Decode (x, block, 64);
 206
 207   /* Round 1 */
 208   FF (a, b, c, d, x[ 0], S11); /* 1 */
 209   FF (d, a, b, c, x[ 1], S12); /* 2 */
 210   FF (c, d, a, b, x[ 2], S13); /* 3 */
 211   FF (b, c, d, a, x[ 3], S14); /* 4 */
 212   FF (a, b, c, d, x[ 4], S11); /* 5 */
 213   FF (d, a, b, c, x[ 5], S12); /* 6 */
 214   FF (c, d, a, b, x[ 6], S13); /* 7 */
 215   FF (b, c, d, a, x[ 7], S14); /* 8 */
 216   FF (a, b, c, d, x[ 8], S11); /* 9 */
 217   FF (d, a, b, c, x[ 9], S12); /* 10 */
 218   FF (c, d, a, b, x[10], S13); /* 11 */
 219   FF (b, c, d, a, x[11], S14); /* 12 */
 220   FF (a, b, c, d, x[12], S11); /* 13 */
 221   FF (d, a, b, c, x[13], S12); /* 14 */
 222   FF (c, d, a, b, x[14], S13); /* 15 */
 223   FF (b, c, d, a, x[15], S14); /* 16 */
 224
 225   /* Round 2 */
 226   GG (a, b, c, d, x[ 0], S21); /* 17 */
 227   GG (d, a, b, c, x[ 4], S22); /* 18 */
 228   GG (c, d, a, b, x[ 8], S23); /* 19 */
 229   GG (b, c, d, a, x[12], S24); /* 20 */
 230   GG (a, b, c, d, x[ 1], S21); /* 21 */
 231   GG (d, a, b, c, x[ 5], S22); /* 22 */
 232   GG (c, d, a, b, x[ 9], S23); /* 23 */
 233   GG (b, c, d, a, x[13], S24); /* 24 */
 234   GG (a, b, c, d, x[ 2], S21); /* 25 */
 235   GG (d, a, b, c, x[ 6], S22); /* 26 */
 236   GG (c, d, a, b, x[10], S23); /* 27 */
 237   GG (b, c, d, a, x[14], S24); /* 28 */
 238   GG (a, b, c, d, x[ 3], S21); /* 29 */
 239   GG (d, a, b, c, x[ 7], S22); /* 30 */
 240   GG (c, d, a, b, x[11], S23); /* 31 */
 241   GG (b, c, d, a, x[15], S24); /* 32 */
 242
 243   /* Round 3 */
 244   HH (a, b, c, d, x[ 0], S31); /* 33 */
 245   HH (d, a, b, c, x[ 8], S32); /* 34 */
 246   HH (c, d, a, b, x[ 4], S33); /* 35 */
 247   HH (b, c, d, a, x[12], S34); /* 36 */
 248   HH (a, b, c, d, x[ 2], S31); /* 37 */
 249   HH (d, a, b, c, x[10], S32); /* 38 */
 250   HH (c, d, a, b, x[ 6], S33); /* 39 */
 251   HH (b, c, d, a, x[14], S34); /* 40 */
 252   HH (a, b, c, d, x[ 1], S31); /* 41 */
 253   HH (d, a, b, c, x[ 9], S32); /* 42 */
 254   HH (c, d, a, b, x[ 5], S33); /* 43 */
 255   HH (b, c, d, a, x[13], S34); /* 44 */
 256   HH (a, b, c, d, x[ 3], S31); /* 45 */
 257   HH (d, a, b, c, x[11], S32); /* 46 */
 258   HH (c, d, a, b, x[ 7], S33); /* 47 */
 259   HH (b, c, d, a, x[15], S34); /* 48 */
 260
 261   state[0] += a;
 262   state[1] += b;
 263   state[2] += c;
 264   state[3] += d;
 265
 266   /* Zeroize sensitive information.
 267    */
 268   memset ((POINTER)x, 0, sizeof (x));
 269 }
 270
 271 /* Encodes input (UINT4) into output (unsigned char). Assumes len is
 272      a multiple of 4.
 273  */
 274 static void Encode (output, input, len)
 275 unsigned char *output;
 276 UINT4 *input;
 277 unsigned int len;
 278 {
 279   unsigned int i, j;
 280
 281   for (i = 0, j = 0; j < len; i++, j += 4) {
 282     output[j] = (unsigned char)(input[i] & 0xff);
 283     output[j+1] = (unsigned char)((input[i] >> 8) & 0xff);
 284     output[j+2] = (unsigned char)((input[i] >> 16) & 0xff);
 285     output[j+3] = (unsigned char)((input[i] >> 24) & 0xff);
 286   }
 287 }
 288
 289 /* Decodes input (unsigned char) into output (UINT4). Assumes len is
 290      a multiple of 4.
 291  */
 292 static void Decode (output, input, len)
 293
 294 UINT4 *output;
 295 const unsigned char *input;
 296 unsigned int len;
 297 {
 298   unsigned int i, j;
 299
 300   for (i = 0, j = 0; j < len; i++, j += 4)
 301     output[i] = ((UINT4)input[j]) | (((UINT4)input[j+1]) << 8) |
 302       (((UINT4)input[j+2]) << 16) | (((UINT4)input[j+3]) << 24);
 303 }