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