From b33278c4d640c3fc8f99a314b637b7e502fceb9c Mon Sep 17 00:00:00 2001 From: Theodore Ts'o Date: Sat, 17 Aug 2002 10:52:51 -0400 Subject: [PATCH] Modify the half MD4 hash so it is no longer endian dependent. This is a backwards incompatible change, but this should be OK since the kernel MD4 ext3 code was only in the CVS tree, and hasn't generally escaped. Add support for the TEA hash. --- lib/ext2fs/ChangeLog | 14 ++++++ lib/ext2fs/dirhash.c | 138 ++++++++++++++++++++++++++++++++++++--------------- lib/ext2fs/ext2_fs.h | 3 +- lib/ext2fs/ext2fs.h | 2 +- 4 files changed, 114 insertions(+), 43 deletions(-) diff --git a/lib/ext2fs/ChangeLog b/lib/ext2fs/ChangeLog index bf0ae7b..26db244 100644 --- a/lib/ext2fs/ChangeLog +++ b/lib/ext2fs/ChangeLog @@ -1,3 +1,17 @@ +2002-08-17 Theodore Ts'o + + * dirhash.c (ext2fs_dirhash): Change the MD4 hash in a backwards + incompatible way so that it is no longer + endian-dependent. Add the TEA hash. Allow the seed + parameter to be optional. + + * ext2_fs.h: Remove the HALF_MD4_SEED and HALF_MD4_64 hashes. + These features are all now in the HALF_MD4 hash. Add + definition for EXT2_HASH_TEA. + + * ext2fs.h (ext2fs_dirhash): Change function prototype so it takes + a pointer instead of an array. + 2002-08-16 Theodore Ts'o * ext2_err.et.in (EXT2_ET_BAD_EA_BLOCK_NUM): New error code diff --git a/lib/ext2fs/dirhash.c b/lib/ext2fs/dirhash.c index d3e0e75..5e18d14 100644 --- a/lib/ext2fs/dirhash.c +++ b/lib/ext2fs/dirhash.c @@ -16,6 +16,36 @@ #include "ext2_fs.h" #include "ext2fs.h" +/* + * Keyed 32-bit hash function using TEA in a Davis-Meyer function + * H0 = Key + * Hi = E Mi(Hi-1) + Hi-1 + * + * (see Applied Cryptography, 2nd edition, p448). + * + * Jeremy Fitzhardinge 1998 + * + * This code is made available under the terms of the GPL + */ +#define DELTA 0x9E3779B9 + +static void TEA_transform(__u32 buf[4], __u32 const in[]) +{ + __u32 sum = 0; + __u32 b0 = buf[0], b1 = buf[1]; + __u32 a = in[0], b = in[1], c = in[2], d = in[3]; + int n = 16; + + do { + sum += DELTA; + b0 += ((b1 << 4)+a) ^ (b1+sum) ^ ((b1 >> 5)+b); + b1 += ((b0 << 4)+c) ^ (b0+sum) ^ ((b0 >> 5)+d); + } while(--n); + + buf[0] += b0; + buf[1] += b1; +} + /* F, G and H are basic MD4 functions: selection, majority, parity */ #define F(x, y, z) ((z) ^ ((x) & ((y) ^ (z)))) #define G(x, y, z) (((x) & (y)) + (((x) ^ (y)) & (z))) @@ -36,7 +66,7 @@ /* * Basic cut-down MD4 transform. Returns only 32 bits of result. */ -static __u32 halfMD4Transform (__u32 buf[4], __u32 const in[]) +static void halfMD4Transform (__u32 buf[4], __u32 const in[]) { __u32 a = buf[0], b = buf[1], c = buf[2], d = buf[3]; @@ -74,9 +104,6 @@ static __u32 halfMD4Transform (__u32 buf[4], __u32 const in[]) buf[1] += b; buf[2] += c; buf[3] += d; - - return ((buf[1] + b) & ~1); /* "most hashed" word */ - /* Alternative: return sum of all words? */ } #undef ROUND @@ -101,6 +128,33 @@ static ext2_dirhash_t dx_hack_hash (const char *name, int len) return (hash0 << 1); } +static void str2hashbuf(const char *msg, int len, __u32 *buf, int num) +{ + __u32 pad, val; + int i; + + pad = (__u32)len | ((__u32)len << 8); + pad |= pad << 16; + + val = pad; + if (len > num*4) + len = num * 4; + for (i=0; i < len; i++) { + if ((i % 4) == 0) + val = pad; + val = msg[i] + (val << 8); + if ((i % 4) == 3) { + *buf++ = val; + val = pad; + num--; + } + } + if (--num >= 0) + *buf++ = val; + while (--num >= 0) + *buf++ = pad; +} + /* * Returns the hash of a filename. If len is 0 and name is NULL, then * this function can be used to test whether or not a hash version is @@ -115,60 +169,64 @@ static ext2_dirhash_t dx_hack_hash (const char *name, int len) * bits. 32 bit hashes will return 0 for the minor hash. */ errcode_t ext2fs_dirhash(int version, const char *name, int len, - const __u32 seed[4], + const __u32 *seed, ext2_dirhash_t *ret_hash, ext2_dirhash_t *ret_minor_hash) { __u32 hash; __u32 minor_hash = 0; const char *p; - int i; + int i; + __u32 in[8], buf[4]; + + /* Initialize the default seed for the hash checksum functions */ + buf[0] = 0x67452301; + buf[1] = 0xefcdab89; + buf[2] = 0x98badcfe; + buf[3] = 0x10325476; /* Check to see if the seed is all zero's */ - for (i=0; i < 4; i++) { - if (seed[i]) - break; + if (seed) { + for (i=0; i < 4; i++) { + if (seed[i]) + break; + } + if (i < 4) + memcpy(buf, seed, sizeof(buf)); } - - if (version == EXT2_HASH_LEGACY) + + switch (version) { + case EXT2_HASH_LEGACY: hash = dx_hack_hash(name, len); - else if ((version == EXT2_HASH_HALF_MD4) || - (version == EXT2_HASH_HALF_MD4_SEED) || - (version == EXT2_HASH_HALF_MD4_64)) { - char in[32]; - __u32 buf[4]; - - if ((i == 4) || (version == EXT2_HASH_HALF_MD4)) { - buf[0] = 0x67452301; - buf[1] = 0xefcdab89; - buf[2] = 0x98badcfe; - buf[3] = 0x10325476; - } else - memcpy(buf, seed, sizeof(buf)); + break; + case EXT2_HASH_HALF_MD4: p = name; - while (len) { - if (len < 32) { - memcpy(in, p, len); - memset(in+len, 0, 32-len); - hash = halfMD4Transform(buf, (__u32 *) in); - break; - } - hash = halfMD4Transform(buf, (__u32 *) p); + while (len > 0) { + str2hashbuf(p, len, in, 8); + halfMD4Transform(buf, in); len -= 32; p += 32; } - if (version == EXT2_HASH_HALF_MD4_64) - minor_hash = buf[2]; - } else { + minor_hash = buf[2]; + hash = buf[1]; + break; + case EXT2_HASH_TEA: + p = name; + while (len > 0) { + str2hashbuf(p, len, in, 4); + TEA_transform(buf, in); + len -= 16; + p += 16; + } + hash = buf[0]; + minor_hash = buf[1]; + break; + default: *ret_hash = 0; return EXT2_ET_DIRHASH_UNSUPP; } - *ret_hash = hash; + *ret_hash = hash & ~1; if (ret_minor_hash) *ret_minor_hash = minor_hash; return 0; - } - - - diff --git a/lib/ext2fs/ext2_fs.h b/lib/ext2fs/ext2_fs.h index c53b13c..f2c4ac3 100644 --- a/lib/ext2fs/ext2_fs.h +++ b/lib/ext2fs/ext2_fs.h @@ -169,8 +169,7 @@ struct ext2_dx_root_info { #define EXT2_HASH_LEGACY 0 #define EXT2_HASH_HALF_MD4 1 -#define EXT2_HASH_HALF_MD4_SEED 2 -#define EXT2_HASH_HALF_MD4_64 3 /* SEED & 64 */ +#define EXT2_HASH_TEA 2 #define EXT2_HASH_FLAG_INCOMPAT 0x1 diff --git a/lib/ext2fs/ext2fs.h b/lib/ext2fs/ext2fs.h index 507b1a3..e871f58 100644 --- a/lib/ext2fs/ext2fs.h +++ b/lib/ext2fs/ext2fs.h @@ -625,7 +625,7 @@ extern errcode_t ext2fs_write_dir_block2(ext2_filsys fs, blk_t block, /* dirhash.c */ extern errcode_t ext2fs_dirhash(int version, const char *name, int len, - const __u32 seed[4], + const __u32 *seed, ext2_dirhash_t *ret_hash, ext2_dirhash_t *ret_minor_hash); -- 1.8.3.1