Proposal: Yet another possible fs-verity interface

Proposal: Yet another possible fs-verity interface

[Theodore Y. Ts'o]

After doing a lot of thinking and conferring with the other fs-verity
developers, our current thinking is to simply move the Merkle tree
creation into the kernel.  The upside of doing this is it completely
bypasses all of the complaints about how to transfer the Merkle tree
from userspace to the kernel.  It avoids the complexities of
redesigning the xattr interface, or creating a magic fd which could be
lseek'ed, mmap'ed, read, written, etc. to transfer the Merkle tree,
etc.  Calculating the Merkle tree from a code complexity is going to
be simpler.

The downside of this approach is that it can take a lot of CPU time in
the kernel (it would have to do be done in a kernel thread).  An extra
bit of complication is worrying about how to handle the situation
where if the kernel crashes.  The current thinking is that the ioctl
which enable fs-verity protection on the file will make sure that the
file descriptor is not otherwise opened for writing, and then set the
immutable bit.  Once the Merkle tree is written and finalized, the
fs-verity flag would be set and the immutable bit would be cleared.
The exact mechanisms of crash recovery would be file-system dependent,
and TBD, but would probably rely on the journalling mechanisms
available (e.g., ext4 might rely on the orphan list; f2fs might use
copy-on-write semantics; etc.)

This effectively moves the complexity from the interface (which is
where we seem to be getting hung up) to the implementation, but as
stated above, the actual code to create a Merkle tree is fairly simple.

Hopefully this will cut through the current complaints of the
fs-verity API.

Cheers,

					- Ted

Re: Proposal: Yet another possible fs-verity interface

[James Bottomley]

On Wed, 2019-02-06 at 22:11 -0500, Theodore Y. Ts'o wrote:
> After doing a lot of thinking and conferring with the other fs-verity
> developers, our current thinking is to simply move the Merkle tree
> creation into the kernel.  The upside of doing this is it completely
> bypasses all of the complaints about how to transfer the Merkle tree
> from userspace to the kernel.  It avoids the complexities of
> redesigning the xattr interface, or creating a magic fd which could
> be lseek'ed, mmap'ed, read, written, etc. to transfer the Merkle
> tree, etc.  Calculating the Merkle tree from a code complexity is
> going to be simpler.

I'm happy with this but, as I asked before when something like this was
proposed: can this now become part of IMA?  We simply write an IMA hash
or signature which is a possibly signed top of merkle tree hash (we'll
need a new IMA hash format for this).  The act of writing the xattr
triggers the merkle tree build, how (or indeed whether) the kernel
caches the tree is a fs dependent detail and if the fs can't cache it,
the tree would be reconstructed on first use after a reboot.

> The downside of this approach is that it can take a lot of CPU time
> in the kernel (it would have to do be done in a kernel thread).  An
> extra bit of complication is worrying about how to handle the
> situationwhere if the kernel crashes.

I think this would be up to the fs, but the semantic expectation could
be that the whole thing gets erased and we retry on next use, or the fs
uses a fs dependent mechanism to cache the partially constructed tree
and completes the construction on next use.

>   The current thinking is that the ioctl which enable fs-verity
> protection on the file will make sure that the file descriptor is not
> otherwise opened for writing, and then set the immutable bit. 

If you simply use standard IMA xattrs, you don't need an ioctl ... you
actually now don't need the file to be immutable (although you could
additionally make it so if you wanted): IMA signed files are
effectively immutable because you must update both the contents and the
signature for the file to verify.

James

> Once the Merkle tree is written and finalized,
> the fs-verity flag would be set and the immutable bit would be
> cleared. The exact mechanisms of crash recovery would be file-system
> dependent, and TBD, but would probably rely on the journalling
> mechanisms available (e.g., ext4 might rely on the orphan list; f2fs
> might use copy-on-write semantics; etc.)

I think all that is per-fs semantics that don't need to be specified
for the generic implementation.  I'd be happy with a write to the file
causing a halt to the construction and a reconstruction not starting
until the xattr is updated.

