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