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

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

[George Spelvin]

> 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.

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

[Linus Torvalds]

On Thu, May 21, 2015 at 4:54 PM, George Spelvin <linux@horizon.com> wrote:
>
> 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.

It's also very annoying because the whole build gets much nastier,
particularly if you want to have modules in external trees.

In short, I don't see any actual *advantages* over just using signed
modules. Signing is much more flexible, and thanks to that extra
indirection (the signing key), there are no ordering constraints on
generating modules vs the kernel.

I realize that people have political objections to signing, but it's
the better technology, for chissake!

                 Linus

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

[Andy Lutomirski]

On Thu, May 21, 2015 at 5:03 PM, Linus Torvalds
<torvalds@linux-foundation.org> wrote:
> On Thu, May 21, 2015 at 4:54 PM, George Spelvin <linux@horizon.com> wrote:
>>
>> 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.
>
> It's also very annoying because the whole build gets much nastier,
> particularly if you want to have modules in external trees.
>
> In short, I don't see any actual *advantages* over just using signed
> modules. Signing is much more flexible, and thanks to that extra
> indirection (the signing key), there are no ordering constraints on
> generating modules vs the kernel.
>
> I realize that people have political objections to signing, but it's
> the better technology, for chissake!

I still claim that reproducible builds are technical, not political.
CONFIG_MODULE_SIGN_ALL=y is literally the only thing in the kernel
that's incompatible with reproducible builds.

Yes, the build gets messier, but it's not that bad.  It's even less
bad if we'd be willing to accept kmod changes as a prerequisite (so
kmod would generate the proofs on the fly from a little database
instead of appending the proof to each .ko file

There's even a (nasty) implementation:
https://wiki.debian.org/SameKernel  I'm sure we could make it much
cleaner (and even make it a normal config option that would generate a
bzImage that depends only on the kernel tree and exact toolchain
version) if we put a bit of effort in.

--Andy

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

[George Spelvin]

Linus Torvalds wrote:
> It's also very annoying because the whole build gets much nastier,
> particularly if you want to have modules in external trees.
> 
> In short, I don't see any actual *advantages* over just using signed
> modules. Signing is much more flexible, and thanks to that extra
> indirection (the signing key), there are no ordering constraints on
> generating modules vs the kernel.

That's why I originally wrote:
>> 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.

Reproducible builds are an attractive security feature; they enable
things like distributed double compilation.  But as you point out,
his proposed mechanism is annoyingly less flexible.

It would have to be an optional alternative to the existing public key,
not a replacement.


It seems that there are two basic ways to satisfy the distributions:

1) Create a tool to canonicalize the kernel and modules,
   stripping out the signatures before comparing them.  This has
   precedent in the way the prelink tool can un-prelink binaries
   so that hashes can be verified.

2) Provide something like Andy's hash tree that covers the in-tree case,
   in addition to the existing public-key signatures.  A reproducible
   build would just not use the public key, but it would still be available.

   One note: if the module hash database were kept separately from the
   modules, then it would only need to store the 2n-1 distinct hashes,
   not n log n.  Or, if you don't mind doing a bit more hashing, you
   could just store the n module hashes and linearly hash that list.
   That's reasonable as long as the master list of modules (32 bytes
   per module) is no larger than the modules being verified.

In both cases, the additional code is part of the attack surface.
The issue is which is less effort, less bugs, and more secure?

While option 1 avoids complcating the kernel by throwing the entire
problem over the fence to the distributions, Andy has a point that adding
option 2 to the kernel might be a lot simpler overall.


I'm also trying to think if the same issues might arise for other
code that loads modules, but the signatures are only an issue when
the "main" binary is loaded from a more trustworthy source than the
modules, a situation that is rare outside the kernel.

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

[Linus Torvalds]

On Fri, May 22, 2015 at 7:13 AM, George Spelvin <linux@horizon.com> wrote:
>
> 1) Create a tool to canonicalize the kernel and modules,
>    stripping out the signatures before comparing them.  This has
>    precedent in the way the prelink tool can un-prelink binaries
>    so that hashes can be verified.

So I'd obviously prefer this, so that we have just one model for verification.

I forget the exact details of the signature (and am way too lazy to
look it up), but for the modules themselves, it's just appended to the
module contents. So getting rid of the signature is literally just
truncating the module to the original size.

