From: Sascha Hauer <s.hauer@pengutronix.de>
To: David Gstir <david@sigma-star.at>
Cc: linux-fscrypt@vger.kernel.org, linux-fsdevel@vger.kernel.org,
linux-mtd@lists.infradead.org,
Richard Weinberger <richard@nod.at>,
linux-kernel@vger.kernel.org, kernel@pengutronix.de
Subject: Re: [RFC] UBIFS authentication
Date: Mon, 9 Apr 2018 11:59:12 +0200 [thread overview]
Message-ID: <20180409095912.f7d35y7yjdnj2ffz@pengutronix.de> (raw)
In-Reply-To: <E6D3BD02-AF3A-4B75-92FD-A8A07B4C9C51@sigma-star.at>
Hi David,
On Wed, Jan 17, 2018 at 04:19:14PM +0100, David Gstir wrote:
> Hi everybody!
>
> ### Index Authentication
>
> Through UBIFS' concept of a wandering tree, it already takes care of only
> updating and persisting changed parts from leaf node up to the root node
> of the full B+ tree. This enables us to augment the index nodes of the tree
> with a hash over each node's child nodes. As a result, the index basically also
> a Merkle tree. Since the leaf nodes of the index contain the actual filesystem
> data, the hashes of their parent index nodes thus cover all the file contents
> and file metadata. When a file changes, the UBIFS index is updated accordingly
> from the leaf nodes up to the root node including the master node. This process
> can be hooked to recompute the hash only for each changed node at the same time.
> Whenever a file is read, UBIFS can verify the hashes from each leaf node up to
> the root node to ensure the node's integrity.
>
> To ensure the authenticity of the whole index, the UBIFS master node stores a
> keyed hash (HMAC) over its own contents (which includes the location of the root
> node) and the root node of the index tree. As mentioned above, the master node
> is always written to the flash whenever the index is persisted (ie. on index
> commit).
>
> Using this approach only UBIFS index nodes and the master node are changed to
> include a hash. All other types of nodes will remain unchanged. This reduces
> the storage overhead which is precious for users of UBIFS (ie. embedded
> devices).
>
>
> HMAC Master Node
> |
> ' ' ' ' ' ' ' ' ' ' ' ' ' '|' '
> ' +---------------+ o '
> ' | Master Node | '
> ' +---------------+ ' Hash Index Node #1
> ' | ' |
> . . . . . . . .'. . . . . . v . . . . . . . . . . . . . . . .|. . . . .
> . ' +---------------+ ' o .
> . ' | Index Node #1 | ' .
> . ' +---------------+ ' .
> . ' | ... | (fanout: 8) .
> . ' ' ' ' | ' ' ' ' | ' ' ' ' ' .
> . +-------+ +------+ .
> . | | .
> . ' ' ' ' ' v ' ' ' ' ' ' ' ' ' ' ' v ' ' ' ' ' ' ' ' ' ' ' .
> . ' +---------------+ ' ' +---------------+ ' .
> . ' | Index Node #2 | ' ' | Index Node #3 | ' .
> . ' +---------------+ ' ' +---------------+ ' .
> . ' | ... ' ' | ... | ' .
> . . . ' . v . . . . . . . '. ' . . . v . . . . v . . . . . . . .' . . .
> ' +-----------+ ' '+----------+ +-----------+ '
> ' | Data Node | ' '| INO Node | | DENT Node | '
> ' +-----------+ ' '+----------+ +-----------+ '
> ' o ' ' o '
> ' '|' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' '|' '
> | |
> Hash Index Node #2 Hash Index Node #3
When a hash covers an index node and also its children then of course
this is really space efficient, but this also means that in order to
read a node we always have to read all of its children. Also adding a
new leaf node means rehashing all siblings. Is it really worth paying
this price to save a few bytes for more hashes?
I would rather suggest to add a hash per child to each index node.
Sascha
--
Pengutronix e.K. | |
Industrial Linux Solutions | http://www.pengutronix.de/ |
Peiner Str. 6-8, 31137 Hildesheim, Germany | Phone: +49-5121-206917-0 |
Amtsgericht Hildesheim, HRA 2686 | Fax: +49-5121-206917-5555 |
next prev parent reply other threads:[~2018-04-09 9:59 UTC|newest]
Thread overview: 6+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-01-17 15:19 [RFC] UBIFS authentication David Gstir
2018-01-25 8:49 ` David Gstir
2018-04-09 9:59 ` Sascha Hauer [this message]
2018-04-09 15:23 ` David Gstir
2018-04-10 7:02 ` Sascha Hauer
2018-04-10 8:18 ` David Gstir
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:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20180409095912.f7d35y7yjdnj2ffz@pengutronix.de \
--to=s.hauer@pengutronix.de \
--cc=david@sigma-star.at \
--cc=kernel@pengutronix.de \
--cc=linux-fscrypt@vger.kernel.org \
--cc=linux-fsdevel@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-mtd@lists.infradead.org \
--cc=richard@nod.at \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).