Linux-Security-Module Archive on
 help / color / Atom feed
From: Chuck Lever <>
To: James Bottomley <>
Cc: Mimi Zohar <>,
	James Morris <>,
	Deven Bowers <>,
	Pavel Machek <>, Sasha Levin <>,,,,,
	Paul Moore <>,
	Jonathan Corbet <>,,,, Jann Horn <>,, Al Viro <>,
	Jens Axboe <>,, open list <>,,,,
	linux-fsdevel <>,,
Subject: Re: [dm-devel] [RFC PATCH v5 00/11] Integrity Policy Enforcement LSM (IPE)
Date: Fri, 14 Aug 2020 10:21:26 -0400
Message-ID: <> (raw)
In-Reply-To: <>

> On Aug 13, 2020, at 11:10 AM, James Bottomley <> wrote:
> On Thu, 2020-08-13 at 10:42 -0400, Chuck Lever wrote:
>>> On Aug 12, 2020, at 11:51 AM, James Bottomley <James.Bottomley@Hans
>>>> wrote:
>>> On Wed, 2020-08-12 at 10:15 -0400, Chuck Lever wrote:
>>>>> On Aug 11, 2020, at 11:53 AM, James Bottomley
>>>>> <> wrote:
>>>>> On Tue, 2020-08-11 at 10:48 -0400, Chuck Lever wrote:
> [...]
>>>>>>>> The client would have to reconstruct that tree again if
>>>>>>>> memory pressure caused some or all of the tree to be
>>>>>>>> evicted, so perhaps an on-demand mechanism is preferable.
>>>>>>> Right, but I think that's implementation detail.  Probably
>>>>>>> what we need is a way to get the log(N) verification hashes
>>>>>>> from the server and it's up to the client whether it caches
>>>>>>> them or not.
>>>>>> Agreed, these are implementation details. But see above about
>>>>>> the trustworthiness of the intermediate hashes. If they are
>>>>>> conveyed on an untrusted network, then they can't be trusted
>>>>>> either.
>>>>> Yes, they can, provided enough of them are asked for to
>>>>> verify.  If you look at the simple example above, suppose I
>>>>> have cached H11 and H12, but I've lost the entire H2X layer.  I
>>>>> want to verify B3 so I also ask you for your copy of H24.  Then
>>>>> I generate H23 from B3 and Hash H23 and H24.  If this doesn't
>>>>> hash to H12 I know either you supplied me the wrong block or
>>>>> lied about H24.  However, if it all hashes correctly I know you
>>>>> supplied me with both the correct B3 and the correct H24.
>>>> My point is there is a difference between a trusted cache and an
>>>> untrusted cache. I argue there is not much value in a cache where
>>>> the hashes have to be verified again.
>>> And my point isn't about caching, it's about where the tree comes
>>> from. I claim and you agree the client can get the tree from the
>>> server a piece at a time (because it can path verify it) and
>>> doesn't have to generate it itself.
>> OK, let's focus on where the tree comes from. It is certainly
>> possible to build protocol to exchange parts of a Merkle tree.
> Which is what I think we need to extend IMA to do.
>> The question is how it might be stored on the server.
> I think the only thing the server has to guarantee to store is the head
> hash, possibly signed.
>> There are some underlying assumptions about the metadata storage
>> mechanism that should be stated up front.
>> Current forms of IMA metadata are limited in size and stored in a
>> container that is read and written in a single operation. If we stick
>> with that container format, I don't see a way to store a Merkle tree
>> in there for all file sizes.
> Well, I don't think you need to.  The only thing that needs to be
> stored is the head hash.  Everything else can be reconstructed.  If you
> asked me to implement it locally, I'd probably put the head hash in an
> xattr but use a CAM based cache for the merkel trees and construct the
> tree on first access if it weren't already in the cache.

The contents of the security.ima xattr might be modeled after

- a format enumerator (used by all IMA metadata formats)
- the tree's unit size
- a fingerprint of the signer's certificate
  - digest algorithm name and full digest
- the root hash, always signed
  - signing algorithm name and signature

The rest of the hash tree is always stored somewhere else or
constructed on-demand.

My experience of security communities both within and outside the
IETF is that they would insist on always having a signature.

If one doesn't care about signing, a self-signed certificate can be
automatically provisioned when ima-evm-utils is installed that can
be used for those cases. That would make the signature process
invisible to any administrator who doesn't care about signed

Because storage in NFS would cross trust boundaries, it would have
to require the use of a signed root hash. I don't want to be in the
position where copying a file with an unsigned root hash into NFS
makes it unreadable because of a change in policy.

> However, the above isn't what fs-verity does: it stores the tree in a
> hidden section of the file.  That's why I don't think we'd mandate
> anything about tree storage.  Just describe the partial retrieval
> properties we'd like and leave the rest as an implementation detail.

I'm starting to consider how much compatibility with fs-verity is
required. There are several forms of hash-tree, and a specification
of the IMA metadata format would need to describe exactly how to
form the tree root. If we want compatibility with fs-verity, then
it is reasonable to assume that this IMA metadata format might be
required to use the same hash tree construction algorithm that
fs-verity uses.

The original Merkle tree concept was patented 40 years ago. I'm not
clear yet on whether the patent encumbers the use of Merkle trees
in any way, but since their usage seems pretty widespread in P2P
and BitCoin applications, I'm guessing the answer to that is
favorable. More research needed.

There is an implementation used by several GNU utilities that is
available as a piece of GPL code. It could be a potential blocker
if that was the tree algorithm that fs-verity uses -- as discussed
in the other thread.

Apparently there are some known weaknesses in older hash tree
algorithms, including at least one CVE. We could choose a recent
algorithm, but perhaps there needs to be a degree of extensibility
in case that algorithm needs to be updated due to a subsequent
security issue.

