lkml.org 
[lkml]   [2015]   [May]   [21]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
From
Date
SubjectRe: Should we automatically generate a module signing key at all?
On Thu, May 21, 2015 at 4:54 PM, George Spelvin <linux@horizon.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


\
 
 \ /
  Last update: 2015-05-22 02:21    [W:0.092 / U:0.584 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site