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

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

[Theodore Ts'o]

I'd like to talk about a proposal to implement and upstream something
that we've been calling fs-verity, which is something like dm-verity,
but implemnted on a per-file basis.  It will be implemnted much like
fs/crypto, in that most of the code will be in a generic layer, with
minimal modifications needed in the file system layer.

The merkle tree will be located after file's normal data, and then
after the package manager sets the verity bit, i_size will be updated
so that the fs-verity header and merkle tree will be "hidden" from
userspace and the file will become immutable.

How does this differ from IMA's file integrity?

*) The pages are verified as they are read, so pages are verified as
they are read the storage device; this avoids a large latency hit when
the file is first opened or referenced.

*) The design and code are done by file system developers, so it
doesn't have the locking problems of the IMA code.

The initial use case of this will be for Android, where the latency
concerns of doing the full checksum at file open time is important.

In the future, the fact that a file has been signed using fs-verity,
using a PKCS 11 signature with a key on a trusted keyring (possibly
the same one used for signed kernel modules, or perhaps a separate
keyring) could be used as input into a security policy which requires
this for say, setuid executables, setuid shell scripts, etc.

Most of this feature could also be used with a non-cryptographic
checksum to provide data checksums for read-only files in a general
way for all file systems.  It wouldn't be as flexible as btrfs, but
for files being stored for backup purposes, it should work quite well.

  	       	   	  	       	      - Ted

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

[Chuck Lever]

> On Jan 25, 2018, at 11:11 AM, Theodore Ts'o <tytso@mit.edu> wrote:
> 
> I'd like to talk about a proposal to implement and upstream something
> that we've been calling fs-verity, which is something like dm-verity,
> but implemnted on a per-file basis.  It will be implemnted much like
> fs/crypto, in that most of the code will be in a generic layer, with
> minimal modifications needed in the file system layer.

I’m interested in this topic, specifically how we can support
binary signing of executable code stored in NFS files.


> The merkle tree will be located after file's normal data, and then
> after the package manager sets the verity bit, i_size will be updated
> so that the fs-verity header and merkle tree will be "hidden" from
> userspace and the file will become immutable.

I’m not expert by any means, but this is also different than IMA
in that it avoids the use of a trusted extended attribute. The NFS
protocol has no support for system/trusted xattrs, currently.

However, I suspect each file system might prefer to store the
tree in its own way. And distributed file systems will have the
additional challenge of protecting this metadata as it is in
flight from file server to client.


> How does this differ from IMA's file integrity?
> 
> *) The pages are verified as they are read, so pages are verified as
> they are read the storage device; this avoids a large latency hit when
> the file is first opened or referenced.

This is also interesting for NFS, which typically reads files by
page, rather than by pulling all of a file to the client.


> *) The design and code are done by file system developers, so it
> doesn't have the locking problems of the IMA code.
> 
> The initial use case of this will be for Android, where the latency
> concerns of doing the full checksum at file open time is important.
> 
> In the future, the fact that a file has been signed using fs-verity,
> using a PKCS 11 signature with a key on a trusted keyring (possibly
> the same one used for signed kernel modules, or perhaps a separate
> keyring) could be used as input into a security policy which requires
> this for say, setuid executables, setuid shell scripts, etc.
> 
> Most of this feature could also be used with a non-cryptographic
> checksum to provide data checksums for read-only files in a general
> way for all file systems.  It wouldn't be as flexible as btrfs, but
> for files being stored for backup purposes, it should work quite well.
> 
>                                               - Ted

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

[Theodore Ts'o]

On Thu, Jan 25, 2018 at 01:49:06PM -0800, Chuck Lever wrote:
> > On Jan 25, 2018, at 11:11 AM, Theodore Ts'o <tytso@mit.edu> wrote:
> > 
> > I'd like to talk about a proposal to implement and upstream something
> > that we've been calling fs-verity, which is something like dm-verity,
> > but implemnted on a per-file basis.  It will be implemnted much like
> > fs/crypto, in that most of the code will be in a generic layer, with
> > minimal modifications needed in the file system layer.
> 
> I’m interested in this topic, specifically how we can support
> binary signing of executable code stored in NFS files.

The challenge for NFS is in the current design, the local disk file
system has to have a way to indicate that a particular file is playing
the fs-verity game.  This is the "fsverity bit"; and so either the NFS
server is going to need to store this bit somewhere for you (which
probably means an extension to the NFS protcol, which is probably out
of scope) --- or you need to store a list of files which are assumed
to have fs-verity on the client.

I suppose you *could* have a magic mount option which says that any
file which is executable should be checked to see if it has the
fs-verity information at the end --- but this means relying on in-band
signalling and that is always fraught with potential false positives.

> I’m not expert by any means, but this is also different than IMA
> in that it avoids the use of a trusted extended attribute. The NFS
> protocol has no support for system/trusted xattrs, currently.

Yes, we don't use at trusted extended attribute.

> However, I suspect each file system might prefer to store the
> tree in its own way. And distributed file systems will have the
> additional challenge of protecting this metadata as it is in
> flight from file server to client.

Well, the root of the merkle tree will be signed by a PKCS11 digtial
signature, so the protection is built into fs-verity mechanism.  The
original plan was that the protected file would look like this:

       +------------------+
       | File Data        |
       |    ...           |
       +------------------+ <----- i_size
       | FS Verity header |
       +------------------+
       | PKCS 11 signature|
       +------------------+
       | Merkle tree      |
       |    ...           |
       +------------------+
       | FS Verity header |
       |    (copy)        |
       +------------------+


This would be the same across all file systems, and all of the logic
for supporting this would be in fs/verity.  An ioctl would cause the
local disk file system to set the FS Verity bit, and change i_size to
be located at the end of the file data (the value would be in the FS
Verity header; the FS Verity would begin on the next PAGE_SIZE offset
from the end of the file data).

So all the local disk file system would have to provide is (a) a way
to set and get the Verity bit, and (b) a way to read beyond i_size to
fetch the FS Verity information.

If you want to do this only in the NFS Client, without needing any
special NFS server support, assuming that you know this file is
playing the FS Verity game (e.g., maybe you use the executable bit as
a hint that you should try to find the FS Verity header), the NFS
client can try to read the last PAGE_SIZE block from the disk, and see
if it looks like a valid FS Verity header.  If so, it can then check
to see if the copy located at the beginning of the FS Verity
information matches the one at the end of the file, and then spoof the
reported i_size reported to userspace via stat(2).  All subsequent
processing would be the same as for a local disk file system; NFS
would just provide its own routing for "reading beyond i_size", which
would just involve sending the standard NFS read operation to the server.

So yeah, I think we could make this work.  There might be a few
details, but I think we can make it work.

					- Ted

   	   	 

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

[James Bottomley]

On Thu, 2018-01-25 at 14:11 -0500, Theodore Ts'o wrote:
> I'd like to talk about a proposal to implement and upstream something
> that we've been calling fs-verity, which is something like dm-verity,
> but implemnted on a per-file basis.  It will be implemnted much like
> fs/crypto, in that most of the code will be in a generic layer, with
> minimal modifications needed in the file system layer.

How do you know the file is in this special format?  Would it be a per
filesystem flag (so every file) or selectable per-file by some other
mechanism.  If it's per-file, why not simply use the existing xattr
mechanism?

I'd have a big problem if it's not per-file because most of the cloud
use for IMA is enforcing immutability and tamper proofness of images
and not all files in an image can be immutable, so you only turn on
appraisal for some files.

However, if it is per-file, how do I tell from an offline backup which
files have the trees and which don't?

> The merkle tree will be located after file's normal data, and then
> after the package manager sets the verity bit, i_size will be updated
> so that the fs-verity header and merkle tree will be "hidden" from
> userspace and the file will become immutable.
> 
> How does this differ from IMA's file integrity?
> 
> *) The pages are verified as they are read, so pages are verified as
> they are read the storage device; this avoids a large latency hit
> when the file is first opened or referenced.

The cost of this is presumably one hash per page in the tree, so it
costs quite a bit in terms of space.  Presumably the hash tree is also
dynamically resident meaning a page fault could now also potentially
fault in the hash tree, leading to a lot of sub optimal I/O patterns?

> *) The design and code are done by file system developers, so it
> doesn't have the locking problems of the IMA code.

That's a bit unfair.  My next question was going to be why not just
make this an actual IMA mode (meaning you could choose to have a global
hash or a tree hash).  Does this mean that a-priori you've already
ruled out IMA integration because you don't want to work with the
developers?

> The initial use case of this will be for Android, where the latency
> concerns of doing the full checksum at file open time is important.
> 
> In the future, the fact that a file has been signed using fs-verity,
> using a PKCS 11

PKCS11 is the standard for cryptokeys.  I presume you just mean a
message signing standard like PKCS7 or RFC 2315?

>  signature with a key on a trusted keyring (possibly
> the same one used for signed kernel modules, or perhaps a separate
> keyring) could be used as input into a security policy which requires
> this for say, setuid executables, setuid shell scripts, etc.
> 
> Most of this feature could also be used with a non-cryptographic
> checksum to provide data checksums for read-only files in a general
> way for all file systems.  It wouldn't be as flexible as btrfs, but
> for files being stored for backup purposes, it should work quite
> well.

I assume the "write" part of this is that the file must be deleted and
re-created?

James

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

[Theodore Ts'o]

On Thu, Jan 25, 2018 at 04:47:46PM -0800, James Bottomley wrote:
> 
> How do you know the file is in this special format? �Would it be a per
> filesystem flag (so every file) or selectable per-file by some other
> mechanism. �If it's per-file, why not simply use the existing xattr
> mechanism?

It would be using a per-file flag, just like we do with fscrypt.
Given that we only need a single bit of information, using an xattr
would be a inefficeint.

> > *) The pages are verified as they are read, so pages are verified as
> > they are read the storage device; this avoids a large latency hit
> > when the file is first opened or referenced.
> 
> The cost of this is presumably one hash per page in the tree, so it
> costs quite a bit in terms of space. �Presumably the hash tree is also
> dynamically resident meaning a page fault could now also potentially
> fault in the hash tree, leading to a lot of sub optimal I/O patterns?

This is how dm-verity works, which is used on every single modern
Chrome OS and Android phone, with no complaints.  (It doesn't work
that way on your phone, unless you've upgraded.  :-)

> > *) The design and code are done by file system developers, so it
> > doesn't have the locking problems of the IMA code.
> 
> That's a bit unfair. �My next question was going to be why not just
> make this an actual IMA mode (meaning you could choose to have a global
> hash or a tree hash). �Does this mean that a-priori you've already
> ruled out IMA integration because you don't want to work with the
> developers?

IMA has a lot of complexity, which I would rather not drag in as a
dependency.  Also, having seen some of the ah, "discussions" that
Christoph and Dave Chinner have been having with the IMA folks, I'd
rather not taint this proposal with IMA's reputation.  :-)

I am completely open to an optional integration with IMA, but I would
prefer not to require CONFIG_IMA to be enabled in order to use
fs-verity.

> PKCS11 is the standard for cryptokeys. �I presume you just mean a
> message signing standard like PKCS7 or RFC 2315?

Sorry, I meant PKCS7.  It would be a restricted PKCS7 mode, using a
detached signature.  My plan was to reuse the existing code we already
have written for signed kernel modules.

> > Most of this feature could also be used with a non-cryptographic
> > checksum to provide data checksums for read-only files in a general
> > way for all file systems.��It wouldn't be as flexible as btrfs, but
> > for files being stored for backup purposes, it should work quite
> > well.
> 
> I assume the "write" part of this is that the file must be deleted and
> re-created?

I'm not sure what you mean.  If you have an existing file that you
want to protect using fs-verity, it's a matter of appending the
fs-verity information onto the end of the file, and then setting the
fs-verity flag, at which point all of the fs-verity information
disappears from the perspective of stat(2) and read(2) system calls.
The verity bit can be examined using FS_IOC_GETFLAGS, and more details
about which key was used to sign the file could be examined via some
ioctl interface.

In general, though, it's expected that userspace won't care about such
details.  Any reads that don't verify will return an error, and if the
key used to sign fs-verity information is not trusted by the kernel,
the open will return an error.  So all userspace or a security policy
would need to take of is that file does have the verity bit set.

Cheers,

					- Ted

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

[James Bottomley]

On Thu, 2018-01-25 at 21:30 -0500, Theodore Ts'o wrote:
> On Thu, Jan 25, 2018 at 04:47:46PM -0800, James Bottomley wrote:
> > 
> > 
> > How do you know the file is in this special format?  Would it be a
> > per filesystem flag (so every file) or selectable per-file by some
> > other mechanism.  If it's per-file, why not simply use the existing
> > xattr mechanism?
> 
> It would be using a per-file flag, just like we do with fscrypt.
> Given that we only need a single bit of information, using an xattr
> would be a inefficeint.
> 
> > 
> > > 
> > > *) The pages are verified as they are read, so pages are verified
> > > as they are read the storage device; this avoids a large latency
> > > hit when the file is first opened or referenced.
> > 
> > The cost of this is presumably one hash per page in the tree, so it
> > costs quite a bit in terms of space.  Presumably the hash tree is
> > also dynamically resident meaning a page fault could now also
> > potentially fault in the hash tree, leading to a lot of sub optimal
> > I/O patterns?
> 
> This is how dm-verity works, which is used on every single modern
> Chrome OS and Android phone, with no complaints.  (It doesn't work
> that way on your phone, unless you've upgraded.  :-)

Well ... I'll upgrade when the phones get better ...

> > > *) The design and code are done by file system developers, so it
> > > doesn't have the locking problems of the IMA code.
> > 
> > That's a bit unfair.  My next question was going to be why not just
> > make this an actual IMA mode (meaning you could choose to have a
> > global hash or a tree hash).  Does this mean that a-priori you've
> > already ruled out IMA integration because you don't want to work
> > with the developers?
> 
> IMA has a lot of complexity, which I would rather not drag in as a
> dependency.  Also, having seen some of the ah, "discussions" that
> Christoph and Dave Chinner have been having with the IMA folks, I'd
> rather not taint this proposal with IMA's reputation.  :-)
> 
> I am completely open to an optional integration with IMA, but I would
> prefer not to require CONFIG_IMA to be enabled in order to use
> fs-verity.

Thanks ... just checking.  There's a lot of integration work going on
in IMA and containers at the moment, so I'd like to preserve the
investment.

> > PKCS11 is the standard for cryptokeys.  I presume you just mean a
> > message signing standard like PKCS7 or RFC 2315?
> 
> Sorry, I meant PKCS7.  It would be a restricted PKCS7 mode, using a
> detached signature.  My plan was to reuse the existing code we
> already have written for signed kernel modules.

OK, so presumably the signature would be over the part of the tree at
the end of the file (so the tree is already reduced to a hashable
binary representation) and this is verified upon write, after which the
hash tree is trusted.

> > > Most of this feature could also be used with a non-cryptographic
> > > checksum to provide data checksums for read-only files in a
> > > general way for all file systems.  It wouldn't be as flexible as
> > > btrfs, but for files being stored for backup purposes, it should
> > > work quite well.
> > 
> > I assume the "write" part of this is that the file must be deleted
> > and re-created?
> 
> I'm not sure what you mean.

Currently container images are simple tar files and one of the main
value adds of docker as a tool is the simplicity of the image creation
process.  That process depends on standard tools like tar to create the
image, so I was trying to fit this proposal into that process.

>   If you have an existing file that you
> want to protect using fs-verity, it's a matter of appending the
> fs-verity information onto the end of the file, and then setting the
> fs-verity flag, at which point all of the fs-verity information
> disappears from the perspective of stat(2) and read(2) system calls.
> The verity bit can be examined using FS_IOC_GETFLAGS, and more
> details about which key was used to sign the file could be examined
> via some ioctl interface.

OK, so that worries me a bit more.  I assume we could use this ioctl to
recreate the file by extracting the tree and thence do a conversion to
tar format so that the untarred file has the signed hash, but just
doing a tar of the directory won't work, so docker save is going to
have to be seriously altered to work with this.

> In general, though, it's expected that userspace won't care about
> such details.  Any reads that don't verify will return an error, and
> if the key used to sign fs-verity information is not trusted by the
> kernel, the open will return an error.  So all userspace or a
> security policy would need to take of is that file does have the
> verity bit set.

Right, I get that once the file is created.  What I'm concerned about
is the process for creating and handling images of the filesystem tree.

James

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

[Colin Walters]

On Thu, Jan 25, 2018, at 2:11 PM, Theodore Ts'o wrote:
> I'd like to talk about a proposal to implement and upstream something
> that we've been calling fs-verity, 

I am very excited by this!

> ... read-only files in a general  way for all file systems

