1 /*-
2 * SPDX-License-Identifier: (BSD-2-Clause AND RSA-MD)
3 *
4 * Copyright (c) 2010, 2013 Zheng Liu <lz@freebsd.org>
5 * Copyright (c) 2012, Vyacheslav Matyushin
6 * All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27 * SUCH DAMAGE.
28 */
29
30 /*
31 * The following notice applies to the code in ext2_half_md4():
32 *
33 * Copyright (C) 1990-2, RSA Data Security, Inc. All rights reserved.
34 *
35 * License to copy and use this software is granted provided that it
36 * is identified as the "RSA Data Security, Inc. MD4 Message-Digest
37 * Algorithm" in all material mentioning or referencing this software
38 * or this function.
39 *
40 * License is also granted to make and use derivative works provided
41 * that such works are identified as "derived from the RSA Data
42 * Security, Inc. MD4 Message-Digest Algorithm" in all material
43 * mentioning or referencing the derived work.
44 *
45 * RSA Data Security, Inc. makes no representations concerning either
46 * the merchantability of this software or the suitability of this
47 * software for any particular purpose. It is provided "as is"
48 * without express or implied warranty of any kind.
49 *
50 * These notices must be retained in any copies of any part of this
51 * documentation and/or software.
52 */
53
54 #include <sys/param.h>
55 #include <sys/systm.h>
56 #include <sys/conf.h>
57 #include <sys/vnode.h>
58 #include <sys/sdt.h>
59 #include <sys/stat.h>
60 #include <sys/mount.h>
61
62 #include <fs/ext2fs/ext2fs.h>
63 #include <fs/ext2fs/fs.h>
64 #include <fs/ext2fs/htree.h>
65 #include <fs/ext2fs/inode.h>
66 #include <fs/ext2fs/ext2_mount.h>
67 #include <fs/ext2fs/ext2_extern.h>
68
69 SDT_PROVIDER_DECLARE(ext2fs);
70 /*
71 * ext2fs trace probe:
72 * arg0: verbosity. Higher numbers give more verbose messages
73 * arg1: Textual message
74 */
75 SDT_PROBE_DEFINE2(ext2fs, , trace, hash, "int", "char*");
76
77 /* F, G, and H are MD4 functions */
78 #define F(x, y, z) (((x) & (y)) | ((~x) & (z)))
79 #define G(x, y, z) (((x) & (y)) | ((x) & (z)) | ((y) & (z)))
80 #define H(x, y, z) ((x) ^ (y) ^ (z))
81
82 /* ROTATE_LEFT rotates x left n bits */
83 #define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32 - (n))))
84
85 /*
86 * FF, GG, and HH are transformations for rounds 1, 2, and 3.
87 * Rotation is separated from addition to prevent recomputation.
88 */
89 #define FF(a, b, c, d, x, s) { \
90 (a) += F ((b), (c), (d)) + (x); \
91 (a) = ROTATE_LEFT ((a), (s)); \
92 }
93
94 #define GG(a, b, c, d, x, s) { \
95 (a) += G ((b), (c), (d)) + (x) + (uint32_t)0x5A827999; \
96 (a) = ROTATE_LEFT ((a), (s)); \
97 }
98
99 #define HH(a, b, c, d, x, s) { \
100 (a) += H ((b), (c), (d)) + (x) + (uint32_t)0x6ED9EBA1; \
101 (a) = ROTATE_LEFT ((a), (s)); \
102 }
103
104 /*
105 * MD4 basic transformation. It transforms state based on block.
106 *
107 * This is a half md4 algorithm since Linux uses this algorithm for dir
108 * index. This function is derived from the RSA Data Security, Inc. MD4
109 * Message-Digest Algorithm and was modified as necessary.
110 *
111 * The return value of this function is uint32_t in Linux, but actually we don't
112 * need to check this value, so in our version this function doesn't return any
113 * value.
114 */
115 static void
ext2_half_md4(uint32_t hash[4],uint32_t data[8])116 ext2_half_md4(uint32_t hash[4], uint32_t data[8])
117 {
118 uint32_t a = hash[0], b = hash[1], c = hash[2], d = hash[3];
119
120 /* Round 1 */
121 FF(a, b, c, d, data[0], 3);
122 FF(d, a, b, c, data[1], 7);
123 FF(c, d, a, b, data[2], 11);
124 FF(b, c, d, a, data[3], 19);
125 FF(a, b, c, d, data[4], 3);
126 FF(d, a, b, c, data[5], 7);
127 FF(c, d, a, b, data[6], 11);
128 FF(b, c, d, a, data[7], 19);
129
130 /* Round 2 */
131 GG(a, b, c, d, data[1], 3);
132 GG(d, a, b, c, data[3], 5);
133 GG(c, d, a, b, data[5], 9);
134 GG(b, c, d, a, data[7], 13);
135 GG(a, b, c, d, data[0], 3);
136 GG(d, a, b, c, data[2], 5);
137 GG(c, d, a, b, data[4], 9);
138 GG(b, c, d, a, data[6], 13);
139
140 /* Round 3 */
141 HH(a, b, c, d, data[3], 3);
142 HH(d, a, b, c, data[7], 9);
143 HH(c, d, a, b, data[2], 11);
144 HH(b, c, d, a, data[6], 15);
145 HH(a, b, c, d, data[1], 3);
146 HH(d, a, b, c, data[5], 9);
147 HH(c, d, a, b, data[0], 11);
148 HH(b, c, d, a, data[4], 15);
149
150 hash[0] += a;
151 hash[1] += b;
152 hash[2] += c;
153 hash[3] += d;
154 }
155
156 /*
157 * Tiny Encryption Algorithm.
158 */
159 static void
ext2_tea(uint32_t hash[4],uint32_t data[8])160 ext2_tea(uint32_t hash[4], uint32_t data[8])
161 {
162 uint32_t tea_delta = 0x9E3779B9;
163 uint32_t sum;
164 uint32_t x = hash[0], y = hash[1];
165 int n = 16;
166 int i = 1;
167
168 while (n-- > 0) {
169 sum = i * tea_delta;
170 x += ((y << 4) + data[0]) ^ (y + sum) ^ ((y >> 5) + data[1]);
171 y += ((x << 4) + data[2]) ^ (x + sum) ^ ((x >> 5) + data[3]);
172 i++;
173 }
174
175 hash[0] += x;
176 hash[1] += y;
177 }
178
179 static uint32_t
ext2_legacy_hash(const char * name,int len,int unsigned_char)180 ext2_legacy_hash(const char *name, int len, int unsigned_char)
181 {
182 uint32_t h0, h1 = 0x12A3FE2D, h2 = 0x37ABE8F9;
183 uint32_t multi = 0x6D22F5;
184 const unsigned char *uname = (const unsigned char *)name;
185 const signed char *sname = (const signed char *)name;
186 int val, i;
187
188 for (i = 0; i < len; i++) {
189 if (unsigned_char)
190 val = (u_int)*uname++;
191 else
192 val = (int)*sname++;
193
194 h0 = h2 + (h1 ^ (val * multi));
195 if (h0 & 0x80000000)
196 h0 -= 0x7FFFFFFF;
197 h2 = h1;
198 h1 = h0;
199 }
200
201 return (h1 << 1);
202 }
203
204 static void
ext2_prep_hashbuf(const char * src,int slen,uint32_t * dst,int dlen,int unsigned_char)205 ext2_prep_hashbuf(const char *src, int slen, uint32_t *dst, int dlen,
206 int unsigned_char)
207 {
208 uint32_t padding = slen | (slen << 8) | (slen << 16) | (slen << 24);
209 uint32_t buf_val;
210 const unsigned char *ubuf = (const unsigned char *)src;
211 const signed char *sbuf = (const signed char *)src;
212 int len, i;
213 int buf_byte;
214
215 if (slen > dlen)
216 len = dlen;
217 else
218 len = slen;
219
220 buf_val = padding;
221
222 for (i = 0; i < len; i++) {
223 if (unsigned_char)
224 buf_byte = (u_int)ubuf[i];
225 else
226 buf_byte = (int)sbuf[i];
227
228 if ((i % 4) == 0)
229 buf_val = padding;
230
231 buf_val <<= 8;
232 buf_val += buf_byte;
233
234 if ((i % 4) == 3) {
235 *dst++ = buf_val;
236 dlen -= sizeof(uint32_t);
237 buf_val = padding;
238 }
239 }
240
241 dlen -= sizeof(uint32_t);
242 if (dlen >= 0)
243 *dst++ = buf_val;
244
245 dlen -= sizeof(uint32_t);
246 while (dlen >= 0) {
247 *dst++ = padding;
248 dlen -= sizeof(uint32_t);
249 }
250 }
251
252 int
ext2_htree_hash(const char * name,int len,uint32_t * hash_seed,int hash_version,uint32_t * hash_major,uint32_t * hash_minor)253 ext2_htree_hash(const char *name, int len,
254 uint32_t *hash_seed, int hash_version,
255 uint32_t *hash_major, uint32_t *hash_minor)
256 {
257 uint32_t hash[4];
258 uint32_t data[8];
259 uint32_t major = 0, minor = 0;
260 int unsigned_char = 0;
261
262 if (!name || !hash_major)
263 return (-1);
264
265 if (len < 1 || len > 255)
266 goto error;
267
268 hash[0] = 0x67452301;
269 hash[1] = 0xEFCDAB89;
270 hash[2] = 0x98BADCFE;
271 hash[3] = 0x10325476;
272
273 if (hash_seed)
274 memcpy(hash, hash_seed, sizeof(hash));
275
276 switch (hash_version) {
277 case EXT2_HTREE_TEA_UNSIGNED:
278 unsigned_char = 1;
279 /* FALLTHROUGH */
280 case EXT2_HTREE_TEA:
281 while (len > 0) {
282 ext2_prep_hashbuf(name, len, data, 16, unsigned_char);
283 ext2_tea(hash, data);
284 len -= 16;
285 name += 16;
286 }
287 major = hash[0];
288 minor = hash[1];
289 break;
290 case EXT2_HTREE_LEGACY_UNSIGNED:
291 unsigned_char = 1;
292 /* FALLTHROUGH */
293 case EXT2_HTREE_LEGACY:
294 major = ext2_legacy_hash(name, len, unsigned_char);
295 break;
296 case EXT2_HTREE_HALF_MD4_UNSIGNED:
297 unsigned_char = 1;
298 /* FALLTHROUGH */
299 case EXT2_HTREE_HALF_MD4:
300 while (len > 0) {
301 ext2_prep_hashbuf(name, len, data, 32, unsigned_char);
302 ext2_half_md4(hash, data);
303 len -= 32;
304 name += 32;
305 }
306 major = hash[1];
307 minor = hash[2];
308 break;
309 default:
310 SDT_PROBE2(ext2fs, , trace, hash, 1, "unexpected hash version");
311 goto error;
312 }
313
314 major &= ~1;
315 if (major == (EXT2_HTREE_EOF << 1))
316 major = (EXT2_HTREE_EOF - 1) << 1;
317 *hash_major = major;
318 if (hash_minor)
319 *hash_minor = minor;
320
321 return (0);
322
323 error:
324 *hash_major = 0;
325 if (hash_minor)
326 *hash_minor = 0;
327 return (-1);
328 }
329