> This effectively moves the complexity from the interface (which is
> where we seem to be getting hung up) to the implementation, but as
> stated above, the actual code to create a Merkle tree is fairly
> simple.
> 
> Hopefully this will cut through the current complaints of the
> fs-verity API.

Re: Proposal: Yet another possible fs-verity interface

[Linus Torvalds]

On Thu, Feb 7, 2019 at 8:10 AM Theodore Y. Ts'o <tytso@mit.edu> wrote:
>
> After doing a lot of thinking and conferring with the other fs-verity
> developers, our current thinking is to simply move the Merkle tree
> creation into the kernel.  The upside of doing this is it completely
> bypasses all of the complaints about how to transfer the Merkle tree
> from userspace to the kernel.

This sounds very sane to me.

In particular, may I suggest that  the interface be made idempotent,
so that you can do the merkle tree operation several times with the
same offset/length arguments, and if the merkle tree has already been
calculated, you just return the resulting root hash directly.

Why? That allows you to "validate" images on filesystems that don't
actually have any long-term storage model for the merkle tree. IOW,
you could do the merkle tree calculation (and verification) every time
at bootup, and on a filesystem that supports the long-term storage of
said merkle data, it's a very cheap operation, but on a filesystem
that doesn't, it would still be *possible* to just calculate the hash
and mark it "finalized" for that boot (or that mount). IOW, it would
work for something like ramfs (but you could also make it work for any
random on-disk filesystem that doesn't support long-term storage).

At that point, the merkle tree thing ends up fairly equivalent to the
IMA "measurement" thing, with the exception that the filesystem *may*
optimize it to be long-term. Hmm?

Now, since I assume that only the merkle tree root hash would be
returned by the "enable merkle tree" operation (so that the code
enabling it can verify that the hash matches the expected value), you
do have to worry about the preimage attack, and make sure that you
can't fool the hashing by making the (bad) file contents themselves be
just the hashes of the (good) blocks. So each level of the merkle tree
needs to have a hash seeding thing or whatever.

              Linus

Re: Proposal: Yet another possible fs-verity interface

[Mimi Zohar]

On Sat, 2019-02-09 at 12:38 -0800, Linus Torvalds wrote:
> On Thu, Feb 7, 2019 at 8:10 AM Theodore Y. Ts'o <tytso@mit.edu> wrote:
> >
> > After doing a lot of thinking and conferring with the other fs-verity
> > developers, our current thinking is to simply move the Merkle tree
> > creation into the kernel.  The upside of doing this is it completely
> > bypasses all of the complaints about how to transfer the Merkle tree
> > from userspace to the kernel.
> 
> This sounds very sane to me.

One of the more interesting use cases for fs-verity, at least to me,
was remote file systems.  Hopefully support for remote file systems
will be included in the new design.

> 
> In particular, may I suggest that  the interface be made idempotent,
> so that you can do the merkle tree operation several times with the
> same offset/length arguments, and if the merkle tree has already been
> calculated, you just return the resulting root hash directly.
> 
> Why? That allows you to "validate" images on filesystems that don't
> actually have any long-term storage model for the merkle tree. IOW,
> you could do the merkle tree calculation (and verification) every time
> at bootup, and on a filesystem that supports the long-term storage of
> said merkle data, it's a very cheap operation, but on a filesystem
> that doesn't, it would still be *possible* to just calculate the hash
> and mark it "finalized" for that boot (or that mount). IOW, it would
> work for something like ramfs (but you could also make it work for any
> random on-disk filesystem that doesn't support long-term storage).

For which files will the Merkle tree be created?  Is this for all
files on a per file system basis?  Or is there some sort of "flag" or
policy?  The original design was based on an ioctl enabling/disabling
a flag.  In this new design, is there still an ioctl?

> 
> At that point, the merkle tree thing ends up fairly equivalent to the
> IMA "measurement" thing, with the exception that the filesystem *may*
> optimize it to be long-term. Hmm?

Wouldn't fs-verity then be similar to IMA-appraisal?  Instead of
verifying the file hash, fs-verity verifies the Merkle tree file root
hash.  The file "measurement", in this case the Merkle tree file root
hash, could be used to extend the TPM and added to a measurement list
or in TCG terminology an event log.

> 
> Now, since I assume that only the merkle tree root hash would be
> returned by the "enable merkle tree" operation (so that the code
> enabling it can verify that the hash matches the expected value), you
> do have to worry about the preimage attack, and make sure that you
> can't fool the hashing by making the (bad) file contents themselves be
> just the hashes of the (good) blocks. So each level of the merkle tree
> needs to have a hash seeding thing or whatever.

Agreed, but wouldn't the Merkle tree file root hash then be system
specific?

The existing file hashes included in the measurement list and the
audit log, are currently being used for remote attestation, forensics
and security analytics.

Mimi

Re: Proposal: Yet another possible fs-verity interface

[Theodore Y. Ts'o]

On Sun, Feb 10, 2019 at 09:06:55AM -0500, Mimi Zohar wrote:
> For which files will the Merkle tree be created?  Is this for all
> files on a per file system basis?  Or is there some sort of "flag" or
> policy?  The original design was based on an ioctl enabling/disabling
> a flag. In this new design, is there still an ioctl?

So for our first use case, it will be used for "privileged APK files"
in Android.  You can think of this as a "setuid binary", effectively.

The Merkle tree hash is digitally signed and provided by the App
Store.  It is *not* calculated on the android device.  So not all
files will have Merkle trees, because storing the android device won't
have access to the signing key.  The enforcement is done by the
userspace code which is loading the privileged APK (the application
loader).  If the APK is privileged, then it must have the Merkle tree,
with the root hash matching the digitally signed hash.  Otherwise, the
application loader will refuse to load it as a privileged "root"
application.

For Android, the policy enforcement is done in userspace (should the
APK be privileged), because userspace loads the APK.  We just let the
kernel take care of verifying the blocks as they are read, and that's
done by fsverity.

If we wanted to do something similar with all setuid executables, that
would have to be enforced via some kind of LSM (e.g., a SELinux
policy).

> The existing file hashes included in the measurement list and the
> audit log, are currently being used for remote attestation, forensics
> and security analytics.

IMA has a very different set primary use cases than fsverity.

As you have pointed out, forcibly dragging the entire file into the
page cache to measure it can sometimes result in performance
improvements.  So there may be system administrators that would prefer
having the entire file measured up front.  On the other hand, if the
binaries/APK's are gargantuan, and not all of the file will be used
(perhaps there are translation files, audio/video assets, etc., that
aren't used most of the time), then only verifying the blocks that are
used will be a better approach.

I've never thought that fsverity should replace IMA or vice versa;
they are optimized for different things.  If it makes sense in some
configuration for IMA to use the fsverity Merkle tree root hash as a
measurement, it's easy enough to set up the hooks so they can be
provided to IMA for its use.  This might be the easist way to
integrate with SELinux, for example.

Regards,
						- Ted

Re: Proposal: Yet another possible fs-verity interface

[Mimi Zohar]

Hi Ted,

The context for my comments/questions was Linus' suggestions, which
you've removed.

On Tue, 2019-02-12 at 00:31 -0500, Theodore Y. Ts'o wrote:
> On Sun, Feb 10, 2019 at 09:06:55AM -0500, Mimi Zohar wrote:
> > For which files will the Merkle tree be created?  Is this for all
> > files on a per file system basis?  Or is there some sort of "flag" or
> > policy?  The original design was based on an ioctl enabling/disabling
> > a flag. In this new design, is there still an ioctl?
> 
> So for our first use case, it will be used for "privileged APK files"
> in Android.  You can think of this as a "setuid binary", effectively.

Yes, I understand that your primary goal hasn't changed.  Linus was
suggesting "the interface be made idempotent" to support "filesystems
that don't actually have any long-term storage model for the merkle
tree.  IOW, you could do the merkle tree calculation (and
verification) every time at bootup".  In that context, I asked whether
the Merkle tree file hash would be for every file on the filesystem or
not, and how to identify those files.

> > The existing file hashes included in the measurement list and the
> > audit log, are currently being used for remote attestation, forensics
> > and security analytics.

Again, the context for this comment was Linus' suggestion "each level
of the merkle tree needs to have a hash seeding thing or whatever."
Up to this point, I had assumed the Merkle tree file root hash could
be used as an identifier, similar to the file hash.  With his
suggestion, it sounds like the Merkle tree file root hash would be
system dependent, making it useless for the above usages.

> 
> IMA has a very different set primary use cases than fsverity.

We need to differentiate between IMA's method of calculating the file
hash from the IMA measurement list.  I totally agree there is a place
for both methods of calculating the file hash.  I am hoping that we
would be able to use the Merkle tree file root hash in the IMA
measurement list.  It makes no sense to have to calculate the file
hash for the measurement list, if you're using fs-verity.

Mimi

Re: Proposal: Yet another possible fs-verity interface

[Theodore Y. Ts'o]

On Tue, Feb 12, 2019 at 08:06:52AM -0500, Mimi Zohar wrote:
> Yes, I understand that your primary goal hasn't changed.  Linus was
> suggesting "the interface be made idempotent" to support "filesystems
> that don't actually have any long-term storage model for the merkle
> tree.  IOW, you could do the merkle tree calculation (and
> verification) every time at bootup".  In that context, I asked whether
> the Merkle tree file hash would be for every file on the filesystem or
> not, and how to identify those files.

I have no idea; *we're* certainly never going to use it in that mode.
Until we have a use case, answering your questions about when the
Merkle tree hash would be calculated, etc. is not something I can do.

If IMA wants to use it in that way, let's talk, and we probably can
drop everyone off the cc line.  But there's a limit to much work the
open source community can expect to extort out of people who are
trying to get a feature upstream.  If it's very closely related, and
it's a small amount of work, that's a no-brainer.  But past a certain
point, it's a completely new feature, and it stops being fair....

> > > The existing file hashes included in the measurement list and the
> > > audit log, are currently being used for remote attestation, forensics
> > > and security analytics.
> 
> Again, the context for this comment was Linus' suggestion "each level
> of the merkle tree needs to have a hash seeding thing or whatever."
> Up to this point, I had assumed the Merkle tree file root hash could
> be used as an identifier, similar to the file hash.  With his
> suggestion, it sounds like the Merkle tree file root hash would be
> system dependent, making it useless for the above usages.

Yeah, I have no idea what Linus was talking about there.  The only
thing that really makes sense is that if you don't have any
file-system place to store a seed, you don't use a seed for the Merkle
tree, and for a given set of bytes, the Merkle root hash is the same.
So it's basically an expensive to calculate crypto checksum, as I said.

If that's helpful to IMA, we need a crisp set of requirements and
expectations of how IMA would use it.  And this includes, as I
mentioned in my other e-mail, questions like how long do we keep the
Merkle tree pinned in memory, how it would be used (I assume it would
be something called from IMA's measurement hook, but maybe you have
other ideas).  Bottom line --- I need *you* to answer the questions
that you posed.  :-)

Once we get the requirements, we can figure out how we can architect
something sane --- but adding this extra feature is going to be a lot
work, make no mistake about it.  One of the other things we will need
to figure out is how to hook into other file systems's readpages
model.  There's no standardization here, since file systems don't even
have to use the page cache!

So my strong preference would be to get the base fs-verity feature in,
and then we can look into how it would be extended for this new,
completely different use case.  And hopefully, the people who would
benefit from this new use case, would be willing to contribute some of
the engineering effort to make it happen?  :-)

					- Ted

Re: [f2fs-dev] Proposal: Yet another possible fs-verity interface

[Eric Biggers]

On Tue, Feb 12, 2019 at 12:24:33PM -0500, Theodore Y. Ts'o wrote:
> 
> > > > The existing file hashes included in the measurement list and the
> > > > audit log, are currently being used for remote attestation, forensics
> > > > and security analytics.
> > 
> > Again, the context for this comment was Linus' suggestion "each level
> > of the merkle tree needs to have a hash seeding thing or whatever."
> > Up to this point, I had assumed the Merkle tree file root hash could
> > be used as an identifier, similar to the file hash.  With his
> > suggestion, it sounds like the Merkle tree file root hash would be
> > system dependent, making it useless for the above usages.
> 
> Yeah, I have no idea what Linus was talking about there.  The only
> thing that really makes sense is that if you don't have any
> file-system place to store a seed, you don't use a seed for the Merkle
> tree, and for a given set of bytes, the Merkle root hash is the same.
> So it's basically an expensive to calculate crypto checksum, as I said.
> 

I think there's confusion due to the use of the phrase "Merkle tree root hash".
Linus's point was:

> Now, since I assume that only the merkle tree root hash would be
> returned by the "enable merkle tree" operation (so that the code
> enabling it can verify that the hash matches the expected value), you
> do have to worry about the preimage attack, and make sure that you
> can't fool the hashing by making the (bad) file contents themselves be
> just the hashes of the (good) blocks. So each level of the merkle tree
> needs to have a hash seeding thing or whatever.

This is already taken into account in the original design.  The file hash
reported by fs-verity is *not* the Merkle tree root hash directly, but rather a
hash of the Merkle tree root hash and additional metadata in the
fsverity_descriptor including the file size in bytes.  This resulting hash is
referred to in the code, documentation, etc. as the "fs-verity file measurement".

Thus you can't fool the hashing in the way that Linus mentioned, because the
file size is included in the hash too.  And I don't expect this part of the
design should change, even if we change the API.

It's been difficult to get people to start saying "fs-verity file measurement"
rather than "Merkle tree root hash", though, so if anyone has a suggestion for a
better name it would be appreciated.  An earlier name was "fs-verity root hash",
but I thought that would too easily be confused with the Merkle tree root hash.

fs-verity does support a salt as well, but it's optional and isn't needed to
prevent preimage attacks, assuming the user chose a strong cryptographic hash
function such as SHA-256 or SHA-512.

- Eric

Re: Proposal: Yet another possible fs-verity interface

[Theodore Y. Ts'o]

On Sat, Feb 09, 2019 at 12:38:05PM -0800, Linus Torvalds wrote:
> 
> In particular, may I suggest that  the interface be made idempotent,
> so that you can do the merkle tree operation several times with the
> same offset/length arguments, and if the merkle tree has already been
> calculated, you just return the resulting root hash directly.

Sure, I was already thinking that rerunning the ioctl should allow us
recover from an interrupted Merkle tree generation.  So I agree about
it being idempotent.

> Why? That allows you to "validate" images on filesystems that don't
> actually have any long-term storage model for the merkle tree. IOW,
> you could do the merkle tree calculation (and verification) every time
> at bootup, and on a filesystem that supports the long-term storage of
> said merkle data, it's a very cheap operation, but on a filesystem
> that doesn't, it would still be *possible* to just calculate the hash
> and mark it "finalized" for that boot (or that mount). IOW, it would
> work for something like ramfs (but you could also make it work for any
> random on-disk filesystem that doesn't support long-term storage).

Well, we *could* do that, but at that point we've just transformed the
Merkle tree to be a very inefficient crypto checksum.  The whole point
of the Merkle tree is that you *don't* have to scan the entire data
file before you open the file (or at boot-time).  Instead, the root
hash of the Merkle tree is digitally signed, and you verify the file
as you use it, block-by-block.  If there are large portions of the
file which are never used (for example, because they contain the
Russian language files, and the phone is being used by a French
speaker), then we don't have to read that portion of the file to
checksum it.

If the file system doesn't have a way to store the Merkle tree, and we
have to recalculate the "Merkle tree has" as a way of validating the
file, it will be *much* faster simply to calculate the SHA-256 of the
file, and then verify that against a digital signature of the expected
crypto checksum.  For a file system that doesn't support the Merkle tree, 

> At that point, the merkle tree thing ends up fairly equivalent to the
> IMA "measurement" thing, with the exception that the filesystem *may*
> optimize it to be long-term. Hmm?

Well, except that it's just a less efficient way of doing IMA
"measurement" (if the file system doesn't support Merkle tree
storage).

So adding that complexity is, in my view, not really worth it, since I
very much doubt anyone would use a slower scheme.  I think the much
better model is that fsverity is for file system where you can store
the Merkle tree (and it's really not that hard for most file systems
to store it); and if you are using a file system which doesn't, use
IMA in good health.

I've talked to Mimi about how we can hook fsverity into the IMA
machinery, so that if you have fsverity protected files, that can be
used for the audit log (for example).  This basically means treating
the Merkle tree hash (which is stored in the fsverity "superblock", so
it can be fetched without pulling the entire file into the page cache)
as a IMA "checksum".

This will have to be a policy matter, since there are security folks
who like the idea that the entire 100 megabyte file must be paged in
to be checksummed *first*, before it is used.  That way, you know that
file is 100% valid before you allow userspace to start using it.  In
the fsverity model, if some portion of the file is corrupted, possibly
maliciously by an adversary, the program might abort in the middle of
being run when the corrupted portion of the file is finally used.
This is a tradeoff; and for people who really care about "how many
seconds before the user touches the facebook app ico, and pixels start
being painted on the screen on a low-end mobile device", they'll take
the fsverity approach and avoid the IMA approach.

So yes --- we can tie into the IMA framework so that if policy allows,
it can be used instead of the IMA measurement.  But I don't think it
makes sense to try to use fsverity without the Merkle tree being
stored in the file system.

Cheers,

					- Ted

Re: Proposal: Yet another possible fs-verity interface

[Mimi Zohar]

> At that point, the merkle tree thing ends up fairly equivalent to
the
> > IMA "measurement" thing, with the exception that the filesystem *may*
> > optimize it to be long-term. Hmm?
> 
> Well, except that it's just a less efficient way of doing IMA
> "measurement" (if the file system doesn't support Merkle tree
> storage).
> 
> So adding that complexity is, in my view, not really worth it, since I
> very much doubt anyone would use a slower scheme.  I think the much
> better model is that fsverity is for file system where you can store
> the Merkle tree (and it's really not that hard for most file systems
> to store it); and if you are using a file system which doesn't, use
> IMA in good health.

Ted, one of the problems with IMA is that the file hash/signature
verification is at file open.  It isn't aware when files are brought
in from cache.  Does fs-verity re-verify blocks as they're restored
from cache?  For some use cases, that might justify the up front cost
associated with building the Merkle tree.

Mimi

Re: Proposal: Yet another possible fs-verity interface

[Theodore Y. Ts'o]

On Tue, Feb 12, 2019 at 09:44:39AM -0500, Mimi Zohar wrote:
> Ted, one of the problems with IMA is that the file hash/signature
> verification is at file open.  It isn't aware when files are brought
> in from cache.  Does fs-verity re-verify blocks as they're restored
> from cache?  For some use cases, that might justify the up front cost
> associated with building the Merkle tree.

fs-verity as designed and implemented today *only* verifies blocks as
they are read from the file system.  The Merkle tree is stored on
disk, and we don't verify all of the pages at open time.  That's the
whole *point* of fs-verity.  So when you say re-verify, that's simply
not correct.

Could we change it so that there is an optional mode where Merkle tree
is kept pinned in memory and recalculated the first time the file is
opened?  I suppose; the overhead is "only" 0.8% of the file size.  But
for big files, it adds up; and if you never use most of the file (say,
it's an unstripped executable with debugging information), you end up
paying twice --- once to calculate the Merkle tree (in CPU and Disk
time wasted), and a second time by pinning the full Merkle tree in
memory.  Also, it leaves open the question of how aggressively we drop
the Merkle tree once the file is closed.  Do we wait until the inode
gets purged from the inode cache?  That might pin the memory for way
too long.  Do we drop the Merkle tree the moment the inode's open
count goes to zero?

If it's not too hard to add, and if we're generating the Merkle tree
in the kernel, it's something we could do, I suppose.  But it's not
something *we're* going to use, so I'm not terribly excited about
wasting effort on work that just bitrots if no one is actually going
to use it in that way.

If you are willing to commit that IMA will use it in that way, and
you're fairly sure IMA users are going to be willing to pay the memory
tax, we can look into adding it, if it's doesn't add too much effort
on our part.  I just want to be clear that this is a "yes, we would
definitely use such a thing", as opposed to, "it might be nice...."

Cheers,

					- Ted