fscrypt/
direntry.rs

1// Copyright 2025 The Fuchsia Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4use fxfs_unicode::CasefoldStr;
5use siphasher::sip::SipHasher;
6use std::hash::Hasher;
7
8// We have to match the hash_code implementation used by f2fs to migrate direntry without
9// decrypting them.
10
11// See: https://en.wikipedia.org/wiki/Tiny_Encryption_Algorithm
12fn tea(input: &[u32; 4], buf: &mut [u32; 2]) {
13    const DELTA: u32 = 0x9e3779b9;
14    let mut sum = 0u32;
15    let mut v = buf.clone();
16    for _ in 0..16 {
17        sum = sum.wrapping_add(DELTA);
18        v[0] = v[0].wrapping_add(
19            (v[1] << 4).wrapping_add(input[0])
20                ^ v[1].wrapping_add(sum)
21                ^ (v[1] >> 5).wrapping_add(input[1]),
22        );
23        v[1] = v[1].wrapping_add(
24            (v[0] << 4).wrapping_add(input[2])
25                ^ v[0].wrapping_add(sum)
26                ^ (v[0] >> 5).wrapping_add(input[3]),
27        );
28    }
29    buf[0] = buf[0].wrapping_add(v[0]);
30    buf[1] = buf[1].wrapping_add(v[1]);
31}
32
33/// This algorithm is not cryptographically secure. It is used for
34/// filename hashing for compatibility reasons. `name_bytes` can be one of:
35///   * A case-sensitive UTF-8 filename (unencrypted)
36///   * A casefolded (+ nfd + default_ignorable) filename (unencrypted)
37///   * An encrypted case-sensitive UTF-8 filename (hashed over encrypted bytes)
38/// Encrypted casefolded filenames always use `casefold_encrypt_hash_filename()`.
39pub fn tea_hash_filename(name_bytes: impl IntoIterator<Item = u8>) -> u32 {
40    let mut name_bytes = name_bytes.into_iter().peekable();
41    if name_bytes.peek().is_none() {
42        return 0;
43    }
44    // The tea hash algorithm operates on groups of [4; u32], but the u32
45    // need to be big-endian.
46    let mut buf = [0x67452301, 0xefcdab89];
47    let mut done = false;
48    let mut bytes = [0u8; 16];
49    while !done {
50        let mut out = 0;
51        while out < 16 {
52            let Some(c) = name_bytes.next() else {
53                if out == 0 {
54                    return buf[0];
55                }
56                // Pad the remainder of the last buffer with the length of this
57                // chunk.
58                bytes[out..].fill(out as u8);
59                done = true;
60                break;
61            };
62            bytes[out] = c;
63            out += 1;
64        }
65        let mut k = [
66            u32::from_be_bytes(bytes[0..4].try_into().unwrap()),
67            u32::from_be_bytes(bytes[4..8].try_into().unwrap()),
68            u32::from_be_bytes(bytes[8..12].try_into().unwrap()),
69            u32::from_be_bytes(bytes[12..16].try_into().unwrap()),
70        ];
71        if done {
72            // Due to a quirk of how the buffer is filled, the last u32 needs
73            // to be rotated.
74            k[out / 4] = k[out / 4].rotate_left(out as u32 % 4 * 8);
75        }
76        tea(&k, &mut buf);
77    }
78    buf[0]
79}
80
81/// Hashes a filename for direntry indexing when both encryption and casefolding are enabled.
82/// Under this configuration, we need to avoid the hash_code leaking details of the filename
83/// but we also need it to be case insensitive so we cannot simply hash the encrypted form.
84pub fn casefold_encrypt_hash_filename(filename: &CasefoldStr, dirhash_key: &[u8; 16]) -> u32 {
85    if filename.as_str().is_empty() {
86        return 0;
87    }
88    let mut hasher = SipHasher::new_with_key(dirhash_key);
89    for b in filename.casefold_normalized_chars().flat_map(fxfs_unicode::utf8_bytes) {
90        hasher.write_u8(b);
91    }
92    hasher.finish() as u32
93}
94
95#[cfg(test)]
96mod tests {
97    use super::*;
98
99    #[test]
100    fn test_tea_hash_empty_filename() {
101        assert_eq!(tea_hash_filename(std::iter::empty()), 0);
102        // Verify non-empty still works (regression check)
103        assert_ne!(tea_hash_filename(b"a".iter().copied()), 0);
104    }
105
106    #[test]
107    fn test_casefold_encrypt_hash_empty_filename() {
108        let key = [0u8; 16];
109        assert_eq!(casefold_encrypt_hash_filename("".into(), &key), 0);
110        // Verify non-empty still works
111        assert_ne!(casefold_encrypt_hash_filename("a".into(), &key), 0);
112    }
113}
fscrypt/direntry.rs

fscrypt/
direntry.rs
