1 // SPDX-License-Identifier: GPL-2.0 2 /* 3 * linux/fs/ext4/hash.c 4 * 5 * Copyright (C) 2002 by Theodore Ts'o 6 */ 7 8 #include <linux/fs.h> 9 #include <linux/unicode.h> 10 #include <linux/compiler.h> 11 #include <linux/bitops.h> 12 #include <linux/unaligned.h> 13 #include "ext4.h" 14 15 #define DELTA 0x9E3779B9 16 17 static void TEA_transform(__u32 buf[4], __u32 const in[]) 18 { 19 __u32 sum = 0; 20 __u32 b0 = buf[0], b1 = buf[1]; 21 __u32 a = in[0], b = in[1], c = in[2], d = in[3]; 22 int n = 16; 23 24 do { 25 sum += DELTA; 26 b0 += ((b1 << 4)+a) ^ (b1+sum) ^ ((b1 >> 5)+b); 27 b1 += ((b0 << 4)+c) ^ (b0+sum) ^ ((b0 >> 5)+d); 28 } while (--n); 29 30 buf[0] += b0; 31 buf[1] += b1; 32 } 33 34 /* F, G and H are basic MD4 functions: selection, majority, parity */ 35 #define F(x, y, z) ((z) ^ ((x) & ((y) ^ (z)))) 36 #define G(x, y, z) (((x) & (y)) + (((x) ^ (y)) & (z))) 37 #define H(x, y, z) ((x) ^ (y) ^ (z)) 38 39 /* 40 * The generic round function. The application is so specific that 41 * we don't bother protecting all the arguments with parens, as is generally 42 * good macro practice, in favor of extra legibility. 43 * Rotation is separate from addition to prevent recomputation 44 */ 45 #define ROUND(f, a, b, c, d, x, s) \ 46 (a += f(b, c, d) + x, a = rol32(a, s)) 47 #define K1 0 48 #define K2 013240474631UL 49 #define K3 015666365641UL 50 51 /* 52 * Basic cut-down MD4 transform. Returns only 32 bits of result. 53 */ 54 static __u32 half_md4_transform(__u32 buf[4], __u32 const in[8]) 55 { 56 __u32 a = buf[0], b = buf[1], c = buf[2], d = buf[3]; 57 58 /* Round 1 */ 59 ROUND(F, a, b, c, d, in[0] + K1, 3); 60 ROUND(F, d, a, b, c, in[1] + K1, 7); 61 ROUND(F, c, d, a, b, in[2] + K1, 11); 62 ROUND(F, b, c, d, a, in[3] + K1, 19); 63 ROUND(F, a, b, c, d, in[4] + K1, 3); 64 ROUND(F, d, a, b, c, in[5] + K1, 7); 65 ROUND(F, c, d, a, b, in[6] + K1, 11); 66 ROUND(F, b, c, d, a, in[7] + K1, 19); 67 68 /* Round 2 */ 69 ROUND(G, a, b, c, d, in[1] + K2, 3); 70 ROUND(G, d, a, b, c, in[3] + K2, 5); 71 ROUND(G, c, d, a, b, in[5] + K2, 9); 72 ROUND(G, b, c, d, a, in[7] + K2, 13); 73 ROUND(G, a, b, c, d, in[0] + K2, 3); 74 ROUND(G, d, a, b, c, in[2] + K2, 5); 75 ROUND(G, c, d, a, b, in[4] + K2, 9); 76 ROUND(G, b, c, d, a, in[6] + K2, 13); 77 78 /* Round 3 */ 79 ROUND(H, a, b, c, d, in[3] + K3, 3); 80 ROUND(H, d, a, b, c, in[7] + K3, 9); 81 ROUND(H, c, d, a, b, in[2] + K3, 11); 82 ROUND(H, b, c, d, a, in[6] + K3, 15); 83 ROUND(H, a, b, c, d, in[1] + K3, 3); 84 ROUND(H, d, a, b, c, in[5] + K3, 9); 85 ROUND(H, c, d, a, b, in[0] + K3, 11); 86 ROUND(H, b, c, d, a, in[4] + K3, 15); 87 88 buf[0] += a; 89 buf[1] += b; 90 buf[2] += c; 91 buf[3] += d; 92 93 return buf[1]; /* "most hashed" word */ 94 } 95 #undef ROUND 96 #undef K1 97 #undef K2 98 #undef K3 99 #undef F 100 #undef G 101 #undef H 102 103 /* The old legacy hash */ 104 static __u32 dx_hack_hash_unsigned(const char *name, int len) 105 { 106 __u32 hash, hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9; 107 const unsigned char *ucp = (const unsigned char *) name; 108 109 while (len--) { 110 hash = hash1 + (hash0 ^ (((int) *ucp++) * 7152373)); 111 112 if (hash & 0x80000000) 113 hash -= 0x7fffffff; 114 hash1 = hash0; 115 hash0 = hash; 116 } 117 return hash0 << 1; 118 } 119 120 static __u32 dx_hack_hash_signed(const char *name, int len) 121 { 122 __u32 hash, hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9; 123 const signed char *scp = (const signed char *) name; 124 125 while (len--) { 126 hash = hash1 + (hash0 ^ (((int) *scp++) * 7152373)); 127 128 if (hash & 0x80000000) 129 hash -= 0x7fffffff; 130 hash1 = hash0; 131 hash0 = hash; 132 } 133 return hash0 << 1; 134 } 135 136 static void str2hashbuf_signed(const char *msg, int len, __u32 *buf, int num) 137 { 138 __u32 pad, val; 139 int i; 140 const signed char *scp = (const signed char *) msg; 141 142 pad = (__u32)len | ((__u32)len << 8); 143 pad |= pad << 16; 144 145 if (len > num*4) 146 len = num * 4; 147 148 while (len >= 4) { 149 val = ((__u32)scp[0] << 24) + ((__u32)scp[1] << 16) + ((__u32)scp[2] << 8) + scp[3]; 150 *buf++ = val; 151 scp += 4; 152 len -= 4; 153 num--; 154 } 155 156 val = pad; 157 158 for (i = 0; i < len; i++) 159 val = scp[i] + (val << 8); 160 161 if (--num >= 0) 162 *buf++ = val; 163 164 while (--num >= 0) 165 *buf++ = pad; 166 167 } 168 169 static void str2hashbuf_unsigned(const char *msg, int len, __u32 *buf, int num) 170 { 171 __u32 pad, val; 172 int i; 173 const unsigned char *ucp = (const unsigned char *) msg; 174 175 pad = (__u32)len | ((__u32)len << 8); 176 pad |= pad << 16; 177 178 if (len > num*4) 179 len = num * 4; 180 181 while (len >= 4) { 182 val = get_unaligned_be32(ucp); 183 *buf++ = val; 184 ucp += 4; 185 len -= 4; 186 num--; 187 } 188 189 val = pad; 190 191 for (i = 0; i < len; i++) 192 val = ucp[i] + (val << 8); 193 194 if (--num >= 0) 195 *buf++ = val; 196 197 while (--num >= 0) 198 *buf++ = pad; 199 200 } 201 202 /* 203 * Returns the hash of a filename. If len is 0 and name is NULL, then 204 * this function can be used to test whether or not a hash version is 205 * supported. 206 * 207 * The seed is an 4 longword (32 bits) "secret" which can be used to 208 * uniquify a hash. If the seed is all zero's, then some default seed 209 * may be used. 210 * 211 * A particular hash version specifies whether or not the seed is 212 * represented, and whether or not the returned hash is 32 bits or 64 213 * bits. 32 bit hashes will return 0 for the minor hash. 214 */ 215 static int __ext4fs_dirhash(const struct inode *dir, const char *name, int len, 216 struct dx_hash_info *hinfo) 217 { 218 __u32 hash; 219 __u32 minor_hash = 0; 220 const char *p; 221 int i; 222 __u32 in[8], buf[4]; 223 bool use_unsigned = false; 224 225 /* Initialize the default seed for the hash checksum functions */ 226 buf[0] = 0x67452301; 227 buf[1] = 0xefcdab89; 228 buf[2] = 0x98badcfe; 229 buf[3] = 0x10325476; 230 231 /* Check to see if the seed is all zero's */ 232 if (hinfo->seed) { 233 for (i = 0; i < 4; i++) { 234 if (hinfo->seed[i]) { 235 memcpy(buf, hinfo->seed, sizeof(buf)); 236 break; 237 } 238 } 239 } 240 241 switch (hinfo->hash_version) { 242 case DX_HASH_LEGACY_UNSIGNED: 243 hash = dx_hack_hash_unsigned(name, len); 244 break; 245 case DX_HASH_LEGACY: 246 hash = dx_hack_hash_signed(name, len); 247 break; 248 case DX_HASH_HALF_MD4_UNSIGNED: 249 use_unsigned = true; 250 fallthrough; 251 case DX_HASH_HALF_MD4: 252 p = name; 253 while (len > 0) { 254 if (use_unsigned) 255 str2hashbuf_unsigned(p, len, in, 8); 256 else 257 str2hashbuf_signed(p, len, in, 8); 258 half_md4_transform(buf, in); 259 len -= 32; 260 p += 32; 261 } 262 minor_hash = buf[2]; 263 hash = buf[1]; 264 break; 265 case DX_HASH_TEA_UNSIGNED: 266 use_unsigned = true; 267 fallthrough; 268 case DX_HASH_TEA: 269 p = name; 270 while (len > 0) { 271 if (use_unsigned) 272 str2hashbuf_unsigned(p, len, in, 4); 273 else 274 str2hashbuf_signed(p, len, in, 4); 275 TEA_transform(buf, in); 276 len -= 16; 277 p += 16; 278 } 279 hash = buf[0]; 280 minor_hash = buf[1]; 281 break; 282 case DX_HASH_SIPHASH: 283 { 284 struct qstr qname = QSTR_INIT(name, len); 285 __u64 combined_hash; 286 287 if (fscrypt_has_encryption_key(dir)) { 288 combined_hash = fscrypt_fname_siphash(dir, &qname); 289 } else { 290 ext4_warning_inode(dir, "Siphash requires key"); 291 return -EINVAL; 292 } 293 294 hash = (__u32)(combined_hash >> 32); 295 minor_hash = (__u32)combined_hash; 296 break; 297 } 298 default: 299 hinfo->hash = 0; 300 hinfo->minor_hash = 0; 301 ext4_warning(dir->i_sb, 302 "invalid/unsupported hash tree version %u", 303 hinfo->hash_version); 304 return -EINVAL; 305 } 306 hash = hash & ~1; 307 if (hash == (EXT4_HTREE_EOF_32BIT << 1)) 308 hash = (EXT4_HTREE_EOF_32BIT - 1) << 1; 309 hinfo->hash = hash; 310 hinfo->minor_hash = minor_hash; 311 return 0; 312 } 313 314 int ext4fs_dirhash(const struct inode *dir, const char *name, int len, 315 struct dx_hash_info *hinfo) 316 { 317 #if IS_ENABLED(CONFIG_UNICODE) 318 const struct unicode_map *um = dir->i_sb->s_encoding; 319 int r, dlen; 320 unsigned char *buff; 321 struct qstr qstr = {.name = name, .len = len }; 322 323 if (len && IS_CASEFOLDED(dir) && 324 (!IS_ENCRYPTED(dir) || fscrypt_has_encryption_key(dir))) { 325 buff = kzalloc(PATH_MAX, GFP_KERNEL); 326 if (!buff) 327 return -ENOMEM; 328 329 dlen = utf8_casefold(um, &qstr, buff, PATH_MAX); 330 if (dlen < 0) { 331 kfree(buff); 332 goto opaque_seq; 333 } 334 335 r = __ext4fs_dirhash(dir, buff, dlen, hinfo); 336 337 kfree(buff); 338 return r; 339 } 340 opaque_seq: 341 #endif 342 return __ext4fs_dirhash(dir, name, len, hinfo); 343 } 344 345 #if IS_ENABLED(CONFIG_EXT4_KUNIT_TESTS) 346 EXPORT_SYMBOL_FOR_EXT4_TEST(ext4fs_dirhash); 347 #endif 348