Add implementation of the MD4 message-digest algorithm

The MD4 Message-Digest Algorithm is a cryptographic hash function developed
by Ronald Rivest in 1990.  The digest length is 128 bits.  The algorithm has
influenced later designs, such as the MD5, SHA-1 and RIPEMD algorithms. The
acronym "MD" stands for "Message Digest."

MD4 consists of 48 of these operations, grouped in three rounds of 16
operations.  F is a nonlinear function;  one function is used in each round.
Mi denotes a 32-bit block of the message input, and Ki denotes a 32-bit
constant, different for each operation.

The security of MD4 has been severely compromised.  The first full collision
attack against MD4 was published in 1995 and several newer attacks have been
published since then.  As of 2007, an attack can generate collisions in less
than 2 MD4 hash operations.  A theoretical preimage attack also exists.

MD4 is used to compute NTLM password-derived key digests (NTHASH) on
Microsoft Windows NT, XP, Vista, 7, 8, and 10.

7 files changed, 385 insertions, 7 deletions

diff --git a/.gitignore b/.gitignore
index f6c0534..ba89e20 100644
--- a/.gitignore
+++ b/.gitignore
@@ -48,6 +48,7 @@
 /crypt-symbol-vers.h
 /libcrypt.map
 /test-alg-des
+/test-alg-md4
 /test-alg-md5
 /test-alg-sha256
 /test-alg-sha512
diff --git a/LICENSING b/LICENSING
index c1df93d..74e8a09 100644
--- a/LICENSING
+++ b/LICENSING
@@ -21,7 +21,7 @@ source tree.  For specific licensing terms consult the files themselves.
    alg-des.h, alg-des.c, crypt-des.c, crypt-des-obsolete.c, gen-des-tables.c
 
  * Public domain, written by Solar Designer et al.:
-   crypt-bcrypt.c, crypt-gensalt.c, test-crypt-bcrypt.c
+   alg-md4.h, alg-md4.c, crypt-bcrypt.c, crypt-gensalt.c, test-crypt-bcrypt.c
 
  * Public domain, written by Zack Weinberg et al.:
    byteorder.h, randombytes.c, test-byteorder.c
@@ -39,10 +39,10 @@ source tree.  For specific licensing terms consult the files themselves.
  * Copyright holders unknown, no statement of license (all of these
    files are part of the testsuite and do not contribute to the
    installed library or its headers):
-   test-alg-des.c, test-alg-md5.c, test-alg-sha256.c,
-   test-alg-sha512.c, test-crypt-des.c, test-crypt-md5.c,
-   test-crypt-sha256.c, test-crypt-sha512.c, test-des-cases.h,
-   test-des-obsolete.c, test-gensalt.c
+   test-alg-des.c, test-alg-md4.c (adaption of test-alg-md5.c),
+   test-alg-md5.c, test-alg-sha256.c, test-alg-sha512.c, test-crypt-des.c,
+   test-crypt-md5.c, test-crypt-sha256.c, test-crypt-sha512.c,
+   test-des-cases.h, test-des-obsolete.c, test-gensalt.c
 
  * The NEWS file formerly contained the following copyright assertions:
 
diff --git a/Makefile.am b/Makefile.am
index d88f13f..6101389 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -113,7 +113,7 @@ check_PROGRAMS = \
 
 if ENABLE_WEAK_HASHES
 libcrypt_la_SOURCES += \
-	crypt-md5.c crypt-des.c alg-md5.c alg-des.c
+	crypt-md5.c crypt-des.c alg-md4.c alg-md5.c alg-des.c
 
 nodist_libcrypt_la_SOURCES = \
 	alg-des-tables.c
@@ -139,7 +139,7 @@ alg-des-tables.c: gen-des-tables
 	$(AM_V_GEN)./gen-des-tables$(BUILD_EXEEXT) > alg-des-tables.c.T
 	$(AM_V_at)mv -f alg-des-tables.c.T alg-des-tables.c
 
-check_PROGRAMS += test-alg-des test-alg-md5 test-crypt-des test-crypt-md5
+check_PROGRAMS += test-alg-des test-alg-md4 test-alg-md5 test-crypt-des test-crypt-md5
 endif
 
 if ENABLE_OBSOLETE_API
