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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <CALCETrWjygX_SsQxD25wfG9ttY=DjuZrDRPrhcLawOpgCXYY4A@mail.gmail.com>
Date:	Tue, 19 May 2015 12:01:11 -0700
From:	Andy Lutomirski <luto@...capital.net>
To:	David Howells <dhowells@...hat.com>
Cc:	David Woodhouse <dwmw2@...radead.org>,
	Linus Torvalds <torvalds@...ux-foundation.org>,
	Andy Lutomirski <luto@...nel.org>,
	Michal Marek <mmarek@...e.cz>,
	Abelardo Ricart III <aricart@...nix.com>,
	Linux Kernel Mailing List <linux-kernel@...r.kernel.org>,
	Sedat Dilek <sedat.dilek@...il.com>, keyrings@...ux-nfs.org,
	Rusty Russell <rusty@...tcorp.com.au>,
	LSM List <linux-security-module@...r.kernel.org>,
	Borislav Petkov <bp@...en8.de>, Jiri Kosina <jkosina@...e.cz>
Subject: Re: Should we automatically generate a module signing key at all?

On Tue, May 19, 2015 at 11:50 AM, David Howells <dhowells@...hat.com> wrote:
> Andy Lutomirski <luto@...capital.net> 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 <dhowells@...hat.com> wrote:
> Andy Lutomirski <luto@...capital.net> 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@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/