projects/linux·blob master · refs

347 lines · 7.7 KiB

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
17static 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 */
54static __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 */
104static __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
120static __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
136static 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
169static 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 */
215static 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
314int 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 }
340opaque_seq:
341#endif
342 return __ext4fs_dirhash(dir, name, len, hinfo);
343}
344
345#if IS_ENABLED(CONFIG_EXT4_KUNIT_TESTS)
346EXPORT_SYMBOL_FOR_EXT4_TEST(ext4fs_dirhash);
347#endif