Tree construction could include a few items besides file content to
help secure the hash further. For instance the file's size and mtime,
as well as the depth of the tree, could be included in the signature.
But that depends on whether it can be done while maintaining
compatibility with fs-verity.

I would feel better if someone with more domain expertise chimed in.

>> Thus it seems to me that we cannot begin to consider the tree-on-the-
>> server model unless there is a proposed storage mechanism for that
>> whole tree. Otherwise, the client must have the primary role in
>> unpacking and verifying the tree.
> Well, as I said,  I don't think you need to store the tree.

We basically agree there.

> You certainly could decide to store the entire tree (as fs-verity does) if
> it fitted your use case, but it's not required.  Perhaps even in my
> case I'd make the CAM based cache persistent, like android's dalvik
> cache.
> James
>> Storing only the tree root in the metadata means the metadata format
>> is nicely bounded in size.

Chuck Lever

  reply index

Thread overview: 61+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2020-07-28 21:36 Deven Bowers
2020-07-28 21:36 ` [RFC PATCH v5 01/11] scripts: add ipe tooling to generate boot policy Deven Bowers
2020-07-28 21:36 ` [RFC PATCH v5 02/11] security: add ipe lsm evaluation loop and audit system Deven Bowers
2020-07-28 21:36 ` [RFC PATCH v5 03/11] security: add ipe lsm policy parser and policy loading Deven Bowers
2020-07-28 21:36 ` [RFC PATCH v5 04/11] ipe: add property for trust of boot volume Deven Bowers
2020-07-28 21:36 ` [RFC PATCH v5 05/11] fs: add security blob and hooks for block_device Deven Bowers
2020-07-28 22:22   ` Casey Schaufler
2020-07-28 22:40     ` Al Viro
2020-07-28 23:55       ` Deven Bowers
2020-07-28 21:36 ` [RFC PATCH v5 06/11] dm-verity: move signature check after tree validation Deven Bowers
2020-07-28 21:50   ` Eric Biggers
2020-07-28 23:55     ` Deven Bowers
2020-07-28 21:36 ` [RFC PATCH v5 07/11] dm-verity: add bdev_setsecurity hook for dm-verity signature Deven Bowers
2020-07-28 21:36 ` [RFC PATCH v5 08/11] ipe: add property for signed dmverity volumes Deven Bowers
2020-07-28 21:36 ` [RFC PATCH v5 09/11] dm-verity: add bdev_setsecurity hook for root-hash Deven Bowers
2020-07-28 21:36 ` [RFC PATCH v5 10/11] documentation: add ipe documentation Deven Bowers
2020-07-28 21:36 ` [RFC PATCH v5 10/12] ipe: add property for dmverity roothash Deven Bowers
2020-07-28 21:36 ` [RFC PATCH v5 11/11] cleanup: uapi/linux/audit.h Deven Bowers
2020-07-28 21:36 ` [RFC PATCH v5 11/12] documentation: add ipe documentation Deven Bowers
2020-07-28 21:36 ` [RFC PATCH v5 12/12] cleanup: uapi/linux/audit.h Deven Bowers
2020-08-02 11:55 ` [RFC PATCH v5 00/11] Integrity Policy Enforcement LSM (IPE) Pavel Machek
2020-08-02 14:03   ` Sasha Levin
2020-08-02 14:31     ` Pavel Machek
2020-08-02 16:43       ` [dm-devel] " James Bottomley
2020-08-04 16:07         ` Deven Bowers
2020-08-05 15:01           ` James Bottomley
2020-08-05 16:59             ` James Morris
2020-08-05 18:15               ` Mimi Zohar
2020-08-05 23:51                 ` James Morris
2020-08-06 14:33                   ` Mimi Zohar
2020-08-07 16:41                     ` James Morris
2020-08-07 17:31                       ` Mimi Zohar
2020-08-07 18:40                         ` Mimi Zohar
2020-08-10 20:29                           ` James Morris
2020-08-08 17:47                 ` Chuck Lever
2020-08-09 17:16                   ` Mimi Zohar
2020-08-10 15:35                     ` James Bottomley
2020-08-10 16:35                       ` Mimi Zohar
2020-08-10 17:13                         ` James Bottomley
2020-08-10 17:57                           ` Mimi Zohar
2020-08-10 23:36                       ` Chuck Lever
2020-08-11  5:43                         ` James Bottomley
2020-08-11 14:48                           ` Chuck Lever
2020-08-11 15:32                             ` James Bottomley
2020-08-11 19:30                               ` Pavel Machek
2020-08-12 14:45                               ` Chuck Lever
2020-08-11 15:53                             ` James Bottomley
2020-08-12 14:15                               ` Chuck Lever
2020-08-12 15:51                                 ` James Bottomley
2020-08-13 14:42                                   ` Chuck Lever
2020-08-13 15:10                                     ` James Bottomley
2020-08-14 14:21                                       ` Chuck Lever [this message]
2020-08-11 18:28                             ` James Bottomley
2020-08-12 13:56                               ` Chuck Lever
2020-08-12 15:42                                 ` James Bottomley
2020-08-13 14:21                                   ` Chuck Lever
2020-08-13 14:42                                     ` James Bottomley
2020-08-13 14:56                                       ` Chuck Lever
2020-08-11 21:03                   ` James Morris
2020-08-12 14:18                     ` Chuck Lever
2020-08-12 17:07                       ` Deven Bowers

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

Linux-Security-Module Archive on

Archives are clonable:
	git clone --mirror linux-security-module/git/0.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 linux-security-module linux-security-module/ \
	public-inbox-index linux-security-module

Example config snippet for mirrors

Newsgroup available over NNTP:

AGPL code for this site: git clone