| /* |
| * Copyright (C) 2021 The Android Open Source Project |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| //! A module for writing to a file from a trusted world to an untrusted storage. |
| //! |
| //! Architectural Model: |
| //! * Trusted world: the writer, a signing secret, has some memory, but NO persistent storage. |
| //! * Untrusted world: persistent storage, assuming untrusted. |
| //! * IPC mechanism between trusted and untrusted world |
| //! |
| //! Use cases: |
| //! * In the trusted world, we want to generate a large file, sign it, and share the signature for |
| //! a third party to verify the file. |
| //! * In the trusted world, we want to read a previously signed file back with signature check |
| //! without having to touch the whole file. |
| //! |
| //! Requirements: |
| //! * Communication between trusted and untrusted world is not cheap, and files can be large. |
| //! * A file write pattern may not be sequential, neither does read. |
| //! |
| //! Considering the above, a technique similar to fs-verity is used. fs-verity uses an alternative |
| //! hash function, a Merkle tree, to calculate the hash of file content. A file update at any |
| //! location will propagate the hash update from the leaf to the root node. Unlike fs-verity, which |
| //! assumes static files, to support write operation, we need to allow the file (thus tree) to |
| //! update. |
| //! |
| //! For the trusted world to generate a large file with random write and hash it, the writer needs |
| //! to hold some private information and update the Merkle tree during a file write (or even when |
| //! the Merkle tree needs to be stashed to the untrusted storage). |
| //! |
| //! A write to a file must update the root hash. In order for the root hash to update, a tree |
| //! walk to update from the write location to the root node is necessary. Importantly, in case when |
| //! (part of) the Merkle tree needs to be read from the untrusted storage (e.g. not yet verified in |
| //! cache), the original path must be verified by the trusted signature before the update to happen. |
| //! |
| //! Denial-of-service is a known weakness if the untrusted storage decides to simply remove the |
| //! file. But there is nothing we can do in this architecture. |
| //! |
| //! Rollback attack is another possible attack, but can be addressed with a rollback counter when |
| //! possible. |
| |
| use std::io; |
| use std::sync::{Arc, RwLock}; |
| |
| use super::builder::MerkleLeaves; |
| use crate::common::{ChunkedSizeIter, CHUNK_SIZE}; |
| use crate::crypto::{CryptoError, Sha256Hash, Sha256Hasher}; |
| use crate::file::{RandomWrite, ReadOnlyDataByChunk}; |
| |
| // Implement the conversion from `CryptoError` to `io::Error` just to avoid manual error type |
| // mapping below. |
| impl From<CryptoError> for io::Error { |
| fn from(error: CryptoError) -> Self { |
| io::Error::new(io::ErrorKind::Other, error) |
| } |
| } |
| |
| /// VerifiedFileEditor provides an integrity layer to an underlying read-writable file, which may |
| /// not be stored in a trusted environment. Only new, empty files are currently supported. |
| pub struct VerifiedFileEditor<F: ReadOnlyDataByChunk + RandomWrite> { |
| file: F, |
| merkle_tree: Arc<RwLock<MerkleLeaves>>, |
| } |
| |
| impl<F: ReadOnlyDataByChunk + RandomWrite> VerifiedFileEditor<F> { |
| /// Wraps a supposedly new file for integrity protection. |
| pub fn new(file: F) -> Self { |
| Self { file, merkle_tree: Arc::new(RwLock::new(MerkleLeaves::new())) } |
| } |
| |
| /// Calculates the fs-verity digest of the current file. |
| #[allow(dead_code)] |
| pub fn calculate_fsverity_digest(&self) -> io::Result<Sha256Hash> { |
| let merkle_tree = self.merkle_tree.read().unwrap(); |
| merkle_tree.calculate_fsverity_digest().map_err(|e| io::Error::new(io::ErrorKind::Other, e)) |
| } |
| |
| fn new_hash_for_incomplete_write( |
| &self, |
| source: &[u8], |
| offset_from_alignment: usize, |
| output_chunk_index: usize, |
| merkle_tree: &mut MerkleLeaves, |
| ) -> io::Result<Sha256Hash> { |
| // The buffer is initialized to 0 purposely. To calculate the block hash, the data is |
| // 0-padded to the block size. When a chunk read is less than a chunk, the initial value |
| // conveniently serves the padding purpose. |
| let mut orig_data = [0u8; CHUNK_SIZE as usize]; |
| |
| // If previous data exists, read back and verify against the known hash (since the |
| // storage / remote server is not trusted). |
| if merkle_tree.is_index_valid(output_chunk_index) { |
| self.read_chunk(output_chunk_index as u64, &mut orig_data)?; |
| |
| // Verify original content |
| let hash = Sha256Hasher::new()?.update(&orig_data)?.finalize()?; |
| if !merkle_tree.is_consistent(output_chunk_index, &hash) { |
| return Err(io::Error::new(io::ErrorKind::InvalidData, "Inconsistent hash")); |
| } |
| } |
| |
| Ok(Sha256Hasher::new()? |
| .update(&orig_data[..offset_from_alignment])? |
| .update(source)? |
| .update(&orig_data[offset_from_alignment + source.len()..])? |
| .finalize()?) |
| } |
| |
| fn new_chunk_hash( |
| &self, |
| source: &[u8], |
| offset_from_alignment: usize, |
| current_size: usize, |
| output_chunk_index: usize, |
| merkle_tree: &mut MerkleLeaves, |
| ) -> io::Result<Sha256Hash> { |
| if current_size as u64 == CHUNK_SIZE { |
| // Case 1: If the chunk is a complete one, just calculate the hash, regardless of |
| // write location. |
| Ok(Sha256Hasher::new()?.update(source)?.finalize()?) |
| } else { |
| // Case 2: For an incomplete write, calculate the hash based on previous data (if |
| // any). |
| self.new_hash_for_incomplete_write( |
| source, |
| offset_from_alignment, |
| output_chunk_index, |
| merkle_tree, |
| ) |
| } |
| } |
| |
| pub fn size(&self) -> u64 { |
| self.merkle_tree.read().unwrap().file_size() |
| } |
| } |
| |
| impl<F: ReadOnlyDataByChunk + RandomWrite> RandomWrite for VerifiedFileEditor<F> { |
| fn write_at(&self, buf: &[u8], offset: u64) -> io::Result<usize> { |
| // Since we don't need to support 32-bit CPU, make an assert to make conversion between |
| // u64 and usize easy below. Otherwise, we need to check `divide_roundup(offset + buf.len() |
| // <= usize::MAX` or handle `TryInto` errors. |
| debug_assert!(usize::MAX as u64 == u64::MAX, "Only 64-bit arch is supported"); |
| |
| // The write range may not be well-aligned with the chunk boundary. There are various cases |
| // to deal with: |
| // 1. A write of a full 4K chunk. |
| // 2. A write of an incomplete chunk, possibly beyond the original EOF. |
| // |
| // Note that a write beyond EOF can create a hole. But we don't need to handle it here |
| // because holes are zeros, and leaves in MerkleLeaves are hashes of 4096-zeros by |
| // default. |
| |
| // Now iterate on the input data, considering the alignment at the destination. |
| for (output_offset, current_size) in |
| ChunkedSizeIter::new(buf.len(), offset, CHUNK_SIZE as usize) |
| { |
| // Lock the tree for the whole write for now. There may be room to improve to increase |
| // throughput. |
| let mut merkle_tree = self.merkle_tree.write().unwrap(); |
| |
| let offset_in_buf = (output_offset - offset) as usize; |
| let source = &buf[offset_in_buf as usize..offset_in_buf as usize + current_size]; |
| let output_chunk_index = (output_offset / CHUNK_SIZE) as usize; |
| let offset_from_alignment = (output_offset % CHUNK_SIZE) as usize; |
| |
| let new_hash = match self.new_chunk_hash( |
| source, |
| offset_from_alignment, |
| current_size, |
| output_chunk_index, |
| &mut merkle_tree, |
| ) { |
| Ok(hash) => hash, |
| Err(e) => { |
| // Return early when any error happens before the right. Even if the hash is not |
| // consistent for the current chunk, we can still consider the earlier writes |
| // successful. Note that nothing persistent has been done in this iteration. |
| let written = output_offset - offset; |
| if written > 0 { |
| return Ok(written as usize); |
| } |
| return Err(e); |
| } |
| }; |
| |
| // A failed, partial write here will make the backing file inconsistent to the (old) |
| // hash. Nothing can be done within this writer, but at least it still maintains the |
| // (original) integrity for the file. To matches what write(2) describes for an error |
| // case (though it's about direct I/O), "Partial data may be written ... should be |
| // considered inconsistent", an error below is propagated. |
| self.file.write_all_at(&source, output_offset)?; |
| |
| // Update the hash only after the write succeeds. Note that this only attempts to keep |
| // the tree consistent to what has been written regardless the actual state beyond the |
| // writer. |
| let size_at_least = offset.saturating_add(buf.len() as u64); |
| merkle_tree.update_hash(output_chunk_index, &new_hash, size_at_least); |
| } |
| Ok(buf.len()) |
| } |
| } |
| |
| impl<F: ReadOnlyDataByChunk + RandomWrite> ReadOnlyDataByChunk for VerifiedFileEditor<F> { |
| fn read_chunk(&self, chunk_index: u64, buf: &mut [u8]) -> io::Result<usize> { |
| self.file.read_chunk(chunk_index, buf) |
| } |
| } |
| |
| #[cfg(test)] |
| mod tests { |
| // Test data below can be generated by: |
| // $ perl -e 'print "\x{00}" x 6000' > foo |
| // $ perl -e 'print "\x{01}" x 5000' >> foo |
| // $ fsverity digest foo |
| use super::*; |
| use anyhow::Result; |
| use std::cell::RefCell; |
| use std::convert::TryInto; |
| |
| struct InMemoryEditor { |
| data: RefCell<Vec<u8>>, |
| fail_read: bool, |
| } |
| |
| impl InMemoryEditor { |
| pub fn new() -> InMemoryEditor { |
| InMemoryEditor { data: RefCell::new(Vec::new()), fail_read: false } |
| } |
| } |
| |
| impl RandomWrite for InMemoryEditor { |
| fn write_at(&self, buf: &[u8], offset: u64) -> io::Result<usize> { |
| let begin: usize = |
| offset.try_into().map_err(|e| io::Error::new(io::ErrorKind::Other, e))?; |
| let end = begin + buf.len(); |
| if end > self.data.borrow().len() { |
| self.data.borrow_mut().resize(end, 0); |
| } |
| self.data.borrow_mut().as_mut_slice()[begin..end].copy_from_slice(&buf); |
| Ok(buf.len()) |
| } |
| } |
| |
| impl ReadOnlyDataByChunk for InMemoryEditor { |
| fn read_chunk(&self, chunk_index: u64, buf: &mut [u8]) -> io::Result<usize> { |
| debug_assert!(buf.len() as u64 >= CHUNK_SIZE); |
| |
| if self.fail_read { |
| return Err(io::Error::new(io::ErrorKind::Other, "test!")); |
| } |
| |
| let borrowed = self.data.borrow(); |
| let chunk = &borrowed |
| .chunks(CHUNK_SIZE as usize) |
| .nth(chunk_index as usize) |
| .ok_or_else(|| { |
| io::Error::new( |
| io::ErrorKind::InvalidInput, |
| format!("read_chunk out of bound: index {}", chunk_index), |
| ) |
| })?; |
| buf[..chunk.len()].copy_from_slice(&chunk); |
| Ok(chunk.len()) |
| } |
| } |
| |
| #[test] |
| fn test_writer() -> Result<()> { |
| let writer = InMemoryEditor::new(); |
| let buf = [1; 4096]; |
| assert_eq!(writer.data.borrow().len(), 0); |
| |
| assert_eq!(writer.write_at(&buf, 16384)?, 4096); |
| assert_eq!(writer.data.borrow()[16384..16384 + 4096], buf); |
| |
| assert_eq!(writer.write_at(&buf, 2048)?, 4096); |
| assert_eq!(writer.data.borrow()[2048..2048 + 4096], buf); |
| |
| assert_eq!(writer.data.borrow().len(), 16384 + 4096); |
| Ok(()) |
| } |
| |
| #[test] |
| fn test_verified_writer_no_write() -> Result<()> { |
| // Verify fs-verity hash without any write. |
| let file = VerifiedFileEditor::new(InMemoryEditor::new()); |
| assert_eq!( |
| file.calculate_fsverity_digest()?, |
| to_u8_vec("3d248ca542a24fc62d1c43b916eae5016878e2533c88238480b26128a1f1af95") |
| .as_slice() |
| ); |
| Ok(()) |
| } |
| |
| #[test] |
| fn test_verified_writer_from_zero() -> Result<()> { |
| // Verify a write of a full chunk. |
| let file = VerifiedFileEditor::new(InMemoryEditor::new()); |
| assert_eq!(file.write_at(&[1; 4096], 0)?, 4096); |
| assert_eq!( |
| file.calculate_fsverity_digest()?, |
| to_u8_vec("cd0875ca59c7d37e962c5e8f5acd3770750ac80225e2df652ce5672fd34500af") |
| .as_slice() |
| ); |
| |
| // Verify a write of across multiple chunks. |
| let file = VerifiedFileEditor::new(InMemoryEditor::new()); |
| assert_eq!(file.write_at(&[1; 4097], 0)?, 4097); |
| assert_eq!( |
| file.calculate_fsverity_digest()?, |
| to_u8_vec("2901b849fda2d91e3929524561c4a47e77bb64734319759507b2029f18b9cc52") |
| .as_slice() |
| ); |
| |
| // Verify another write of across multiple chunks. |
| let file = VerifiedFileEditor::new(InMemoryEditor::new()); |
| assert_eq!(file.write_at(&[1; 10000], 0)?, 10000); |
| assert_eq!( |
| file.calculate_fsverity_digest()?, |
| to_u8_vec("7545409b556071554d18973a29b96409588c7cda4edd00d5586b27a11e1a523b") |
| .as_slice() |
| ); |
| Ok(()) |
| } |
| |
| #[test] |
| fn test_verified_writer_unaligned() -> Result<()> { |
| // Verify small, unaligned write beyond EOF. |
| let file = VerifiedFileEditor::new(InMemoryEditor::new()); |
| assert_eq!(file.write_at(&[1; 5], 3)?, 5); |
| assert_eq!( |
| file.calculate_fsverity_digest()?, |
| to_u8_vec("a23fc5130d3d7b3323fc4b4a5e79d5d3e9ddf3a3f5872639e867713512c6702f") |
| .as_slice() |
| ); |
| |
| // Verify bigger, unaligned write beyond EOF. |
| let file = VerifiedFileEditor::new(InMemoryEditor::new()); |
| assert_eq!(file.write_at(&[1; 6000], 4000)?, 6000); |
| assert_eq!( |
| file.calculate_fsverity_digest()?, |
| to_u8_vec("d16d4c1c186d757e646f76208b21254f50d7f07ea07b1505ff48b2a6f603f989") |
| .as_slice() |
| ); |
| Ok(()) |
| } |
| |
| #[test] |
| fn test_verified_writer_with_hole() -> Result<()> { |
| // Verify an aligned write beyond EOF with holes. |
| let file = VerifiedFileEditor::new(InMemoryEditor::new()); |
| assert_eq!(file.write_at(&[1; 4096], 4096)?, 4096); |
| assert_eq!( |
| file.calculate_fsverity_digest()?, |
| to_u8_vec("4df2aefd8c2a9101d1d8770dca3ede418232eabce766bb8e020395eae2e97103") |
| .as_slice() |
| ); |
| |
| // Verify an unaligned write beyond EOF with holes. |
| let file = VerifiedFileEditor::new(InMemoryEditor::new()); |
| assert_eq!(file.write_at(&[1; 5000], 6000)?, 5000); |
| assert_eq!( |
| file.calculate_fsverity_digest()?, |
| to_u8_vec("47d5da26f6934484e260630a69eb2eebb21b48f69bc8fbf8486d1694b7dba94f") |
| .as_slice() |
| ); |
| |
| // Just another example with a small write. |
| let file = VerifiedFileEditor::new(InMemoryEditor::new()); |
| assert_eq!(file.write_at(&[1; 5], 16381)?, 5); |
| assert_eq!( |
| file.calculate_fsverity_digest()?, |
| to_u8_vec("8bd118821fb4aff26bb4b51d485cc481a093c68131b7f4f112e9546198449752") |
| .as_slice() |
| ); |
| Ok(()) |
| } |
| |
| #[test] |
| fn test_verified_writer_various_writes() -> Result<()> { |
| let file = VerifiedFileEditor::new(InMemoryEditor::new()); |
| assert_eq!(file.write_at(&[1; 2048], 0)?, 2048); |
| assert_eq!(file.write_at(&[1; 2048], 4096 + 2048)?, 2048); |
| assert_eq!( |
| file.calculate_fsverity_digest()?, |
| to_u8_vec("4c433d8640c888b629dc673d318cbb8d93b1eebcc784d9353e07f09f0dcfe707") |
| .as_slice() |
| ); |
| assert_eq!(file.write_at(&[1; 2048], 2048)?, 2048); |
| assert_eq!(file.write_at(&[1; 2048], 4096)?, 2048); |
| assert_eq!( |
| file.calculate_fsverity_digest()?, |
| to_u8_vec("2a476d58eb80394052a3a783111e1458ac3ecf68a7878183fed86ca0ff47ec0d") |
| .as_slice() |
| ); |
| assert_eq!(file.write_at(&[0; 2048], 2048)?, 2048); |
| assert_eq!(file.write_at(&[0; 2048], 4096)?, 2048); |
| assert_eq!( |
| file.calculate_fsverity_digest()?, |
| to_u8_vec("4c433d8640c888b629dc673d318cbb8d93b1eebcc784d9353e07f09f0dcfe707") |
| .as_slice() |
| ); |
| assert_eq!(file.write_at(&[1; 4096], 2048)?, 4096); |
| assert_eq!( |
| file.calculate_fsverity_digest()?, |
| to_u8_vec("2a476d58eb80394052a3a783111e1458ac3ecf68a7878183fed86ca0ff47ec0d") |
| .as_slice() |
| ); |
| assert_eq!(file.write_at(&[1; 2048], 8192)?, 2048); |
| assert_eq!(file.write_at(&[1; 2048], 8192 + 2048)?, 2048); |
| assert_eq!( |
| file.calculate_fsverity_digest()?, |
| to_u8_vec("23cbac08371e6ee838ebcc7ae6512b939d2226e802337be7b383c3e046047d24") |
| .as_slice() |
| ); |
| Ok(()) |
| } |
| |
| #[test] |
| fn test_verified_writer_inconsistent_read() -> Result<()> { |
| let file = VerifiedFileEditor::new(InMemoryEditor::new()); |
| assert_eq!(file.write_at(&[1; 8192], 0)?, 8192); |
| |
| // Replace the expected hash of the first/0-th chunk. An incomplete write will fail when it |
| // detects the inconsistent read. |
| { |
| let mut merkle_tree = file.merkle_tree.write().unwrap(); |
| let overriding_hash = [42; Sha256Hasher::HASH_SIZE]; |
| merkle_tree.update_hash(0, &overriding_hash, 8192); |
| } |
| assert!(file.write_at(&[1; 1], 2048).is_err()); |
| |
| // A write of full chunk can still succeed. Also fixed the inconsistency. |
| assert_eq!(file.write_at(&[1; 4096], 4096)?, 4096); |
| |
| // Replace the expected hash of the second/1-th chunk. A write range from previous chunk can |
| // still succeed, but returns early due to an inconsistent read but still successfully. A |
| // resumed write will fail since no bytes can be written due to the same inconsistency. |
| { |
| let mut merkle_tree = file.merkle_tree.write().unwrap(); |
| let overriding_hash = [42; Sha256Hasher::HASH_SIZE]; |
| merkle_tree.update_hash(1, &overriding_hash, 8192); |
| } |
| assert_eq!(file.write_at(&[10; 8000], 0)?, 4096); |
| assert!(file.write_at(&[10; 8000 - 4096], 4096).is_err()); |
| Ok(()) |
| } |
| |
| #[test] |
| fn test_verified_writer_failed_read_back() -> Result<()> { |
| let mut writer = InMemoryEditor::new(); |
| writer.fail_read = true; |
| let file = VerifiedFileEditor::new(writer); |
| assert_eq!(file.write_at(&[1; 8192], 0)?, 8192); |
| |
| // When a read back is needed, a read failure will fail to write. |
| assert!(file.write_at(&[1; 1], 2048).is_err()); |
| Ok(()) |
| } |
| |
| fn to_u8_vec(hex_str: &str) -> Vec<u8> { |
| assert!(hex_str.len() % 2 == 0); |
| (0..hex_str.len()) |
| .step_by(2) |
| .map(|i| u8::from_str_radix(&hex_str[i..i + 2], 16).unwrap()) |
| .collect() |
| } |
| } |