From: Rusty Russell Date: Wed, 25 Feb 2009 00:30:39 +0000 (+1030) Subject: MD4 module. X-Git-Url: http://git.ozlabs.org/?p=ccan;a=commitdiff_plain;h=a16a125d3c1fae99f7a261ed65fc7d3729c4d1e5;hp=3404ba2a1b34e766628d5b9febf401011aa6753f MD4 module. --- diff --git a/ccan/md4/_info.c b/ccan/md4/_info.c new file mode 100644 index 00000000..d3c2c420 --- /dev/null +++ b/ccan/md4/_info.c @@ -0,0 +1,48 @@ +#include +#include +#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 + * #include + * + * // 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 index 00000000..476af14b --- /dev/null +++ b/ccan/md4/md4.c @@ -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 + * + * 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 +#include +#include + +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 index 00000000..22d0b85b --- /dev/null +++ b/ccan/md4/md4.h @@ -0,0 +1,64 @@ +#ifndef CCAN_MD4_H +#define CCAN_MD4_H +#include +#include + +/** + * 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 index 00000000..39810498 --- /dev/null +++ b/ccan/md4/test/api.c @@ -0,0 +1,39 @@ +#include "md4/md4.h" +#include "md4/md4.c" +#include +#include + +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()); +}