composefs/fsverity/
digest.rs

1//! Userspace fs-verity digest computation.
2//!
3//! This module implements the fs-verity Merkle tree algorithm in userspace,
4//! allowing computation of fs-verity digests without kernel support.
5
6use core::{cmp::min, mem::size_of};
7
8use sha2::Digest;
9
10use super::FsVerityHashValue;
11
12#[derive(Debug)]
13struct FsVerityLayer<H: FsVerityHashValue, const LG_BLKSZ: u8 = 12> {
14    context: H::Digest,
15    remaining: usize,
16}
17
18impl<H: FsVerityHashValue, const LG_BLKSZ: u8> FsVerityLayer<H, LG_BLKSZ> {
19    fn new() -> Self {
20        Self {
21            context: H::Digest::new(),
22            remaining: 1 << LG_BLKSZ,
23        }
24    }
25
26    fn add_data(&mut self, data: &[u8]) {
27        self.context.update(data);
28        self.remaining -= data.len();
29    }
30
31    fn complete(&mut self) -> H {
32        self.context.update([0].repeat(self.remaining));
33        self.remaining = 1 << LG_BLKSZ;
34        self.context.finalize_reset().into()
35    }
36}
37
38#[derive(Debug)]
39pub(super) struct FsVerityHasher<H: FsVerityHashValue, const LG_BLKSZ: u8 = 12> {
40    layers: Vec<FsVerityLayer<H, LG_BLKSZ>>,
41    value: Option<H>,
42    n_bytes: u64,
43}
44
45impl<H: FsVerityHashValue, const LG_BLKSZ: u8> FsVerityHasher<H, LG_BLKSZ> {
46    pub(super) fn hash(buffer: &[u8]) -> H {
47        let mut hasher = Self::new();
48
49        let mut start = 0;
50        while start < buffer.len() {
51            let end = min(start + (1 << LG_BLKSZ), buffer.len());
52            hasher.add_data(&buffer[start..end]);
53            start = end;
54        }
55
56        hasher.digest()
57    }
58
59    fn new() -> Self {
60        Self {
61            layers: vec![],
62            value: None,
63            n_bytes: 0,
64        }
65    }
66
67    fn add_data(&mut self, data: &[u8]) {
68        if let Some(value) = self.value.take() {
69            // We had a complete value, but now we're adding new data.
70            // This means that we need to add a new hash layer...
71            let mut new_layer = FsVerityLayer::new();
72            new_layer.add_data(value.as_bytes());
73            self.layers.push(new_layer);
74        }
75
76        // Get the value of this block
77        let mut context = FsVerityLayer::<H, LG_BLKSZ>::new();
78        context.add_data(data);
79        let mut value = context.complete();
80        self.n_bytes += data.len() as u64;
81
82        for layer in self.layers.iter_mut() {
83            // We have a layer we need to hash this value into
84            layer.add_data(value.as_bytes());
85            if layer.remaining != 0 {
86                return;
87            }
88            // ...but now this layer itself is now complete, so get the value of *it*.
89            value = layer.complete();
90        }
91
92        // If we made it this far, we completed the last layer and have a value.  Store it.
93        self.value = Some(value);
94    }
95
96    fn root_hash(&mut self) -> H {
97        if let Some(value) = &self.value {
98            value.clone()
99        } else {
100            let mut value = H::EMPTY;
101
102            for layer in self.layers.iter_mut() {
103                // We have a layer we need to hash this value into
104                if value != H::EMPTY {
105                    layer.add_data(value.as_bytes());
106                }
107                if layer.remaining != (1 << LG_BLKSZ) {
108                    // ...but now this layer itself is complete, so get the value of *it*.
109                    value = layer.complete();
110                } else {
111                    value = H::EMPTY;
112                }
113            }
114
115            self.value = Some(value.clone());
116
117            value
118        }
119    }
120
121    fn digest(&mut self) -> H {
122        /*
123        let mut root_hash = [0u8; 64];
124        let result = self.root_hash();
125        root_hash[..result.as_ref().len()].copy_from_slice(result.as_ref());
126
127        let descriptor = FsVerityDescriptor {
128            version: 1,
129            hash_algorithm: H::ALGORITHM,
130            log_blocksize: LG_BLKSZ,
131            salt_size: 0,
132            reserved_0x04: U32::new(0),
133            data_size: U64::new(self.n_bytes),
134            root_hash,
135            salt: [0; 32],
136            reserved: [0; 144],
137        };
138
139        let mut context = H::Digest::new();
140        context.update(descriptor.as_bytes());
141        context.finalize().into()
142            */
143
144        let mut context = H::Digest::new();
145        context.update(1u8.to_le_bytes()); /* version */
146        context.update(H::ALGORITHM.to_le_bytes()); /* hash_algorithm */
147        context.update(LG_BLKSZ.to_le_bytes()); /* log_blocksize */
148        context.update(0u8.to_le_bytes()); /* salt_size */
149        context.update([0; 4]); /* reserved */
150        context.update(self.n_bytes.to_le_bytes());
151        context.update(self.root_hash().as_bytes());
152        context.update([0].repeat(64 - size_of::<H>()));
153        context.update([0; 32]); /* salt */
154        context.update([0; 144]); /* reserved */
155        context.finalize().into()
156    }
157}
158
159#[cfg(test)]
160mod tests {
161    use similar_asserts::assert_eq;
162
163    use crate::fsverity::{Sha256HashValue, Sha512HashValue};
164
165    use super::*;
166
167    #[test]
168    fn test_digest() {
169        assert_eq!(
170            FsVerityHasher::<Sha256HashValue, 12>::hash(b"hello world").to_hex(),
171            "1e2eaa4202d750a41174ee454970b92c1bc2f925b1e35076d8c7d5f56362ba64"
172        );
173
174        assert_eq!(
175            FsVerityHasher::<Sha512HashValue, 12>::hash(b"hello world").to_hex(),
176            "18430270729d162d4e469daca123ae61893db4b0583d8f7081e3bf4f92b88ba514e7982f10733fb6aa895195c5ae8fd2eb2c47a8be05513ce5a0c51a6f570409"
177        );
178    }
179}
composefs/fsverity/digest.rs

composefs/fsverity/
digest.rs
