MD4 module.
authorRusty Russell <rusty@rustcorp.com.au>
Wed, 25 Feb 2009 00:30:39 +0000 (11:00 +1030)
committerRusty Russell <rusty@rustcorp.com.au>
Wed, 25 Feb 2009 00:30:39 +0000 (11:00 +1030)
ccan/md4/_info.c [new file with mode: 0644]
ccan/md4/md4.c [new file with mode: 0644]
ccan/md4/md4.h [new file with mode: 0644]
ccan/md4/test/api.c [new file with mode: 0644]

diff --git a/ccan/md4/_info.c b/ccan/md4/_info.c
new file mode 100644 (file)
index 0000000..d3c2c42
--- /dev/null
@@ -0,0 +1,48 @@
+#include <stdio.h>
+#include <string.h>
+#include "config.h"
+
+/**
+ * md4 - MD4 Message Digest Algorithm (RFC1320).
+ *
+ * Message Digest #4 is a 128-bit hashing algorithm; it is quick but
+ * not sufficiently strong for cryptographic use (duplicates can be
+ * found very efficiently).  It provides sufficient mixing to have an
+ * avalanche effect: any change in input changes the output completely.
+ *
+ * Example:
+ *     #include <stdio.h>
+ *     #include <ccan/md4/md4.h>
+ *
+ *     // Provide MD4 sums of the input strings.
+ *     int main(int argc, char *argv[])
+ *     {
+ *             unsigned int i, j;
+ *             struct md4_ctx ctx;
+ *
+ *             for (i = 1; i < argc; i++) {
+ *                     md4_init(&ctx);
+ *                     md4_hash(&ctx, argv[i], strlen(argv[i]));
+ *                     md4_finish(&ctx);
+ *                     for (j = 0; j < 16; j++)
+ *                             printf("%02x", ctx.hash.bytes[j]);
+ *                     printf("\n");
+ *             }
+ *             return 0;
+ *     }
+ *
+ * Licence: LGPL (2 or any later version)
+ */
+int main(int argc, char *argv[])
+{
+       if (argc != 2)
+               return 1;
+
+       if (strcmp(argv[1], "depends") == 0) {
+               printf("ccan/endian\n");
+               printf("ccan/array_size\n");
+               return 0;
+       }
+
+       return 1;
+}
diff --git a/ccan/md4/md4.c b/ccan/md4/md4.c
new file mode 100644 (file)
index 0000000..476af14
--- /dev/null
@@ -0,0 +1,200 @@
+/*
+ * MD4 Message Digest Algorithm (RFC1320).
+ *
+ * Based on linux kernel 2.6.28-rc5:
+ *
+ * Implementation derived from Andrew Tridgell and Steve French's
+ * CIFS MD4 implementation, and the cryptoapi implementation
+ * originally based on the public domain implementation written
+ * by Colin Plumb in 1993.
+ *
+ * Copyright (c) Andrew Tridgell 1997-1998.
+ * Modified by Steve French (sfrench@us.ibm.com) 2002
+ * Copyright (c) Cryptoapi developers.
+ * Copyright (c) 2002 David S. Miller (davem@redhat.com)
+ * Copyright (c) 2002 James Morris <jmorris@intercode.com.au>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ */
+#include "md4.h"
+#include <ccan/endian/endian.h>
+#include <ccan/array_size/array_size.h>
+#include <string.h>
+
+static inline uint32_t lshift(uint32_t x, unsigned int s)
+{
+       x &= 0xFFFFFFFF;
+       return ((x << s) & 0xFFFFFFFF) | (x >> (32 - s));
+}
+
+static inline uint32_t F(uint32_t x, uint32_t y, uint32_t z)
+{
+       return (x & y) | ((~x) & z);
+}
+
+static inline uint32_t G(uint32_t x, uint32_t y, uint32_t z)
+{
+       return (x & y) | (x & z) | (y & z);
+}
+
+static inline uint32_t H(uint32_t x, uint32_t y, uint32_t z)
+{
+       return x ^ y ^ z;
+}
+
+#define ROUND1(a,b,c,d,k,s) (a = lshift(a + F(b,c,d) + k, s))
+#define ROUND2(a,b,c,d,k,s) (a = lshift(a + G(b,c,d) + k + (uint32_t)0x5A827999,s))
+#define ROUND3(a,b,c,d,k,s) (a = lshift(a + H(b,c,d) + k + (uint32_t)0x6ED9EBA1,s))
+
+static inline void le32_to_cpu_array(uint32_t *buf, unsigned int words)
+{
+       while (words--) {
+               *buf = le32_to_cpu(*buf);
+               buf++;
+       }
+}
+
+static inline void cpu_to_le32_array(uint32_t *buf, unsigned int words)
+{
+       while (words--) {
+               *buf = cpu_to_le32(*buf);
+               buf++;
+       }
+}
+
+static void md4_transform(uint32_t *hash, uint32_t const *in)
+{
+       uint32_t a, b, c, d;
+
+       a = hash[0];
+       b = hash[1];
+       c = hash[2];
+       d = hash[3];
+
+       ROUND1(a, b, c, d, in[0], 3);
+       ROUND1(d, a, b, c, in[1], 7);
+       ROUND1(c, d, a, b, in[2], 11);
+       ROUND1(b, c, d, a, in[3], 19);
+       ROUND1(a, b, c, d, in[4], 3);
+       ROUND1(d, a, b, c, in[5], 7);
+       ROUND1(c, d, a, b, in[6], 11);
+       ROUND1(b, c, d, a, in[7], 19);
+       ROUND1(a, b, c, d, in[8], 3);
+       ROUND1(d, a, b, c, in[9], 7);
+       ROUND1(c, d, a, b, in[10], 11);
+       ROUND1(b, c, d, a, in[11], 19);
+       ROUND1(a, b, c, d, in[12], 3);
+       ROUND1(d, a, b, c, in[13], 7);
+       ROUND1(c, d, a, b, in[14], 11);
+       ROUND1(b, c, d, a, in[15], 19);
+
+       ROUND2(a, b, c, d,in[ 0], 3);
+       ROUND2(d, a, b, c, in[4], 5);
+       ROUND2(c, d, a, b, in[8], 9);
+       ROUND2(b, c, d, a, in[12], 13);
+       ROUND2(a, b, c, d, in[1], 3);
+       ROUND2(d, a, b, c, in[5], 5);
+       ROUND2(c, d, a, b, in[9], 9);
+       ROUND2(b, c, d, a, in[13], 13);
+       ROUND2(a, b, c, d, in[2], 3);
+       ROUND2(d, a, b, c, in[6], 5);
+       ROUND2(c, d, a, b, in[10], 9);
+       ROUND2(b, c, d, a, in[14], 13);
+       ROUND2(a, b, c, d, in[3], 3);
+       ROUND2(d, a, b, c, in[7], 5);
+       ROUND2(c, d, a, b, in[11], 9);
+       ROUND2(b, c, d, a, in[15], 13);
+
+       ROUND3(a, b, c, d,in[ 0], 3);
+       ROUND3(d, a, b, c, in[8], 9);
+       ROUND3(c, d, a, b, in[4], 11);
+       ROUND3(b, c, d, a, in[12], 15);
+       ROUND3(a, b, c, d, in[2], 3);
+       ROUND3(d, a, b, c, in[10], 9);
+       ROUND3(c, d, a, b, in[6], 11);
+       ROUND3(b, c, d, a, in[14], 15);
+       ROUND3(a, b, c, d, in[1], 3);
+       ROUND3(d, a, b, c, in[9], 9);
+       ROUND3(c, d, a, b, in[5], 11);
+       ROUND3(b, c, d, a, in[13], 15);
+       ROUND3(a, b, c, d, in[3], 3);
+       ROUND3(d, a, b, c, in[11], 9);
+       ROUND3(c, d, a, b, in[7], 11);
+       ROUND3(b, c, d, a, in[15], 15);
+
+       hash[0] += a;
+       hash[1] += b;
+       hash[2] += c;
+       hash[3] += d;
+}
+
+static inline void md4_transform_helper(struct md4_ctx *ctx)
+{
+       le32_to_cpu_array(ctx->block, ARRAY_SIZE(ctx->block));
+       md4_transform(ctx->hash.words, ctx->block);
+}
+
+void md4_init(struct md4_ctx *mctx)
+{
+       mctx->hash.words[0] = 0x67452301;
+       mctx->hash.words[1] = 0xefcdab89;
+       mctx->hash.words[2] = 0x98badcfe;
+       mctx->hash.words[3] = 0x10325476;
+       mctx->byte_count = 0;
+}
+
+void md4_hash(struct md4_ctx *mctx, const void *p, size_t len)
+{
+       const unsigned char *data = p;
+       const uint32_t avail = sizeof(mctx->block) - (mctx->byte_count & 0x3f);
+
+       mctx->byte_count += len;
+
+       if (avail > len) {
+               memcpy((char *)mctx->block + (sizeof(mctx->block) - avail),
+                      data, len);
+               return;
+       }
+
+       memcpy((char *)mctx->block + (sizeof(mctx->block) - avail),
+              data, avail);
+
+       md4_transform_helper(mctx);
+       data += avail;
+       len -= avail;
+
+       while (len >= sizeof(mctx->block)) {
+               memcpy(mctx->block, data, sizeof(mctx->block));
+               md4_transform_helper(mctx);
+               data += sizeof(mctx->block);
+               len -= sizeof(mctx->block);
+       }
+
+       memcpy(mctx->block, data, len);
+}
+
+void md4_finish(struct md4_ctx *mctx)
+{
+       const unsigned int offset = mctx->byte_count & 0x3f;
+       char *p = (char *)mctx->block + offset;
+       int padding = 56 - (offset + 1);
+
+       *p++ = 0x80;
+       if (padding < 0) {
+               memset(p, 0x00, padding + sizeof (uint64_t));
+               md4_transform_helper(mctx);
+               p = (char *)mctx->block;
+               padding = 56;
+       }
+
+       memset(p, 0, padding);
+       mctx->block[14] = mctx->byte_count << 3;
+       mctx->block[15] = mctx->byte_count >> 29;
+       le32_to_cpu_array(mctx->block, (sizeof(mctx->block) -
+                         sizeof(uint64_t)) / sizeof(uint32_t));
+       md4_transform(mctx->hash.words, mctx->block);
+       cpu_to_le32_array(mctx->hash.words, ARRAY_SIZE(mctx->hash.words));
+}
diff --git a/ccan/md4/md4.h b/ccan/md4/md4.h
new file mode 100644 (file)
index 0000000..22d0b85
--- /dev/null
@@ -0,0 +1,64 @@
+#ifndef CCAN_MD4_H
+#define CCAN_MD4_H
+#include <stdint.h>
+#include <stdlib.h>
+
+/**
+ * md4_ctx - context structure for md4 hashing
+ * @hash: the 128-bit hash value (only valid after md4_finish)
+ * @block: internal working state.
+ * @byte_count: the total number of bytes processed.
+ */
+struct md4_ctx {
+       union {
+               unsigned char bytes[16];
+               uint32_t words[4];
+       } hash;
+       uint32_t block[16];
+       uint64_t byte_count;
+};
+
+/**
+ * md4_init - (re-)initialize the struct md4_ctx before md4_hash.
+ * @mctx: the struct md4_ctx which will be handed to md4_hash.
+ *
+ * Contexts can be safely re-used by calling md4_init() on them again.
+ *
+ * Example:
+ *     struct md4_ctx ctx;
+ *
+ *     md4_init(&ctx);
+ *     ...
+ */
+void md4_init(struct md4_ctx *mctx);
+
+/**
+ * md4_hash - add these bytes into the hash
+ * @mctx: the struct md4_ctx.
+ * @p: pointer to the bytes to hash.
+ * @len: the number of bytes pointed to by @p.
+ *
+ * Example:
+ *     struct md4_ctx ctx;
+ *
+ *     md4_init(&ctx);
+ *     md4_hash(&ctx, "hello", 5);
+ *     md4_hash(&ctx, " ", 1);
+ *     md4_hash(&ctx, "world", 5);
+ */
+void md4_hash(struct md4_ctx *mctx, const void *p, size_t len);
+
+/**
+ * md4_finish - complete the MD4 hash
+ * @mctx: the struct md4_ctx.
+ *
+ * Example:
+ *     struct md4_ctx ctx;
+ *
+ *     md4_init(&ctx);
+ *     md4_hash(&ctx, "hello world", strlen("hello world"));
+ *     md4_finish(&ctx);
+ */
+void md4_finish(struct md4_ctx *mctx);
+
+#endif /* CCAN_MD4_H */
diff --git a/ccan/md4/test/api.c b/ccan/md4/test/api.c
new file mode 100644 (file)
index 0000000..3981049
--- /dev/null
@@ -0,0 +1,39 @@
+#include "md4/md4.h"
+#include "md4/md4.c"
+#include <tap/tap.h>
+#include <stdio.h>
+
+static void check_md4(const char *string, const char *expected)
+{
+       struct md4_ctx ctx;
+       unsigned int i;
+       char result[33];
+
+       md4_init(&ctx);
+       md4_hash(&ctx, string, strlen(string));
+       md4_finish(&ctx);
+       for (i = 0; i < sizeof(ctx.hash.bytes); i++)
+               sprintf(result+i*2, "%02x", ctx.hash.bytes[i]);
+       ok(strcmp(result, expected) == 0,
+          "Expected %s, got %s", expected, result);
+}
+
+int main(int argc, char *argv[])
+{
+       /* Tests taken from the RFC. */
+       plan_tests(7);
+
+       check_md4("", "31d6cfe0d16ae931b73c59d7e0c089c0");
+       check_md4("a", "bde52cb31de33e46245e05fbdbd6fb24");
+       check_md4("abc", "a448017aaf21d8525fc10ae87aa6729d");
+       check_md4("message digest", "d9130a8164549fe818874806e1c7014b");
+       check_md4("abcdefghijklmnopqrstuvwxyz",
+                 "d79e1c308aa5bbcdeea8ed63df412da9");
+       check_md4("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
+                  "0123456789",
+                 "043f8582f241db351ce627e153e7f0e4");
+       check_md4("1234567890123456789012345678901234567890123456789"
+                  "0123456789012345678901234567890",
+                 "e33b4ddc9c38f2199c3e7b164fcc0536");
+       exit(exit_status());
+}