md4.c

   1 /* md4.h
   2  *
   3  * The MD4 hash function, described in RFC 1320.
   4  */
   5
   6 /* nettle, low-level cryptographics library
   7  *
   8  * Copyright (C) 2003 Niels Möller, Marcus Comstedt
   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 the public domain md5 code, and modified by Marcus
  27    Comstedt */
  28
  29 #if HAVE_CONFIG_H
  30 # include "config.h"
  31 #endif
  32
  33 #include <assert.h>
  34 #include <string.h>
  35
  36 #include "md4.h"
  37
  38 #include "macros.h"
  39
  40 /* A block, treated as a sequence of 32-bit words. */
  41 #define MD4_DATA_LENGTH 16
  42
  43 static void
  44 md4_transform(uint32_t *digest, const uint32_t *data);
  45
  46 static void
  47 md4_block(struct md4_ctx *ctx, const uint8_t *block);
  48
  49 static void
  50 md4_final(struct md4_ctx *ctx);
  51
  52 void
  53 md4_init(struct md4_ctx *ctx)
  54 {
  55   /* Same constants as for md5. */
  56   ctx->digest[0] = 0x67452301;
  57   ctx->digest[1] = 0xefcdab89;
  58   ctx->digest[2] = 0x98badcfe;
  59   ctx->digest[3] = 0x10325476;
  60
  61   ctx->count_l = ctx->count_h = 0;
  62   ctx->index = 0;
  63 }
  64
  65 void
  66 md4_update(struct md4_ctx *ctx,
  67            unsigned length,
  68            const uint8_t *data)
  69 {
  70   if (ctx->index)
  71     {
  72       /* Try to fill partial block */
  73       unsigned left = MD4_DATA_SIZE - ctx->index;
  74       if (length < left)
  75         {
  76           memcpy(ctx->block + ctx->index, data, length);
  77           ctx->index += length;
  78           return; /* Finished */
  79         }
  80       else
  81         {
  82           memcpy(ctx->block + ctx->index, data, left);
  83           md4_block(ctx, ctx->block);
  84           data += left;
  85           length -= left;
  86         }
  87     }
  88   while (length >= MD4_DATA_SIZE)
  89     {
  90       md4_block(ctx, data);
  91       data += MD4_DATA_SIZE;
  92       length -= MD4_DATA_SIZE;
  93     }
  94   if ((ctx->index = length))     /* This assignment is intended */
  95     /* Buffer leftovers */
  96     memcpy(ctx->block, data, length);
  97 }
  98
  99 void
 100 md4_digest(struct md4_ctx *ctx,
 101            unsigned length,
 102            uint8_t *digest)
 103 {
 104   unsigned i;
 105   unsigned words;
 106   unsigned leftover;
 107
 108   assert(length <= MD4_DIGEST_SIZE);
 109
 110   md4_final(ctx);
 111
 112   words = length / 4;
 113   leftover = length % 4;
 114
 115   /* Little endian order */
 116   for (i = 0; i < words; i++, digest += 4)
 117     LE_WRITE_UINT32(digest, ctx->digest[i]);
 118
 119   if (leftover)
 120     {
 121       uint32_t word;
 122       unsigned j;
 123
 124       assert(i < _MD4_DIGEST_LENGTH);
 125
 126       /* Still least significant byte first. */
 127       for (word = ctx->digest[i], j = 0; j < leftover;
 128            j++, word >>= 8)
 129         digest[j] = word & 0xff;
 130     }
 131   md4_init(ctx);
 132 }
 133
 134 /* MD4 functions */
 135 #define F(x, y, z) (((y) & (x)) | ((z) & ~(x)))
 136 #define G(x, y, z) (((y) & (x)) | ((z) & (x)) | ((y) & (z)))
 137 #define H(x, y, z) ((x) ^ (y) ^ (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) )
 141
 142 /* Perform the MD4 transformation on one full block of 16 32-bit words. */
 143
 144 static void
 145 md4_transform(uint32_t *digest, const uint32_t *data)
 146 {
 147   uint32_t a, b, c, d;
 148   a = digest[0];
 149   b = digest[1];
 150   c = digest[2];
 151   d = digest[3];
 152
 153   ROUND(F, a, b, c, d, data[ 0], 3);
 154   ROUND(F, d, a, b, c, data[ 1], 7);
 155   ROUND(F, c, d, a, b, data[ 2], 11);
 156   ROUND(F, b, c, d, a, data[ 3], 19);
 157   ROUND(F, a, b, c, d, data[ 4], 3);
 158   ROUND(F, d, a, b, c, data[ 5], 7);
 159   ROUND(F, c, d, a, b, data[ 6], 11);
 160   ROUND(F, b, c, d, a, data[ 7], 19);
 161   ROUND(F, a, b, c, d, data[ 8], 3);
 162   ROUND(F, d, a, b, c, data[ 9], 7);
 163   ROUND(F, c, d, a, b, data[10], 11);
 164   ROUND(F, b, c, d, a, data[11], 19);
 165   ROUND(F, a, b, c, d, data[12], 3);
 166   ROUND(F, d, a, b, c, data[13], 7);
 167   ROUND(F, c, d, a, b, data[14], 11);
 168   ROUND(F, b, c, d, a, data[15], 19);
 169
 170   ROUND(G, a, b, c, d, data[ 0] + 0x5a827999, 3);
 171   ROUND(G, d, a, b, c, data[ 4] + 0x5a827999, 5);
 172   ROUND(G, c, d, a, b, data[ 8] + 0x5a827999, 9);
 173   ROUND(G, b, c, d, a, data[12] + 0x5a827999, 13);
 174   ROUND(G, a, b, c, d, data[ 1] + 0x5a827999, 3);
 175   ROUND(G, d, a, b, c, data[ 5] + 0x5a827999, 5);
 176   ROUND(G, c, d, a, b, data[ 9] + 0x5a827999, 9);
 177   ROUND(G, b, c, d, a, data[13] + 0x5a827999, 13);
 178   ROUND(G, a, b, c, d, data[ 2] + 0x5a827999, 3);
 179   ROUND(G, d, a, b, c, data[ 6] + 0x5a827999, 5);
 180   ROUND(G, c, d, a, b, data[10] + 0x5a827999, 9);
 181   ROUND(G, b, c, d, a, data[14] + 0x5a827999, 13);
 182   ROUND(G, a, b, c, d, data[ 3] + 0x5a827999, 3);
 183   ROUND(G, d, a, b, c, data[ 7] + 0x5a827999, 5);
 184   ROUND(G, c, d, a, b, data[11] + 0x5a827999, 9);
 185   ROUND(G, b, c, d, a, data[15] + 0x5a827999, 13);
 186
 187   ROUND(H, a, b, c, d, data[ 0] + 0x6ed9eba1, 3);
 188   ROUND(H, d, a, b, c, data[ 8] + 0x6ed9eba1, 9);
 189   ROUND(H, c, d, a, b, data[ 4] + 0x6ed9eba1, 11);
 190   ROUND(H, b, c, d, a, data[12] + 0x6ed9eba1, 15);
 191   ROUND(H, a, b, c, d, data[ 2] + 0x6ed9eba1, 3);
 192   ROUND(H, d, a, b, c, data[10] + 0x6ed9eba1, 9);
 193   ROUND(H, c, d, a, b, data[ 6] + 0x6ed9eba1, 11);
 194   ROUND(H, b, c, d, a, data[14] + 0x6ed9eba1, 15);
 195   ROUND(H, a, b, c, d, data[ 1] + 0x6ed9eba1, 3);
 196   ROUND(H, d, a, b, c, data[ 9] + 0x6ed9eba1, 9);
 197   ROUND(H, c, d, a, b, data[ 5] + 0x6ed9eba1, 11);
 198   ROUND(H, b, c, d, a, data[13] + 0x6ed9eba1, 15);
 199   ROUND(H, a, b, c, d, data[ 3] + 0x6ed9eba1, 3);
 200   ROUND(H, d, a, b, c, data[11] + 0x6ed9eba1, 9);
 201   ROUND(H, c, d, a, b, data[ 7] + 0x6ed9eba1, 11);
 202   ROUND(H, b, c, d, a, data[15] + 0x6ed9eba1, 15);
 203
 204   digest[0] += a;
 205   digest[1] += b;
 206   digest[2] += c;
 207   digest[3] += d;
 208 }
 209
 210 static void
 211 md4_block(struct md4_ctx *ctx, const uint8_t *block)
 212 {
 213   uint32_t data[MD4_DATA_LENGTH];
 214   unsigned i;
 215
 216   /* Update block count */
 217   if (!++ctx->count_l)
 218     ++ctx->count_h;
 219
 220   /* Endian independent conversion */
 221   for (i = 0; i<16; i++, block += 4)
 222     data[i] = LE_READ_UINT32(block);
 223
 224   md4_transform(ctx->digest, data);
 225 }
 226
 227 /* Final wrapup - pad to MD4_DATA_SIZE-byte boundary with the bit
 228  * pattern 1 0* (64-bit count of bits processed, LSB-first) */
 229
 230 static void
 231 md4_final(struct md4_ctx *ctx)
 232 {
 233   uint32_t data[MD4_DATA_LENGTH];
 234   unsigned i;
 235   unsigned words;
 236
 237   i = ctx->index;
 238
 239   /* Set the first char of padding to 0x80. This is safe since there
 240    * is always at least one byte free */
 241   assert(i < MD4_DATA_SIZE);
 242   ctx->block[i++] = 0x80;
 243
 244   /* Fill rest of word */
 245   for( ; i & 3; i++)
 246     ctx->block[i] = 0;
 247
 248   /* i is now a multiple of the word size 4 */
 249   words = i >> 2;
 250   for (i = 0; i < words; i++)
 251     data[i] = LE_READ_UINT32(ctx->block + 4*i);
 252
 253   if (words > (MD4_DATA_LENGTH-2))
 254     { /* No room for length in this block. Process it and
 255        * pad with another one */
 256       for (i = words ; i < MD4_DATA_LENGTH; i++)
 257         data[i] = 0;
 258       md4_transform(ctx->digest, data);
 259       for (i = 0; i < (MD4_DATA_LENGTH-2); i++)
 260         data[i] = 0;
 261     }
 262   else
 263     for (i = words ; i < MD4_DATA_LENGTH - 2; i++)
 264       data[i] = 0;
 265
 266   /* There are 512 = 2^9 bits in one block
 267    * Little-endian order => Least significant word first */
 268
 269   data[MD4_DATA_LENGTH-1] = (ctx->count_h << 9) | (ctx->count_l >> 23);
 270   data[MD4_DATA_LENGTH-2] = (ctx->count_l << 9) | (ctx->index << 3);
 271   md4_transform(ctx->digest, data);
 272 }