Hi, it's me again!  I was summoned by this mention of
read-only files.  You may recall our previous conversation:
https://www.spinics.net/lists/linux-fsdevel/msg75086.html
(I also cleverly tried to work it in to a tangentially related DAX
 discussion in https://marc.info/?l=linux-fsdevel&m=150152316817001&w=2 )

So given this proposal will require read-only files, can we do
the interface bikeshedding soon around what the userspace API
will look like, and have it be orthogonal to (but a prerequisite for) fs-verity?

My thought is that it's some sort of fcntl on O_TMPFILE fds, and
the link() seals it.  Also, I really hope it'll be possible to make
hardlinks to "read-only files", as that's how
https://github.com/ostreedev/ostree
works.  

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

[Theodore Ts'o]

On Thu, Jan 25, 2018 at 08:50:35PM -0800, James Bottomley wrote:
> > Sorry, I meant PKCS7.��It would be a restricted PKCS7 mode, using a
> > detached signature.��My plan was to reuse the existing code we
> > already have written for signed kernel modules.
> 
> OK, so presumably the signature would be over the part of the tree at
> the end of the file (so the tree is already reduced to a hashable
> binary representation) and this is verified upon write, after which the
> hash tree is trusted.

The signature would cover the fs-verity header including the "root
hash" of the merkle tree (e.g., the hash of the first block of the
merkle tree), yes.

> 
> Currently container images are simple tar files and one of the main
> value adds of docker as a tool is the simplicity of the image creation
> process. �That process depends on standard tools like tar to create the
> image, so I was trying to fit this proposal into that process.

The goal of fs-verity is protect arbitrary files without breaking the
backwards compatibility of those that *read* the file.  So for
example, an APK file is downloaded and verified at the intial download
--- and never verified again.  It is *used* many times after the
initial download (and hence, potentially after an evil maid attack),
and this is done by many different tools, including by code inside the
APK itself.  So it is not feasible to change the tools that read the
APK, which means we can't make any backwards-incompatible changes to
the file itself.

However, changing the tools that *establish* the locally verified copy
is considered completely fair game.  I'll note that this is true no
matter what system you use.  If you are using IMA, after the file is
downloaded, you still have to set the magic "trusted xattr" (which, I
will note, requires root access since it is a trusted root access).
So you have to make at least *some* changes to the code path which
writes the file that you want to be integrity protected.  In the case
of IMA, this includes code that has to run as root.

For fs-verity, there would be a userspace library that would append
the fs-verity information, and then call the fs-verity ioctl to set up
the protection.  Since the data is self-verifying, due to the digital
signature, using setting the verity bit does not require root
privileges.  The kernel will check and make sure it is signed by a
trusted key, of course, but it will simply reject the attempt to
enable fs-verity if the cert is not present on a trusted keyring.

> OK, so that worries me a bit more. �I assume we could use this ioctl to
> recreate the file by extracting the tree and thence do a conversion to
> tar format so that the untarred file has the signed hash, but just
> doing a tar of the directory won't work, so docker save is going to
> have to be seriously altered to work with this.

Docker save was going to have to be altered to use IMA, anyway.  So I
don't see that as being any more difficult.  Whether you have to have
root to set the magic IMA trusted xattr, or you call a userspace
library, there isn't much difference between those two.

							- Ted

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

[Theodore Ts'o]

On Fri, Jan 26, 2018 at 02:58:39AM -0500, Colin Walters wrote:
> Hi, it's me again!  I was summoned by this mention of
> read-only files.  You may recall our previous conversation:
> https://www.spinics.net/lists/linux-fsdevel/msg75086.html
> (I also cleverly tried to work it in to a tangentially related DAX
>  discussion in https://marc.info/?l=linux-fsdevel&m=150152316817001&w=2 )
> 
> So given this proposal will require read-only files, can we do
> the interface bikeshedding soon around what the userspace API
> will look like, and have it be orthogonal to (but a prerequisite for) fs-verity?

The problem is not the userspace API, it's the bike-shedding over all
of the different ways we could *do* immutability, all of which would
require separate bits in the on-disk representation of the inode.  You
can have any combination of:

* Immutable data
* Immutable metadata
   * Immutable xattrs
   * Immutable links_counts (don't allow hard links / don't allow deletes)
   * Immutable timestamps
   * etc.
* Who is allowed to set the immutable bit?
* Is the immutable bit allowed to be cleared?  If so, by who?

So it's not userspace API, it's the feature explosion --- for
something which I consider to be a fringe use case.

We picked a particular set of combinations for the current immutable
bit, and they clearly aren't to your liking; so you are essentially
trying to propose another bit, with a different set of the above
combinations.  The problem is this doesn't scale.

Given that this *is* such a fringe use case, I wonder if a better way
of satisfying your wishlist is to have a mount option which changes
how the immutable bit is enforced; essentially from reading the
previous mail thread, you want to (a) allow non-root users to set the
immutable bit, (b) you want to disable the immutable bit from being
cleared, and (c) allow immutable files to be deleted and hard linked.
Yes?

I'd much rather keep this entirely orthogonal to the fs-verity
proposal, because we could easily end up rat holing all of the
different ways *different* applications might want to interpret
immutability.

						- Ted

P.S.  The reason why it would be tricky to set the immutable bit on a
directory is because of your wish for (b) and (c) as you requested in
[2] is if you make a directory immutable, and you can't clear the
immutable bit --- then it becomes impossible to delete a non-empty
directory, since we don't have rm -rf as a system call.  So if the
kernel prohibits a directory from being changed, then we can't delete
the files in the directory --- and thus we can't empty the directory
to delete it.  Allowing a non-root user to be able to permanently make
files completely undeletable is... a non-starter.

[2] https://www.spinics.net/lists/linux-fsdevel/msg75087.html

P.P.S.  You could also implement your own custom LSM which enforces
your particular use case.  That might be a better way to go at least
in the short-term, especially since we now have stable LSM support.

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

[Colin Walters]

On Fri, Jan 26, 2018, at 10:29 AM, Theodore Ts'o wrote:
> The problem is not the userspace API, it's the bike-shedding over all
> of the different ways we could *do* immutability, all of which would
> require separate bits in the on-disk representation of the inode.  You
> can have any combination of:
> 
> * Immutable data
> * Immutable metadata
>    * Immutable xattrs

Everyone here wants immutable data (*all* of the data I hope),
and security.* xattr namespace at least. The user. xattr namespace...eh. 
If it's simpler to seal *all* xattr namespaces that seems sane to me.

(Who would want immutable xattrs but *not* immutable data?)

>    * Immutable links_counts (don't allow hard links / don't allow deletes)
>    * Immutable timestamps

So this part is definitely where ostree and dpkg/rpm diverge for example.
rpm -V treats different link counts as an error, where of course the entire
way ostree works is using hardlinks.  We also canonicalize all timestamps to 0
and would ideally have those immutable, though it's not like much really breaks if
they change.

>    * etc.
> * Who is allowed to set the immutable bit?

ostree (unlike e.g. docker which uses overlayfs) works just great as non-root
and I really like that for the build system use case.  We currently have a terrible
FUSE filesystem that implements the "immutable hardlinked files":
https://github.com/ostreedev/ostree/tree/master/src/rofiles-fuse
Which obviously like a lot of FUSE filesystems is buggy.  (Of course I know
there's patches for unprivileged overlayfs in progress)

Also as I mentioned git could use it.

> * Is the immutable bit allowed to be cleared?  If so, by who?

No, that breaks the whole point.  (Did anyone ask for that?)

> We picked a particular set of combinations for the current immutable
> bit, and they clearly aren't to your liking; so you are essentially
> trying to propose another bit, with a different set of the above
> combinations.  The problem is this doesn't scale.

I am not familiar with the LSF/MM process so forgive me if it's
obvious; but are the details of your proposal posted?  I don't
see it in the initial mail, and the conversation that followed
didn't fully clarify it.
 
> Given that this *is* such a fringe use case, 

I'm not so sure about that.  The other example I gave was
`visudo`.  If you think about /etc, almost *every* file in there
should have "object semantics" too.  And of course most of my
~/. config files.

> I wonder if a better way
> of satisfying your wishlist is to have a mount option which changes
> how the immutable bit is enforced; essentially from reading the
> previous mail thread, you want to (a) allow non-root users to set the
> immutable bit, (b) you want to disable the immutable bit from being
> cleared, and (c) allow immutable files to be deleted and hard linked.
> Yes?

All of that, plus:
- At least security. xattr namespace sealed, or all of them if no one
  cares about the user. one being dynamic (I'm honestly not sure how
  much uptake that xattr has in userspace)
- This also applies to symlinks (mostly for xattrs)
- Probably make the timestamps immutable too

That's the ostree semantics.   Now this is just my opinion of course but I
think the future of classical dpkg/rpm is to live on top of overlayfs in containers ;)
Since overlayfs already does copyup, it doesn't matter too much if we make the
"content immutable" bit allow hardlinks does it?   Mutating the filesystem underneath
an overlayfs is currently undefined anyways.

(Oh actually of course overlayfs roots is a whole other use case for this
 but that's what James was getting at)

> P.S.  The reason why it would be tricky to set the immutable bit on a
> directory 

Directories are a whole other topic.  Is that covered at all in fs-verity?

Though honestly big picture at some point down the line we're likely
to just make our /sysroot mount read-only or possibly even hidden inside
a privileged mount namespace, and remove it from the default mount namespace.
See https://github.com/ostreedev/ostree/issues/1265
And that ameliorates a *lot* of the "accidental damage" issues for host systems.
It doesn't help flatpak (which fill a similar role as APKs).  It also doesn't get
us out of the FUSE requirement for unprivileged build systems.

> P.P.S.  You could also implement your own custom LSM which enforces
> your particular use case.  That might be a better way to go at least
> in the short-term, especially since we now have stable LSM support.

And you're thinking that say the LSM would key off an xattr or something?
I suppose actually we could change the SELinux policy to deny even
"unconfined_t" from writing to `usr_t` etc.   Hmm, I may look at that.
I'd have to make it an ostree-system-based specific policy tweak as it'd almost
certainly break dpkg/rpm+SELinux systems.

But let's have the list of use cases handy:

- host root filesystem
- overlayfs lower layers
- ostree cases (buildroots, flatpak, host system)
- dpkg/rpm (mostly differs from ostree in not wanting hardlinks?)
- git (loose objects + packfiles)
- Lots of /etc

OK actually I just read the mail chain and I think I understand; you're proposing
the tree covers the inode basically as is, and that's why it wouldn't allow hardlinks?

Can we reuse the Unix permission bits or something to say that files that are u+w
but have the verity bit set allow hardlinking, and then teach the code to just ignore
the hardlink count?

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

[James Bottomley]

On Fri, 2018-01-26 at 09:58 -0500, Theodore Ts'o wrote:
> Docker save was going to have to be altered to use IMA, anyway. 

Actually, no, that's not entirely true[1].  Docker save produces a tar
file.  Once the tar on your platform picks up xattrs, docker save just
works for container images with IMA hashes and signatures (and selinux
labels, which was actually the driver for the change).  The point at
which the ecosystem changed to "just work" was the point at which tar
understood xattrs.  That's why I was poking on how do we get tar to
understand this format, following on the way IMA and selinux did it.
 There may be another way of getting this change into the ecosystem,
but ecosystem adoption has to be part of the considerations for this.

We both have our separate focusses: you for apk and me for containers.
 The point is that there should be a way of getting it to work for both
of us.  There may be a simple way based on the work that's already
done:  xattrs are already a bit magic, so all you might need is an
xattr that simply points to the tree and header, then xattr
understanding tar would simply pick up your additional metadata.  Of
course you'd have to be able to set it by writing the xattr so untar
works, but that should be possible.  The file could be instantiated
either by writing the magic format or by writing contents and xattr.
 That would seem to work both for the container and apk use case.

James

[1] For unsigned hashes.  For signatures we need lots of other stuff
like namespace aware keyrings and for the CT deployment system to load
your key onto your namespaced keyring, but in principle the *format*
problem is solved for IMA, the deployment problem of signed hashes
isn't.

>  So I don't see that as being any more difficult.  Whether you have
> to have root to set the magic IMA trusted xattr, or you call a
> userspace library, there isn't much difference between those two.
> 
> 							- Ted
> _______________________________________________
> Lsf-pc mailing list
> Lsf-pc@lists.linux-foundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lsf-pc
> 

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

[James Bottomley]

On Fri, 2018-01-26 at 11:40 -0500, Colin Walters wrote:
> On Fri, Jan 26, 2018, at 10:29 AM, Theodore Ts'o wrote:
> > 
> > The problem is not the userspace API, it's the bike-shedding over
> > all of the different ways we could *do* immutability, all of which
> > would require separate bits in the on-disk representation of the
> > inode.  You can have any combination of:
> > 
> > * Immutable data
> > * Immutable metadata
> >    * Immutable xattrs
> 
> Everyone here wants immutable data (*all* of the data I hope),

No, no, I don't.   In the world today most linux distributions from
which we produce containers do have the annoying property of writing
stuff where they shouldn't (mostly into /etc).  Systemd is working on
fixing this and when you can make everything other than your /tmp and
/var/tmp read only on your distro, then I will be able to have fully
immutable container images.  But, until that day comes, I'm going to
need a mix of immutable and mutable files on one filesystem.

So when container people boast about immutable images, what they
actually mean is *mostly* immutable apart from bits we can't fix.  What
they actually mean is we don't patch the image in situ but instead
deploy an upgraded image and when we start each time we start from the
pristine state but as the image is running it can mutate slightly.

James

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

[Colin Walters]

On Fri, Jan 26, 2018, at 11:49 AM, James Bottomley wrote:
> On Fri, 2018-01-26 at 11:40 -0500, Colin Walters wrote:
> > On Fri, Jan 26, 2018, at 10:29 AM, Theodore Ts'o wrote:
> > > 
> > > The problem is not the userspace API, it's the bike-shedding over
> > > all of the different ways we could *do* immutability, all of which
> > > would require separate bits in the on-disk representation of the
> > > inode.  You can have any combination of:
> > > 
> > > * Immutable data
> > > * Immutable metadata
> > >    * Immutable xattrs
> > 
> > Everyone here wants immutable data (*all* of the data I hope),
> 
> No, no, I don't.   In the world today most linux distributions from
> which we produce containers do have the annoying property of writing
> stuff where they shouldn't (mostly into /etc). 

Sorry, I meant that no one was asking for *partially* immutable single files,
like how one can F_SETLK byte ranges today.  Now that I think about it
though that's kind of what log files like the systemd journal want (i.e. O_APPEND like)
but honestly people who care about that kind of stuff tend to send log messages remotely
anyways and I personally care a whole lot more about binaries (basically
ideally fs-verity covers at least everything that can gain CAP_SYS_ADMIN,
including e.g. supporting local signing of installed RPMs/host extensions,
and notably if one has a Docker container or whatever that is configured
to gain CAP_SYS_ADMIN on start, or equivalent).

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

[Mimi Zohar]

[Cc'ing the linux-integrity mailing list]

On Thu, 2018-01-25 at 14:11 -0500, Theodore Ts'o wrote:
> I'd like to talk about a proposal to implement and upstream something
> that we've been calling fs-verity, which is something like dm-verity,
> but implemnted on a per-file basis.  It will be implemnted much like
> fs/crypto, in that most of the code will be in a generic layer, with
> minimal modifications needed in the file system layer.
> 
> The merkle tree will be located after file's normal data, and then
> after the package manager sets the verity bit, i_size will be updated
> so that the fs-verity header and merkle tree will be "hidden" from
> userspace and the file will become immutable.
> 
> How does this differ from IMA's file integrity?
> 
> *) The pages are verified as they are read, so pages are verified as
> they are read the storage device; this avoids a large latency hit when
> the file is first opened or referenced.

Secure and trusted boot standards require files to be measured and
appraised before usage.  Perhaps verifying the merkle tree satifies
these requirements.

IMA-appraisal is being extended to support appended signatures, as
generated by scripts/sign-file.  This proposed method of calculating
the file hash could be another signature method.

> *) The design and code are done by file system developers, so it
> doesn't have the locking problems of the IMA code.

True, the locking problem is a direct result of using xattrs for
storing file metadata, which requires taking the i_rwsem exclusively
for writing.  This solution circumvents the locking issues because it
appends the file metadata to the file data instead of using xattrs.

By using atomic flags, as suggested by Linus, Dmitry Kasatkin has
resolved the xattr locking issue.  The patch is currently staged to
be upstreamed in the next open window.

> 
> The initial use case of this will be for Android, where the latency
> concerns of doing the full checksum at file open time is important.
> 
> In the future, the fact that a file has been signed using fs-verity,
> using a PKCS 11 signature with a key on a trusted keyring (possibly
> the same one used for signed kernel modules, or perhaps a separate
> keyring) could be used as input into a security policy which requires
> this for say, setuid executables, setuid shell scripts, etc.
> 
> Most of this feature could also be used with a non-cryptographic
> checksum to provide data checksums for read-only files in a general
> way for all file systems.  It wouldn't be as flexible as btrfs, but
> for files being stored for backup purposes, it should work quite well.

Signing and verifying local file signatures, is a lot simpler than
supporting a full software package life cycle.  Can the file metadata
- signatures and trees - be calculated and included in software
packages, with the file data, for distribution?

In terms of remote filesystems, the same trust issues exist with this
solution as with IMA-appraisal.

Mimi

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

[Mimi Zohar]

[Cc'ing the linux-integrity mailing list]

On Thu, 2018-01-25 at 14:11 -0500, Theodore Ts'o wrote:
> I'd like to talk about a proposal to implement and upstream something
> that we've been calling fs-verity, which is something like dm-verity,
> but implemnted on a per-file basis.  It will be implemnted much like
> fs/crypto, in that most of the code will be in a generic layer, with
> minimal modifications needed in the file system layer.
> 
> The merkle tree will be located after file's normal data, and then
> after the package manager sets the verity bit, i_size will be updated
> so that the fs-verity header and merkle tree will be "hidden" from
> userspace and the file will become immutable.
> 
> How does this differ from IMA's file integrity?
> 
> *) The pages are verified as they are read, so pages are verified as
> they are read the storage device; this avoids a large latency hit when
> the file is first opened or referenced.

Secure and trusted boot standards require files to be measured and
appraised before usage.  Perhaps verifying the merkle tree satifies
these requirements.

IMA-appraisal is being extended to support appended signatures, as
generated by scripts/sign-file.  This proposed method of calculating
the file hash could be another signature method.

> *) The design and code are done by file system developers, so it
> doesn't have the locking problems of the IMA code.

True, the locking problem is a direct result of using xattrs for
storing file metadata, which requires taking the i_rwsem exclusively
for writing.  This solution circumvents the locking issues because it
appends the file metadata to the file data instead of using xattrs.

By using atomic flags, as suggested by Linus, Dmitry Kasatkin has
resolved the xattr locking issue.  The patch is currently staged to
be upstreamed in the next open window.

> 
> The initial use case of this will be for Android, where the latency
> concerns of doing the full checksum at file open time is important.
> 
> In the future, the fact that a file has been signed using fs-verity,
> using a PKCS 11 signature with a key on a trusted keyring (possibly
> the same one used for signed kernel modules, or perhaps a separate
> keyring) could be used as input into a security policy which requires
> this for say, setuid executables, setuid shell scripts, etc.
> 
> Most of this feature could also be used with a non-cryptographic
> checksum to provide data checksums for read-only files in a general
> way for all file systems.  It wouldn't be as flexible as btrfs, but
> for files being stored for backup purposes, it should work quite well.

Signing and verifying local file signatures, is a lot simpler than
supporting a full software package life cycle.  Can the file metadata
- signatures and trees - be calculated and included in software
packages, with the file data, for distribution?

In terms of remote filesystems, the same trust issues exist with this
solution as with IMA-appraisal.

Mimi

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

[Mimi Zohar]

[Cc'ing linux-integrity]

On Fri, 2018-01-26 at 09:58 -0500, Theodore Ts'o wrote:

> > 
> > Currently container images are simple tar files and one of the main
> > value adds of docker as a tool is the simplicity of the image creation
> > process.  That process depends on standard tools like tar to create the
> > image, so I was trying to fit this proposal into that process.
> 
> The goal of fs-verity is protect arbitrary files without breaking the
> backwards compatibility of those that *read* the file.  So for
> example, an APK file is downloaded and verified at the intial download
> --- and never verified again.  It is *used* many times after the
> initial download (and hence, potentially after an evil maid attack),
> and this is done by many different tools, including by code inside the
> APK itself.  So it is not feasible to change the tools that read the
> APK, which means we can't make any backwards-incompatible changes to
> the file itself.
> 
> However, changing the tools that *establish* the locally verified copy
> is considered completely fair game.  I'll note that this is true no
> matter what system you use.  If you are using IMA, after the file is
> downloaded, you still have to set the magic "trusted xattr" (which, I
> will note, requires root access since it is a trusted root access).
> So you have to make at least *some* changes to the code path which
> writes the file that you want to be integrity protected.  In the case
> of IMA, this includes code that has to run as root.

Different types of software packages (eg. tar, rpm, multiple deb
prototypes) can be built to include file signatures.  Both the file
data and metadata (eg. signatures) would be installed together by the
same app, which already has root privileges needed to install them.

Mimi

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

[Mimi Zohar]

[Cc'ing linux-integrity]

On Fri, 2018-01-26 at 09:58 -0500, Theodore Ts'o wrote:

> > 
> > Currently container images are simple tar files and one of the main
> > value adds of docker as a tool is the simplicity of the image creation
> > process.  That process depends on standard tools like tar to create the
> > image, so I was trying to fit this proposal into that process.
> 
> The goal of fs-verity is protect arbitrary files without breaking the
> backwards compatibility of those that *read* the file.  So for
> example, an APK file is downloaded and verified at the intial download
> --- and never verified again.  It is *used* many times after the
> initial download (and hence, potentially after an evil maid attack),
> and this is done by many different tools, including by code inside the
> APK itself.  So it is not feasible to change the tools that read the
> APK, which means we can't make any backwards-incompatible changes to
> the file itself.
> 
> However, changing the tools that *establish* the locally verified copy
> is considered completely fair game.  I'll note that this is true no
> matter what system you use.  If you are using IMA, after the file is
> downloaded, you still have to set the magic "trusted xattr" (which, I
> will note, requires root access since it is a trusted root access).
> So you have to make at least *some* changes to the code path which
> writes the file that you want to be integrity protected.  In the case
> of IMA, this includes code that has to run as root.

Different types of software packages (eg. tar, rpm, multiple deb
prototypes) can be built to include file signatures.  Both the file
data and metadata (eg. signatures) would be installed together by the
same app, which already has root privileges needed to install them.

Mimi

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

[Theodore Ts'o]

On Fri, Jan 26, 2018 at 08:44:27AM -0800, James Bottomley wrote:
> On Fri, 2018-01-26 at 09:58 -0500, Theodore Ts'o wrote:
> > Docker save was going to have to be altered to use IMA, anyway.�
> 
> Actually, no, that's not entirely true[1]. �Docker save produces a tar
> file. �Once the tar on your platform picks up xattrs, docker save just
> works for container images with IMA hashes and signatures (and selinux
> labels, which was actually the driver for the change). �The point at
> which the ecosystem changed to "just work" was the point at which tar
> understood xattrs. �That's why I was poking on how do we get tar to
> understand this format, following on the way IMA and selinux did it.
> �There may be another way of getting this change into the ecosystem,
> but ecosystem adoption has to be part of the considerations for this.

Oh, I see.  You are saying that you want to be able to use tar to
backup integrity protected files, and then restore them later.

Yes, that's different from what I was assuming, which is a model where
the integrity protect file would be written by some package manager
(e.g,. rpm, dpkg, the code that downloads the apk, etc.), and that we
would *not* be trying to backup the file with the integrity data, and
then restore it later via some kind of untar operation.

The problem here is that a merkle tree simply won't fit inside an
xattr for any non-trivail file.  And there may be use cases where
blocking the open until the integrity is verifeid on the entire file.
However, there are uses cases where the a signifcant increase in the
open latency can't be tolerated, and wher the file might have might
have large portions of dat which will never be read, and thus, don't
need to have their integrity verified.  (Example: an APK might have
megabytes and megabytes of translation resources for N languages, only
one of which will normally be used by a particular user on a
particular phone.  Or as another example, an ELF binary that has huge
portions of symbol table and debugging information that is normally
not used.)

So the requirement that you must be able to backup an integrity
protected file, and then restore it again, without modifying the tool
which does the backup and restore, does certainly push you towards
using xattrs.  But xattrs force the huge open latency, and while
Docker is big in some circles, there are lots of use cases where the
unmodified backup/restore requiremnt is simply not applicable.

So perhaps there is room for both solutions.

Cheers,

						- Ted

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

[Andreas Dilger]

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

On Jan 26, 2018, at 2:55 PM, Theodore Ts'o <tytso@mit.edu> wrote:
> 
> On Fri, Jan 26, 2018 at 08:44:27AM -0800, James Bottomley wrote:
>> On Fri, 2018-01-26 at 09:58 -0500, Theodore Ts'o wrote:
>>> Docker save was going to have to be altered to use IMA, anyway.
>> 
>> Actually, no, that's not entirely true[1].  Docker save produces a tar
>> file.  Once the tar on your platform picks up xattrs, docker save just
>> works for container images with IMA hashes and signatures (and selinux
>> labels, which was actually the driver for the change).  The point at
>> which the ecosystem changed to "just work" was the point at which tar
>> understood xattrs.  That's why I was poking on how do we get tar to
>> understand this format, following on the way IMA and selinux did it.
>>  There may be another way of getting this change into the ecosystem,
>> but ecosystem adoption has to be part of the considerations for this.
> 
> Oh, I see.  You are saying that you want to be able to use tar to
> backup integrity protected files, and then restore them later.
> 
> Yes, that's different from what I was assuming, which is a model where
> the integrity protect file would be written by some package manager
> (e.g,. rpm, dpkg, the code that downloads the apk, etc.), and that we
> would *not* be trying to backup the file with the integrity data, and
> then restore it later via some kind of untar operation.
> 
> The problem here is that a merkle tree simply won't fit inside an
> xattr for any non-trivail file.  And there may be use cases where
> blocking the open until the integrity is verifeid on the entire file.
> However, there are uses cases where the a signifcant increase in the
> open latency can't be tolerated, and wher the file might have might
> have large portions of dat which will never be read, and thus, don't
> need to have their integrity verified.  (Example: an APK might have
> megabytes and megabytes of translation resources for N languages, only
> one of which will normally be used by a particular user on a
> particular phone.  Or as another example, an ELF binary that has huge
> portions of symbol table and debugging information that is normally
> not used.)
> 
> So the requirement that you must be able to backup an integrity
> protected file, and then restore it again, without modifying the tool
> which does the backup and restore, does certainly push you towards
> using xattrs.  But xattrs force the huge open latency, and while
> Docker is big in some circles, there are lots of use cases where the
> unmodified backup/restore requiremnt is simply not applicable.
> 
> So perhaps there is room for both solutions.

I think this is relatively straight forward to handle.  The package
(tarball, whatever) itself only needs to store the top-level checksum,
since this validates the whole Merkle tree, and in turn the integrity
of the whole file.  This is exactly what Bittorrent does for files.

When the package is extracted, the Merkle tree can be regenerated and
written with the file for random IO access using fs-verity.  When the
Merkle tree is written to disk, the top-level checksum is verified
against the checksum stored in the package to ensure it was written
correctly.  This means only a small checksum needs to be stored in
the archive (32 bytes), but an integrated system will have end-to-end
data verification.

Cheers, Andreas






[-- Attachment #2: Message signed with OpenPGP --]
[-- Type: application/pgp-signature, Size: 873 bytes --]

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

[James Bottomley]

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

On Sat, 2018-01-27 at 00:58 -0700, Andreas Dilger wrote:
> On Jan 26, 2018, at 2:55 PM, Theodore Ts'o <tytso@mit.edu> wrote:
> > 
> > 
> > On Fri, Jan 26, 2018 at 08:44:27AM -0800, James Bottomley wrote:
> > > 
> > > On Fri, 2018-01-26 at 09:58 -0500, Theodore Ts'o wrote:
> > > > 
> > > > Docker save was going to have to be altered to use IMA, anyway.
> > > 
> > > Actually, no, that's not entirely true[1].  Docker save produces
> > > a tar file.  Once the tar on your platform picks up xattrs,
> > > docker save just works for container images with IMA hashes and
> > > signatures (and selinux labels, which was actually the driver for
> > > the change).  The point at which the ecosystem changed to "just
> > > work" was the point at which tar understood xattrs.  That's why I
> > > was poking on how do we get tar to understand this format,
> > > following on the way IMA and selinux did it.  There may be
> > > another way of getting this change into the ecosystem, but
> > > ecosystem adoption has to be part of the considerations for this.
> > 
> > Oh, I see.  You are saying that you want to be able to use tar to
> > backup integrity protected files, and then restore them later.
> > 
> > Yes, that's different from what I was assuming, which is a model
> > where the integrity protect file would be written by some package
> > manager (e.g,. rpm, dpkg, the code that downloads the apk, etc.),
> > and that we would *not* be trying to backup the file with the
> > integrity data, and then restore it later via some kind of untar
> > operation.
> > 
> > The problem here is that a merkle tree simply won't fit inside an
> > xattr for any non-trivail file.  And there may be use cases where
> > blocking the open until the integrity is verifeid on the entire
> > file. However, there are uses cases where the a signifcant increase
> > in the open latency can't be tolerated, and wher the file might
> > have might have large portions of dat which will never be read, and
> > thus, don't need to have their integrity verified.  (Example: an
> > APK might have megabytes and megabytes of translation resources for
> > N languages, only one of which will normally be used by a
> > particular user on a particular phone.  Or as another example, an
> > ELF binary that has huge portions of symbol table and debugging
> > information that is normally not used.)
> > 
> > So the requirement that you must be able to backup an integrity
> > protected file, and then restore it again, without modifying the
> > tool which does the backup and restore, does certainly push you
> > towards using xattrs.  But xattrs force the huge open latency, and
> > while Docker is big in some circles, there are lots of use cases
> > where the unmodified backup/restore requiremnt is simply not
> > applicable.
> > 
> > So perhaps there is room for both solutions.
> 
> I think this is relatively straight forward to handle.  The package
> (tarball, whatever) itself only needs to store the top-level
> checksum, since this validates the whole Merkle tree, and in turn the
> integrity of the whole file.  This is exactly what Bittorrent does
> for files.

Well, not quite: bittorrent doesn't reconstruct the hash from the file,
it downloads the hash a piece at a time and uses that to verify the
piece of the file it's obtained.  However, I accept that's only because
the leechers don't have the whole file from which to reconstruct the
hash; seed creation certainly does this.

> When the package is extracted, the Merkle tree can be regenerated and
> written with the file for random IO access using fs-verity.  When the
> Merkle tree is written to disk, the top-level checksum is verified
> against the checksum stored in the package to ensure it was written
> correctly.  This means only a small checksum needs to be stored in
> the archive (32 bytes), but an integrated system will have end-to-end
> data verification.

I certainly buy this approach, and it fits well with the limited data
size there is in xattrs but Ted said in the initial proposal the entire
tree would be present in the file.  I can't see a need for supplying
the entire tree rather than reconstructing it but maybe there's an
android use case I'm not seeing (Like not wanting to waste limited CPU
power).

Just so I understand the mechanics: The xattr would contain the head
node.  When this is written, the tree would be reconstructed from the
file and verified.  If it verifies, it must be stored in the filesystem
data somehow (or at least the lowest layer), so all subsequent uses of
the file can proceed from the per page hash even after unmount and
remount?  Then I certainly think it suits both cases.

James

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

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

[James Bottomley]

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

[cc'ing linux-integrity, since they're the experts]

On Sat, 2018-01-27 at 08:19 -0800, James Bottomley wrote:
> On Sat, 2018-01-27 at 00:58 -0700, Andreas Dilger wrote:
> > 
> > On Jan 26, 2018, at 2:55 PM, Theodore Ts'o <tytso@mit.edu> wrote:
> > > 
> > > 
> > > 
> > > On Fri, Jan 26, 2018 at 08:44:27AM -0800, James Bottomley wrote:
> > > > 
> > > > 
> > > > On Fri, 2018-01-26 at 09:58 -0500, Theodore Ts'o wrote:
> > > > > 
> > > > > 
> > > > > Docker save was going to have to be altered to use IMA,
> > > > > anyway.
> > > > 
> > > > Actually, no, that's not entirely true[1].  Docker save
> > > > produces a tar file.  Once the tar on your platform picks up
> > > > xattrs, docker save just works for container images with IMA
> > > > hashes and signatures (and selinux labels, which was actually
> > > > the driver for the change).  The point at which the ecosystem
> > > > changed to "just work" was the point at which tar understood
> > > > xattrs.  That's why I was poking on how do we get tar to
> > > > understand this format, following on the way IMA and selinux
> > > > did it.  There may be another way of getting this change into
> > > > the ecosystem, but ecosystem adoption has to be part of the
> > > > considerations for this.
> > > 
> > > Oh, I see.  You are saying that you want to be able to use tar to
> > > backup integrity protected files, and then restore them later.
> > > 
> > > Yes, that's different from what I was assuming, which is a model
> > > where the integrity protect file would be written by some package
> > > manager (e.g,. rpm, dpkg, the code that downloads the apk, etc.),
> > > and that we would *not* be trying to backup the file with the
> > > integrity data, and then restore it later via some kind of untar
> > > operation.
> > > 
> > > The problem here is that a merkle tree simply won't fit inside an
> > > xattr for any non-trivail file.  And there may be use cases where
> > > blocking the open until the integrity is verifeid on the entire
> > > file. However, there are uses cases where the a signifcant
> > > increase in the open latency can't be tolerated, and wher the
> > > file might have might have large portions of dat which will never
> > > be read, and thus, don't need to have their integrity
> > > verified.  (Example: an APK might have megabytes and megabytes of
> > > translation resources for N languages, only one of which will
> > > normally be used by a particular user on a particular phone.  Or
> > > as another example, an ELF binary that has huge portions of
> > > symbol table and debugging information that is normally not
> > > used.)
> > > 
> > > So the requirement that you must be able to backup an integrity
> > > protected file, and then restore it again, without modifying the
> > > tool which does the backup and restore, does certainly push you
> > > towards using xattrs.  But xattrs force the huge open latency,
> > > and while Docker is big in some circles, there are lots of use
> > > cases where the unmodified backup/restore requiremnt is simply
> > > not applicable.
> > > 
> > > So perhaps there is room for both solutions.
> > 
> > I think this is relatively straight forward to handle.  The package
> > (tarball, whatever) itself only needs to store the top-level
> > checksum, since this validates the whole Merkle tree, and in turn
> > the integrity of the whole file.  This is exactly what Bittorrent
> > does for files.
> 
> Well, not quite: bittorrent doesn't reconstruct the hash from the
> file, it downloads the hash a piece at a time and uses that to verify
> the piece of the file it's obtained.  However, I accept that's only
> because the leechers don't have the whole file from which to
> reconstruct the hash; seed creation certainly does this.
> 
> > 
> > When the package is extracted, the Merkle tree can be regenerated
> > and written with the file for random IO access using fs-
> > verity.  When the Merkle tree is written to disk, the top-level
> > checksum is verified against the checksum stored in the package to
> > ensure it was written correctly.  This means only a small checksum
> > needs to be stored in the archive (32 bytes), but an integrated
> > system will have end-to-end data verification.
> 
> I certainly buy this approach, and it fits well with the limited data
> size there is in xattrs but Ted said in the initial proposal the
> entire tree would be present in the file.  I can't see a need for
> supplying the entire tree rather than reconstructing it but maybe
> there's an android use case I'm not seeing (Like not wanting to waste
> limited CPU power).
> 
> Just so I understand the mechanics: The xattr would contain the head
> node.  When this is written, the tree would be reconstructed from the
> file and verified.  If it verifies, it must be stored in the
> filesystem data somehow (or at least the lowest layer), so all
> subsequent uses of the file can proceed from the per page hash even
> after unmount and remount?  Then I certainly think it suits both
> cases.

Just adding to this: it looks like the merkle tree could be an internal
thing only depending on whether the filesystem supported it and whether
the user wanted this mode of verification (likely because of the space
it takes in the filesystem) because you can also construct a merkle
tree from a standard IMA signed hash, so there's no real need for a new
external format.

James

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

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

[James Bottomley]

[-- Attachment #1: Type: multipart/signed, Size: 5564 bytes --]

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

[Theodore Ts'o]

On Sat, Jan 27, 2018 at 08:19:19AM -0800, James Bottomley wrote:
> I certainly buy this approach, and it fits well with the limited data
> size there is in xattrs but Ted said in the initial proposal the entire
> tree would be present in the file.��I can't see a need for supplying
> the entire tree rather than reconstructing it but maybe there's an
> android use case I'm not seeing (Like not wanting to waste limited CPU
> power).

You can certainly reconstruct the Merkle tree at install time, but it
does need to be saved on disk.  My assumption was that Merkle tree
would be written to disk by userspace, along with the fs-verity
header, simply because it would make things much simpler for the
kernel, and in my view you *have* to modify userspace in some way.

> Just so I understand the mechanics: The xattr would contain the head
> node. �When this is written, the tree would be reconstructed from the
> file and verified. �If it verifies, it must be stored in the filesystem
> data somehow (or at least the lowest layer), so all subsequent uses of
> the file can proceed from the per page hash even after unmount and
> remount? �Then I certainly think it suits both cases.

Yes.... in theory we could store the bare root hash (and some other
bare minmum information, such as the PKCS7 signature and the elments
of a fs-verity header) in an xattr, and setting that xattr would
magically cause the merkle tree to be reconstructed and stored on
disk.  But most of the file sytem developers have considered the use
of setting or clearing xattrs to cause magically code paths to be
executed to be an extremely bad idea.  And since I don't really care
about the use case, I can let *you* try to convince Cristoph and Al
Viro that his is a good idea, despite the general agreemnt by all file
system developers that we've been there, done that, decided it was a
really bad idea, and let's never ever do that again.  (And then you
can get some of the "the IMA people are insane" taint on yourself.  :-)

    	    	    	     	 	- Ted

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

[James Bottomley]

Just addressing this one comment from a process point of view; I'll
come back to the technical part later.

On Sat, 2018-01-27 at 21:46 -0500, Theodore Ts'o wrote:
> (And then you can get some of the "the IMA people are insane" taint
> on yourself.  :-)

Can we please stop it with the "all IMA people are insane" mantra.

I think we've created this problem, for all security people not just
IMA, ourselves to some extent:  We think they're insane, so we don't
listen to what they want.  They go and implement a complicated layering
system to get what they need and we congratulate ourselves that they
were insane because of the tasteless layering violations they've just
committed.  The average security person, as ably created by us, has a
mind that automatically thinks in terms of convoluted external
layering, for which we just drive them further away.

IMA has demonstrated a willingness to work with fs people to try to
clean up the layering problems over the past year or so, including
attending the last LSF/MM to discuss it.  Sure, they're going to have
relapses into the layering mindset (fstype policies springs to mind),
but the test is their willingness to listen to the correct way of doing
things, which I think they're currently passing.

Why don't you try working with them instead of starting from the a-
priori axiom that you can't because they're insane?  They do have years
of experience of what the industry is looking for in security terms,
which we should make use of.  Doing security ourselves because we can't
work with security people is a recipe for eventual tears.

James

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

[James Bottomley]

On Sat, 2018-01-27 at 21:46 -0500, Theodore Ts'o wrote:
> On Sat, Jan 27, 2018 at 08:19:19AM -0800, James Bottomley wrote:
> > 
> > I certainly buy this approach, and it fits well with the limited
> > data size there is in xattrs but Ted said in the initial proposal
> > the entire tree would be present in the file.  I can't see a need
> > for supplying the entire tree rather than reconstructing it but
> > maybe there's an android use case I'm not seeing (Like not wanting
> > to waste limited CPU power).
> 
> You can certainly reconstruct the Merkle tree at install time, but it
> does need to be saved on disk.  My assumption was that Merkle tree
> would be written to disk by userspace, along with the fs-verity
> header, simply because it would make things much simpler for the
> kernel, and in my view you *have* to modify userspace in some way.

OK, so we agree then that what IMA provides: a hash and potential
signature over the hash is sufficient input for what you want and does
provide existing tooling to achieve it.

> > Just so I understand the mechanics: The xattr would contain the
> > head node.  When this is written, the tree would be reconstructed
> > from the file and verified.  If it verifies, it must be stored in
> > the filesystem data somehow (or at least the lowest layer), so all
> > subsequent uses of the file can proceed from the per page hash even
> > after unmount and remount?  Then I certainly think it suits both
> > cases.
> 
> Yes.... in theory we could store the bare root hash (and some other
> bare minmum information, such as the PKCS7 signature and the elments
> of a fs-verity header) in an xattr, and setting that xattr would
> magically cause the merkle tree to be reconstructed and stored on
> disk.  But most of the file sytem developers have considered the use
> of setting or clearing xattrs to cause magically code paths to be
> executed to be an extremely bad idea.

Hang on, you've jumped straight from a discussion of ideas to an insane
implementation ... can we take a step back?  I'm thinking of three
separate things

   1. Could the signature piece of this be done in the way IMA currently
      does file signatures.  We all agree "yes" on this, since a signed
      mekle hash head is the same size as an existing IMA signature and
      therefore does fit into xattrs.
   2. Could IMA use a merkle tree for hash verification a page at a time
      as part of its implementation?  I think the answer to this is yes,
      except the hook has to be somewhere in the page fault mechanism, so
      it would need some exploration and prototyping.
   3. Could the merkle tree be cached somehow in the filesystem (probably
      as part of the filesystem implementaiton)?  You've already assumed
      "yes" for this since it's how fs-verity is proposed to work.

So the issue we could discuss is how all this is tied together.  The
implementation could be your special format file for 3. but with the
head hash signature in an xattr.  What we get back on tar would be the
ordinary file + xattr, but perhaps tar could use this to reconstruct
the magic file on untar.

I do think the "special format magic file" is a violation of the unix
principles of files being "just files" but if it's the only way, I
suppose I could be persuaded.  However, this part should also be
discussed; it does seem like, to satisfy unix principles, the merkle
tree should be provided separately from the file, possibly as a
fcntl().

James

>   And since I don't really care about the use case, I can let *you*
> try to convince Cristoph and Al Viro that his is a good idea, despite
> the general agreemnt by all file system developers that we've been
> there, done that, decided it was a really bad idea, and let's never
> ever do that again.  (And then you can get some of the "the IMA
> people are insane" taint on yourself.  :-)
> 
>     	    	    	     	 	- Ted
> 

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

[Chuck Lever]

> On Jan 28, 2018, at 10:03 AM, James Bottomley <James.Bottomley@HansenPartnership.com> wrote:
> 
> On Sat, 2018-01-27 at 21:46 -0500, Theodore Ts'o wrote:
>> On Sat, Jan 27, 2018 at 08:19:19AM -0800, James Bottomley wrote:
>>> 
>>> I certainly buy this approach, and it fits well with the limited
>>> data size there is in xattrs but Ted said in the initial proposal
>>> the entire tree would be present in the file.  I can't see a need
>>> for supplying the entire tree rather than reconstructing it but
>>> maybe there's an android use case I'm not seeing (Like not wanting
>>> to waste limited CPU power).
>> 
>> You can certainly reconstruct the Merkle tree at install time, but it
>> does need to be saved on disk.  My assumption was that Merkle tree
>> would be written to disk by userspace, along with the fs-verity
>> header, simply because it would make things much simpler for the
>> kernel, and in my view you *have* to modify userspace in some way.
> 
> OK, so we agree then that what IMA provides: a hash and potential
> signature over the hash is sufficient input for what you want and does
> provide existing tooling to achieve it.
> 
>>> Just so I understand the mechanics: The xattr would contain the
>>> head node.  When this is written, the tree would be reconstructed
>>> from the file and verified.  If it verifies, it must be stored in
>>> the filesystem data somehow (or at least the lowest layer), so all
>>> subsequent uses of the file can proceed from the per page hash even
>>> after unmount and remount?  Then I certainly think it suits both
>>> cases.
>> 
>> Yes.... in theory we could store the bare root hash (and some other
>> bare minmum information, such as the PKCS7 signature and the elments
>> of a fs-verity header) in an xattr, and setting that xattr would
>> magically cause the merkle tree to be reconstructed and stored on
>> disk.  But most of the file sytem developers have considered the use
>> of setting or clearing xattrs to cause magically code paths to be
>> executed to be an extremely bad idea.
> 
> Hang on, you've jumped straight from a discussion of ideas to an insane
> implementation ... can we take a step back?  I'm thinking of three
> separate things
> 
>   1. Could the signature piece of this be done in the way IMA currently
>      does file signatures.  We all agree "yes" on this, since a signed
>      mekle hash head is the same size as an existing IMA signature and
>      therefore does fit into xattrs.
>   2. Could IMA use a merkle tree for hash verification a page at a time
>      as part of its implementation?  I think the answer to this is yes,
>      except the hook has to be somewhere in the page fault mechanism, so
>      it would need some exploration and prototyping.
>   3. Could the merkle tree be cached somehow in the filesystem (probably
>      as part of the filesystem implementaiton)?  You've already assumed
>      "yes" for this since it's how fs-verity is proposed to work.
> 
> So the issue we could discuss is how all this is tied together.  The
> implementation could be your special format file for 3. but with the
> head hash signature in an xattr.  What we get back on tar would be the
> ordinary file + xattr, but perhaps tar could use this to reconstruct
> the magic file on untar.
> 
> I do think the "special format magic file" is a violation of the unix
> principles of files being "just files" but if it's the only way, I
> suppose I could be persuaded.  However, this part should also be
> discussed; it does seem like, to satisfy unix principles, the merkle
> tree should be provided separately from the file, possibly as a
> fcntl().

For NFS, storing the tree or even an IMA signature in a trusted xattr
is currently off the table because the protocol does not convey
non-user xattrs. My interest is finding a way to get binary signing
without the need of the xattr.

Interestingly, Solaris puts the signature in an ELF header. That
would certainly work for NFS.


> James
> 
>>   And since I don't really care about the use case, I can let *you*
>> try to convince Cristoph and Al Viro that his is a good idea, despite
>> the general agreemnt by all file system developers that we've been
>> there, done that, decided it was a really bad idea, and let's never
>> ever do that again.  (And then you can get some of the "the IMA
>> people are insane" taint on yourself.  :-)
>> 
>>     	    	    	     	 	- Ted

--
Chuck Lever

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

[Theodore Ts'o]

On Sun, Jan 28, 2018 at 10:03:10AM -0800, James Bottomley wrote:
> 
> OK, so we agree then that what IMA provides: a hash and potential
> signature over the hash is sufficient input for what you want and does
> provide existing tooling to achieve it.

Well, that's not all IMA provides.  Remmber, the 'M' in IMA is
*measurement*.  IMA was originally about checksuming every single file
that is opened and writing it to a long.  You could suppress it by
using SELinux to tag files (using xattrs which are *not* signed) and
then writing an IMA policy which tells IMA to ignore files that belong
to a certain SE Linux tag.  This is something that I *don't* want and
today, enabling CONFIG_IMA drags all of this (including doing text
parsing of the IMA policy in the kernel, SELinux, etc.) into the
kernel.

One of my other complaints about IMA is that it's an integrated
solution, with a huge amount of complexity.  If it was only about file
signing, that would be one thing, but that's actually not the case
today.  Hence my comment about I don't want fs-verity to have a
dependency on IMA, such that we are forced to drag in all of IMA and
SELinux for anyone who wants to use use fs-verity.

This is fine; I don't want to have to dictate changes to IMA; I'd much
prefer to avoid the complexity instead of trying to reform it, since
I'm sure the IMA folks will be happy to explain why there are all
sorts of reasons why things have to be done the way it has to be done.
For example, the assertion that the latency hit at open(2) *must* be
there in order to kowtow to Microsoft because of its Trusted Boot
policies; fair enough, but *I* don't care about Trusted Boot, and it's
not fair to impose penalties on all scenarios because of a desire to
keep Microsoft happy just for one particular use case.

>    1. Could the signature piece of this be done in the way IMA currently
>       does file signatures. �We all agree "yes" on this, since a signed
>       mekle hash head is the same size as an existing IMA signature and
>       therefore does fit into xattrs.

Well.... not exactly.

It is fair to say that there are two parts of integrity metadata; and
the Merkle tree can be reconstructed at file install time.

>    2. Could IMA use a merkle tree for hash verification a page at a time
>       as part of its implementation? �I think the answer to this is yes,
>       except the hook has to be somewhere in the page fault mechanism, so
>       it would need some exploration and prototyping.

The way you are formulating things presumes that all of IMA has to be
dragged into any file integrity solution.  That's begging the
question.  As I've mentioned above, IMA has all sorts of complexity
which is currently mandatory, and I'm not volunteering to disentagling
the mess to make it be sane.  (And if you don't like that word, how
about, "designed with good taste?")

>    3. Could the merkle tree be cached somehow in the filesystem (probably
>       as part of the filesystem implementaiton)? �You've already assumed
>       "yes" for this since it's how fs-verity is proposed to work.

I don't consider this the Merkel tree to a *cache*, however because if
you don't mind a massive latency at file open tme, you can just use
the existing IMA mechanism.  So a core part of the design is that the
Merkle file is stored permanently (*not* as a cache) alongside the
file.  And if the file is renamed, the Merkle tree should come along
for the ride.

Whether the Merkle tree is reconstructed as part of the file / package
installation process, or whether the Merkle tree stored as part of the
package or streamed from the app store, etc., is an implementation
detail, and I don't think we need to prescribe one way of doing
things.  I *do* think though we should allow for possibility where
limitations on the local CPU power is such that it would be preferable
for the Merkle tree to be supplied from a remote server instead of
generated on the local system.

The problem is you have a specific use case in mind, involving the
Docker client, where you want to store the signature in an xattr, and
then not require any local changes to the Docker client --- and that's
not in my requirements set, and it was *your* statement that the
Docker client MUST NOT be modified which forced where (a) the Merkle
tree must be reconstructed in the kernel, and (b) it must be triggered
by setting the xattr.

My goal is to keep things simple, which means

* No parsing of the IMA policy as a text input in the kernel
* No Merkle tree construction in the kernel (which is also true of dm-verity)
* No magic xattr triggering

Speaking as a kernel developer, it makes a more sense to keep things
in the kernel, and do as much in userspace as possible --- and if that
means that the Docker client (or the package manager, etc.) needs a
minor change to call the userspace library, that's infinitely
preferable to keeping huge amounts of complexity in non-swappable
kernel memory --- which increases the attack surface of the kernel,
and so on.

So in my opinion, clean design of the kernel trumps the requirement of
"not one change, not one jot, in the Docker client".

It could be that the requiremnts of "keep the kernel changes simple"
and "no massive latency at file open time", means that requiremnt sets
of fs-verity and IMA are irreconcilable.  Which is fine as far as I'm
concerned.  Maybe IMA and fs-verity should be considered orthogonal
solutions.

						- Ted

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

[Theodore Ts'o]

On Sun, Jan 28, 2018 at 04:49:25PM -0500, Theodore Ts'o wrote:
> Speaking as a kernel developer, it makes a more sense to keep things
> in the kernel,

That should have read, "keep as little as possible in the kernel".
Apologies for the bad proofreading.

Ultimately, I think the issue is fundamentally philosophical.  IMA was
designed with a very strong point of view, and assumes that its
requirements set was the only thing the that it needed to support.
Worse, it seems designed to that you can't easily reporpose for it for
different requirements; part of this is because a lot of the policy is
in the kernel, opposed to be in userspace.  I understand why that's
tempting from as security perspective (even if it does make the attack
surface much larger).

The bottom line is that I don't think fs-verity should be stretched
over the procrustrean bed of IMA.  And I am *not* asking that IMA
change; because of userspace backwards compatibility requirements, I
recognize that *that* ship has already sailed.  So ultimately,
designing something new which is minimal, and which could be *used* by
IMA, but which does not *require* IMA may be the best way to move
forward from here.

						- Ted




 and do as much in userspace as possible --- and if that
> means that the Docker client (or the package manager, etc.) needs a
> minor change to call the userspace library, that's infinitely
> preferable to keeping huge amounts of complexity in non-swappable
> kernel memory --- which increases the attack surface of the kernel,
> and so on.
> 
> So in my opinion, clean design of the kernel trumps the requirement of
> "not one change, not one jot, in the Docker client".
> 
> It could be that the requiremnts of "keep the kernel changes simple"
> and "no massive latency at file open time", means that requiremnt sets
> of fs-verity and IMA are irreconcilable.  Which is fine as far as I'm
> concerned.  Maybe IMA and fs-verity should be considered orthogonal
> solutions.
> 
> 						- Ted

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

[Mimi Zohar]

On Sun, 2018-01-28 at 16:49 -0500, Theodore Ts'o wrote:
> On Sun, Jan 28, 2018 at 10:03:10AM -0800, James Bottomley wrote:
> > 
> > OK, so we agree then that what IMA provides: a hash and potential
> > signature over the hash is sufficient input for what you want and does
> > provide existing tooling to achieve it.
> 
> Well, that's not all IMA provides.  Remmber, the 'M' in IMA is
> *measurement*.  IMA was originally about checksuming every single file
> that is opened and writing it to a long.  You could suppress it by
> using SELinux to tag files (using xattrs which are *not* signed) and
> then writing an IMA policy which tells IMA to ignore files that belong
> to a certain SE Linux tag.  This is something that I *don't* want and
> today, enabling CONFIG_IMA drags all of this (including doing text
> parsing of the IMA policy in the kernel, SELinux, etc.) into the
> kernel.

Sigh, there seems to be some confusion.  Initially, when the Integrity
Measurement Architecture (IMA) was first upstreamed, it only extended
the trusted boot concept of measuring files before use up to the OS,
but that was a long time ago.  Since then, IMA-appraisal was
upstreamed, which extends the secure boot concept of verifying
signatures up to the running OS.

Both IMA-measurement and IMA-appraisal are policy based.  You can
enable one, the other, both or none based on rules.  The rules can
further be constrained based on LSM hooks, or even further constrained
based on LSM labels.

> One of my other complaints about IMA is that it's an integrated
> solution, with a huge amount of complexity.  If it was only about file
> signing, that would be one thing, but that's actually not the case
> today.  Hence my comment about I don't want fs-verity to have a
> dependency on IMA, such that we are forced to drag in all of IMA and
> SELinux for anyone who wants to use use fs-verity.

Enabling IMA doesn't automatically require SELinux or any other LSM
labels.  The rule granularity is up to you.

> This is fine; I don't want to have to dictate changes to IMA; I'd much
> prefer to avoid the complexity instead of trying to reform it, since
> I'm sure the IMA folks will be happy to explain why there are all
> sorts of reasons why things have to be done the way it has to be done.
> For example, the assertion that the latency hit at open(2) *must* be
> there in order to kowtow to Microsoft because of its Trusted Boot
> policies; fair enough, but *I* don't care about Trusted Boot, and it's
> not fair to impose penalties on all scenarios because of a desire to
> keep Microsoft happy just for one particular use case.

Nobody is forcing you to define a measurement policy, if all you're
interested in is signature verification.   

> 
> >    1. Could the signature piece of this be done in the way IMA currently
> >       does file signatures.  We all agree "yes" on this, since a signed
> >       mekle hash head is the same size as an existing IMA signature and
> >       therefore does fit into xattrs.
> 
> Well.... not exactly.
> 
> It is fair to say that there are two parts of integrity metadata; and
> the Merkle tree can be reconstructed at file install time.
> 
> >    2. Could IMA use a merkle tree for hash verification a page at a time
> >       as part of its implementation?  I think the answer to this is yes,
> >       except the hook has to be somewhere in the page fault mechanism, so
> >       it would need some exploration and prototyping.
> 
> The way you are formulating things presumes that all of IMA has to be
> dragged into any file integrity solution.  That's begging the
> question.  As I've mentioned above, IMA has all sorts of complexity
> which is currently mandatory, and I'm not volunteering to disentagling
> the mess to make it be sane.  (And if you don't like that word, how
> about, "designed with good taste?")

The architecture is really quite simple:
	if (measurement is enabled)
		do measurement
	if (signature verification is enabled)
		do signature verification
	if (IMA-audit is enabled)
		add file signature/hash to audit/system log

Pick and choose what you're interested in.

Mimi

> 
> >    3. Could the merkle tree be cached somehow in the filesystem (probably
> >       as part of the filesystem implementaiton)?  You've already assumed
> >       "yes" for this since it's how fs-verity is proposed to work.
> 
> I don't consider this the Merkel tree to a *cache*, however because if
> you don't mind a massive latency at file open tme, you can just use
> the existing IMA mechanism.  So a core part of the design is that the
> Merkle file is stored permanently (*not* as a cache) alongside the
> file.  And if the file is renamed, the Merkle tree should come along
> for the ride.
> 
> Whether the Merkle tree is reconstructed as part of the file / package
> installation process, or whether the Merkle tree stored as part of the
> package or streamed from the app store, etc., is an implementation
> detail, and I don't think we need to prescribe one way of doing
> things.  I *do* think though we should allow for possibility where
> limitations on the local CPU power is such that it would be preferable
> for the Merkle tree to be supplied from a remote server instead of
> generated on the local system.
> 
> The problem is you have a specific use case in mind, involving the
> Docker client, where you want to store the signature in an xattr, and
> then not require any local changes to the Docker client --- and that's
> not in my requirements set, and it was *your* statement that the
> Docker client MUST NOT be modified which forced where (a) the Merkle
> tree must be reconstructed in the kernel, and (b) it must be triggered
> by setting the xattr.
> 
> My goal is to keep things simple, which means
> 
> * No parsing of the IMA policy as a text input in the kernel
> * No Merkle tree construction in the kernel (which is also true of dm-verity)
> * No magic xattr triggering
> 
> Speaking as a kernel developer, it makes a more sense to keep things
> in the kernel, and do as much in userspace as possible --- and if that
> means that the Docker client (or the package manager, etc.) needs a
> minor change to call the userspace library, that's infinitely
> preferable to keeping huge amounts of complexity in non-swappable
> kernel memory --- which increases the attack surface of the kernel,
> and so on.
> 
> So in my opinion, clean design of the kernel trumps the requirement of
> "not one change, not one jot, in the Docker client".
> 
> It could be that the requiremnts of "keep the kernel changes simple"
> and "no massive latency at file open time", means that requiremnt sets
> of fs-verity and IMA are irreconcilable.  Which is fine as far as I'm
> concerned.  Maybe IMA and fs-verity should be considered orthogonal
> solutions.
> 
> 						- Ted
> 

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

[James Bottomley]

On Sun, 2018-01-28 at 16:49 -0500, Theodore Ts'o wrote:
> On Sun, Jan 28, 2018 at 10:03:10AM -0800, James Bottomley wrote:
> > 
> > 
> > OK, so we agree then that what IMA provides: a hash and potential
> > signature over the hash is sufficient input for what you want and
> > does
> > provide existing tooling to achieve it.
> 
> Well, that's not all IMA provides.  Remmber, the 'M' in IMA is
> *measurement*.  IMA was originally about checksuming every single
> file that is opened and writing it to a long.  You could suppress it
> by using SELinux to tag files (using xattrs which are *not* signed)
> and then writing an IMA policy which tells IMA to ignore files that
> belong to a certain SE Linux tag.  This is something that I *don't*
> want and today, enabling CONFIG_IMA drags all of this (including
> doing text parsing of the IMA policy in the kernel, SELinux, etc.)
> into the kernel.

That's not actually correct.  For instance, it's not how I'm using IMA
in the cloud to give me immutability and tamperproofness.  In fact, I'm
not using IMA with selinux at all.  The only connection between them is
that they both use xattrs.

> One of my other complaints about IMA is that it's an integrated
> solution, with a huge amount of complexity.  If it was only about
> file signing, that would be one thing, but that's actually not the
> case today.

OK, so I think I need to get a tame IMA developer to explain simply
what IMA actually does before we start accusing it of things it doesn't
do (or doesn't have to do).

>   Hence my comment about I don't want fs-verity to have a
> dependency on IMA, such that we are forced to drag in all of IMA and
> SELinux for anyone who wants to use use fs-verity.
> 
> This is fine; I don't want to have to dictate changes to IMA; I'd
> much prefer to avoid the complexity instead of trying to reform it,
> since I'm sure the IMA folks will be happy to explain why there are
> all sorts of reasons why things have to be done the way it has to be
> done. For example, the assertion that the latency hit at open(2)
> *must* be there in order to kowtow to Microsoft because of its
> Trusted Boot policies; fair enough, but *I* don't care about Trusted
> Boot, and it's not fair to impose penalties on all scenarios because
> of a desire to keep Microsoft happy just for one particular use case.

OK, so I don't believe that to be true either.  Secure Boot was
something we did based on MS mandated technologies and something *some*
people though we had to impose strange policies over to please MS.
 However, IMA was never part of that secure boot solution, so trying to
tar it with the same brush is unfair (and inaccurate).

> >    1. Could the signature piece of this be done in the way IMA
> > currently
> >       does file signatures.  We all agree "yes" on this, since a
> > signed
> >       mekle hash head is the same size as an existing IMA signature
> > and
> >       therefore does fit into xattrs.
> 
> Well.... not exactly.
> 
> It is fair to say that there are two parts of integrity metadata; and
> the Merkle tree can be reconstructed at file install time.

I thought we agreed the signature need only be over the head hash of
the tree, which means it's the same size as a current IMA signature
(because they're both signatures of hashes).  I left all questions
about how we obtain the entire tree to step 3.


> >    2. Could IMA use a merkle tree for hash verification a page at a
> > time
> >       as part of its implementation?  I think the answer to this is
> > yes,
> >       except the hook has to be somewhere in the page fault
> > mechanism, so
> >       it would need some exploration and prototyping.
> 
> The way you are formulating things presumes that all of IMA has to be
> dragged into any file integrity solution.  That's begging the
> question.

The question I'm poking at is how integrity is enforced.  Right at the
moment it's a small number of security hooks but they're on the fops
gates (exec and the like).  To verify a per page hash, they'd have to
be in the mm subsystem as well (regardless of whether it's IMA or fs-
verity doing it) ... unless you're planning to ignore all the security
hooks as well.

>   As I've mentioned above, IMA has all sorts of complexity
> which is currently mandatory, and I'm not volunteering to
> disentagling the mess to make it be sane.  (And if you don't like
> that word, how about, "designed with good taste?")

This boils down to IMA is insane so I can't use it.  It's an emotional
not a technical argument.  Can we look at the pieces of IMA that you
might be able to use and make an evaluation on that.  The hooks, for
instance, exist within the kernel when CONFIG_IMA=n.

> >    3. Could the merkle tree be cached somehow in the filesystem
> > (probably
> >       as part of the filesystem implementaiton)?  You've already
> > assumed
> >       "yes" for this since it's how fs-verity is proposed to work.
> 
> I don't consider this the Merkel tree to a *cache*, however because
> if you don't mind a massive latency at file open tme, you can just
> use the existing IMA mechanism.  So a core part of the design is that
> the Merkle file is stored permanently (*not* as a cache) alongside
> the file.

That's a semantic quibble.  I think of it as a "cache" because we can
verify and derive the entire tree from the head node.  However, doing
the derivation costs, so supplying the tree is a shortcut but it's
telling us nothing we couldn't have worked out for ourselves (hence
it's a cache).  We definitely use the base of the tree to verify the
file a page at a time.

>   And if the file is renamed, the Merkle tree should come along
> for the ride.
> 
> Whether the Merkle tree is reconstructed as part of the file /
> package installation process, or whether the Merkle tree stored as
> part of the package or streamed from the app store, etc., is an
> implementation detail, and I don't think we need to prescribe one way
> of doing things.

agreed.

>   I *do* think though we should allow for possibility where
> limitations on the local CPU power is such that it would be
> preferable for the Merkle tree to be supplied from a remote server
> instead of generated on the local system.
> 
> The problem is you have a specific use case in mind, involving the
> Docker client, where you want to store the signature in an xattr, and
> then not require any local changes to the Docker client --- and
> that's not in my requirements set, and it was *your* statement that
> the Docker client MUST NOT be modified which forced where (a) the
> Merkle tree must be reconstructed in the kernel, and (b) it must be
> triggered by setting the xattr.

My goal (the reason I know all this about IMA) is actually to get some
integrity and signature verification in containers.  Your goal seems to
be the same for a non-container use case.  I really don't think we need
two completely separate mechanisms to achieve the same goal ... it's
going to create userspace confusion about which mechanism they're
supposed to be using.

> My goal is to keep things simple, which means
> 
> * No parsing of the IMA policy as a text input in the kernel
> * No Merkle tree construction in the kernel (which is also true of
> dm-verity)
> * No magic xattr triggering

So I don't actually think there's anything here that means we have to
have two solutions.

> Speaking as a kernel developer, it makes a more sense to keep things
> in the kernel, and do as much in userspace as possible --- and if
> that means that the Docker client (or the package manager, etc.)
> needs a minor change to call the userspace library, that's infinitely
> preferable to keeping huge amounts of complexity in non-swappable
> kernel memory --- which increases the attack surface of the kernel,
> and so on.
> 
> So in my opinion, clean design of the kernel trumps the requirement
> of "not one change, not one jot, in the Docker client".

OK, bad example on my part, thanks to runc and containerd I don't give
much of a toss about the docker client.  I care much more about
compliance with the container runtime standard.  At it's base that has
anything you can do to tar is fine because it uses tar to define the
image.  I buy that we can modify tools easily, but the same doesn't
apply to standards.

> It could be that the requiremnts of "keep the kernel changes simple"
> and "no massive latency at file open time", means that requiremnt
> sets of fs-verity and IMA are irreconcilable.  Which is fine as far
> as I'm concerned.  Maybe IMA and fs-verity should be considered
> orthogonal solutions.

I don't really think that's a good way to go, given they're both
mechanisms for enforcing file integrity.

James


> 						- Ted
> 

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

[Theodore Ts'o]

On Sun, Jan 28, 2018 at 06:04:52PM -0500, Mimi Zohar wrote:
> 
> Sigh, there seems to be some confusion. �Initially, when the Integrity
> Measurement Architecture (IMA) was first upstreamed, it only extended
> the trusted boot concept of measuring files before use up to the OS,
> but that was a long time ago. �Since then, IMA-appraisal was
> upstreamed, which extends the secure boot concept of verifying
> signatures up to the running OS.

Part of the problem is the documentation doesn't make any of this at
all clear.  Indeed, I'll note that Documentation/ABI/testing/ima_policy
still talks about using file system magic numbers to determine whether
or not files should be measured, and I've been given to understand you're using
a per-filesytsem flag now.

The documentation seems to strongly imply that in order to be secure,
you can't use IMA by itself, you have to use EVM as well.  Exactly
which components can be used independently is not clear, and
apparently I made the wrong guesses when trying to read through the
Linux-IMA wiki pages as well as the Gentoo pages on IMA and EVM.
Maybe it's just the documentation is badly written, but it leaves the
impression of *extreme* complexity.

I did try to play with it, but ima-evm-utils aren't packaged for
Debian, and when I tried building from source, they apparently don't
even build on Debian Testing.  (Sorry, I don't use RHEL for my
development systems.)  And I'll note the Gentoo pages warn, "don't use
on production systems".  All of which do not make for a good first
look for IMA.

> Enabling IMA doesn't automatically require SELinux or any other LSM
> labels. �The rule granularity is up to you.

Yes, but if I only want to have a dozen or so files to be data
integrity protect, it appears that it's not simple to do, *without*
using SELinux.  And anytime SELinux and "simple" go in the same
sentence, I weep a little.  Every few years I try configuring SELinux
on Debian development laptop.  And I conclude that I'm too stupid for
to configure SELinux.

							- Ted

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

[Theodore Ts'o]

On Sun, Jan 28, 2018 at 04:21:59PM -0800, James Bottomley wrote:
> OK, so I don't believe that to be true either. �Secure Boot was
> something we did based on MS mandated technologies and something *some*
> people though we had to impose strange policies over to please MS.
> �However, IMA was never part of that secure boot solution, so trying to
> tar it with the same brush is unfair (and inaccurate).

This was based on an assertion Mimi made that we had to do the full
data checksum verification at file open time due to requirements of
Trusted Boot.  I know I am incredibility privileged in that I don't
have to worry about Trusted Boot, so I don't have any personal
knowledge one way or another; this was a claim articulated by Mimi.

> The question I'm poking at is how integrity is enforced. �Right at the
> moment it's a small number of security hooks but they're on the fops
> gates (exec and the like). �To verify a per page hash, they'd have to
> be in the mm subsystem as well (regardless of whether it's IMA or fs-
> verity doing it) ... unless you're planning to ignore all the security
> hooks as well.

The fs-verity design plumbs this into the file system's readpage
methods, just like we do with fs/crypto.  Again, the idea was to make
something easy to use that would require minimal changes to the file
system (just as minimal changes are needed for fscrypt), and where you
could query the file to see if the verity bit is set, and that would
be the hook for the LSM's --- if you want to use LSM's.  Essentially
the file system would provide the mechanism (data integrity
verification cleanly hooked into the file system's readpage method)
and the policy could be done using an LSM, but it could potentially be
done via other, more simpler mechanisms.

I think one of the things that made IMA challenging was that it was a
separate, foreign body that was stapled on top of the file system.
We're using a different approach, where it is integrated into the file
system, which makes the avoidance of locking problems *much* simpler,
since we're not trying to do file reads triggered by LSM hooks.

> > So in my opinion, clean design of the kernel trumps the requirement
> > of "not one change, not one jot, in the Docker client".
> 
> OK, bad example on my part, thanks to runc and containerd I don't give
> much of a toss about the docker client. �I care much more about
> compliance with the container runtime standard. �At it's base that has
> anything you can do to tar is fine because it uses tar to define the
> image. �I buy that we can modify tools easily, but the same doesn't
> apply to standards.

OK, so what you care about the is the file format.  Yes?

So if there as a solution which enapculated the information needed to
create the fs-verity header and the PKCS7 signature in an xattr ---
which is how you carry it around in the tar image --- and when the
tarfile is unpacked, the software which does the unpacking calls a
library which checks for the xattr, removes it, writes out the
fsverity header and Merkle tree, and then calls the ioctl which sets
the "verity" bit, thus instantiating the data integrity protection,
would this meet your requirements?

In other words, the xattr in the tar file is just the method for
carrying the information; and (a) it is not how the information would
be stored in the underlying file system when it is actually used, and
(b) it requires the userspace code to do this transformation, so we
don't have to build the Merkle tree in the kernel.  Is this sufficient
for your container use case?

Whether we require IMA as a dependency for fs-verity then because a
separable question, and I think that basically boils down to (a) what
value-add does using IMA bring to fs-verity, and (b) what complexity
does IMA impose on fs-verity.  That's a pretty simple cost benefit
analysis.  And if the IMA integration is optional, that might be the
best win-win scenario.  People who want the extra value of IMA, can
pay the costs (which might include the complexity burden imposed by
inadequate documentation), and those that don't, can skip it.

	   		       	     	  	 - Ted

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

[Mimi Zohar]

On Sun, 2018-01-28 at 19:38 -0500, Theodore Ts'o wrote:
> On Sun, Jan 28, 2018 at 06:04:52PM -0500, Mimi Zohar wrote:
> > 
> > Sigh, there seems to be some confusion.  Initially, when the Integrity
> > Measurement Architecture (IMA) was first upstreamed, it only extended
> > the trusted boot concept of measuring files before use up to the OS,
> > but that was a long time ago.  Since then, IMA-appraisal was
> > upstreamed, which extends the secure boot concept of verifying
> > signatures up to the running OS.
> 
> Part of the problem is the documentation doesn't make any of this at
> all clear.

Agreed the documentation is dated and needs to be updated, especially
the wiki.

> Indeed, I'll note that Documentation/ABI/testing/ima_policy
> still talks about using file system magic numbers to determine whether
> or not files should be measured, and I've been given to understand you're using
> a per-filesystem flag now.

Defining policies based on magic file system numbers has been there
for a really long time.  Removing it would cause existing policies to
fail to load.  So I can't just remove it.

> The documentation seems to strongly imply that in order to be secure,
> you can't use IMA by itself, you have to use EVM as well.  Exactly
> which components can be used independently is not clear, and
> apparently I made the wrong guesses when trying to read through the
> Linux-IMA wiki pages as well as the Gentoo pages on IMA and EVM.
> Maybe it's just the documentation is badly written, but it leaves the
> impression of *extreme* complexity.

The basic difference between EVM and IMA is that EVM protects the file
meta-data, while IMA protects the file data.  If all you want to
verify is the file data signature, then just use IMA-appraisal.

> 
> I did try to play with it, but ima-evm-utils aren't packaged for
> Debian, and when I tried building from source, they apparently don't
> even build on Debian Testing.  (Sorry, I don't use RHEL for my
> development systems.)

I'm about to release version 1.1.  Please try the next branch
of git://git.code.sf.net/p/linux-ima/ima-evm-utils.

>  And I'll note the Gentoo pages warn, "don't use
> on production systems".  All of which do not make for a good first
> look for IMA.

We need to differentiate between IMA-measurement and IMA-appraisal
here.  Measurement isn't a problem.  The problem is signature
verification.  Until distros include file signatures in software
packages, it is difficult.  This is the main reason that IMA/EVM is
being used in the embedded environment, and not on desktops.

We've extended RPM to include file signatures.  There have been
multiple attempts to add support for including file signatures in deb
packages.  Matthew would be able to tell you if his version, the last
attempt, was upstreamed.

Stefan Berger and Mehmet Kayaalp set up distro mirrors, which include
the file signatures in the software packages, as a proof of concept.
 The file signatures are then installed with the file data.

> 
> > Enabling IMA doesn't automatically require SELinux or any other LSM
> > labels.  The rule granularity is up to you.
> 
> Yes, but if I only want to have a dozen or so files to be data
> integrity protect, it appears that it's not simple to do, *without*
> using SELinux.  And anytime SELinux and "simple" go in the same
> sentence, I weep a little.  Every few years I try configuring SELinux
> on Debian development laptop.  And I conclude that I'm too stupid for
> to configure SELinux.

A lot of people have requested being able to identify files based on
pathnames.  I don't need to tell you this isn't safe from a security
perspective.  So how would you identify these few files?  I doubt you
are planning on hard coding them.  If you have a generic solution, I
would really be interested in hearing it.

There are a few files which can be identified based on the LSM hook.
 For example, the kernel_read_file_from_path/fd calls the pre and post
security_kernel_read_file() LSM hooks, which can be used to verify the
kexec kernel image, kexec initramfs, kernel modules and firmware.

Mimi

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

[Theodore Ts'o]

On Sun, Jan 28, 2018 at 08:53:41PM -0500, Mimi Zohar wrote:
> A lot of people have requested being able to identify files based on
> pathnames. �I don't need to tell you this isn't safe from a security
> perspective. �So how would you identify these few files? �I doubt you
> are planning on hard coding them. �If you have a generic solution, I
> would really be interested in hearing it.

So what we are implementing with fs-verity is that verification is
enabled by setting a flag in the inode ("the verity bit") which causes
the file system to enforce the data integrity checks.  This bit can be
checked by using the FS_IOC_GETFLAGS ioctl (like any of the other
existing file system flags, such as immutable, append-only, no-COW,
etc.)

What this means is that it would be possible for userspace application
to simply open a file (which might, for example, be a privileged APK)
and before using it, check the verity bit via the open file
descriptor.  If the verity bit is set, then the userspace application
can safely read from the file, and no that it hasn't been tampered
with, even via an off-line evil maid attack.  In this particular case
case, there isn't even a need to use SELinux, or indeed, any LSM at
all.  No need to compile in EVM, no need to compile in IMA, no need to
compile in SELinux, etc.

In other use cases, whether or not a file has the verity bit set could
be used by an LSM that wishes to make policy restrictions --- for
example: "if the file is setuid, then the verity bit *must* be set".
Or there could be a policy where all executables *must* have the
verity bit set.  This model has the advantage of a very clean
separation between the policy and the mechanism, where the mechanism
exports a single bit, "is this file one which is protected by the
verity bit"?

Granted, it is a different model than what IMA/EVM use.  But it is
much simpler, and it is optimized for use cases where most of the
files might not be data integrity protected (perhaps because most of
then security-critical files are located on a read-only volume being
protected using dm-verity).

Because we use a Merkle tree, we are also making the tradeoff between
a complete verification of the entire contents of the file at file
open time (which imposes a file open latency, and means that if the
file can be tampered after it is opened, IMA won't detect the
problem), versus verification at readpage time (which means that you
might fail while reading the file, instead of finding out at open
time).  This is again consistent with dm-verity, where we do not
attempt to verify the checksum of the entire block device at system
startup; instead we check on each block read, and if the verification
fails, we fail the read in question.

For some use cases, the use of a full-file hash ala today's
IMA-Appraisal might be a better choice.  I have never claimed that
fs-verity was intended to be a replacemnt for IMA. 

Cheers,

						- Ted

P.S.  I wonder if it was a mistake to not choose a whole new name for
IMA-Appraisal.  There are lots of documentations on the web which talk
about "IMA", and it's not clear if it supposed to mean "IMA-Measure",
or a generic term encompassing "IMA-Appraisal" and "IMA-Meaure".  One
might be able to guess based on how out-of-date the rest of web page
happens to be, but it's really not clear.

Also, the two concepts are quite different, and data integrity via
checking a digitally signed hash is only partially related to
"measuring" a file.  Perhaps it's related by virtue of the fact that
you have to calculate a cryptographic checksum over the entire file.
But once you get to data integrity protected via a Merkle tree at file
read time, this is extremely quite far away from any traditional
definition of "measurement".  So purely from a naming convention,
perhaps trying to take data integrity verification using Merkle trees
should forcing it into the IMA framework might not be such a great
fit.

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

[Mimi Zohar]

On Sun, 2018-01-28 at 21:38 -0500, Theodore Ts'o wrote:
> On Sun, Jan 28, 2018 at 08:53:41PM -0500, Mimi Zohar wrote:
> > A lot of people have requested being able to identify files based on
> > pathnames.  I don't need to tell you this isn't safe from a security
> > perspective.  So how would you identify these few files?  I doubt you
> > are planning on hard coding them.  If you have a generic solution, I
> > would really be interested in hearing it.
> 
> So what we are implementing with fs-verity is that verification is
> enabled by setting a flag in the inode ("the verity bit") which causes
> the file system to enforce the data integrity checks.  This bit can be
> checked by using the FS_IOC_GETFLAGS ioctl (like any of the other
> existing file system flags, such as immutable, append-only, no-COW,
> etc.)

> What this means is that it would be possible for userspace application
> to simply open a file (which might, for example, be a privileged APK)
> and before using it, check the verity bit via the open file
> descriptor.  If the verity bit is set, then the userspace application
> can safely read from the file, and no that it hasn't been tampered
> with, even via an off-line evil maid attack.  In this particular case
> case, there isn't even a need to use SELinux, or indeed, any LSM at
> all.  No need to compile in EVM, no need to compile in IMA, no need to
> compile in SELinux, etc.

So the filesystem is enforcing a policy set by userspace.  What is
protecting that policy?  Can the verity bit be unset once set?

> In other use cases, whether or not a file has the verity bit set could
> be used by an LSM that wishes to make policy restrictions --- for
> example: "if the file is setuid, then the verity bit *must* be set".
> Or there could be a policy where all executables *must* have the
> verity bit set.  This model has the advantage of a very clean
> separation between the policy and the mechanism, where the mechanism
> exports a single bit, "is this file one which is protected by the
> verity bit"?
> 
> Granted, it is a different model than what IMA/EVM use.  But it is
> much simpler, and it is optimized for use cases where most of the
> files might not be data integrity protected (perhaps because most of
> then security-critical files are located on a read-only volume being
> protected using dm-verity).
> 
> Because we use a Merkle tree, we are also making the tradeoff between
> a complete verification of the entire contents of the file at file
> open time (which imposes a file open latency, and means that if the
> file can be tampered after it is opened, IMA won't detect the
> problem), versus verification at readpage time (which means that you
> might fail while reading the file, instead of finding out at open
> time).  This is again consistent with dm-verity, where we do not
> attempt to verify the checksum of the entire block device at system
> startup; instead we check on each block read, and if the verification
> fails, we fail the read in question.

True IMA verifies the file signature on open, but any attempt to open
signed files for write will immediately fail, as they are considered
immutable.

> For some use cases, the use of a full-file hash ala today's
> IMA-Appraisal might be a better choice.  I have never claimed that
> fs-verity was intended to be a replacemnt for IMA. 
> 
> Cheers,
> 
> 						- Ted
> 
> P.S.  I wonder if it was a mistake to not choose a whole new name for
> IMA-Appraisal.  There are lots of documentations on the web which talk
> about "IMA", and it's not clear if it supposed to mean "IMA-Measure",
> or a generic term encompassing "IMA-Appraisal" and "IMA-Meaure".  One
> might be able to guess based on how out-of-date the rest of web page
> happens to be, but it's really not clear.

[A bit of history: originally EVM was enforcing both file data and
meta-data integrity.]
  
> Also, the two concepts are quite different, and data integrity via
> checking a digitally signed hash is only partially related to
> "measuring" a file.  Perhaps it's related by virtue of the fact that
> you have to calculate a cryptographic checksum over the entire file.

Right, the file hash is calculated once and used for measurement,
appraisal, and audit.  The measurement list can be used to remotely
attest to the integrity of the running system.  The hash is used for
local signature verification.  The hash included in the audit record
can then be used for forensics/system analytics.      

> But once you get to data integrity protected via a Merkle tree at file
> read time, this is extremely quite far away from any traditional
> definition of "measurement".  So purely from a naming convention,
> perhaps trying to take data integrity verification using Merkle trees
> should forcing it into the IMA framework might not be such a great
> fit.

At what point is the signature on the Merkle tree hash verified?  I
can't imagine it being done every time a page is read.  It must be
done and the result cached at file open.

Mimi

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

[Theodore Ts'o]

On Sun, Jan 28, 2018 at 10:39:10PM -0500, Mimi Zohar wrote:
> So the filesystem is enforcing a policy set by userspace. �What is
> protecting that policy? �Can the verity bit be unset once set?

No.  Well, technically it would be safe to allow the bit to be unset
if the file is not in use (not open or mmaped), but in practice it
would be simplest to not allow it to be unset.

> > But once you get to data integrity protected via a Merkle tree at file
> > read time, this is extremely quite far away from any traditional
> > definition of "measurement".  So purely from a naming convention,
> > perhaps trying to take data integrity verification using Merkle trees
> > should forcing it into the IMA framework might not be such a great
> > fit.
> 
> At what point is the signature on the Merkle tree hash verified? �I
> can't imagine it being done every time a page is read. �It must be
> done and the result cached at file open.

The page is verified each time it is read from the storage device (in
practice, flash).  Why can't you imagine this working?  Are you
concerned from a performance perspective, or because IMA has different
security requirements/expectations/assumptions?

What I am proposing is completely analogous to how dm-verity works.
In dm-verity, we verify each block (whether it be file system metadata
block or a file data block) when it is read from flash.  If you own a
modern Android device, or a Chrome OS device, the system software is
protected using dm-verity.  The only difference between this fs-verity
proposal and dm-verity is that it's being done at the file level
instead of the block device level.

						- Ted

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

[Theodore Ts'o]

On Sun, Jan 28, 2018 at 10:39:10PM -0500, Mimi Zohar wrote:
> At what point is the signature on the Merkle tree hash verified? �I
> can't imagine it being done every time a page is read. �It must be
> done and the result cached at file open.

Sorry, I misread your question.  The signature on the Merkle tree hash
is verified the file is opened, and then validated Merkle tree hash is
cached in the in-memory inode data structure.

This is similar to how we cache the per-file key in fscrypt; once the
key is derived, we keep it in the inode cache until the inode is
dropped from the inode cache, or after a userspace request to revoke
all keys derived from a user's login key (which is triggered when the
user logs out of their ChromeOS session).

							- Ted

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

[James Bottomley]

On Sun, 2018-01-28 at 10:19 -0800, Chuck Lever wrote:
> 
> > 
> > On Jan 28, 2018, at 10:03 AM, James Bottomley <James.Bottomley@Hans
> > enPartnership.com> wrote:
> > 
> > On Sat, 2018-01-27 at 21:46 -0500, Theodore Ts'o wrote:
> > > 
> > > On Sat, Jan 27, 2018 at 08:19:19AM -0800, James Bottomley wrote:
> > > > 
> > > > 
> > > > I certainly buy this approach, and it fits well with the
> > > > limited
> > > > data size there is in xattrs but Ted said in the initial
> > > > proposal
> > > > the entire tree would be present in the file.  I can't see a
> > > > need
> > > > for supplying the entire tree rather than reconstructing it but
> > > > maybe there's an android use case I'm not seeing (Like not
> > > > wanting
> > > > to waste limited CPU power).
> > > 
> > > You can certainly reconstruct the Merkle tree at install time,
> > > but it
> > > does need to be saved on disk.  My assumption was that Merkle
> > > tree
> > > would be written to disk by userspace, along with the fs-verity
> > > header, simply because it would make things much simpler for the
> > > kernel, and in my view you *have* to modify userspace in some
> > > way.
> > 
> > OK, so we agree then that what IMA provides: a hash and potential
> > signature over the hash is sufficient input for what you want and
> > does
> > provide existing tooling to achieve it.
> > 
> > > 
> > > > 
> > > > Just so I understand the mechanics: The xattr would contain the
> > > > head node.  When this is written, the tree would be
> > > > reconstructed
> > > > from the file and verified.  If it verifies, it must be stored
> > > > in
> > > > the filesystem data somehow (or at least the lowest layer), so
> > > > all
> > > > subsequent uses of the file can proceed from the per page hash
> > > > even
> > > > after unmount and remount?  Then I certainly think it suits
> > > > both
> > > > cases.
> > > 
> > > Yes.... in theory we could store the bare root hash (and some
> > > other
> > > bare minmum information, such as the PKCS7 signature and the
> > > elments
> > > of a fs-verity header) in an xattr, and setting that xattr would
> > > magically cause the merkle tree to be reconstructed and stored on
> > > disk.  But most of the file sytem developers have considered the
> > > use
> > > of setting or clearing xattrs to cause magically code paths to be
> > > executed to be an extremely bad idea.
> > 
> > Hang on, you've jumped straight from a discussion of ideas to an
> > insane
> > implementation ... can we take a step back?  I'm thinking of three
> > separate things
> > 
> >   1. Could the signature piece of this be done in the way IMA
> > currently
> >      does file signatures.  We all agree "yes" on this, since a
> > signed
> >      mekle hash head is the same size as an existing IMA signature
> > and
> >      therefore does fit into xattrs.
> >   2. Could IMA use a merkle tree for hash verification a page at a
> > time
> >      as part of its implementation?  I think the answer to this is
> > yes,
> >      except the hook has to be somewhere in the page fault
> > mechanism, so
> >      it would need some exploration and prototyping.
> >   3. Could the merkle tree be cached somehow in the filesystem
> > (probably
> >      as part of the filesystem implementaiton)?  You've already
> > assumed
> >      "yes" for this since it's how fs-verity is proposed to work.
> > 
> > So the issue we could discuss is how all this is tied
> > together.  The
> > implementation could be your special format file for 3. but with
> > the
> > head hash signature in an xattr.  What we get back on tar would be
> > the
> > ordinary file + xattr, but perhaps tar could use this to
> > reconstruct
> > the magic file on untar.
> > 
> > I do think the "special format magic file" is a violation of the
> > unix
> > principles of files being "just files" but if it's the only way, I
> > suppose I could be persuaded.  However, this part should also be
> > discussed; it does seem like, to satisfy unix principles, the
> > merkle
> > tree should be provided separately from the file, possibly as a
> > fcntl().
> 
> For NFS, storing the tree or even an IMA signature in a trusted xattr
> is currently off the table because the protocol does not convey
> non-user xattrs.

OK, but are you sure fixing that with a binary format interpreter is
the correct thing to do?  I think it should work both for IMA and
selinux if you go this road, right?

>  My interest is finding a way to get binary signing
> without the need of the xattr.
> 
> Interestingly, Solaris puts the signature in an ELF header. That
> would certainly work for NFS.

That would work ... sort of the ELF equivalent of authenticode.
 However, it only works for binaries ... what about the IMA uses of non
binary files?

James


> 
> > 
> > James
> > 
> > > 
> > >   And since I don't really care about the use case, I can let
> > > *you*
> > > try to convince Cristoph and Al Viro that his is a good idea,
> > > despite
> > > the general agreemnt by all file system developers that we've
> > > been
> > > there, done that, decided it was a really bad idea, and let's
> > > never
> > > ever do that again.  (And then you can get some of the "the IMA
> > > people are insane" taint on yourself.  :-)
> > > 
> > >     	    	    	     	 	- Ted
> 
> --
> Chuck Lever
> 
> 
> 

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

[Mimi Zohar]

On Sun, 2018-01-28 at 23:50 -0500, Theodore Ts'o wrote:
> On Sun, Jan 28, 2018 at 10:39:10PM -0500, Mimi Zohar wrote:
> > At what point is the signature on the Merkle tree hash verified?  I
> > can't imagine it being done every time a page is read.  It must be
> > done and the result cached at file open.
> 
> Sorry, I misread your question.  The signature on the Merkle tree hash
> is verified the file is opened, and then validated Merkle tree hash is
> cached in the in-memory inode data structure.

Let's assume for the moment that there are valid, safe use cases for
fs-verity.  (Defining under which circumstances the fs-verity
integrity verification method is safe to use, is a separate
discussion.)

The LSM security_file_open hook is where fs-verity and IMA meet.  The
fs-verity Merkle tree hash signature would be another IMA-appraisal
integrity verification method.

For those that are interested in attesting to the measurement list or
including the file hash/signatures in the audit log, the same
mechanisms that currently exist would be in place for using the fs-
verity merkle tree signature.  The same mechanisms that are in place
for including file signatures in software packages could be re-used.

Bringing it all together, what is needed?
- the signature of the Merkle tree hash
- a method for validating the signature
- a method for knowing if fs-verity is enabled on the system
A mode where fs-verity can not be disabled on the local, running
system, once enabled.
- lastly, a policy.  Just because a file has a signature, does not
necessarily imply that it should be verified.

A decision was made years ago, at the time when LSMs "just" enforced
mandatory access control (MAC), that there would be a clear division
between integrity and MAC, totally independent of each other.  Today,
LSMs do other things than enforce MAC, but this separation still
exists.

With Matthew Garrett's patch set this division will continue to exist,
but will be blurred by an LSM calling the integrity subsystem
directly.

Mimi

> This is similar to how we cache the per-file key in fscrypt; once the
> key is derived, we keep it in the inode cache until the inode is
> dropped from the inode cache, or after a userspace request to revoke
> all keys derived from a user's login key (which is triggered when the
> user logs out of their ChromeOS session).
> 
> 							- Ted
> 

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

[Mimi Zohar]

On Mon, 2018-01-29 at 07:09 -0500, Mimi Zohar wrote:

> Bringing it all together, what is needed?
> - the signature of the Merkle tree hash
> - a method for validating the signature
> - a method for knowing if fs-verity is enabled on the system
> A mode where fs-verity can not be disabled on the local, running
> system, once enabled.
> - lastly, a policy.  Just because a file has a signature, does not
> necessarily imply that it should be verified.

Before people start saying that the policy doesn't belong in IMA,
maybe it doesn't, but let me describe a couple of use cases to
illustrate the problems:

- On systems that support multiple types of signatures, it's important
to be able to define which signature types are acceptable, or for that
matter if a file hash suffices (normally used for mutable files), on a
per file basis.

- Similarly, suppose the trusted keyring contains multiple keys.  I've
installed software from multiple software providers and loaded their
public keys on the trusted keyring.  Is using any key to verify the
file signature acceptable?  How would you indicate which key is
acceptable for which file.

For embedded or closed systems, a single key can be used to sign all
files, but for the generic case, like our laptops, this doesn't scale.

Mimi

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

[Chuck Lever]

> On Jan 29, 2018, at 1:39 AM, James Bottomley <James.Bottomley@HansenPartnership.com> wrote:
> 
> On Sun, 2018-01-28 at 10:19 -0800, Chuck Lever wrote:
>> 
>>> 
>>> On Jan 28, 2018, at 10:03 AM, James Bottomley <James.Bottomley@Hans
>>> enPartnership.com> wrote:
>>> 
>>> On Sat, 2018-01-27 at 21:46 -0500, Theodore Ts'o wrote:
>>>> 
>>>> On Sat, Jan 27, 2018 at 08:19:19AM -0800, James Bottomley wrote:
>>>>> 
>>>>> 
>>>>> I certainly buy this approach, and it fits well with the
>>>>> limited
>>>>> data size there is in xattrs but Ted said in the initial
>>>>> proposal
>>>>> the entire tree would be present in the file.  I can't see a
>>>>> need
>>>>> for supplying the entire tree rather than reconstructing it but
>>>>> maybe there's an android use case I'm not seeing (Like not
>>>>> wanting
>>>>> to waste limited CPU power).
>>>> 
>>>> You can certainly reconstruct the Merkle tree at install time,
>>>> but it
>>>> does need to be saved on disk.  My assumption was that Merkle
>>>> tree
>>>> would be written to disk by userspace, along with the fs-verity
>>>> header, simply because it would make things much simpler for the
>>>> kernel, and in my view you *have* to modify userspace in some
>>>> way.
>>> 
>>> OK, so we agree then that what IMA provides: a hash and potential
>>> signature over the hash is sufficient input for what you want and
>>> does
>>> provide existing tooling to achieve it.
>>> 
>>>> 
>>>>> 
>>>>> Just so I understand the mechanics: The xattr would contain the
>>>>> head node.  When this is written, the tree would be
>>>>> reconstructed
>>>>> from the file and verified.  If it verifies, it must be stored
>>>>> in
>>>>> the filesystem data somehow (or at least the lowest layer), so
>>>>> all
>>>>> subsequent uses of the file can proceed from the per page hash
>>>>> even
>>>>> after unmount and remount?  Then I certainly think it suits
>>>>> both
>>>>> cases.
>>>> 
>>>> Yes.... in theory we could store the bare root hash (and some
>>>> other
>>>> bare minmum information, such as the PKCS7 signature and the
>>>> elments
>>>> of a fs-verity header) in an xattr, and setting that xattr would
>>>> magically cause the merkle tree to be reconstructed and stored on
>>>> disk.  But most of the file sytem developers have considered the
>>>> use
>>>> of setting or clearing xattrs to cause magically code paths to be
>>>> executed to be an extremely bad idea.
>>> 
>>> Hang on, you've jumped straight from a discussion of ideas to an
>>> insane
>>> implementation ... can we take a step back?  I'm thinking of three
>>> separate things
>>> 
>>>   1. Could the signature piece of this be done in the way IMA
>>> currently
>>>      does file signatures.  We all agree "yes" on this, since a
>>> signed
>>>      mekle hash head is the same size as an existing IMA signature
>>> and
>>>      therefore does fit into xattrs.
>>>   2. Could IMA use a merkle tree for hash verification a page at a
>>> time
>>>      as part of its implementation?  I think the answer to this is
>>> yes,
>>>      except the hook has to be somewhere in the page fault
>>> mechanism, so
>>>      it would need some exploration and prototyping.
>>>   3. Could the merkle tree be cached somehow in the filesystem
>>> (probably
>>>      as part of the filesystem implementaiton)?  You've already
>>> assumed
>>>      "yes" for this since it's how fs-verity is proposed to work.
>>> 
>>> So the issue we could discuss is how all this is tied
>>> together.  The
>>> implementation could be your special format file for 3. but with
>>> the
>>> head hash signature in an xattr.  What we get back on tar would be
>>> the
>>> ordinary file + xattr, but perhaps tar could use this to
>>> reconstruct
>>> the magic file on untar.
>>> 
>>> I do think the "special format magic file" is a violation of the
>>> unix
>>> principles of files being "just files" but if it's the only way, I
>>> suppose I could be persuaded.  However, this part should also be
>>> discussed; it does seem like, to satisfy unix principles, the
>>> merkle
>>> tree should be provided separately from the file, possibly as a
>>> fcntl().
>> 
>> For NFS, storing the tree or even an IMA signature in a trusted xattr
>> is currently off the table because the protocol does not convey
>> non-user xattrs.
> 
> OK, but are you sure fixing that with a binary format interpreter is
> the correct thing to do?  I think it should work both for IMA and
> selinux if you go this road, right?

NFSv4.2 does have the ability to convey security labels between NFS
client and server. One thing that has been suggested is to define a
security label that can store information such as file capabilities.
The same tactic could be used to store a limited size item such as
the signed root hash.

Given the ability to reconstitute the Merkle tree instead of storing
it, that might be enough to allow NFS to play (using the mechanism
that you and Ted are developing here).


>> My interest is finding a way to get binary signing
>> without the need of the xattr.
>> 
>> Interestingly, Solaris puts the signature in an ELF header. That
>> would certainly work for NFS.
> 
> That would work ... sort of the ELF equivalent of authenticode.
>  However, it only works for binaries ... what about the IMA uses of non
> binary files?

Fair enough, though I'm not sure Oracle (for example) has a non-
executable use case. We are focusing largely on similar virtualization
use cases as yours.


> James
> 
> 
>> 
>>> 
>>> James
>>> 
>>>> 
>>>>   And since I don't really care about the use case, I can let
>>>> *you*
>>>> try to convince Cristoph and Al Viro that his is a good idea,
>>>> despite
>>>> the general agreemnt by all file system developers that we've
>>>> been
>>>> there, done that, decided it was a really bad idea, and let's
>>>> never
>>>> ever do that again.  (And then you can get some of the "the IMA
>>>> people are insane" taint on yourself.  :-)
>>>> 
>>>>     	    	    	     	 	- Ted
>> 
>> --
>> Chuck Lever

--
Chuck Lever

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

[Michael Halcrow]

I'm working on an implementation of fs-verity.

On Thu, Jan 25, 2018 at 04:47:46PM -0800, James Bottomley wrote:
> The cost of this is presumably one hash per page in the tree, so it
> costs quite a bit in terms of space. �Presumably the hash tree is
> also dynamically resident meaning a page fault could now also
> potentially fault in the hash tree, leading to a lot of sub optimal
> I/O patterns?

Good observation.  I'm managing all of the data pages and their
associated authenticated dictionary structure (i.e., Merkle tree)
pages in the same (existing) inode page cache.  I'm determining what
the set of pages are, and for any auth pages not up-to-date in the
cache, I'm issuing the read request for those pages together with the
data pages.  I expect that any block-level optimizations that normally
occur with data pages will occur with both the data and auth pages.

I'm introducing a new shared control structure for the group of bio
structs that cover all of the pages.  Since all of the dependent auth
pages that aren't up-to-date in the cache need to complete before we
can complete the data page, the I/O completion is decrementing the
refcount of the shared data structure and measuring the pages in the
bio.  The last to decrement owns walking all bio structs in the group
and performing the page completion ops (set error/up-to-date and
unlock) after validating the hash values.

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

[Andreas Dilger]

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

On Jan 28, 2018, at 6:03 PM, Theodore Ts'o <tytso@mit.edu> wrote:
> 
> So if there as a solution which enapculated the information needed to
> create the fs-verity header and the PKCS7 signature in an xattr ---
> which is how you carry it around in the tar image --- and when the
> tarfile is unpacked, the software which does the unpacking calls a
> library which checks for the xattr, removes it, writes out the
> fsverity header and Merkle tree, and then calls the ioctl which sets
> the "verity" bit, thus instantiating the data integrity protection,
> would this meet your requirements?
> 
> In other words, the xattr in the tar file is just the method for
> carrying the information; and (a) it is not how the information would
> be stored in the underlying file system when it is actually used, and
> (b) it requires the userspace code to do this transformation, so we
> don't have to build the Merkle tree in the kernel.  Is this sufficient
> for your container use case?

Why would you throw away the xattr signature at that point?  That would
still be useful to store back into a new tarball or other backup of the
file, and is also useful for external tools to verify (e.g. bittorrent,
maybe rsync or others in the future), especially if it is a common format.

That doesn't mean storing the whole fs-verity tree in an xattr (though
that could also be done with the ext4 xattr inode feature), nor does it
imply that this is a "magic" xattr that causes the fs-verity tree to
be created when written.  It would just be an xattr that stores the
top-level hash of the Merkle tree to expose to userspace.

Also, the Merkle tree should be computed with fixed-size leaf blocks
like 1KB or 4KB, so that userspace doesn't need to know details like the
underlying fs blocksize.  The actual on-disk fs-verity tree can be stored
in fs blocksize units, and if the blocksize is larger than the leaf blocks
it would just store a higher-level node in the Merkle tree.

We actually worked on a design for this years ago with Lustre+ZFS, with
sending higher-level nodes in the Merkle tree over the network for the
RPC checksum so that it is independent of the client/server PAGE_SIZE,
the RPC size and the underlying fs blocksize, but this would also be
useful for storage in tarballs or for read/write requests with fs-verity.

For more details see:
http://wiki.old.lustre.org/images/c/c1/End-to-End-Integrity-2009-06-15.pdf

Cheers, Andreas






[-- Attachment #2: Message signed with OpenPGP --]
[-- Type: application/pgp-signature, Size: 873 bytes --]

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

[Theodore Ts'o]

On Mon, Jan 29, 2018 at 07:09:01AM -0500, Mimi Zohar wrote:
> 
> The LSM security_file_open hook is where fs-verity and IMA meet. �The
> fs-verity Merkle tree hash signature would be another IMA-appraisal
> integrity verification method.

I wasn't planning on using the file open hook for fs-verity at all,
since the merkle hash signature is going to be cached in the per-file
system inode --- e.g., for ext4, it would be stored in EXT4_I(inode),
aka "struct ext4_inode_info".

> For those that are interested in attesting to the measurement list or
> including the file hash/signatures in the audit log, the same
> mechanisms that currently exist would be in place for using the fs-
> verity merkle tree signature. �The same mechanisms that are in place
> for including file signatures in software packages could be re-used.

This is *your* set of requiremnets, not mine.  If it's easy to do,
that's fine.  But if it doesn't, piling on extra requirements which
fs-verity can't meet is not a proof of fs-verity being not fit for
purpose, at least some use cases (e.g,. the ones we are envisioning
for fs-verity).

Again, I'm not the one arguing for IMA/fs-verity integration, and
while I am happy to work with IMA if at all possible, I am *not*
interested in compromising the fs-verity use case, or adding vast
amounts of complexity to fs-verity just to confirm to the IMA
architecture.  (That is, any complexity will need to be in optional
userspace components, such as what I've been discussing with James to
support his docker use case, or in the security/integrity subtree.  I
really *don't* want to deal with unnecessary complexity into fs/ext4,
fs/f2fs, or fs/verity.)

> Bringing it all together, what is needed?
> - the signature of the Merkle tree hash
> - a method for validating the signature
> - a method for knowing if fs-verity is enabled on the system
> A mode where fs-verity can not be disabled on the local, running
> system, once enabled.
> - lastly, a policy. �Just because a file has a signature, does not
> necessarily imply that it should be verified.

So I want to support a very simple case where the policy is simply
"the public key needed to verify the PKCS7 signing block is in a
trusted keyring".

If someone needs something more complex than the simple "key is in the
trusted keyring", I'm happy to say that the right answer is to use the
LSM hooks, and it should be straight forward to provide interfaces so
that the LSM can determine that file system supports verity and the
file has the verity bit set.  The LSM could also apply additional
restrictions (if the SELinux file type is supersekrit_t, then only a
smaller set of keys will be allowed to be used to sign the PKCS7
signature block).

Is this sufficient to allow fs-verity the ability to use IMA, if the
policy so requests it?

						- Ted

P.S.  I should note that we already have examples of data integrity
functionality that doesn't go through security/integrity.  I refer you
to diginally signed kernel modules (which do not use IMA), or
dm-verity (also not mediated through IMA).  And the existence of data
integrity functions that don't use security/integrity has not caused
the security programmers union to show up and break knuckles, just as
the Teamsters Union might have done if they had discovered that
programmers were carrying networking gear into Interop (back when it
was in San Jose) without being accredited union members.

My original intent was for fs-verity to be much like dm-verity.  That
is, something simple doesn't require a huge policy machinery just to
use it.  If others are interested in using fs-verity in a much more
complex way, or as part of a Rube Goldberg arrangement of security
modules and policies, that's fine.  I just want that mode to be
optional.

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

[James Bottomley]

On Mon, 2018-01-29 at 10:22 -0500, Chuck Lever wrote:
> > On Jan 29, 2018, at 1:39 AM, James Bottomley <James.Bottomley@Hanse
> > nPartnership.com> wrote:
> > On Sun, 2018-01-28 at 10:19 -0800, Chuck Lever wrote:
[...]
> > > > I do think the "special format magic file" is a violation of
> > > > the unix principles of files being "just files" but if it's the
> > > > only way, I suppose I could be persuaded.  However, this part
> > > > should also be discussed; it does seem like, to satisfy unix
> > > > principles, the merkle tree should be provided separately from
> > > > the file, possibly as a fcntl().
> > > 
> > > For NFS, storing the tree or even an IMA signature in a trusted
> > > xattr is currently off the table because the protocol does not
> > > convey non-user xattrs.
> > 
> > OK, but are you sure fixing that with a binary format interpreter
> > is the correct thing to do?  I think it should work both for IMA
> > and selinux if you go this road, right?
> 
> NFSv4.2 does have the ability to convey security labels between NFS
> client and server. One thing that has been suggested is to define a
> security label that can store information such as file capabilities.
> The same tactic could be used to store a limited size item such as
> the signed root hash.

In xattr terms, IMA *is* a security label (it's under the "security."
xattr namespace), so that should work for both IMA and selinux, so it
sounds like the problem is solved on V4.2+

> Given the ability to reconstitute the Merkle tree instead of storing
> it, that might be enough to allow NFS to play (using the mechanism
> that you and Ted are developing here).

To me that's an implementation detail.  The only problem is if we need
to provide the tree instead of reconstructing it, how should that be
done?

> > > My interest is finding a way to get binary signing
> > > without the need of the xattr.
> > > 
> > > Interestingly, Solaris puts the signature in an ELF header. That
> > > would certainly work for NFS.
> > 
> > That would work ... sort of the ELF equivalent of authenticode.
> >  However, it only works for binaries ... what about the IMA uses of
> > non binary files?
> 
> Fair enough, though I'm not sure Oracle (for example) has a non-
> executable use case. We are focusing largely on similar
> virtualization use cases as yours.

Even in my use case, I want to provide a mechanism to make *some*
configuration immutable, which means applying signatures to non-binary
files.  I expect the amount of config files which can be made immutable
to grow as the OS people work on separating /etc from /run.

James

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

[Mimi Zohar]

On Mon, 2018-01-29 at 18:02 -0500, Theodore Ts'o wrote:
> On Mon, Jan 29, 2018 at 07:09:01AM -0500, Mimi Zohar wrote:
> > 
> > The LSM security_file_open hook is where fs-verity and IMA meet.  The
> > fs-verity Merkle tree hash signature would be another IMA-appraisal
> > integrity verification method.
> 
> I wasn't planning on using the file open hook for fs-verity at all,
> since the merkle hash signature is going to be cached in the per-file
> system inode --- e.g., for ext4, it would be stored in EXT4_I(inode),
> aka "struct ext4_inode_info".

Ok, so if not at open, at what point do you plan on validating the
merkle hash signature?

> > For those that are interested in attesting to the measurement list or
> > including the file hash/signatures in the audit log, the same
> > mechanisms that currently exist would be in place for using the fs-
> > verity merkle tree signature.  The same mechanisms that are in place
> > for including file signatures in software packages could be re-used.
> 
> This is *your* set of requiremnets, not mine.  If it's easy to do,
> that's fine.  But if it doesn't, piling on extra requirements which
> fs-verity can't meet is not a proof of fs-verity being not fit for
> purpose, at least some use cases (e.g,. the ones we are envisioning
> for fs-verity).

That didn't sound like requirements to me, but more a benefit
statement.

> Again, I'm not the one arguing for IMA/fs-verity integration, and
> while I am happy to work with IMA if at all possible, I am *not*
> interested in compromising the fs-verity use case, or adding vast
> amounts of complexity to fs-verity just to confirm to the IMA
> architecture.  (That is, any complexity will need to be in optional
> userspace components, such as what I've been discussing with James to
> support his docker use case, or in the security/integrity subtree.  I
> really *don't* want to deal with unnecessary complexity into fs/ext4,
> fs/f2fs, or fs/verity.)

I agree with you that the integrity architecture needs to be easily
extendsible to support different integrity authentication methods.
 The list, below, is a set of fs-verity functions needed to be
exported for IMA.  Hopefully I didn't miss anything.

> > Bringing it all together, what is needed?
> > - the signature of the Merkle tree hash
> > - a method for validating the signature
> > - a method for knowing if fs-verity is enabled on the system
> > A mode where fs-verity can not be disabled on the local, running
> > system, once enabled.
> > - lastly, a policy.  Just because a file has a signature, does not
> > necessarily imply that it should be verified.
> 
> So I want to support a very simple case where the policy is simply
> "the public key needed to verify the PKCS7 signing block is in a
> trusted keyring".

Which trusted keyring?  How is the keyring populated?  What prevents
other keys from being added to that keyring?

So the implied policy is that no signatures will be verified unless
userspace turns the bit on.  So you're trust is based in userspace.

> If someone needs something more complex than the simple "key is in the
> trusted keyring", I'm happy to say that the right answer is to use the
> LSM hooks, and it should be straight forward to provide interfaces so
> that the LSM can determine that file system supports verity and the
> file has the verity bit set.  The LSM could also apply additional
> restrictions (if the SELinux file type is supersekrit_t, then only a
> smaller set of keys will be allowed to be used to sign the PKCS7
> signature block).

Interesting, so there is an additional policy limiting which keys may
be used based on an LSM labels, if so desired.

> Is this sufficient to allow fs-verity the ability to use IMA, if the
> policy so requests it?

- A function to verify that the kernel supports and is currently enforcing verity.
- A function to know if the file is in policy and has a signature.
 Different return codes.
- A function to force re-validation of the file signature.
- Access to the signature, wherever it might be stored, for inclusion
in the measurement list and audit log.
(- Possibly access to the public keys for the remote attestation
server.)

Mimi

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

[Theodore Ts'o]

On Tue, Jan 30, 2018 at 06:25:02PM -0500, Mimi Zohar wrote:
> On Mon, 2018-01-29 at 18:02 -0500, Theodore Ts'o wrote:
> > On Mon, Jan 29, 2018 at 07:09:01AM -0500, Mimi Zohar wrote:
> > > 
> > > The LSM security_file_open hook is where fs-verity and IMA meet. �The
> > > fs-verity Merkle tree hash signature would be another IMA-appraisal
> > > integrity verification method.
> > 
> > I wasn't planning on using the file open hook for fs-verity at all,
> > since the merkle hash signature is going to be cached in the per-file
> > system inode --- e.g., for ext4, it would be stored in EXT4_I(inode),
> > aka "struct ext4_inode_info".
> 
> Ok, so if not at open, at what point do you plan on validating the
> merkle hash signature?

I said we would not using the LSM file_open hook.  Instead it will be
done in ext4_file_open() or f2fs_file_open().  That's because the
place where the key is cached is in the file system specific portion
of the inode.  This is what I meant by EXT4_I(inode) aka struct
ext4_inode_info.  So it does happen at file open time; it just doesn't
use the LSM file_open hook.  One of the features of fs-verity is that
it does *not* require the use of the LSM infrastructure.

> I agree with you that the integrity architecture needs to be easily
> extendsible to support different integrity authentication methods.
> �The list, below, is a set of fs-verity functions needed to be
> exported for IMA. �Hopefully I didn't miss anything.

Just to be clear, who is signing up to do all of this work to enable
fs-verity for IMA?  In particular, if you and James are asking *me* to
do all of this development work, when I have no need for any of these
benefits, I'm going to have to decline the honor.  I'm happy to try to
modify the design to make it easier for IMA to use fs-verity.  That's
different from actually implementing it.

> > So I want to support a very simple case where the policy is simply
> > "the public key needed to verify the PKCS7 signing block is in a
> > trusted keyring".
> 
> Which trusted keyring? �How is the keyring populated? �What prevents
> other keys from being added to that keyring?

It will probably be a separate keyring, but in theory we could use the
keyring used to validate signed kernel modules.  There are a number of
different ways the policy for signed kernel modules can be
configured[1], and the same would be true for fs-verity.  (The reason
for a separate kernel keyring is to allow for a separation between
those keys trusted to sign kernel modules, and those trusted to sign
for fs-verity.)

[1] https://01.org/linuxgraphics/gfx-docs/drm/admin-guide/module-signing.html

> So the implied policy is that no signatures will be verified unless
> userspace turns the bit on. �So you're trust is based in userspace.

For the initial use case that we're interested in, yes.  The check to
make sure the verity bit is enabled for a small set of privileged
APK's will be done by the AOSP userspace, and the AOSP userspace lives
in a read-only system partition which is protected using dm-verity.
(And the keys for dm-verity are protected using asigned bootloader; it
is possible to do data integrity without using IMA/EVM, and millions
and millions of Android devices are doing in this way.)


The problem we're trying to solve is that in order to allow for the
privileged APK's to be upgraded more frequently, they are stored in
the /data partition, which is encrypted; however, fs-crypt does not
provide data integrity guarntees.  fs-verity allows us to protect
those APK's (which are equivalent in power to software in the system
partition, being privileged APK's).

Note also that an APK will often have large number of translations
that will never be used on a particular device, so doing full check of
the entire APK will mean doing unneeded work.  Obviously you have to
trade off the time of doing sequential reads versus the random reads
for doing on-demand Merkle tree checks, but if you have translation
resources for Russian, Chinese, French, Spanish, etc, and the only
language used on a particular device is English, then the on-demand
checks can often be far more efficient, especially if the one of the
figures of merit is how long it takes for an application to start
painting the first pixel after the user clicks on its icon.

> > If someone needs something more complex than the simple "key is in the
> > trusted keyring", I'm happy to say that the right answer is to use the
> > LSM hooks, and it should be straight forward to provide interfaces so
> > that the LSM can determine that file system supports verity and the
> > file has the verity bit set.  The LSM could also apply additional
> > restrictions (if the SELinux file type is supersekrit_t, then only a
> > smaller set of keys will be allowed to be used to sign the PKCS7
> > signature block).
> 
> Interesting, so there is an additional policy limiting which keys may
> be used based on an LSM labels, if so desired.

If someone implements it, yes.  If there is a business case where the
benefits outweighs the costs, and the headcount can be funded, it
would happen.  However, having spent time trying to understand the
IMA/EVM/LSM/SELinux architecture, I've spent enough time to decide
it's not something I would do on my own time, for fun.  :-)

						- Ted

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

[James Bottomley]

On Wed, 2018-01-31 at 11:05 -0500, Theodore Ts'o wrote:
> On Tue, Jan 30, 2018 at 06:25:02PM -0500, Mimi Zohar wrote:
> > 
> > On Mon, 2018-01-29 at 18:02 -0500, Theodore Ts'o wrote:
> > > 
> > > On Mon, Jan 29, 2018 at 07:09:01AM -0500, Mimi Zohar wrote:
> > > > 
> > > > 
> > > > The LSM security_file_open hook is where fs-verity and IMA
> > > > meet.  The fs-verity Merkle tree hash signature would be
> > > > another IMA-appraisal integrity verification method.
> > > 
> > > I wasn't planning on using the file open hook for fs-verity at
> > > all, since the merkle hash signature is going to be cached in the
> > > per-file system inode --- e.g., for ext4, it would be stored in
> > > EXT4_I(inode), aka "struct ext4_inode_info".
> > 
> > Ok, so if not at open, at what point do you plan on validating the
> > merkle hash signature?
> 
> I said we would not using the LSM file_open hook.  Instead it will be
> done in ext4_file_open() or f2fs_file_open().  That's because the
> place where the key is cached is in the file system specific portion
> of the inode.  This is what I meant by EXT4_I(inode) aka struct
> ext4_inode_info.  So it does happen at file open time; it just
> doesn't use the LSM file_open hook.  One of the features of fs-verity 
> is that it does *not* require the use of the LSM infrastructure.

This is all sounding appallingly ext4/f2fs specific.  What about other
filesystems that might want this feature, how would they play?

I assume also that a write of the magic file updates the key and
signature in the inode metadata?  I suppose this also avoids the
original IMA locking problem by sorting it out below the VFS, but it
also means you have to invent mechanisms to query the key (user space
might want to know for audit purposes) and to update the key (in case
the original is compromised).

Also when you say "key" presumably you mean pointer to x509 public
certificate in a keyring somewhere, say by DN and Version or SKID?

I really think some time needs to be spent figuring out how it should
be supported in a fs generic way (at least for the user visible API)
otherwise every fs will grow its own version and we'll have a user
tooling nightmare on our hands.

James

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

[Theodore Ts'o]

On Wed, Jan 31, 2018 at 09:12:48AM -0800, James Bottomley wrote:
> 
> This is all sounding appallingly ext4/f2fs specific. �What about other
> filesystems that might want this feature, how would they play?

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.

> I assume also that a write of the magic file updates the key and
> signature in the inode metadata? �I suppose this also avoids the
> original IMA locking problem by sorting it out below the VFS, but it
> also means you have to invent mechanisms to query the key (user space
> might want to know for audit purposes) and to update the key (in case
> the original is compromised).

Like dm-verity, fs-verity only supports the read-only case.  So we
don't need to worry about write updates.

> Also when you say "key" presumably you mean pointer to x509 public
> certificate in a keyring somewhere, say by DN and Version or SKID?

Yes.  The cert might be hard-coded public key in the kernel sources;
or there might be a hard-coded CA public key, and userspace is allowed
to add new certs to the keyring so long as they are signed by a CA
cert in the system keyring.  Again, I refer you to how how signed
kernel modules are managed.

It would be possible to add something more complicated, involving
SELinux policies, or IMA policies --- but that's not something that I
need, so I view that as something that can be added later, by those
who need it.

> I really think some time needs to be spent figuring out how it should
> be supported in a fs generic way (at least for the user visible API)
> otherwise every fs will grow its own version and we'll have a user
> tooling nightmare on our hands.

Like with fscrypt, there will be a standard set of user interfaces,
most of which will be implemented in file sytem generic code.  In the
case of fscrypt, the same userspace is used for ext4 and f2fs in AOSP.

For the generic desktop case, there is a generic userspace tooling[1]
which we are hoping will be picked up by Ubuntu as a replacement for
ecryptfs in the next year or so.  (Discussions are in process; it is
not plan of record yet as far as I know.)

[1] https://github.com/google/fscrypt

The goal for fs-verity to keep the userspace interface as simple as
possible, and of *course* it will be file system generic (it will work
for ext4 and f2fs, and it will be set up to be easy for other
interested file systems to add support for it).

There are admittedly tradeoffs from the model model used by IMA/EVM
where the security feature is imposed on the file system code without
its knowledge or consent, and that is some minor changes are needed in
the file system code.  But there are some efficiencies and some
approaches that it allows that aren't possible with one where new file
system functionality is shoehorned into an LSM.

Cheers,

					- Ted

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

[Mimi Zohar]

On Wed, 2018-01-31 at 11:05 -0500, Theodore Ts'o wrote:
> On Tue, Jan 30, 2018 at 06:25:02PM -0500, Mimi Zohar wrote:
> > On Mon, 2018-01-29 at 18:02 -0500, Theodore Ts'o wrote:
> > > On Mon, Jan 29, 2018 at 07:09:01AM -0500, Mimi Zohar wrote:
> > > > 
> > > > The LSM security_file_open hook is where fs-verity and IMA meet.  The
> > > > fs-verity Merkle tree hash signature would be another IMA-appraisal
> > > > integrity verification method.
> > > 
> > > I wasn't planning on using the file open hook for fs-verity at all,
> > > since the merkle hash signature is going to be cached in the per-file
> > > system inode --- e.g., for ext4, it would be stored in EXT4_I(inode),
> > > aka "struct ext4_inode_info".
> > 
> > Ok, so if not at open, at what point do you plan on validating the
> > merkle hash signature?
> 
> I said we would not using the LSM file_open hook.  Instead it will be
> done in ext4_file_open() or f2fs_file_open().  That's because the
> place where the key is cached is in the file system specific portion
> of the inode.  This is what I meant by EXT4_I(inode) aka struct
> ext4_inode_info.  So it does happen at file open time; it just doesn't
> use the LSM file_open hook.  One of the features of fs-verity is that
> it does *not* require the use of the LSM infrastructure.

I see.  So anyone else adding security features is required to use the
LSM hooks, but your use case is different? (rhetorical statement)

> > I agree with you that the integrity architecture needs to be easily
> > extendsible to support different integrity authentication methods.
> >  The list, below, is a set of fs-verity functions needed to be
> > exported for IMA.  Hopefully I didn't miss anything.
> 
> Just to be clear, who is signing up to do all of this work to enable
> fs-verity for IMA?  In particular, if you and James are asking *me* to
> do all of this development work, when I have no need for any of these
> benefits, I'm going to have to decline the honor.  I'm happy to try to
> modify the design to make it easier for IMA to use fs-verity.  That's
> different from actually implementing it.

As long as you provide the fs-verity functions as previously
discussed, I'll do the integration.

> > > So I want to support a very simple case where the policy is simply
> > > "the public key needed to verify the PKCS7 signing block is in a
> > > trusted keyring".
> > 
> > Which trusted keyring?  How is the keyring populated?  What prevents
> > other keys from being added to that keyring?
> 
> It will probably be a separate keyring, but in theory we could use the
> keyring used to validate signed kernel modules.

The .builtin_trusted_keys only contains keys that are built into the
kernel.  With secure boot enabled, there is a signature chain of trust
up to the running OS.  Since the kernel is signed, the keys embedded
in the kernel are part of this signature chain of trusted.  These
embedded keys become the new root of trust for the running OS.

We can extend this signature chain of trust by requiring keys to be
signed by a key on the .builtin_trusted_keys, before adding the key to
another trusted keyring.  If you are interested in extending the
secure boot signature chain of trust to your keyring, you would create
the trusted keyring specifying "restrict_link_by_builtin_trusted and
include a signing key to the builtin keyring.  Then you can safely
load your signed fs-verity key from userspace, define a new fs-verity
key, and black list the old fs-verity key, by adding it to the system
blacklist keyring.

>   There are a number of
> different ways the policy for signed kernel modules can be
> configured[1], and the same would be true for fs-verity.  (The reason
> for a separate kernel keyring is to allow for a separation between
> those keys trusted to sign kernel modules, and those trusted to sign
> for fs-verity.)

Sure.  For this reason, IMA defined a separate trusted keyring.

> [1] https://01.org/linuxgraphics/gfx-docs/drm/admin-guide/module-signing.html
> 
> > So the implied policy is that no signatures will be verified unless
> > userspace turns the bit on.  So you're trust is based in userspace.
> 
> For the initial use case that we're interested in, yes.  The check to
> make sure the verity bit is enabled for a small set of privileged
> APK's will be done by the AOSP userspace, and the AOSP userspace lives
> in a read-only system partition which is protected using dm-verity.
> (And the keys for dm-verity are protected using asigned bootloader; it
> is possible to do data integrity without using IMA/EVM, and millions
> and millions of Android devices are doing in this way.)
> 
> 
> The problem we're trying to solve is that in order to allow for the
> privileged APK's to be upgraded more frequently, they are stored in
> the /data partition, which is encrypted; however, fs-crypt does not
> provide data integrity guarntees.  fs-verity allows us to protect
> those APK's (which are equivalent in power to software in the system
> partition, being privileged APK's).
> 
> Note also that an APK will often have large number of translations
> that will never be used on a particular device, so doing full check of
> the entire APK will mean doing unneeded work.  Obviously you have to
> trade off the time of doing sequential reads versus the random reads
> for doing on-demand Merkle tree checks, but if you have translation
> resources for Russian, Chinese, French, Spanish, etc, and the only
> language used on a particular device is English, then the on-demand
> checks can often be far more efficient, especially if the one of the
> figures of merit is how long it takes for an application to start
> painting the first pixel after the user clicks on its icon.

I think we already benched the discussion as to the level of
security/integrity fs-verity provides; and in which use cases it can
be safely used.

> > > If someone needs something more complex than the simple "key is in the
> > > trusted keyring", I'm happy to say that the right answer is to use the
> > > LSM hooks, and it should be straight forward to provide interfaces so
> > > that the LSM can determine that file system supports verity and the
> > > file has the verity bit set.  The LSM could also apply additional
> > > restrictions (if the SELinux file type is supersekrit_t, then only a
> > > smaller set of keys will be allowed to be used to sign the PKCS7
> > > signature block).
> > 
> > Interesting, so there is an additional policy limiting which keys may
> > be used based on an LSM labels, if so desired.
> 
> If someone implements it, yes.  If there is a business case where the
> benefits outweighs the costs, and the headcount can be funded, it
> would happen.  However, having spent time trying to understand the
> IMA/EVM/LSM/SELinux architecture, I've spent enough time to decide
> it's not something I would do on my own time, for fun.  :-)

I understand you have lots of experience reading and understanding
kernel code, but understanding another subsystem, without ever having
been involved, no matter how well written that code is, takes time to
understand.  There is some really well written code in the security
tree, especially considering the constraints put on it.

Mimi

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

[James Bottomley]

On Wed, 2018-01-31 at 13:46 -0500, Theodore Ts'o wrote:
> On Wed, Jan 31, 2018 at 09:12:48AM -0800, James Bottomley wrote:
> > 
> > 
> > This is all sounding appallingly ext4/f2fs specific.  What about
> > other filesystems that might want this feature, how would they
> > play?
> 
> 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 also that a write of the magic file updates the key and
> > signature in the inode metadata?  I suppose this also avoids the
> > original IMA locking problem by sorting it out below the VFS, but
> > it also means you have to invent mechanisms to query the key (user
> > space might want to know for audit purposes) and to update the key
> > (in case the original is compromised).
> 
> Like dm-verity, fs-verity only supports the read-only case.  So we
> don't need to worry about write updates.

OK, but we still need to retrieve the key (if only for the "I just
found this image what did I sign the file with?" case).  I assume, in-
line with fscrypt, you'll use ioctls for that.

One thought that strikes is that since you're already using xattrs
under the covers, they could simply be exposed, at least for the new
VERITY index I assume you'll be using.  That way most archive systems
would pick up the signature.  If you're worried about locking
inversions and other problems on write, the xattrs could be read only,
so the archive would need extra help being rewritten.

> > Also when you say "key" presumably you mean pointer to x509 public
> > certificate in a keyring somewhere, say by DN and Version or SKID?
> 
> Yes.  The cert might be hard-coded public key in the kernel sources;
> or there might be a hard-coded CA public key, and userspace is
> allowed to add new certs to the keyring so long as they are signed by
> a CA cert in the system keyring.  Again, I refer you to how how
> signed kernel modules are managed.
> 
> It would be possible to add something more complicated, involving
> SELinux policies, or IMA policies --- but that's not something that I
> need, so I view that as something that can be added later, by those
> who need it.

No, as long as you do cert to signature matching by DN/Serial or SKID
it's fine if the key policy is must match and be in system keyring.
 The reason being we're inching towards dumping all the UEFI certs into
the system keyring which wouldn't enhance my view of security if I knew
some random OEM could also produce acceptable signatures for my
filesystem.

> > I really think some time needs to be spent figuring out how it
> > should be supported in a fs generic way (at least for the user
> > visible API) otherwise every fs will grow its own version and we'll
> > have a user tooling nightmare on our hands.
> 
> Like with fscrypt, there will be a standard set of user interfaces,
> most of which will be implemented in file sytem generic code.  In the
> case of fscrypt, the same userspace is used for ext4 and f2fs in
> AOSP.
> 
> For the generic desktop case, there is a generic userspace tooling[1]
> which we are hoping will be picked up by Ubuntu as a replacement for
> ecryptfs in the next year or so.  (Discussions are in process; it is
> not plan of record yet as far as I know.)
> 
> [1] https://github.com/google/fscrypt

Wow, that's 160k lines of go code ... OK, over the initial indigestion;
I'll look at it on the 'plane to FOSDEM.

> The goal for fs-verity to keep the userspace interface as simple as
> possible, and of *course* it will be file system generic (it will
> work for ext4 and f2fs, and it will be set up to be easy for other
> interested file systems to add support for it).
> 
> There are admittedly tradeoffs from the model model used by IMA/EVM
> where the security feature is imposed on the file system code without
> its knowledge or consent, and that is some minor changes are needed
> in the file system code.  But there are some efficiencies and some
> approaches that it allows that aren't possible with one where new
> file system functionality is shoehorned into an LSM.

The implementations in fscrypt look pretty close to a lot of what IMA
does, just coded under the VFS.  Assuming fs-verity follows the model,
it may be possible to have a generic case that just works with IMA and
a specific case for a fs where the presence of the new verity
superblock operations overrides the IMA attachment.  This might
actually allow building a model where either the FS just takes care of
integrity via the verity sops or we use the generic IMA.  The only
complexity might be archive restore of the image.

James

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

[Theodore Ts'o]

On Wed, Jan 31, 2018 at 03:40:39PM -0500, Mimi Zohar wrote:
> 
> I see. �So anyone else adding security features is required to use the
> LSM hooks, but your use case is different? (rhetorical statement)

dm-verity does not use LSM.  Signed kernel-modules does not use LSM.
Ergo, it is not true all security features have to use the LSM hooks.
It may be instructive to review why LSM exists[1][2][3][4].

[1] https://lkml.org/lkml/2007/10/1/110
[2] https://lkml.org/lkml/2007/10/1/192
[3] https://lkml.org/lkml/2007/10/1/217
[4] https://lkml.org/lkml/2007/10/2/315

I would presume the authors of dm-verity and signed kernel modules
were able to convince Linus that their design was "sane", so he didn't
insist they were put behind an LSM hook.  I would expect that for
fs-verity, a similar standard would apply in order for it to be
accepted.

> > If someone implements it, yes.  If there is a business case where the
> > benefits outweighs the costs, and the headcount can be funded, it
> > would happen.  However, having spent time trying to understand the
> > IMA/EVM/LSM/SELinux architecture, I've spent enough time to decide
> > it's not something I would do on my own time, for fun.  :-)
> 
> I understand you have lots of experience reading and understanding
> kernel code, but understanding another subsystem, without ever having
> been involved, no matter how well written that code is, takes time to
> understand. �There is some really well written code in the security
> tree, especially considering the constraints put on it.

Well, it would also help if the interfaces to those subsystems were
accurately documented, and it was clear what documentation was
accurate and what wasn't.  Certainly documentation in the kernel tree
would be helpful, and not just magic cookbook style, "this is how you
use 'git commit' and 'git log'", but rather, "this is the low-level
data storage model of git" and "this is how the low-level git commands
can be used so that other programs can interface with git".

To be fair, some of the complexity is caused by the large amounts of
generality which was described by Stephen Smalley in [1] when he
argued that maybe LSM should go away.  But it's the lack of consensus
about how to make the tradeoff between between complexity and the
threat model should be, and just what the threat model should *be*
which causes a dispersion of resources.  (For example Fedora uses
SELinux, but Debian has recently decided that since it is too hard to
make SELinux be configured for desktops/laptops, they will be moving
to support AppArmor as the default LSM in the next stable release.)

So this is a much larger problem, and it's why I'm trying to avoid
getting stuck in this tarbit by following the path trod by dm-verity
and signed kernel modules.

Cheers,

						- Ted

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

[Theodore Ts'o]

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.

The suggestion I had of putting the fs-verity header and PKCS 7 in the
signature was just to carry the information for the Docker image's tar
file.  Before fs-verity gets ahold of it, a userspace librart would
read the xattr, and use it to append the fs-verity header, PKCS 7, and
the reconstructed Merkle tree to the file, and then call an ioctl to
transfer it into a fs-verity protected file.

> > Like dm-verity, fs-verity only supports the read-only case.��So we
> > don't need to worry about write updates.
> 
> OK, but we still need to retrieve the key (if only for the "I just
> found this image what did I sign the file with?" case). �I assume, in-
> line with fscrypt, you'll use ioctls for that.

Yes.

> One thought that strikes is that since you're already using xattrs
> under the covers, they could simply be exposed, at least for the new
> VERITY index I assume you'll be using. �That way most archive systems
> would pick up the signature. �If you're worried about locking
> inversions and other problems on write, the xattrs could be read only,
> so the archive would need extra help being rewritten.

As I stated above, we need to put the Merkle tree after i_size anyway,
so the current plan doesn't use xattrs at all.  Xattr storage space is
also precious (especially if you are trying to keep all of the xattrs
in the inode) so keeping an extra copy of the xattr just to make life
convenient for the archive systems seems like a waste, especially for
those use cases which don't *care* about backwards compatibility for
archive systems that only want to deal with xattrs (and there might
not be a need for any archive systems at all).

And as far having magic code which reads the xattr from the storage
space beyond i_size where fs-verity data is located, that's very much
frowned upon.

> No, as long as you do cert to signature matching by DN/Serial or SKID
> it's fine if the key policy is must match and be in system keyring.
> �The reason being we're inching towards dumping all the UEFI certs into
> the system keyring which wouldn't enhance my view of security if I knew
> some random OEM could also produce acceptable signatures for my
> filesystem.

Another (simpler) solution would be to use a completely separate
keyring for fs-verity, no?

> The implementations in fscrypt look pretty close to a lot of what IMA
> does, just coded under the VFS.

If what you mean is whether fscrypt could have been implemented in
terms of the LSM hooks, I believe the answer to this to be "no".
That's because part of the LSM model is that it's not allowed to
change arguments to the system call --- it can return an error which
aborts the operation or return "OK, go ahead", but it's not supposed
to change what the kernel operation would do or change its arguments.

In the case of encryption, we are replacing the plaintext with
ciphertext for writes, and replacing the ciphertext with the plaintext
on reads, and that's not compatible with the original LSM model.  Even
if we ignored that rule, it would have been *much* more complicated to
implement fscrypt in terms of the LSM hook model.

> �Assuming fs-verity follows the model, it may be possible to have a
> generic case that just works with IMA and a specific case for a fs
> where the presence of the new verity superblock operations overrides
> the IMA attachment. �This might actually allow building a model
> where either the FS just takes care of integrity via the verity sops
> or we use the generic IMA. �The only complexity might be archive
> restore of the image.

If you want to use the tar format and xattrs to carry the integrity
information, that's where things get complex.  That wasn't part the
original requirement set, although I understand how this gets
interesting from the Docker perspective.  I think it should be
possible to provide ioctl's to set and get the fs-verity information,
which should allow for a userspace library which could be used to do
what you want.

							- Ted

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

[Mimi Zohar]

On Wed, 2018-01-31 at 17:00 -0500, Theodore Ts'o wrote:
> dm-verity does not use LSM.  Signed kernel-modules does not use LSM.

True, the original kernel module syscall does not use the LSM hooks,
but the new syscall does.

Mimi

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

[Dave Chinner]

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?

> As I stated above, we need to put the Merkle tree after i_size anyway,
> so the current plan doesn't use xattrs at all.  Xattr storage space is
> also precious (especially if you are trying to keep all of the xattrs

No it's not. xattr space is specifically designed for uses like
this, and if you have to take an extra IO to read it then that's the
cost of storing large chunks of non-userdata data on a file. You;ve
got to take extra IOs to read the merkle tree if it's stored beyond
EOF anyway, so it doesn't matter if we take extra IOs to read it
from an xattr....

Cheers,

Dave.
-- 
Dave Chinner
david@fromorbit.com

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

[Andreas Dilger]

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

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%.

Strictly speaking, the whole Merkle tree does not need to be stored on
disk.  If the leaf checksums are stored (to allow random IO access with
data verification) and the root node (to allow verification of the rest
of the leaf blocks) then the intermediate tree could be recomputed with
relatively low overhead (0.1% vs. checksumming the whole file at open).

>> As I stated above, we need to put the Merkle tree after i_size anyway,
>> so the current plan doesn't use xattrs at all.  Xattr storage space is
>> also precious (especially if you are trying to keep all of the xattrs
> 
> No it's not. xattr space is specifically designed for uses like
> this, and if you have to take an extra IO to read it then that's the
> cost of storing large chunks of non-userdata data on a file. You;ve
> got to take extra IOs to read the merkle tree if it's stored beyond
> EOF anyway, so it doesn't matter if we take extra IOs to read it
> from an xattr....

Since the tree size depends on file size, it would hit the 64KB xattr size
limit at 64MB (CRC32) or 8MB (SHA256), unless we also allow larger xattrs
to userspace.  There was an ext4 feature landed in 4.13 to allow larger
on-disk xattrs than the previous 4KB (single block) limit (essentially any
size xattr could be stored), so that wouldn't be a problem if the userspace
xattr API limit was removed.

Cheers, Andreas






[-- Attachment #2: Message signed with OpenPGP --]
[-- Type: application/pgp-signature, Size: 873 bytes --]

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

[Steve French]

This could be useful for SMB3 as well - good topic

On Thu, Jan 25, 2018 at 1:11 PM, Theodore Ts'o <tytso@mit.edu> wrote:
> I'd like to talk about a proposal to implement and upstream something
> that we've been calling fs-verity, which is something like dm-verity,
> but implemnted on a per-file basis.  It will be implemnted much like
> fs/crypto, in that most of the code will be in a generic layer, with
> minimal modifications needed in the file system layer.
>
> The merkle tree will be located after file's normal data, and then
> after the package manager sets the verity bit, i_size will be updated
> so that the fs-verity header and merkle tree will be "hidden" from
> userspace and the file will become immutable.
>
> How does this differ from IMA's file integrity?
>
> *) The pages are verified as they are read, so pages are verified as
> they are read the storage device; this avoids a large latency hit when
> the file is first opened or referenced.
>
> *) The design and code are done by file system developers, so it
> doesn't have the locking problems of the IMA code.
>
> The initial use case of this will be for Android, where the latency
> concerns of doing the full checksum at file open time is important.
>
> In the future, the fact that a file has been signed using fs-verity,
> using a PKCS 11 signature with a key on a trusted keyring (possibly
> the same one used for signed kernel modules, or perhaps a separate
> keyring) could be used as input into a security policy which requires
> this for say, setuid executables, setuid shell scripts, etc.
>
> Most of this feature could also be used with a non-cryptographic
> checksum to provide data checksums for read-only files in a general
> way for all file systems.  It wouldn't be as flexible as btrfs, but
> for files being stored for backup purposes, it should work quite well.
>
>                                               - Ted



-- 
Thanks,

Steve

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

[Dave Chinner]

On Thu, Feb 01, 2018 at 04:43:37PM -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).
....
> Since the tree size depends on file size, it would hit the 64KB xattr size
> limit at 64MB (CRC32) or 8MB (SHA256), unless we also allow larger xattrs
> to userspace.

So how many cases are there where we need to support >64MB files
for integrity measurement? I just checked my laptop, and there are
only a handful or binaries/library/data files shipped by the distro
that are over 64MB.

Perhaps there's a tradeoff that can be made here - store the full
merkle tree if it fits in an xattr (which covers the vast majority
of system binaries and data files), otherwise calculate it on the
fly and cache it in memory?

> There was an ext4 feature landed in 4.13 to allow larger
> on-disk xattrs than the previous 4KB (single block) limit (essentially any
> size xattr could be stored), so that wouldn't be a problem if the userspace
> xattr API limit was removed.

We'd need to rev the on-disk format for XFS as the internal xattr
value length is held in a 16 bit field. Might be trivial to do
because we'd only need to modify the "remote attribute" header as we
already store large attributes out of line. Of course, that still
leaves all the userspace API to deal with. :(

Cheers,

Dave.
-- 
Dave Chinner
david@fromorbit.com

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

[Theodore Ts'o]

On Fri, Feb 02, 2018 at 10:04:15AM +1100, Dave Chinner wrote:
> 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?

This isn't an issue because once fs-verity protection is enabled, the
file becomes immutable.  That is, you can delete the file, but you
can't modify it afterwards --- so you don't have to truncate it.

We don't actually want userspace to be able to access pages beyond
i_size via read(2) or mmap(2), so I don't believe this to be a
problem.  It's only kernel code that needs to access the pages via
find_get_page.

Regards,

						- Ted

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

[James Bottomley]

[-- 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 --]

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

[Dave Chinner]

On Thu, Feb 01, 2018 at 09:40:03PM -0500, Theodore Ts'o wrote:
> On Fri, Feb 02, 2018 at 10:04:15AM +1100, Dave Chinner wrote:
> > 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?
> 
> This isn't an issue because once fs-verity protection is enabled, the
> file becomes immutable.

yes, but we still have to do some kind of "truncate but not
truncate" to change the file size leaving the data beyond EOF
behind. What's the API for this?

> That is, you can delete the file, but you
> can't modify it afterwards --- so you don't have to truncate it.

Sure, but....

> We don't actually want userspace to be able to access pages beyond
> i_size via read(2) or mmap(2), so I don't believe this to be a
> problem.  It's only kernel code that needs to access the pages via
> find_get_page.

So you're expecting to short circuit page cache read paths to ignore
that the page is beyond EOF. i.e. we've got to screw with the
truncate race detection code in the generic read code to make this
work?

This really seems like a one-way process to me - we can't back up
a filesystem that has integrity information stored beyond EOF,
right? What other common filesystem tools are going to break (or
break integrity checking) because they don't understand that there
is valid data stored in "unused" extents beyond EOF?

Cheers,

Dave.
-- 
Dave Chinner
david@fromorbit.com

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

[David Gstir]

[CC-ing linux-mtd]

> On 25.01.2018, at 20:11, Theodore Ts'o <tytso@mit.edu> wrote:
> 
> I'd like to talk about a proposal to implement and upstream something
> that we've been calling fs-verity, which is something like dm-verity,
> but implemnted on a per-file basis.  It will be implemnted much like
> fs/crypto, in that most of the code will be in a generic layer, with
> minimal modifications needed in the file system layer.
> 
> The merkle tree will be located after file's normal data, and then
> after the package manager sets the verity bit, i_size will be updated
> so that the fs-verity header and merkle tree will be "hidden" from
> userspace and the file will become immutable.
> 
> How does this differ from IMA's file integrity?
> 
> *) The pages are verified as they are read, so pages are verified as
> they are read the storage device; this avoids a large latency hit when
> the file is first opened or referenced.
> 
> *) The design and code are done by file system developers, so it
> doesn't have the locking problems of the IMA code.

This sounds interesting! We recently sent a proposal to add file
authentication to UBIFS [1]. Although it does not cover the exact
same use case, the concept is similar so that it could implement
the same VFS/fs-verity API.

It would be great to get some input on this.

Thanks,
David

[1] https://marc.info/?l=linux-fsdevel&m=151620293206369&w=2