fsverity_merkle/
util.rs

Help
1// Copyright 2023 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.
4
5use crate::{SHA256_SALT_PADDING, SHA512_SALT_PADDING};
6use mundane::hash::{Digest, Hasher, Sha256, Sha512};
7use std::fmt;
8
9/// `FsVerityHasherOptions` contains relevant metadata for the FsVerityHasher. The `salt` is set
10/// according to the FsverityMetadata struct stored in fxfs and `block_size` is that of the
11/// filesystem.
12#[derive(Clone)]
13pub struct FsVerityHasherOptions {
14    salt: Vec<u8>,
15    block_size: usize,
16    fsverity: bool,
17}
18
19impl FsVerityHasherOptions {
20    pub fn new(salt: Vec<u8>, block_size: usize) -> Self {
21        FsVerityHasherOptions { salt, block_size, fsverity: true }
22    }
23
24    pub fn new_dmverity(salt: Vec<u8>, block_size: usize) -> Self {
25        FsVerityHasherOptions { salt, block_size, fsverity: false }
26    }
27}
28
29/// `FsVerityHasher` is used by fsverity to construct merkle trees for verity-enabled files.
30/// `FsVerityHasher` is parameterized by a salt and a block size.
31#[derive(Clone)]
32pub enum FsVerityHasher {
33    Sha256(FsVerityHasherOptions),
34    Sha512(FsVerityHasherOptions),
35}
36
37impl fmt::Debug for FsVerityHasher {
38    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
39        match self {
40            FsVerityHasher::Sha256(metadata) => f
41                .debug_struct("FsVerityHasher::Sha256")
42                .field("salt", &metadata.salt)
43                .field("block_size", &metadata.block_size)
44                .finish(),
45            FsVerityHasher::Sha512(metadata) => f
46                .debug_struct("FsVerityHasher::Sha512")
47                .field("salt", &metadata.salt)
48                .field("block_size", &metadata.block_size)
49                .finish(),
50        }
51    }
52}
53
54impl FsVerityHasher {
55    pub fn block_size(&self) -> usize {
56        match self {
57            FsVerityHasher::Sha256(metadata) => metadata.block_size,
58            FsVerityHasher::Sha512(metadata) => metadata.block_size,
59        }
60    }
61
62    pub fn hash_size(&self) -> usize {
63        match self {
64            FsVerityHasher::Sha256(_) => <Sha256 as Hasher>::Digest::DIGEST_LEN,
65            FsVerityHasher::Sha512(_) => <Sha512 as Hasher>::Digest::DIGEST_LEN,
66        }
67    }
68
69    pub fn fsverity(&self) -> bool {
70        match &self {
71            FsVerityHasher::Sha256(metadata) => metadata.fsverity,
72            FsVerityHasher::Sha512(metadata) => metadata.fsverity,
73        }
74    }
75
76    /// Computes the MerkleTree digest from a `block` of data.
77    ///
78    /// A MerkleTree digest is a hash of a block of data. The block will be zero filled if its
79    /// len is less than the block_size, except for when the first data block is completely empty.
80    /// If `salt.len() > 0`, we prepend the block with the salt which itself is zero filled up
81    /// to the padding.
82    ///
83    /// # Panics
84    ///
85    /// Panics if `block.len()` exceeds `self.block_size()`.
86    pub fn hash_block(&self, block: &[u8]) -> Vec<u8> {
87        match self {
88            FsVerityHasher::Sha256(metadata) => {
89                if block.is_empty() {
90                    // Empty files have a root hash of all zeroes.
91                    return vec![0; <Sha256 as Hasher>::Digest::DIGEST_LEN];
92                }
93                assert!(block.len() <= metadata.block_size);
94                let mut hasher = Sha256::default();
95                let salt_size = metadata.salt.len() as u8;
96
97                if salt_size > 0 {
98                    hasher.update(&metadata.salt);
99                    if metadata.fsverity && salt_size % SHA256_SALT_PADDING != 0 {
100                        hasher.update(&vec![
101                            0;
102                            (SHA256_SALT_PADDING - salt_size % SHA256_SALT_PADDING)
103                                as usize
104                        ])
105                    }
106                }
107
108                hasher.update(block);
109                // Zero fill block up to self.block_size(). As a special case, if the first data
110                // block is completely empty, it is not zero filled.
111                if block.len() != metadata.block_size {
112                    hasher.update(&vec![0; metadata.block_size - block.len()]);
113                }
114                hasher.finish().bytes().to_vec()
115            }
116            FsVerityHasher::Sha512(metadata) => {
117                if block.is_empty() {
118                    // Empty files have a root hash of all zeroes.
119                    return vec![0; <Sha512 as Hasher>::Digest::DIGEST_LEN];
120                }
121                assert!(block.len() <= metadata.block_size);
122                let mut hasher = Sha512::default();
123                let salt_size = metadata.salt.len() as u8;
124
125                if salt_size > 0 {
126                    hasher.update(&metadata.salt);
127                    if metadata.fsverity && salt_size % SHA512_SALT_PADDING != 0 {
128                        hasher.update(&vec![
129                            0;
130                            (SHA512_SALT_PADDING - salt_size % SHA512_SALT_PADDING)
131                                as usize
132                        ])
133                    }
134                }
135
136                hasher.update(block);
137                // Zero fill block up to self.block_size(). As a special case, if the first data
138                // block is completely empty, it is not zero filled.
139                if block.len() != metadata.block_size {
140                    hasher.update(&vec![0; metadata.block_size - block.len()]);
141                }
142                hasher.finish().bytes().to_vec()
143            }
144        }
145    }
146
147    /// Computes a MerkleTree digest from a block of `hashes`.
148    ///
149    /// Like `hash_block`, `hash_hashes` zero fills incomplete buffers and prepends the digests
150    /// with a salt, which is zero filled up to the padding.
151    ///
152    /// # Panics
153    ///
154    /// Panics if any of the following conditions are met:
155    /// - `hashes.len()` is 0
156    /// - `hashes.len() > self.block_size() / digest length`
157    pub fn hash_hashes(&self, hashes: &[Vec<u8>]) -> Vec<u8> {
158        assert_ne!(hashes.len(), 0);
159        match self {
160            FsVerityHasher::Sha256(metadata) => {
161                assert!(
162                    hashes.len() <= (metadata.block_size / <Sha256 as Hasher>::Digest::DIGEST_LEN)
163                );
164                let mut hasher = Sha256::default();
165                let salt_size = metadata.salt.len() as u8;
166                if salt_size > 0 {
167                    hasher.update(&metadata.salt);
168                    if metadata.fsverity && salt_size % SHA256_SALT_PADDING != 0 {
169                        hasher.update(&vec![
170                            0;
171                            (SHA256_SALT_PADDING - salt_size % SHA256_SALT_PADDING)
172                                as usize
173                        ])
174                    }
175                }
176
177                for hash in hashes {
178                    hasher.update(hash.as_slice());
179                }
180                for _ in 0..((metadata.block_size / <Sha256 as Hasher>::Digest::DIGEST_LEN)
181                    - hashes.len())
182                {
183                    hasher.update(&[0; <Sha256 as Hasher>::Digest::DIGEST_LEN]);
184                }
185
186                hasher.finish().bytes().to_vec()
187            }
188            FsVerityHasher::Sha512(metadata) => {
189                assert!(
190                    hashes.len() <= (metadata.block_size / <Sha512 as Hasher>::Digest::DIGEST_LEN)
191                );
192
193                let mut hasher = Sha512::default();
194                let salt_size = metadata.salt.len() as u8;
195                if salt_size > 0 {
196                    hasher.update(&metadata.salt);
197                    if metadata.fsverity && salt_size % SHA512_SALT_PADDING != 0 {
198                        hasher.update(&vec![
199                            0;
200                            (SHA512_SALT_PADDING - salt_size % SHA512_SALT_PADDING)
201                                as usize
202                        ])
203                    }
204                }
205
206                for hash in hashes {
207                    hasher.update(hash.as_slice());
208                }
209                for _ in 0..((metadata.block_size / <Sha512 as Hasher>::Digest::DIGEST_LEN)
210                    - hashes.len())
211                {
212                    hasher.update(&[0; <Sha512 as Hasher>::Digest::DIGEST_LEN]);
213                }
214
215                hasher.finish().bytes().to_vec()
216            }
217        }
218    }
219}
220
221#[cfg(test)]
222mod tests {
223    use super::*;
224    use hex::FromHex;
225
226    #[test]
227    fn test_hash_block_empty_sha256() {
228        let hasher = FsVerityHasher::Sha256(FsVerityHasherOptions::new(vec![0xFF; 8], 4096));
229        let block = [];
230        let hash = hasher.hash_block(&block[..]);
231        assert_eq!(hash, [0; 32]);
232    }
233
234    #[test]
235    fn test_hash_block_empty_sha512() {
236        let hasher = FsVerityHasher::Sha512(FsVerityHasherOptions::new(vec![0xFF; 8], 4096));
237        let block = [];
238        let hash = hasher.hash_block(&block[..]);
239        assert_eq!(hash, [0; 64]);
240    }
241
242    #[test]
243    fn test_hash_block_partial_block_sha256() {
244        let hasher = FsVerityHasher::Sha256(FsVerityHasherOptions::new(vec![0xFF; 8], 4096));
245        let block = vec![0xFF; hasher.block_size()];
246        let mut block2: Vec<u8> = vec![0xFF; hasher.block_size() / 2];
247        block2.append(&mut vec![0; hasher.block_size() / 2]);
248        let hash = hasher.hash_block(&block[..]);
249        let expected = hasher.hash_block(&block[..]);
250        assert_eq!(hash, expected);
251    }
252
253    #[test]
254    fn test_hash_block_partial_block_sha512() {
255        let hasher = FsVerityHasher::Sha512(FsVerityHasherOptions::new(vec![0xFF; 8], 4096));
256        let block = vec![0xFF; hasher.block_size()];
257        let mut block2: Vec<u8> = vec![0xFF; hasher.block_size() / 2];
258        block2.append(&mut vec![0; hasher.block_size() / 2]);
259        let hash = hasher.hash_block(&block[..]);
260        let expected = hasher.hash_block(&block[..]);
261        assert_eq!(hash, expected);
262    }
263
264    #[test]
265    fn test_hash_block_single_sha256() {
266        let hasher = FsVerityHasher::Sha256(FsVerityHasherOptions::new(vec![0xFF; 8], 4096));
267        let block = vec![0xFF; hasher.block_size()];
268        let hash = hasher.hash_block(&block[..]);
269        // Root hash of file size 4096 = block_size
270        let expected: [u8; 32] =
271            FromHex::from_hex("207f18729b037894447f948b81f63abe68007d0cd7c99a4ae0a3e323c52013a5")
272                .unwrap();
273        assert_eq!(hash, expected);
274    }
275
276    #[test]
277    fn test_hash_block_single_sha512() {
278        let hasher = FsVerityHasher::Sha512(FsVerityHasherOptions::new(vec![0xFF; 8], 4096));
279        let block = vec![0xFF; hasher.block_size()];
280        let hash = hasher.hash_block(&block[..]);
281        // Root hash of file size 4096 = block_size
282        let expected: [u8; 64] = FromHex::from_hex("96d217a5f593384eb266b4bb2574b93c145ff1fd5ca89af52af6d4a14d2ce5200b2ddad30771c7cbcd139688e1a3847da7fd681490690adc945c3776154c42f6").unwrap();
283        assert_eq!(hash, expected);
284    }
285
286    #[test]
287    fn test_hash_hashes_full_block_sha256() {
288        let hasher = FsVerityHasher::Sha256(FsVerityHasherOptions::new(vec![0xFF; 8], 4096));
289        let mut leafs = Vec::new();
290        {
291            let block = vec![0xFF; hasher.block_size()];
292            for _i in 0..hasher.block_size() / hasher.hash_size() {
293                leafs.push(hasher.hash_block(&block));
294            }
295        }
296        let root = hasher.hash_hashes(&leafs);
297        // Root hash of file size 524288 = block_size * (block_size / hash_size) = 4096 * (4096 / 32)
298        let expected: [u8; 32] =
299            FromHex::from_hex("827c28168aba953cf74706d4f3e776bd8892f6edf7b25d89645409f24108fb0b")
300                .unwrap();
301        assert_eq!(root, expected);
302    }
303
304    #[test]
305    fn test_hash_hashes_full_block_sha512() {
306        let hasher = FsVerityHasher::Sha512(FsVerityHasherOptions::new(vec![0xFF; 8], 4096));
307        let mut leafs = Vec::new();
308        {
309            let block = vec![0xFF; hasher.block_size()];
310            for _i in 0..hasher.block_size() / hasher.hash_size() {
311                leafs.push(hasher.hash_block(&block));
312            }
313        }
314        let root = hasher.hash_hashes(&leafs);
315        // Root hash of file size 262144 = block_size * (block_size / hash_size) = 4096 * (4096 / 64)
316        let expected: [u8; 64] = FromHex::from_hex("17d1728518330e0d48951ba43908ea7ad73ea018597643aabba9af2e43dea70468ba54fa09f9c7d02b1c240bd8009d1abd49c05559815a3b73ce31c5c26f93ba").unwrap();
317        assert_eq!(root, expected);
318    }
319
320    #[test]
321    fn test_hash_hashes_zero_pad_same_length_sha256() {
322        let hasher = FsVerityHasher::Sha256(FsVerityHasherOptions::new(vec![0xFF; 8], 4096));
323        let data_hash = hasher.hash_block(&vec![0xFF; hasher.block_size()]);
324        let zero_hash = vec![0; 32];
325        let hash_of_single_hash = hasher.hash_hashes(&[data_hash.clone()]);
326        let hash_of_single_hash_and_zero_hash = hasher.hash_hashes(&[data_hash, zero_hash]);
327        assert_eq!(hash_of_single_hash, hash_of_single_hash_and_zero_hash);
328    }
329
330    #[test]
331    fn test_hash_hashes_zero_pad_same_length_sha512() {
332        let hasher = FsVerityHasher::Sha512(FsVerityHasherOptions::new(vec![0xFF; 8], 4096));
333        let data_hash = hasher.hash_block(&vec![0xFF; hasher.block_size()]);
334        let zero_hash = vec![0; 64];
335        let hash_of_single_hash = hasher.hash_hashes(&[data_hash.clone()]);
336        let hash_of_single_hash_and_zero_hash = hasher.hash_hashes(&[data_hash, zero_hash]);
337        assert_eq!(hash_of_single_hash, hash_of_single_hash_and_zero_hash);
338    }
339}
fsverity_merkle/util.rs

fsverity_merkle/
util.rs
