1
2
3 /* Copyright (C) 1990, RSA Data Security, Inc. All rights reserved.
4 *
5 * License to copy and use this software is granted provided that it
6 * is identified as the "RSA Data Security, Inc. MD4 Message-Digest
7 * Algorithm" in all material mentioning or referencing this software
8 * or this function.
9 *
10 * License is also granted to make and use derivative works provided
11 * that such works are identified as "derived from the RSA Data
12 * Security, Inc. MD4 Message-Digest Algorithm" in all material
13 * mentioning or referencing the derived work.
14 *
15 * RSA Data Security, Inc. makes no representations concerning either
16 * the merchantability of this software or the suitability of this
17 * software for any particular purpose. It is provided "as is"
18 * without express or implied warranty of any kind.
19 *
20 * These notices must be retained in any copies of any part of this
21 * documentation and/or software.
22 */
23
24
25 /*
26 * md4.c -- Implementation of MD4 Message Digest Algorithm
27 * Updated: 2/16/90 by Ronald L. Rivest
28 * (C) 1990 RSA Data Security, Inc.
29 *
30 * Portability nits fixed and reformatted - 2/12/91 Phil Karn
31 */
32
33 /*
34 * To use MD4:
35 * -- Include md4.h in your program
36 * -- Declare an MDstruct MD to hold the state of the digest computation.
37 * -- Initialize MD using MDbegin(&MD)
38 * -- For each full block (64 bytes) X you wish to process, call
39 * MDupdate(&MD,X,512)
40 * (512 is the number of bits in a full block.)
41 * -- For the last block (less than 64 bytes) you wish to process,
42 * MDupdate(&MD,X,n)
43 * where n is the number of bits in the partial block. A partial
44 * block terminates the computation, so every MD computation should
45 * terminate by processing a partial block, even if it has n = 0.
46 * -- The message digest is available in MD.buffer[0] ... MD.buffer[3].
47 * (Least-significant byte of each word should be output first.)
48 * -- You can print out the digest using MDprint(&MD)
49 */
50
51 /* Implementation notes:
52 * This implementation assumes that longs are 32-bit quantities.
53 * If the machine stores the least-significant byte of an long in the
54 * least-addressed byte (eg., VAX and 8086), then LOWBYTEFIRST should be
55 * set to TRUE. Otherwise (eg., SUNS), LOWBYTEFIRST should be set to
56 * FALSE. Note that on machines with LOWBYTEFIRST FALSE the routine
57 * MDupdate modifies has a side-effect on its input array (the order of bytes
58 * in each word are reversed). If this is undesired a call to MDreverse(X) can
59 * reverse the bytes of X back into order after each call to MDupdate.
60 */
61 #define TRUE 1
62 #define FALSE 0
63
64 #if (defined(__MSDOS__) || defined(MPU8086) || defined(MPU8080) \
65 || defined(vax) || defined (MIPSEL))
66 #define LOWBYTEFIRST TRUE /* Low order bytes are first in memory */
67 #else /* Almost all other machines are big-endian */
68 #define LOWBYTEFIRST FALSE
69 #endif
70
71
72 /* Compile-time includes */
73 #include <stdio.h>
74 #include "md4.h"
75
76 /* Compile-time declarations of MD4 ``magic constants'' */
77 #define I0 0x67452301 /* Initial values for MD buffer */
78 #define I1 0xefcdab89
79 #define I2 0x98badcfe
80 #define I3 0x10325476
81 #define C2 013240474631 /* round 2 constant = sqrt(2) in octal */
82 #define C3 015666365641 /* round 3 constant = sqrt(3) in octal */
83 /* C2 and C3 are from Knuth, The Art of Programming, Volume 2
84 * (Seminumerical Algorithms), Second Edition (1981), Addison-Wesley.
85 * Table 2, page 660.
86 */
87 #define fs1 3 /* round 1 shift amounts */
88 #define fs2 7
89 #define fs3 11
90 #define fs4 19
91 #define gs1 3 /* round 2 shift amounts */
92 #define gs2 5
93 #define gs3 9
94 #define gs4 13
95 #define hs1 3 /* round 3 shift amounts */
96 #define hs2 9
97 #define hs3 11
98 #define hs4 15
99
100
101 /* Compile-time macro declarations for MD4.
102 * Note: The ``rot'' operator uses the variable ``tmp''.
103 * It assumes tmp is declared as unsigned long, so that the >>
104 * operator will shift in zeros rather than extending the sign bit.
105 */
106 #define f(X,Y,Z) ((X&Y) | ((~X)&Z))
107 #define g(X,Y,Z) ((X&Y) | (X&Z) | (Y&Z))
108 #define h(X,Y,Z) (X^Y^Z)
109 #define rot(X,S) (tmp=X,(tmp<<S) | (tmp>>(32-S)))
110 #define ff(A,B,C,D,i,s) A = rot((A + f(B,C,D) + X[i]),s)
111 #define gg(A,B,C,D,i,s) A = rot((A + g(B,C,D) + X[i] + C2),s)
112 #define hh(A,B,C,D,i,s) A = rot((A + h(B,C,D) + X[i] + C3),s)
113
114 void MDreverse __ARGS((unsigned long *X));
115
116 /* MDprint(MDp)
117 * Print message digest buffer MDp as 32 hexadecimal digits.
118 * Order is from low-order byte of buffer[0] to high-order byte of buffer[3].
119 * Each byte is printed with high-order hexadecimal digit first.
120 * This is a user-callable routine.
121 */
122 void
MDprint(MDp)123 MDprint(MDp)
124 MDptr MDp;
125 {
126 int i,j;
127
128 for(i=0;i<4;i++)
129 for(j=0;j<32;j=j+8)
130 printf("%02lx",(MDp->buffer[i]>>j) & 0xFF);
131 }
132
133 /* MDbegin(MDp)
134 * Initialize message digest buffer MDp.
135 * This is a user-callable routine.
136 */
137 void
MDbegin(MDp)138 MDbegin(MDp)
139 MDptr MDp;
140 {
141 int i;
142
143 MDp->buffer[0] = I0;
144 MDp->buffer[1] = I1;
145 MDp->buffer[2] = I2;
146 MDp->buffer[3] = I3;
147 for(i=0;i<8;i++)
148 MDp->count[i] = 0;
149 MDp->done = 0;
150 }
151
152 /* MDreverse(X)
153 * Reverse the byte-ordering of every long in X.
154 * Assumes X is an array of 16 longs.
155 * The macro revx reverses the byte-ordering of the next word of X.
156 */
157 #define revx { t = (*X << 16) | (*X >> 16); \
158 *X++ = ((t & 0xFF00FF00) >> 8) | ((t & 0x00FF00FF) << 8); }
159 void
MDreverse(X)160 MDreverse(X)
161 unsigned long *X;
162 {
163 register unsigned long t;
164
165 revx;
166 revx;
167 revx;
168 revx;
169 revx;
170 revx;
171 revx;
172 revx;
173 revx;
174 revx;
175 revx;
176 revx;
177 revx;
178 revx;
179 revx;
180 revx;
181
182 }
183
184 /* MDblock(MDp,X)
185 * Update message digest buffer MDp->buffer using 16-word data block X.
186 * Assumes all 16 words of X are full of data.
187 * Does not update MDp->count.
188 * This routine is not user-callable.
189 */
190 static void
MDblock(MDp,X)191 MDblock(MDp,X)
192 MDptr MDp;
193 unsigned long *X;
194 {
195 register unsigned long tmp, A, B, C, D;
196
197 #if LOWBYTEFIRST == FALSE
198 MDreverse(X);
199 #endif
200 A = MDp->buffer[0];
201 B = MDp->buffer[1];
202 C = MDp->buffer[2];
203 D = MDp->buffer[3];
204 /* Update the message digest buffer */
205 ff(A,B,C,D,0,fs1); /* Round 1 */
206 ff(D,A,B,C,1,fs2);
207 ff(C,D,A,B,2,fs3);
208 ff(B,C,D,A,3,fs4);
209 ff(A,B,C,D,4,fs1);
210 ff(D,A,B,C,5,fs2);
211 ff(C,D,A,B,6,fs3);
212 ff(B,C,D,A,7,fs4);
213 ff(A,B,C,D,8,fs1);
214 ff(D,A,B,C,9,fs2);
215 ff(C,D,A,B,10,fs3);
216 ff(B,C,D,A,11,fs4);
217 ff(A,B,C,D,12,fs1);
218 ff(D,A,B,C,13,fs2);
219 ff(C,D,A,B,14,fs3);
220 ff(B,C,D,A,15,fs4);
221 gg(A,B,C,D,0,gs1); /* Round 2 */
222 gg(D,A,B,C,4,gs2);
223 gg(C,D,A,B,8,gs3);
224 gg(B,C,D,A,12,gs4);
225 gg(A,B,C,D,1,gs1);
226 gg(D,A,B,C,5,gs2);
227 gg(C,D,A,B,9,gs3);
228 gg(B,C,D,A,13,gs4);
229 gg(A,B,C,D,2,gs1);
230 gg(D,A,B,C,6,gs2);
231 gg(C,D,A,B,10,gs3);
232 gg(B,C,D,A,14,gs4);
233 gg(A,B,C,D,3,gs1);
234 gg(D,A,B,C,7,gs2);
235 gg(C,D,A,B,11,gs3);
236 gg(B,C,D,A,15,gs4);
237 hh(A,B,C,D,0,hs1); /* Round 3 */
238 hh(D,A,B,C,8,hs2);
239 hh(C,D,A,B,4,hs3);
240 hh(B,C,D,A,12,hs4);
241 hh(A,B,C,D,2,hs1);
242 hh(D,A,B,C,10,hs2);
243 hh(C,D,A,B,6,hs3);
244 hh(B,C,D,A,14,hs4);
245 hh(A,B,C,D,1,hs1);
246 hh(D,A,B,C,9,hs2);
247 hh(C,D,A,B,5,hs3);
248 hh(B,C,D,A,13,hs4);
249 hh(A,B,C,D,3,hs1);
250 hh(D,A,B,C,11,hs2);
251 hh(C,D,A,B,7,hs3);
252 hh(B,C,D,A,15,hs4);
253 MDp->buffer[0] += A;
254 MDp->buffer[1] += B;
255 MDp->buffer[2] += C;
256 MDp->buffer[3] += D;
257 }
258
259 /* MDupdate(MDp,X,count)
260 * Input: MDp -- an MDptr
261 * X -- a pointer to an array of unsigned characters.
262 * count -- the number of bits of X to use.
263 * (if not a multiple of 8, uses high bits of last byte.)
264 * Update MDp using the number of bits of X given by count.
265 * This is the basic input routine for an MD4 user.
266 * The routine completes the MD computation when count < 512, so
267 * every MD computation should end with one call to MDupdate with a
268 * count less than 512. A call with count 0 will be ignored if the
269 * MD has already been terminated (done != 0), so an extra call with count
270 * 0 can be given as a ``courtesy close'' to force termination if desired.
271 */
272 void
MDupdate(MDp,X,count)273 MDupdate(MDp,X,count)
274 MDptr MDp;
275 unsigned char *X;
276 unsigned int count;
277 {
278 int i,bit,byte,mask;
279 unsigned long tmp;
280 unsigned char XX[64];
281 unsigned char *p;
282
283 /* return with no error if this is a courtesy close with count
284 * zero and MDp->done is true.
285 */
286 if(count == 0 && MDp->done)
287 return;
288 /* check to see if MD is already done and report error */
289 if(MDp->done){
290 printf("\nError: MDupdate MD already done.");
291 return;
292 }
293 /* Add count to MDp->count */
294 tmp = count;
295 p = MDp->count;
296 while(tmp){
297 tmp += *p;
298 *p++ = tmp;
299 tmp = tmp >> 8;
300 }
301 /* Process data */
302 if(count == 512){
303 /* Full block of data to handle */
304 MDblock(MDp,(unsigned long *)X);
305 } else if(count > 512){
306 /* Check for count too large */
307 printf("\nError: MDupdate called with illegal count value %ld.",count);
308 return;
309 } else {
310 /* partial block -- must be last block so finish up
311 * Find out how many bytes and residual bits there are
312 */
313 byte = count >> 3;
314 bit = count & 7;
315 /* Copy X into XX since we need to modify it */
316 for(i=0;i<=byte;i++)
317 XX[i] = X[i];
318 for(i=byte+1;i<64;i++)
319 XX[i] = 0;
320 /* Add padding '1' bit and low-order zeros in last byte */
321 mask = 1 << (7 - bit);
322 XX[byte] = (XX[byte] | mask) & ~( mask - 1);
323 /* If room for bit count, finish up with this block */
324 if(byte <= 55){
325 for(i=0;i<8;i++)
326 XX[56+i] = MDp->count[i];
327 MDblock(MDp,(unsigned long *)XX);
328 } else {
329 /* need to do two blocks to finish up */
330 MDblock(MDp,(unsigned long *)XX);
331 for(i=0;i<56;i++)
332 XX[i] = 0;
333 for(i=0;i<8;i++)
334 XX[56+i] = MDp->count[i];
335 MDblock(MDp,(unsigned long *)XX);
336 }
337 /* Set flag saying we're done with MD computation */
338 MDp->done = 1;
339 }
340 }
341 /* End of md4.c */
342