sys/fs/ext2fs/ext2_hash.c

   1 /*-
   2  * SPDX-License-Identifier: (BSD-2-Clause-FreeBSD 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  * $FreeBSD$
  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/param.h>
  57 #include <sys/systm.h>
  58 #include <sys/conf.h>
  59 #include <sys/vnode.h>
  60 #include <sys/sdt.h>
  61 #include <sys/stat.h>
  62 #include <sys/mount.h>
  63
  64 #include <fs/ext2fs/ext2fs.h>
  65 #include <fs/ext2fs/fs.h>
  66 #include <fs/ext2fs/htree.h>
  67 #include <fs/ext2fs/inode.h>
  68 #include <fs/ext2fs/ext2_mount.h>
  69 #include <fs/ext2fs/ext2_extern.h>
  70
  71 SDT_PROVIDER_DECLARE(ext2fs);
  72 /*
  73  * ext2fs trace probe:
  74  * arg0: verbosity. Higher numbers give more verbose messages
  75  * arg1: Textual message
  76  */
  77 SDT_PROBE_DEFINE2(ext2fs, , trace, hash, "int", "char*");
  78
  79 /* F, G, and H are MD4 functions */
  80 #define F(x, y, z) (((x) & (y)) | ((~x) & (z)))
  81 #define G(x, y, z) (((x) & (y)) | ((x) & (z)) | ((y) & (z)))
  82 #define H(x, y, z) ((x) ^ (y) ^ (z))
  83
  84 /* ROTATE_LEFT rotates x left n bits */
  85 #define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32 - (n))))
  86
  87 /*
  88  * FF, GG, and HH are transformations for rounds 1, 2, and 3.
  89  * Rotation is separated from addition to prevent recomputation.
  90  */
  91 #define FF(a, b, c, d, x, s) { \
  92         (a) += F ((b), (c), (d)) + (x); \
  93         (a) = ROTATE_LEFT ((a), (s)); \
  94 }
  95
  96 #define GG(a, b, c, d, x, s) { \
  97         (a) += G ((b), (c), (d)) + (x) + (uint32_t)0x5A827999; \
  98         (a) = ROTATE_LEFT ((a), (s)); \
  99 }
 100
 101 #define HH(a, b, c, d, x, s) { \
 102         (a) += H ((b), (c), (d)) + (x) + (uint32_t)0x6ED9EBA1; \
 103         (a) = ROTATE_LEFT ((a), (s)); \
 104 }
 105
 106 /*
 107  * MD4 basic transformation.  It transforms state based on block.
 108  *
 109  * This is a half md4 algorithm since Linux uses this algorithm for dir
 110  * index.  This function is derived from the RSA Data Security, Inc. MD4
 111  * Message-Digest Algorithm and was modified as necessary.
 112  *
 113  * The return value of this function is uint32_t in Linux, but actually we don't
 114  * need to check this value, so in our version this function doesn't return any
 115  * value.
 116  */
 117 static void
 118 ext2_half_md4(uint32_t hash[4], uint32_t data[8])
 119 {
 120         uint32_t a = hash[0], b = hash[1], c = hash[2], d = hash[3];
 121
 122         /* Round 1 */
 123         FF(a, b, c, d, data[0],  3);
 124         FF(d, a, b, c, data[1],  7);
 125         FF(c, d, a, b, data[2], 11);
 126         FF(b, c, d, a, data[3], 19);
 127         FF(a, b, c, d, data[4],  3);
 128         FF(d, a, b, c, data[5],  7);
 129         FF(c, d, a, b, data[6], 11);
 130         FF(b, c, d, a, data[7], 19);
 131
 132         /* Round 2 */
 133         GG(a, b, c, d, data[1],  3);
 134         GG(d, a, b, c, data[3],  5);
 135         GG(c, d, a, b, data[5],  9);
 136         GG(b, c, d, a, data[7], 13);
 137         GG(a, b, c, d, data[0],  3);
 138         GG(d, a, b, c, data[2],  5);
 139         GG(c, d, a, b, data[4],  9);
 140         GG(b, c, d, a, data[6], 13);
 141
 142         /* Round 3 */
 143         HH(a, b, c, d, data[3],  3);
 144         HH(d, a, b, c, data[7],  9);
 145         HH(c, d, a, b, data[2], 11);
 146         HH(b, c, d, a, data[6], 15);
 147         HH(a, b, c, d, data[1],  3);
 148         HH(d, a, b, c, data[5],  9);
 149         HH(c, d, a, b, data[0], 11);
 150         HH(b, c, d, a, data[4], 15);
 151
 152         hash[0] += a;
 153         hash[1] += b;
 154         hash[2] += c;
 155         hash[3] += d;
 156 }
 157
 158 /*
 159  * Tiny Encryption Algorithm.
 160  */
 161 static void
 162 ext2_tea(uint32_t hash[4], uint32_t data[8])
 163 {
 164         uint32_t tea_delta = 0x9E3779B9;
 165         uint32_t sum;
 166         uint32_t x = hash[0], y = hash[1];
 167         int n = 16;
 168         int i = 1;
 169
 170         while (n-- > 0) {
 171                 sum = i * tea_delta;
 172                 x += ((y << 4) + data[0]) ^ (y + sum) ^ ((y >> 5) + data[1]);
 173                 y += ((x << 4) + data[2]) ^ (x + sum) ^ ((x >> 5) + data[3]);
 174                 i++;
 175         }
 176
 177         hash[0] += x;
 178         hash[1] += y;
 179 }
 180
 181 static uint32_t
 182 ext2_legacy_hash(const char *name, int len, int unsigned_char)
 183 {
 184         uint32_t h0, h1 = 0x12A3FE2D, h2 = 0x37ABE8F9;
 185         uint32_t multi = 0x6D22F5;
 186         const unsigned char *uname = (const unsigned char *)name;
 187         const signed char *sname = (const signed char *)name;
 188         int val, i;
 189
 190         for (i = 0; i < len; i++) {
 191                 if (unsigned_char)
 192                         val = (u_int)*uname++;
 193                 else
 194                         val = (int)*sname++;
 195
 196                 h0 = h2 + (h1 ^ (val * multi));
 197                 if (h0 & 0x80000000)
 198                         h0 -= 0x7FFFFFFF;
 199                 h2 = h1;
 200                 h1 = h0;
 201         }
 202
 203         return (h1 << 1);
 204 }
 205
 206 static void
 207 ext2_prep_hashbuf(const char *src, int slen, uint32_t *dst, int dlen,
 208     int unsigned_char)
 209 {
 210         uint32_t padding = slen | (slen << 8) | (slen << 16) | (slen << 24);
 211         uint32_t buf_val;
 212         const unsigned char *ubuf = (const unsigned char *)src;
 213         const signed char *sbuf = (const signed char *)src;
 214         int len, i;
 215         int buf_byte;
 216
 217         if (slen > dlen)
 218                 len = dlen;
 219         else
 220                 len = slen;
 221
 222         buf_val = padding;
 223
 224         for (i = 0; i < len; i++) {
 225                 if (unsigned_char)
 226                         buf_byte = (u_int)ubuf[i];
 227                 else
 228                         buf_byte = (int)sbuf[i];
 229
 230                 if ((i % 4) == 0)
 231                         buf_val = padding;
 232
 233                 buf_val <<= 8;
 234                 buf_val += buf_byte;
 235
 236                 if ((i % 4) == 3) {
 237                         *dst++ = buf_val;
 238                         dlen -= sizeof(uint32_t);
 239                         buf_val = padding;
 240                 }
 241         }
 242
 243         dlen -= sizeof(uint32_t);
 244         if (dlen >= 0)
 245                 *dst++ = buf_val;
 246
 247         dlen -= sizeof(uint32_t);
 248         while (dlen >= 0) {
 249                 *dst++ = padding;
 250                 dlen -= sizeof(uint32_t);
 251         }
 252 }
 253
 254 int
 255 ext2_htree_hash(const char *name, int len,
 256     uint32_t *hash_seed, int hash_version,
 257     uint32_t *hash_major, uint32_t *hash_minor)
 258 {
 259         uint32_t hash[4];
 260         uint32_t data[8];
 261         uint32_t major = 0, minor = 0;
 262         int unsigned_char = 0;
 263
 264         if (!name || !hash_major)
 265                 return (-1);
 266
 267         if (len < 1 || len > 255)
 268                 goto error;
 269
 270         hash[0] = 0x67452301;
 271         hash[1] = 0xEFCDAB89;
 272         hash[2] = 0x98BADCFE;
 273         hash[3] = 0x10325476;
 274
 275         if (hash_seed)
 276                 memcpy(hash, hash_seed, sizeof(hash));
 277
 278         switch (hash_version) {
 279         case EXT2_HTREE_TEA_UNSIGNED:
 280                 unsigned_char = 1;
 281                 /* FALLTHROUGH */
 282         case EXT2_HTREE_TEA:
 283                 while (len > 0) {
 284                         ext2_prep_hashbuf(name, len, data, 16, unsigned_char);
 285                         ext2_tea(hash, data);
 286                         len -= 16;
 287                         name += 16;
 288                 }
 289                 major = hash[0];
 290                 minor = hash[1];
 291                 break;
 292         case EXT2_HTREE_LEGACY_UNSIGNED:
 293                 unsigned_char = 1;
 294                 /* FALLTHROUGH */
 295         case EXT2_HTREE_LEGACY:
 296                 major = ext2_legacy_hash(name, len, unsigned_char);
 297                 break;
 298         case EXT2_HTREE_HALF_MD4_UNSIGNED:
 299                 unsigned_char = 1;
 300                 /* FALLTHROUGH */
 301         case EXT2_HTREE_HALF_MD4:
 302                 while (len > 0) {
 303                         ext2_prep_hashbuf(name, len, data, 32, unsigned_char);
 304                         ext2_half_md4(hash, data);
 305                         len -= 32;
 306                         name += 32;
 307                 }
 308                 major = hash[1];
 309                 minor = hash[2];
 310                 break;
 311         default:
 312                 SDT_PROBE2(ext2fs, , trace, hash, 1, "unexpected hash version");
 313                 goto error;
 314         }
 315
 316         major &= ~1;
 317         if (major == (EXT2_HTREE_EOF << 1))
 318                 major = (EXT2_HTREE_EOF - 1) << 1;
 319         *hash_major = major;
 320         if (hash_minor)
 321                 *hash_minor = minor;
 322
 323         return (0);
 324
 325 error:
 326         *hash_major = 0;
 327         if (hash_minor)
 328                 *hash_minor = 0;
 329         return (-1);
 330 }