blob: fc4e10157d80af0a43798e00abc9a25a8a7ce692 [file] [log] [blame]
Victor Hsiehac4f3f42021-02-26 12:35:58 -08001/*
2 * Copyright (C) 2021 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17//! A module for writing to a file from a trusted world to an untrusted storage.
18//!
19//! Architectural Model:
20//! * Trusted world: the writer, a signing secret, has some memory, but NO persistent storage.
21//! * Untrusted world: persistent storage, assuming untrusted.
22//! * IPC mechanism between trusted and untrusted world
23//!
24//! Use cases:
25//! * In the trusted world, we want to generate a large file, sign it, and share the signature for
26//! a third party to verify the file.
27//! * In the trusted world, we want to read a previously signed file back with signature check
28//! without having to touch the whole file.
29//!
30//! Requirements:
31//! * Communication between trusted and untrusted world is not cheap, and files can be large.
32//! * A file write pattern may not be sequential, neither does read.
33//!
34//! Considering the above, a technique similar to fs-verity is used. fs-verity uses an alternative
35//! hash function, a Merkle tree, to calculate the hash of file content. A file update at any
36//! location will propagate the hash update from the leaf to the root node. Unlike fs-verity, which
37//! assumes static files, to support write operation, we need to allow the file (thus tree) to
38//! update.
39//!
40//! For the trusted world to generate a large file with random write and hash it, the writer needs
41//! to hold some private information and update the Merkle tree during a file write (or even when
42//! the Merkle tree needs to be stashed to the untrusted storage).
43//!
44//! A write to a file must update the root hash. In order for the root hash to update, a tree
45//! walk to update from the write location to the root node is necessary. Importantly, in case when
46//! (part of) the Merkle tree needs to be read from the untrusted storage (e.g. not yet verified in
47//! cache), the original path must be verified by the trusted signature before the update to happen.
48//!
49//! Denial-of-service is a known weakness if the untrusted storage decides to simply remove the
50//! file. But there is nothing we can do in this architecture.
51//!
52//! Rollback attack is another possible attack, but can be addressed with a rollback counter when
53//! possible.
54
55use std::io;
56use std::sync::{Arc, RwLock};
57
Victor Hsieh09e26262021-03-03 16:00:55 -080058use super::builder::MerkleLeaves;
Victor Hsiehac4f3f42021-02-26 12:35:58 -080059use crate::common::{ChunkedSizeIter, CHUNK_SIZE};
60use crate::crypto::{CryptoError, Sha256Hash, Sha256Hasher};
Victor Hsieh09e26262021-03-03 16:00:55 -080061use crate::file::{RandomWrite, ReadOnlyDataByChunk};
Victor Hsiehac4f3f42021-02-26 12:35:58 -080062
63// Implement the conversion from `CryptoError` to `io::Error` just to avoid manual error type
64// mapping below.
65impl From<CryptoError> for io::Error {
66 fn from(error: CryptoError) -> Self {
67 io::Error::new(io::ErrorKind::Other, error)
68 }
69}
70
Victor Hsiehac4f3f42021-02-26 12:35:58 -080071/// VerifiedFileEditor provides an integrity layer to an underlying read-writable file, which may
72/// not be stored in a trusted environment. Only new, empty files are currently supported.
73pub struct VerifiedFileEditor<F: ReadOnlyDataByChunk + RandomWrite> {
74 file: F,
75 merkle_tree: Arc<RwLock<MerkleLeaves>>,
76}
77
78#[allow(dead_code)]
79impl<F: ReadOnlyDataByChunk + RandomWrite> VerifiedFileEditor<F> {
80 /// Wraps a supposedly new file for integrity protection.
81 pub fn new(file: F) -> Self {
82 Self { file, merkle_tree: Arc::new(RwLock::new(MerkleLeaves::new())) }
83 }
84
85 /// Calculates the fs-verity digest of the current file.
86 pub fn calculate_fsverity_digest(&self) -> io::Result<Sha256Hash> {
87 let merkle_tree = self.merkle_tree.read().unwrap();
88 merkle_tree.calculate_fsverity_digest().map_err(|e| io::Error::new(io::ErrorKind::Other, e))
89 }
90
91 fn new_hash_for_incomplete_write(
92 &self,
93 source: &[u8],
94 offset_from_alignment: usize,
95 output_chunk_index: usize,
96 merkle_tree: &mut MerkleLeaves,
97 ) -> io::Result<Sha256Hash> {
98 // The buffer is initialized to 0 purposely. To calculate the block hash, the data is
99 // 0-padded to the block size. When a chunk read is less than a chunk, the initial value
100 // conveniently serves the padding purpose.
101 let mut orig_data = [0u8; CHUNK_SIZE as usize];
102
103 // If previous data exists, read back and verify against the known hash (since the
104 // storage / remote server is not trusted).
105 if merkle_tree.is_index_valid(output_chunk_index) {
106 self.read_chunk(output_chunk_index as u64, &mut orig_data)?;
107
108 // Verify original content
109 let hash = Sha256Hasher::new()?.update(&orig_data)?.finalize()?;
110 if !merkle_tree.is_consistent(output_chunk_index, &hash) {
111 return Err(io::Error::new(io::ErrorKind::InvalidData, "Inconsistent hash"));
112 }
113 }
114
115 Ok(Sha256Hasher::new()?
116 .update(&orig_data[..offset_from_alignment])?
117 .update(source)?
118 .update(&orig_data[offset_from_alignment + source.len()..])?
119 .finalize()?)
120 }
121
122 fn new_chunk_hash(
123 &self,
124 source: &[u8],
125 offset_from_alignment: usize,
126 current_size: usize,
127 output_chunk_index: usize,
128 merkle_tree: &mut MerkleLeaves,
129 ) -> io::Result<Sha256Hash> {
130 if current_size as u64 == CHUNK_SIZE {
131 // Case 1: If the chunk is a complete one, just calculate the hash, regardless of
132 // write location.
133 Ok(Sha256Hasher::new()?.update(source)?.finalize()?)
134 } else {
135 // Case 2: For an incomplete write, calculate the hash based on previous data (if
136 // any).
137 self.new_hash_for_incomplete_write(
138 source,
139 offset_from_alignment,
140 output_chunk_index,
141 merkle_tree,
142 )
143 }
144 }
145}
146
147impl<F: ReadOnlyDataByChunk + RandomWrite> RandomWrite for VerifiedFileEditor<F> {
148 fn write_at(&self, buf: &[u8], offset: u64) -> io::Result<usize> {
149 // Since we don't need to support 32-bit CPU, make an assert to make conversion between
150 // u64 and usize easy below. Otherwise, we need to check `divide_roundup(offset + buf.len()
151 // <= usize::MAX` or handle `TryInto` errors.
152 debug_assert!(usize::MAX as u64 == u64::MAX, "Only 64-bit arch is supported");
153
154 // The write range may not be well-aligned with the chunk boundary. There are various cases
155 // to deal with:
156 // 1. A write of a full 4K chunk.
157 // 2. A write of an incomplete chunk, possibly beyond the original EOF.
158 //
159 // Note that a write beyond EOF can create a hole. But we don't need to handle it here
160 // because holes are zeros, and leaves in MerkleLeaves are hashes of 4096-zeros by
161 // default.
162
163 // Now iterate on the input data, considering the alignment at the destination.
164 for (output_offset, current_size) in
165 ChunkedSizeIter::new(buf.len(), offset, CHUNK_SIZE as usize)
166 {
167 // Lock the tree for the whole write for now. There may be room to improve to increase
168 // throughput.
169 let mut merkle_tree = self.merkle_tree.write().unwrap();
170
171 let offset_in_buf = (output_offset - offset) as usize;
172 let source = &buf[offset_in_buf as usize..offset_in_buf as usize + current_size];
173 let output_chunk_index = (output_offset / CHUNK_SIZE) as usize;
174 let offset_from_alignment = (output_offset % CHUNK_SIZE) as usize;
175
176 let new_hash = match self.new_chunk_hash(
177 source,
178 offset_from_alignment,
179 current_size,
180 output_chunk_index,
181 &mut merkle_tree,
182 ) {
183 Ok(hash) => hash,
184 Err(e) => {
185 // Return early when any error happens before the right. Even if the hash is not
186 // consistent for the current chunk, we can still consider the earlier writes
187 // successful. Note that nothing persistent has been done in this iteration.
188 let written = output_offset - offset;
189 if written > 0 {
190 return Ok(written as usize);
191 }
192 return Err(e);
193 }
194 };
195
196 // A failed, partial write here will make the backing file inconsistent to the (old)
197 // hash. Nothing can be done within this writer, but at least it still maintains the
198 // (original) integrity for the file. To matches what write(2) describes for an error
199 // case (though it's about direct I/O), "Partial data may be written ... should be
200 // considered inconsistent", an error below is propagated.
201 self.file.write_all_at(&source, output_offset)?;
202
203 // Update the hash only after the write succeeds. Note that this only attempts to keep
204 // the tree consistent to what has been written regardless the actual state beyond the
205 // writer.
206 let size_at_least = offset.saturating_add(buf.len() as u64);
207 merkle_tree.update_hash(output_chunk_index, &new_hash, size_at_least);
208 }
209 Ok(buf.len())
210 }
211}
212
213impl<F: ReadOnlyDataByChunk + RandomWrite> ReadOnlyDataByChunk for VerifiedFileEditor<F> {
214 fn read_chunk(&self, chunk_index: u64, buf: &mut [u8]) -> io::Result<usize> {
215 self.file.read_chunk(chunk_index, buf)
216 }
217}
218
219#[cfg(test)]
220mod tests {
221 // Test data below can be generated by:
222 // $ perl -e 'print "\x{00}" x 6000' > foo
223 // $ perl -e 'print "\x{01}" x 5000' >> foo
224 // $ fsverity digest foo
225 use super::*;
226 use anyhow::Result;
227 use std::cell::RefCell;
228 use std::convert::TryInto;
229
Victor Hsieh09e26262021-03-03 16:00:55 -0800230 struct InMemoryEditor {
Victor Hsiehac4f3f42021-02-26 12:35:58 -0800231 data: RefCell<Vec<u8>>,
232 fail_read: bool,
233 }
234
Victor Hsieh09e26262021-03-03 16:00:55 -0800235 impl InMemoryEditor {
236 pub fn new() -> InMemoryEditor {
237 InMemoryEditor { data: RefCell::new(Vec::new()), fail_read: false }
Victor Hsiehac4f3f42021-02-26 12:35:58 -0800238 }
239 }
240
Victor Hsieh09e26262021-03-03 16:00:55 -0800241 impl RandomWrite for InMemoryEditor {
Victor Hsiehac4f3f42021-02-26 12:35:58 -0800242 fn write_at(&self, buf: &[u8], offset: u64) -> io::Result<usize> {
243 let begin: usize =
244 offset.try_into().map_err(|e| io::Error::new(io::ErrorKind::Other, e))?;
245 let end = begin + buf.len();
246 if end > self.data.borrow().len() {
247 self.data.borrow_mut().resize(end, 0);
248 }
249 self.data.borrow_mut().as_mut_slice()[begin..end].copy_from_slice(&buf);
250 Ok(buf.len())
251 }
252 }
253
Victor Hsieh09e26262021-03-03 16:00:55 -0800254 impl ReadOnlyDataByChunk for InMemoryEditor {
Victor Hsiehac4f3f42021-02-26 12:35:58 -0800255 fn read_chunk(&self, chunk_index: u64, buf: &mut [u8]) -> io::Result<usize> {
256 debug_assert!(buf.len() as u64 >= CHUNK_SIZE);
257
258 if self.fail_read {
259 return Err(io::Error::new(io::ErrorKind::Other, "test!"));
260 }
261
262 let borrowed = self.data.borrow();
263 let chunk = &borrowed
264 .chunks(CHUNK_SIZE as usize)
265 .nth(chunk_index as usize)
266 .ok_or_else(|| {
267 io::Error::new(
268 io::ErrorKind::InvalidInput,
269 format!("read_chunk out of bound: index {}", chunk_index),
270 )
271 })?;
272 buf[..chunk.len()].copy_from_slice(&chunk);
273 Ok(chunk.len())
274 }
275 }
276
277 #[test]
278 fn test_writer() -> Result<()> {
Victor Hsieh09e26262021-03-03 16:00:55 -0800279 let writer = InMemoryEditor::new();
Victor Hsiehac4f3f42021-02-26 12:35:58 -0800280 let buf = [1; 4096];
281 assert_eq!(writer.data.borrow().len(), 0);
282
283 assert_eq!(writer.write_at(&buf, 16384)?, 4096);
284 assert_eq!(writer.data.borrow()[16384..16384 + 4096], buf);
285
286 assert_eq!(writer.write_at(&buf, 2048)?, 4096);
287 assert_eq!(writer.data.borrow()[2048..2048 + 4096], buf);
288
289 assert_eq!(writer.data.borrow().len(), 16384 + 4096);
290 Ok(())
291 }
292
293 #[test]
294 fn test_verified_writer_no_write() -> Result<()> {
295 // Verify fs-verity hash without any write.
Victor Hsieh09e26262021-03-03 16:00:55 -0800296 let file = VerifiedFileEditor::new(InMemoryEditor::new());
Victor Hsiehac4f3f42021-02-26 12:35:58 -0800297 assert_eq!(
298 file.calculate_fsverity_digest()?,
299 to_u8_vec("3d248ca542a24fc62d1c43b916eae5016878e2533c88238480b26128a1f1af95")
300 .as_slice()
301 );
302 Ok(())
303 }
304
305 #[test]
306 fn test_verified_writer_from_zero() -> Result<()> {
307 // Verify a write of a full chunk.
Victor Hsieh09e26262021-03-03 16:00:55 -0800308 let file = VerifiedFileEditor::new(InMemoryEditor::new());
Victor Hsiehac4f3f42021-02-26 12:35:58 -0800309 assert_eq!(file.write_at(&[1; 4096], 0)?, 4096);
310 assert_eq!(
311 file.calculate_fsverity_digest()?,
312 to_u8_vec("cd0875ca59c7d37e962c5e8f5acd3770750ac80225e2df652ce5672fd34500af")
313 .as_slice()
314 );
315
316 // Verify a write of across multiple chunks.
Victor Hsieh09e26262021-03-03 16:00:55 -0800317 let file = VerifiedFileEditor::new(InMemoryEditor::new());
Victor Hsiehac4f3f42021-02-26 12:35:58 -0800318 assert_eq!(file.write_at(&[1; 4097], 0)?, 4097);
319 assert_eq!(
320 file.calculate_fsverity_digest()?,
321 to_u8_vec("2901b849fda2d91e3929524561c4a47e77bb64734319759507b2029f18b9cc52")
322 .as_slice()
323 );
324
325 // Verify another write of across multiple chunks.
Victor Hsieh09e26262021-03-03 16:00:55 -0800326 let file = VerifiedFileEditor::new(InMemoryEditor::new());
Victor Hsiehac4f3f42021-02-26 12:35:58 -0800327 assert_eq!(file.write_at(&[1; 10000], 0)?, 10000);
328 assert_eq!(
329 file.calculate_fsverity_digest()?,
330 to_u8_vec("7545409b556071554d18973a29b96409588c7cda4edd00d5586b27a11e1a523b")
331 .as_slice()
332 );
333 Ok(())
334 }
335
336 #[test]
337 fn test_verified_writer_unaligned() -> Result<()> {
338 // Verify small, unaligned write beyond EOF.
Victor Hsieh09e26262021-03-03 16:00:55 -0800339 let file = VerifiedFileEditor::new(InMemoryEditor::new());
Victor Hsiehac4f3f42021-02-26 12:35:58 -0800340 assert_eq!(file.write_at(&[1; 5], 3)?, 5);
341 assert_eq!(
342 file.calculate_fsverity_digest()?,
343 to_u8_vec("a23fc5130d3d7b3323fc4b4a5e79d5d3e9ddf3a3f5872639e867713512c6702f")
344 .as_slice()
345 );
346
347 // Verify bigger, unaligned write beyond EOF.
Victor Hsieh09e26262021-03-03 16:00:55 -0800348 let file = VerifiedFileEditor::new(InMemoryEditor::new());
Victor Hsiehac4f3f42021-02-26 12:35:58 -0800349 assert_eq!(file.write_at(&[1; 6000], 4000)?, 6000);
350 assert_eq!(
351 file.calculate_fsverity_digest()?,
352 to_u8_vec("d16d4c1c186d757e646f76208b21254f50d7f07ea07b1505ff48b2a6f603f989")
353 .as_slice()
354 );
355 Ok(())
356 }
357
358 #[test]
359 fn test_verified_writer_with_hole() -> Result<()> {
360 // Verify an aligned write beyond EOF with holes.
Victor Hsieh09e26262021-03-03 16:00:55 -0800361 let file = VerifiedFileEditor::new(InMemoryEditor::new());
Victor Hsiehac4f3f42021-02-26 12:35:58 -0800362 assert_eq!(file.write_at(&[1; 4096], 4096)?, 4096);
363 assert_eq!(
364 file.calculate_fsverity_digest()?,
365 to_u8_vec("4df2aefd8c2a9101d1d8770dca3ede418232eabce766bb8e020395eae2e97103")
366 .as_slice()
367 );
368
369 // Verify an unaligned write beyond EOF with holes.
Victor Hsieh09e26262021-03-03 16:00:55 -0800370 let file = VerifiedFileEditor::new(InMemoryEditor::new());
Victor Hsiehac4f3f42021-02-26 12:35:58 -0800371 assert_eq!(file.write_at(&[1; 5000], 6000)?, 5000);
372 assert_eq!(
373 file.calculate_fsverity_digest()?,
374 to_u8_vec("47d5da26f6934484e260630a69eb2eebb21b48f69bc8fbf8486d1694b7dba94f")
375 .as_slice()
376 );
377
378 // Just another example with a small write.
Victor Hsieh09e26262021-03-03 16:00:55 -0800379 let file = VerifiedFileEditor::new(InMemoryEditor::new());
Victor Hsiehac4f3f42021-02-26 12:35:58 -0800380 assert_eq!(file.write_at(&[1; 5], 16381)?, 5);
381 assert_eq!(
382 file.calculate_fsverity_digest()?,
383 to_u8_vec("8bd118821fb4aff26bb4b51d485cc481a093c68131b7f4f112e9546198449752")
384 .as_slice()
385 );
386 Ok(())
387 }
388
389 #[test]
390 fn test_verified_writer_various_writes() -> Result<()> {
Victor Hsieh09e26262021-03-03 16:00:55 -0800391 let file = VerifiedFileEditor::new(InMemoryEditor::new());
Victor Hsiehac4f3f42021-02-26 12:35:58 -0800392 assert_eq!(file.write_at(&[1; 2048], 0)?, 2048);
393 assert_eq!(file.write_at(&[1; 2048], 4096 + 2048)?, 2048);
394 assert_eq!(
395 file.calculate_fsverity_digest()?,
396 to_u8_vec("4c433d8640c888b629dc673d318cbb8d93b1eebcc784d9353e07f09f0dcfe707")
397 .as_slice()
398 );
399 assert_eq!(file.write_at(&[1; 2048], 2048)?, 2048);
400 assert_eq!(file.write_at(&[1; 2048], 4096)?, 2048);
401 assert_eq!(
402 file.calculate_fsverity_digest()?,
403 to_u8_vec("2a476d58eb80394052a3a783111e1458ac3ecf68a7878183fed86ca0ff47ec0d")
404 .as_slice()
405 );
406 assert_eq!(file.write_at(&[0; 2048], 2048)?, 2048);
407 assert_eq!(file.write_at(&[0; 2048], 4096)?, 2048);
408 assert_eq!(
409 file.calculate_fsverity_digest()?,
410 to_u8_vec("4c433d8640c888b629dc673d318cbb8d93b1eebcc784d9353e07f09f0dcfe707")
411 .as_slice()
412 );
413 assert_eq!(file.write_at(&[1; 4096], 2048)?, 4096);
414 assert_eq!(
415 file.calculate_fsverity_digest()?,
416 to_u8_vec("2a476d58eb80394052a3a783111e1458ac3ecf68a7878183fed86ca0ff47ec0d")
417 .as_slice()
418 );
419 assert_eq!(file.write_at(&[1; 2048], 8192)?, 2048);
420 assert_eq!(file.write_at(&[1; 2048], 8192 + 2048)?, 2048);
421 assert_eq!(
422 file.calculate_fsverity_digest()?,
423 to_u8_vec("23cbac08371e6ee838ebcc7ae6512b939d2226e802337be7b383c3e046047d24")
424 .as_slice()
425 );
426 Ok(())
427 }
428
429 #[test]
430 fn test_verified_writer_inconsistent_read() -> Result<()> {
Victor Hsieh09e26262021-03-03 16:00:55 -0800431 let file = VerifiedFileEditor::new(InMemoryEditor::new());
Victor Hsiehac4f3f42021-02-26 12:35:58 -0800432 assert_eq!(file.write_at(&[1; 8192], 0)?, 8192);
433
434 // Replace the expected hash of the first/0-th chunk. An incomplete write will fail when it
435 // detects the inconsistent read.
436 {
437 let mut merkle_tree = file.merkle_tree.write().unwrap();
438 let overriding_hash = [42; Sha256Hasher::HASH_SIZE];
439 merkle_tree.update_hash(0, &overriding_hash, 8192);
440 }
441 assert!(file.write_at(&[1; 1], 2048).is_err());
442
443 // A write of full chunk can still succeed. Also fixed the inconsistency.
444 assert_eq!(file.write_at(&[1; 4096], 4096)?, 4096);
445
446 // Replace the expected hash of the second/1-th chunk. A write range from previous chunk can
447 // still succeed, but returns early due to an inconsistent read but still successfully. A
448 // resumed write will fail since no bytes can be written due to the same inconsistency.
449 {
450 let mut merkle_tree = file.merkle_tree.write().unwrap();
451 let overriding_hash = [42; Sha256Hasher::HASH_SIZE];
452 merkle_tree.update_hash(1, &overriding_hash, 8192);
453 }
454 assert_eq!(file.write_at(&[10; 8000], 0)?, 4096);
455 assert!(file.write_at(&[10; 8000 - 4096], 4096).is_err());
456 Ok(())
457 }
458
459 #[test]
460 fn test_verified_writer_failed_read_back() -> Result<()> {
Victor Hsieh09e26262021-03-03 16:00:55 -0800461 let mut writer = InMemoryEditor::new();
Victor Hsiehac4f3f42021-02-26 12:35:58 -0800462 writer.fail_read = true;
463 let file = VerifiedFileEditor::new(writer);
464 assert_eq!(file.write_at(&[1; 8192], 0)?, 8192);
465
466 // When a read back is needed, a read failure will fail to write.
467 assert!(file.write_at(&[1; 1], 2048).is_err());
468 Ok(())
469 }
470
471 fn to_u8_vec(hex_str: &str) -> Vec<u8> {
472 assert!(hex_str.len() % 2 == 0);
473 (0..hex_str.len())
474 .step_by(2)
475 .map(|i| u8::from_str_radix(&hex_str[i..i + 2], 16).unwrap())
476 .collect()
477 }
478}