1252890Spfg/*- 2252890Spfg * Copyright (c) 2010, 2013 Zheng Liu <lz@freebsd.org> 3252890Spfg * Copyright (c) 2012, Vyacheslav Matyushin 4252890Spfg * All rights reserved. 5252890Spfg * 6252890Spfg * Redistribution and use in source and binary forms, with or without 7252890Spfg * modification, are permitted provided that the following conditions 8252890Spfg * are met: 9252890Spfg * 1. Redistributions of source code must retain the above copyright 10252890Spfg * notice, this list of conditions and the following disclaimer. 11252890Spfg * 2. Redistributions in binary form must reproduce the above copyright 12252890Spfg * notice, this list of conditions and the following disclaimer in the 13252890Spfg * documentation and/or other materials provided with the distribution. 14252890Spfg * 15252890Spfg * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 16252890Spfg * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 17252890Spfg * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 18252890Spfg * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 19252890Spfg * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 20252890Spfg * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 21252890Spfg * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 22252890Spfg * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 23252890Spfg * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 24252890Spfg * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 25252890Spfg * SUCH DAMAGE. 26252890Spfg * 27252890Spfg * $FreeBSD$ 28252890Spfg */ 29252890Spfg 30253861Spfg/* 31253861Spfg * The following notice applies to the code in ext2_half_md4(): 32253861Spfg * 33253861Spfg * Copyright (C) 1990-2, RSA Data Security, Inc. All rights reserved. 34253861Spfg * 35253861Spfg * License to copy and use this software is granted provided that it 36253861Spfg * is identified as the "RSA Data Security, Inc. MD4 Message-Digest 37253861Spfg * Algorithm" in all material mentioning or referencing this software 38253861Spfg * or this function. 39253861Spfg * 40253861Spfg * License is also granted to make and use derivative works provided 41253861Spfg * that such works are identified as "derived from the RSA Data 42253861Spfg * Security, Inc. MD4 Message-Digest Algorithm" in all material 43253861Spfg * mentioning or referencing the derived work. 44253861Spfg * 45253861Spfg * RSA Data Security, Inc. makes no representations concerning either 46253861Spfg * the merchantability of this software or the suitability of this 47253861Spfg * software for any particular purpose. It is provided "as is" 48253861Spfg * without express or implied warranty of any kind. 49253861Spfg * 50253861Spfg * These notices must be retained in any copies of any part of this 51253861Spfg * documentation and/or software. 52253861Spfg */ 53253861Spfg 54252890Spfg#include <sys/param.h> 55252890Spfg#include <sys/systm.h> 56252890Spfg#include <sys/conf.h> 57252890Spfg#include <sys/vnode.h> 58252890Spfg#include <sys/stat.h> 59252890Spfg#include <sys/mount.h> 60252890Spfg 61252890Spfg#include <fs/ext2fs/htree.h> 62252890Spfg#include <fs/ext2fs/inode.h> 63252890Spfg#include <fs/ext2fs/ext2_mount.h> 64252890Spfg#include <fs/ext2fs/ext2_extern.h> 65252890Spfg 66252890Spfg/* F, G, and H are MD4 functions */ 67252890Spfg#define F(x, y, z) (((x) & (y)) | ((~x) & (z))) 68252890Spfg#define G(x, y, z) (((x) & (y)) | ((x) & (z)) | ((y) & (z))) 69252890Spfg#define H(x, y, z) ((x) ^ (y) ^ (z)) 70252890Spfg 71252890Spfg/* ROTATE_LEFT rotates x left n bits */ 72252890Spfg#define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32 - (n)))) 73252890Spfg 74252890Spfg/* 75252890Spfg * FF, GG, and HH are transformations for rounds 1, 2, and 3. 76254104Spfg * Rotation is separated from addition to prevent recomputation. 77252890Spfg */ 78252890Spfg#define FF(a, b, c, d, x, s) { \ 79252890Spfg (a) += F ((b), (c), (d)) + (x); \ 80252890Spfg (a) = ROTATE_LEFT ((a), (s)); \ 81252890Spfg} 82252890Spfg 83252890Spfg#define GG(a, b, c, d, x, s) { \ 84252890Spfg (a) += G ((b), (c), (d)) + (x) + (uint32_t)0x5A827999; \ 85252890Spfg (a) = ROTATE_LEFT ((a), (s)); \ 86252890Spfg} 87252890Spfg 88252890Spfg#define HH(a, b, c, d, x, s) { \ 89252890Spfg (a) += H ((b), (c), (d)) + (x) + (uint32_t)0x6ED9EBA1; \ 90252890Spfg (a) = ROTATE_LEFT ((a), (s)); \ 91252890Spfg} 92252890Spfg 93252890Spfg/* 94252890Spfg * MD4 basic transformation. It transforms state based on block. 95252890Spfg * 96253861Spfg * This is a half md4 algorithm since Linux uses this algorithm for dir 97253861Spfg * index. This function is derived from the RSA Data Security, Inc. MD4 98253861Spfg * Message-Digest Algorithm and was modified as necessary. 99252890Spfg * 100252890Spfg * The return value of this function is uint32_t in Linux, but actually we don't 101253861Spfg * need to check this value, so in our version this function doesn't return any 102253861Spfg * value. 103252890Spfg */ 104252890Spfgstatic void 105252890Spfgext2_half_md4(uint32_t hash[4], uint32_t data[8]) 106252890Spfg{ 107252890Spfg uint32_t a = hash[0], b = hash[1], c = hash[2], d = hash[3]; 108252890Spfg 109252890Spfg /* Round 1 */ 110252890Spfg FF(a, b, c, d, data[0], 3); 111252890Spfg FF(d, a, b, c, data[1], 7); 112252890Spfg FF(c, d, a, b, data[2], 11); 113252890Spfg FF(b, c, d, a, data[3], 19); 114252890Spfg FF(a, b, c, d, data[4], 3); 115252890Spfg FF(d, a, b, c, data[5], 7); 116252890Spfg FF(c, d, a, b, data[6], 11); 117252890Spfg FF(b, c, d, a, data[7], 19); 118252890Spfg 119252890Spfg /* Round 2 */ 120252890Spfg GG(a, b, c, d, data[1], 3); 121252890Spfg GG(d, a, b, c, data[3], 5); 122252890Spfg GG(c, d, a, b, data[5], 9); 123252890Spfg GG(b, c, d, a, data[7], 13); 124252890Spfg GG(a, b, c, d, data[0], 3); 125252890Spfg GG(d, a, b, c, data[2], 5); 126252890Spfg GG(c, d, a, b, data[4], 9); 127252890Spfg GG(b, c, d, a, data[6], 13); 128252890Spfg 129252890Spfg /* Round 3 */ 130252890Spfg HH(a, b, c, d, data[3], 3); 131252890Spfg HH(d, a, b, c, data[7], 9); 132252890Spfg HH(c, d, a, b, data[2], 11); 133252890Spfg HH(b, c, d, a, data[6], 15); 134252890Spfg HH(a, b, c, d, data[1], 3); 135252890Spfg HH(d, a, b, c, data[5], 9); 136252890Spfg HH(c, d, a, b, data[0], 11); 137252890Spfg HH(b, c, d, a, data[4], 15); 138252890Spfg 139252890Spfg hash[0] += a; 140252890Spfg hash[1] += b; 141252890Spfg hash[2] += c; 142252890Spfg hash[3] += d; 143252890Spfg} 144252890Spfg 145252890Spfg/* 146252890Spfg * Tiny Encryption Algorithm. 147252890Spfg */ 148252890Spfgstatic void 149252890Spfgext2_tea(uint32_t hash[4], uint32_t data[8]) 150252890Spfg{ 151252890Spfg uint32_t tea_delta = 0x9E3779B9; 152252890Spfg uint32_t sum; 153252890Spfg uint32_t x = hash[0], y = hash[1]; 154252890Spfg int n = 16; 155252890Spfg int i = 1; 156252890Spfg 157252890Spfg while (n-- > 0) { 158252890Spfg sum = i * tea_delta; 159252890Spfg x += ((y << 4) + data[0]) ^ (y + sum) ^ ((y >> 5) + data[1]); 160252890Spfg y += ((x << 4) + data[2]) ^ (x + sum) ^ ((x >> 5) + data[3]); 161252890Spfg i++; 162252890Spfg } 163252890Spfg 164252890Spfg hash[0] += x; 165252890Spfg hash[1] += y; 166252890Spfg} 167252890Spfg 168252890Spfgstatic uint32_t 169252890Spfgext2_legacy_hash(const char *name, int len, int unsigned_char) 170252890Spfg{ 171252890Spfg uint32_t h0, h1 = 0x12A3FE2D, h2 = 0x37ABE8F9; 172252890Spfg uint32_t multi = 0x6D22F5; 173252890Spfg const unsigned char *uname = (const unsigned char *)name; 174252890Spfg const signed char *sname = (const signed char *)name; 175252890Spfg int val, i; 176252890Spfg 177252890Spfg for (i = 0; i < len; i++) { 178252890Spfg if (unsigned_char) 179252890Spfg val = (u_int)*uname++; 180252890Spfg else 181252890Spfg val = (int)*sname++; 182252890Spfg 183252890Spfg h0 = h2 + (h1 ^ (val * multi)); 184252890Spfg if (h0 & 0x80000000) 185252890Spfg h0 -= 0x7FFFFFFF; 186252890Spfg h2 = h1; 187252890Spfg h1 = h0; 188252890Spfg } 189252890Spfg 190252890Spfg return (h1 << 1); 191252890Spfg} 192252890Spfg 193252890Spfgstatic void 194252890Spfgext2_prep_hashbuf(const char *src, int slen, uint32_t *dst, int dlen, 195252890Spfg int unsigned_char) 196252890Spfg{ 197252890Spfg uint32_t padding = slen | (slen << 8) | (slen << 16) | (slen << 24); 198252890Spfg uint32_t buf_val; 199252890Spfg int len, i; 200252890Spfg int buf_byte; 201252890Spfg const unsigned char *ubuf = (const unsigned char *)src; 202252890Spfg const signed char *sbuf = (const signed char *)src; 203252890Spfg 204252890Spfg if (slen > dlen) 205252890Spfg len = dlen; 206252890Spfg else 207252890Spfg len = slen; 208252890Spfg 209252890Spfg buf_val = padding; 210252890Spfg 211252890Spfg for (i = 0; i < len; i++) { 212252890Spfg if (unsigned_char) 213252890Spfg buf_byte = (u_int)ubuf[i]; 214252890Spfg else 215252890Spfg buf_byte = (int)sbuf[i]; 216252890Spfg 217252890Spfg if ((i % 4) == 0) 218252890Spfg buf_val = padding; 219252890Spfg 220252890Spfg buf_val <<= 8; 221252890Spfg buf_val += buf_byte; 222252890Spfg 223252890Spfg if ((i % 4) == 3) { 224252890Spfg *dst++ = buf_val; 225252890Spfg dlen -= sizeof(uint32_t); 226252890Spfg buf_val = padding; 227252890Spfg } 228252890Spfg } 229252890Spfg 230252890Spfg dlen -= sizeof(uint32_t); 231252890Spfg if (dlen >= 0) 232252890Spfg *dst++ = buf_val; 233252890Spfg 234252890Spfg dlen -= sizeof(uint32_t); 235252890Spfg while (dlen >= 0) { 236252890Spfg *dst++ = padding; 237252890Spfg dlen -= sizeof(uint32_t); 238252890Spfg } 239252890Spfg} 240252890Spfg 241252890Spfgint 242252890Spfgext2_htree_hash(const char *name, int len, 243252890Spfg uint32_t *hash_seed, int hash_version, 244252890Spfg uint32_t *hash_major, uint32_t *hash_minor) 245252890Spfg{ 246252890Spfg uint32_t hash[4]; 247252890Spfg uint32_t data[8]; 248252890Spfg uint32_t major = 0, minor = 0; 249252890Spfg int unsigned_char = 0; 250252890Spfg 251252890Spfg if (!name || !hash_major) 252252890Spfg return (-1); 253252890Spfg 254252890Spfg if (len < 1 || len > 255) 255252890Spfg goto error; 256252890Spfg 257252890Spfg hash[0] = 0x67452301; 258252890Spfg hash[1] = 0xEFCDAB89; 259252890Spfg hash[2] = 0x98BADCFE; 260252890Spfg hash[3] = 0x10325476; 261252890Spfg 262252890Spfg if (hash_seed) 263252890Spfg memcpy(hash, hash_seed, sizeof(hash)); 264252890Spfg 265252890Spfg switch (hash_version) { 266252890Spfg case EXT2_HTREE_TEA_UNSIGNED: 267252890Spfg unsigned_char = 1; 268252890Spfg case EXT2_HTREE_TEA: 269252890Spfg while (len > 0) { 270252890Spfg ext2_prep_hashbuf(name, len, data, 16, unsigned_char); 271252890Spfg ext2_tea(hash, data); 272252890Spfg len -= 16; 273252890Spfg name += 16; 274252890Spfg } 275252890Spfg major = hash[0]; 276252890Spfg minor = hash[1]; 277252890Spfg break; 278252890Spfg case EXT2_HTREE_LEGACY_UNSIGNED: 279252890Spfg unsigned_char = 1; 280252890Spfg case EXT2_HTREE_LEGACY: 281252890Spfg major = ext2_legacy_hash(name, len, unsigned_char); 282252890Spfg break; 283252890Spfg case EXT2_HTREE_HALF_MD4_UNSIGNED: 284252890Spfg unsigned_char = 1; 285252890Spfg case EXT2_HTREE_HALF_MD4: 286252890Spfg while (len > 0) { 287252890Spfg ext2_prep_hashbuf(name, len, data, 32, unsigned_char); 288252890Spfg ext2_half_md4(hash, data); 289252890Spfg len -= 32; 290252890Spfg name += 32; 291252890Spfg } 292259904Spfg major = hash[1]; 293259904Spfg minor = hash[2]; 294252890Spfg break; 295252890Spfg default: 296252890Spfg goto error; 297252890Spfg } 298252890Spfg 299252890Spfg major &= ~1; 300252890Spfg if (major == (EXT2_HTREE_EOF << 1)) 301252890Spfg major = (EXT2_HTREE_EOF - 1) << 1; 302252890Spfg *hash_major = major; 303252890Spfg if (hash_minor) 304252890Spfg *hash_minor = minor; 305252890Spfg 306252890Spfg return (0); 307252890Spfg 308252890Spfgerror: 309252890Spfg *hash_major = 0; 310252890Spfg if (hash_minor) 311252890Spfg *hash_minor = 0; 312252890Spfg return (-1); 313252890Spfg} 314