crypto/md5.c

   1 /* md5.c
   2  *
   3  * The MD5 hash function, described in RFC 1321.
   4  */
   5
   6 /* nettle, low-level cryptographics library
   7  *
   8  * Copyright (C) 2001 Niels Möller
   9  *
  10  * The nettle library is free software; you can redistribute it and/or modify
  11  * it under the terms of the GNU Lesser General Public License as published by
  12  * the Free Software Foundation; either version 2.1 of the License, or (at your
  13  * option) any later version.
  14  *
  15  * The nettle library is distributed in the hope that it will be useful, but
  16  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  17  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  18  * License for more details.
  19  *
  20  * You should have received a copy of the GNU Lesser General Public License
  21  * along with the nettle library; see the file COPYING.LIB.  If not, write to
  22  * the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  23  * MA 02111-1307, USA.
  24  */
  25
  26 /* Based on public domain code hacked by Colin Plumb, Andrew Kuchling, and
  27  * Niels Möller. */
  28
  29 #if HAVE_CONFIG_H
  30 # include "config.h"
  31 #endif
  32
  33 #include <assert.h>
  34 #include <string.h>
  35
  36 #include "md5.h"
  37
  38 #include "macros.h"
  39
  40 /* A block, treated as a sequence of 32-bit words. */
  41 #define MD5_DATA_LENGTH 16
  42
  43 static void
  44 md5_transform(uint32_t *digest, const uint32_t *data);
  45
  46 static void
  47 md5_block(struct md5_ctx *ctx, const uint8_t *block);
  48
  49 static void
  50 md5_final(struct md5_ctx *ctx);
  51
  52 void
  53 md5_init(struct md5_ctx *ctx)
  54 {
  55   ctx->digest[0] = 0x67452301;
  56   ctx->digest[1] = 0xefcdab89;
  57   ctx->digest[2] = 0x98badcfe;
  58   ctx->digest[3] = 0x10325476;
  59
  60   ctx->count_l = ctx->count_h = 0;
  61   ctx->index = 0;
  62 }
  63
  64 void
  65 md5_update(struct md5_ctx *ctx,
  66            unsigned length,
  67            const uint8_t *data)
  68 {
  69   if (ctx->index)
  70     {
  71       /* Try to fill partial block */
  72       unsigned left = MD5_DATA_SIZE - ctx->index;
  73       if (length < left)
  74         {
  75           memcpy(ctx->block + ctx->index, data, length);
  76           ctx->index += length;
  77           return; /* Finished */
  78         }
  79       else
  80         {
  81           memcpy(ctx->block + ctx->index, data, left);
  82           md5_block(ctx, ctx->block);
  83           data += left;
  84           length -= left;
  85         }
  86     }
  87   while (length >= MD5_DATA_SIZE)
  88     {
  89       md5_block(ctx, data);
  90       data += MD5_DATA_SIZE;
  91       length -= MD5_DATA_SIZE;
  92     }
  93   if ((ctx->index = length))     /* This assignment is intended */
  94     /* Buffer leftovers */
  95     memcpy(ctx->block, data, length);
  96 }
  97
  98 void
  99 md5_digest(struct md5_ctx *ctx,
 100            unsigned length,
 101            uint8_t *digest)
 102 {
 103   unsigned i;
 104   unsigned words;
 105   unsigned leftover;
 106
 107   assert(length <= MD5_DIGEST_SIZE);
 108
 109   md5_final(ctx);
 110
 111   words = length / 4;
 112   leftover = length % 4;
 113
 114   /* Little endian order */
 115   for (i = 0; i < words; i++, digest += 4)
 116     LE_WRITE_UINT32(digest, ctx->digest[i]);
 117
 118   if (leftover)
 119     {
 120       uint32_t word;
 121       unsigned j;
 122
 123       assert(i < _MD5_DIGEST_LENGTH);
 124
 125       /* Still least significant byte first. */
 126       for (word = ctx->digest[i], j = 0; j < leftover;
 127            j++, word >>= 8)
 128         digest[j] = word & 0xff;
 129     }
 130   md5_init(ctx);
 131 }
 132
 133 /* MD5 functions */
 134 #define F1(x, y, z) ((z) ^ ((x) & ((y) ^ (z))))
 135 #define F2(x, y, z) F1((z), (x), (y))
 136 #define F3(x, y, z) ((x) ^ (y) ^ (z))
 137 #define F4(x, y, z) ((y) ^ ((x) | ~(z)))
 138
 139 #define ROUND(f, w, x, y, z, data, s) \
 140 ( w += f(x, y, z) + data,  w = w<<s | w>>(32-s),  w += x )
 141
 142 /* Perform the MD5 transformation on one full block of 16 32-bit
 143  * words.
 144  *
 145  * Compresses 20 (_MD5_DIGEST_LENGTH + MD5_DATA_LENGTH) words into 4
 146  * (_MD5_DIGEST_LENGTH) words. */
 147
 148 static void
 149 md5_transform(uint32_t *digest, const uint32_t *data)
 150 {
 151   uint32_t a, b, c, d;
 152   a = digest[0];
 153   b = digest[1];
 154   c = digest[2];
 155   d = digest[3];
 156
 157   ROUND(F1, a, b, c, d, data[ 0] + 0xd76aa478, 7);
 158   ROUND(F1, d, a, b, c, data[ 1] + 0xe8c7b756, 12);
 159   ROUND(F1, c, d, a, b, data[ 2] + 0x242070db, 17);
 160   ROUND(F1, b, c, d, a, data[ 3] + 0xc1bdceee, 22);
 161   ROUND(F1, a, b, c, d, data[ 4] + 0xf57c0faf, 7);
 162   ROUND(F1, d, a, b, c, data[ 5] + 0x4787c62a, 12);
 163   ROUND(F1, c, d, a, b, data[ 6] + 0xa8304613, 17);
 164   ROUND(F1, b, c, d, a, data[ 7] + 0xfd469501, 22);
 165   ROUND(F1, a, b, c, d, data[ 8] + 0x698098d8, 7);
 166   ROUND(F1, d, a, b, c, data[ 9] + 0x8b44f7af, 12);
 167   ROUND(F1, c, d, a, b, data[10] + 0xffff5bb1, 17);
 168   ROUND(F1, b, c, d, a, data[11] + 0x895cd7be, 22);
 169   ROUND(F1, a, b, c, d, data[12] + 0x6b901122, 7);
 170   ROUND(F1, d, a, b, c, data[13] + 0xfd987193, 12);
 171   ROUND(F1, c, d, a, b, data[14] + 0xa679438e, 17);
 172   ROUND(F1, b, c, d, a, data[15] + 0x49b40821, 22);
 173
 174   ROUND(F2, a, b, c, d, data[ 1] + 0xf61e2562, 5);
 175   ROUND(F2, d, a, b, c, data[ 6] + 0xc040b340, 9);
 176   ROUND(F2, c, d, a, b, data[11] + 0x265e5a51, 14);
 177   ROUND(F2, b, c, d, a, data[ 0] + 0xe9b6c7aa, 20);
 178   ROUND(F2, a, b, c, d, data[ 5] + 0xd62f105d, 5);
 179   ROUND(F2, d, a, b, c, data[10] + 0x02441453, 9);
 180   ROUND(F2, c, d, a, b, data[15] + 0xd8a1e681, 14);
 181   ROUND(F2, b, c, d, a, data[ 4] + 0xe7d3fbc8, 20);
 182   ROUND(F2, a, b, c, d, data[ 9] + 0x21e1cde6, 5);
 183   ROUND(F2, d, a, b, c, data[14] + 0xc33707d6, 9);
 184   ROUND(F2, c, d, a, b, data[ 3] + 0xf4d50d87, 14);
 185   ROUND(F2, b, c, d, a, data[ 8] + 0x455a14ed, 20);
 186   ROUND(F2, a, b, c, d, data[13] + 0xa9e3e905, 5);
 187   ROUND(F2, d, a, b, c, data[ 2] + 0xfcefa3f8, 9);
 188   ROUND(F2, c, d, a, b, data[ 7] + 0x676f02d9, 14);
 189   ROUND(F2, b, c, d, a, data[12] + 0x8d2a4c8a, 20);
 190
 191   ROUND(F3, a, b, c, d, data[ 5] + 0xfffa3942, 4);
 192   ROUND(F3, d, a, b, c, data[ 8] + 0x8771f681, 11);
 193   ROUND(F3, c, d, a, b, data[11] + 0x6d9d6122, 16);
 194   ROUND(F3, b, c, d, a, data[14] + 0xfde5380c, 23);
 195   ROUND(F3, a, b, c, d, data[ 1] + 0xa4beea44, 4);
 196   ROUND(F3, d, a, b, c, data[ 4] + 0x4bdecfa9, 11);
 197   ROUND(F3, c, d, a, b, data[ 7] + 0xf6bb4b60, 16);
 198   ROUND(F3, b, c, d, a, data[10] + 0xbebfbc70, 23);
 199   ROUND(F3, a, b, c, d, data[13] + 0x289b7ec6, 4);
 200   ROUND(F3, d, a, b, c, data[ 0] + 0xeaa127fa, 11);
 201   ROUND(F3, c, d, a, b, data[ 3] + 0xd4ef3085, 16);
 202   ROUND(F3, b, c, d, a, data[ 6] + 0x04881d05, 23);
 203   ROUND(F3, a, b, c, d, data[ 9] + 0xd9d4d039, 4);
 204   ROUND(F3, d, a, b, c, data[12] + 0xe6db99e5, 11);
 205   ROUND(F3, c, d, a, b, data[15] + 0x1fa27cf8, 16);
 206   ROUND(F3, b, c, d, a, data[ 2] + 0xc4ac5665, 23);
 207
 208   ROUND(F4, a, b, c, d, data[ 0] + 0xf4292244, 6);
 209   ROUND(F4, d, a, b, c, data[ 7] + 0x432aff97, 10);
 210   ROUND(F4, c, d, a, b, data[14] + 0xab9423a7, 15);
 211   ROUND(F4, b, c, d, a, data[ 5] + 0xfc93a039, 21);
 212   ROUND(F4, a, b, c, d, data[12] + 0x655b59c3, 6);
 213   ROUND(F4, d, a, b, c, data[ 3] + 0x8f0ccc92, 10);
 214   ROUND(F4, c, d, a, b, data[10] + 0xffeff47d, 15);
 215   ROUND(F4, b, c, d, a, data[ 1] + 0x85845dd1, 21);
 216   ROUND(F4, a, b, c, d, data[ 8] + 0x6fa87e4f, 6);
 217   ROUND(F4, d, a, b, c, data[15] + 0xfe2ce6e0, 10);
 218   ROUND(F4, c, d, a, b, data[ 6] + 0xa3014314, 15);
 219   ROUND(F4, b, c, d, a, data[13] + 0x4e0811a1, 21);
 220   ROUND(F4, a, b, c, d, data[ 4] + 0xf7537e82, 6);
 221   ROUND(F4, d, a, b, c, data[11] + 0xbd3af235, 10);
 222   ROUND(F4, c, d, a, b, data[ 2] + 0x2ad7d2bb, 15);
 223   ROUND(F4, b, c, d, a, data[ 9] + 0xeb86d391, 21);
 224
 225   digest[0] += a;
 226   digest[1] += b;
 227   digest[2] += c;
 228   digest[3] += d;
 229 }
 230
 231 static void
 232 md5_block(struct md5_ctx *ctx, const uint8_t *block)
 233 {
 234   uint32_t data[MD5_DATA_LENGTH];
 235   unsigned i;
 236
 237   /* Update block count */
 238   if (!++ctx->count_l)
 239     ++ctx->count_h;
 240
 241   /* Endian independent conversion */
 242   for (i = 0; i<16; i++, block += 4)
 243     data[i] = LE_READ_UINT32(block);
 244
 245   md5_transform(ctx->digest, data);
 246 }
 247
 248 /* Final wrapup - pad to MD5_DATA_SIZE-byte boundary with the bit
 249  * pattern 1 0* (64-bit count of bits processed, LSB-first) */
 250
 251 static void
 252 md5_final(struct md5_ctx *ctx)
 253 {
 254   uint32_t data[MD5_DATA_LENGTH];
 255   unsigned i;
 256   unsigned words;
 257
 258   i = ctx->index;
 259
 260   /* Set the first char of padding to 0x80. This is safe since there
 261    * is always at least one byte free */
 262   assert(i < MD5_DATA_SIZE);
 263   ctx->block[i++] = 0x80;
 264
 265   /* Fill rest of word */
 266   for( ; i & 3; i++)
 267     ctx->block[i] = 0;
 268
 269   /* i is now a multiple of the word size 4 */
 270   words = i >> 2;
 271   for (i = 0; i < words; i++)
 272     data[i] = LE_READ_UINT32(ctx->block + 4*i);
 273
 274   if (words > (MD5_DATA_LENGTH-2))
 275     { /* No room for length in this block. Process it and
 276        * pad with another one */
 277       for (i = words ; i < MD5_DATA_LENGTH; i++)
 278         data[i] = 0;
 279       md5_transform(ctx->digest, data);
 280       for (i = 0; i < (MD5_DATA_LENGTH-2); i++)
 281         data[i] = 0;
 282     }
 283   else
 284     for (i = words ; i < MD5_DATA_LENGTH - 2; i++)
 285       data[i] = 0;
 286
 287   /* There are 512 = 2^9 bits in one block
 288    * Little-endian order => Least significant word first */
 289
 290   data[MD5_DATA_LENGTH-1] = (ctx->count_h << 9) | (ctx->count_l >> 23);
 291   data[MD5_DATA_LENGTH-2] = (ctx->count_l << 9) | (ctx->index << 3);
 292   md5_transform(ctx->digest, data);
 293 }