Messages in this thread | | | From | Andy Lutomirski <> | Date | Thu, 21 May 2015 17:03:21 -0700 | Subject | Re: 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
| |