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

["George Spelvin" <linux@horizon.com>]

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

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.

The modules are numbered 2^k through 2^(k+1)-1.

It's the same information, but slightly easier to keep track of.