fs/ext4/hash.c

0001 // SPDX-License-Identifier: GPL-2.0
0002 /*
0003  *  linux/fs/ext4/hash.c
0004  *
0005  * Copyright (C) 2002 by Theodore Ts'o
0006  */
0007
0008 #include <linux/fs.h>
0009 #include <linux/unicode.h>
0010 #include <linux/compiler.h>
0011 #include <linux/bitops.h>
0012 #include "ext4.h"
0013
0014 #define DELTA 0x9E3779B9
0015
0016 static void TEA_transform(__u32 buf[4], __u32 const in[])
0017 {
0018     __u32   sum = 0;
0019     __u32   b0 = buf[0], b1 = buf[1];
0020     __u32   a = in[0], b = in[1], c = in[2], d = in[3];
0021     int n = 16;
0022
0023     do {
0024         sum += DELTA;
0025         b0 += ((b1 << 4)+a) ^ (b1+sum) ^ ((b1 >> 5)+b);
0026         b1 += ((b0 << 4)+c) ^ (b0+sum) ^ ((b0 >> 5)+d);
0027     } while (--n);
0028
0029     buf[0] += b0;
0030     buf[1] += b1;
0031 }
0032
0033 /* F, G and H are basic MD4 functions: selection, majority, parity */
0034 #define F(x, y, z) ((z) ^ ((x) & ((y) ^ (z))))
0035 #define G(x, y, z) (((x) & (y)) + (((x) ^ (y)) & (z)))
0036 #define H(x, y, z) ((x) ^ (y) ^ (z))
0037
0038 /*
0039  * The generic round function.  The application is so specific that
0040  * we don't bother protecting all the arguments with parens, as is generally
0041  * good macro practice, in favor of extra legibility.
0042  * Rotation is separate from addition to prevent recomputation
0043  */
0044 #define ROUND(f, a, b, c, d, x, s)  \
0045     (a += f(b, c, d) + x, a = rol32(a, s))
0046 #define K1 0
0047 #define K2 013240474631UL
0048 #define K3 015666365641UL
0049
0050 /*
0051  * Basic cut-down MD4 transform.  Returns only 32 bits of result.
0052  */
0053 static __u32 half_md4_transform(__u32 buf[4], __u32 const in[8])
0054 {
0055     __u32 a = buf[0], b = buf[1], c = buf[2], d = buf[3];
0056
0057     /* Round 1 */
0058     ROUND(F, a, b, c, d, in[0] + K1,  3);
0059     ROUND(F, d, a, b, c, in[1] + K1,  7);
0060     ROUND(F, c, d, a, b, in[2] + K1, 11);
0061     ROUND(F, b, c, d, a, in[3] + K1, 19);
0062     ROUND(F, a, b, c, d, in[4] + K1,  3);
0063     ROUND(F, d, a, b, c, in[5] + K1,  7);
0064     ROUND(F, c, d, a, b, in[6] + K1, 11);
0065     ROUND(F, b, c, d, a, in[7] + K1, 19);
0066
0067     /* Round 2 */
0068     ROUND(G, a, b, c, d, in[1] + K2,  3);
0069     ROUND(G, d, a, b, c, in[3] + K2,  5);
0070     ROUND(G, c, d, a, b, in[5] + K2,  9);
0071     ROUND(G, b, c, d, a, in[7] + K2, 13);
0072     ROUND(G, a, b, c, d, in[0] + K2,  3);
0073     ROUND(G, d, a, b, c, in[2] + K2,  5);
0074     ROUND(G, c, d, a, b, in[4] + K2,  9);
0075     ROUND(G, b, c, d, a, in[6] + K2, 13);
0076
0077     /* Round 3 */
0078     ROUND(H, a, b, c, d, in[3] + K3,  3);
0079     ROUND(H, d, a, b, c, in[7] + K3,  9);
0080     ROUND(H, c, d, a, b, in[2] + K3, 11);
0081     ROUND(H, b, c, d, a, in[6] + K3, 15);
0082     ROUND(H, a, b, c, d, in[1] + K3,  3);
0083     ROUND(H, d, a, b, c, in[5] + K3,  9);
0084     ROUND(H, c, d, a, b, in[0] + K3, 11);
0085     ROUND(H, b, c, d, a, in[4] + K3, 15);
0086
0087     buf[0] += a;
0088     buf[1] += b;
0089     buf[2] += c;
0090     buf[3] += d;
0091
0092     return buf[1]; /* "most hashed" word */
0093 }
0094 #undef ROUND
0095 #undef K1
0096 #undef K2
0097 #undef K3
0098 #undef F
0099 #undef G
0100 #undef H
0101
0102 /* The old legacy hash */
0103 static __u32 dx_hack_hash_unsigned(const char *name, int len)
0104 {
0105     __u32 hash, hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9;
0106     const unsigned char *ucp = (const unsigned char *) name;
0107
0108     while (len--) {
0109         hash = hash1 + (hash0 ^ (((int) *ucp++) * 7152373));
0110
0111         if (hash & 0x80000000)
0112             hash -= 0x7fffffff;
0113         hash1 = hash0;
0114         hash0 = hash;
0115     }
0116     return hash0 << 1;
0117 }
0118
0119 static __u32 dx_hack_hash_signed(const char *name, int len)
0120 {
0121     __u32 hash, hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9;
0122     const signed char *scp = (const signed char *) name;
0123
0124     while (len--) {
0125         hash = hash1 + (hash0 ^ (((int) *scp++) * 7152373));
0126
0127         if (hash & 0x80000000)
0128             hash -= 0x7fffffff;
0129         hash1 = hash0;
0130         hash0 = hash;
0131     }
0132     return hash0 << 1;
0133 }
0134
0135 static void str2hashbuf_signed(const char *msg, int len, __u32 *buf, int num)
0136 {
0137     __u32   pad, val;
0138     int i;
0139     const signed char *scp = (const signed char *) msg;
0140
0141     pad = (__u32)len | ((__u32)len << 8);
0142     pad |= pad << 16;
0143
0144     val = pad;
0145     if (len > num*4)
0146         len = num * 4;
0147     for (i = 0; i < len; i++) {
0148         val = ((int) scp[i]) + (val << 8);
0149         if ((i % 4) == 3) {
0150             *buf++ = val;
0151             val = pad;
0152             num--;
0153         }
0154     }
0155     if (--num >= 0)
0156         *buf++ = val;
0157     while (--num >= 0)
0158         *buf++ = pad;
0159 }
0160
0161 static void str2hashbuf_unsigned(const char *msg, int len, __u32 *buf, int num)
0162 {
0163     __u32   pad, val;
0164     int i;
0165     const unsigned char *ucp = (const unsigned char *) msg;
0166
0167     pad = (__u32)len | ((__u32)len << 8);
0168     pad |= pad << 16;
0169
0170     val = pad;
0171     if (len > num*4)
0172         len = num * 4;
0173     for (i = 0; i < len; i++) {
0174         val = ((int) ucp[i]) + (val << 8);
0175         if ((i % 4) == 3) {
0176             *buf++ = val;
0177             val = pad;
0178             num--;
0179         }
0180     }
0181     if (--num >= 0)
0182         *buf++ = val;
0183     while (--num >= 0)
0184         *buf++ = pad;
0185 }
0186
0187 /*
0188  * Returns the hash of a filename.  If len is 0 and name is NULL, then
0189  * this function can be used to test whether or not a hash version is
0190  * supported.
0191  *
0192  * The seed is an 4 longword (32 bits) "secret" which can be used to
0193  * uniquify a hash.  If the seed is all zero's, then some default seed
0194  * may be used.
0195  *
0196  * A particular hash version specifies whether or not the seed is
0197  * represented, and whether or not the returned hash is 32 bits or 64
0198  * bits.  32 bit hashes will return 0 for the minor hash.
0199  */
0200 static int __ext4fs_dirhash(const struct inode *dir, const char *name, int len,
0201                 struct dx_hash_info *hinfo)
0202 {
0203     __u32   hash;
0204     __u32   minor_hash = 0;
0205     const char  *p;
0206     int     i;
0207     __u32       in[8], buf[4];
0208     void        (*str2hashbuf)(const char *, int, __u32 *, int) =
0209                 str2hashbuf_signed;
0210
0211     /* Initialize the default seed for the hash checksum functions */
0212     buf[0] = 0x67452301;
0213     buf[1] = 0xefcdab89;
0214     buf[2] = 0x98badcfe;
0215     buf[3] = 0x10325476;
0216
0217     /* Check to see if the seed is all zero's */
0218     if (hinfo->seed) {
0219         for (i = 0; i < 4; i++) {
0220             if (hinfo->seed[i]) {
0221                 memcpy(buf, hinfo->seed, sizeof(buf));
0222                 break;
0223             }
0224         }
0225     }
0226
0227     switch (hinfo->hash_version) {
0228     case DX_HASH_LEGACY_UNSIGNED:
0229         hash = dx_hack_hash_unsigned(name, len);
0230         break;
0231     case DX_HASH_LEGACY:
0232         hash = dx_hack_hash_signed(name, len);
0233         break;
0234     case DX_HASH_HALF_MD4_UNSIGNED:
0235         str2hashbuf = str2hashbuf_unsigned;
0236         fallthrough;
0237     case DX_HASH_HALF_MD4:
0238         p = name;
0239         while (len > 0) {
0240             (*str2hashbuf)(p, len, in, 8);
0241             half_md4_transform(buf, in);
0242             len -= 32;
0243             p += 32;
0244         }
0245         minor_hash = buf[2];
0246         hash = buf[1];
0247         break;
0248     case DX_HASH_TEA_UNSIGNED:
0249         str2hashbuf = str2hashbuf_unsigned;
0250         fallthrough;
0251     case DX_HASH_TEA:
0252         p = name;
0253         while (len > 0) {
0254             (*str2hashbuf)(p, len, in, 4);
0255             TEA_transform(buf, in);
0256             len -= 16;
0257             p += 16;
0258         }
0259         hash = buf[0];
0260         minor_hash = buf[1];
0261         break;
0262     case DX_HASH_SIPHASH:
0263     {
0264         struct qstr qname = QSTR_INIT(name, len);
0265         __u64   combined_hash;
0266
0267         if (fscrypt_has_encryption_key(dir)) {
0268             combined_hash = fscrypt_fname_siphash(dir, &qname);
0269         } else {
0270             ext4_warning_inode(dir, "Siphash requires key");
0271             return -1;
0272         }
0273
0274         hash = (__u32)(combined_hash >> 32);
0275         minor_hash = (__u32)combined_hash;
0276         break;
0277     }
0278     default:
0279         hinfo->hash = 0;
0280         return -1;
0281     }
0282     hash = hash & ~1;
0283     if (hash == (EXT4_HTREE_EOF_32BIT << 1))
0284         hash = (EXT4_HTREE_EOF_32BIT - 1) << 1;
0285     hinfo->hash = hash;
0286     hinfo->minor_hash = minor_hash;
0287     return 0;
0288 }
0289
0290 int ext4fs_dirhash(const struct inode *dir, const char *name, int len,
0291            struct dx_hash_info *hinfo)
0292 {
0293 #if IS_ENABLED(CONFIG_UNICODE)
0294     const struct unicode_map *um = dir->i_sb->s_encoding;
0295     int r, dlen;
0296     unsigned char *buff;
0297     struct qstr qstr = {.name = name, .len = len };
0298
0299     if (len && IS_CASEFOLDED(dir) && um &&
0300        (!IS_ENCRYPTED(dir) || fscrypt_has_encryption_key(dir))) {
0301         buff = kzalloc(sizeof(char) * PATH_MAX, GFP_KERNEL);
0302         if (!buff)
0303             return -ENOMEM;
0304
0305         dlen = utf8_casefold(um, &qstr, buff, PATH_MAX);
0306         if (dlen < 0) {
0307             kfree(buff);
0308             goto opaque_seq;
0309         }
0310
0311         r = __ext4fs_dirhash(dir, buff, dlen, hinfo);
0312
0313         kfree(buff);
0314         return r;
0315     }
0316 opaque_seq:
0317 #endif
0318     return __ext4fs_dirhash(dir, name, len, hinfo);
0319 }