For the kernel image, it's a bit nastier, since the public key is just
inserted into the object file as variables (system_certificate_list:
"__cert_list_start...__cert_list_end:" and the length in "unsigned
long system_certificate_list_size"). And because the size of the
certificate list is variable, you can't just zero it out or anything
like that to make things compare equal.

Of course, even just zeroing that out will probably work as long as
you use the *same* setup (ie kernels with just the one randomly
generated key will probably have the same certificate size - I say
"probably" because I didn't check how the encoding might affect it)

But we might also simply decide to pack the keys differently. I'd
personally be ok with it being in the initrd, for example, although
for all I know that might screw up the people who actually want to use
the BIOS secure booting thing (I don't know how much that verifies).

             Linus

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

[Andy Lutomirski]

On Fri, May 22, 2015 at 1:40 PM, Linus Torvalds
<torvalds@linux-foundation.org> wrote:
> On Fri, May 22, 2015 at 7:13 AM, George Spelvin <linux@horizon.com> wrote:
>>
>> 1) Create a tool to canonicalize the kernel and modules,
>>    stripping out the signatures before comparing them.  This has
>>    precedent in the way the prelink tool can un-prelink binaries
>>    so that hashes can be verified.
>
> So I'd obviously prefer this, so that we have just one model for verification.
>

In the threat model where module signatures matter in the first place
[1], this prevents reproducible builds from serving their purpose.  I
can build a kernel with a fresh signing key and throw away the private
key.  You can build a canonically identical kernel with a private key
that you keep.  A third party using mine is safe, but a third party
using yours is unsafe, even though the whole packages canonicalize to
exactly the same bytes.

[1] I still think this is a silly threat model, but many people
disagree with me.

--Andy

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

[Linus Torvalds]

On Fri, May 22, 2015 at 1:44 PM, Andy Lutomirski <luto@amacapital.net> wrote:
>
> In the threat model where module signatures matter in the first place
> [1], this prevents reproducible builds from serving their purpose.  I
> can build a kernel with a fresh signing key and throw away the private
> key.  You can build a canonically identical kernel with a private key
> that you keep.  A third party using mine is safe, but a third party
> using yours is unsafe, even though the whole packages canonicalize to
> exactly the same bytes.

So the thing is, I don't see why the third party couldn't just re-sign
his kernel with his own key (and throw it away).

Now he *is* safe. He can verify that the kernel and module images
match, and he has just guaranteed that no other modules can be loaded,
since module loading depends on *his* key.

So even if the silly case, I think signatures actually work fine.

And if he doesn't have access to all modules, then he wasn't safe with
the hash model anyway, because he'd have hashes in the kernel that he
couldn't validate.  So by definition, he'd have to have access to
everything he needs to just re-sign things.

And yes, he would need the ability to insert his own public key in the
kernel image (he already has the ability to re-sign the modules, we
have the script for that in the kernel build tree).

I still think that kind of "strip off and re-populate" the signatures
is a better model than having two completely different validation
models. I also suspect it's less work (although I do agree that it
likely means that we should package out certs differently).

But whatever. Code talks louder than words. If you have a good model
that does *not* screw up the build, and isn't too nasty, maybe we can
add that alongside signature verification.

                 Linus

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

[David Howells]

Linus Torvalds <torvalds@linux-foundation.org> wrote:

> And yes, he would need the ability to insert his own public key in the
> kernel image (he already has the ability to re-sign the modules, we
> have the script for that in the kernel build tree).

With UEFI he could also store his key there.  We assume we can trust the keys
there.

David

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

[Linus Torvalds]

On Fri, May 22, 2015 at 3:18 PM, David Howells <dhowells@redhat.com> wrote:
>
> With UEFI he could also store his key there.  We assume we can trust the keys
> there.

We assume no such thing. The normal situation is that people are *not*
supposed to touch any keys in UEFI, for all the usual reasons.

                Linus

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

[David Howells]

Linus Torvalds <torvalds@linux-foundation.org> wrote:

> I forget the exact details of the signature ..., but for the modules
> themselves, it's just appended to the module contents.

Yes.

> And because the size of the certificate list is variable, you can't just
> zero it out or anything like that to make things compare equal.

Since it's discarded at the end of boot, it could be padded significantly.

Also the kernel image gets compressed and a prologue attached before being
placed in the binary RPMs or whatever, so you can't zero out the keys in those
very easily.

> But we might also simply decide to pack the keys differently. I'd
> personally be ok with it being in the initrd, for example, although
> for all I know that might screw up the people who actually want to use
> the BIOS secure booting thing

We wouldn't be able to trust any key loaded from the initrd unless the initrd
was itself verifiable.  Further, the initrd, at least in Fedora, gets composed
on the running system upon kernel installation so that it holds just the
modules you need to keep the size down.

> (I don't know how much that verifies).

The BIOS secure booting thing verifies the shim, grub and the kernel, as I
understand it.  The kernel then verifies modules and kexec images.

David

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

[Andy Lutomirski]

On Fri, May 22, 2015 at 3:15 PM, David Howells <dhowells@redhat.com> wrote:
> Linus Torvalds <torvalds@linux-foundation.org> wrote:
>
>> I forget the exact details of the signature ..., but for the modules
>> themselves, it's just appended to the module contents.
>
> Yes.
>
>> And because the size of the certificate list is variable, you can't just
>> zero it out or anything like that to make things compare equal.
>
> Since it's discarded at the end of boot, it could be padded significantly.

If you use the hash tree approach, the size of the thing in bzImage is constant.

--Andy

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

[David Howells]

Andy Lutomirski <luto@amacapital.net> wrote:

> > Since it's discarded at the end of boot, it could be padded significantly.
> 
> If you use the hash tree approach, the size of the thing in bzImage is
> constant.

Given that bzImage is usually compressed, a whole slew of contiguous zero
padding is also constant in size.

David

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

[Andy Lutomirski]

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

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

[George Spelvin]

Andy Lutomirski wrote:
> 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.

Well, does the kernel store the number of levels in the hash tree along
with the hash, or believe the module?

The other practical issue is whether 2x256 bits = 64 bytes of concatenated
hashes can look enough like an ELF header to be loaded.  Or contain
enough payload do anything "interesting".

But that sort of cheap trick is putting the ELF header parsing on the
front lines (i.e. it's now part of the attack surface).  I fully agree
that it's bad crypto design and the crypto should fully validate
the input before passing it on.

>> 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.

Not at all; if anything it's inspired by the xor-1 trick.  It works
exactly the same, you just omit the level beccause it's derivable from
i^1, i>>1^1, i>>2^1, etc.

All you're doing is storing (i | 1<<level).  The position of the msbit
gives the level, while the lsbits are unmodified, so the XOR trick is
also unmodified.


> 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 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.)

It would also take some hacking on the spec to cover hashing separate
messages; Sakura is specified to cover various ways of breaking up a
single message into pieces which are logically concatenated.

Should we automatically generate a module signing key at all?

[David Howells]

Hi Michal, Dave,

Should we automatically generate a module signing key at all since that has
the possibility of accidentally overwriting a key that the builder has placed
in the tree?

Should we instead provide a script:

	./scripts/generate-key

That generates a key if run and make it so that the build fails if you turn on
module signing and there's no key.

The script could then be parameterised, eg:

	./scripts/generate-key -n dhowells@redhat.com -k rsa2048 -d sha256 \
		-o ./my-signing-key.priv -x ./my-signing-key.x509 \
		-p "correct horse battery staple"

Yes, this might throw randconfig into a strop but that can be dealt with by:

 (1) Requiring anyone who runs randconfig to provide a key first just in case.

 (2) Marking the CONFIG_MODULE_SIG_ALL option to be ignored by randconfig - it
     only applies during installation anyway.

 (3) Accept that module *installation* will fail due to a lack of private key
     and just handle a complete lack of X.509 certs in the source and build
     dirs when assembling system_certificates.S.

David

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

[David Woodhouse]

[-- Attachment #1: Type: text/plain, Size: 584 bytes --]

On Mon, 2015-05-18 at 17:04 +0100, David Howells wrote:
> Should we automatically generate a module signing key at all since 
> that has the possibility of accidentally overwriting a key that the 
> builder has placed in the tree?

I prefer the other solution I suggested a few minutes ago — let
signing_key.{priv,x509} be autogenerated, and if the user wants to
provide their own then let them call it something else.

-- 
David Woodhouse                            Open Source Technology Centre
David.Woodhouse@intel.com                              Intel Corporation

[-- Attachment #2: smime.p7s --]
[-- Type: application/x-pkcs7-signature, Size: 5691 bytes --]

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

[Linus Torvalds]

On Mon, May 18, 2015 at 9:19 AM, David Woodhouse <dwmw2@infradead.org> wrote:
>
> I prefer the other solution I suggested a few minutes ago — let
> signing_key.{priv,x509} be autogenerated, and if the user wants to
> provide their own then let them call it something else.

Absolutely. And external keys probably shouldn't be in the build tree
at all, they should be a pointer to outside the build tree (ie "I have
my magic kernel key on the USB key that I mount at xyz").

               Linus

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

[David Woodhouse]

[-- Attachment #1: Type: text/plain, Size: 1614 bytes --]

On Mon, 2015-05-18 at 09:22 -0700, Linus Torvalds wrote:
> On Mon, May 18, 2015 at 9:19 AM, David Woodhouse <dwmw2@infradead.org
> > wrote:
> >
> > I prefer the other solution I suggested a few minutes ago — let
> > signing_key.{priv,x509} be autogenerated, and if the user wants to
> > provide their own then let them call it something else.
> 
> Absolutely. And external keys probably shouldn't be in the build tree
> at all, they should be a pointer to outside the build tree (ie "I 
> have my magic kernel key on the USB key that I mount at xyz").

I basically have that already working at 
http://git.infradead.org/users/dwmw2/modsign-pkcs11-c.git


For an external key, I think I'm happy to insist that *both* cert and
key be present at $CONFIG_MODULE_SIG_KEY — it's either a PEM file with
both, or a PKCS#11 URI which identifies both. There doesn't seem to be
much point in allowing them to be in separate files.

I'm tempted to convert the autogenerated keys to do the same, so we
*always* extract signing_key.x509 from the 'key' file. But then again,
it (counter-intuitively) makes the dependencies non-trivial so I probably
won't.

I am moderately unhappy with the fact that CONFIG_MODULE_SIG_KEY being
equal to its default of 'signing_key.priv' is a special case meaning
'in-tree, autogenerated'. My first incarnation had an explicit boolean
variable for 'use an external key' but... randconfig would have broken.

-- 
David Woodhouse                            Open Source Technology Centre
David.Woodhouse@intel.com                              Intel Corporation

[-- Attachment #2: smime.p7s --]
[-- Type: application/x-pkcs7-signature, Size: 5691 bytes --]

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

[Linus Torvalds]

On Mon, May 18, 2015 at 9:04 AM, David Howells <dhowells@redhat.com> wrote:
>
> Should we instead provide a script:
>
>         ./scripts/generate-key
>
> That generates a key if run and make it so that the build fails if you turn on
> module signing and there's no key.

That would just be stupid.

I'm not ever applying a patch like that. That would absolutely destroy
the sane "git clean + rebuild" model.

Why the hell would you want to make the sane case that people actually
*use* be harder to use.

Nobody sane bothers with long-term keys. They are inconvenient and less secure.

Put the onus on making it inconvenient on those people who actually
have special keys, not on normal people.

                   Linus

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

[Andy Lutomirski]

On 05/18/2015 09:20 AM, Linus Torvalds wrote:
> On Mon, May 18, 2015 at 9:04 AM, David Howells <dhowells@redhat.com> wrote:
>>
>> Should we instead provide a script:
>>
>>          ./scripts/generate-key
>>
>> That generates a key if run and make it so that the build fails if you turn on
>> module signing and there's no key.
>
> That would just be stupid.
>
> I'm not ever applying a patch like that. That would absolutely destroy
> the sane "git clean + rebuild" model.
>
> Why the hell would you want to make the sane case that people actually
> *use* be harder to use.
>
> Nobody sane bothers with long-term keys. They are inconvenient and less secure.
>
> Put the onus on making it inconvenient on those people who actually
> have special keys, not on normal people.
>

I think we should get rid of the idea of automatically generated signing 
keys entirely.  Instead I think we should generate, at build time, a 
list of all the module hashes and link that into vmlinux.

If we want to make it better, we could instead have a concept of 
dynamically loadable module verifiers.  A module is acceptable if any of 
the verifiers approve.  We autogenerate module_hashes.ko, which 
registers a verifier that accepts the modules that were built by the 
kernel build in question.  The main vmlinux image includes another 
verifier that accepts *only* module_hashes.ko as built by the build in 
question.

Then, if anyone actually wants to use a public key to verify modules, 
they can build the public key into a module as opposed to dragging all 
of the public key crud into the main kernel image.

Also, this scheme is compatible with deterministic builds, whereas the 
current scheme is fundamentally broken if you try to deterministically 
build a kernel without trusting some key issuer.

--Andy

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

[David Woodhouse]

On Mon, 2015-05-18 at 17:51 -0700, Andy Lutomirski wrote:
> I think we should get rid of the idea of automatically generated signing 
> keys entirely.  Instead I think we should generate, at build time, a 
> list of all the module hashes and link that into vmlinux.

How many module hashes can you have hard-coded into the image, before
all that (non-compressible, I hope!) data ends up being larger than the
'public key crud'?

If you really wanted to make the public key version minimal, I bet you
could rip out the X.509 support and make it *just* check that the module
is signed by a single specified RSA public key. We're fairly certain to
have a hash algorithm in the kernel already, and all we really need on
top of that is RSA-encrypt — for which there are other uses, too.

> Also, this scheme is compatible with deterministic builds, whereas the 
> current scheme is fundamentally broken if you try to deterministically 
> build a kernel without trusting some key issuer.

Well, if you're just trying to check that you can reproduce the previous
kernel then you don't need the private key at all. You don't get to
reproduce the *signing* step from scratch; all you can do is validate
that the previously-generated signature is still correct. But you can
reproduce the *compilation*.

-- 
David Woodhouse                            Open Source Technology Centre
David.Woodhouse@intel.com                              Intel Corporation

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

[Linus Torvalds]

On Mon, May 18, 2015 at 5:51 PM, Andy Lutomirski <luto@kernel.org> wrote:
>
> I think we should get rid of the idea of automatically generated signing
> keys entirely.  Instead I think we should generate, at build time, a list of
> all the module hashes and link that into vmlinux.

Ugh. I think that would be a mistake. It doesn't add any new security
(it's 100% equivalent to just using a throw-away key), and it adds new
complexity and a new ordering dependency.

Yes, yes, "throwing away the key" is a somewhat gray area, and just
unlinking the key-file without any secure erase in theory makes it
recoverable. In practice, though, it is fine. If you have an attacker
that has raw access to your disk and almost infinite resources, they
have easier ways to make your life miserable.

Even a non-secure unlinking of the temporary key file is going to make
things like rootkit authors give up on trying to recover it. Really.

So creating a whole new infrastructure that is more inconvenient than
just key signing and cannot be used to handle cases that key signing
*does* handle is definitely not worth it. It's technically the
inferior solution, and it's more work.

                Linus

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

[Andy Lutomirski]

On Tue, May 19, 2015 at 10:44 AM, Linus Torvalds
<torvalds@linux-foundation.org> wrote:
> On Mon, May 18, 2015 at 5:51 PM, Andy Lutomirski <luto@kernel.org> wrote:
>>
>> I think we should get rid of the idea of automatically generated signing
>> keys entirely.  Instead I think we should generate, at build time, a list of
>> all the module hashes and link that into vmlinux.
>
> Ugh. I think that would be a mistake. It doesn't add any new security
> (it's 100% equivalent to just using a throw-away key), and it adds new
> complexity and a new ordering dependency.
>
> Yes, yes, "throwing away the key" is a somewhat gray area, and just
> unlinking the key-file without any secure erase in theory makes it
> recoverable. In practice, though, it is fine. If you have an attacker
> that has raw access to your disk and almost infinite resources, they
> have easier ways to make your life miserable.

Throwing away the key is outright impossible in some contexts.

https://wiki.debian.org/ReproducibleBuilds

--Andy

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

[Linus Torvalds]

On Tue, May 19, 2015 at 10:58 AM, Andy Lutomirski <luto@amacapital.net> wrote:
>
> Throwing away the key is outright impossible in some contexts.
>
> https://wiki.debian.org/ReproducibleBuilds

Bah. That's just stupid.

Sure, if you have to use "cmp" to compare your builds, you can't embed
random one-time keys. Tough.

That's a problem with your environment, and not a technical argument,
it's a political one.

I couldn't care less. "Doctor, doctor, it hurts when I use a stapler
on my forehead".

Debian has lots of "rules". That doesn't make it right.

                 Linus

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

[David Woodhouse]

On Tue, 2015-05-19 at 10:58 -0700, Andy Lutomirski wrote:
> 
> Throwing away the key is outright impossible in some contexts.
> 
> https://wiki.debian.org/ReproducibleBuilds

Are any of the benefits described at
https://wiki.debian.org/ReproducibleBuilds/About *not* just as
achievable with the method I suggested — where you throw away the key
and just validate that your builds are identical *except* for the
signatures... which you can reuse, since your builds were identical.

-- 
dwmw2

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

[Andy Lutomirski]

On Tue, May 19, 2015 at 11:08 AM, David Woodhouse <dwmw2@infradead.org> wrote:
> On Tue, 2015-05-19 at 10:58 -0700, Andy Lutomirski wrote:
>>
>> Throwing away the key is outright impossible in some contexts.
>>
>> https://wiki.debian.org/ReproducibleBuilds
>
> Are any of the benefits described at
> https://wiki.debian.org/ReproducibleBuilds/About *not* just as
> achievable with the method I suggested — where you throw away the key
> and just validate that your builds are identical *except* for the
> signatures... which you can reuse, since your builds were identical.

Yes, blatantly.  Quoting that link:

Should reproducible uploads become mandatory, then the incentive of an
attacker to compromise the system of a developer with upload rights is
lowered because it is not anymore possible for the developer to upload
a binary that does not match the uploaded sources.

In the context of a kernel, this means that I shouldn't have to trust
the machine that actually generated the binary.  In principle, I
shouldn't even need to trust the person who generated the package,
since the package should be easily comparable to kernel.org sources.

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.

The actual runtime code needed to implement a hash tree solution is
maybe twenty lines.  The bzImage will be smaller, and the modules will
be smaller (although the latter is only true because the current
scheme is bloated).  The only tricky part is getting the build process
to work.

--Andy

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

[David Woodhouse]

On Tue, 2015-05-19 at 11:12 -0700, Andy Lutomirski wrote:
> With your proposal, I need to trust that whoever built the actual
> running kernel image really did throw away the key. 

Ah right, that makes sense.

So it might make sense to use the LSM hook for checking hashes then.
It's kind of orthogonal to the *signing* discussion though.

-- 
dwmw2

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

[Andy Lutomirski]

On Tue, May 19, 2015 at 11:38 AM, David Woodhouse <dwmw2@infradead.org> wrote:
> On Tue, 2015-05-19 at 11:12 -0700, Andy Lutomirski wrote:
>> With your proposal, I need to trust that whoever built the actual
>> running kernel image really did throw away the key.
>
> Ah right, that makes sense.
>
> So it might make sense to use the LSM hook for checking hashes then.
> It's kind of orthogonal to the *signing* discussion though.

I think it's very much related.  Quoting the original discussion that
prompted this:

On 05/18/2015 09:20 AM, Linus Torvalds wrote:
> On Mon, May 18, 2015 at 9:04 AM, David Howells <dhowells@redhat.com> wrote:
>>
>> Should we instead provide a script:
>>
>>          ./scripts/generate-key
>>
>> That generates a key if run and make it so that the build fails if you turn on
>> module signing and there's no key.
>
> That would just be stupid.
>
> I'm not ever applying a patch like that. That would absolutely destroy
> the sane "git clean + rebuild" model.
>
> Why the hell would you want to make the sane case that people actually
> *use* be harder to use.
>
> Nobody sane bothers with long-term keys. They are inconvenient and less secure.
>
> Put the onus on making it inconvenient on those people who actually
> have special keys, not on normal people.
>

If we use hashes instead of signatures on in-tree modules (at least in
the case where no long-term key is provided), then generation of the
temporary signing key stops being an issue because there is no longer
a temporary signing key.

Two birds, one stone :)

--Andy

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

[David Woodhouse]

On Tue, 2015-05-19 at 11:49 -0700, Andy Lutomirski wrote:
> 
> If we use hashes instead of signatures on in-tree modules (at least in
> the case where no long-term key is provided), then generation of the
> temporary signing key stops being an issue because there is no longer
> a temporary signing key.

With signatures I can make a one-line change to a module and rebuild it,
and still load it without having to rebuild my vmlinux to 'permit' it.

My signing key is valid for as long as I *choose* it to be valid.

I appreciate why that's a problem in your scenario, but it's a valid and
useful feature of signatures, and I don't think we can just abandon it.

-- 
dwmw2

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

[Andy Lutomirski]

On Tue, May 19, 2015 at 1:00 PM, David Woodhouse <dwmw2@infradead.org> wrote:
> On Tue, 2015-05-19 at 11:49 -0700, Andy Lutomirski wrote:
>>
>> If we use hashes instead of signatures on in-tree modules (at least in
>> the case where no long-term key is provided), then generation of the
>> temporary signing key stops being an issue because there is no longer
>> a temporary signing key.
>
> With signatures I can make a one-line change to a module and rebuild it,
> and still load it without having to rebuild my vmlinux to 'permit' it.
>
> My signing key is valid for as long as I *choose* it to be valid.
>
> I appreciate why that's a problem in your scenario, but it's a valid and
> useful feature of signatures, and I don't think we can just abandon it.

True, but I'd consider that use case (running a kernel built on a
development machine) to be more in line with unsigned use or long-term
(maybe medium-term) signing keys.

IOW, for this use case, running scripts/generate_module_signing_key or
whatever and configuring accordingly seems entirely reasonable to me.
Or you could just turn off forced module signature verification since
keeping the signing key in plaintext on your machine mostly negates
any benefit of verifying signatures on that machine at runtime.

--Andy

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

[David Woodhouse]

On Tue, 2015-05-19 at 13:05 -0700, Andy Lutomirski wrote:
> > I appreciate why that's a problem in your scenario, but it's a valid and
> > useful feature of signatures, and I don't think we can just abandon it.
> 
> True, but I'd consider that use case (running a kernel built on a
> development machine) to be more in line with unsigned use or long-term
> (maybe medium-term) signing keys.
> 
> IOW, for this use case, running scripts/generate_module_signing_key or
> whatever and configuring accordingly seems entirely reasonable to me.
> Or you could just turn off forced module signature verification since
> keeping the signing key in plaintext on your machine mostly negates
> any benefit of verifying signatures on that machine at runtime.

Perhaps so (although it's ignoring use cases where the build tree is
somewhere secure and internal and I'm deploying to a server which is
more accessible).

But we already *fixed* the problem of generating the signing key
automatically. The in-tree signing_key.{priv,x509} are always transient
auto-generated files now, and the ambiguity is gone. As a side-effect of
what I was already doing to enable PKCS#11. It was mostly just a
documentation change.

So I'm not sure I see the point of ditching it, now that it's working.

-- 
David Woodhouse                            Open Source Technology Centre
David.Woodhouse@intel.com                              Intel Corporation

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

[David Howells]

Andy Lutomirski <luto@amacapital.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.

And that doesn't include the issue of hashing the firmware blobs you might
need.

> 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.

David

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

[Andy Lutomirski]

On Tue, May 19, 2015 at 11:50 AM, David Howells <dhowells@redhat.com> wrote:
> Andy Lutomirski <luto@amacapital.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@redhat.com> wrote:
> Andy Lutomirski <luto@amacapital.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

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

[David Howells]

Andy Lutomirski <luto@amacapital.net> 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.

Now you've got a different problem.  Unless you want to load the entire tree
in one go (in which case you're back to the kernel space issue), the kernel
now has to be able to pull it piecemeal from storage and the initramfs builder
either has to pull in the entire tree or select a subset.  Further, if the
initfamfs only contains a subtree, then the kernel has to be able to switch to
the full tree as some point.

> > 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.

>From a distribution point of view, a hash list of all known firmware is icky
as all the kernels maintained by the distribution would have to be updated
each time a new firmware blob needs listing.  Further, all past known firmware
would have to be kept in the list and could never be discarded lest you
prevent someone's machine from booting.

David

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

[Andy Lutomirski]

On Thu, May 21, 2015 at 9:10 AM, David Howells <dhowells@redhat.com> wrote:
> Andy Lutomirski <luto@amacapital.net> 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.
>
> Now you've got a different problem.  Unless you want to load the entire tree
> in one go (in which case you're back to the kernel space issue), the kernel
> now has to be able to pull it piecemeal from storage and the initramfs builder
> either has to pull in the entire tree or select a subset.  Further, if the
> initfamfs only contains a subtree, then the kernel has to be able to switch to
> the full tree as some point.

Each module would just package its proof as part of the module file.
After the kernel build is done, no one ever needs to see the whole
tree at once.

>
>> > 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.
>
> From a distribution point of view, a hash list of all known firmware is icky
> as all the kernels maintained by the distribution would have to be updated
> each time a new firmware blob needs listing.  Further, all past known firmware
> would have to be kept in the list and could never be discarded lest you
> prevent someone's machine from booting.
>

Sorry, I mis-spoke.  I don't think we should use a hash for firmware,
except possibly for Atomic-like systems, in which case we should
really just turn off firmware signature verification entirely in favor
of using IMA, dm-verity or similar to verify the entire root fs.

--Andy


> David



-- 
Andy Lutomirski
AMA Capital Management, LLC

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

[Pavel Machek]

On Tue 2015-05-19 10:44:47, Linus Torvalds wrote:
> On Mon, May 18, 2015 at 5:51 PM, Andy Lutomirski <luto@kernel.org> wrote:
> >
> > I think we should get rid of the idea of automatically generated signing
> > keys entirely.  Instead I think we should generate, at build time, a list of
> > all the module hashes and link that into vmlinux.
> 
> Ugh. I think that would be a mistake. It doesn't add any new security
> (it's 100% equivalent to just using a throw-away key), and it adds new
> complexity and a new ordering dependency.
> 
> Yes, yes, "throwing away the key" is a somewhat gray area, and just
> unlinking the key-file without any secure erase in theory makes it
> recoverable. In practice, though, it is fine. If you have an attacker
> that has raw access to your disk and almost infinite resources, they
> have easier ways to make your life miserable.

We should really implement secure erase, and it probably needs to be
at kernel level.

> Even a non-secure unlinking of the temporary key file is going to make
> things like rootkit authors give up on trying to recover it. Really.

Placing the key in some kind of ram filesystem where erase is easy to
do might be easy solution to this...
									Pavel
-- 
(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html

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

[Rusty Russell]

Andy Lutomirski <luto@kernel.org> writes:
> On 05/18/2015 09:20 AM, Linus Torvalds wrote:
>> On Mon, May 18, 2015 at 9:04 AM, David Howells <dhowells@redhat.com> wrote:
>>>
>>> Should we instead provide a script:
>>>
>>>          ./scripts/generate-key
>>>
>>> That generates a key if run and make it so that the build fails if you turn on
>>> module signing and there's no key.
>>
>> That would just be stupid.
>>
>> I'm not ever applying a patch like that. That would absolutely destroy
>> the sane "git clean + rebuild" model.
>>
>> Why the hell would you want to make the sane case that people actually
>> *use* be harder to use.
>>
>> Nobody sane bothers with long-term keys. They are inconvenient and less secure.
>>
>> Put the onus on making it inconvenient on those people who actually
>> have special keys, not on normal people.
>>
>
> I think we should get rid of the idea of automatically generated signing 
> keys entirely.  Instead I think we should generate, at build time, a 
> list of all the module hashes and link that into vmlinux.

Yep, suggested that long ago.  But people want signatures, because
the actual push for pubkeys was never the temp-pubkey model.

Cheers,
Rusty.

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

[David Howells]

Andy Lutomirski <luto@kernel.org> wrote:

> I think we should get rid of the idea of automatically generated signing keys
> entirely.  Instead I think we should generate, at build time, a list of all
> the module hashes and link that into vmlinux.

Just in Fedora 21:

warthog>rpm -ql kernel-modules | grep [.]ko | wc -l
3604
warthog>rpm -ql kernel-modules-extra | grep [.]ko | wc -l
480

So that's >4000 modules, each signed with a SHA256 sum (32 bytes).  That's
more than 125K of unswappable memory.  And it's uncompressible as Dave pointed
out.  And that doesn't include any metadata to match a module to a digest, but
rather assumes we just scan through the entire list comparing against each
SHA256 sum until we find one that matches.

> Then, if anyone actually wants to use a public key to verify modules, they can
> build the public key into a module as opposed to dragging all of the public
> key crud into the main kernel image.

A chunk of the 'public key crud' has to be in the kernel for other reasons
(the integrity stuff, I think, which has to start before you load any modules)
and the public key stuff is used for other things too (such as kexec and may
well be used for firmware validation in future) - though that doesn't preclude
it being modularised, it does mean that you are likely to load it anyway in
future.

> We autogenerate module_hashes.ko

This just makes things worse.  I suspect all distributions would have to load
it anyway - and you don't really win as it will just make the initramfs bigger
instead of the bzImage.

David

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

[David Woodhouse]

[-- Attachment #1: Type: text/plain, Size: 1244 bytes --]

On Tue, 2015-05-19 at 09:53 +0100, David Howells wrote:
> 
> Just in Fedora 21:
> 
> warthog>rpm -ql kernel-modules | grep [.]ko | wc -l
> 3604
> warthog>rpm -ql kernel-modules-extra | grep [.]ko | wc -l
> 480
> 
> So that's >4000 modules, each signed with a SHA256 sum (32 bytes).  That's
> more than 125K of unswappable memory.  And it's uncompressible as Dave pointed
> out.  And that doesn't include any metadata to match a module to a digest, but
> rather assumes we just scan through the entire list comparing against each
> SHA256 sum until we find one that matches.

If you *really* wanted to do it, there might be ways round this
explosion of data.

Perhaps the kernel only contains *one* sha256 ― the sha256 of all the
sha256's of all the modules.

Then when one module is loaded, we also have to pass in a table
containing all the other sha256's. The kernel checks the sha256 of what's being loaded, checks it matches what's in the table that was 
also
loaded. And then validates the integrity of that table.

I don't much like that idea, mind you.

-- 
David Woodhouse                            Open Source Technology Centre
David.Woodhouse@intel.com                              Intel Corporation

[-- Attachment #2: smime.p7s --]
[-- Type: application/x-pkcs7-signature, Size: 5691 bytes --]

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

[David Howells]

David Woodhouse <dwmw2@infradead.org> wrote:

> Then when one module is loaded, we also have to pass in a table containing
> all the other sha256's. The kernel checks the sha256 of what's being loaded,
> checks it matches what's in the table that was also loaded. And then
> validates the integrity of that table.

That's basically Andy's idea with a special module containing the table.  But
unless you want to reload the table every time you load a module, you haven't
gained anything.

David

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

[Andy Lutomirski]

On Tue, May 19, 2015 at 1:53 AM, David Howells <dhowells@redhat.com> wrote:
> Andy Lutomirski <luto@kernel.org> wrote:
>
>> I think we should get rid of the idea of automatically generated signing keys
>> entirely.  Instead I think we should generate, at build time, a list of all
>> the module hashes and link that into vmlinux.
>
> Just in Fedora 21:
>
> warthog>rpm -ql kernel-modules | grep [.]ko | wc -l
> 3604
> warthog>rpm -ql kernel-modules-extra | grep [.]ko | wc -l
> 480
>
> So that's >4000 modules, each signed with a SHA256 sum (32 bytes).  That's
> more than 125K of unswappable memory.  And it's uncompressible as Dave pointed
> out.  And that doesn't include any metadata to match a module to a digest, but
> rather assumes we just scan through the entire list comparing against each
> SHA256 sum until we find one that matches.

Let's go through the numbers.  There are two main things that matter,
I think: non-swappable memory and disk space.  For simplicity and
because it doesn't really matter, I'll ignore things like the
filesystem block size.

I'll assume that everyone uses a 256-bit hash.  (This is charitable to
the status quo, since hash size doesn't really matter for public-key
signatures, and the default is SHA-1.)  I'll further assume that there
are 4096 modules or so.

The current kernel uses 4096-bit RSA.  The kernel text needed for
verification seems to be around 21kB (9kB asymmetric_keys + 12kB MPI).
The public key is tiny, and the signature is 512 bytes per module.
(Actually, it's probably more because of PKCS garbage.  I'll ignore
that.)  This is a total of ~21kB of non-swappable storage and 2MB of
disk space for all the signatures.

If the goal were to optimize for size, the kernel should probably use
a much more compact signature scheme, probably some compressed EC
signature.  Ed25519 is 64 bytes per signature, which seems to be more
or less optimal.  That would reduce disk space used to 64 bytes per
module or 256kB for 4k modules.

With the hash-based scheme I outlined, the kernel text needed is
nearly zero.  The overhead in each .ko file is zero, and
module_hashes.ko is 32 bytes per module or 128kB for 4k modules.  It
wins the disk space competition hands down.  Naively, though, all of
that space is non-swappable.  Note that any sensible implementation
would sort the hash list, making hash checks very fast.

One improvement would be to unload module_hashes.ko when you're done
with it.  That's annoying.  A different approach would be to use a
hash tree.  For a basic binary hash tree, the root (module_hashes.ko,
for example) is a single signature, i.e. 32 bytes.  (For simplicity,
we'd store the number of hashes, too.  That would add a couple of
bytes.)  Each module needs log2(number of modules) - 1 hashes stored.
(There's no need for a module to store its own hash, and if the hashes
are sorted before the hash tree is generated, then the edge directions
are all implicit.)  For 4k modules, that's 11 hashes or 352 bytes per
module, for a total of 1408kB for 4k modules.  The kernel text
required is almost zero (while efficiently generating hash trees takes
some thought, verifying them is a very simple loop over the hash
function).  This already beats the status quo in terms of both
non-swappable memory and disk space.  It still loses to Ed25519 or
similar, though.

As David Woodhouse pointed out, if kmod were changed, most of the
overhead could go away.  kmod could generate the proof at module load
time.  That reduces the total overhead to just the list of hashes.

In summary, I think that the hash scheme does quite well for space
efficiency, although the comparison is a bit unfair because the
current code is unnecessarily inefficient.

>
>> Then, if anyone actually wants to use a public key to verify modules, they can
>> build the public key into a module as opposed to dragging all of the public
>> key crud into the main kernel image.
>
> A chunk of the 'public key crud' has to be in the kernel for other reasons
> (the integrity stuff, I think, which has to start before you load any modules)
> and the public key stuff is used for other things too (such as kexec and may
> well be used for firmware validation in future) - though that doesn't preclude
> it being modularised, it does mean that you are likely to load it anyway in
> future.

What integrity stuff?  IIRC dm-verity doesn't use asymmetric crypto at
all.  IMA probably does, though.

For firmware validation, there's no good reason it couldn't work
exactly like module signatures.  Alternatively, firmware validation
could still use loadable public key crypto.  (Again, it could be
unloaded after boot, which is currently impossible.)

For kexec, I think that the main use is for crash dumps, in which case
the hash of the crash kernel could be built in.  Alternatively, if the
crash kernel is identical to the original kernel, it would be
reasonably straightforward to arrange for the kernel to accept itself
as a valid kexec image.

>
>> We autogenerate module_hashes.ko
>
> This just makes things worse.  I suspect all distributions would have to load
> it anyway - and you don't really win as it will just make the initramfs bigger
> instead of the bzImage.

For initramfs use, the hash tree approach works quite well, since the
hash list doesn't need to live in the initramfs.

--Andy

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

[Mimi Zohar]

On Tue, 2015-05-19 at 07:36 -0700, Andy Lutomirski wrote:
> On Tue, May 19, 2015 at 1:53 AM, David Howells <dhowells@redhat.com> wrote:
> > Andy Lutomirski <luto@kernel.org> wrote:
> >
> >> I think we should get rid of the idea of automatically generated signing keys
> >> entirely.  Instead I think we should generate, at build time, a list of all
> >> the module hashes and link that into vmlinux.
> >
> > Just in Fedora 21:
> >
> > warthog>rpm -ql kernel-modules | grep [.]ko | wc -l
> > 3604
> > warthog>rpm -ql kernel-modules-extra | grep [.]ko | wc -l
> > 480
> >
> > So that's >4000 modules, each signed with a SHA256 sum (32 bytes).  That's
> > more than 125K of unswappable memory.  And it's uncompressible as Dave pointed
> > out.  And that doesn't include any metadata to match a module to a digest, but
> > rather assumes we just scan through the entire list comparing against each
> > SHA256 sum until we find one that matches.
> 
> Let's go through the numbers.  There are two main things that matter,
> I think: non-swappable memory and disk space.  For simplicity and
> because it doesn't really matter, I'll ignore things like the
> filesystem block size.
> 
> I'll assume that everyone uses a 256-bit hash.  (This is charitable to
> the status quo, since hash size doesn't really matter for public-key
> signatures, and the default is SHA-1.)  I'll further assume that there
> are 4096 modules or so.
> 
> The current kernel uses 4096-bit RSA.  The kernel text needed for
> verification seems to be around 21kB (9kB asymmetric_keys + 12kB MPI).
> The public key is tiny, and the signature is 512 bytes per module.
> (Actually, it's probably more because of PKCS garbage.  I'll ignore
> that.)  This is a total of ~21kB of non-swappable storage and 2MB of
> disk space for all the signatures.
> 
> If the goal were to optimize for size, the kernel should probably use
> a much more compact signature scheme, probably some compressed EC
> signature.  Ed25519 is 64 bytes per signature, which seems to be more
> or less optimal.  That would reduce disk space used to 64 bytes per
> module or 256kB for 4k modules.
> 
> With the hash-based scheme I outlined, the kernel text needed is
> nearly zero.  The overhead in each .ko file is zero, and
> module_hashes.ko is 32 bytes per module or 128kB for 4k modules.  It
> wins the disk space competition hands down.  Naively, though, all of
> that space is non-swappable.  Note that any sensible implementation
> would sort the hash list, making hash checks very fast.
> 
> One improvement would be to unload module_hashes.ko when you're done
> with it.  That's annoying.  A different approach would be to use a
> hash tree.  For a basic binary hash tree, the root (module_hashes.ko,
> for example) is a single signature, i.e. 32 bytes.  (For simplicity,
> we'd store the number of hashes, too.  That would add a couple of
> bytes.)  Each module needs log2(number of modules) - 1 hashes stored.
> (There's no need for a module to store its own hash, and if the hashes
> are sorted before the hash tree is generated, then the edge directions
> are all implicit.)  For 4k modules, that's 11 hashes or 352 bytes per
> module, for a total of 1408kB for 4k modules.  The kernel text
> required is almost zero (while efficiently generating hash trees takes
> some thought, verifying them is a very simple loop over the hash
> function).  This already beats the status quo in terms of both
> non-swappable memory and disk space.  It still loses to Ed25519 or
> similar, though.
> 
> As David Woodhouse pointed out, if kmod were changed, most of the
> overhead could go away.  kmod could generate the proof at module load
> time.  That reduces the total overhead to just the list of hashes.
> 
> In summary, I think that the hash scheme does quite well for space
> efficiency, although the comparison is a bit unfair because the
> current code is unnecessarily inefficient.

I'm not sure why you're bringing this up at such a late date.   There
was a kernel summit discussion led by Rusty on kernel module
verification.  The result of that discussion was to append the signature
to the kernel modules.  At the same time, Kees Cook was told to define
an LSM kernel module hook.  IMA is on that hook and can be used to
verify kernel modules integrity based on either fiel hashes or
signatures.  The choice is yours.

> >
> >> Then, if anyone actually wants to use a public key to verify modules, they can
> >> build the public key into a module as opposed to dragging all of the public
> >> key crud into the main kernel image.
> >
> > A chunk of the 'public key crud' has to be in the kernel for other reasons
> > (the integrity stuff, I think, which has to start before you load any modules)
> > and the public key stuff is used for other things too (such as kexec and may
> > well be used for firmware validation in future) - though that doesn't preclude
> > it being modularised, it does mean that you are likely to load it anyway in
> > future.
> 
> What integrity stuff?  IIRC dm-verity doesn't use asymmetric crypto at
> all.  IMA probably does, though.

IMA can appraise file integrity based on either hashes or signatures.
The difference being that In addition to file integrity, signatures
provides file provenance.  Going forward we'd like to see software come
with the associated file signatures.

> For firmware validation, there's no good reason it couldn't work
> exactly like module signatures.  Alternatively, firmware validation
> could still use loadable public key crypto.  (Again, it could be
> unloaded after boot, which is currently impossible.)
> 
> For kexec, I think that the main use is for crash dumps, in which case
> the hash of the crash kernel could be built in.  Alternatively, if the
> crash kernel is identical to the original kernel, it would be
> reasonably straightforward to arrange for the kernel to accept itself
> as a valid kexec image.

Kexec is also used to load a different kernel image.

Mimi

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

[Petko Manolov]

On 15-05-19 11:37:49, Mimi Zohar wrote:
> On Tue, 2015-05-19 at 07:36 -0700, Andy Lutomirski wrote:
> > 
> > What integrity stuff?  IIRC dm-verity doesn't use asymmetric crypto at
> > all.  IMA probably does, though.
> 
> IMA can appraise file integrity based on either hashes or signatures.
> The difference being that In addition to file integrity, signatures
> provides file provenance.  Going forward we'd like to see software come
> with the associated file signatures.

I second this one.  There's plenty of situations where integrity isn't enough 
and authenticity is needed.


cheers,
Petko

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

[Andy Lutomirski]

On Tue, May 19, 2015 at 8:37 AM, Mimi Zohar <zohar@linux.vnet.ibm.com> wrote:
> I'm not sure why you're bringing this up at such a late date.   There
> was a kernel summit discussion led by Rusty on kernel module
> verification.  The result of that discussion was to append the signature
> to the kernel modules.  At the same time, Kees Cook was told to define
> an LSM kernel module hook.  IMA is on that hook and can be used to
> verify kernel modules integrity based on either fiel hashes or
> signatures.  The choice is yours.

I didn't notice that discussion.  If I had, I would have suggested this at KS.


--Andy

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

[David Howells]

Andy Lutomirski <luto@amacapital.net> wrote:

> I'll assume that everyone uses a 256-bit hash.

UEFI makes it very likely that SHA256 is in use, at least on x86_64.

> The public key is tiny, and the signature is 512 bytes per module.
> (Actually, it's probably more because of PKCS garbage.

There is metadata selecting the particular key to be checked against, so with
a 512-byte signature, you get around 500 bytes of metadata and ASN.1
wrappings.  We could probably trim that some more by removing PKCS#7 attribute
sections.

We do have to allow people to load external modules.  Yes, you could argue
that you should just disable all your security systems if you want to do
that...

> This is a total of ~21kB of non-swappable storage and 2MB of disk space for
> all the signatures.

Disk space is a lot cheaper than RAM.

> Ed25519

Is it endorsed by various governmental authorities?  It's not entirely clear.
And also the aforementioned authorities may mandate minimum key (eg. 2048) and
digest sizes (eg. 256) which we need to deal with.

> With the hash-based scheme I outlined, the kernel text needed is
> nearly zero.

What matters is kernel text *plus* kernel data.

> What integrity stuff?  IIRC dm-verity doesn't use asymmetric crypto at
> all.  IMA probably does, though.

IMA.

> For firmware validation, there's no good reason it couldn't work exactly
> like module signatures.

That's really impractical.  It would mean that the kernel would have to be
built with a hash, grand-hash, great-grand-hash or whatever that covers every
possible firmware blob you might want to load.

If a vendor releases a new firmware blob, this has to be added to the
linux-firmware hash list, say, then the hash of that added to the kernel, say,
and the kernel rebuilt and reissued before the firmware blob can be used.

With a key-based approach, you just need to get a signature for the new
firmware blob.  You can even sign it yourself and add your key to your UEFI
database.

> For kexec, I think that the main use is for crash dumps

We also want to be able to kexec new kernels on servers to avoid heavy duty
hardware reboot cycles.  But you can't put the new kernel's hash in the old
kernel.

David

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

[Theodore Ts'o]

On Tue, May 19, 2015 at 04:30:17PM +0100, David Howells wrote:
> We do have to allow people to load external modules.  Yes, you could argue
> that you should just disable all your security systems if you want to do
> that...

Is module signing really meant for distro kernels, or would anyone
besides people creating distro kernels care about this?  I thought I
saw some messages (including from Linus) that the "common case" is the
average kernel developer who creates a throw-away key, uses it to sign
all of the modules in the kernel build, and then throws it away.

I wouldn't know, because I don't use module signing at all, and I
don't really see the point.  I build my own kernels for my own use,
which means either modules for my own developer convenience, or if I'm
building it for a server where I really care about security, I'll
build in exactly the drivers I need and disable modules entirely.  So
I'm clearly not the intended use case, either as a distro kernel
release engineer, or as a "build a kernel with modules and then throw
away the key use case".

So I'm really curious --- are there significant numbers of people
doing kernel builds, besides distro kernel engineers, who would use
module signing?  If so, them sure, let's spend time optimizing so that
it's really easy for those folks.  If not, maybe it's simpler just
make things easy for people who will be storing the key in some
external hardware device, and just be done with it.

Cheers,

						- Ted

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

[Petko Manolov]

On 15-05-19 11:55:32, Theodore Ts'o wrote:
>
> So I'm really curious --- are there significant numbers of people
> doing kernel builds, besides distro kernel engineers, who would use
> module signing?  If so, them sure, let's spend time optimizing so that
> it's really easy for those folks.  If not, maybe it's simpler just
> make things easy for people who will be storing the key in some
> external hardware device, and just be done with it.

I am working on a project that requires kernel module authenticity.  Building 
monolithic kernel is not an option.  It is also highly customized system where 
uptime is very important.  The machine is going to be exposed to all the fun of 
contemporary Internet connectivity so every piece of code or data on this box 
must be measured and authenticated prior to accessing it.

I do agree that this is not the common case, though.


cheers,
Petko

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

[Mimi Zohar]

On Tue, 2015-05-19 at 11:55 -0400, Theodore Ts'o wrote:
> On Tue, May 19, 2015 at 04:30:17PM +0100, David Howells wrote:
> > We do have to allow people to load external modules.  Yes, you could argue
> > that you should just disable all your security systems if you want to do
> > that...
> 
> Is module signing really meant for distro kernels, or would anyone
> besides people creating distro kernels care about this?  I thought I
> saw some messages (including from Linus) that the "common case" is the
> average kernel developer who creates a throw-away key, uses it to sign
> all of the modules in the kernel build, and then throws it away.
> 
> I wouldn't know, because I don't use module signing at all, and I
> don't really see the point.  I build my own kernels for my own use,
> which means either modules for my own developer convenience, or if I'm
> building it for a server where I really care about security, I'll
> build in exactly the drivers I need and disable modules entirely.  So
> I'm clearly not the intended use case, either as a distro kernel
> release engineer, or as a "build a kernel with modules and then throw
> away the key use case".
> 
> So I'm really curious --- are there significant numbers of people
> doing kernel builds, besides distro kernel engineers, who would use
> module signing?  If so, them sure, let's spend time optimizing so that
> it's really easy for those folks.  If not, maybe it's simpler just
> make things easy for people who will be storing the key in some
> external hardware device, and just be done with it.

I assume you're signing your kernel images.  Remember the Yubikey NEOs,
given out last year at the kernel summit, they can be used to sign the
kernel images and with David Woodhouse's patches sign the kernel modules
as well.

The next step (as mentioned in this thread), would be for software to
come signed.  The associated public key could be signed by the Yubikey
NEO and loaded onto the trusted IMA keyring.

Mimi

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

[Andy Lutomirski]

On Tue, May 19, 2015 at 10:32 AM, Mimi Zohar <zohar@linux.vnet.ibm.com> wrote:
> On Tue, 2015-05-19 at 11:55 -0400, Theodore Ts'o wrote:
>> On Tue, May 19, 2015 at 04:30:17PM +0100, David Howells wrote:
>> > We do have to allow people to load external modules.  Yes, you could argue
>> > that you should just disable all your security systems if you want to do
>> > that...
>>
>> Is module signing really meant for distro kernels, or would anyone
>> besides people creating distro kernels care about this?  I thought I
>> saw some messages (including from Linus) that the "common case" is the
>> average kernel developer who creates a throw-away key, uses it to sign
>> all of the modules in the kernel build, and then throws it away.
>>
>> I wouldn't know, because I don't use module signing at all, and I
>> don't really see the point.  I build my own kernels for my own use,
>> which means either modules for my own developer convenience, or if I'm
>> building it for a server where I really care about security, I'll
>> build in exactly the drivers I need and disable modules entirely.  So
>> I'm clearly not the intended use case, either as a distro kernel
>> release engineer, or as a "build a kernel with modules and then throw
>> away the key use case".
>>
>> So I'm really curious --- are there significant numbers of people
>> doing kernel builds, besides distro kernel engineers, who would use
>> module signing?  If so, them sure, let's spend time optimizing so that
>> it's really easy for those folks.  If not, maybe it's simpler just
>> make things easy for people who will be storing the key in some
>> external hardware device, and just be done with it.
>
> I assume you're signing your kernel images.  Remember the Yubikey NEOs,
> given out last year at the kernel summit, they can be used to sign the
> kernel images and with David Woodhouse's patches sign the kernel modules
> as well.

If it weren't a giant PITA, I would consider enabling module signing,
but I don't see much point on my system since I don't have secure boot
and I think it's misguided that kernel mode code should be considered
more important to protect than fully privileged user-space code.  I
think that managing the integrity of the filesystem as a whole is much
more important and indirectly protects modules as well.

The remaining thing to protect is the kernel image itself and whatever
trust in the filesystem is rooted in.  The kernel image could be
protected by secure boot or by a TPM that would prevent filesystem
access if the kernel hash is wrong (assuming that the BIOS has usable
TPM support -- TXT would be even better, but it's dangerously broken
on my system).  The filesystem could be protected by a key of some
sort baked into the kernel image.

Keep in mind that, for a normal mutable desktop system, there's no
reason at all to use asymmetric crypto to protect the filesystem or
root block device.  The running system needs to be able to *modify*
the image, so it would need the private key.  This means that
symmetric crypto would be a better choice.

For an atomic system, if the kernel is longer-lived than the root fs
image then we need some way of verifying a root fs image that isn't
rooted in a hash baked into the kernel image.  If they have the same
lifetime, then it makes little difference.

Nonetheless, I think this is all irrelevant to the present discussion.
The sane way to verify modules on an IMA or other integrity-protected
/lib/modules fs is using finit_module.  If that's not available *and*
a user wants to protect kernel mode against root, then the user needs
some kind of module verification.  Both the secure boot compliance use
case and the kernel developer running 'make' with forced verification
use case are IMO quite nicely covered by a hash tree, and using a hash
tree allows deterministic builds and makes the build process cleaner.

If someone wants to deterministically build an entire OS (kernel,
modules, initramfs, and root fs), then a hash tree works for all of
it.  If some authority is needed to verify updates, then that
authority can use asymmetric crypto.

--Andy

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

[Linus Torvalds]

On Tue, May 19, 2015 at 10:43 AM, Andy Lutomirski <luto@amacapital.net> wrote:
>
> If it weren't a giant PITA, I would consider enabling module signing,
> but I don't see much point on my system since I don't have secure boot
> and I think it's misguided that kernel mode code should be considered
> more important to protect than fully privileged user-space code.

What PITA?

Do this:

  CONFIG_MODULE_SIG=y
  CONFIG_MODULE_SIG_FORCE=y
  CONFIG_MODULE_SIG_ALL=y

and you're done. You don't need to do anythign else. There's no PITA.
It just works. I do this in my /etc/kernel-config, so *all* the
kernels I build and boot hjave this, and I never even have think about
it, much less have to do anything special.  I don't even bother
removing the key consciously, because I end up doing "git clean -dqfx
; make allmodconfig ; make -j16" so many times a day during the merge
window anyway that it doesn't last.

Enabling those three config options makes the build generate the key
for you, and assuming you just remove the key after the build/install
(incidentally like I do, or consciously like you *should* do it), it
makes your kernel as secure as if you were to just build everything
into the kernel.

Is it going to fix any *other* security issues? No. But it does mean
that if you somehow have a security issue, the attacker is going to
have a *much* harder time to install a rootkit kernel module that
actively hides the attack from you.

And that is not some theoretical concern. There's been multiple cases of that.

                    Linus

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

[David Howells]

Theodore Ts'o <tytso@mit.edu> wrote:

> Is module signing really meant for distro kernels, or would anyone
> besides people creating distro kernels care about this?

I think this is mainly for distro kernels where we need to provide certainty
and security.

Fedora and RHEL make good use of this for their kernel modules and are now
making use of it for kexec too.  Kernel images are EFI objects - ie. signed PE
files using Microsoft's spec.

Firmware validation isn't a consideration yet, but UEFI interaction is (UEFI
keys, blacklists).

For my own purposes when running kernels on my test machines, I build kernels
with all the necessary drivers built in and boot them directly out of the
build tree by PXE.  Then I copy any modules I'm testing by scp and use them.
I don't generally use signed modules anymore because the modules aren't signed
during the build phase but rather during the module installation phase (which
isn't of any use to me).   I'm not too worried about being attacked on those
machines though as they're rebooted (or powered off) regularly and are crashed
a lot.

> If not, maybe it's simpler just make things easy for people who will be
> storing the key in some external hardware device, and just be done with it.

Did you mean make it possible to only use external hardware for storing the
key?  That wouldn't very convenient for building our kernels in our build farm
- we have a lot of machines and all of them would have to be equiped with the
key.  Besides, we *want* to discard the private key where possible as soon as
possible because then we can't leak it and we can't be forced to disclose it.

David

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

[Theodore Ts'o]

On Tue, May 19, 2015 at 05:23:19PM +0100, David Howells wrote:
> Did you mean make it possible to only use external hardware for storing the
> key?  That wouldn't very convenient for building our kernels in our build farm
> - we have a lot of machines and all of them would have to be equiped with the
> key.  Besides, we *want* to discard the private key where possible as soon as
> possible because then we can't leak it and we can't be forced to disclose it.

Oh, so you are generating a one-time key for each kernel build, and
then dropping the public key into a cert which is then signed by some
trusted CA system?  (Which I presume *would* be done with the private
key stored in some trusted secured hardware --- i.e., YubiKey,
SmartCard, or some other tempest-shielded hardware designed for use by
CA's)?

						- Ted

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

[David Howells]

Theodore Ts'o <tytso@mit.edu> wrote:

> Oh, so you are generating a one-time key for each kernel build,

Yes.

> and then dropping the public key into a cert which is then signed by some
> trusted CA system?

No.  We compile the public key into the vmlinux binary and leave it at that.
Trying to automatically sign the key would expose the signing key through the
buildfarm.

David

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

[Jiri Kosina]

On Tue, 19 May 2015, David Howells wrote:

> That wouldn't very convenient for building our kernels in our build farm 
> - we have a lot of machines and all of them would have to be equiped 
> with the key.  Besides, we *want* to discard the private key where 
> possible as soon as possible because then we can't leak it and we can't 
> be forced to disclose it.

You can still have a dedicated machine that's used just for signing the 
binaries. That machine wouldn't be connected to the network, would be 
physically secured, and would sign through a serial line or so.

-- 
Jiri Kosina
SUSE Labs

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

[Michal Marek]

Dne 20.5.2015 v 05:47 Jiri Kosina napsal(a):
> On Tue, 19 May 2015, David Howells wrote:
> 
>> That wouldn't very convenient for building our kernels in our build farm 
>> - we have a lot of machines and all of them would have to be equiped 
>> with the key.  Besides, we *want* to discard the private key where 
>> possible as soon as possible because then we can't leak it and we can't 
>> be forced to disclose it.
> 
> You can still have a dedicated machine that's used just for signing the 
> binaries. That machine wouldn't be connected to the network, would be 
> physically secured, and would sign through a serial line or so.

Right, that's what CONFIG_MODULE_SIG_ALL=n is meant for -- build the
public key into the kernel, but sign the modules later, outside of the
build system. So you still have to trust the build machine to build what
you ask it to build, but you do not have to trust it not to leak your
private key.

Michal

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

[Michal Marek]

Dne 20.5.2015 v 00:23 David Howells napsal(a):
> For my own purposes when running kernels on my test machines, I build kernels
> with all the necessary drivers built in and boot them directly out of the
> build tree by PXE.  Then I copy any modules I'm testing by scp and use them.
> I don't generally use signed modules anymore because the modules aren't signed
> during the build phase but rather during the module installation phase (which
> isn't of any use to me).

If you really wanted, you could do

  make INSTALL_MOD_PATH=$pwd/tmp modules_install

and then scp the (signed) module tree in ./tmp.

Michal

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

[Andy Lutomirski]

On May 19, 2015 8:30 AM, "David Howells" <dhowells@redhat.com> wrote:
>
> Andy Lutomirski <luto@amacapital.net> wrote:
>
> > I'll assume that everyone uses a 256-bit hash.
>
> UEFI makes it very likely that SHA256 is in use, at least on x86_64.
>
> > The public key is tiny, and the signature is 512 bytes per module.
> > (Actually, it's probably more because of PKCS garbage.
>
> There is metadata selecting the particular key to be checked against, so with
> a 512-byte signature, you get around 500 bytes of metadata and ASN.1
> wrappings.  We could probably trim that some more by removing PKCS#7 attribute
> sections.

You could trim even more by simply not using PKCS#7.  A raw PKCS#1
signature would be just fine.  (We should really be using PSS,
though.)

>
> We do have to allow people to load external modules.  Yes, you could argue
> that you should just disable all your security systems if you want to do
> that...
>

Or use signatures for external modules.  I'm not arguing for removal
of signature support; I'm arguing that the automatically generated key
mechanism be removed in favor of hashes.

> > This is a total of ~21kB of non-swappable storage and 2MB of disk space for
> > all the signatures.
>
> Disk space is a lot cheaper than RAM.
>
> > Ed25519
>
> Is it endorsed by various governmental authorities?  It's not entirely clear.

For users who care about cryptographic security instead of compliance
with poorly designed standards, this is completely irrelevant...

> And also the aforementioned authorities may mandate minimum key (eg. 2048) and
> digest sizes (eg. 256) which we need to deal with.

...and for users who need to comply with unfortunate standards,
there's ECDSA on P-256, which is blessed by NIST.

>
> > With the hash-based scheme I outlined, the kernel text needed is
> > nearly zero.
>
> What matters is kernel text *plus* kernel data.

The kernel data involved is 32 bytes.

>
> > What integrity stuff?  IIRC dm-verity doesn't use asymmetric crypto at
> > all.  IMA probably does, though.
>
> IMA.

I don't think that the needs of IMA users should affect normal people
who run 'make' on their kernel tree.

>
> > For firmware validation, there's no good reason it couldn't work exactly
> > like module signatures.
>
> That's really impractical.  It would mean that the kernel would have to be
> built with a hash, grand-hash, great-grand-hash or whatever that covers every
> possible firmware blob you might want to load.
>
> If a vendor releases a new firmware blob, this has to be added to the
> linux-firmware hash list, say, then the hash of that added to the kernel, say,
> and the kernel rebuilt and reissued before the firmware blob can be used.

Deterministic builds can't apply to firmware regardless, so users are
trusting a vendor one way or another.  And for Chromebook or
Atomic-like uses, hashes are fine.

>
> With a key-based approach, you just need to get a signature for the new
> firmware blob.  You can even sign it yourself and add your key to your UEFI
> database.

Agreed, although I don't understand why UEFI is a reasonable place for
firmware or module keys.  UEFI is a giant implementation detail,
whereas module and firmware validation is really a cross-architecture
thing.

>
> > For kexec, I think that the main use is for crash dumps
>
> We also want to be able to kexec new kernels on servers to avoid heavy duty
> hardware reboot cycles.  But you can't put the new kernel's hash in the old
> kernel.

That should use signatures, too.

AFAICS, none of the cases for which signatures seem better than hashes
make sense in the signing_key.priv model.  If distros want to
configure a public key, too, they're welcome to.  When I do "make &&
make install", I think we shouldn't generate a key pair.

--Andy

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

[David Howells]

Andy Lutomirski <luto@amacapital.net> wrote:

> > There is metadata selecting the particular key to be checked against, so
> > with a 512-byte signature, you get around 500 bytes of metadata and ASN.1
> > wrappings.  We could probably trim that some more by removing PKCS#7
> > attribute sections.
> 
> You could trim even more by simply not using PKCS#7.  A raw PKCS#1
> signature would be just fine.  (We should really be using PSS,
> though.)

Trimming the attributes reduces it to about 150 bytes over the signature.
PKCS#7 is handy because it's a standard that has standard ways of specifying
digest and crypto algorithms and key lookups.  Plus we need it available to
verify PE-signed kernel images.

> ...and for users who need to comply with unfortunate standards,

If you want to get into certain markets, you have to care.

> The kernel data involved is 32 bytes.

No, it isn't.  It's the entire hash list and whatever metadata it requires.
Dynamically loaded kernel data is *still* kernel data.

> I don't think that the needs of IMA users should affect normal people
> who run 'make' on their kernel tree.

The sad fact is that 'normal' Linux users use distribution kernels and don't
give two figs about how it does what it does (or use something like Android
and don't even realise Linux exists).  I'm not that sure people who build
their own kernels can really said to be 'normal' in this sense.

> Deterministic builds can't apply to firmware regardless, so users are
> trusting a vendor one way or another.  And for Chromebook or
> Atomic-like uses, hashes are fine.

That may be so, but that doesn't help Fedora, RHEL and suchlike that run on
less restricted hardware.  For an embedded platform, a monolithic kernel may
also be fine.

> Agreed, although I don't understand why UEFI is a reasonable place for
> firmware or module keys.  UEFI is a giant implementation detail,
> whereas module and firmware validation is really a cross-architecture
> thing.

Because it exists and we have to use it on many new machines, so we might as
well make best use of it if it's there.  Besides, if M$ have their way, it'll
be everywhere - even on your toaster;-)

David

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

[Andy Lutomirski]

On May 19, 2015 11:38 AM, "David Howells" <dhowells@redhat.com> wrote:
>
> Andy Lutomirski <luto@amacapital.net> wrote:
>
> > > There is metadata selecting the particular key to be checked against, so
> > > with a 512-byte signature, you get around 500 bytes of metadata and ASN.1
> > > wrappings.  We could probably trim that some more by removing PKCS#7
> > > attribute sections.
> >
> > You could trim even more by simply not using PKCS#7.  A raw PKCS#1
> > signature would be just fine.  (We should really be using PSS,
> > though.)
>
> Trimming the attributes reduces it to about 150 bytes over the signature.
> PKCS#7 is handy because it's a standard that has standard ways of specifying
> digest and crypto algorithms and key lookups.  Plus we need it available to
> verify PE-signed kernel images.
>
> > ...and for users who need to comply with unfortunate standards,
>
> If you want to get into certain markets, you have to care.
>
> > The kernel data involved is 32 bytes.
>
> No, it isn't.  It's the entire hash list and whatever metadata it requires.
> Dynamically loaded kernel data is *still* kernel data.
>

No, in the hash tree variant, it really is 32 bytes.  No one ever
needs the full list once the build is done.

> > I don't think that the needs of IMA users should affect normal people
> > who run 'make' on their kernel tree.
>
> The sad fact is that 'normal' Linux users use distribution kernels and don't
> give two figs about how it does what it does (or use something like Android
> and don't even realise Linux exists).  I'm not that sure people who build
> their own kernels can really said to be 'normal' in this sense.
>
> > Deterministic builds can't apply to firmware regardless, so users are
> > trusting a vendor one way or another.  And for Chromebook or
> > Atomic-like uses, hashes are fine.
>
> That may be so, but that doesn't help Fedora, RHEL and suchlike that run on
> less restricted hardware.  For an embedded platform, a monolithic kernel may
> also be fine.

Both Fedora and RHEL seems to be moving toward having fully-supported
configurations with immutable root images.  Building those images
reproducibly would be fantastic.  (Of course, if Fedora or RHEL wants
to allow support out-of-tree drivers, that's a different story.)

--Andy

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

[David Howells]

Andy Lutomirski <luto@amacapital.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.

David

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

[David Howells]

Andy Lutomirski <luto@amacapital.net> wrote:

> Both Fedora and RHEL seems to be moving toward having fully-supported
> configurations with immutable root images.  Building those images
> reproducibly would be fantastic.  (Of course, if Fedora or RHEL wants
> to allow support out-of-tree drivers, that's a different story.)

Irrelevant.  initramfs is *not* immutable.  It has different modules in it
depending on what hardware you have.  Further, you *still* need the module and
firmware hash lists in either the kernel or the initramfs to be loaded into
kernel memory before you load the first module because you have to check the
hash on it.

Or are you suggesting a tree of hashed nodes that have leaves that are the
hashes of the modules so you can save a subtree?

David

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

[Andy Lutomirski]

On Tue, May 19, 2015 at 11:57 AM, David Howells <dhowells@redhat.com> wrote:
> Andy Lutomirski <luto@amacapital.net> wrote:
>
>> Both Fedora and RHEL seems to be moving toward having fully-supported
>> configurations with immutable root images.  Building those images
>> reproducibly would be fantastic.  (Of course, if Fedora or RHEL wants
>> to allow support out-of-tree drivers, that's a different story.)
>
> Irrelevant.  initramfs is *not* immutable.  It has different modules in it
> depending on what hardware you have.  Further, you *still* need the module and
> firmware hash lists in either the kernel or the initramfs to be loaded into
> kernel memory before you load the first module because you have to check the
> hash on it.

Well, that's a problem regardless of how module verification works,
and it'll probably need solving at some point.  If the distro can't
sign initramfs, then you can get pwned by an attacker who modifies the
initramfs.  ISTM whatever verifies the kernel image should maybe be
able to verify the initramfs as well.  This might be tricky for distro
use cases, though.

Alternatively, we could eventually support some way of verifying a
hash or signature on each tuple (path, mode, contents) in the
initramfs image so that the only thing an attacker could do is replace
a valid initramfs with a different subset of the maximally complicated
initramfs.  There may be an unavoidable configuration file or two in
there.  In that case, distros should have the initramfs scripts be
reasonably resiliant to a maliciously configured initramfs.

If distros start using a TPM to protect access to the FS, they could
have the TPM verify the initramfs as well.

>
> Or are you suggesting a tree of hashed nodes that have leaves that are the
> hashes of the modules so you can save a subtree?
>

Yes, as in the email I just sent.  (Actually, you never save a full
subtree -- it's implicit.)

--Andy

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

[David Howells]

Andy Lutomirski <luto@amacapital.net> wrote:

> Alternatively, we could eventually support some way of verifying a
> hash or signature on each tuple (path, mode, contents)

Since the initramfs is composed on the system being installed according to the
hardware on that machine, you have to expose this list to meddling during
composition whether you sign it (you need a private key) or hash it (what do
you do with the hash once you've produced it?).

David