1 /* $NetBSD: ext2fs_hash.c,v 1.2 2016/08/13 07:40:10 christos Exp $ */
2
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 * $FreeBSD: head/sys/fs/ext2fs/ext2_hash.c 294504 2016-01-21 14:50:28Z pfg $
30 */
31
32 /*
33 * The following notice applies to the code in ext2_half_md4():
34 *
35 * Copyright (C) 1990-2, RSA Data Security, Inc. All rights reserved.
36 *
37 * License to copy and use this software is granted provided that it
38 * is identified as the "RSA Data Security, Inc. MD4 Message-Digest
39 * Algorithm" in all material mentioning or referencing this software
40 * or this function.
41 *
42 * License is also granted to make and use derivative works provided
43 * that such works are identified as "derived from the RSA Data
44 * Security, Inc. MD4 Message-Digest Algorithm" in all material
45 * mentioning or referencing the derived work.
46 *
47 * RSA Data Security, Inc. makes no representations concerning either
48 * the merchantability of this software or the suitability of this
49 * software for any particular purpose. It is provided "as is"
50 * without express or implied warranty of any kind.
51 *
52 * These notices must be retained in any copies of any part of this
53 * documentation and/or software.
54 */
55
56 #include <sys/cdefs.h>
57 __KERNEL_RCSID(0, "$NetBSD: ext2fs_hash.c,v 1.2 2016/08/13 07:40:10 christos Exp $");
58
59 #include <sys/param.h>
60 #include <sys/systm.h>
61 #include <sys/conf.h>
62 #include <sys/vnode.h>
63 #include <sys/stat.h>
64 #include <sys/mount.h>
65
66 #include <ufs/ext2fs/ext2fs_htree.h>
67 #include <ufs/ext2fs/ext2fs_hash.h>
68 #include <ufs/ufs/inode.h>
69 #include <ufs/ufs/ufsmount.h>
70 #include <ufs/ext2fs/ext2fs_extern.h>
71
72 /*
73 * FF, GG, and HH are transformations for rounds 1, 2, and 3.
74 * Rotation is separated from addition to prevent recomputation.
75 */
76 #define FF(a, b, c, d, x, s) { \
77 (a) += F ((b), (c), (d)) + (x); \
78 (a) = ROTATE_LEFT ((a), (s)); \
79 }
80
81 #define GG(a, b, c, d, x, s) { \
82 (a) += G ((b), (c), (d)) + (x) + (uint32_t)0x5A827999; \
83 (a) = ROTATE_LEFT ((a), (s)); \
84 }
85
86 #define HH(a, b, c, d, x, s) { \
87 (a) += H ((b), (c), (d)) + (x) + (uint32_t)0x6ED9EBA1; \
88 (a) = ROTATE_LEFT ((a), (s)); \
89 }
90
91 static void
ext2fs_prep_hashbuf(const char * src,int slen,uint32_t * dst,int dlen,int unsigned_char)92 ext2fs_prep_hashbuf(const char *src, int slen, uint32_t *dst, int dlen,
93 int unsigned_char)
94 {
95 uint32_t padding = slen | (slen << 8) | (slen << 16) | (slen << 24);
96 uint32_t buf_val;
97 const unsigned char *ubuf = (const unsigned char *)src;
98 const signed char *sbuf = (const signed char *)src;
99 int len, i;
100 int buf_byte;
101
102 if (slen > dlen)
103 len = dlen;
104 else
105 len = slen;
106
107 buf_val = padding;
108
109 for (i = 0; i < len; i++) {
110 if (unsigned_char)
111 buf_byte = (u_int)ubuf[i];
112 else
113 buf_byte = (int)sbuf[i];
114
115 if ((i % 4) == 0)
116 buf_val = padding;
117
118 buf_val <<= 8;
119 buf_val += buf_byte;
120
121 if ((i % 4) == 3) {
122 *dst++ = buf_val;
123 dlen -= sizeof(uint32_t);
124 buf_val = padding;
125 }
126 }
127
128 dlen -= sizeof(uint32_t);
129 if (dlen >= 0)
130 *dst++ = buf_val;
131
132 dlen -= sizeof(uint32_t);
133 while (dlen >= 0) {
134 *dst++ = padding;
135 dlen -= sizeof(uint32_t);
136 }
137 }
138
139 static uint32_t
ext2fs_legacy_hash(const char * name,int len,int unsigned_char)140 ext2fs_legacy_hash(const char *name, int len, int unsigned_char)
141 {
142 uint32_t h0, h1 = 0x12A3FE2D, h2 = 0x37ABE8F9;
143 uint32_t multi = 0x6D22F5;
144 const unsigned char *uname = (const unsigned char *)name;
145 const signed char *sname = (const signed char *)name;
146 int val, i;
147
148 for (i = 0; i < len; i++) {
149 if (unsigned_char)
150 val = (u_int)*uname++;
151 else
152 val = (int)*sname++;
153
154 h0 = h2 + (h1 ^ (val * multi));
155 if (h0 & 0x80000000)
156 h0 -= 0x7FFFFFFF;
157 h2 = h1;
158 h1 = h0;
159 }
160
161 return h1 << 1;
162 }
163
164 /*
165 * MD4 basic transformation. It transforms state based on block.
166 *
167 * This is a half md4 algorithm since Linux uses this algorithm for dir
168 * index. This function is derived from the RSA Data Security, Inc. MD4
169 * Message-Digest Algorithm and was modified as necessary.
170 *
171 * The return value of this function is uint32_t in Linux, but actually we don't
172 * need to check this value, so in our version this function doesn't return any
173 * value.
174 */
175 static void
ext2fs_half_md4(uint32_t hash[4],uint32_t data[8])176 ext2fs_half_md4(uint32_t hash[4], uint32_t data[8])
177 {
178 uint32_t a = hash[0], b = hash[1], c = hash[2], d = hash[3];
179
180 /* Round 1 */
181 FF(a, b, c, d, data[0], 3);
182 FF(d, a, b, c, data[1], 7);
183 FF(c, d, a, b, data[2], 11);
184 FF(b, c, d, a, data[3], 19);
185 FF(a, b, c, d, data[4], 3);
186 FF(d, a, b, c, data[5], 7);
187 FF(c, d, a, b, data[6], 11);
188 FF(b, c, d, a, data[7], 19);
189
190 /* Round 2 */
191 GG(a, b, c, d, data[1], 3);
192 GG(d, a, b, c, data[3], 5);
193 GG(c, d, a, b, data[5], 9);
194 GG(b, c, d, a, data[7], 13);
195 GG(a, b, c, d, data[0], 3);
196 GG(d, a, b, c, data[2], 5);
197 GG(c, d, a, b, data[4], 9);
198 GG(b, c, d, a, data[6], 13);
199
200 /* Round 3 */
201 HH(a, b, c, d, data[3], 3);
202 HH(d, a, b, c, data[7], 9);
203 HH(c, d, a, b, data[2], 11);
204 HH(b, c, d, a, data[6], 15);
205 HH(a, b, c, d, data[1], 3);
206 HH(d, a, b, c, data[5], 9);
207 HH(c, d, a, b, data[0], 11);
208 HH(b, c, d, a, data[4], 15);
209
210 hash[0] += a;
211 hash[1] += b;
212 hash[2] += c;
213 hash[3] += d;
214 }
215
216 /*
217 * Tiny Encryption Algorithm.
218 */
219 static void
ext2fs_tea(uint32_t hash[4],uint32_t data[8])220 ext2fs_tea(uint32_t hash[4], uint32_t data[8])
221 {
222 uint32_t tea_delta = 0x9E3779B9;
223 uint32_t sum;
224 uint32_t x = hash[0], y = hash[1];
225 int n = 16;
226 int i = 1;
227
228 while (n-- > 0) {
229 sum = i * tea_delta;
230 x += ((y << 4) + data[0]) ^ (y + sum) ^ ((y >> 5) + data[1]);
231 y += ((x << 4) + data[2]) ^ (x + sum) ^ ((x >> 5) + data[3]);
232 i++;
233 }
234
235 hash[0] += x;
236 hash[1] += y;
237 }
238
239 int
ext2fs_htree_hash(const char * name,int len,uint32_t * hash_seed,int hash_version,uint32_t * hash_major,uint32_t * hash_minor)240 ext2fs_htree_hash(const char *name, int len,
241 uint32_t *hash_seed, int hash_version,
242 uint32_t *hash_major, uint32_t *hash_minor)
243 {
244 uint32_t hash[4];
245 uint32_t data[8];
246 uint32_t major = 0, minor = 0;
247 int unsigned_char = 0;
248
249 if (!name || !hash_major)
250 return -1;
251
252 if (len < 1 || len > 255)
253 goto error;
254
255 hash[0] = 0x67452301;
256 hash[1] = 0xEFCDAB89;
257 hash[2] = 0x98BADCFE;
258 hash[3] = 0x10325476;
259
260 if (hash_seed)
261 memcpy(hash, hash_seed, sizeof(hash));
262
263 switch (hash_version) {
264 case EXT2_HTREE_TEA_UNSIGNED:
265 unsigned_char = 1;
266 /* FALLTHROUGH */
267 case EXT2_HTREE_TEA:
268 while (len > 0) {
269 ext2fs_prep_hashbuf(name, len, data, 16, unsigned_char);
270 ext2fs_tea(hash, data);
271 len -= 16;
272 name += 16;
273 }
274 major = hash[0];
275 minor = hash[1];
276 break;
277 case EXT2_HTREE_LEGACY_UNSIGNED:
278 unsigned_char = 1;
279 /* FALLTHROUGH */
280 case EXT2_HTREE_LEGACY:
281 major = ext2fs_legacy_hash(name, len, unsigned_char);
282 break;
283 case EXT2_HTREE_HALF_MD4_UNSIGNED:
284 unsigned_char = 1;
285 /* FALLTHROUGH */
286 case EXT2_HTREE_HALF_MD4:
287 while (len > 0) {
288 ext2fs_prep_hashbuf(name, len, data, 32, unsigned_char);
289 ext2fs_half_md4(hash, data);
290 len -= 32;
291 name += 32;
292 }
293 major = hash[1];
294 minor = hash[2];
295 break;
296 default:
297 goto error;
298 }
299
300 major &= ~1;
301 if (major == (EXT2_HTREE_EOF << 1))
302 major = (EXT2_HTREE_EOF - 1) << 1;
303 *hash_major = major;
304 if (hash_minor)
305 *hash_minor = minor;
306
307 return 0;
308
309 error:
310 *hash_major = 0;
311 if (hash_minor)
312 *hash_minor = 0;
313 return -1;
314 }
315