19824e4adSPedro F. Giffuni /*- 262cf53fdSPedro F. Giffuni * SPDX-License-Identifier: (BSD-2-Clause-FreeBSD AND RSA-MD) 3d63027b6SPedro F. Giffuni * 49824e4adSPedro F. Giffuni * Copyright (c) 2010, 2013 Zheng Liu <lz@freebsd.org> 59824e4adSPedro F. Giffuni * Copyright (c) 2012, Vyacheslav Matyushin 69824e4adSPedro F. Giffuni * All rights reserved. 79824e4adSPedro F. Giffuni * 89824e4adSPedro F. Giffuni * Redistribution and use in source and binary forms, with or without 99824e4adSPedro F. Giffuni * modification, are permitted provided that the following conditions 109824e4adSPedro F. Giffuni * are met: 119824e4adSPedro F. Giffuni * 1. Redistributions of source code must retain the above copyright 129824e4adSPedro F. Giffuni * notice, this list of conditions and the following disclaimer. 139824e4adSPedro F. Giffuni * 2. Redistributions in binary form must reproduce the above copyright 149824e4adSPedro F. Giffuni * notice, this list of conditions and the following disclaimer in the 159824e4adSPedro F. Giffuni * documentation and/or other materials provided with the distribution. 169824e4adSPedro F. Giffuni * 179824e4adSPedro F. Giffuni * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 189824e4adSPedro F. Giffuni * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 199824e4adSPedro F. Giffuni * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 209824e4adSPedro F. Giffuni * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 219824e4adSPedro F. Giffuni * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 229824e4adSPedro F. Giffuni * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 239824e4adSPedro F. Giffuni * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 249824e4adSPedro F. Giffuni * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 259824e4adSPedro F. Giffuni * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 269824e4adSPedro F. Giffuni * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 279824e4adSPedro F. Giffuni * SUCH DAMAGE. 289824e4adSPedro F. Giffuni * 299824e4adSPedro F. Giffuni * $FreeBSD$ 309824e4adSPedro F. Giffuni */ 319824e4adSPedro F. Giffuni 329824e4adSPedro F. Giffuni /* 339824e4adSPedro F. Giffuni * The following notice applies to the code in ext2_half_md4(): 349824e4adSPedro F. Giffuni * 359824e4adSPedro F. Giffuni * Copyright (C) 1990-2, RSA Data Security, Inc. All rights reserved. 369824e4adSPedro F. Giffuni * 379824e4adSPedro F. Giffuni * License to copy and use this software is granted provided that it 389824e4adSPedro F. Giffuni * is identified as the "RSA Data Security, Inc. MD4 Message-Digest 399824e4adSPedro F. Giffuni * Algorithm" in all material mentioning or referencing this software 409824e4adSPedro F. Giffuni * or this function. 419824e4adSPedro F. Giffuni * 429824e4adSPedro F. Giffuni * License is also granted to make and use derivative works provided 439824e4adSPedro F. Giffuni * that such works are identified as "derived from the RSA Data 449824e4adSPedro F. Giffuni * Security, Inc. MD4 Message-Digest Algorithm" in all material 459824e4adSPedro F. Giffuni * mentioning or referencing the derived work. 469824e4adSPedro F. Giffuni * 479824e4adSPedro F. Giffuni * RSA Data Security, Inc. makes no representations concerning either 489824e4adSPedro F. Giffuni * the merchantability of this software or the suitability of this 499824e4adSPedro F. Giffuni * software for any particular purpose. It is provided "as is" 509824e4adSPedro F. Giffuni * without express or implied warranty of any kind. 519824e4adSPedro F. Giffuni * 529824e4adSPedro F. Giffuni * These notices must be retained in any copies of any part of this 539824e4adSPedro F. Giffuni * documentation and/or software. 549824e4adSPedro F. Giffuni */ 559824e4adSPedro F. Giffuni 569824e4adSPedro F. Giffuni #include <sys/param.h> 579824e4adSPedro F. Giffuni #include <sys/systm.h> 589824e4adSPedro F. Giffuni #include <sys/conf.h> 599824e4adSPedro F. Giffuni #include <sys/vnode.h> 609824e4adSPedro F. Giffuni #include <sys/stat.h> 619824e4adSPedro F. Giffuni #include <sys/mount.h> 629824e4adSPedro F. Giffuni 63*3acd9182SFedor Uporov #include <fs/ext2fs/ext2fs.h> 649824e4adSPedro F. Giffuni #include <fs/ext2fs/htree.h> 659824e4adSPedro F. Giffuni #include <fs/ext2fs/inode.h> 669824e4adSPedro F. Giffuni #include <fs/ext2fs/ext2_mount.h> 679824e4adSPedro F. Giffuni #include <fs/ext2fs/ext2_extern.h> 689824e4adSPedro F. Giffuni 699824e4adSPedro F. Giffuni /* F, G, and H are MD4 functions */ 709824e4adSPedro F. Giffuni #define F(x, y, z) (((x) & (y)) | ((~x) & (z))) 719824e4adSPedro F. Giffuni #define G(x, y, z) (((x) & (y)) | ((x) & (z)) | ((y) & (z))) 729824e4adSPedro F. Giffuni #define H(x, y, z) ((x) ^ (y) ^ (z)) 739824e4adSPedro F. Giffuni 749824e4adSPedro F. Giffuni /* ROTATE_LEFT rotates x left n bits */ 759824e4adSPedro F. Giffuni #define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32 - (n)))) 769824e4adSPedro F. Giffuni 779824e4adSPedro F. Giffuni /* 789824e4adSPedro F. Giffuni * FF, GG, and HH are transformations for rounds 1, 2, and 3. 799824e4adSPedro F. Giffuni * Rotation is separated from addition to prevent recomputation. 809824e4adSPedro F. Giffuni */ 819824e4adSPedro F. Giffuni #define FF(a, b, c, d, x, s) { \ 829824e4adSPedro F. Giffuni (a) += F ((b), (c), (d)) + (x); \ 839824e4adSPedro F. Giffuni (a) = ROTATE_LEFT ((a), (s)); \ 849824e4adSPedro F. Giffuni } 859824e4adSPedro F. Giffuni 869824e4adSPedro F. Giffuni #define GG(a, b, c, d, x, s) { \ 879824e4adSPedro F. Giffuni (a) += G ((b), (c), (d)) + (x) + (uint32_t)0x5A827999; \ 889824e4adSPedro F. Giffuni (a) = ROTATE_LEFT ((a), (s)); \ 899824e4adSPedro F. Giffuni } 909824e4adSPedro F. Giffuni 919824e4adSPedro F. Giffuni #define HH(a, b, c, d, x, s) { \ 929824e4adSPedro F. Giffuni (a) += H ((b), (c), (d)) + (x) + (uint32_t)0x6ED9EBA1; \ 939824e4adSPedro F. Giffuni (a) = ROTATE_LEFT ((a), (s)); \ 949824e4adSPedro F. Giffuni } 959824e4adSPedro F. Giffuni 969824e4adSPedro F. Giffuni /* 979824e4adSPedro F. Giffuni * MD4 basic transformation. It transforms state based on block. 989824e4adSPedro F. Giffuni * 999824e4adSPedro F. Giffuni * This is a half md4 algorithm since Linux uses this algorithm for dir 1009824e4adSPedro F. Giffuni * index. This function is derived from the RSA Data Security, Inc. MD4 1019824e4adSPedro F. Giffuni * Message-Digest Algorithm and was modified as necessary. 1029824e4adSPedro F. Giffuni * 1039824e4adSPedro F. Giffuni * The return value of this function is uint32_t in Linux, but actually we don't 1049824e4adSPedro F. Giffuni * need to check this value, so in our version this function doesn't return any 1059824e4adSPedro F. Giffuni * value. 1069824e4adSPedro F. Giffuni */ 1079824e4adSPedro F. Giffuni static void 1089824e4adSPedro F. Giffuni ext2_half_md4(uint32_t hash[4], uint32_t data[8]) 1099824e4adSPedro F. Giffuni { 1109824e4adSPedro F. Giffuni uint32_t a = hash[0], b = hash[1], c = hash[2], d = hash[3]; 1119824e4adSPedro F. Giffuni 1129824e4adSPedro F. Giffuni /* Round 1 */ 1139824e4adSPedro F. Giffuni FF(a, b, c, d, data[0], 3); 1149824e4adSPedro F. Giffuni FF(d, a, b, c, data[1], 7); 1159824e4adSPedro F. Giffuni FF(c, d, a, b, data[2], 11); 1169824e4adSPedro F. Giffuni FF(b, c, d, a, data[3], 19); 1179824e4adSPedro F. Giffuni FF(a, b, c, d, data[4], 3); 1189824e4adSPedro F. Giffuni FF(d, a, b, c, data[5], 7); 1199824e4adSPedro F. Giffuni FF(c, d, a, b, data[6], 11); 1209824e4adSPedro F. Giffuni FF(b, c, d, a, data[7], 19); 1219824e4adSPedro F. Giffuni 1229824e4adSPedro F. Giffuni /* Round 2 */ 1239824e4adSPedro F. Giffuni GG(a, b, c, d, data[1], 3); 1249824e4adSPedro F. Giffuni GG(d, a, b, c, data[3], 5); 1259824e4adSPedro F. Giffuni GG(c, d, a, b, data[5], 9); 1269824e4adSPedro F. Giffuni GG(b, c, d, a, data[7], 13); 1279824e4adSPedro F. Giffuni GG(a, b, c, d, data[0], 3); 1289824e4adSPedro F. Giffuni GG(d, a, b, c, data[2], 5); 1299824e4adSPedro F. Giffuni GG(c, d, a, b, data[4], 9); 1309824e4adSPedro F. Giffuni GG(b, c, d, a, data[6], 13); 1319824e4adSPedro F. Giffuni 1329824e4adSPedro F. Giffuni /* Round 3 */ 1339824e4adSPedro F. Giffuni HH(a, b, c, d, data[3], 3); 1349824e4adSPedro F. Giffuni HH(d, a, b, c, data[7], 9); 1359824e4adSPedro F. Giffuni HH(c, d, a, b, data[2], 11); 1369824e4adSPedro F. Giffuni HH(b, c, d, a, data[6], 15); 1379824e4adSPedro F. Giffuni HH(a, b, c, d, data[1], 3); 1389824e4adSPedro F. Giffuni HH(d, a, b, c, data[5], 9); 1399824e4adSPedro F. Giffuni HH(c, d, a, b, data[0], 11); 1409824e4adSPedro F. Giffuni HH(b, c, d, a, data[4], 15); 1419824e4adSPedro F. Giffuni 1429824e4adSPedro F. Giffuni hash[0] += a; 1439824e4adSPedro F. Giffuni hash[1] += b; 1449824e4adSPedro F. Giffuni hash[2] += c; 1459824e4adSPedro F. Giffuni hash[3] += d; 1469824e4adSPedro F. Giffuni } 1479824e4adSPedro F. Giffuni 1489824e4adSPedro F. Giffuni /* 1499824e4adSPedro F. Giffuni * Tiny Encryption Algorithm. 1509824e4adSPedro F. Giffuni */ 1519824e4adSPedro F. Giffuni static void 1529824e4adSPedro F. Giffuni ext2_tea(uint32_t hash[4], uint32_t data[8]) 1539824e4adSPedro F. Giffuni { 1549824e4adSPedro F. Giffuni uint32_t tea_delta = 0x9E3779B9; 1559824e4adSPedro F. Giffuni uint32_t sum; 1569824e4adSPedro F. Giffuni uint32_t x = hash[0], y = hash[1]; 1579824e4adSPedro F. Giffuni int n = 16; 1589824e4adSPedro F. Giffuni int i = 1; 1599824e4adSPedro F. Giffuni 1609824e4adSPedro F. Giffuni while (n-- > 0) { 1619824e4adSPedro F. Giffuni sum = i * tea_delta; 1629824e4adSPedro F. Giffuni x += ((y << 4) + data[0]) ^ (y + sum) ^ ((y >> 5) + data[1]); 1639824e4adSPedro F. Giffuni y += ((x << 4) + data[2]) ^ (x + sum) ^ ((x >> 5) + data[3]); 1649824e4adSPedro F. Giffuni i++; 1659824e4adSPedro F. Giffuni } 1669824e4adSPedro F. Giffuni 1679824e4adSPedro F. Giffuni hash[0] += x; 1689824e4adSPedro F. Giffuni hash[1] += y; 1699824e4adSPedro F. Giffuni } 1709824e4adSPedro F. Giffuni 1719824e4adSPedro F. Giffuni static uint32_t 1729824e4adSPedro F. Giffuni ext2_legacy_hash(const char *name, int len, int unsigned_char) 1739824e4adSPedro F. Giffuni { 1749824e4adSPedro F. Giffuni uint32_t h0, h1 = 0x12A3FE2D, h2 = 0x37ABE8F9; 1759824e4adSPedro F. Giffuni uint32_t multi = 0x6D22F5; 1769824e4adSPedro F. Giffuni const unsigned char *uname = (const unsigned char *)name; 1779824e4adSPedro F. Giffuni const signed char *sname = (const signed char *)name; 1789824e4adSPedro F. Giffuni int val, i; 1799824e4adSPedro F. Giffuni 1809824e4adSPedro F. Giffuni for (i = 0; i < len; i++) { 1819824e4adSPedro F. Giffuni if (unsigned_char) 1829824e4adSPedro F. Giffuni val = (u_int)*uname++; 1839824e4adSPedro F. Giffuni else 1849824e4adSPedro F. Giffuni val = (int)*sname++; 1859824e4adSPedro F. Giffuni 1869824e4adSPedro F. Giffuni h0 = h2 + (h1 ^ (val * multi)); 1879824e4adSPedro F. Giffuni if (h0 & 0x80000000) 1889824e4adSPedro F. Giffuni h0 -= 0x7FFFFFFF; 1899824e4adSPedro F. Giffuni h2 = h1; 1909824e4adSPedro F. Giffuni h1 = h0; 1919824e4adSPedro F. Giffuni } 1929824e4adSPedro F. Giffuni 1939824e4adSPedro F. Giffuni return (h1 << 1); 1949824e4adSPedro F. Giffuni } 1959824e4adSPedro F. Giffuni 1969824e4adSPedro F. Giffuni static void 1979824e4adSPedro F. Giffuni ext2_prep_hashbuf(const char *src, int slen, uint32_t *dst, int dlen, 1989824e4adSPedro F. Giffuni int unsigned_char) 1999824e4adSPedro F. Giffuni { 2009824e4adSPedro F. Giffuni uint32_t padding = slen | (slen << 8) | (slen << 16) | (slen << 24); 2019824e4adSPedro F. Giffuni uint32_t buf_val; 2029824e4adSPedro F. Giffuni const unsigned char *ubuf = (const unsigned char *)src; 2039824e4adSPedro F. Giffuni const signed char *sbuf = (const signed char *)src; 2049824e4adSPedro F. Giffuni int len, i; 2059824e4adSPedro F. Giffuni int buf_byte; 2069824e4adSPedro F. Giffuni 2079824e4adSPedro F. Giffuni if (slen > dlen) 2089824e4adSPedro F. Giffuni len = dlen; 2099824e4adSPedro F. Giffuni else 2109824e4adSPedro F. Giffuni len = slen; 2119824e4adSPedro F. Giffuni 2129824e4adSPedro F. Giffuni buf_val = padding; 2139824e4adSPedro F. Giffuni 2149824e4adSPedro F. Giffuni for (i = 0; i < len; i++) { 2159824e4adSPedro F. Giffuni if (unsigned_char) 2169824e4adSPedro F. Giffuni buf_byte = (u_int)ubuf[i]; 2179824e4adSPedro F. Giffuni else 2189824e4adSPedro F. Giffuni buf_byte = (int)sbuf[i]; 2199824e4adSPedro F. Giffuni 2209824e4adSPedro F. Giffuni if ((i % 4) == 0) 2219824e4adSPedro F. Giffuni buf_val = padding; 2229824e4adSPedro F. Giffuni 2239824e4adSPedro F. Giffuni buf_val <<= 8; 2249824e4adSPedro F. Giffuni buf_val += buf_byte; 2259824e4adSPedro F. Giffuni 2269824e4adSPedro F. Giffuni if ((i % 4) == 3) { 2279824e4adSPedro F. Giffuni *dst++ = buf_val; 2289824e4adSPedro F. Giffuni dlen -= sizeof(uint32_t); 2299824e4adSPedro F. Giffuni buf_val = padding; 2309824e4adSPedro F. Giffuni } 2319824e4adSPedro F. Giffuni } 2329824e4adSPedro F. Giffuni 2339824e4adSPedro F. Giffuni dlen -= sizeof(uint32_t); 2349824e4adSPedro F. Giffuni if (dlen >= 0) 2359824e4adSPedro F. Giffuni *dst++ = buf_val; 2369824e4adSPedro F. Giffuni 2379824e4adSPedro F. Giffuni dlen -= sizeof(uint32_t); 2389824e4adSPedro F. Giffuni while (dlen >= 0) { 2399824e4adSPedro F. Giffuni *dst++ = padding; 2409824e4adSPedro F. Giffuni dlen -= sizeof(uint32_t); 2419824e4adSPedro F. Giffuni } 2429824e4adSPedro F. Giffuni } 2439824e4adSPedro F. Giffuni 2449824e4adSPedro F. Giffuni int 2459824e4adSPedro F. Giffuni ext2_htree_hash(const char *name, int len, 2469824e4adSPedro F. Giffuni uint32_t *hash_seed, int hash_version, 2479824e4adSPedro F. Giffuni uint32_t *hash_major, uint32_t *hash_minor) 2489824e4adSPedro F. Giffuni { 2499824e4adSPedro F. Giffuni uint32_t hash[4]; 2509824e4adSPedro F. Giffuni uint32_t data[8]; 2519824e4adSPedro F. Giffuni uint32_t major = 0, minor = 0; 2529824e4adSPedro F. Giffuni int unsigned_char = 0; 2539824e4adSPedro F. Giffuni 2549824e4adSPedro F. Giffuni if (!name || !hash_major) 2559824e4adSPedro F. Giffuni return (-1); 2569824e4adSPedro F. Giffuni 2579824e4adSPedro F. Giffuni if (len < 1 || len > 255) 2589824e4adSPedro F. Giffuni goto error; 2599824e4adSPedro F. Giffuni 2609824e4adSPedro F. Giffuni hash[0] = 0x67452301; 2619824e4adSPedro F. Giffuni hash[1] = 0xEFCDAB89; 2629824e4adSPedro F. Giffuni hash[2] = 0x98BADCFE; 2639824e4adSPedro F. Giffuni hash[3] = 0x10325476; 2649824e4adSPedro F. Giffuni 2659824e4adSPedro F. Giffuni if (hash_seed) 2669824e4adSPedro F. Giffuni memcpy(hash, hash_seed, sizeof(hash)); 2679824e4adSPedro F. Giffuni 2689824e4adSPedro F. Giffuni switch (hash_version) { 2699824e4adSPedro F. Giffuni case EXT2_HTREE_TEA_UNSIGNED: 2709824e4adSPedro F. Giffuni unsigned_char = 1; 2719824e4adSPedro F. Giffuni /* FALLTHROUGH */ 2729824e4adSPedro F. Giffuni case EXT2_HTREE_TEA: 2739824e4adSPedro F. Giffuni while (len > 0) { 2749824e4adSPedro F. Giffuni ext2_prep_hashbuf(name, len, data, 16, unsigned_char); 2759824e4adSPedro F. Giffuni ext2_tea(hash, data); 2769824e4adSPedro F. Giffuni len -= 16; 2779824e4adSPedro F. Giffuni name += 16; 2789824e4adSPedro F. Giffuni } 2799824e4adSPedro F. Giffuni major = hash[0]; 2809824e4adSPedro F. Giffuni minor = hash[1]; 2819824e4adSPedro F. Giffuni break; 2829824e4adSPedro F. Giffuni case EXT2_HTREE_LEGACY_UNSIGNED: 2839824e4adSPedro F. Giffuni unsigned_char = 1; 2849824e4adSPedro F. Giffuni /* FALLTHROUGH */ 2859824e4adSPedro F. Giffuni case EXT2_HTREE_LEGACY: 2869824e4adSPedro F. Giffuni major = ext2_legacy_hash(name, len, unsigned_char); 2879824e4adSPedro F. Giffuni break; 2889824e4adSPedro F. Giffuni case EXT2_HTREE_HALF_MD4_UNSIGNED: 2899824e4adSPedro F. Giffuni unsigned_char = 1; 2909824e4adSPedro F. Giffuni /* FALLTHROUGH */ 2919824e4adSPedro F. Giffuni case EXT2_HTREE_HALF_MD4: 2929824e4adSPedro F. Giffuni while (len > 0) { 2939824e4adSPedro F. Giffuni ext2_prep_hashbuf(name, len, data, 32, unsigned_char); 2949824e4adSPedro F. Giffuni ext2_half_md4(hash, data); 2959824e4adSPedro F. Giffuni len -= 32; 2969824e4adSPedro F. Giffuni name += 32; 2979824e4adSPedro F. Giffuni } 2989824e4adSPedro F. Giffuni major = hash[1]; 2999824e4adSPedro F. Giffuni minor = hash[2]; 3009824e4adSPedro F. Giffuni break; 3019824e4adSPedro F. Giffuni default: 3029824e4adSPedro F. Giffuni goto error; 3039824e4adSPedro F. Giffuni } 3049824e4adSPedro F. Giffuni 3059824e4adSPedro F. Giffuni major &= ~1; 3069824e4adSPedro F. Giffuni if (major == (EXT2_HTREE_EOF << 1)) 3079824e4adSPedro F. Giffuni major = (EXT2_HTREE_EOF - 1) << 1; 3089824e4adSPedro F. Giffuni *hash_major = major; 3099824e4adSPedro F. Giffuni if (hash_minor) 3109824e4adSPedro F. Giffuni *hash_minor = minor; 3119824e4adSPedro F. Giffuni 3129824e4adSPedro F. Giffuni return (0); 3139824e4adSPedro F. Giffuni 3149824e4adSPedro F. Giffuni error: 3159824e4adSPedro F. Giffuni *hash_major = 0; 3169824e4adSPedro F. Giffuni if (hash_minor) 3179824e4adSPedro F. Giffuni *hash_minor = 0; 3189824e4adSPedro F. Giffuni return (-1); 3199824e4adSPedro F. Giffuni } 320