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