blob: 81ccd53984418f9258a70dfc760a672e63989511 [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 Hsiehd0bb5d32021-03-19 12:48:03 -070061use crate::file::{ChunkBuffer, RandomWrite, ReadByChunk};
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.
Victor Hsiehd0bb5d32021-03-19 12:48:03 -070073pub struct VerifiedFileEditor<F: ReadByChunk + RandomWrite> {
Victor Hsiehac4f3f42021-02-26 12:35:58 -080074 file: F,
75 merkle_tree: Arc<RwLock<MerkleLeaves>>,
76}
77
Victor Hsiehd0bb5d32021-03-19 12:48:03 -070078impl<F: ReadByChunk + RandomWrite> VerifiedFileEditor<F> {
Victor Hsiehac4f3f42021-02-26 12:35:58 -080079 /// Wraps a supposedly new file for integrity protection.
80 pub fn new(file: F) -> Self {
81 Self { file, merkle_tree: Arc::new(RwLock::new(MerkleLeaves::new())) }
82 }
83
84 /// Calculates the fs-verity digest of the current file.
Victor Hsieh6a47e7f2021-03-03 15:53:49 -080085 #[allow(dead_code)]
Victor Hsiehac4f3f42021-02-26 12:35:58 -080086 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 }
Victor Hsieh6a47e7f2021-03-03 15:53:49 -0800145
146 pub fn size(&self) -> u64 {
147 self.merkle_tree.read().unwrap().file_size()
148 }
Victor Hsiehac4f3f42021-02-26 12:35:58 -0800149}
150
Victor Hsiehd0bb5d32021-03-19 12:48:03 -0700151impl<F: ReadByChunk + RandomWrite> RandomWrite for VerifiedFileEditor<F> {
Victor Hsiehac4f3f42021-02-26 12:35:58 -0800152 fn write_at(&self, buf: &[u8], offset: u64) -> io::Result<usize> {
153 // Since we don't need to support 32-bit CPU, make an assert to make conversion between
154 // u64 and usize easy below. Otherwise, we need to check `divide_roundup(offset + buf.len()
155 // <= usize::MAX` or handle `TryInto` errors.
156 debug_assert!(usize::MAX as u64 == u64::MAX, "Only 64-bit arch is supported");
157
158 // The write range may not be well-aligned with the chunk boundary. There are various cases
159 // to deal with:
160 // 1. A write of a full 4K chunk.
161 // 2. A write of an incomplete chunk, possibly beyond the original EOF.
162 //
163 // Note that a write beyond EOF can create a hole. But we don't need to handle it here
164 // because holes are zeros, and leaves in MerkleLeaves are hashes of 4096-zeros by
165 // default.
166
167 // Now iterate on the input data, considering the alignment at the destination.
168 for (output_offset, current_size) in
169 ChunkedSizeIter::new(buf.len(), offset, CHUNK_SIZE as usize)
170 {
171 // Lock the tree for the whole write for now. There may be room to improve to increase
172 // throughput.
173 let mut merkle_tree = self.merkle_tree.write().unwrap();
174
175 let offset_in_buf = (output_offset - offset) as usize;
176 let source = &buf[offset_in_buf as usize..offset_in_buf as usize + current_size];
177 let output_chunk_index = (output_offset / CHUNK_SIZE) as usize;
178 let offset_from_alignment = (output_offset % CHUNK_SIZE) as usize;
179
180 let new_hash = match self.new_chunk_hash(
181 source,
182 offset_from_alignment,
183 current_size,
184 output_chunk_index,
185 &mut merkle_tree,
186 ) {
187 Ok(hash) => hash,
188 Err(e) => {
189 // Return early when any error happens before the right. Even if the hash is not
190 // consistent for the current chunk, we can still consider the earlier writes
191 // successful. Note that nothing persistent has been done in this iteration.
192 let written = output_offset - offset;
193 if written > 0 {
194 return Ok(written as usize);
195 }
196 return Err(e);
197 }
198 };
199
200 // A failed, partial write here will make the backing file inconsistent to the (old)
201 // hash. Nothing can be done within this writer, but at least it still maintains the
202 // (original) integrity for the file. To matches what write(2) describes for an error
203 // case (though it's about direct I/O), "Partial data may be written ... should be
204 // considered inconsistent", an error below is propagated.
205 self.file.write_all_at(&source, output_offset)?;
206
207 // Update the hash only after the write succeeds. Note that this only attempts to keep
208 // the tree consistent to what has been written regardless the actual state beyond the
209 // writer.
210 let size_at_least = offset.saturating_add(buf.len() as u64);
211 merkle_tree.update_hash(output_chunk_index, &new_hash, size_at_least);
212 }
213 Ok(buf.len())
214 }
215}
216
Victor Hsiehd0bb5d32021-03-19 12:48:03 -0700217impl<F: ReadByChunk + RandomWrite> ReadByChunk for VerifiedFileEditor<F> {
218 fn read_chunk(&self, chunk_index: u64, buf: &mut ChunkBuffer) -> io::Result<usize> {
Victor Hsiehac4f3f42021-02-26 12:35:58 -0800219 self.file.read_chunk(chunk_index, buf)
220 }
221}
222
223#[cfg(test)]
224mod tests {
225 // Test data below can be generated by:
226 // $ perl -e 'print "\x{00}" x 6000' > foo
227 // $ perl -e 'print "\x{01}" x 5000' >> foo
228 // $ fsverity digest foo
229 use super::*;
230 use anyhow::Result;
231 use std::cell::RefCell;
232 use std::convert::TryInto;
233
Victor Hsieh09e26262021-03-03 16:00:55 -0800234 struct InMemoryEditor {
Victor Hsiehac4f3f42021-02-26 12:35:58 -0800235 data: RefCell<Vec<u8>>,
236 fail_read: bool,
237 }
238
Victor Hsieh09e26262021-03-03 16:00:55 -0800239 impl InMemoryEditor {
240 pub fn new() -> InMemoryEditor {
241 InMemoryEditor { data: RefCell::new(Vec::new()), fail_read: false }
Victor Hsiehac4f3f42021-02-26 12:35:58 -0800242 }
243 }
244
Victor Hsieh09e26262021-03-03 16:00:55 -0800245 impl RandomWrite for InMemoryEditor {
Victor Hsiehac4f3f42021-02-26 12:35:58 -0800246 fn write_at(&self, buf: &[u8], offset: u64) -> io::Result<usize> {
247 let begin: usize =
248 offset.try_into().map_err(|e| io::Error::new(io::ErrorKind::Other, e))?;
249 let end = begin + buf.len();
250 if end > self.data.borrow().len() {
251 self.data.borrow_mut().resize(end, 0);
252 }
253 self.data.borrow_mut().as_mut_slice()[begin..end].copy_from_slice(&buf);
254 Ok(buf.len())
255 }
256 }
257
Victor Hsiehd0bb5d32021-03-19 12:48:03 -0700258 impl ReadByChunk for InMemoryEditor {
259 fn read_chunk(&self, chunk_index: u64, buf: &mut ChunkBuffer) -> io::Result<usize> {
Victor Hsiehac4f3f42021-02-26 12:35:58 -0800260 if self.fail_read {
261 return Err(io::Error::new(io::ErrorKind::Other, "test!"));
262 }
263
264 let borrowed = self.data.borrow();
265 let chunk = &borrowed
266 .chunks(CHUNK_SIZE as usize)
267 .nth(chunk_index as usize)
268 .ok_or_else(|| {
269 io::Error::new(
270 io::ErrorKind::InvalidInput,
271 format!("read_chunk out of bound: index {}", chunk_index),
272 )
273 })?;
274 buf[..chunk.len()].copy_from_slice(&chunk);
275 Ok(chunk.len())
276 }
277 }
278
279 #[test]
280 fn test_writer() -> Result<()> {
Victor Hsieh09e26262021-03-03 16:00:55 -0800281 let writer = InMemoryEditor::new();
Victor Hsiehac4f3f42021-02-26 12:35:58 -0800282 let buf = [1; 4096];
283 assert_eq!(writer.data.borrow().len(), 0);
284
285 assert_eq!(writer.write_at(&buf, 16384)?, 4096);
286 assert_eq!(writer.data.borrow()[16384..16384 + 4096], buf);
287
288 assert_eq!(writer.write_at(&buf, 2048)?, 4096);
289 assert_eq!(writer.data.borrow()[2048..2048 + 4096], buf);
290
291 assert_eq!(writer.data.borrow().len(), 16384 + 4096);
292 Ok(())
293 }
294
295 #[test]
296 fn test_verified_writer_no_write() -> Result<()> {
297 // Verify fs-verity hash without any write.
Victor Hsieh09e26262021-03-03 16:00:55 -0800298 let file = VerifiedFileEditor::new(InMemoryEditor::new());
Victor Hsiehac4f3f42021-02-26 12:35:58 -0800299 assert_eq!(
300 file.calculate_fsverity_digest()?,
301 to_u8_vec("3d248ca542a24fc62d1c43b916eae5016878e2533c88238480b26128a1f1af95")
302 .as_slice()
303 );
304 Ok(())
305 }
306
307 #[test]
308 fn test_verified_writer_from_zero() -> Result<()> {
309 // Verify a write of a full chunk.
Victor Hsieh09e26262021-03-03 16:00:55 -0800310 let file = VerifiedFileEditor::new(InMemoryEditor::new());
Victor Hsiehac4f3f42021-02-26 12:35:58 -0800311 assert_eq!(file.write_at(&[1; 4096], 0)?, 4096);
312 assert_eq!(
313 file.calculate_fsverity_digest()?,
314 to_u8_vec("cd0875ca59c7d37e962c5e8f5acd3770750ac80225e2df652ce5672fd34500af")
315 .as_slice()
316 );
317
318 // Verify a write of across multiple chunks.
Victor Hsieh09e26262021-03-03 16:00:55 -0800319 let file = VerifiedFileEditor::new(InMemoryEditor::new());
Victor Hsiehac4f3f42021-02-26 12:35:58 -0800320 assert_eq!(file.write_at(&[1; 4097], 0)?, 4097);
321 assert_eq!(
322 file.calculate_fsverity_digest()?,
323 to_u8_vec("2901b849fda2d91e3929524561c4a47e77bb64734319759507b2029f18b9cc52")
324 .as_slice()
325 );
326
327 // Verify another write of across multiple chunks.
Victor Hsieh09e26262021-03-03 16:00:55 -0800328 let file = VerifiedFileEditor::new(InMemoryEditor::new());
Victor Hsiehac4f3f42021-02-26 12:35:58 -0800329 assert_eq!(file.write_at(&[1; 10000], 0)?, 10000);
330 assert_eq!(
331 file.calculate_fsverity_digest()?,
332 to_u8_vec("7545409b556071554d18973a29b96409588c7cda4edd00d5586b27a11e1a523b")
333 .as_slice()
334 );
335 Ok(())
336 }
337
338 #[test]
339 fn test_verified_writer_unaligned() -> Result<()> {
340 // Verify small, unaligned write beyond EOF.
Victor Hsieh09e26262021-03-03 16:00:55 -0800341 let file = VerifiedFileEditor::new(InMemoryEditor::new());
Victor Hsiehac4f3f42021-02-26 12:35:58 -0800342 assert_eq!(file.write_at(&[1; 5], 3)?, 5);
343 assert_eq!(
344 file.calculate_fsverity_digest()?,
345 to_u8_vec("a23fc5130d3d7b3323fc4b4a5e79d5d3e9ddf3a3f5872639e867713512c6702f")
346 .as_slice()
347 );
348
349 // Verify bigger, unaligned write beyond EOF.
Victor Hsieh09e26262021-03-03 16:00:55 -0800350 let file = VerifiedFileEditor::new(InMemoryEditor::new());
Victor Hsiehac4f3f42021-02-26 12:35:58 -0800351 assert_eq!(file.write_at(&[1; 6000], 4000)?, 6000);
352 assert_eq!(
353 file.calculate_fsverity_digest()?,
354 to_u8_vec("d16d4c1c186d757e646f76208b21254f50d7f07ea07b1505ff48b2a6f603f989")
355 .as_slice()
356 );
357 Ok(())
358 }
359
360 #[test]
361 fn test_verified_writer_with_hole() -> Result<()> {
362 // Verify an aligned write beyond EOF with holes.
Victor Hsieh09e26262021-03-03 16:00:55 -0800363 let file = VerifiedFileEditor::new(InMemoryEditor::new());
Victor Hsiehac4f3f42021-02-26 12:35:58 -0800364 assert_eq!(file.write_at(&[1; 4096], 4096)?, 4096);
365 assert_eq!(
366 file.calculate_fsverity_digest()?,
367 to_u8_vec("4df2aefd8c2a9101d1d8770dca3ede418232eabce766bb8e020395eae2e97103")
368 .as_slice()
369 );
370
371 // Verify an unaligned write beyond EOF with holes.
Victor Hsieh09e26262021-03-03 16:00:55 -0800372 let file = VerifiedFileEditor::new(InMemoryEditor::new());
Victor Hsiehac4f3f42021-02-26 12:35:58 -0800373 assert_eq!(file.write_at(&[1; 5000], 6000)?, 5000);
374 assert_eq!(
375 file.calculate_fsverity_digest()?,
376 to_u8_vec("47d5da26f6934484e260630a69eb2eebb21b48f69bc8fbf8486d1694b7dba94f")
377 .as_slice()
378 );
379
380 // Just another example with a small write.
Victor Hsieh09e26262021-03-03 16:00:55 -0800381 let file = VerifiedFileEditor::new(InMemoryEditor::new());
Victor Hsiehac4f3f42021-02-26 12:35:58 -0800382 assert_eq!(file.write_at(&[1; 5], 16381)?, 5);
383 assert_eq!(
384 file.calculate_fsverity_digest()?,
385 to_u8_vec("8bd118821fb4aff26bb4b51d485cc481a093c68131b7f4f112e9546198449752")
386 .as_slice()
387 );
388 Ok(())
389 }
390
391 #[test]
392 fn test_verified_writer_various_writes() -> Result<()> {
Victor Hsieh09e26262021-03-03 16:00:55 -0800393 let file = VerifiedFileEditor::new(InMemoryEditor::new());
Victor Hsiehac4f3f42021-02-26 12:35:58 -0800394 assert_eq!(file.write_at(&[1; 2048], 0)?, 2048);
395 assert_eq!(file.write_at(&[1; 2048], 4096 + 2048)?, 2048);
396 assert_eq!(
397 file.calculate_fsverity_digest()?,
398 to_u8_vec("4c433d8640c888b629dc673d318cbb8d93b1eebcc784d9353e07f09f0dcfe707")
399 .as_slice()
400 );
401 assert_eq!(file.write_at(&[1; 2048], 2048)?, 2048);
402 assert_eq!(file.write_at(&[1; 2048], 4096)?, 2048);
403 assert_eq!(
404 file.calculate_fsverity_digest()?,
405 to_u8_vec("2a476d58eb80394052a3a783111e1458ac3ecf68a7878183fed86ca0ff47ec0d")
406 .as_slice()
407 );
408 assert_eq!(file.write_at(&[0; 2048], 2048)?, 2048);
409 assert_eq!(file.write_at(&[0; 2048], 4096)?, 2048);
410 assert_eq!(
411 file.calculate_fsverity_digest()?,
412 to_u8_vec("4c433d8640c888b629dc673d318cbb8d93b1eebcc784d9353e07f09f0dcfe707")
413 .as_slice()
414 );
415 assert_eq!(file.write_at(&[1; 4096], 2048)?, 4096);
416 assert_eq!(
417 file.calculate_fsverity_digest()?,
418 to_u8_vec("2a476d58eb80394052a3a783111e1458ac3ecf68a7878183fed86ca0ff47ec0d")
419 .as_slice()
420 );
421 assert_eq!(file.write_at(&[1; 2048], 8192)?, 2048);
422 assert_eq!(file.write_at(&[1; 2048], 8192 + 2048)?, 2048);
423 assert_eq!(
424 file.calculate_fsverity_digest()?,
425 to_u8_vec("23cbac08371e6ee838ebcc7ae6512b939d2226e802337be7b383c3e046047d24")
426 .as_slice()
427 );
428 Ok(())
429 }
430
431 #[test]
432 fn test_verified_writer_inconsistent_read() -> Result<()> {
Victor Hsieh09e26262021-03-03 16:00:55 -0800433 let file = VerifiedFileEditor::new(InMemoryEditor::new());
Victor Hsiehac4f3f42021-02-26 12:35:58 -0800434 assert_eq!(file.write_at(&[1; 8192], 0)?, 8192);
435
436 // Replace the expected hash of the first/0-th chunk. An incomplete write will fail when it
437 // detects the inconsistent read.
438 {
439 let mut merkle_tree = file.merkle_tree.write().unwrap();
440 let overriding_hash = [42; Sha256Hasher::HASH_SIZE];
441 merkle_tree.update_hash(0, &overriding_hash, 8192);
442 }
443 assert!(file.write_at(&[1; 1], 2048).is_err());
444
445 // A write of full chunk can still succeed. Also fixed the inconsistency.
446 assert_eq!(file.write_at(&[1; 4096], 4096)?, 4096);
447
448 // Replace the expected hash of the second/1-th chunk. A write range from previous chunk can
449 // still succeed, but returns early due to an inconsistent read but still successfully. A
450 // resumed write will fail since no bytes can be written due to the same inconsistency.
451 {
452 let mut merkle_tree = file.merkle_tree.write().unwrap();
453 let overriding_hash = [42; Sha256Hasher::HASH_SIZE];
454 merkle_tree.update_hash(1, &overriding_hash, 8192);
455 }
456 assert_eq!(file.write_at(&[10; 8000], 0)?, 4096);
457 assert!(file.write_at(&[10; 8000 - 4096], 4096).is_err());
458 Ok(())
459 }
460
461 #[test]
462 fn test_verified_writer_failed_read_back() -> Result<()> {
Victor Hsieh09e26262021-03-03 16:00:55 -0800463 let mut writer = InMemoryEditor::new();
Victor Hsiehac4f3f42021-02-26 12:35:58 -0800464 writer.fail_read = true;
465 let file = VerifiedFileEditor::new(writer);
466 assert_eq!(file.write_at(&[1; 8192], 0)?, 8192);
467
468 // When a read back is needed, a read failure will fail to write.
469 assert!(file.write_at(&[1; 1], 2048).is_err());
470 Ok(())
471 }
472
473 fn to_u8_vec(hex_str: &str) -> Vec<u8> {
474 assert!(hex_str.len() % 2 == 0);
475 (0..hex_str.len())
476 .step_by(2)
477 .map(|i| u8::from_str_radix(&hex_str[i..i + 2], 16).unwrap())
478 .collect()
479 }
480}