RFC: ideas for a tamper-proof filesystem

[Philipp Marek <philipp@xxxxxxxxxxxxx>]

Hello everyone!

I'd like to share some ideas about various ways to implement a tamper-proof 
filesystem for linux.

I hope to get some opinions whether the statements in this mail are valid or 
indeed sane :-).


######

As far as I can see, there are some ways to protect the data in a filesystem 
against modifications from outside.

Common to them is that some verification data (below written as vd) has to be 
stored.
That could be the IV after block-encryption, a HMAC for unencrypted devices, 
or even a error-correction code for use on buggy media (eg. floppy) (which 
would allow on-the-fly error-correction).


The main problem to solve is that the vd must match the data. If this isn't 
true the block should be rejected, and an operator probably has to be 
alerted. (This is what I mean with atomicity - vd and data must match)



I) defining a new filesystem
----------------------------


Ia) storing the vd in every data block


The idea here is to use the last n bytes of each logical block as vd area, eg. 
storing a hash there.

PRO:
 - The updates of "normal" data and vd are atomic

CON:
 - Slow, if data has to be memcpy()ed for user-space
 - Troubles with mmap
 - New filesystem needed


Ib) vd inline only in special blocks

A subvariant of this is to store vd only in "special" blocks like the 
free/used-bitmap, the inodes, and perhaps the directories; for the filedata 
we could use just 1 direct block address in the inode (with a vd for this 
block), and defining the indirect blocks to contain (block number, vd) * n + 
the vd of the indirect block.
Then for writing data the fs could look for a free block, write the data 
there, and update atomically the block number, the block's vd, and the 
indirect block's vd in one write.

PRO:
 - easier to do (as I), ext2/3 could be modified as ext4
 - not much slower (no memcpy())
 - mmap works

CON:
 - free space in fs needed
 - fragmentation
 - atomicity


II) protecting the block-device-layer, storing the vd outside the data blocks
-----------------------------------------------------------------------------

These things could be done as a part of device-mapper.


IIa) The simple way with header blocks

For a logical block size of LB (eg. 4KB) and a vd size of VD (eg. 16B) we can 
store N=LB/VD (eg. 256) vds in a logical block (the vd-lb).
So we can precede N data blocks with one lb to store the vd.
(Or perhaps N-1, and store the vd of the vd-lb there.)

PRO:
 - works with any fs
 - locality (vd near the data)
 - a one-to-one mapping of data blocks and blocks on media

CON:
 - atomicity not guaranteed


IIb) using a flag while updating

This is like IIa, except that there is a flag in every vd-lb.
Here the idea is to
 1) write the vd-lb with the old vd's, and the flag saying "this is about to 
be modified", with a correct vd.
 2) write the "normal" data
 3) update the vd-lb with the flag cleared, and an updated vd.

If there is a non-matching vd, we allow it if the flag is set.
And we can check that at most one flag is set on a block-device.

PRO:
 - easily implemented
 - atomicity is no problem

CON:
 - doubled writes to the vd-lb (can tire the media, eg. floppy, flash memory)
 - the flag is not aestethically pleasing


IIc) a bit of journaling (sort of)
We define a header block in the block device and a field in every vd-lb.
These fields are filled with a counter, whose value is periodically written to 
the header block.

So a non-matching vd is allowed only if the counter is within a small distance 
from the header counter value.

PRO:
 - easy to do
 - atomicity solved

CON:
 - many writes to the header block


######

I'd suggest going for IIc, but I expect the experts for journaling filesystems 
can give some hints how to improve the idea.

So here's the call for ideas, comments, and suggestions.


- Phil

-
Linux-crypto:  cryptography in and on the Linux system
Archive:       http://mail.nl.linux.org/linux-crypto/