Re: [Lsf-pc] [LSF/MM TOPIC] fs-verity: file system-level integrity protection

[James Bottomley <James.Bottomley@HansenPartnership.com>]

[-- Attachment #1: Type: text/plain, Size: 3555 bytes --]

On Thu, 2018-02-01 at 16:43 -0700, Andreas Dilger wrote:
> On Feb 1, 2018, at 4:04 PM, Dave Chinner <david@fromorbit.com> wrote:
> > 
> > 
> > On Wed, Jan 31, 2018 at 07:03:16PM -0500, Theodore Ts'o wrote:
> > > 
> > > On Wed, Jan 31, 2018 at 12:41:13PM -0800, James Bottomley wrote:
> > > > 
> > > > > 
> > > > > Like fscrypto, where most of the code is in fs/crypto, most
> > > > > of the fs-verity will be in fs/verity.  There will be minimal
> > > > > hooks in a particular file system, so if another file system
> > > > > wants to play, then can do so relatively easily.
> > > > 
> > > > OK, sounds good ... I notice, now I look, that fscrypt uses
> > > > xattrs (albeit hidden under the covers of get/set_context),
> > > > will dm-verity use the same trick or do people really need
> > > > space in the inode?
> > > 
> > > I assume you mean fs-verity above, and no, we aren't going to use
> > > xattrs because the Merkle tree won't fit in the xattr.  So the
> > > plan was to put the fs-verity header, the PKCS7 signature, and
> > > the Merkle tree after i_size (rounded to a blocksize
> > > boundary).  Remember, the fs-verity case we only worry about the
> > > read-ony case.
> > 
> > I think putting valid data beyond EOF is going to be problematic
> > for many filesystems. Getting things like truncate right are hard
> > enough without having to special case a bunch of new functionality
> > that specifically allows IO access beyond EOF. Indeed, how does
> > "truncate isize but leave special data behind" work and what's the
> > userspace API to drive it? And how does it interact with all the
> > page cache code that checks for page->index beyond EOF to detect a
> > truncated page that should not be accessed?
> > 
> > There's also further complications for filesystems like XFS e.g.
> > how do we tell the difference between valid data beyond EOF and
> > speculative allocation (done by delalloc) beyond EOF that contains
> > no data and can be removed if it is not written to in a short
> > while?
> > 
> > This just seems like a horrible can of worms to me and is not
> > something we should be building generic infrastructure around.
> > 
> > Just how big do these merkle trees get, anyway?
> 
> The Merkle tree will have one checksum per "leaf block" of the
> filesystem (though I'd recommend to use a fixed-size checksum leaf
> block like 4KB so that userspace doesn't need to care about the
> actual filesystem blocksize on disk).  After that, there is a tree of
> checksums from the leaf blocks up to the root.  If there was a weak
> checksum like CRC32 (4 bytes/leaf) then the tree size would be
> somewhat over 0.1% of the file size.  If the tree has a strong
> checksum like SHA256 (32 bytes/leaf) then the overhead is over 0.8%.

Actually, based on what Ted has already said about his use case, I
don't believe we need a binary merkle tree.  The binary tree itself is
only useful if you're doing partial hash verifications on random chunks
as you download, like in p2p.  In this use case we only verify the leaf
nodes on read and the signature is only verified at open, so it sounds
like all we actually need is the leaf chunks and a signature over the
hash of all of them, in fact a simple hash list.  That also protects us
from having to worry about pre-image attacks which are a known problem
of binary merkle trees.

Of course, the leaf nodes are sill about 50% of the binary tree size,
so I've only made a small space improvement.

James

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 228 bytes --]