linux-kernel - Re: Should we automatically generate a module signing key at all?

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <CALCETrVccHBUHnXZ_1axaESWw-1LYf7SakCdU34S=R3QU1hWog@mail.gmail.com>
Date:	Thu, 21 May 2015 17:03:21 -0700
From:	Andy Lutomirski <luto@...capital.net>
To:	George Spelvin <linux@...izon.com>
Cc:	David Howells <dhowells@...hat.com>,
	David Woodhouse <dwmw2@...radead.org>,
	"linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>,
	LSM List <linux-security-module@...r.kernel.org>,
	petkan@...-labs.com,
	Linus Torvalds <torvalds@...ux-foundation.org>,
	"Theodore Ts'o" <tytso@....edu>,
	Mimi Zohar <zohar@...ux.vnet.ibm.com>
Subject: Re: Should we automatically generate a module signing key at all?

On Thu, May 21, 2015 at 4:54 PM, George Spelvin <linux@...izon.com> wrote:
>> Suppose you have a depth-k tree (i.e. up to 2^k modules).  We'll
>> compute a 32-byte value Tree(d, i) for each d from 0 to k and each i
>> from 0 to 2^d-1.  First you assign each module an index starting at
>> zero (with the maximum index less than 2^k).  Then you hash each
>> module.
>>
>> To generate the leaves (i.e. nodes at depth k), you compute, for each
>> i, Tree(k, i) = H(k, i, H(module payload)).  For leaves that don't
>> correspond to modules, you use some placeholder.
>>
>> For the ith node at lower depth, compute Tree(d, i) = H(k-1, i,
>> Tree(d+1, 2*i), Tree(d+1, 2*i+1)).
>>
>> The proof associated with module i is Tree(k, i^1), Tree(k-1,
>> (i>>1)^1), Tree(k-2, (i>>2)^1), etc, up through depth 1.  Tree(0, 0)
>> is built into the kernel.
>
> Nice system.  For an easier-to-visualize description (omitting some of
> the details Andy includes here to avoid security problems), think of a
> depth-k binary tree with 2^k modules (padded with zero-length dummies)
> at the leaves.  Each internal node is a hash of its two child hashes,
> and the root hash is baked into the kernel.

Bonus exercise for the reader: find the security hole in this
simplified scheme :)  Hint: you can construct a proof of validity for
a sequence of bytes that isn't a module at all.

>
> To prove a module is a member of the hash tree, you need to walk the
> path to the root, combining the two child hashes at each step.
>
> So each module includes the k sibling hashes needed to trace a path to
> the root.  You hash the module, then combine it with its stored depth-k
> sibling hash to compute the depth-k-1 hash.  Then combine that with the
> stored depth-k-1 sibling hash, and so on.
>
> If any of the hashes are wrong (most importantly, the module hash itself),
> the root hash won't match and the kernel will refuse to load the module.
>
> It takes n log n space for n modules, which is completely reasonable.
>
> The annoying thing is that it's a two-pass process: the kernel has to
> have the hashes of ALL of the modules to generate the sibling hashes
> for ANY of them.
>
> Or, and this is the biggest change to the kernel build process, the kernel
> image itself.  No longer can you build the kernel image before building
> modules.
>
>
> To address other use cases, it's possible to allow multiple authentication
> systems.  You can generate one big tree for in-tree modules, then either
> additional trees or the existing public-key signatures for additions.
>
>
> Andy, an easier indexing scheme might use, instead the depth
> and index separately, the implicit heap numbering.  The root is
> node 1, its children are 2 and 3, their children are 4 through 7, etc.

That could work, too.  I think it kills my xor-1 trick, though.

Long-term, I think it would be neat if NIST standardized something
like the Sakura tree coding system, and we'd just use that.  It
wouldn't be compatible with SHA-256 at all (unless they also generated
a modified version of SHA-256 that worked with Sakura), but we could
use genuine hypothetically standard SHA-3/Sakura hashes.

(Sakura is a clever, low-overhead way to encode fairly general hash
trees, complete with a security proof for Sakura as a whole.  It would
be extra neat if they standardized an encoding of Sakura proofs, but
I'll take a standard and correct hash tree as a very good start.)

--Andy
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/