md4.c

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