Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1755860AbbESTBf (ORCPT ); Tue, 19 May 2015 15:01:35 -0400 Received: from mail-la0-f46.google.com ([209.85.215.46]:36792 "EHLO mail-la0-f46.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751104AbbESTBd (ORCPT ); Tue, 19 May 2015 15:01:33 -0400 MIME-Version: 1.0 In-Reply-To: <5348.1432061085@warthog.procyon.org.uk> References: <31154.1431965087@warthog.procyon.org.uk> <555A88FB.7000809@kernel.org> <1432058889.3277.73.camel@infradead.org> <5348.1432061085@warthog.procyon.org.uk> From: Andy Lutomirski Date: Tue, 19 May 2015 12:01:11 -0700 Message-ID: Subject: Re: Should we automatically generate a module signing key at all? To: David Howells Cc: David Woodhouse , Linus Torvalds , Andy Lutomirski , Michal Marek , Abelardo Ricart III , Linux Kernel Mailing List , Sedat Dilek , keyrings@linux-nfs.org, Rusty Russell , LSM List , Borislav Petkov , Jiri Kosina 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: 2819 Lines: 72 On Tue, May 19, 2015 at 11:50 AM, David Howells wrote: > Andy Lutomirski wrote: > >> No, in the hash tree variant, it really is 32 bytes. No one ever >> needs the full list once the build is done. > > Yes, you do. You have to check the hash on the hash list or you can't trust > it. > No, you don't :) See below. On Tue, May 19, 2015 at 11:44 AM, David Howells wrote: > Andy Lutomirski wrote: > >> The actual runtime code needed to implement a hash tree solution is >> maybe twenty lines. The bzImage will be smaller, > > But the initramfs image will be bigger because it will have to carry the > entire module hash list just in case any particular module needs to get loaded > from the initramfs. You have to carry the entire hash set so that you can > hash it and compare against the one hash in the vmlinux file. > No. Here's one way it could work: 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. Variants of this scheme are possible. Don't emulate Amazon or Bittorrent here, though -- they both managed to screw up the crypto. > And that doesn't include the issue of hashing the firmware blobs you might > need. As before, that's true. To verify firmware, either you need to hash it, use a termporary signing key, or use a long-term signing key. Choose your poison. I still prefer a hash over a temporary signing key. > >> With your proposal, I need to trust that whoever built the actual >> running kernel image really did throw away the key. If they didn't, >> then under whatever threat model requires that I enable module >> verification, I'm screwed -- the bad guy has the private key. > > Each private key is used for one single kernel, so if they steal one, you can > blacklist it if you have the capability (eg. UEFI) and change your kernel. > How do you know it was stolen? --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/