> 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. -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
