crypto/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
   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 /* Adapted from md5 code by Marcus Comstedt */
  27
  28 #if HAVE_CONFIG_H
  29 # include "config.h"
  30 #endif
  31
  32 #include <assert.h>
  33 #include <string.h>
  34
  35 #include "md4.h"
  36
  37 #include "macros.h"
  38
  39 /* A block, treated as a sequence of 32-bit words. */
  40 #define MD4_DATA_LENGTH 16
  41
  42 static void
  43 md4_transform(uint32_t *digest, const uint32_t *data);
  44
  45 static void
  46 md4_block(struct md4_ctx *ctx, const uint8_t *block);
  47
  48 static void
  49 md4_final(struct md4_ctx *ctx);
  50
  51 void
  52 md4_init(struct md4_ctx *ctx)
  53 {
  54   /* Same constants as for md5. */
  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 md4_update(struct md4_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 = MD4_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           md4_block(ctx, ctx->block);
  83           data += left;
  84           length -= left;
  85         }
  86     }
  87   while (length >= MD4_DATA_SIZE)
  88     {
  89       md4_block(ctx, data);
  90       data += MD4_DATA_SIZE;
  91       length -= MD4_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 md4_digest(struct md4_ctx *ctx,
 100            unsigned length,
 101            uint8_t *digest)
 102 {
 103   unsigned i;
 104   unsigned words;
 105   unsigned leftover;
 106
 107   assert(length <= MD4_DIGEST_SIZE);
 108
 109   md4_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 < _MD4_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   md4_init(ctx);
 131 }
 132
 133 /* MD4 functions */
 134 #define F(x, y, z) (((y) & (x)) | ((z) & ~(x)))
 135 #define G(x, y, z) (((y) & (x)) | ((z) & (x)) | ((y) & (z)))
 136 #define H(x, y, z) ((x) ^ (y) ^ (z))
 137
 138 #define ROUND(f, w, x, y, z, data, s) \
 139 ( w += f(x, y, z) + data,  w = w<<s | w>>(32-s) )
 140
 141 /* Perform the MD4 transformation on one full block of 16 32-bit words. */
 142
 143 static void
 144 md4_transform(uint32_t *digest, const uint32_t *data)
 145 {
 146   uint32_t a, b, c, d;
 147   a = digest[0];
 148   b = digest[1];
 149   c = digest[2];
 150   d = digest[3];
 151
 152   ROUND(F, a, b, c, d, data[ 0], 3);
 153   ROUND(F, d, a, b, c, data[ 1], 7);
 154   ROUND(F, c, d, a, b, data[ 2], 11);
 155   ROUND(F, b, c, d, a, data[ 3], 19);
 156   ROUND(F, a, b, c, d, data[ 4], 3);
 157   ROUND(F, d, a, b, c, data[ 5], 7);
 158   ROUND(F, c, d, a, b, data[ 6], 11);
 159   ROUND(F, b, c, d, a, data[ 7], 19);
 160   ROUND(F, a, b, c, d, data[ 8], 3);
 161   ROUND(F, d, a, b, c, data[ 9], 7);
 162   ROUND(F, c, d, a, b, data[10], 11);
 163   ROUND(F, b, c, d, a, data[11], 19);
 164   ROUND(F, a, b, c, d, data[12], 3);
 165   ROUND(F, d, a, b, c, data[13], 7);
 166   ROUND(F, c, d, a, b, data[14], 11);
 167   ROUND(F, b, c, d, a, data[15], 19);
 168
 169   ROUND(G, a, b, c, d, data[ 0] + 0x5a827999, 3);
 170   ROUND(G, d, a, b, c, data[ 4] + 0x5a827999, 5);
 171   ROUND(G, c, d, a, b, data[ 8] + 0x5a827999, 9);
 172   ROUND(G, b, c, d, a, data[12] + 0x5a827999, 13);
 173   ROUND(G, a, b, c, d, data[ 1] + 0x5a827999, 3);
 174   ROUND(G, d, a, b, c, data[ 5] + 0x5a827999, 5);
 175   ROUND(G, c, d, a, b, data[ 9] + 0x5a827999, 9);
 176   ROUND(G, b, c, d, a, data[13] + 0x5a827999, 13);
 177   ROUND(G, a, b, c, d, data[ 2] + 0x5a827999, 3);
 178   ROUND(G, d, a, b, c, data[ 6] + 0x5a827999, 5);
 179   ROUND(G, c, d, a, b, data[10] + 0x5a827999, 9);
 180   ROUND(G, b, c, d, a, data[14] + 0x5a827999, 13);
 181   ROUND(G, a, b, c, d, data[ 3] + 0x5a827999, 3);
 182   ROUND(G, d, a, b, c, data[ 7] + 0x5a827999, 5);
 183   ROUND(G, c, d, a, b, data[11] + 0x5a827999, 9);
 184   ROUND(G, b, c, d, a, data[15] + 0x5a827999, 13);
 185
 186   ROUND(H, a, b, c, d, data[ 0] + 0x6ed9eba1, 3);
 187   ROUND(H, d, a, b, c, data[ 8] + 0x6ed9eba1, 9);
 188   ROUND(H, c, d, a, b, data[ 4] + 0x6ed9eba1, 11);
 189   ROUND(H, b, c, d, a, data[12] + 0x6ed9eba1, 15);
 190   ROUND(H, a, b, c, d, data[ 2] + 0x6ed9eba1, 3);
 191   ROUND(H, d, a, b, c, data[10] + 0x6ed9eba1, 9);
 192   ROUND(H, c, d, a, b, data[ 6] + 0x6ed9eba1, 11);
 193   ROUND(H, b, c, d, a, data[14] + 0x6ed9eba1, 15);
 194   ROUND(H, a, b, c, d, data[ 1] + 0x6ed9eba1, 3);
 195   ROUND(H, d, a, b, c, data[ 9] + 0x6ed9eba1, 9);
 196   ROUND(H, c, d, a, b, data[ 5] + 0x6ed9eba1, 11);
 197   ROUND(H, b, c, d, a, data[13] + 0x6ed9eba1, 15);
 198   ROUND(H, a, b, c, d, data[ 3] + 0x6ed9eba1, 3);
 199   ROUND(H, d, a, b, c, data[11] + 0x6ed9eba1, 9);
 200   ROUND(H, c, d, a, b, data[ 7] + 0x6ed9eba1, 11);
 201   ROUND(H, b, c, d, a, data[15] + 0x6ed9eba1, 15);
 202
 203   digest[0] += a;
 204   digest[1] += b;
 205   digest[2] += c;
 206   digest[3] += d;
 207 }
 208
 209 static void
 210 md4_block(struct md4_ctx *ctx, const uint8_t *block)
 211 {
 212   uint32_t data[MD4_DATA_LENGTH];
 213   unsigned i;
 214
 215   /* Update block count */
 216   if (!++ctx->count_l)
 217     ++ctx->count_h;
 218
 219   /* Endian independent conversion */
 220   for (i = 0; i<16; i++, block += 4)
 221     data[i] = LE_READ_UINT32(block);
 222
 223   md4_transform(ctx->digest, data);
 224 }
 225
 226 /* Final wrapup - pad to MD4_DATA_SIZE-byte boundary with the bit
 227  * pattern 1 0* (64-bit count of bits processed, LSB-first) */
 228
 229 static void
 230 md4_final(struct md4_ctx *ctx)
 231 {
 232   uint32_t data[MD4_DATA_LENGTH];
 233   unsigned i;
 234   unsigned words;
 235
 236   i = ctx->index;
 237
 238   /* Set the first char of padding to 0x80. This is safe since there
 239    * is always at least one byte free */
 240   assert(i < MD4_DATA_SIZE);
 241   ctx->block[i++] = 0x80;
 242
 243   /* Fill rest of word */
 244   for( ; i & 3; i++)
 245     ctx->block[i] = 0;
 246
 247   /* i is now a multiple of the word size 4 */
 248   words = i >> 2;
 249   for (i = 0; i < words; i++)
 250     data[i] = LE_READ_UINT32(ctx->block + 4*i);
 251
 252   if (words > (MD4_DATA_LENGTH-2))
 253     { /* No room for length in this block. Process it and
 254        * pad with another one */
 255       for (i = words ; i < MD4_DATA_LENGTH; i++)
 256         data[i] = 0;
 257       md4_transform(ctx->digest, data);
 258       for (i = 0; i < (MD4_DATA_LENGTH-2); i++)
 259         data[i] = 0;
 260     }
 261   else
 262     for (i = words ; i < MD4_DATA_LENGTH - 2; i++)
 263       data[i] = 0;
 264
 265   /* There are 512 = 2^9 bits in one block
 266    * Little-endian order => Least significant word first */
 267
 268   data[MD4_DATA_LENGTH-1] = (ctx->count_h << 9) | (ctx->count_l >> 23);
 269   data[MD4_DATA_LENGTH-2] = (ctx->count_l << 9) | (ctx->index << 3);
 270   md4_transform(ctx->digest, data);
 271 }