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
MD4Print(MDp)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
MD4Init(MDp)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
MDblock(MDp,Xb)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
MD4Update(MDp,X,count)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
MD4Final(buf,MD)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)***********************************/
300