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