@@ -182,6 +182,7 @@ test_des_obsolete_LDADD = libcrypt.la
 # These tests call internal APIs that may not be accessible from the
 # fully linked shared library.
 test_alg_des_LDADD = alg-des.lo alg-des-tables.lo
+test_alg_md4_LDADD = alg-md4.lo
 test_alg_md5_LDADD = alg-md5.lo
 test_alg_sha256_LDADD = alg-sha256.lo
 test_alg_sha512_LDADD = alg-sha512.lo
diff --git a/alg-md4.c b/alg-md4.c
new file mode 100644
index 0000000..1cb8d4c
--- /dev/null
+++ b/alg-md4.c
@@ -0,0 +1,250 @@
+/*
+ * MD4 (RFC-1320) message digest.
+ * Modified from MD5 code by Andrey Panin <pazke@donpac.ru>
+ *
+ * Written by Solar Designer <solar@openwall.com> in 2001, and placed in
+ * the public domain.  There's absolutely no warranty.
+ *
+ * This differs from Colin Plumb's older public domain implementation in
+ * that no 32-bit integer data type is required, there's no compile-time
+ * endianness configuration.
+ * The primary goals are portability and ease of use.
+ *
+ * This implementation is meant to be fast, but not as fast as possible.
+ * Some known optimizations are not included to reduce source code size
+ * and avoid compile-time configuration.
+ */
+
+#include "crypt-port.h"
+#include "alg-md4.h"
+#include "byteorder.h"
+
+#include <string.h>
+
+/*
+ * The basic MD4 functions.
+ */
+#define F(x, y, z)  ((z) ^ ((x) & ((y) ^ (z))))
+#define G(x, y, z)  (((x) & (y)) | ((x) & (z)) | ((y) & (z)))
+#define H(x, y, z)  ((x) ^ (y) ^ (z))
+
+/*
+ * The MD4 transformation for all four rounds.
+ */
+#define STEP(f, a, b, c, d, x, s) \
+  (a) += f((b), (c), (d)) + (x);   \
+  (a) = ((a) << (s)) | ((a) >> (32 - (s)))
+
+/*
+ * SET reads 4 input bytes in little-endian byte order and stores them
+ * in a properly aligned word in host byte order.
+ *
+ * The check for little-endian architectures which tolerate unaligned
+ * memory accesses is just an optimization.  Nothing will break if it
+ * doesn't work.
+ */
+#define SET(n) \
+  (ctx->block[(n)] = le32_to_cpu (&ptr[(n) * 4]))
+#define GET(n) \
+  (ctx->block[(n)])
+
+/*
+ * This processes one or more 64-byte data blocks, but does NOT update
+ * the bit counters.  There're no alignment requirements.
+ */
+static const unsigned char *
+body (struct md4_ctx *ctx, const unsigned char *data, size_t size)
+{
+  const unsigned char *ptr;
+  uint32_t a, b, c, d;
+  uint32_t saved_a, saved_b, saved_c, saved_d;
+
+  ptr = data;
+
+  a = ctx->a;
+  b = ctx->b;
+  c = ctx->c;
+  d = ctx->d;
+
+  do
+  {
+    saved_a = a;
+    saved_b = b;
+    saved_c = c;
+    saved_d = d;
+
+    /* Round 1 */
+    STEP(F, a, b, c, d, SET( 0),  3);
+    STEP(F, d, a, b, c, SET( 1),  7);
+    STEP(F, c, d, a, b, SET( 2), 11);
+    STEP(F, b, c, d, a, SET( 3), 19);
+
+    STEP(F, a, b, c, d, SET( 4),  3);
+    STEP(F, d, a, b, c, SET( 5),  7);
+    STEP(F, c, d, a, b, SET( 6), 11);
+    STEP(F, b, c, d, a, SET( 7), 19);
+
+    STEP(F, a, b, c, d, SET( 8),  3);
+    STEP(F, d, a, b, c, SET( 9),  7);
+    STEP(F, c, d, a, b, SET(10), 11);
+    STEP(F, b, c, d, a, SET(11), 19);
+
+    STEP(F, a, b, c, d, SET(12),  3);
+    STEP(F, d, a, b, c, SET(13),  7);
+    STEP(F, c, d, a, b, SET(14), 11);
+    STEP(F, b, c, d, a, SET(15), 19);
+
+    /* Round 2 */
+    STEP(G, a, b, c, d, GET( 0) + 0x5A827999,  3);
+    STEP(G, d, a, b, c, GET( 4) + 0x5A827999,  5);
+    STEP(G, c, d, a, b, GET( 8) + 0x5A827999,  9);
+    STEP(G, b, c, d, a, GET(12) + 0x5A827999, 13);
+
+    STEP(G, a, b, c, d, GET( 1) + 0x5A827999,  3);
+    STEP(G, d, a, b, c, GET( 5) + 0x5A827999,  5);
+    STEP(G, c, d, a, b, GET( 9) + 0x5A827999,  9);
+    STEP(G, b, c, d, a, GET(13) + 0x5A827999, 13);
+
+    STEP(G, a, b, c, d, GET( 2) + 0x5A827999,  3);
+    STEP(G, d, a, b, c, GET( 6) + 0x5A827999,  5);
+    STEP(G, c, d, a, b, GET(10) + 0x5A827999,  9);
+    STEP(G, b, c, d, a, GET(14) + 0x5A827999, 13);
+
+    STEP(G, a, b, c, d, GET( 3) + 0x5A827999,  3);
+    STEP(G, d, a, b, c, GET( 7) + 0x5A827999,  5);
+    STEP(G, c, d, a, b, GET(11) + 0x5A827999,  9);
+    STEP(G, b, c, d, a, GET(15) + 0x5A827999, 13);
+
+    /* Round 3 */
+    STEP(H, a, b, c, d, GET( 0) + 0x6ED9EBA1,  3);
+    STEP(H, d, a, b, c, GET( 8) + 0x6ED9EBA1,  9);
+    STEP(H, c, d, a, b, GET( 4) + 0x6ED9EBA1, 11);
+    STEP(H, b, c, d, a, GET(12) + 0x6ED9EBA1, 15);
+
+    STEP(H, a, b, c, d, GET( 2) + 0x6ED9EBA1,  3);
+    STEP(H, d, a, b, c, GET(10) + 0x6ED9EBA1,  9);
+    STEP(H, c, d, a, b, GET( 6) + 0x6ED9EBA1, 11);
+    STEP(H, b, c, d, a, GET(14) + 0x6ED9EBA1, 15);
+
+    STEP(H, a, b, c, d, GET( 1) + 0x6ED9EBA1,  3);
+    STEP(H, d, a, b, c, GET( 9) + 0x6ED9EBA1,  9);
+    STEP(H, c, d, a, b, GET( 5) + 0x6ED9EBA1, 11);
+    STEP(H, b, c, d, a, GET(13) + 0x6ED9EBA1, 15);
+
+    STEP(H, a, b, c, d, GET( 3) + 0x6ED9EBA1,  3);
+    STEP(H, d, a, b, c, GET(11) + 0x6ED9EBA1,  9);
+    STEP(H, c, d, a, b, GET( 7) + 0x6ED9EBA1, 11);
+    STEP(H, b, c, d, a, GET(15) + 0x6ED9EBA1, 15);
+
+    a += saved_a;
+    b += saved_b;
+    c += saved_c;
+    d += saved_d;
+
+    ptr += 64;
+  } while (size -= 64);
+
+  ctx->a = a;
+  ctx->b = b;
+  ctx->c = c;
+  ctx->d = d;
+
+  return ptr;
+}
+
+/* Put result from CTX in first 16 bytes following RESBUF.  The result
+   will be in little endian byte order.  */
+static void *
+md4_read_ctx (const struct md4_ctx *ctx, void *resbuf)
+{
+  unsigned char *buf = resbuf;
+  cpu_to_le32 (buf +  0, ctx->a);
+  cpu_to_le32 (buf +  4, ctx->b);
+  cpu_to_le32 (buf +  8, ctx->c);
+  cpu_to_le32 (buf + 12, ctx->d);
+  return resbuf;
+}
+
+void
+md4_init_ctx (struct md4_ctx *ctx)
+{
+  ctx->a = 0x67452301;
+  ctx->b = 0xefcdab89;
+  ctx->c = 0x98badcfe;
+  ctx->d = 0x10325476;
+
+  ctx->lo = 0;
+  ctx->hi = 0;
+}
+
+void
+md4_process_bytes (const void *buffer, struct md4_ctx *ctx, size_t size)
+{
+  uint32_t saved_lo;
+  size_t used, free;
+
+  saved_lo = ctx->lo;
+  if ((ctx->lo = (saved_lo + size) & 0x1fffffff) < saved_lo)
+    ctx->hi++;
+  ctx->hi += (uint32_t)(size >> 29);
+
+  used = saved_lo & 0x3f;
+
+  if (used) {
+    free = 64 - used;
+
+    if (size < free) {
+      memcpy(&ctx->buffer[used], buffer, size);
+      return;
+    }
+
+    memcpy(&ctx->buffer[used], buffer, free);
+    buffer = (const unsigned char *) buffer + free;
+    size -= free;
+    body(ctx, ctx->buffer, 64);
+  }
+
+  if (size >= 64) {
+    buffer = body(ctx, buffer, size & ~(uint32_t)0x3f);
+    size &= 0x3f;
+  }
+
+  memcpy(ctx->buffer, buffer, size);
+}
+
+void
+md4_finish_ctx (struct md4_ctx *ctx, void *resbuf)
+{
+  size_t used, free;
+
+  used = ctx->lo & 0x3f;
+
+  ctx->buffer[used++] = 0x80;
+
+  free = 64 - used;
+
+  if (free < 8) {
+    memset(&ctx->buffer[used], 0, free);
+    body(ctx, ctx->buffer, 64);
+    used = 0;
+    free = 64;
+  }
+
+  memset(&ctx->buffer[used], 0, free - 8);
+
+  ctx->lo <<= 3;
+  ctx->buffer[56] = (unsigned char)((ctx->lo) & 0xff);
+  ctx->buffer[57] = (unsigned char)((ctx->lo >> 8) & 0xff);
+  ctx->buffer[58] = (unsigned char)((ctx->lo >> 16) & 0xff);
+  ctx->buffer[59] = (unsigned char)((ctx->lo >> 24) & 0xff);
+  ctx->buffer[60] = (unsigned char)((ctx->hi) & 0xff);
+  ctx->buffer[61] = (unsigned char)((ctx->hi >> 8) & 0xff);
+  ctx->buffer[62] = (unsigned char)((ctx->hi >> 16) & 0xff);
+  ctx->buffer[63] = (unsigned char)((ctx->hi >> 24) & 0xff);
+
+  body(ctx, ctx->buffer, 64);
+
+  md4_read_ctx (ctx, resbuf);
+
+  memset(ctx, 0, sizeof(*ctx));
+}
diff --git a/alg-md4.h b/alg-md4.h
new file mode 100644
index 0000000..fa9c27f
--- /dev/null
+++ b/alg-md4.h
@@ -0,0 +1,37 @@
+/*
+ * This is an implementation of the RSA Data Security, Inc.
+ * MD4 Message-Digest Algorithm.
+ *
+ * Written by Solar Designer <solar@openwall.com> in 2001, and placed in
+ * the public domain.  See md4.c for more information.
+ */
+
+#ifndef _CRYPT_ALG_MD4_H
+#define _CRYPT_ALG_MD4_H 1
+
+#include <stddef.h>
+#include <stdint.h>
+
+/* Structure to save state of computation between the single steps.  */
+struct md4_ctx
+{
+  uint32_t lo, hi;
+  uint32_t a, b, c, d;
+  unsigned char buffer[64];
+  uint32_t block[16];
+};
+
+/* Initialize structure containing state of computation.
+   (RFC 1320, 3.3: Step 3)  */
+extern void md4_init_ctx (struct md4_ctx *ctx);
+
+/* Starting with the result of former calls of this function (or the
+   initialization function) update the context for the next LEN bytes
+   starting at BUFFER.  LEN does not need to be a multiple of 64.  */
+extern void md4_process_bytes (const void *buffer, struct md4_ctx *ctx, size_t size);
+
+/* Process the remaining bytes in the buffer and write the finalized
+   hash to RESBUF, which should point to 16 bytes of storage.  */
+extern void md4_finish_ctx (struct md4_ctx *ctx, void *resbuf);
+
+#endif
diff --git a/crypt-port.h b/crypt-port.h
index 89eee87..d42eae2 100644
--- a/crypt-port.h
+++ b/crypt-port.h
@@ -202,6 +202,9 @@ typedef union
 #define ip_maskr                 _crypt_ip_maskr
 #define key_perm_maskl           _crypt_key_perm_maskl
 #define key_perm_maskr           _crypt_key_perm_maskr
