]> the.earth.li Git - onak.git/blob - md5.c
Improve handling of colliding 64-bit key IDs
[onak.git] / md5.c
1 /* Functions to compute MD5 message digest of files or memory blocks.
2    according to the definition of MD5 in RFC 1321 from April 1992.
3    Copyright (C) 1995,1996,1997,1999,2000,2001 Free Software Foundation, Inc.
4    This file is part of the GNU C Library.
5
6    The GNU C Library is free software; you can redistribute it and/or
7    modify it under the terms of the GNU Lesser General Public
8    License as published by the Free Software Foundation; either
9    version 2.1 of the License, or (at your option) any later version.
10
11    The GNU C Library is distributed in the hope that it will be useful,
12    but WITHOUT ANY WARRANTY; without even the implied warranty of
13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14    Lesser General Public License for more details.
15
16    You should have received a copy of the GNU Lesser General Public
17    License along with the GNU C Library; if not, write to the Free
18    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
19    02111-1307 USA.  */
20
21 /* Written by Ulrich Drepper <drepper@gnu.ai.mit.edu>, 1995.  */
22
23 #include "build-config.h"
24
25 #include <sys/types.h>
26
27 #include <stdlib.h>
28 #include <string.h>
29
30 #include "md5.h"
31
32 #ifdef WORDS_BIGENDIAN
33 # define SWAP(n)                                                        \
34     (((n) << 24) | (((n) & 0xff00) << 8) | (((n) >> 8) & 0xff00) | ((n) >> 24))
35 #else
36 # define SWAP(n) (n)
37 #endif
38
39
40 /* This array contains the bytes used to pad the buffer to the next
41    64-byte boundary.  (RFC 1321, 3.1: Step 1)  */
42 static const unsigned char fillbuf[64] = { 0x80, 0 /* , 0, 0, ...  */ };
43
44 /* These are the four functions used in the four steps of the MD5 algorithm
45    and defined in the RFC 1321.  The first function is a little bit optimized
46    (as found in Colin Plumbs public domain implementation).  */
47 /* #define FF(b, c, d) ((b & c) | (~b & d)) */
48 #define FF(b, c, d) (d ^ (b & (c ^ d)))
49 #define FG(b, c, d) FF (d, b, c)
50 #define FH(b, c, d) (b ^ c ^ d)
51 #define FI(b, c, d) (c ^ (b | ~d))
52
53 /* Process LEN bytes of BUFFER, accumulating context into CTX.
54    It is assumed that LEN % 64 == 0.  */
55
56 void
57 md5_process_block(const void *buffer, size_t len, struct md5_ctx *ctx)
58 {
59   uint32_t correct_words[16];
60   const uint32_t *words = buffer;
61   size_t nwords = len / sizeof (uint32_t);
62   const uint32_t *endp = words + nwords;
63   uint32_t A = ctx->A;
64   uint32_t B = ctx->B;
65   uint32_t C = ctx->C;
66   uint32_t D = ctx->D;
67
68   /* First increment the byte count.  RFC 1321 specifies the possible
69      length of the file up to 2^64 bits.  Here we only compute the
70      number of bytes.  Do a double word increment.  */
71   ctx->total[0] += len;
72   if (ctx->total[0] < len)
73     ++ctx->total[1];
74
75   /* Process all bytes in the buffer with 64 bytes in each round of
76      the loop.  */
77   while (words < endp)
78     {
79       uint32_t *cwp = correct_words;
80       uint32_t A_save = A;
81       uint32_t B_save = B;
82       uint32_t C_save = C;
83       uint32_t D_save = D;
84
85       /* First round: using the given function, the context and a constant
86          the next context is computed.  Because the algorithms processing
87          unit is a 32-bit word and it is determined to work on words in
88          little endian byte order we perhaps have to change the byte order
89          before the computation.  To reduce the work for the next steps
90          we store the swapped words in the array CORRECT_WORDS.  */
91
92 #define OP(a, b, c, d, s, T)                                            \
93       do                                                                \
94         {                                                               \
95           a += FF (b, c, d) + (*cwp++ = SWAP (*words)) + T;             \
96           ++words;                                                      \
97           CYCLIC (a, s);                                                \
98           a += b;                                                       \
99         }                                                               \
100       while (0)
101
102       /* It is unfortunate that C does not provide an operator for
103          cyclic rotation.  Hope the C compiler is smart enough.  */
104 #define CYCLIC(w, s) (w = (w << s) | (w >> (32 - s)))
105
106       /* Before we start, one word to the strange constants.
107          They are defined in RFC 1321 as
108
109          T[i] = (int) (4294967296.0 * fabs (sin (i))), i=1..64
110        */
111
112       /* Round 1.  */
113       OP (A, B, C, D,  7, 0xd76aa478);
114       OP (D, A, B, C, 12, 0xe8c7b756);
115       OP (C, D, A, B, 17, 0x242070db);
116       OP (B, C, D, A, 22, 0xc1bdceee);
117       OP (A, B, C, D,  7, 0xf57c0faf);
118       OP (D, A, B, C, 12, 0x4787c62a);
119       OP (C, D, A, B, 17, 0xa8304613);
120       OP (B, C, D, A, 22, 0xfd469501);
121       OP (A, B, C, D,  7, 0x698098d8);
122       OP (D, A, B, C, 12, 0x8b44f7af);
123       OP (C, D, A, B, 17, 0xffff5bb1);
124       OP (B, C, D, A, 22, 0x895cd7be);
125       OP (A, B, C, D,  7, 0x6b901122);
126       OP (D, A, B, C, 12, 0xfd987193);
127       OP (C, D, A, B, 17, 0xa679438e);
128       OP (B, C, D, A, 22, 0x49b40821);
129
130       /* For the second to fourth round we have the possibly swapped words
131          in CORRECT_WORDS.  Redefine the macro to take an additional first
132          argument specifying the function to use.  */
133 #undef OP
134 #define OP(f, a, b, c, d, k, s, T)                                      \
135       do                                                                \
136         {                                                               \
137           a += f (b, c, d) + correct_words[k] + T;                      \
138           CYCLIC (a, s);                                                \
139           a += b;                                                       \
140         }                                                               \
141       while (0)
142
143       /* Round 2.  */
144       OP (FG, A, B, C, D,  1,  5, 0xf61e2562);
145       OP (FG, D, A, B, C,  6,  9, 0xc040b340);
146       OP (FG, C, D, A, B, 11, 14, 0x265e5a51);
147       OP (FG, B, C, D, A,  0, 20, 0xe9b6c7aa);
148       OP (FG, A, B, C, D,  5,  5, 0xd62f105d);
149       OP (FG, D, A, B, C, 10,  9, 0x02441453);
150       OP (FG, C, D, A, B, 15, 14, 0xd8a1e681);
151       OP (FG, B, C, D, A,  4, 20, 0xe7d3fbc8);
152       OP (FG, A, B, C, D,  9,  5, 0x21e1cde6);
153       OP (FG, D, A, B, C, 14,  9, 0xc33707d6);
154       OP (FG, C, D, A, B,  3, 14, 0xf4d50d87);
155       OP (FG, B, C, D, A,  8, 20, 0x455a14ed);
156       OP (FG, A, B, C, D, 13,  5, 0xa9e3e905);
157       OP (FG, D, A, B, C,  2,  9, 0xfcefa3f8);
158       OP (FG, C, D, A, B,  7, 14, 0x676f02d9);
159       OP (FG, B, C, D, A, 12, 20, 0x8d2a4c8a);
160
161       /* Round 3.  */
162       OP (FH, A, B, C, D,  5,  4, 0xfffa3942);
163       OP (FH, D, A, B, C,  8, 11, 0x8771f681);
164       OP (FH, C, D, A, B, 11, 16, 0x6d9d6122);
165       OP (FH, B, C, D, A, 14, 23, 0xfde5380c);
166       OP (FH, A, B, C, D,  1,  4, 0xa4beea44);
167       OP (FH, D, A, B, C,  4, 11, 0x4bdecfa9);
168       OP (FH, C, D, A, B,  7, 16, 0xf6bb4b60);
169       OP (FH, B, C, D, A, 10, 23, 0xbebfbc70);
170       OP (FH, A, B, C, D, 13,  4, 0x289b7ec6);
171       OP (FH, D, A, B, C,  0, 11, 0xeaa127fa);
172       OP (FH, C, D, A, B,  3, 16, 0xd4ef3085);
173       OP (FH, B, C, D, A,  6, 23, 0x04881d05);
174       OP (FH, A, B, C, D,  9,  4, 0xd9d4d039);
175       OP (FH, D, A, B, C, 12, 11, 0xe6db99e5);
176       OP (FH, C, D, A, B, 15, 16, 0x1fa27cf8);
177       OP (FH, B, C, D, A,  2, 23, 0xc4ac5665);
178
179       /* Round 4.  */
180       OP (FI, A, B, C, D,  0,  6, 0xf4292244);
181       OP (FI, D, A, B, C,  7, 10, 0x432aff97);
182       OP (FI, C, D, A, B, 14, 15, 0xab9423a7);
183       OP (FI, B, C, D, A,  5, 21, 0xfc93a039);
184       OP (FI, A, B, C, D, 12,  6, 0x655b59c3);
185       OP (FI, D, A, B, C,  3, 10, 0x8f0ccc92);
186       OP (FI, C, D, A, B, 10, 15, 0xffeff47d);
187       OP (FI, B, C, D, A,  1, 21, 0x85845dd1);
188       OP (FI, A, B, C, D,  8,  6, 0x6fa87e4f);
189       OP (FI, D, A, B, C, 15, 10, 0xfe2ce6e0);
190       OP (FI, C, D, A, B,  6, 15, 0xa3014314);
191       OP (FI, B, C, D, A, 13, 21, 0x4e0811a1);
192       OP (FI, A, B, C, D,  4,  6, 0xf7537e82);
193       OP (FI, D, A, B, C, 11, 10, 0xbd3af235);
194       OP (FI, C, D, A, B,  2, 15, 0x2ad7d2bb);
195       OP (FI, B, C, D, A,  9, 21, 0xeb86d391);
196
197       /* Add the starting values of the context.  */
198       A += A_save;
199       B += B_save;
200       C += C_save;
201       D += D_save;
202     }
203
204   /* Put checksum in context given as argument.  */
205   ctx->A = A;
206   ctx->B = B;
207   ctx->C = C;
208   ctx->D = D;
209 }
210
211 /* Initialize structure containing state of computation.
212    (RFC 1321, 3.3: Step 3)  */
213 void
214 md5_init(struct md5_ctx *ctx)
215 {
216   ctx->A = 0x67452301;
217   ctx->B = 0xefcdab89;
218   ctx->C = 0x98badcfe;
219   ctx->D = 0x10325476;
220
221   ctx->total[0] = ctx->total[1] = 0;
222   ctx->buflen = 0;
223 }
224
225 /* Put result from CTX in first 16 bytes following RESBUF.  The result
226    must be in little endian byte order.
227
228    IMPORTANT: On some systems it is required that RESBUF is correctly
229    aligned for a 32 bits value.  */
230 void
231 md5_read_ctx(const struct md5_ctx *ctx, void *resbuf)
232 {
233   ((uint32_t *) resbuf)[0] = SWAP (ctx->A);
234   ((uint32_t *) resbuf)[1] = SWAP (ctx->B);
235   ((uint32_t *) resbuf)[2] = SWAP (ctx->C);
236   ((uint32_t *) resbuf)[3] = SWAP (ctx->D);
237 }
238
239 /* Process the remaining bytes in the internal buffer and the usual
240    prolog according to the standard and write the result to RESBUF.
241
242    IMPORTANT: On some systems it is required that RESBUF is correctly
243    aligned for a 32 bits value.  */
244 void
245 md5_digest(struct md5_ctx *ctx, unsigned length, uint8_t *resbuf)
246 {
247   /* Take yet unprocessed bytes into account.  */
248   uint32_t bytes = ctx->buflen;
249   size_t pad;
250
251   /* Now count remaining bytes.  */
252   ctx->total[0] += bytes;
253   if (ctx->total[0] < bytes)
254     ++ctx->total[1];
255
256   pad = bytes >= 56 ? 64 + 56 - bytes : 56 - bytes;
257   memcpy (&ctx->buffer[bytes], fillbuf, pad);
258
259   /* Put the 64-bit file length in *bits* at the end of the buffer.  */
260   *(uint32_t *) &ctx->buffer[bytes + pad] = SWAP (ctx->total[0] << 3);
261   *(uint32_t *) &ctx->buffer[bytes + pad + 4] = SWAP ((ctx->total[1] << 3) |
262                                                         (ctx->total[0] >> 29));
263
264   /* Process last bytes.  */
265   md5_process_block (ctx->buffer, bytes + pad + 8, ctx);
266
267   md5_read_ctx(ctx, resbuf);
268
269   return;
270 }
271
272 void
273 md5_update(struct md5_ctx *ctx, unsigned length,
274                         const uint8_t *buffer)
275 {
276   /* When we already have some bits in our internal buffer concatenate
277      both inputs first.  */
278   if (ctx->buflen != 0)
279     {
280       size_t left_over = ctx->buflen;
281       size_t add = 128 - left_over > length ? length : 128 - left_over;
282
283       memcpy (&ctx->buffer[left_over], buffer, add);
284       ctx->buflen += add;
285
286       if (ctx->buflen > 64)
287         {
288           md5_process_block (ctx->buffer, ctx->buflen & ~63, ctx);
289
290           ctx->buflen &= 63;
291           /* The regions in the following copy operation cannot overlap.  */
292           memcpy (ctx->buffer, &ctx->buffer[(left_over + add) & ~63],
293                   ctx->buflen);
294         }
295
296       buffer = (const uint8_t *) buffer + add;
297       length -= add;
298     }
299
300   /* Process available complete blocks.  */
301   if (length >= 64)
302     {
303 #if !_STRING_ARCH_unaligned
304 /* To check alignment gcc has an appropriate operator.  Other
305    compilers don't.  */
306 # if __GNUC__ >= 2
307 #  define UNALIGNED_P(p) (((md5_uintptr) p) % __alignof__ (uint32_t) != 0)
308 # else
309 #  define UNALIGNED_P(p) (((md5_uintptr) p) % sizeof (uint32_t) != 0)
310 # endif
311       if (UNALIGNED_P (buffer))
312         while (length > 64)
313           {
314             md5_process_block (memcpy (ctx->buffer, buffer, 64), 64, ctx);
315             buffer = (const uint8_t *) buffer + 64;
316             length -= 64;
317           }
318       else
319 #endif
320         {
321           md5_process_block (buffer, length & ~63, ctx);
322           buffer = (const uint8_t *) buffer + (length & ~63);
323           length &= 63;
324         }
325     }
326
327   /* Move remaining bytes in internal buffer.  */
328   if (length > 0)
329     {
330       size_t left_over = ctx->buflen;
331
332       memcpy (&ctx->buffer[left_over], buffer, length);
333       left_over += length;
334       if (left_over >= 64)
335         {
336           md5_process_block (ctx->buffer, 64, ctx);
337           left_over -= 64;
338           memcpy (ctx->buffer, &ctx->buffer[64], left_over);
339         }
340       ctx->buflen = left_over;
341     }
342 }