fsverity_merkle/
util.rs

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 anyhow::{Error, anyhow, ensure};
7use fidl_fuchsia_io as fio;
8use mundane::hash::{Digest, Hasher, Sha256, Sha512};
9use std::fmt;
10use storage_ptr_slice::PtrByteSlice;
11use zerocopy::{FromBytes, Immutable, IntoBytes, KnownLayout};
12
13/// `FsVerityHasherOptions` contains relevant metadata for the FsVerityHasher. The `salt` is set
14/// according to the FsverityMetadata struct stored in fxfs and `block_size` is that of the
15/// filesystem.
16#[derive(Clone, PartialEq, Eq)]
17pub struct FsVerityHasherOptions {
18    salt: Vec<u8>,
19    block_size: usize,
20    fsverity: bool,
21}
22
23impl FsVerityHasherOptions {
24    pub fn new(salt: Vec<u8>, block_size: usize) -> Self {
25        FsVerityHasherOptions { salt, block_size, fsverity: true }
26    }
27
28    pub fn new_dmverity(salt: Vec<u8>, block_size: usize) -> Self {
29        FsVerityHasherOptions { salt, block_size, fsverity: false }
30    }
31}
32
33/// The raw structure of an FsVerity descriptor. The values in this are not necessarily valid.
34#[derive(Debug, Copy, Clone, KnownLayout, FromBytes, Immutable, IntoBytes)]
35#[repr(C, packed)]
36pub struct FsVerityDescriptorRaw {
37    version: u8,
38    algorithm: u8,
39    block_size_log2: u8,
40    salt_size: u8,
41    _reserved_1: [u8; 4],
42    file_size: [u8; 8],
43    root_digest: [u8; 64],
44    salt: [u8; 32],
45    _reserved_2: [u8; 144],
46}
47
48impl FsVerityDescriptorRaw {
49    pub fn new(
50        algorithm: fio::HashAlgorithm,
51        block_size: u64,
52        file_size: u64,
53        root: &[u8],
54        salt: &[u8],
55    ) -> Result<Self, Error> {
56        ensure!(block_size.is_power_of_two() && block_size >= 1024, "Invalid merkle block size");
57        ensure!(salt.len() <= 32, "Salt too long");
58        let (hash_len, algorithm) = match algorithm {
59            fio::HashAlgorithm::Sha256 => (<Sha256 as Hasher>::Digest::DIGEST_LEN, 1),
60            fio::HashAlgorithm::Sha512 => (<Sha512 as Hasher>::Digest::DIGEST_LEN, 2),
61            _ => return Err(anyhow!("Unknown hash type")),
62        };
63        ensure!(root.len() == hash_len, "Wrong length of root digest");
64
65        let mut this = Self {
66            version: 1,
67            algorithm,
68            block_size_log2: block_size.trailing_zeros() as u8,
69            salt_size: salt.len() as u8,
70            _reserved_1: [0u8; 4],
71            file_size: file_size.to_le_bytes(),
72            root_digest: [0u8; 64],
73            salt: [0u8; 32],
74            _reserved_2: [0u8; 144],
75        };
76        this.root_digest.as_mut_slice()[0..hash_len].copy_from_slice(root);
77        this.salt.as_mut_slice()[0..salt.len()].copy_from_slice(salt);
78        Ok(this)
79    }
80
81    pub fn write_to_slice(&self, dest: &mut [u8]) -> Result<(), Error> {
82        self.write_to_prefix(dest).map_err(|_| anyhow!("Buffer too short"))
83    }
84}
85
86/// A descriptor struct for fsverity backed by a pointer slice. It does not own the bytes
87/// backing it.
88#[derive(Debug, Clone)]
89pub struct FsVerityDescriptor<'a> {
90    inner: FsVerityDescriptorRaw,
91    bytes: PtrByteSlice<'a>,
92    descriptor_offset: usize,
93}
94
95impl<'a> FsVerityDescriptor<'a> {
96    /// Create a descriptor from data that can be converted into a pointer slice.
97    pub fn new(bytes: impl Into<PtrByteSlice<'a>>, block_size: usize) -> Result<Self, Error> {
98        let bytes = bytes.into();
99        ensure!(block_size.is_power_of_two() && block_size > 0, "Invalid block size.");
100        // Descriptor is placed in the last block. Go to the start of the last block.
101        let descriptor_offset = if bytes.len() == 0 {
102            // This will fail properly below.
103            0
104        } else {
105            ((bytes.len() - 1) / block_size) * block_size
106        };
107        ensure!(
108            bytes.len() >= descriptor_offset + std::mem::size_of::<FsVerityDescriptorRaw>(),
109            "Descriptor bytes too small"
110        );
111        let inner = bytes
112            .subslice(
113                descriptor_offset..descriptor_offset + std::mem::size_of::<FsVerityDescriptorRaw>(),
114            )
115            .read::<FsVerityDescriptorRaw>()
116            .unwrap();
117
118        ensure!(inner.version == 1, "Unsupported version {}", inner.version);
119
120        ensure!(
121            inner.algorithm == 1 || inner.algorithm == 2,
122            "Unsupported algorithm {}",
123            inner.algorithm
124        );
125
126        // Merkle block size here doesn't necessarily need to match fs block size, but it is the
127        // most efficient choice, greatly simplifies handling, and is the only supported choice in
128        // the destination fxfs. It it stored in the descriptor as the log_2 of the value. It must
129        // be at least 1024 and also no more than system page size. We won't verify page size here
130        // but also won't support more than 64KiB.
131        ensure!(
132            inner.block_size_log2 >= 10 && inner.block_size_log2 <= 16,
133            "Only supports 1KiB-64KiB"
134        );
135
136        ensure!(inner.salt_size <= 32, "Salt too big for struct");
137        let this = Self { inner, bytes, descriptor_offset };
138        ensure!(this.block_size() == block_size, "Only support same block size as file system");
139        Ok(this)
140    }
141
142    pub fn digest_len(&self) -> usize {
143        match self.inner.algorithm {
144            1 => <Sha256 as Hasher>::Digest::DIGEST_LEN,
145            2 => <Sha512 as Hasher>::Digest::DIGEST_LEN,
146            _ => unreachable!("This should be verified at creation time."),
147        }
148    }
149
150    pub fn digest_algorithm(&self) -> fio::HashAlgorithm {
151        match self.inner.algorithm {
152            1 => fio::HashAlgorithm::Sha256,
153            2 => fio::HashAlgorithm::Sha512,
154            _ => unreachable!("This should be verified at creation time."),
155        }
156    }
157
158    pub fn block_size(&self) -> usize {
159        1usize << self.inner.block_size_log2
160    }
161
162    pub fn file_size(&self) -> usize {
163        u64::from_le_bytes(self.inner.file_size) as usize
164    }
165
166    pub fn root_digest(&self) -> &[u8] {
167        &self.inner.root_digest[..self.digest_len()]
168    }
169
170    pub fn salt(&self) -> &[u8] {
171        &self.inner.salt[..self.inner.salt_size as usize]
172    }
173
174    /// Return a hasher configured based on this descriptor.
175    pub fn hasher(&self) -> FsVerityHasher {
176        match self.inner.algorithm {
177            1 => FsVerityHasher::Sha256(FsVerityHasherOptions::new(
178                self.salt().to_vec(),
179                self.block_size(),
180            )),
181            2 => FsVerityHasher::Sha512(FsVerityHasherOptions::new(
182                self.salt().to_vec(),
183                self.block_size(),
184            )),
185            _ => unreachable!("This should be verified at creation time."),
186        }
187    }
188
189    /// A vector containing a copy of all the leaf digests required for the file.
190    pub fn leaf_digests(&self) -> Result<Vec<u8>, Error> {
191        let block_size = self.block_size();
192        Ok(match self.file_size().div_ceil(block_size) {
193            0 => vec![],
194            1 => self.root_digest().to_vec(),
195            file_blocks => {
196                let leaf_size = file_blocks * self.digest_len();
197                let layer_size = leaf_size.next_multiple_of(block_size);
198                ensure!(self.descriptor_offset >= layer_size, "No space for leaves in descriptor");
199                let leaf_offset = self.descriptor_offset - layer_size;
200                self.bytes.subslice(leaf_offset..(leaf_offset + leaf_size)).to_vec()
201            }
202        })
203    }
204}
205
206/// `FsVerityHasher` is used by fsverity to construct merkle trees for verity-enabled files.
207/// `FsVerityHasher` is parameterized by a salt and a block size.
208#[derive(Clone, PartialEq, Eq)]
209pub enum FsVerityHasher {
210    Sha256(FsVerityHasherOptions),
211    Sha512(FsVerityHasherOptions),
212}
213
214impl fmt::Debug for FsVerityHasher {
215    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
216        match self {
217            FsVerityHasher::Sha256(metadata) => f
218                .debug_struct("FsVerityHasher::Sha256")
219                .field("salt", &metadata.salt)
220                .field("block_size", &metadata.block_size)
221                .finish(),
222            FsVerityHasher::Sha512(metadata) => f
223                .debug_struct("FsVerityHasher::Sha512")
224                .field("salt", &metadata.salt)
225                .field("block_size", &metadata.block_size)
226                .finish(),
227        }
228    }
229}
230
231impl FsVerityHasher {
232    pub fn block_size(&self) -> usize {
233        match self {
234            FsVerityHasher::Sha256(metadata) => metadata.block_size,
235            FsVerityHasher::Sha512(metadata) => metadata.block_size,
236        }
237    }
238
239    pub fn hash_size(&self) -> usize {
240        match self {
241            FsVerityHasher::Sha256(_) => <Sha256 as Hasher>::Digest::DIGEST_LEN,
242            FsVerityHasher::Sha512(_) => <Sha512 as Hasher>::Digest::DIGEST_LEN,
243        }
244    }
245
246    pub fn fsverity(&self) -> bool {
247        match &self {
248            FsVerityHasher::Sha256(metadata) => metadata.fsverity,
249            FsVerityHasher::Sha512(metadata) => metadata.fsverity,
250        }
251    }
252
253    /// Computes the MerkleTree digest from a `block` of data.
254    ///
255    /// A MerkleTree digest is a hash of a block of data. The block will be zero filled if its
256    /// len is less than the block_size, except for when the first data block is completely empty.
257    /// If `salt.len() > 0`, we prepend the block with the salt which itself is zero filled up
258    /// to the padding.
259    ///
260    /// # Panics
261    ///
262    /// Panics if `block.len()` exceeds `self.block_size()`.
263    pub fn hash_block(&self, block: &[u8]) -> Vec<u8> {
264        match self {
265            FsVerityHasher::Sha256(metadata) => {
266                if block.is_empty() {
267                    // Empty files have a root hash of all zeroes.
268                    return vec![0; <Sha256 as Hasher>::Digest::DIGEST_LEN];
269                }
270                assert!(block.len() <= metadata.block_size);
271                let mut hasher = Sha256::default();
272                let salt_size = metadata.salt.len() as u8;
273
274                if salt_size > 0 {
275                    hasher.update(&metadata.salt);
276                    if metadata.fsverity && salt_size % SHA256_SALT_PADDING != 0 {
277                        hasher.update(&vec![
278                            0;
279                            (SHA256_SALT_PADDING - salt_size % SHA256_SALT_PADDING)
280                                as usize
281                        ])
282                    }
283                }
284
285                hasher.update(block);
286                // Zero fill block up to self.block_size(). As a special case, if the first data
287                // block is completely empty, it is not zero filled.
288                if block.len() != metadata.block_size {
289                    hasher.update(&vec![0; metadata.block_size - block.len()]);
290                }
291                hasher.finish().bytes().to_vec()
292            }
293            FsVerityHasher::Sha512(metadata) => {
294                if block.is_empty() {
295                    // Empty files have a root hash of all zeroes.
296                    return vec![0; <Sha512 as Hasher>::Digest::DIGEST_LEN];
297                }
298                assert!(block.len() <= metadata.block_size);
299                let mut hasher = Sha512::default();
300                let salt_size = metadata.salt.len() as u8;
301
302                if salt_size > 0 {
303                    hasher.update(&metadata.salt);
304                    if metadata.fsverity && salt_size % SHA512_SALT_PADDING != 0 {
305                        hasher.update(&vec![
306                            0;
307                            (SHA512_SALT_PADDING - salt_size % SHA512_SALT_PADDING)
308                                as usize
309                        ])
310                    }
311                }
312
313                hasher.update(block);
314                // Zero fill block up to self.block_size(). As a special case, if the first data
315                // block is completely empty, it is not zero filled.
316                if block.len() != metadata.block_size {
317                    hasher.update(&vec![0; metadata.block_size - block.len()]);
318                }
319                hasher.finish().bytes().to_vec()
320            }
321        }
322    }
323
324    /// Computes a MerkleTree digest from a block of `hashes`.
325    ///
326    /// Like `hash_block`, `hash_hashes` zero fills incomplete buffers and prepends the digests
327    /// with a salt, which is zero filled up to the padding.
328    ///
329    /// # Panics
330    ///
331    /// Panics if any of the following conditions are met:
332    /// - `hashes.len()` is 0
333    /// - `hashes.len() > self.block_size() / digest length`
334    pub fn hash_hashes(&self, hashes: &[Vec<u8>]) -> Vec<u8> {
335        assert_ne!(hashes.len(), 0);
336        match self {
337            FsVerityHasher::Sha256(metadata) => {
338                assert!(
339                    hashes.len() <= (metadata.block_size / <Sha256 as Hasher>::Digest::DIGEST_LEN)
340                );
341                let mut hasher = Sha256::default();
342                let salt_size = metadata.salt.len() as u8;
343                if salt_size > 0 {
344                    hasher.update(&metadata.salt);
345                    if metadata.fsverity && salt_size % SHA256_SALT_PADDING != 0 {
346                        hasher.update(&vec![
347                            0;
348                            (SHA256_SALT_PADDING - salt_size % SHA256_SALT_PADDING)
349                                as usize
350                        ])
351                    }
352                }
353
354                for hash in hashes {
355                    hasher.update(hash.as_slice());
356                }
357                for _ in 0..((metadata.block_size / <Sha256 as Hasher>::Digest::DIGEST_LEN)
358                    - hashes.len())
359                {
360                    hasher.update(&[0; <Sha256 as Hasher>::Digest::DIGEST_LEN]);
361                }
362
363                hasher.finish().bytes().to_vec()
364            }
365            FsVerityHasher::Sha512(metadata) => {
366                assert!(
367                    hashes.len() <= (metadata.block_size / <Sha512 as Hasher>::Digest::DIGEST_LEN)
368                );
369
370                let mut hasher = Sha512::default();
371                let salt_size = metadata.salt.len() as u8;
372                if salt_size > 0 {
373                    hasher.update(&metadata.salt);
374                    if metadata.fsverity && salt_size % SHA512_SALT_PADDING != 0 {
375                        hasher.update(&vec![
376                            0;
377                            (SHA512_SALT_PADDING - salt_size % SHA512_SALT_PADDING)
378                                as usize
379                        ])
380                    }
381                }
382
383                for hash in hashes {
384                    hasher.update(hash.as_slice());
385                }
386                for _ in 0..((metadata.block_size / <Sha512 as Hasher>::Digest::DIGEST_LEN)
387                    - hashes.len())
388                {
389                    hasher.update(&[0; <Sha512 as Hasher>::Digest::DIGEST_LEN]);
390                }
391
392                hasher.finish().bytes().to_vec()
393            }
394        }
395    }
396}
397
398#[cfg(test)]
399mod tests {
400    use super::*;
401    use crate::{FsVerityHash, MerkleTreeBuilder, Sha256Hash, Sha512Hash};
402    use fidl_fuchsia_io as fio;
403    use hex::FromHex;
404    use test_case::test_case;
405
406    const BLOCK_SIZE: usize = 4096;
407
408    #[test]
409    fn test_hash_block_empty_sha256() {
410        let hasher = FsVerityHasher::Sha256(FsVerityHasherOptions::new(vec![0xFF; 8], 4096));
411        let block = [];
412        let hash = hasher.hash_block(&block[..]);
413        assert_eq!(hash, [0; 32]);
414    }
415
416    #[test]
417    fn test_hash_block_empty_sha512() {
418        let hasher = FsVerityHasher::Sha512(FsVerityHasherOptions::new(vec![0xFF; 8], 4096));
419        let block = [];
420        let hash = hasher.hash_block(&block[..]);
421        assert_eq!(hash, [0; 64]);
422    }
423
424    #[test]
425    fn test_hash_block_partial_block_sha256() {
426        let hasher = FsVerityHasher::Sha256(FsVerityHasherOptions::new(vec![0xFF; 8], 4096));
427        let block = vec![0xFF; hasher.block_size()];
428        let mut block2: Vec<u8> = vec![0xFF; hasher.block_size() / 2];
429        block2.append(&mut vec![0; hasher.block_size() / 2]);
430        let hash = hasher.hash_block(&block[..]);
431        let expected = hasher.hash_block(&block[..]);
432        assert_eq!(hash, expected);
433    }
434
435    #[test]
436    fn test_hash_block_partial_block_sha512() {
437        let hasher = FsVerityHasher::Sha512(FsVerityHasherOptions::new(vec![0xFF; 8], 4096));
438        let block = vec![0xFF; hasher.block_size()];
439        let mut block2: Vec<u8> = vec![0xFF; hasher.block_size() / 2];
440        block2.append(&mut vec![0; hasher.block_size() / 2]);
441        let hash = hasher.hash_block(&block[..]);
442        let expected = hasher.hash_block(&block[..]);
443        assert_eq!(hash, expected);
444    }
445
446    #[test]
447    fn test_hash_block_single_sha256() {
448        let hasher = FsVerityHasher::Sha256(FsVerityHasherOptions::new(vec![0xFF; 8], 4096));
449        let block = vec![0xFF; hasher.block_size()];
450        let hash = hasher.hash_block(&block[..]);
451        // Root hash of file size 4096 = block_size
452        let expected: [u8; 32] =
453            FromHex::from_hex("207f18729b037894447f948b81f63abe68007d0cd7c99a4ae0a3e323c52013a5")
454                .unwrap();
455        assert_eq!(hash, expected);
456    }
457
458    #[test]
459    fn test_hash_block_single_sha512() {
460        let hasher = FsVerityHasher::Sha512(FsVerityHasherOptions::new(vec![0xFF; 8], 4096));
461        let block = vec![0xFF; hasher.block_size()];
462        let hash = hasher.hash_block(&block[..]);
463        // Root hash of file size 4096 = block_size
464        let expected: [u8; 64] = FromHex::from_hex("96d217a5f593384eb266b4bb2574b93c145ff1fd5ca89af52af6d4a14d2ce5200b2ddad30771c7cbcd139688e1a3847da7fd681490690adc945c3776154c42f6").unwrap();
465        assert_eq!(hash, expected);
466    }
467
468    #[test]
469    fn test_hash_hashes_full_block_sha256() {
470        let hasher = FsVerityHasher::Sha256(FsVerityHasherOptions::new(vec![0xFF; 8], 4096));
471        let mut leafs = Vec::new();
472        {
473            let block = vec![0xFF; hasher.block_size()];
474            for _i in 0..hasher.block_size() / hasher.hash_size() {
475                leafs.push(hasher.hash_block(&block));
476            }
477        }
478        let root = hasher.hash_hashes(&leafs);
479        // Root hash of file size 524288 = block_size * (block_size / hash_size) = 4096 * (4096 / 32)
480        let expected: [u8; 32] =
481            FromHex::from_hex("827c28168aba953cf74706d4f3e776bd8892f6edf7b25d89645409f24108fb0b")
482                .unwrap();
483        assert_eq!(root, expected);
484    }
485
486    #[test]
487    fn test_hash_hashes_full_block_sha512() {
488        let hasher = FsVerityHasher::Sha512(FsVerityHasherOptions::new(vec![0xFF; 8], 4096));
489        let mut leafs = Vec::new();
490        {
491            let block = vec![0xFF; hasher.block_size()];
492            for _i in 0..hasher.block_size() / hasher.hash_size() {
493                leafs.push(hasher.hash_block(&block));
494            }
495        }
496        let root = hasher.hash_hashes(&leafs);
497        // Root hash of file size 262144 = block_size * (block_size / hash_size) = 4096 * (4096 / 64)
498        let expected: [u8; 64] = FromHex::from_hex("17d1728518330e0d48951ba43908ea7ad73ea018597643aabba9af2e43dea70468ba54fa09f9c7d02b1c240bd8009d1abd49c05559815a3b73ce31c5c26f93ba").unwrap();
499        assert_eq!(root, expected);
500    }
501
502    #[test_case(FsVerityHasher::Sha256(FsVerityHasherOptions::new(vec![0xFF; 8], 4096)); "sha256")]
503    #[test_case(FsVerityHasher::Sha512(FsVerityHasherOptions::new(vec![0xFF; 8], 4096)); "sha512")]
504    fn test_hash_hashes_zero_pad_same_length(hasher: FsVerityHasher) {
505        let data_hash = hasher.hash_block(&vec![0xFF; hasher.block_size()]);
506        let mut zero_hash = Vec::with_capacity(hasher.hash_size());
507        zero_hash.extend(std::iter::repeat(0).take(hasher.hash_size()));
508        let hash_of_single_hash = hasher.hash_hashes(&[data_hash.clone()]);
509        let hash_of_single_hash_and_zero_hash = hasher.hash_hashes(&[data_hash, zero_hash]);
510        assert_eq!(hash_of_single_hash, hash_of_single_hash_and_zero_hash);
511    }
512
513    #[test_case(vec![0u8; BLOCK_SIZE + 256], BLOCK_SIZE ; "test_exact_size")]
514    #[test_case(vec![0u8; 256], 0 ; "test_exact_size_from_zero")]
515    #[test_case(vec![0u8; BLOCK_SIZE * 2], BLOCK_SIZE ; "test_block_aligned")]
516    #[test_case(vec![0u8; BLOCK_SIZE], 0 ; "test_block_aligned_from_zero")]
517    #[test_case(vec![0u8; BLOCK_SIZE + 300], BLOCK_SIZE ; "test_trailing_space")]
518    #[test_case(vec![0u8; 300], 0 ; "test_trailing_space_from_zero")]
519    fn descriptor_read_write_locations(mut buf: Vec<u8>, descriptor_offset: usize) {
520        let salt = [4u8; 6];
521        let root = [65u8; 32];
522        let descriptor = FsVerityDescriptorRaw::new(
523            fio::HashAlgorithm::Sha256,
524            BLOCK_SIZE as u64,
525            8192,
526            root.as_slice(),
527            salt.as_slice(),
528        )
529        .expect("Create raw descriptor");
530
531        descriptor
532            .write_to_slice(&mut buf.as_mut_slice()[descriptor_offset..])
533            .expect("Writing to buf.");
534
535        let descriptor2 =
536            FsVerityDescriptor::new(buf.as_slice(), BLOCK_SIZE).expect("Parsing descriptor back");
537        // Verify the raw values.
538        assert_eq!(descriptor2.inner.version, descriptor.version);
539        assert_eq!(descriptor2.inner.algorithm, descriptor.algorithm);
540        assert_eq!(descriptor2.inner.block_size_log2, descriptor.block_size_log2);
541        assert_eq!(descriptor2.inner.salt_size, descriptor.salt_size);
542        assert_eq!(descriptor2.inner.file_size, descriptor.file_size);
543        assert_eq!(descriptor2.inner.root_digest, descriptor.root_digest);
544        assert_eq!(descriptor2.inner.salt, descriptor.salt);
545
546        // Verify the processed values.
547        assert_eq!(descriptor2.file_size(), 8192);
548        assert_eq!(descriptor2.digest_len(), 32);
549        assert_eq!(descriptor2.digest_algorithm(), fio::HashAlgorithm::Sha256);
550        assert_eq!(descriptor2.root_digest(), root.as_slice());
551        assert_eq!(descriptor2.salt(), salt.as_slice());
552    }
553
554    #[test_case(2, vec![0u8; BLOCK_SIZE * 2], BLOCK_SIZE, 0, FsVerityHasher::Sha256(FsVerityHasherOptions::new(vec![0xAB; 8], BLOCK_SIZE)); "sha256")]
555    #[test_case(2, vec![0u8; BLOCK_SIZE * 2], BLOCK_SIZE, 0, FsVerityHasher::Sha512(FsVerityHasherOptions::new(vec![0xAB; 8], BLOCK_SIZE)); "sha512")]
556    // Enough blocks to have a second layer of merkle tree.
557    #[test_case(129, vec![0u8; BLOCK_SIZE * 3], BLOCK_SIZE * 2, 0, FsVerityHasher::Sha256(FsVerityHasherOptions::new(vec![0xAB; 8], BLOCK_SIZE)); "sha256_big_file")]
558    #[test_case(129, vec![0u8; BLOCK_SIZE * 4], BLOCK_SIZE * 3, 0, FsVerityHasher::Sha512(FsVerityHasherOptions::new(vec![0xAB; 8], BLOCK_SIZE)); "sha512_big_file")]
559    // Don't block align the end, just enough space for the descriptor.
560    #[test_case(2, vec![0u8; BLOCK_SIZE + 256], BLOCK_SIZE, 0, FsVerityHasher::Sha256(FsVerityHasherOptions::new(vec![0xAB; 8], BLOCK_SIZE)); "sha256_exact_fit")]
561    #[test_case(2, vec![0u8; BLOCK_SIZE + 256], BLOCK_SIZE, 0, FsVerityHasher::Sha512(FsVerityHasherOptions::new(vec![0xAB; 8], BLOCK_SIZE)); "sha512_exact_fit")]
562    // A really big merkle buffer, everything should still be at the end of it.
563    #[test_case(2, vec![0u8; BLOCK_SIZE * 100], BLOCK_SIZE * 99, BLOCK_SIZE * 98, FsVerityHasher::Sha256(FsVerityHasherOptions::new(vec![0xAB; 8], BLOCK_SIZE)); "sha256_big_buf")]
564    #[test_case(2, vec![0u8; BLOCK_SIZE * 100], BLOCK_SIZE * 99, BLOCK_SIZE * 98, FsVerityHasher::Sha512(FsVerityHasherOptions::new(vec![0xAB; 8], BLOCK_SIZE)); "sha512_big_buf")]
565    // File has only a single block. This is a special case for generating the leaf data.
566    #[test_case(1, vec![0u8; BLOCK_SIZE * 2], BLOCK_SIZE, 0, FsVerityHasher::Sha256(FsVerityHasherOptions::new(vec![0xAB; 8], BLOCK_SIZE)); "sha256_one_block")]
567    #[test_case(1, vec![0u8; BLOCK_SIZE * 2], BLOCK_SIZE, 0, FsVerityHasher::Sha512(FsVerityHasherOptions::new(vec![0xAB; 8], BLOCK_SIZE)); "sha512_one_block")]
568    // File has no data blocks. This is a special case for generating the leaf data.
569    #[test_case(0, vec![0u8; BLOCK_SIZE * 2], BLOCK_SIZE, 0, FsVerityHasher::Sha256(FsVerityHasherOptions::new(vec![0xAB; 8], BLOCK_SIZE)); "sha256_empty_file")]
570    #[test_case(0, vec![0u8; BLOCK_SIZE * 2], BLOCK_SIZE, 0, FsVerityHasher::Sha512(FsVerityHasherOptions::new(vec![0xAB; 8], BLOCK_SIZE)); "sha512_empty_file")]
571    fn descriptor_merkle_leaves_locations(
572        file_blocks: usize,
573        buf: Vec<u8>,
574        descriptor_offset: usize,
575        leaf_offset: usize,
576        hasher: FsVerityHasher,
577    ) {
578        match hasher {
579            FsVerityHasher::Sha256(_) => descriptor_merkle_leaves_locations_impl::<Sha256Hash>(
580                file_blocks,
581                buf,
582                descriptor_offset,
583                leaf_offset,
584                hasher,
585            ),
586            FsVerityHasher::Sha512(_) => descriptor_merkle_leaves_locations_impl::<Sha512Hash>(
587                file_blocks,
588                buf,
589                descriptor_offset,
590                leaf_offset,
591                hasher,
592            ),
593        }
594    }
595
596    fn descriptor_merkle_leaves_locations_impl<D: FsVerityHash>(
597        file_blocks: usize,
598        mut buf: Vec<u8>,
599        descriptor_offset: usize,
600        leaf_offset: usize,
601        hasher: FsVerityHasher,
602    ) {
603        let mut file = vec![0u8; BLOCK_SIZE * file_blocks];
604        for i in 0..file_blocks {
605            let offset = i * BLOCK_SIZE;
606            file.as_mut_slice()[offset..(offset + BLOCK_SIZE)].fill(i as u8);
607        }
608
609        let (algorithm, salt) = match &hasher {
610            FsVerityHasher::Sha256(options) => (fio::HashAlgorithm::Sha256, options.salt.clone()),
611            FsVerityHasher::Sha512(options) => (fio::HashAlgorithm::Sha512, options.salt.clone()),
612        };
613
614        let hash_size = hasher.hash_size();
615        let mut builder = MerkleTreeBuilder::<D>::new(hasher);
616        builder.write(file.as_slice());
617        let tree = builder.finish();
618
619        let descriptor = FsVerityDescriptorRaw::new(
620            algorithm,
621            BLOCK_SIZE as u64,
622            file.len() as u64,
623            tree.root(),
624            salt.as_slice(),
625        )
626        .expect("Creating raw descriptor");
627
628        descriptor
629            .write_to_slice(&mut buf.as_mut_slice()[descriptor_offset..])
630            .expect("Writing descriptor");
631        // FsVerity doesn't actually write out the leaves if there is one or fewer blocks.
632        if file_blocks > 1 {
633            let leaf_bytes = tree.leaf_hashes();
634            buf.as_mut_slice()[leaf_offset..(leaf_offset + (file_blocks * hash_size))]
635                .copy_from_slice(leaf_bytes);
636        }
637
638        let descriptor2 =
639            FsVerityDescriptor::new(buf.as_slice(), BLOCK_SIZE).expect("Parsing decsriptor");
640        assert_eq!(descriptor2.root_digest(), tree.root());
641
642        let mut verifier_builder = MerkleTreeBuilder::<D>::new(descriptor2.hasher());
643        let leaves = descriptor2.leaf_digests().expect("Finding leaf digests");
644        for leaf in leaves.chunks_exact(hash_size) {
645            let hash = D::read_from_bytes(leaf).unwrap();
646            verifier_builder.push_data_hash(hash);
647        }
648
649        let verifier_tree = verifier_builder.finish();
650        assert_eq!(verifier_tree.root(), tree.root());
651    }
652
653    #[test]
654    fn test_raw_descriptor_failure_cases() {
655        // The base case is valid.
656        let descriptor = FsVerityDescriptorRaw::new(
657            fio::HashAlgorithm::Sha256,
658            BLOCK_SIZE as u64,
659            12,
660            &[0u8; 32],
661            &[0u8; 32],
662        )
663        .expect("Creating valid descriptor");
664        {
665            let mut buf = vec![0u8; 256];
666            descriptor.write_to_slice(buf.as_mut_slice()).expect("Writing out descriptor");
667        }
668
669        // Try with buf too small.
670        {
671            let mut buf = vec![0u8; 200];
672            descriptor.write_to_slice(buf.as_mut_slice()).expect_err("Buffer too small");
673        }
674
675        // Block is too small or not power of two.
676        FsVerityDescriptorRaw::new(fio::HashAlgorithm::Sha256, 256, 12, &[0u8; 32], &[0u8; 32])
677            .expect_err("Bad block size");
678        FsVerityDescriptorRaw::new(
679            fio::HashAlgorithm::Sha256,
680            4097 as u64,
681            12,
682            &[0u8; 32],
683            &[0u8; 32],
684        )
685        .expect_err("Bad block size");
686
687        // Salt is too long.
688        FsVerityDescriptorRaw::new(
689            fio::HashAlgorithm::Sha256,
690            BLOCK_SIZE as u64,
691            12,
692            &[0u8; 32],
693            &[0u8; 33],
694        )
695        .expect_err("Bad salt");
696
697        // Hash length wrong at 33
698        FsVerityDescriptorRaw::new(
699            fio::HashAlgorithm::Sha256,
700            BLOCK_SIZE as u64,
701            12,
702            &[0u8; 33],
703            &[0u8; 32],
704        )
705        .expect_err("Bad hash length");
706        FsVerityDescriptorRaw::new(
707            fio::HashAlgorithm::Sha512,
708            BLOCK_SIZE as u64,
709            12,
710            &[0u8; 33],
711            &[0u8; 32],
712        )
713        .expect_err("Bad hash length");
714    }
715
716    #[test]
717    fn test_descriptor_buf_too_small_for_leaves() {
718        let raw_descriptor = FsVerityDescriptorRaw {
719            version: 1,
720            algorithm: 1,
721            block_size_log2: BLOCK_SIZE.trailing_zeros() as u8,
722            salt_size: 8,
723            _reserved_1: [0u8; 4],
724            file_size: 3000000u64.to_le_bytes(),
725            root_digest: [0u8; 64],
726            salt: [0u8; 32],
727            _reserved_2: [0u8; 144],
728        };
729        let mut buf = vec![0u8; BLOCK_SIZE * 2];
730        raw_descriptor.write_to_slice(&mut buf[BLOCK_SIZE..]).expect("Writing out descriptor");
731        let descriptor = FsVerityDescriptor::new(buf.as_slice(), BLOCK_SIZE).expect("Parsing fine");
732        descriptor.leaf_digests().expect_err("Not enough space for leaves");
733    }
734
735    #[test]
736    fn test_descriptor_from_bytes_validation() {
737        // Base case, success.
738        {
739            let descriptor = FsVerityDescriptorRaw {
740                version: 1,
741                algorithm: 1,
742                block_size_log2: BLOCK_SIZE.trailing_zeros() as u8,
743                salt_size: 8,
744                _reserved_1: [0u8; 4],
745                file_size: 25u64.to_le_bytes(),
746                root_digest: [0u8; 64],
747                salt: [0u8; 32],
748                _reserved_2: [0u8; 144],
749            };
750            let mut buf = vec![0u8; 256];
751            descriptor.write_to_slice(buf.as_mut_slice()).expect("Writing out descriptor");
752            FsVerityDescriptor::new(buf.as_slice(), BLOCK_SIZE).expect("Parsing fine");
753        }
754
755        // Buffer too small to parse.
756        {
757            let buf = vec![0u8; 200];
758            FsVerityDescriptor::new(buf.as_slice(), BLOCK_SIZE).expect_err("Buff too small");
759        }
760
761        // Bad block sizes provided to method
762        {
763            let descriptor = FsVerityDescriptorRaw {
764                version: 1,
765                algorithm: 1,
766                block_size_log2: BLOCK_SIZE.trailing_zeros() as u8,
767                salt_size: 8,
768                _reserved_1: [0u8; 4],
769                file_size: 25u64.to_le_bytes(),
770                root_digest: [0u8; 64],
771                salt: [0u8; 32],
772                _reserved_2: [0u8; 144],
773            };
774            let mut buf = vec![0u8; 256];
775            descriptor.write_to_slice(buf.as_mut_slice()).expect("Writing out descriptor");
776            FsVerityDescriptor::new(buf.as_slice(), 4097).expect_err("Bad provided block size");
777        }
778        {
779            let descriptor = FsVerityDescriptorRaw {
780                version: 1,
781                algorithm: 1,
782                block_size_log2: BLOCK_SIZE.trailing_zeros() as u8,
783                salt_size: 8,
784                _reserved_1: [0u8; 4],
785                file_size: 25u64.to_le_bytes(),
786                root_digest: [0u8; 64],
787                salt: [0u8; 32],
788                _reserved_2: [0u8; 144],
789            };
790            let mut buf = vec![0u8; 256];
791            descriptor.write_to_slice(buf.as_mut_slice()).expect("Writing out descriptor");
792            FsVerityDescriptor::new(buf.as_slice(), 0).expect_err("Bad provided block size");
793        }
794
795        // Bad version
796        {
797            let descriptor = FsVerityDescriptorRaw {
798                version: 2,
799                algorithm: 1,
800                block_size_log2: BLOCK_SIZE.trailing_zeros() as u8,
801                salt_size: 8,
802                _reserved_1: [0u8; 4],
803                file_size: 25u64.to_le_bytes(),
804                root_digest: [0u8; 64],
805                salt: [0u8; 32],
806                _reserved_2: [0u8; 144],
807            };
808            let mut buf = vec![0u8; 256];
809            descriptor.write_to_slice(buf.as_mut_slice()).expect("Writing out descriptor");
810            FsVerityDescriptor::new(buf.as_slice(), BLOCK_SIZE).expect_err("Bad version");
811        }
812
813        // Bad algorithm type.
814        {
815            let descriptor = FsVerityDescriptorRaw {
816                version: 1,
817                algorithm: 3,
818                block_size_log2: BLOCK_SIZE.trailing_zeros() as u8,
819                salt_size: 8,
820                _reserved_1: [0u8; 4],
821                file_size: 25u64.to_le_bytes(),
822                root_digest: [0u8; 64],
823                salt: [0u8; 32],
824                _reserved_2: [0u8; 144],
825            };
826            let mut buf = vec![0u8; 256];
827            descriptor.write_to_slice(buf.as_mut_slice()).expect("Writing out descriptor");
828            FsVerityDescriptor::new(buf.as_slice(), BLOCK_SIZE).expect_err("Bad algorithm");
829        }
830
831        // Bad block size. Too small.
832        {
833            let descriptor = FsVerityDescriptorRaw {
834                version: 1,
835                algorithm: 1,
836                block_size_log2: 9,
837                salt_size: 8,
838                _reserved_1: [0u8; 4],
839                file_size: 25u64.to_le_bytes(),
840                root_digest: [0u8; 64],
841                salt: [0u8; 32],
842                _reserved_2: [0u8; 144],
843            };
844            let mut buf = vec![0u8; 256];
845            descriptor.write_to_slice(buf.as_mut_slice()).expect("Writing out descriptor");
846            FsVerityDescriptor::new(buf.as_slice(), BLOCK_SIZE).expect_err("Bad block size");
847        }
848
849        // Bad block size. Too big.
850        {
851            let descriptor = FsVerityDescriptorRaw {
852                version: 1,
853                algorithm: 1,
854                block_size_log2: 128,
855                salt_size: 8,
856                _reserved_1: [0u8; 4],
857                file_size: 25u64.to_le_bytes(),
858                root_digest: [0u8; 64],
859                salt: [0u8; 32],
860                _reserved_2: [0u8; 144],
861            };
862            let mut buf = vec![0u8; 256];
863            descriptor.write_to_slice(buf.as_mut_slice()).expect("Writing out descriptor");
864            FsVerityDescriptor::new(buf.as_slice(), BLOCK_SIZE).expect_err("Bad block size");
865        }
866
867        // Salt size too big.
868        {
869            let descriptor = FsVerityDescriptorRaw {
870                version: 1,
871                algorithm: 1,
872                block_size_log2: BLOCK_SIZE.trailing_zeros() as u8,
873                salt_size: 40,
874                _reserved_1: [0u8; 4],
875                file_size: 25u64.to_le_bytes(),
876                root_digest: [0u8; 64],
877                salt: [0u8; 32],
878                _reserved_2: [0u8; 144],
879            };
880            let mut buf = vec![0u8; 256];
881            descriptor.write_to_slice(buf.as_mut_slice()).expect("Writing out descriptor");
882            FsVerityDescriptor::new(buf.as_slice(), BLOCK_SIZE).expect_err("Bad salt size");
883        }
884
885        // Block size doesn't match.
886        {
887            let descriptor = FsVerityDescriptorRaw {
888                version: 1,
889                algorithm: 1,
890                block_size_log2: 2048usize.trailing_zeros() as u8,
891                salt_size: 8,
892                _reserved_1: [0u8; 4],
893                file_size: 25u64.to_le_bytes(),
894                root_digest: [0u8; 64],
895                salt: [0u8; 32],
896                _reserved_2: [0u8; 144],
897            };
898            let mut buf = vec![0u8; 256];
899            descriptor.write_to_slice(buf.as_mut_slice()).expect("Writing out descriptor");
900            FsVerityDescriptor::new(buf.as_slice(), BLOCK_SIZE).expect_err("Block size mismatch");
901        }
902    }
903}
fsverity_merkle/util.rs

fsverity_merkle/
util.rs
