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