1 /*  $Id: md5.c 4154 2000-10-31 16:28:53Z kondou $
2 **
3 **  RSA Data Security, Inc. MD5 Message-Digest Algorithm
4 **
5 **  The standard MD5 message digest routines, from RSA Data Security, Inc.
6 **  by way of Landon Curt Noll, modified and integrated into INN by Clayton
7 **  O'Neill and then simplified somewhat, converted to INN coding style,
8 **  and commented by Russ Allbery.
9 **
10 **  To form the message digest for a message M:
11 **    (1) Initialize a context buffer md5_context using md5_init
12 **    (2) Call md5_update on md5_context and M
13 **    (3) Call md5_final on md5_context
14 **  The message digest is now in md5_context->digest[0...15].
15 **
16 **  Alternately, just call md5_hash on M, passing it a buffer of at least
17 **  16 bytes into which to put the digest.  md5_hash does the above
18 **  internally for you and is the most convenient interface; the interface
19 **  described above, however, is better when all of the data to hash isn't
20 **  available neatly in a single buffer (such as hashing data aquired a
21 **  block at a time).
22 **
23 **  For information about MD5, see RFC 1321.
24 **
25 **  LANDON CURT NOLL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
26 **  INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS.  IN NO
27 **  EVENT SHALL LANDON CURT NOLL BE LIABLE FOR ANY SPECIAL, INDIRECT OR
28 **  CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF
29 **  USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
30 **  OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
31 **  PERFORMANCE OF THIS SOFTWARE.
32 **
33 **  Copyright (C) 1990, RSA Data Security, Inc.  All rights reserved.
34 **
35 **  License to copy and use this software is granted provided that it is
36 **  identified as the "RSA Data Security, Inc. MD5 Message-Digest Algorithm"
37 **  in all material mentioning or referencing this software or this
38 **  function.
39 **
40 **  License is also granted to make and use derivative works provided that
41 **  such works are identified as "derived from the RSA Data Security,
42 **  Inc. MD5 Message-Digest Algorithm" in all material mentioning or
43 **  referencing the derived work.
44 **
45 **  RSA Data Security, Inc. makes no representations concerning either the
46 **  merchantability of this software or the suitability of this software for
47 **  any particular purpose.  It is provided "as is" without express or
48 **  implied warranty of any kind.
49 **
50 **  These notices must be retained in any copies of any part of this
51 **  documentation and/or software.
52 */
53 
54 /*
55 **  The actual mathematics and cryptography are at the bottom of this file,
56 **  as those parts should be fully debugged and very infrequently changed.
57 **  The core of actual work is done by md5_transform.  The beginning of this
58 **  file contains the infrastructure around the mathematics.
59 */
60 
61 #include "config.h"
62 #include "clibrary.h"
63 #include "inn/md5.h"
64 
65 /* Rotate a 32-bit value left, used by both the MD5 mathematics and by the
66    routine below to byteswap data on big-endian machines. */
67 #define ROT(X, n)       (((X) << (n)) | ((X) >> (32 - (n))))
68 
69 /* Almost zero fill padding, used by md5_final.  The 0x80 is part of the MD5
70    hash algorithm, from RFC 1321 section 3.1:
71 
72      Padding is performed as follows: a single "1" bit is appended to the
73      message, and then "0" bits are appended so that the length in bits of
74      the padded message becomes congruent to 448, modulo 512.  In all, at
75      least one bit and at most 512 bits are appended.
76 
77    Let the compiler zero the remainder of the array for us, guaranteed by
78    ISO C99 6.7.8 paragraph 21.  */
79 static const unsigned char padding[MD5_CHUNKSIZE] = { 0x80, 0 /* 0, ... */ };
80 
81 /* Internal prototypes. */
82 static void md5_transform(uint32_t *, const uint32_t *);
83 static void md5_update_block(struct md5_context *, const unsigned char *,
84                              size_t);
85 
86 /* MD5 requires that input data be treated as words in little-endian byte
87    order.  From RFC 1321 section 2:
88 
89      Similarly, a sequence of bytes can be interpreted as a sequence of
90      32-bit words, where each consecutive group of four bytes is interpreted
91      as a word with the low-order (least significant) byte given first.
92 
93    Input data must therefore be byteswapped on big-endian machines, as must
94    the 16-byte result digest.  Since we have to make a copy of the incoming
95    data anyway to ensure alignment for 4-byte access, we can byteswap it in
96    place. */
97 #if !WORDS_BIGENDIAN
98 # define decode(data)           /* empty */
99 # define encode(data, out)      memcpy((out), (data), MD5_DIGESTSIZE)
100 #else
101 
102 /* The obvious way to do this is to pull single bytes at a time out of the
103    input array and build words from them; this requires three shifts and
104    three Boolean or operations, but it requires four memory reads per word
105    unless the compiler is really smart.  Since we can assume four-byte
106    alignment for the input data, use this optimized routine from J. Touch,
107    USC/ISI.  This requires four shifts, two ands, and two ors, but only one
108    memory read per word. */
109 #define swap(word)              \
110     do {                        \
111         htmp = ROT((word), 16); \
112         ltmp = htmp >> 8;       \
113         htmp &= 0x00ff00ff;     \
114         ltmp &= 0x00ff00ff;     \
115         htmp <<= 8;             \
116         (word) = htmp | ltmp;   \
117     } while (0)
118 
119 /* We process 16 words of data (one MD5 block) of data at a time, completely
120    unrolling the loop manually since it should allow the compiler to take
121    advantage of pipelining and parallel arithmetic units. */
122 static void
decode(uint32_t * data)123 decode(uint32_t *data)
124 {
125     uint32_t ltmp, htmp;
126 
127     swap(data[ 0]); swap(data[ 1]); swap(data[ 2]); swap(data[ 3]);
128     swap(data[ 4]); swap(data[ 5]); swap(data[ 6]); swap(data[ 7]);
129     swap(data[ 8]); swap(data[ 9]); swap(data[10]); swap(data[11]);
130     swap(data[12]); swap(data[13]); swap(data[14]); swap(data[15]);
131 }
132 
133 /* Used by md5_final to generate the final digest.  The digest is not
134    guaranteed to be aligned for 4-byte access but we are allowed to be
135    destructive, so byteswap first and then copy the result over. */
136 static void
encode(uint32_t * data,unsigned char * out)137 encode(uint32_t *data, unsigned char *out)
138 {
139     uint32_t ltmp, htmp;
140 
141     swap(data[0]);
142     swap(data[1]);
143     swap(data[2]);
144     swap(data[3]);
145     memcpy(out, data, MD5_DIGESTSIZE);
146 }
147 
148 #endif /* WORDS_BIGENDIAN */
149 
150 
151 /*
152 **  That takes care of the preliminaries; now the real fun begins.  The
153 **  initialization function for a struct md5_context; set lengths to zero
154 **  and initialize our working buffer with the magic constants (c.f. RFC
155 **  1321 section 3.3).
156 */
157 void
md5_init(struct md5_context * context)158 md5_init(struct md5_context *context)
159 {
160     context->buf[0] = 0x67452301U;
161     context->buf[1] = 0xefcdab89U;
162     context->buf[2] = 0x98badcfeU;
163     context->buf[3] = 0x10325476U;
164 
165     context->count[0] = 0;
166     context->count[1] = 0;
167     context->datalen  = 0;
168 }
169 
170 
171 /*
172 **  The workhorse function, called for each chunk of data.  Update the
173 **  message-digest context to account for the presence of each of the
174 **  characters data[0 .. count - 1] in the message whose digest is being
175 **  computed.  Accepts any length of data; all whole blocks are processed
176 **  and the remaining data is buffered for later processing by either
177 **  another call to md5_update or by md5_final.
178 */
179 void
md5_update(struct md5_context * context,const unsigned char * data,size_t count)180 md5_update(struct md5_context *context, const unsigned char *data,
181            size_t count)
182 {
183     unsigned int datalen = context->datalen;
184     unsigned int left;
185     size_t high_count, low_count, used;
186 
187     /* Update the count of hashed bytes.  The machinations here are to do
188        the right thing on a platform where size_t > 32 bits without causing
189        compiler warnings on platforms where it's 32 bits.  RFC 1321 section
190        3.2 says:
191 
192          A 64-bit representation of b (the length of the message before the
193          padding bits were added) is appended to the result of the previous
194          step.  In the unlikely event that b is greater than 2^64, then only
195          the low-order 64 bits of b are used.
196 
197        so we can just ignore the higher bits of count if size_t is larger
198        than 64 bits.  (Think ahead!)  If size_t is only 32 bits, the
199        compiler should kill the whole if statement as dead code. */
200     if (sizeof(count) > 4) {
201         high_count = count >> 31;
202         context->count[1] += (high_count >> 1) & 0xffffffffU;
203     }
204 
205     /* Now deal with count[0].  Add in the low 32 bits of count and
206        increment count[1] if count[0] wraps.  Isn't unsigned arithmetic
207        cool? */
208     low_count = count & 0xffffffffU;
209     context->count[0] += low_count;
210     if (context->count[0] < low_count)
211         context->count[1]++;
212 
213     /* See if we already have some data queued.  If so, try to complete a
214        block and then deal with it first.  If the new data still doesn't
215        fill the buffer, add it to the buffer and return.  Otherwise,
216        transform that block and update data and count to account for the
217        data we've already used. */
218     if (datalen > 0) {
219         left = MD5_CHUNKSIZE - datalen;
220         if (left > count) {
221             memcpy(context->in.byte + datalen, data, count);
222             context->datalen += count;
223             return;
224         } else {
225             memcpy(context->in.byte + datalen, data, left);
226             decode(context->in.word);
227             md5_transform(context->buf, context->in.word);
228             data += left;
229             count -= left;
230             context->datalen = 0;
231         }
232     }
233 
234     /* If we have a block of data or more left, pass the rest off to
235        md5_update_block to deal with all of the full blocks available. */
236     if (count >= MD5_CHUNKSIZE) {
237         md5_update_block(context, data, count);
238         used = (count / MD5_CHUNKSIZE) * MD5_CHUNKSIZE;
239         data += used;
240         count -= used;
241     }
242 
243     /* If there's anything left, buffer it until we can complete a block or
244        for md5_final to deal with. */
245     if (count > 0) {
246         memcpy(context->in.byte, data, count);
247         context->datalen = count;
248     }
249 }
250 
251 
252 /*
253 **  Update the message-digest context to account for the presence of each of
254 **  the characters data[0 .. count - 1] in the message whose digest is being
255 **  computed, except that we only deal with full blocks of data.  The data
256 **  is processed one block at a time, and partial blocks at the end are
257 **  ignored (they're dealt with by md5_update, which calls this routine.
258 **
259 **  Note that we always make a copy of the input data into an array of
260 **  4-byte values.  If our input data were guaranteed to be aligned for
261 **  4-byte access, we could just use the input buffer directly on
262 **  little-endian machines, and in fact this implementation used to do that.
263 **  However, a requirement to align isn't always easily detectable, even by
264 **  configure (an Alpha running Tru64 will appear to allow unaligned
265 **  accesses, but will spew errors to the terminal if you do it).  On top of
266 **  that, even when it's allowed, unaligned access is quite frequently
267 **  slower; we're about to do four reads of each word of the input data for
268 **  the calculations, so doing one additional copy of the data up-front is
269 **  probably worth it.
270 */
271 static void
md5_update_block(struct md5_context * context,const unsigned char * data,size_t count)272 md5_update_block(struct md5_context *context, const unsigned char *data,
273                  size_t count)
274 {
275     uint32_t in[MD5_CHUNKWORDS];
276 
277     /* Process data in MD5_CHUNKSIZE blocks. */
278     while (count >= MD5_CHUNKSIZE) {
279         memcpy(in, data, MD5_CHUNKSIZE);
280         decode(in);
281         md5_transform(context->buf, in);
282         data += MD5_CHUNKSIZE;
283         count -= MD5_CHUNKSIZE;
284     }
285 }
286 
287 
288 /*
289 **  Terminates the message-digest computation, accounting for any final
290 **  trailing data and adding the message length to the hashed data, and ends
291 **  with the desired message digest in context->digest[0...15].
292 */
293 void
md5_final(struct md5_context * context)294 md5_final(struct md5_context *context)
295 {
296     unsigned int pad_needed, left;
297     uint32_t count[2];
298     uint32_t *countloc;
299 
300     /* Save the count before appending the padding. */
301     count[0] = context->count[0];
302     count[1] = context->count[1];
303 
304     /* Pad the final block of data.  RFC 1321 section 3.1:
305 
306          The message is "padded" (extended) so that its length (in bits) is
307          congruent to 448, modulo 512.  That is, the message is extended so
308          that it is just 64 bits shy of being a multiple of 512 bits long.
309          Padding is always performed, even if the length of the message is
310          already congruent to 448, modulo 512.
311 
312        The 64 bits (two words) left are for the 64-bit count of bits
313        hashed.  We'll need at most 64 bytes of padding; lucky that the
314        padding array is exactly that size! */
315     left = context->datalen;
316     pad_needed = (left < 64 - 8) ? (64 - 8 - left) : (128 - 8 - left);
317     md5_update(context, padding, pad_needed);
318 
319     /* Append length in bits and transform.  Note that we cheat slightly
320        here to save a few operations on big-endian machines; the algorithm
321        says that we should add the length, in little-endian byte order, to
322        the last block of data.  We'd then transform it into big-endian order
323        on a big-endian machine.  But the count is *already* in big-endian
324        order on a big-endian machine, so effectively we'd be byteswapping it
325        twice.  Instead, add it to the block after doing byte swapping on the
326        rest.
327 
328        Note that we've been counting *bytes*, but the algorithm demands the
329        length in *bits*, so shift things around a bit. */
330     decode(context->in.word);
331     countloc = &context->in.word[MD5_CHUNKWORDS - 2];
332     countloc[0] = count[0] << 3;
333     countloc[1] = (count[1] << 3) | (count[0] >> 29);
334     md5_transform(context->buf, context->in.word);
335 
336     /* Recover the final digest.  Whoo-hoo, we're done! */
337     encode(context->buf, context->digest);
338 }
339 
340 
341 /*
342 **  A convenience wrapper around md5_init, md5_update, and md5_final.  Takes
343 **  a pointer to a buffer of data, the length of the data, and a pointer to
344 **  a buffer of at least 16 bytes into which to write the message digest.
345 */
346 void
md5_hash(const unsigned char * data,size_t length,unsigned char * digest)347 md5_hash(const unsigned char *data, size_t length, unsigned char *digest)
348 {
349     struct md5_context context;
350 
351     md5_init(&context);
352     md5_update(&context, data, length);
353     md5_final(&context);
354     memcpy(digest, context.digest, MD5_DIGESTSIZE);
355 }
356 
357 
358 /*
359 **  Look out, here comes the math.
360 **
361 **  There are no user-serviceable parts below this point unless you know
362 **  quite a bit about MD5 or optimization of integer math.  The only
363 **  function remaining, down below, is md5_transform; the rest of this is
364 **  setting up macros to make that function more readable.
365 **
366 **  The F, G, H and I are basic MD5 functions.  The following identity saves
367 **  one boolean operation.
368 **
369 **  F: (((x) & (y)) | (~(x) & (z))) == ((z) ^ ((x) & ((y) ^ (z))))
370 **  G: (((x) & (z)) | ((y) & ~(z))) == ((y) ^ ((z) & ((x) ^ (y))))
371 */
372 #define F(x, y, z)      ((z) ^ ((x) & ((y) ^ (z))))
373 #define G(x, y, z)      ((y) ^ ((z) & ((x) ^ (y))))
374 #define H(x, y, z)      ((x) ^ (y) ^ (z))
375 #define I(x, y, z)      ((y) ^ ((x) | (~z)))
376 
377 /*
378 **  FF, GG, HH, and II transformations for rounds 1, 2, 3, and 4.  Rotation
379 **  is separate from addition to prevent recomputation.  S?? are the shift
380 **  values for each round.
381 */
382 #define S11 7
383 #define S12 12
384 #define S13 17
385 #define S14 22
386 #define FF(a, b, c, d, x, s, ac)                                \
387     {                                                           \
388         (a) += F((b), (c), (d)) + (x) + (uint32_t) (ac);        \
389         (a) = ROT((a), (s));                                    \
390         (a) += (b);                                             \
391     }
392 
393 #define S21 5
394 #define S22 9
395 #define S23 14
396 #define S24 20
397 #define GG(a, b, c, d, x, s, ac)                                \
398     {                                                           \
399         (a) += G((b), (c), (d)) + (x) + (uint32_t) (ac);        \
400         (a) = ROT((a), (s));                                    \
401         (a) += (b);                                             \
402     }
403 
404 #define S31 4
405 #define S32 11
406 #define S33 16
407 #define S34 23
408 #define HH(a, b, c, d, x, s, ac)                                \
409     {                                                           \
410         (a) += H((b), (c), (d)) + (x) + (uint32_t) (ac);        \
411         (a) = ROT((a), (s));                                    \
412         (a) += (b);                                             \
413     }
414 
415 #define S41 6
416 #define S42 10
417 #define S43 15
418 #define S44 21
419 #define II(a, b, c, d, x, s, ac)                                \
420     {                                                           \
421         (a) += I((b), (c), (d)) + (x) + (uint32_t) (ac);        \
422         (a) = ROT((a), (s));                                    \
423         (a) += (b);                                             \
424     }
425 
426 /*
427 **  Basic MD5 step.  Transforms buf based on in.
428 */
429 static void
md5_transform(uint32_t * buf,const uint32_t * in)430 md5_transform(uint32_t *buf, const uint32_t *in)
431 {
432     uint32_t a = buf[0];
433     uint32_t b = buf[1];
434     uint32_t c = buf[2];
435     uint32_t d = buf[3];
436 
437     /* Round 1 */
438     FF(a, b, c, d, in[ 0], S11, 3614090360UL); /*  1 */
439     FF(d, a, b, c, in[ 1], S12, 3905402710UL); /*  2 */
440     FF(c, d, a, b, in[ 2], S13,  606105819UL); /*  3 */
441     FF(b, c, d, a, in[ 3], S14, 3250441966UL); /*  4 */
442     FF(a, b, c, d, in[ 4], S11, 4118548399UL); /*  5 */
443     FF(d, a, b, c, in[ 5], S12, 1200080426UL); /*  6 */
444     FF(c, d, a, b, in[ 6], S13, 2821735955UL); /*  7 */
445     FF(b, c, d, a, in[ 7], S14, 4249261313UL); /*  8 */
446     FF(a, b, c, d, in[ 8], S11, 1770035416UL); /*  9 */
447     FF(d, a, b, c, in[ 9], S12, 2336552879UL); /* 10 */
448     FF(c, d, a, b, in[10], S13, 4294925233UL); /* 11 */
449     FF(b, c, d, a, in[11], S14, 2304563134UL); /* 12 */
450     FF(a, b, c, d, in[12], S11, 1804603682UL); /* 13 */
451     FF(d, a, b, c, in[13], S12, 4254626195UL); /* 14 */
452     FF(c, d, a, b, in[14], S13, 2792965006UL); /* 15 */
453     FF(b, c, d, a, in[15], S14, 1236535329UL); /* 16 */
454 
455     /* Round 2 */
456     GG(a, b, c, d, in[ 1], S21, 4129170786UL); /* 17 */
457     GG(d, a, b, c, in[ 6], S22, 3225465664UL); /* 18 */
458     GG(c, d, a, b, in[11], S23,  643717713UL); /* 19 */
459     GG(b, c, d, a, in[ 0], S24, 3921069994UL); /* 20 */
460     GG(a, b, c, d, in[ 5], S21, 3593408605UL); /* 21 */
461     GG(d, a, b, c, in[10], S22,   38016083UL); /* 22 */
462     GG(c, d, a, b, in[15], S23, 3634488961UL); /* 23 */
463     GG(b, c, d, a, in[ 4], S24, 3889429448UL); /* 24 */
464     GG(a, b, c, d, in[ 9], S21,  568446438UL); /* 25 */
465     GG(d, a, b, c, in[14], S22, 3275163606UL); /* 26 */
466     GG(c, d, a, b, in[ 3], S23, 4107603335UL); /* 27 */
467     GG(b, c, d, a, in[ 8], S24, 1163531501UL); /* 28 */
468     GG(a, b, c, d, in[13], S21, 2850285829UL); /* 29 */
469     GG(d, a, b, c, in[ 2], S22, 4243563512UL); /* 30 */
470     GG(c, d, a, b, in[ 7], S23, 1735328473UL); /* 31 */
471     GG(b, c, d, a, in[12], S24, 2368359562UL); /* 32 */
472 
473     /* Round 3 */
474     HH(a, b, c, d, in[ 5], S31, 4294588738UL); /* 33 */
475     HH(d, a, b, c, in[ 8], S32, 2272392833UL); /* 34 */
476     HH(c, d, a, b, in[11], S33, 1839030562UL); /* 35 */
477     HH(b, c, d, a, in[14], S34, 4259657740UL); /* 36 */
478     HH(a, b, c, d, in[ 1], S31, 2763975236UL); /* 37 */
479     HH(d, a, b, c, in[ 4], S32, 1272893353UL); /* 38 */
480     HH(c, d, a, b, in[ 7], S33, 4139469664UL); /* 39 */
481     HH(b, c, d, a, in[10], S34, 3200236656UL); /* 40 */
482     HH(a, b, c, d, in[13], S31,  681279174UL); /* 41 */
483     HH(d, a, b, c, in[ 0], S32, 3936430074UL); /* 42 */
484     HH(c, d, a, b, in[ 3], S33, 3572445317UL); /* 43 */
485     HH(b, c, d, a, in[ 6], S34,   76029189UL); /* 44 */
486     HH(a, b, c, d, in[ 9], S31, 3654602809UL); /* 45 */
487     HH(d, a, b, c, in[12], S32, 3873151461UL); /* 46 */
488     HH(c, d, a, b, in[15], S33,  530742520UL); /* 47 */
489     HH(b, c, d, a, in[ 2], S34, 3299628645UL); /* 48 */
490 
491     /* Round 4 */
492     II(a, b, c, d, in[ 0], S41, 4096336452UL); /* 49 */
493     II(d, a, b, c, in[ 7], S42, 1126891415UL); /* 50 */
494     II(c, d, a, b, in[14], S43, 2878612391UL); /* 51 */
495     II(b, c, d, a, in[ 5], S44, 4237533241UL); /* 52 */
496     II(a, b, c, d, in[12], S41, 1700485571UL); /* 53 */
497     II(d, a, b, c, in[ 3], S42, 2399980690UL); /* 54 */
498     II(c, d, a, b, in[10], S43, 4293915773UL); /* 55 */
499     II(b, c, d, a, in[ 1], S44, 2240044497UL); /* 56 */
500     II(a, b, c, d, in[ 8], S41, 1873313359UL); /* 57 */
501     II(d, a, b, c, in[15], S42, 4264355552UL); /* 58 */
502     II(c, d, a, b, in[ 6], S43, 2734768916UL); /* 59 */
503     II(b, c, d, a, in[13], S44, 1309151649UL); /* 60 */
504     II(a, b, c, d, in[ 4], S41, 4149444226UL); /* 61 */
505     II(d, a, b, c, in[11], S42, 3174756917UL); /* 62 */
506     II(c, d, a, b, in[ 2], S43,  718787259UL); /* 63 */
507     II(b, c, d, a, in[ 9], S44, 3951481745UL); /* 64 */
508 
509     buf[0] += a;
510     buf[1] += b;
511     buf[2] += c;
512     buf[3] += d;
513 }
514