Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1422669AbbEVADq (ORCPT ); Thu, 21 May 2015 20:03:46 -0400 Received: from mail-lb0-f171.google.com ([209.85.217.171]:36802 "EHLO mail-lb0-f171.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1755922AbbEVADo (ORCPT ); Thu, 21 May 2015 20:03:44 -0400 MIME-Version: 1.0 In-Reply-To: <20150521235430.24546.qmail@ns.horizon.com> References: <20150521235430.24546.qmail@ns.horizon.com> From: Andy Lutomirski Date: Thu, 21 May 2015 17:03:21 -0700 Message-ID: Subject: Re: Should we automatically generate a module signing key at all? To: George Spelvin Cc: David Howells , David Woodhouse , "linux-kernel@vger.kernel.org" , LSM List , petkan@mip-labs.com, Linus Torvalds , "Theodore Ts'o" , Mimi Zohar Content-Type: text/plain; charset=UTF-8 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 3678 Lines: 79 On Thu, May 21, 2015 at 4:54 PM, George Spelvin 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@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/