1 /*- 2 * Copyright (c) 2010, 2013 Zheng Liu <lz@freebsd.org> 3 * Copyright (c) 2012, Vyacheslav Matyushin 4 * All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 1. Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 2. Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 * 15 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 16 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 18 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 19 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 20 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 21 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 22 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 23 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 24 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 25 * SUCH DAMAGE. 26 * 27 * $FreeBSD$ 28 */ 29 30 /* 31 * The following notice applies to the code in ext2_half_md4(): 32 * 33 * Copyright (C) 1990-2, RSA Data Security, Inc. All rights reserved. 34 * 35 * License to copy and use this software is granted provided that it 36 * is identified as the "RSA Data Security, Inc. MD4 Message-Digest 37 * Algorithm" in all material mentioning or referencing this software 38 * or this function. 39 * 40 * License is also granted to make and use derivative works provided 41 * that such works are identified as "derived from the RSA Data 42 * Security, Inc. MD4 Message-Digest Algorithm" in all material 43 * mentioning or referencing the derived work. 44 * 45 * RSA Data Security, Inc. makes no representations concerning either 46 * the merchantability of this software or the suitability of this 47 * software for any particular purpose. It is provided "as is" 48 * without express or implied warranty of any kind. 49 * 50 * These notices must be retained in any copies of any part of this 51 * documentation and/or software. 52 */ 53 54 #include <sys/param.h> 55 #include <sys/systm.h> 56 #include <sys/conf.h> 57 #include <sys/vnode.h> 58 #include <sys/stat.h> 59 #include <sys/mount.h> 60 61 #include <fs/ext2fs/htree.h> 62 #include <fs/ext2fs/inode.h> 63 #include <fs/ext2fs/ext2_mount.h> 64 #include <fs/ext2fs/ext2_extern.h> 65 66 /* F, G, and H are MD4 functions */ 67 #define F(x, y, z) (((x) & (y)) | ((~x) & (z))) 68 #define G(x, y, z) (((x) & (y)) | ((x) & (z)) | ((y) & (z))) 69 #define H(x, y, z) ((x) ^ (y) ^ (z)) 70 71 /* ROTATE_LEFT rotates x left n bits */ 72 #define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32 - (n)))) 73 74 /* 75 * FF, GG, and HH are transformations for rounds 1, 2, and 3. 76 * Rotation is separated from addition to prevent recomputation. 77 */ 78 #define FF(a, b, c, d, x, s) { \ 79 (a) += F ((b), (c), (d)) + (x); \ 80 (a) = ROTATE_LEFT ((a), (s)); \ 81 } 82 83 #define GG(a, b, c, d, x, s) { \ 84 (a) += G ((b), (c), (d)) + (x) + (uint32_t)0x5A827999; \ 85 (a) = ROTATE_LEFT ((a), (s)); \ 86 } 87 88 #define HH(a, b, c, d, x, s) { \ 89 (a) += H ((b), (c), (d)) + (x) + (uint32_t)0x6ED9EBA1; \ 90 (a) = ROTATE_LEFT ((a), (s)); \ 91 } 92 93 /* 94 * MD4 basic transformation. It transforms state based on block. 95 * 96 * This is a half md4 algorithm since Linux uses this algorithm for dir 97 * index. This function is derived from the RSA Data Security, Inc. MD4 98 * Message-Digest Algorithm and was modified as necessary. 99 * 100 * The return value of this function is uint32_t in Linux, but actually we don't 101 * need to check this value, so in our version this function doesn't return any 102 * value. 103 */ 104 static void 105 ext2_half_md4(uint32_t hash[4], uint32_t data[8]) 106 { 107 uint32_t a = hash[0], b = hash[1], c = hash[2], d = hash[3]; 108 109 /* Round 1 */ 110 FF(a, b, c, d, data[0], 3); 111 FF(d, a, b, c, data[1], 7); 112 FF(c, d, a, b, data[2], 11); 113 FF(b, c, d, a, data[3], 19); 114 FF(a, b, c, d, data[4], 3); 115 FF(d, a, b, c, data[5], 7); 116 FF(c, d, a, b, data[6], 11); 117 FF(b, c, d, a, data[7], 19); 118 119 /* Round 2 */ 120 GG(a, b, c, d, data[1], 3); 121 GG(d, a, b, c, data[3], 5); 122 GG(c, d, a, b, data[5], 9); 123 GG(b, c, d, a, data[7], 13); 124 GG(a, b, c, d, data[0], 3); 125 GG(d, a, b, c, data[2], 5); 126 GG(c, d, a, b, data[4], 9); 127 GG(b, c, d, a, data[6], 13); 128 129 /* Round 3 */ 130 HH(a, b, c, d, data[3], 3); 131 HH(d, a, b, c, data[7], 9); 132 HH(c, d, a, b, data[2], 11); 133 HH(b, c, d, a, data[6], 15); 134 HH(a, b, c, d, data[1], 3); 135 HH(d, a, b, c, data[5], 9); 136 HH(c, d, a, b, data[0], 11); 137 HH(b, c, d, a, data[4], 15); 138 139 hash[0] += a; 140 hash[1] += b; 141 hash[2] += c; 142 hash[3] += d; 143 } 144 145 /* 146 * Tiny Encryption Algorithm. 147 */ 148 static void 149 ext2_tea(uint32_t hash[4], uint32_t data[8]) 150 { 151 uint32_t tea_delta = 0x9E3779B9; 152 uint32_t sum; 153 uint32_t x = hash[0], y = hash[1]; 154 int n = 16; 155 int i = 1; 156 157 while (n-- > 0) { 158 sum = i * tea_delta; 159 x += ((y << 4) + data[0]) ^ (y + sum) ^ ((y >> 5) + data[1]); 160 y += ((x << 4) + data[2]) ^ (x + sum) ^ ((x >> 5) + data[3]); 161 i++; 162 } 163 164 hash[0] += x; 165 hash[1] += y; 166 } 167 168 static uint32_t 169 ext2_legacy_hash(const char *name, int len, int unsigned_char) 170 { 171 uint32_t h0, h1 = 0x12A3FE2D, h2 = 0x37ABE8F9; 172 uint32_t multi = 0x6D22F5; 173 const unsigned char *uname = (const unsigned char *)name; 174 const signed char *sname = (const signed char *)name; 175 int val, i; 176 177 for (i = 0; i < len; i++) { 178 if (unsigned_char) 179 val = (u_int)*uname++; 180 else 181 val = (int)*sname++; 182 183 h0 = h2 + (h1 ^ (val * multi)); 184 if (h0 & 0x80000000) 185 h0 -= 0x7FFFFFFF; 186 h2 = h1; 187 h1 = h0; 188 } 189 190 return (h1 << 1); 191 } 192 193 static void 194 ext2_prep_hashbuf(const char *src, int slen, uint32_t *dst, int dlen, 195 int unsigned_char) 196 { 197 uint32_t padding = slen | (slen << 8) | (slen << 16) | (slen << 24); 198 uint32_t buf_val; 199 const unsigned char *ubuf = (const unsigned char *)src; 200 const signed char *sbuf = (const signed char *)src; 201 int len, i; 202 int buf_byte; 203 204 if (slen > dlen) 205 len = dlen; 206 else 207 len = slen; 208 209 buf_val = padding; 210 211 for (i = 0; i < len; i++) { 212 if (unsigned_char) 213 buf_byte = (u_int)ubuf[i]; 214 else 215 buf_byte = (int)sbuf[i]; 216 217 if ((i % 4) == 0) 218 buf_val = padding; 219 220 buf_val <<= 8; 221 buf_val += buf_byte; 222 223 if ((i % 4) == 3) { 224 *dst++ = buf_val; 225 dlen -= sizeof(uint32_t); 226 buf_val = padding; 227 } 228 } 229 230 dlen -= sizeof(uint32_t); 231 if (dlen >= 0) 232 *dst++ = buf_val; 233 234 dlen -= sizeof(uint32_t); 235 while (dlen >= 0) { 236 *dst++ = padding; 237 dlen -= sizeof(uint32_t); 238 } 239 } 240 241 int 242 ext2_htree_hash(const char *name, int len, 243 uint32_t *hash_seed, int hash_version, 244 uint32_t *hash_major, uint32_t *hash_minor) 245 { 246 uint32_t hash[4]; 247 uint32_t data[8]; 248 uint32_t major = 0, minor = 0; 249 int unsigned_char = 0; 250 251 if (!name || !hash_major) 252 return (-1); 253 254 if (len < 1 || len > 255) 255 goto error; 256 257 hash[0] = 0x67452301; 258 hash[1] = 0xEFCDAB89; 259 hash[2] = 0x98BADCFE; 260 hash[3] = 0x10325476; 261 262 if (hash_seed) 263 memcpy(hash, hash_seed, sizeof(hash)); 264 265 switch (hash_version) { 266 case EXT2_HTREE_TEA_UNSIGNED: 267 unsigned_char = 1; 268 /* FALLTHROUGH */ 269 case EXT2_HTREE_TEA: 270 while (len > 0) { 271 ext2_prep_hashbuf(name, len, data, 16, unsigned_char); 272 ext2_tea(hash, data); 273 len -= 16; 274 name += 16; 275 } 276 major = hash[0]; 277 minor = hash[1]; 278 break; 279 case EXT2_HTREE_LEGACY_UNSIGNED: 280 unsigned_char = 1; 281 /* FALLTHROUGH */ 282 case EXT2_HTREE_LEGACY: 283 major = ext2_legacy_hash(name, len, unsigned_char); 284 break; 285 case EXT2_HTREE_HALF_MD4_UNSIGNED: 286 unsigned_char = 1; 287 /* FALLTHROUGH */ 288 case EXT2_HTREE_HALF_MD4: 289 while (len > 0) { 290 ext2_prep_hashbuf(name, len, data, 32, unsigned_char); 291 ext2_half_md4(hash, data); 292 len -= 32; 293 name += 32; 294 } 295 major = hash[1]; 296 minor = hash[2]; 297 break; 298 default: 299 goto error; 300 } 301 302 major &= ~1; 303 if (major == (EXT2_HTREE_EOF << 1)) 304 major = (EXT2_HTREE_EOF - 1) << 1; 305 *hash_major = major; 306 if (hash_minor) 307 *hash_minor = minor; 308 309 return (0); 310 311 error: 312 *hash_major = 0; 313 if (hash_minor) 314 *hash_minor = 0; 315 return (-1); 316 } 317