Should we automatically generate a module signing key at all?
Quoted 10 lines
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.
Quoted 6 lines
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.
Quoted 4 lines · George Spelvin
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
Quoted 9 lines · Linus Torvalds
Quoted 4 lines · George Spelvin
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.
Quoted 7 lines
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
Quoted 7 lines · Linus Torvalds
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.
Quoted 3 lines · That's why I originally
Quoted 3 lines
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.
Quoted 5 lines · George Spelvin
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
Quoted 9 lines · Linus Torvalds
Quoted 5 lines · George Spelvin
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
Quoted 8 lines · Andy Lutomirski
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
Quoted 3 lines · Linus Torvalds
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
Quoted 3 lines · David Howells
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
Quoted 2 lines · Linus Torvalds
I forget the exact details of the signature ..., but for the modules themselves, it's just appended to the module contents.
Yes.
Quoted 2 lines
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.
Quoted 4 lines
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.
Quoted 1 line
(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
Quoted 11 lines · David Howells
Quoted 2 lines · Linus Torvalds
I forget the exact details of the signature ..., but for the modules themselves, it's just appended to the module contents.
Yes.
Quoted 2 lines
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
Quoted 4 lines · Andy Lutomirski
Quoted 1 line
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
Quoted 17 lines · George Spelvin
Quoted 10 lines
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.Quoted 6 lines
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.
Quoted 5 lines
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.
Quoted 23 lines
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.
Quoted 8 lines
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
Quoted 3 lines · Andy Lutomirski
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.
Quoted 5 lines
Quoted 3 lines
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.
Quoted 5 lines
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.