+#define md4_finish_ctx           _crypt_md4_finish_ctx
+#define md4_init_ctx             _crypt_md4_init_ctx
+#define md4_process_bytes        _crypt_md4_process_bytes
 #define md5_finish_ctx           _crypt_md5_finish_ctx
 #define md5_init_ctx             _crypt_md5_init_ctx
 #define md5_process_bytes        _crypt_md5_process_bytes
diff --git a/test-alg-md4.c b/test-alg-md4.c
new file mode 100644
index 0000000..c00c522
--- /dev/null
+++ b/test-alg-md4.c
@@ -0,0 +1,86 @@
+#include "crypt-port.h"
+#include "alg-md4.h"
+
+#include <stdio.h>
+#include <string.h>
+
+static const struct
+{
+  const char *input;
+  const char result[16];
+} tests[] =
+  {
+    /* Test vectors as defined in RFC 1320, appendix A, section 5.
+       https://tools.ietf.org/html/rfc1320#appendix-A.5  */
+    { "",
+      "\x31\xd6\xcf\xe0\xd1\x6a\xe9\x31\xb7\x3c\x59\xd7\xe0\xc0\x89\xc0" },
+    { "a",
+      "\xbd\xe5\x2c\xb3\x1d\xe3\x3e\x46\x24\x5e\x05\xfb\xdb\xd6\xfb\x24" },
+    { "abc",
+      "\xa4\x48\x01\x7a\xaf\x21\xd8\x52\x5f\xc1\x0a\xe8\x7a\xa6\x72\x9d" },
+    { "message digest",
+      "\xd9\x13\x0a\x81\x64\x54\x9f\xe8\x18\x87\x48\x06\xe1\xc7\x01\x4b" },
+    { "abcdefghijklmnopqrstuvwxyz",
+      "\xd7\x9e\x1c\x30\x8a\xa5\xbb\xcd\xee\xa8\xed\x63\xdf\x41\x2d\xa9" },
+    { "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789",
+      "\x04\x3f\x85\x82\xf2\x41\xdb\x35\x1c\xe6\x27\xe1\x53\xe7\xf0\xe4" },
+    { "12345678901234567890123456789012345678901234567890123456789012345678901234567890",
+      "\xe3\x3b\x4d\xdc\x9c\x38\xf2\x19\x9c\x3e\x7b\x16\x4f\xcc\x05\x36" }
+  };
+
+static void
+report_failure(int n, const char *tag,
+               const char expected[16], const char actual[16])
+{
+  int i;
+  printf ("FAIL: test %d (%s):\n  exp:", n, tag);
+  for (i = 0; i < 16; i++)
+    {
+      if (i % 4 == 0)
+        putchar (' ');
+      printf ("%02x", (unsigned int)(unsigned char)expected[i]);
+    }
+  printf ("\n  got:");
+  for (i = 0; i < 16; i++)
+    {
+      if (i % 4 == 0)
+        putchar (' ');
+      printf ("%02x", (unsigned int)(unsigned char)actual[i]);
+    }
+  putchar ('\n');
+  putchar ('\n');
+}
+
+int
+main (void)
+{
+  struct md4_ctx ctx;
+  char sum[16];
+  int result = 0;
+  int cnt;
+  int i;
+
+  for (cnt = 0; cnt < (int) (sizeof (tests) / sizeof (tests[0])); ++cnt)
+    {
+      md4_init_ctx (&ctx);
+      md4_process_bytes ((const unsigned char*)tests[cnt].input, &ctx, strlen (tests[cnt].input));
+      md4_finish_ctx (&ctx, (unsigned char*)sum);
+      if (memcmp (tests[cnt].result, sum, 16))
+        {
+          report_failure (cnt, "all at once", tests[cnt].result, sum);
+          result = 1;
+        }
+
+      md4_init_ctx (&ctx);
+      for (i = 0; tests[cnt].input[i] != '\0'; ++i)
+        md4_process_bytes ((const unsigned char*)&tests[cnt].input[i], &ctx, 1);
+      md4_finish_ctx (&ctx, (unsigned char*)sum);
+      if (memcmp (tests[cnt].result, sum, 16))
+        {
+          report_failure (cnt, "byte by byte", tests[cnt].result, sum);
+          result = 1;
+        }
+    }
+
+  return result;
+}