1/* -*- mode: C; c-file-style: "gnu"; indent-tabs-mode: nil; -*- */
2/* dbus-md5.c md5 implementation (based on L Peter Deutsch implementation)
3 *
4 * Copyright (C) 2003 Red Hat Inc.
5 * Copyright (C) 1999, 2000 Aladdin Enterprises.  All rights reserved.
6 *
7 * This software is provided 'as-is', without any express or implied
8 * warranty.  In no event will the authors be held liable for any damages
9 * arising from the use of this software.
10 *
11 * Permission is granted to anyone to use this software for any purpose,
12 * including commercial applications, and to alter it and redistribute it
13 * freely, subject to the following restrictions:
14 *
15 * 1. The origin of this software must not be misrepresented; you must not
16 *    claim that you wrote the original software. If you use this software
17 *    in a product, an acknowledgment in the product documentation would be
18 *    appreciated but is not required.
19 * 2. Altered source versions must be plainly marked as such, and must not be
20 *    misrepresented as being the original software.
21 * 3. This notice may not be removed or altered from any source distribution.
22 *
23 * L. Peter Deutsch
24 * ghost@aladdin.com
25 */
26/*
27 * Independent implementation of MD5 (RFC 1321).
28 *
29 * This code implements the MD5 Algorithm defined in RFC 1321.
30 * It is derived directly from the text of the RFC and not from the
31 * reference implementation.
32 *
33 * The original and principal author of md5.c is L. Peter Deutsch
34 * <ghost@aladdin.com>.
35 */
36
37#include <config.h>
38#include "dbus-internals.h"
39#include "dbus-md5.h"
40#include <string.h>
41
42/**
43 * @defgroup DBusMD5 MD5 implementation
44 * @ingroup  DBusInternals
45 * @brief MD5 hash
46 *
47 * Types and functions related to computing MD5 sums.
48 */
49
50/**
51 * @defgroup DBusMD5Internals MD5 implementation details
52 * @ingroup  DBusInternals
53 * @brief Internals of MD5 implementation.
54 *
55 * The implementation of MD5 (see http://www.ietf.org/rfc/rfc1321.txt).
56 * This MD5 implementation was written by L. Peter Deutsch and
57 * is not derived from the RSA reference implementation in the
58 * RFC. The version included in D-Bus comes from the Ghostscript
59 * 7.05 distribution.
60 *
61 * @{
62 */
63#ifndef DOXYGEN_SHOULD_SKIP_THIS
64/*
65 * For reference, here is the program that computed the T values.
66 */
67#ifdef COMPUTE_T_VALUES
68#include <math.h>
69int
70main(int argc, char **argv)
71{
72  int i;
73  for (i = 1; i <= 64; ++i)
74    {
75      unsigned long v = (unsigned long)(4294967296.0 * fabs(sin((double)i)));
76
77      /*
78       * The following nonsense is only to avoid compiler warnings about
79       * "integer constant is unsigned in ANSI C, signed with -traditional".
80       */
81      if (v >> 31)
82        {
83          printf("#define T%d /* 0x%08lx */ (T_MASK ^ 0x%08lx)\n", i,
84                 v, (unsigned long)(unsigned int)(~v));
85        } else {
86        printf("#define T%d    0x%08lx\n", i, v);
87      }
88    }
89  return 0;
90}
91#endif /* COMPUTE_T_VALUES */
92/*
93 * End of T computation program.
94 */
95
96#define T_MASK ((dbus_uint32_t)~0)
97#define T1 /* 0xd76aa478 */ (T_MASK ^ 0x28955b87)
98#define T2 /* 0xe8c7b756 */ (T_MASK ^ 0x173848a9)
99#define T3    0x242070db
100#define T4 /* 0xc1bdceee */ (T_MASK ^ 0x3e423111)
101#define T5 /* 0xf57c0faf */ (T_MASK ^ 0x0a83f050)
102#define T6    0x4787c62a
103#define T7 /* 0xa8304613 */ (T_MASK ^ 0x57cfb9ec)
104#define T8 /* 0xfd469501 */ (T_MASK ^ 0x02b96afe)
105#define T9    0x698098d8
106#define T10 /* 0x8b44f7af */ (T_MASK ^ 0x74bb0850)
107#define T11 /* 0xffff5bb1 */ (T_MASK ^ 0x0000a44e)
108#define T12 /* 0x895cd7be */ (T_MASK ^ 0x76a32841)
109#define T13    0x6b901122
110#define T14 /* 0xfd987193 */ (T_MASK ^ 0x02678e6c)
111#define T15 /* 0xa679438e */ (T_MASK ^ 0x5986bc71)
112#define T16    0x49b40821
113#define T17 /* 0xf61e2562 */ (T_MASK ^ 0x09e1da9d)
114#define T18 /* 0xc040b340 */ (T_MASK ^ 0x3fbf4cbf)
115#define T19    0x265e5a51
116#define T20 /* 0xe9b6c7aa */ (T_MASK ^ 0x16493855)
117#define T21 /* 0xd62f105d */ (T_MASK ^ 0x29d0efa2)
118#define T22    0x02441453
119#define T23 /* 0xd8a1e681 */ (T_MASK ^ 0x275e197e)
120#define T24 /* 0xe7d3fbc8 */ (T_MASK ^ 0x182c0437)
121#define T25    0x21e1cde6
122#define T26 /* 0xc33707d6 */ (T_MASK ^ 0x3cc8f829)
123#define T27 /* 0xf4d50d87 */ (T_MASK ^ 0x0b2af278)
124#define T28    0x455a14ed
125#define T29 /* 0xa9e3e905 */ (T_MASK ^ 0x561c16fa)
126#define T30 /* 0xfcefa3f8 */ (T_MASK ^ 0x03105c07)
127#define T31    0x676f02d9
128#define T32 /* 0x8d2a4c8a */ (T_MASK ^ 0x72d5b375)
129#define T33 /* 0xfffa3942 */ (T_MASK ^ 0x0005c6bd)
130#define T34 /* 0x8771f681 */ (T_MASK ^ 0x788e097e)
131#define T35    0x6d9d6122
132#define T36 /* 0xfde5380c */ (T_MASK ^ 0x021ac7f3)
133#define T37 /* 0xa4beea44 */ (T_MASK ^ 0x5b4115bb)
134#define T38    0x4bdecfa9
135#define T39 /* 0xf6bb4b60 */ (T_MASK ^ 0x0944b49f)
136#define T40 /* 0xbebfbc70 */ (T_MASK ^ 0x4140438f)
137#define T41    0x289b7ec6
138#define T42 /* 0xeaa127fa */ (T_MASK ^ 0x155ed805)
139#define T43 /* 0xd4ef3085 */ (T_MASK ^ 0x2b10cf7a)
140#define T44    0x04881d05
141#define T45 /* 0xd9d4d039 */ (T_MASK ^ 0x262b2fc6)
142#define T46 /* 0xe6db99e5 */ (T_MASK ^ 0x1924661a)
143#define T47    0x1fa27cf8
144#define T48 /* 0xc4ac5665 */ (T_MASK ^ 0x3b53a99a)
145#define T49 /* 0xf4292244 */ (T_MASK ^ 0x0bd6ddbb)
146#define T50    0x432aff97
147#define T51 /* 0xab9423a7 */ (T_MASK ^ 0x546bdc58)
148#define T52 /* 0xfc93a039 */ (T_MASK ^ 0x036c5fc6)
149#define T53    0x655b59c3
150#define T54 /* 0x8f0ccc92 */ (T_MASK ^ 0x70f3336d)
151#define T55 /* 0xffeff47d */ (T_MASK ^ 0x00100b82)
152#define T56 /* 0x85845dd1 */ (T_MASK ^ 0x7a7ba22e)
153#define T57    0x6fa87e4f
154#define T58 /* 0xfe2ce6e0 */ (T_MASK ^ 0x01d3191f)
155#define T59 /* 0xa3014314 */ (T_MASK ^ 0x5cfebceb)
156#define T60    0x4e0811a1
157#define T61 /* 0xf7537e82 */ (T_MASK ^ 0x08ac817d)
158#define T62 /* 0xbd3af235 */ (T_MASK ^ 0x42c50dca)
159#define T63    0x2ad7d2bb
160#define T64 /* 0xeb86d391 */ (T_MASK ^ 0x14792c6e)
161#endif /* !DOXYGEN_SHOULD_SKIP_THIS */
162
163static void
164md5_process(DBusMD5Context *context, const unsigned char *data /*[64]*/)
165{
166  dbus_uint32_t
167    a = context->abcd[0], b = context->abcd[1],
168    c = context->abcd[2], d = context->abcd[3];
169  dbus_uint32_t t;
170
171#ifdef WORDS_BIGENDIAN
172  /*
173   * On big-endian machines, we must arrange the bytes in the right
174   * order.  (This also works on machines of unknown byte order.)
175   */
176  dbus_uint32_t X[16];
177  const unsigned char *xp = data;
178  int i;
179
180  for (i = 0; i < 16; ++i, xp += 4)
181    X[i] = xp[0] + (xp[1] << 8) + (xp[2] << 16) + (xp[3] << 24);
182
183#else  /* !WORDS_BIGENDIAN */
184  /*
185   * On little-endian machines, we can process properly aligned data
186   * without copying it.
187   */
188  dbus_uint32_t xbuf[16];
189  const dbus_uint32_t *X;
190
191  if (!((data - (const unsigned char *)0) & 3))
192    {
193      /* data are properly aligned */
194      X = (const dbus_uint32_t *)data;
195    }
196  else
197    {
198      /* not aligned */
199      memcpy(xbuf, data, 64);
200      X = xbuf;
201    }
202#endif
203
204#define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32 - (n))))
205
206  /* Round 1. */
207  /* Let [abcd k s i] denote the operation
208     a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s). */
209#define F(x, y, z) (((x) & (y)) | (~(x) & (z)))
210#define SET(a, b, c, d, k, s, Ti)               \
211  t = a + F(b,c,d) + X[k] + Ti;                 \
212  a = ROTATE_LEFT(t, s) + b
213  /* Do the following 16 operations. */
214  SET(a, b, c, d,  0,  7,  T1);
215  SET(d, a, b, c,  1, 12,  T2);
216  SET(c, d, a, b,  2, 17,  T3);
217  SET(b, c, d, a,  3, 22,  T4);
218  SET(a, b, c, d,  4,  7,  T5);
219  SET(d, a, b, c,  5, 12,  T6);
220  SET(c, d, a, b,  6, 17,  T7);
221  SET(b, c, d, a,  7, 22,  T8);
222  SET(a, b, c, d,  8,  7,  T9);
223  SET(d, a, b, c,  9, 12, T10);
224  SET(c, d, a, b, 10, 17, T11);
225  SET(b, c, d, a, 11, 22, T12);
226  SET(a, b, c, d, 12,  7, T13);
227  SET(d, a, b, c, 13, 12, T14);
228  SET(c, d, a, b, 14, 17, T15);
229  SET(b, c, d, a, 15, 22, T16);
230#undef SET
231
232  /* Round 2. */
233  /* Let [abcd k s i] denote the operation
234     a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s). */
235#define G(x, y, z) (((x) & (z)) | ((y) & ~(z)))
236#define SET(a, b, c, d, k, s, Ti)               \
237  t = a + G(b,c,d) + X[k] + Ti;                 \
238  a = ROTATE_LEFT(t, s) + b
239  /* Do the following 16 operations. */
240  SET(a, b, c, d,  1,  5, T17);
241  SET(d, a, b, c,  6,  9, T18);
242  SET(c, d, a, b, 11, 14, T19);
243  SET(b, c, d, a,  0, 20, T20);
244  SET(a, b, c, d,  5,  5, T21);
245  SET(d, a, b, c, 10,  9, T22);
246  SET(c, d, a, b, 15, 14, T23);
247  SET(b, c, d, a,  4, 20, T24);
248  SET(a, b, c, d,  9,  5, T25);
249  SET(d, a, b, c, 14,  9, T26);
250  SET(c, d, a, b,  3, 14, T27);
251  SET(b, c, d, a,  8, 20, T28);
252  SET(a, b, c, d, 13,  5, T29);
253  SET(d, a, b, c,  2,  9, T30);
254  SET(c, d, a, b,  7, 14, T31);
255  SET(b, c, d, a, 12, 20, T32);
256#undef SET
257
258  /* Round 3. */
259  /* Let [abcd k s t] denote the operation
260     a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s). */
261#define H(x, y, z) ((x) ^ (y) ^ (z))
262#define SET(a, b, c, d, k, s, Ti)               \
263  t = a + H(b,c,d) + X[k] + Ti;                 \
264  a = ROTATE_LEFT(t, s) + b
265  /* Do the following 16 operations. */
266  SET(a, b, c, d,  5,  4, T33);
267  SET(d, a, b, c,  8, 11, T34);
268  SET(c, d, a, b, 11, 16, T35);
269  SET(b, c, d, a, 14, 23, T36);
270  SET(a, b, c, d,  1,  4, T37);
271  SET(d, a, b, c,  4, 11, T38);
272  SET(c, d, a, b,  7, 16, T39);
273  SET(b, c, d, a, 10, 23, T40);
274  SET(a, b, c, d, 13,  4, T41);
275  SET(d, a, b, c,  0, 11, T42);
276  SET(c, d, a, b,  3, 16, T43);
277  SET(b, c, d, a,  6, 23, T44);
278  SET(a, b, c, d,  9,  4, T45);
279  SET(d, a, b, c, 12, 11, T46);
280  SET(c, d, a, b, 15, 16, T47);
281  SET(b, c, d, a,  2, 23, T48);
282#undef SET
283
284  /* Round 4. */
285  /* Let [abcd k s t] denote the operation
286     a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s). */
287#define I(x, y, z) ((y) ^ ((x) | ~(z)))
288#define SET(a, b, c, d, k, s, Ti)               \
289  t = a + I(b,c,d) + X[k] + Ti;                 \
290  a = ROTATE_LEFT(t, s) + b
291  /* Do the following 16 operations. */
292  SET(a, b, c, d,  0,  6, T49);
293  SET(d, a, b, c,  7, 10, T50);
294  SET(c, d, a, b, 14, 15, T51);
295  SET(b, c, d, a,  5, 21, T52);
296  SET(a, b, c, d, 12,  6, T53);
297  SET(d, a, b, c,  3, 10, T54);
298  SET(c, d, a, b, 10, 15, T55);
299  SET(b, c, d, a,  1, 21, T56);
300  SET(a, b, c, d,  8,  6, T57);
301  SET(d, a, b, c, 15, 10, T58);
302  SET(c, d, a, b,  6, 15, T59);
303  SET(b, c, d, a, 13, 21, T60);
304  SET(a, b, c, d,  4,  6, T61);
305  SET(d, a, b, c, 11, 10, T62);
306  SET(c, d, a, b,  2, 15, T63);
307  SET(b, c, d, a,  9, 21, T64);
308#undef SET
309
310  /* Then perform the following additions. (That is increment each
311     of the four registers by the value it had before this block
312     was started.) */
313  context->abcd[0] += a;
314  context->abcd[1] += b;
315  context->abcd[2] += c;
316  context->abcd[3] += d;
317}
318
319static void
320md5_init (DBusMD5Context *context)
321{
322  context->count[0] = context->count[1] = 0;
323  context->abcd[0] = 0x67452301;
324  context->abcd[1] = /*0xefcdab89*/ T_MASK ^ 0x10325476;
325  context->abcd[2] = /*0x98badcfe*/ T_MASK ^ 0x67452301;
326  context->abcd[3] = 0x10325476;
327}
328
329static void
330md5_append (DBusMD5Context *context, const unsigned char *data, int nbytes)
331{
332  const unsigned char *p = data;
333  int left = nbytes;
334  int offset = (context->count[0] >> 3) & 63;
335  dbus_uint32_t nbits = (dbus_uint32_t)(nbytes << 3);
336
337  if (nbytes <= 0)
338    return;
339
340  /* Update the message length. */
341  context->count[1] += nbytes >> 29;
342  context->count[0] += nbits;
343  if (context->count[0] < nbits)
344    context->count[1]++;
345
346  /* Process an initial partial block. */
347  if (offset)
348    {
349      int copy = (offset + nbytes > 64 ? 64 - offset : nbytes);
350
351      memcpy(context->buf + offset, p, copy);
352      if (offset + copy < 64)
353        return;
354      p += copy;
355      left -= copy;
356      md5_process(context, context->buf);
357    }
358
359  /* Process full blocks. */
360  for (; left >= 64; p += 64, left -= 64)
361    md5_process(context, p);
362
363  /* Process a final partial block. */
364  if (left)
365    memcpy(context->buf, p, left);
366}
367
368static void
369md5_finish (DBusMD5Context *context, unsigned char digest[16])
370{
371  static const unsigned char pad[64] = {
372    0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
373    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
374    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
375    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
376  };
377  unsigned char data[8];
378  int i;
379
380  /* Save the length before padding. */
381  for (i = 0; i < 8; ++i)
382    data[i] = (unsigned char)(context->count[i >> 2] >> ((i & 3) << 3));
383  /* Pad to 56 bytes mod 64. */
384  md5_append(context, pad, ((55 - (context->count[0] >> 3)) & 63) + 1);
385  /* Append the length. */
386  md5_append(context, data, 8);
387  for (i = 0; i < 16; ++i)
388    digest[i] = (unsigned char)(context->abcd[i >> 2] >> ((i & 3) << 3));
389}
390
391/** @} */ /* End of internals */
392
393/**
394 * @addtogroup DBusMD5
395 *
396 * @{
397 */
398
399/**
400 * Initializes the MD5 context.
401 *
402 * @param context an uninitialized context, typically on the stack.
403 */
404void
405_dbus_md5_init (DBusMD5Context *context)
406{
407  md5_init (context);
408}
409
410
411/**
412 * Feeds more data into an existing md5sum computation.
413 *
414 * @param context the MD5 context
415 * @param data the additional data to hash
416 */
417void
418_dbus_md5_update (DBusMD5Context   *context,
419                  const DBusString *data)
420{
421  unsigned int inputLen;
422  unsigned char *input;
423
424  _dbus_string_get_const_data (data, (const char**) &input);
425  inputLen = _dbus_string_get_length (data);
426
427  md5_append (context, input, inputLen);
428}
429
430/**
431 * MD5 finalization. Ends an MD5 message-digest operation, writing the
432 * the message digest and zeroing the context.  The results are
433 * returned as a raw 16-byte digest, not as the ascii-hex-digits
434 * string form of the digest.
435 *
436 * @param context the MD5 context
437 * @param results string to append the 16-byte MD5 digest to
438 * @returns #FALSE if not enough memory to append the digest
439 *
440 */
441dbus_bool_t
442_dbus_md5_final (DBusMD5Context   *context,
443                 DBusString       *results)
444{
445  unsigned char digest[16];
446
447  md5_finish (context, digest);
448
449  if (!_dbus_string_append_len (results, digest, 16))
450    return FALSE;
451
452  /* some kind of security paranoia, though it seems pointless
453   * to me given the nonzeroed stuff flying around
454   */
455  _DBUS_ZERO(*context);
456
457  return TRUE;
458}
459
460/**
461 * Computes the ASCII hex-encoded md5sum of the given data and
462 * appends it to the output string.
463 *
464 * @param data input data to be hashed
465 * @param ascii_output string to append ASCII md5sum to
466 * @returns #FALSE if not enough memory
467 */
468dbus_bool_t
469_dbus_md5_compute (const DBusString *data,
470                   DBusString       *ascii_output)
471{
472  DBusMD5Context context;
473  DBusString digest;
474
475  _dbus_md5_init (&context);
476
477  _dbus_md5_update (&context, data);
478
479  if (!_dbus_string_init (&digest))
480    return FALSE;
481
482  if (!_dbus_md5_final (&context, &digest))
483    goto error;
484
485  if (!_dbus_string_hex_encode (&digest, 0, ascii_output,
486                                _dbus_string_get_length (ascii_output)))
487    goto error;
488
489  _dbus_string_free (&digest);
490
491  return TRUE;
492
493 error:
494  _dbus_string_free (&digest);
495  return FALSE;
496}
497
498/** @} */ /* end of exported functions */
499
500#ifdef DBUS_BUILD_TESTS
501#include "dbus-test.h"
502#include <stdio.h>
503
504static dbus_bool_t
505check_md5_binary (const unsigned char *input,
506                  int                  input_len,
507                  const char          *expected)
508{
509  DBusString input_str;
510  DBusString expected_str;
511  DBusString results;
512
513  _dbus_string_init_const_len (&input_str, input, input_len);
514  _dbus_string_init_const (&expected_str, expected);
515
516  if (!_dbus_string_init (&results))
517    _dbus_assert_not_reached ("no memory for md5 results");
518
519  if (!_dbus_md5_compute (&input_str, &results))
520    _dbus_assert_not_reached ("no memory for md5 results");
521
522  if (!_dbus_string_equal (&expected_str, &results))
523    {
524      const char *s;
525      _dbus_string_get_const_data (&results, &s);
526      _dbus_warn ("Expected hash %s got %s for md5 sum\n",
527                  expected, s);
528      _dbus_string_free (&results);
529      return FALSE;
530    }
531
532  _dbus_string_free (&results);
533  return TRUE;
534}
535
536static dbus_bool_t
537check_md5_str (const char *input,
538               const char *expected)
539{
540  return check_md5_binary (input, strlen (input), expected);
541}
542
543/**
544 * @ingroup DBusMD5Internals
545 * Unit test for MD5 computation.
546 *
547 * @returns #TRUE on success.
548 */
549dbus_bool_t
550_dbus_md5_test (void)
551{
552  unsigned char all_bytes[256];
553  int i;
554
555  i = 0;
556  while (i < 256)
557    {
558      all_bytes[i] = i;
559      ++i;
560    }
561
562  if (!check_md5_binary (all_bytes, 256,
563                         "e2c865db4162bed963bfaa9ef6ac18f0"))
564    return FALSE;
565
566#define CHECK(input,expected) if (!check_md5_str (input, expected)) return FALSE
567
568  CHECK ("", "d41d8cd98f00b204e9800998ecf8427e");
569  CHECK ("a", "0cc175b9c0f1b6a831c399e269772661");
570  CHECK ("abc", "900150983cd24fb0d6963f7d28e17f72");
571  CHECK ("message digest", "f96b697d7cb7938d525a2f31aaf161d0");
572  CHECK ("abcdefghijklmnopqrstuvwxyz", "c3fcd3d76192e4007dfb496cca67e13b");
573  CHECK ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789",
574         "d174ab98d277d9f5a5611c2c9f419d9f");
575  CHECK ("12345678901234567890123456789012345678901234567890123456789012345678901234567890",
576         "57edf4a22be3c955ac49da2e2107b67a");
577
578  return TRUE;
579}
580
581#endif /* DBUS_BUILD_TESTS */
582