1 /*- 2 * SPDX-License-Identifier: (BSD-2-Clause 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 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/sdt.h> 59 #include <sys/stat.h> 60 #include <sys/mount.h> 61 62 #include <fs/ext2fs/ext2fs.h> 63 #include <fs/ext2fs/fs.h> 64 #include <fs/ext2fs/htree.h> 65 #include <fs/ext2fs/inode.h> 66 #include <fs/ext2fs/ext2_mount.h> 67 #include <fs/ext2fs/ext2_extern.h> 68 69 SDT_PROVIDER_DECLARE(ext2fs); 70 /* 71 * ext2fs trace probe: 72 * arg0: verbosity. Higher numbers give more verbose messages 73 * arg1: Textual message 74 */ 75 SDT_PROBE_DEFINE2(ext2fs, , trace, hash, "int", "char*"); 76 77 /* F, G, and H are MD4 functions */ 78 #define F(x, y, z) (((x) & (y)) | ((~x) & (z))) 79 #define G(x, y, z) (((x) & (y)) | ((x) & (z)) | ((y) & (z))) 80 #define H(x, y, z) ((x) ^ (y) ^ (z)) 81 82 /* ROTATE_LEFT rotates x left n bits */ 83 #define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32 - (n)))) 84 85 /* 86 * FF, GG, and HH are transformations for rounds 1, 2, and 3. 87 * Rotation is separated from addition to prevent recomputation. 88 */ 89 #define FF(a, b, c, d, x, s) { \ 90 (a) += F ((b), (c), (d)) + (x); \ 91 (a) = ROTATE_LEFT ((a), (s)); \ 92 } 93 94 #define GG(a, b, c, d, x, s) { \ 95 (a) += G ((b), (c), (d)) + (x) + (uint32_t)0x5A827999; \ 96 (a) = ROTATE_LEFT ((a), (s)); \ 97 } 98 99 #define HH(a, b, c, d, x, s) { \ 100 (a) += H ((b), (c), (d)) + (x) + (uint32_t)0x6ED9EBA1; \ 101 (a) = ROTATE_LEFT ((a), (s)); \ 102 } 103 104 /* 105 * MD4 basic transformation. It transforms state based on block. 106 * 107 * This is a half md4 algorithm since Linux uses this algorithm for dir 108 * index. This function is derived from the RSA Data Security, Inc. MD4 109 * Message-Digest Algorithm and was modified as necessary. 110 * 111 * The return value of this function is uint32_t in Linux, but actually we don't 112 * need to check this value, so in our version this function doesn't return any 113 * value. 114 */ 115 static void 116 ext2_half_md4(uint32_t hash[4], uint32_t data[8]) 117 { 118 uint32_t a = hash[0], b = hash[1], c = hash[2], d = hash[3]; 119 120 /* Round 1 */ 121 FF(a, b, c, d, data[0], 3); 122 FF(d, a, b, c, data[1], 7); 123 FF(c, d, a, b, data[2], 11); 124 FF(b, c, d, a, data[3], 19); 125 FF(a, b, c, d, data[4], 3); 126 FF(d, a, b, c, data[5], 7); 127 FF(c, d, a, b, data[6], 11); 128 FF(b, c, d, a, data[7], 19); 129 130 /* Round 2 */ 131 GG(a, b, c, d, data[1], 3); 132 GG(d, a, b, c, data[3], 5); 133 GG(c, d, a, b, data[5], 9); 134 GG(b, c, d, a, data[7], 13); 135 GG(a, b, c, d, data[0], 3); 136 GG(d, a, b, c, data[2], 5); 137 GG(c, d, a, b, data[4], 9); 138 GG(b, c, d, a, data[6], 13); 139 140 /* Round 3 */ 141 HH(a, b, c, d, data[3], 3); 142 HH(d, a, b, c, data[7], 9); 143 HH(c, d, a, b, data[2], 11); 144 HH(b, c, d, a, data[6], 15); 145 HH(a, b, c, d, data[1], 3); 146 HH(d, a, b, c, data[5], 9); 147 HH(c, d, a, b, data[0], 11); 148 HH(b, c, d, a, data[4], 15); 149 150 hash[0] += a; 151 hash[1] += b; 152 hash[2] += c; 153 hash[3] += d; 154 } 155 156 /* 157 * Tiny Encryption Algorithm. 158 */ 159 static void 160 ext2_tea(uint32_t hash[4], uint32_t data[8]) 161 { 162 uint32_t tea_delta = 0x9E3779B9; 163 uint32_t sum; 164 uint32_t x = hash[0], y = hash[1]; 165 int n = 16; 166 int i = 1; 167 168 while (n-- > 0) { 169 sum = i * tea_delta; 170 x += ((y << 4) + data[0]) ^ (y + sum) ^ ((y >> 5) + data[1]); 171 y += ((x << 4) + data[2]) ^ (x + sum) ^ ((x >> 5) + data[3]); 172 i++; 173 } 174 175 hash[0] += x; 176 hash[1] += y; 177 } 178 179 static uint32_t 180 ext2_legacy_hash(const char *name, int len, int unsigned_char) 181 { 182 uint32_t h0, h1 = 0x12A3FE2D, h2 = 0x37ABE8F9; 183 uint32_t multi = 0x6D22F5; 184 const unsigned char *uname = (const unsigned char *)name; 185 const signed char *sname = (const signed char *)name; 186 int val, i; 187 188 for (i = 0; i < len; i++) { 189 if (unsigned_char) 190 val = (u_int)*uname++; 191 else 192 val = (int)*sname++; 193 194 h0 = h2 + (h1 ^ (val * multi)); 195 if (h0 & 0x80000000) 196 h0 -= 0x7FFFFFFF; 197 h2 = h1; 198 h1 = h0; 199 } 200 201 return (h1 << 1); 202 } 203 204 static void 205 ext2_prep_hashbuf(const char *src, int slen, uint32_t *dst, int dlen, 206 int unsigned_char) 207 { 208 uint32_t padding = slen | (slen << 8) | (slen << 16) | (slen << 24); 209 uint32_t buf_val; 210 const unsigned char *ubuf = (const unsigned char *)src; 211 const signed char *sbuf = (const signed char *)src; 212 int len, i; 213 int buf_byte; 214 215 if (slen > dlen) 216 len = dlen; 217 else 218 len = slen; 219 220 buf_val = padding; 221 222 for (i = 0; i < len; i++) { 223 if (unsigned_char) 224 buf_byte = (u_int)ubuf[i]; 225 else 226 buf_byte = (int)sbuf[i]; 227 228 if ((i % 4) == 0) 229 buf_val = padding; 230 231 buf_val <<= 8; 232 buf_val += buf_byte; 233 234 if ((i % 4) == 3) { 235 *dst++ = buf_val; 236 dlen -= sizeof(uint32_t); 237 buf_val = padding; 238 } 239 } 240 241 dlen -= sizeof(uint32_t); 242 if (dlen >= 0) 243 *dst++ = buf_val; 244 245 dlen -= sizeof(uint32_t); 246 while (dlen >= 0) { 247 *dst++ = padding; 248 dlen -= sizeof(uint32_t); 249 } 250 } 251 252 int 253 ext2_htree_hash(const char *name, int len, 254 uint32_t *hash_seed, int hash_version, 255 uint32_t *hash_major, uint32_t *hash_minor) 256 { 257 uint32_t hash[4]; 258 uint32_t data[8]; 259 uint32_t major = 0, minor = 0; 260 int unsigned_char = 0; 261 262 if (!name || !hash_major) 263 return (-1); 264 265 if (len < 1 || len > 255) 266 goto error; 267 268 hash[0] = 0x67452301; 269 hash[1] = 0xEFCDAB89; 270 hash[2] = 0x98BADCFE; 271 hash[3] = 0x10325476; 272 273 if (hash_seed) 274 memcpy(hash, hash_seed, sizeof(hash)); 275 276 switch (hash_version) { 277 case EXT2_HTREE_TEA_UNSIGNED: 278 unsigned_char = 1; 279 /* FALLTHROUGH */ 280 case EXT2_HTREE_TEA: 281 while (len > 0) { 282 ext2_prep_hashbuf(name, len, data, 16, unsigned_char); 283 ext2_tea(hash, data); 284 len -= 16; 285 name += 16; 286 } 287 major = hash[0]; 288 minor = hash[1]; 289 break; 290 case EXT2_HTREE_LEGACY_UNSIGNED: 291 unsigned_char = 1; 292 /* FALLTHROUGH */ 293 case EXT2_HTREE_LEGACY: 294 major = ext2_legacy_hash(name, len, unsigned_char); 295 break; 296 case EXT2_HTREE_HALF_MD4_UNSIGNED: 297 unsigned_char = 1; 298 /* FALLTHROUGH */ 299 case EXT2_HTREE_HALF_MD4: 300 while (len > 0) { 301 ext2_prep_hashbuf(name, len, data, 32, unsigned_char); 302 ext2_half_md4(hash, data); 303 len -= 32; 304 name += 32; 305 } 306 major = hash[1]; 307 minor = hash[2]; 308 break; 309 default: 310 SDT_PROBE2(ext2fs, , trace, hash, 1, "unexpected hash version"); 311 goto error; 312 } 313 314 major &= ~1; 315 if (major == (EXT2_HTREE_EOF << 1)) 316 major = (EXT2_HTREE_EOF - 1) << 1; 317 *hash_major = major; 318 if (hash_minor) 319 *hash_minor = minor; 320 321 return (0); 322 323 error: 324 *hash_major = 0; 325 if (hash_minor) 326 *hash_minor = 0; 327 return (-1); 328 } 329