pppd/md4.c

   1 /*
   2 ** ********************************************************************
   3 ** md4.c -- Implementation of MD4 Message Digest Algorithm           **
   4 ** Updated: 2/16/90 by Ronald L. Rivest                              **
   5 ** (C) 1990 RSA Data Security, Inc.                                  **
   6 ** ********************************************************************
   7 */
   8
   9 /*
  10 ** To use MD4:
  11 **   -- Include md4.h in your program
  12 **   -- Declare an MDstruct MD to hold the state of the digest
  13 **          computation.
  14 **   -- Initialize MD using MDbegin(&MD)
  15 **   -- For each full block (64 bytes) X you wish to process, call
  16 **          MD4Update(&MD,X,512)
  17 **      (512 is the number of bits in a full block.)
  18 **   -- For the last block (less than 64 bytes) you wish to process,
  19 **          MD4Update(&MD,X,n)
  20 **      where n is the number of bits in the partial block. A partial
  21 **      block terminates the computation, so every MD computation
  22 **      should terminate by processing a partial block, even if it
  23 **      has n = 0.
  24 **   -- The message digest is available in MD.buffer[0] ...
  25 **      MD.buffer[3].  (Least-significant byte of each word
  26 **      should be output first.)
  27 **   -- You can print out the digest using MDprint(&MD)
  28 */
  29
  30 /* Implementation notes:
  31 ** This implementation assumes that ints are 32-bit quantities.
  32 */
  33
  34 #define TRUE  1
  35 #define FALSE 0
  36
  37 /* Compile-time includes
  38 */
  39 #include <stdio.h>
  40 #include "md4.h"
  41 #include "pppd.h"
  42
  43 /* Compile-time declarations of MD4 "magic constants".
  44 */
  45 #define I0  0x67452301       /* Initial values for MD buffer */
  46 #define I1  0xefcdab89
  47 #define I2  0x98badcfe
  48 #define I3  0x10325476
  49 #define C2  013240474631     /* round 2 constant = sqrt(2) in octal */
  50 #define C3  015666365641     /* round 3 constant = sqrt(3) in octal */
  51 /* C2 and C3 are from Knuth, The Art of Programming, Volume 2
  52 ** (Seminumerical Algorithms), Second Edition (1981), Addison-Wesley.
  53 ** Table 2, page 660.
  54 */
  55
  56 #define fs1  3               /* round 1 shift amounts */
  57 #define fs2  7
  58 #define fs3 11
  59 #define fs4 19
  60 #define gs1  3               /* round 2 shift amounts */
  61 #define gs2  5
  62 #define gs3  9
  63 #define gs4 13
  64 #define hs1  3               /* round 3 shift amounts */
  65 #define hs2  9
  66 #define hs3 11
  67 #define hs4 15
  68
  69 /* Compile-time macro declarations for MD4.
  70 ** Note: The "rot" operator uses the variable "tmp".
  71 ** It assumes tmp is declared as unsigned int, so that the >>
  72 ** operator will shift in zeros rather than extending the sign bit.
  73 */
  74 #define f(X,Y,Z)             ((X&Y) | ((~X)&Z))
  75 #define g(X,Y,Z)             ((X&Y) | (X&Z) | (Y&Z))
  76 #define h(X,Y,Z)             (X^Y^Z)
  77 #define rot(X,S)             (tmp=X,(tmp<<S) | (tmp>>(32-S)))
  78 #define ff(A,B,C,D,i,s)      A = rot((A + f(B,C,D) + X[i]),s)
  79 #define gg(A,B,C,D,i,s)      A = rot((A + g(B,C,D) + X[i] + C2),s)
  80 #define hh(A,B,C,D,i,s)      A = rot((A + h(B,C,D) + X[i] + C3),s)
  81
  82 /* MD4print(MDp)
  83 ** Print message digest buffer MDp as 32 hexadecimal digits.
  84 ** Order is from low-order byte of buffer[0] to high-order byte of
  85 ** buffer[3].
  86 ** Each byte is printed with high-order hexadecimal digit first.
  87 ** This is a user-callable routine.
  88 */
  89 void
  90 MD4Print(MDp)
  91 MD4_CTX *MDp;
  92 {
  93   int i,j;
  94   for (i=0;i<4;i++)
  95     for (j=0;j<32;j=j+8)
  96       printf("%02x",(MDp->buffer[i]>>j) & 0xFF);
  97 }
  98
  99 /* MD4Init(MDp)
 100 ** Initialize message digest buffer MDp.
 101 ** This is a user-callable routine.
 102 */
 103 void
 104 MD4Init(MDp)
 105 MD4_CTX *MDp;
 106 {
 107   int i;
 108   MDp->buffer[0] = I0;
 109   MDp->buffer[1] = I1;
 110   MDp->buffer[2] = I2;
 111   MDp->buffer[3] = I3;
 112   for (i=0;i<8;i++) MDp->count[i] = 0;
 113   MDp->done = 0;
 114 }
 115
 116 /* MDblock(MDp,X)
 117 ** Update message digest buffer MDp->buffer using 16-word data block X.
 118 ** Assumes all 16 words of X are full of data.
 119 ** Does not update MDp->count.
 120 ** This routine is not user-callable.
 121 */
 122 static void
 123 MDblock(MDp,Xb)
 124 MD4_CTX *MDp;
 125 unsigned char *Xb;
 126 {
 127   register unsigned int tmp, A, B, C, D;
 128   unsigned int X[16];
 129   int i;
 130
 131   for (i = 0; i < 16; ++i) {
 132     X[i] = Xb[0] + (Xb[1] << 8) + (Xb[2] << 16) + (Xb[3] << 24);
 133     Xb += 4;
 134   }
 135
 136   A = MDp->buffer[0];
 137   B = MDp->buffer[1];
 138   C = MDp->buffer[2];
 139   D = MDp->buffer[3];
 140   /* Update the message digest buffer */
 141   ff(A , B , C , D ,  0 , fs1); /* Round 1 */
 142   ff(D , A , B , C ,  1 , fs2);
 143   ff(C , D , A , B ,  2 , fs3);
 144   ff(B , C , D , A ,  3 , fs4);
 145   ff(A , B , C , D ,  4 , fs1);
 146   ff(D , A , B , C ,  5 , fs2);
 147   ff(C , D , A , B ,  6 , fs3);
 148   ff(B , C , D , A ,  7 , fs4);
 149   ff(A , B , C , D ,  8 , fs1);
 150   ff(D , A , B , C ,  9 , fs2);
 151   ff(C , D , A , B , 10 , fs3);
 152   ff(B , C , D , A , 11 , fs4);
 153   ff(A , B , C , D , 12 , fs1);
 154   ff(D , A , B , C , 13 , fs2);
 155   ff(C , D , A , B , 14 , fs3);
 156   ff(B , C , D , A , 15 , fs4);
 157   gg(A , B , C , D ,  0 , gs1); /* Round 2 */
 158   gg(D , A , B , C ,  4 , gs2);
 159   gg(C , D , A , B ,  8 , gs3);
 160   gg(B , C , D , A , 12 , gs4);
 161   gg(A , B , C , D ,  1 , gs1);
 162   gg(D , A , B , C ,  5 , gs2);
 163   gg(C , D , A , B ,  9 , gs3);
 164   gg(B , C , D , A , 13 , gs4);
 165   gg(A , B , C , D ,  2 , gs1);
 166   gg(D , A , B , C ,  6 , gs2);
 167   gg(C , D , A , B , 10 , gs3);
 168   gg(B , C , D , A , 14 , gs4);
 169   gg(A , B , C , D ,  3 , gs1);
 170   gg(D , A , B , C ,  7 , gs2);
 171   gg(C , D , A , B , 11 , gs3);
 172   gg(B , C , D , A , 15 , gs4);
 173   hh(A , B , C , D ,  0 , hs1); /* Round 3 */
 174   hh(D , A , B , C ,  8 , hs2);
 175   hh(C , D , A , B ,  4 , hs3);
 176   hh(B , C , D , A , 12 , hs4);
 177   hh(A , B , C , D ,  2 , hs1);
 178   hh(D , A , B , C , 10 , hs2);
 179   hh(C , D , A , B ,  6 , hs3);
 180   hh(B , C , D , A , 14 , hs4);
 181   hh(A , B , C , D ,  1 , hs1);
 182   hh(D , A , B , C ,  9 , hs2);
 183   hh(C , D , A , B ,  5 , hs3);
 184   hh(B , C , D , A , 13 , hs4);
 185   hh(A , B , C , D ,  3 , hs1);
 186   hh(D , A , B , C , 11 , hs2);
 187   hh(C , D , A , B ,  7 , hs3);
 188   hh(B , C , D , A , 15 , hs4);
 189   MDp->buffer[0] += A;
 190   MDp->buffer[1] += B;
 191   MDp->buffer[2] += C;
 192   MDp->buffer[3] += D;
 193 }
 194
 195 /* MD4Update(MDp,X,count)
 196 ** Input: X -- a pointer to an array of unsigned characters.
 197 **        count -- the number of bits of X to use.
 198 **          (if not a multiple of 8, uses high bits of last byte.)
 199 ** Update MDp using the number of bits of X given by count.
 200 ** This is the basic input routine for an MD4 user.
 201 ** The routine completes the MD computation when count < 512, so
 202 ** every MD computation should end with one call to MD4Update with a
 203 ** count less than 512.  A call with count 0 will be ignored if the
 204 ** MD has already been terminated (done != 0), so an extra call with
 205 ** count 0 can be given as a "courtesy close" to force termination
 206 ** if desired.
 207 */
 208 void
 209 MD4Update(MDp,X,count)
 210 MD4_CTX *MDp;
 211 unsigned char *X;
 212 unsigned int count;
 213 {
 214   unsigned int i, tmp, bit, byte, mask;
 215   unsigned char XX[64];
 216   unsigned char *p;
 217
 218   /* return with no error if this is a courtesy close with count
 219   ** zero and MDp->done is true.
 220   */
 221   if (count == 0 && MDp->done) return;
 222   /* check to see if MD is already done and report error */
 223   if (MDp->done)
 224   { printf("\nError: MD4Update MD already done."); return; }
 225
 226   /* Add count to MDp->count */
 227   tmp = count;
 228   p = MDp->count;
 229   while (tmp)
 230   { tmp += *p;
 231   *p++ = tmp;
 232   tmp = tmp >> 8;
 233   }
 234
 235   /* Process data */
 236   if (count == 512)
 237   { /* Full block of data to handle */
 238     MDblock(MDp,X);
 239   }
 240   else if (count > 512) /* Check for count too large */
 241   {
 242     printf("\nError: MD4Update called with illegal count value %d.",
 243            count);
 244     return;
 245   }
 246   else /* partial block -- must be last block so finish up */
 247   {
 248     /* Find out how many bytes and residual bits there are */
 249     byte = count >> 3;
 250     bit =  count & 7;
 251     /* Copy X into XX since we need to modify it */
 252     if (count)
 253       for (i=0;i<=byte;i++) XX[i] = X[i];
 254     for (i=byte+1;i<64;i++) XX[i] = 0;
 255     /* Add padding '1' bit and low-order zeros in last byte */
 256     mask = 1 << (7 - bit);
 257     XX[byte] = (XX[byte] | mask) & ~( mask - 1);
 258     /* If room for bit count, finish up with this block */
 259     if (byte <= 55)
 260     {
 261       for (i=0;i<8;i++) XX[56+i] = MDp->count[i];
 262       MDblock(MDp,XX);
 263     }
 264     else /* need to do two blocks to finish up */
 265     {
 266       MDblock(MDp,XX);
 267       for (i=0;i<56;i++) XX[i] = 0;
 268       for (i=0;i<8;i++)  XX[56+i] = MDp->count[i];
 269       MDblock(MDp,XX);
 270     }
 271     /* Set flag saying we're done with MD computation */
 272     MDp->done = 1;
 273   }
 274 }
 275
 276 /*
 277 ** Finish up MD4 computation and return message digest.
 278 */
 279 void
 280 MD4Final(buf, MD)
 281 unsigned char *buf;
 282 MD4_CTX *MD;
 283 {
 284   int i, j;
 285   unsigned int w;
 286
 287   MD4Update(MD, NULL, 0);
 288   for (i = 0; i < 4; ++i) {
 289     w = MD->buffer[i];
 290     for (j = 0; j < 4; ++j) {
 291       *buf++ = w;
 292       w >>= 8;
 293     }
 294   }
 295 }
 296
 297 /*
 298 ** End of md4.c
 299 ****************************(cut)***********************************/