This article was originally written back in 2014 to accompany the talk I gave at Shmoocon called "The History of Linux Kernel Module Signing". It is a discussion of various Linux kernel module signing implementations while highlighting some of the motivating factors behind various design decisions. I decided it was about time to publish this write up, so here it is.
Before I begin, here are a few notes:
- I have not found kernel module signing implementations outside of those created by Red Hat and by the mainstream Linux developers so there may be other flavors of Linux module signing that I do not mention here.
- The information I present here is based on Linux developer mailing lists and source code I have found. I do not have an insider perspective of the implementation decisions. If you want the ground truth, you should go talk to those developers who are a part of the narrative I present here.
- Although I highlight potential implementation issues, I have not put in the time to build any proof-of-concept exploits (but perhaps you can build one and submit it to the International Journal of PoC || GTFO).
This article has been edited somewhat since it was originally written in my outdoor office. I blame any bugs I inserted on the mosquitoes that were attacking me at the time.
Introduction
Code signing is not just an algorithm, it is a lifestyle. By which I mean there is so much involved in a code signing implementation beyond cryptography and consequentially there are many ways to get it wrong. For example, how the code and signature are formatted, parsed, and interpreted is more important than it may first seem. As someone who has spent a lot of time working with ELF metadata I have decided to focus on two small components of the signing process:
- Where the signature is stored in terms of what metadata is consulted in order to locate the signature
- Which components/bytes in the file are signed and which are not
These may seem like trivial questions, but they are not. Any signature may be handled with multiple tools, each of which needs to parse the signature in order to examine it -- this in and of itself is not trivial. Yet all signature-handling tools must independently agree on the answers to these questions. Cryptographic signatures are useless when tools disagree on these simple questions, yet we can find multiple examples of such failures. Android Master Key-type bugs and X.509 parser differentials ("PKI Layer Cake") are famous examples of code signing failures due to parser differentials. Linux module signing is an interesting case study in that they were not only concerned with the signature scheme itself but also the supporting binary building infrastructure and we can see this reflected in their signature scheme design choices. Also by studying the evolution of the Linux signature systems we can see what the potential pitfalls of a code signing scheme are and design future signature-verifying loaders to avoid such pitfalls.
Background
Here I will briefly describe what code signing is and the ELF file format in which kernel modules are stored. If you are fed up with reading such introductory material, feel free to jump right into my discussion of Linux kernel module signing.
Code signing
The idea behind code signing is fairly simple: we can digitally sign a a file or chunk of code such that another party has high assurance of its origin and that it has not been altered. This is generally implemented as follows:
- Developer builds file/binary
- Developer hashes the file or parts of the file and digitally signs the hash using their private key, usually embedded the signature in a signed version of the file
- User retrieves the signed version of the file
- User hashes the same parts of the file that the developer hashed and checks that the hash they created matches the hash signed with the developer's public key
It is important that different tools operating on the same binary/signature agree on what is signed and where the signature is located. Failure to agree on exactly what is signed can not only lead to Master Key and Layer Cake bugs, but also enable cryptographic attacks. A classic attack that uses ambiguity in how a signature is represented in the PKCS #1 standard is Bleichenbacher's attack. Since then, many attacks of this kind have been discovered, for example the recent BERserk attack.
ELF
ELF, the Executable and Linkable Format, is a flexible file format used to store binaries such as kernel modules, libraries, and executables. ELF was first published in 1990 as part of UNIX System V Release 4 and documented in their ANSI C and Programming Support Tools guide. ELF files not only contain the binary's code and the static data the code operates on, but also metadata the runtime or static linker needs in order to load the file into memory and/or resolve any dependencies on other ELF files such as libraries. Due to the flexibility of ELF, we can easily find ELF files that contain metadata (including signatures) that are not defined in the ELF specification.
Every ELF file includes an ELF header which contains information such as the architecture the ELF's code was compiled for and how to locate the tables of program and/or section headers. Section headers denote named chunks of bytes in the file that are semantically the same, such as a section of code (e.g. ".text") or a section of strings (e.g. ".strtab""). ELF program headers denote groups of sections that should be loaded together at runtime, such as "all read only data including ELF headers" and "all executable code". The Linux kernel module loader, unlike most other ELF-loaders, only processes and loads ELFs based on their section headers.
Linux kernel module signing
Back in 2004 Greg Kroah-Harman noticed that unlike other kernels at the time Linux did not sign its kernel modules so he wrote a proof-of-concept module signing implementation which includes a tool that signs a module and kernel code the checks a module's signature when loaded (Kroah-Hartman, 2004). David Howells contributed to this implementation and continued on to maintain kernel module signing patches for Red Hat (corbet, 2004).
I will present 4 different kernel module signing implementations which I have labeled v0-v2 and the version included in Linux 3.7. These names are labels I created, you will see different labels used in the mailing list posts I reference in this article. Also please note that the code samples I have posted below have been altered, trimmed, and annotated (by me) to make them easier to read and understand.
The code examples I include in this post that locate the signature in an ELF will seem simple and straightforward since ELF metadata can be extracted via simple array traversals and string comparisons. However ELF is a complex format with many objects and metadata tables. The position of a particular object inside the ELF can often be computed in several ways (of which none is known as "canonical"); several distinct table entries must agree in order for all parsers to agree on the target object's location. In other words, ELF metadata can be inconsistent in many ways, and any particular tool or OS component may not be able to notice -- which can cause different tools to interpret the same bytes in such a file differently. The simple-looking parsers we will see below make a lot of assumptions about the file's consistency and merely sweep the mounds of complexity under the rug.
v0
v0 was proposed in 2004 by Greg Kroah-Hartman. Although it did not appear in any of the stable Fedora/RHEL releases, there is evidence that v0 existed in a Fedora rawhide/development kernel (corbet, 2004).
Where the signature is located and what metadata are trusted
In v0 the signature is stored in an ELF section named "module_sig". This means the signature verification code must process multiple layers of metadata to locate the sections themselves including the section that contains section name strings. The following is part of the code that locates the signature during signature verification:
1 sig_index = 0;
2 for (i = 1; i < hdr->e_shnum; i++)
3 if (strcmp(secstrings+sechdrs[i].sh_name, "module_sig") == 0) {
4 sig_index = i;
5 break;
6 }This technique of storing and retrieving signatures is reminiscent of how Android apk packages are signed, which makes me curious if there is some "Android Master Key"-esque vulnerability lurking here (what if there are two sections named "module_sig"?) (Freeman, 2013).
What is signed
In order to verify a signature, the kernel module loader needs to recreate the hash that was signed. In v0 only the contents of sections whose names contain the string "text" or "data" (but not ".rel.") are hashed, as shown below.
1 for (i = 1; i < hdr->e_shnum; i++) {
2 name = secstrings+sechdrs[i].sh_name;
3
4 /* We only care about sections with "text" or
5 "data" in their names */
6 if ((strstr(name, "text") == NULL) &&
7 (strstr(name, "data") == NULL))
8 continue;
9 /* avoid the ".rel.*" sections too. */
10 if (strstr(name, ".rel.") != NULL)
11 continue;
12 /* add contents of section to signature */
13 ...
14 }This means that only contents of sections claiming to contain module code and data are signed, metadata are not checked. I find this worrisome given how powerful ELF metadata are and how much they can influence a program's execution (missing reference). In fact, this snippet of code is what prompted me to spend more time researching Linux kernel module signing.
The fact that only module code and data are signed is not the only worrisome thing about vo. There are multiple ways of specifying a section's purpose in ELF such as via a human-friendly string or a machine-friendly integer indicating the section type. This code signing mechanism relies on the human-friendly metadata instead of the metadata normally used by ELF parsers (i.e. the section header's flags, "sh_flags"). There is nothing that forces the human-friendly metadata to mach the machine-friendly metadata and there are examples of such discrepancies causing security problems such as those documented in Harrison and Li's 2014 Shmoocon talk entitled "Arms Race: The Story of (In)-Secure Bootloaders".
v1
In 2007 David Howells posted a set of module signing patches to the kernel mailing list, I will refer to these patches as v1 (Howells, 2007). v1 appears in Fedora Core 3-8 and RHEL 4-5, you can find the source code in kernel/module*.c (after you apply the module signing kernel patches). If you grab the FC3 kernel source code you will find the kernel module signing implementation in a patch called linux-2.6.7-modsign-core.patch. A rpm containing the source code/patches can be found here.
Where the signature is located and what metadata are trusted
v1 performs a large set of ELF metadata sanity checks before validating the signature. The following code sample (which is a trimmed version of the original) will give you an idea of what these sanity checks look like:
1 /*
2 * verify the ELF structure of a module
3 */
4 static int module_verify_elf(struct module_verify_data *mvdata)
5 {
6 // data declarations
7 ...
8
9 size = mvdata->size;
10 mvdata->nsects = hdr->e_shnum;
11
12 #define elfcheck(X) do {if (unlikely(!(X))){line = __LINE__; goto error;}} while(0)
13
14 /* validate the ELF header */
15 elfcheck(hdr->e_ehsize < size);
16 elfcheck(hdr->e_entry == 0);
17 elfcheck(hdr->e_phoff == 0);
18 elfcheck(hdr->e_phnum == 0);
19
20 elfcheck(hdr->e_shnum < SHN_LORESERVE);
21 elfcheck(hdr->e_shoff < size);
22 elfcheck(hdr->e_shoff >= hdr->e_ehsize);
23 elfcheck((hdr->e_shoff & (sizeof(long) - 1)) == 0);
24 elfcheck(hdr->e_shstrndx > 0);
25 elfcheck(hdr->e_shstrndx < hdr->e_shnum);
26 elfcheck(hdr->e_shentsize == sizeof(Elf_Shdr));
27
28 tmp = (size_t) hdr->e_shentsize * (size_t) hdr->e_shnum;
29 elfcheck(tmp < size - hdr->e_shoff);
30
31 ...
32
33 /* validate the ELF section headers */
34 mvdata->sections = mvdata->buffer + hdr->e_shoff;
35 secstop = mvdata->sections + mvdata->nsects;
36
37 sssize = mvdata->sections[hdr->e_shstrndx].sh_size;
38 elfcheck(sssize > 0);
39
40 section = mvdata->sections;
41 elfcheck(section->sh_type == SHT_NULL);
42 elfcheck(section->sh_size == 0);
43 elfcheck(section->sh_offset == 0);
44 secsize = mvdata->secsizes + 1;
45 for (section++; section < secstop; secsize++, section++) {
46 // check section header information and that certain sections exist
47 ...
48 /* perform section type specific checks */
49 switch (section->sh_type) {
50 case SHT_NOBITS:
51 break;
52 case SHT_REL:
53 elfcheck(section->sh_entsize == sizeof(Elf_Rel));
54 goto more_rel_checks;
55 case SHT_RELA:
56 elfcheck(section->sh_entsize == sizeof(Elf_Rela);
57 more_rel_checks:
58 elfcheck(section->sh_info > 0);
59 elfcheck(section->sh_info < hdr->e_shnum);
60 goto more_sec_checks;
61 case SHT_SYMTAB:
62 elfcheck(section->sh_entsize == sizeof(Elf_Sym));
63 goto more_sec_checks;
64 default:
65 more_sec_checks:
66 /* most types of section must be contained entirely
67 * within the file */
68 elfcheck(section->sh_size <= *secsize);
69 break;
70 }
71 }
72 /* validate the symbol table */
73 ...
74
75 /* validate each relocation table as best we can */
76 for (section = mvdata->sections + 1; section < secstop; section++) {
77 section2 = mvdata->sections + section->sh_info;
78 switch (section->sh_type) {
79 case SHT_REL:
80 rels = mvdata->buffer + section->sh_offset;
81 relstop = mvdata->buffer + section->sh_offset + section->sh_size;
82 for (rel = rels; rel < relstop; rel++) {
83 elfcheck(rel->r_offset < section2->sh_size);
84 elfcheck(ELF_R_SYM(rel->r_info) > 0);
85 elfcheck(ELF_R_SYM(rel->r_info) < mvdata->nsyms);
86 }
87 break;
88 case SHT_RELA:
89 relas = mvdata->buffer + section->sh_offset;
90 relastop = mvdata->buffer + section->sh_offset + section->sh_size;
91 for (rela = relas; rela < relastop; rela++) {
92 elfcheck(rela->r_offset < section2->sh_size);
93 elfcheck(ELF_R_SYM(rela->r_info) < mvdata->nsyms);
94 }
95 break;
96 default:
97 break;
98 }
99 }
100
101 _debug("ELF okay\n");
102 return 0;
103 error:
104 return -ELIBBAD;
105
106 } It is nice to see them place less trust on the contents of the ELF metadata, however it is hard to determine whether their sanity checks are aggressive enough. They still need to interpret some metadata to locate the signature. In v1 the signature itself is stored in a ".module_sig" section just like in v0 and is located using a similar technique that v0 uses to locate its signature.
What is signed
In v1, more than just the code and data section contents are hashed, their corresponding section headers are hashed as well. Relocation section headers and entries get hashed too, along with any symbols they reference. The ELF header itself is not hashed which is interesting because it is often used to locate the table of section headers. We can see this below:
1 /* load data from each relevant section into the digest */
2 for (i = 1; i < mvdata->nsects; i++) {
3 ...
4 if (i == mvdata->sig_index) // Do not add signature section to digest
5 continue;
6 /* it would be nice to include relocation sections, but the act of adding a
7 signature to the module seems changes their contents, because the symtab gets
8 changed when sections are added or removed */
9 if (sh_type == SHT_REL || sh_type == SHT_RELA) {
10 // add relocation section header information to hash
11 // for each relocation entry, add relocation information to hash
12 // if relocation entry uses a named symbol add symbol's name to hash
13
14 ...
15 continue;
16 }
17 // hash allocatable loadable sections
18 if (sh_type != SHT_NOBITS && sh_flags & SHF_ALLOC)
19 goto include_section;
20 continue;
21 include_section:
22 // add section header and section data to signature
23 ...
24 }Notice the comment on line 6 about not being able to include relocation sections in the signature. It is misleading because relocation entries are hashed. Although unlike other sections that are hashed as a single chunk of data, the loader iterates through each relocation entry in a relocation section, copies each entry's field into a separate (local) data structure (including any symbol information it references), and hashes the local data structure. The code that performs this is not shown here. My first guess was that this comment is a relic of a previous version of the module signing mechanism that I have not been able to locate. An alternative (and more likely) theory is that the comment is really about the symbol tables -- the act of adding the signature appears to alter the symbol tables. We can see this by inspecting the section header table of a kernel module built to be used with the v1 signature scheme. If you wish to play along at home, grab a copy of this kernel rpm and extract its contents.
$ readelf -S snd-mtpav.ko
There are 26 section headers, starting at offset 0x232c:
Section Headers:
[Nr] Name Type Addr Off Size ES Flg Lk Inf Al
[ 0] NULL 00000000 000000 000000 00 0 0 0
[ 1] .text PROGBITS 00000000 000034 0012f4 00 AX 0 0 4
[ 2] .rel.text REL 00000000 003308 0008c8 08 24 1 4
[ 3] .altinstr_replace PROGBITS 00000000 001328 000006 00 AX 0 0 1
[ 4] .init.text PROGBITS 00000000 00132e 00010d 00 AX 0 0 1
[ 5] .rel.init.text REL 00000000 003bd0 0000e8 08 24 4 4
[ 6] .exit.text PROGBITS 00000000 00143b 00001f 00 AX 0 0 1
[ 7] .rel.exit.text REL 00000000 003cb8 000020 08 24 6 4
[ 8] .modinfo PROGBITS 00000000 001460 0001ea 00 A 0 0 32
[ 9] __param PROGBITS 00000000 00164c 000064 00 A 0 0 4
[10] .rel__param REL 00000000 003cd8 0000a0 08 24 9 4
[11] .rodata.str1.1 PROGBITS 00000000 0016b0 0001cc 01 AMS 0 0 1
[12] .altinstructions PROGBITS 00000000 00187c 000017 00 A 0 0 4
[13] .rel.altinstructi REL 00000000 003d78 000020 08 24 12 4
[14] __versions PROGBITS 00000000 0018a0 000680 00 A 0 0 32
[15] .data PROGBITS 00000000 001f20 00004c 00 WA 0 0 4
[16] .rel.data REL 00000000 003d98 000030 08 24 15 4
[17] .gnu.linkonce.thi PROGBITS 00000000 001f80 000200 00 WA 0 0 128
[18] .rel.gnu.linkonce REL 00000000 003dc8 000010 08 24 17 4
[19] .bss NOBITS 00000000 002180 000008 00 WA 0 0 4
[20] .comment PROGBITS 00000000 002180 000062 00 0 0 1
[21] .module_sig PROGBITS 00000000 0021e2 000041 00 WA 0 0 1
[22] .gnu_debuglink PROGBITS 00000000 002224 000018 00 0 0 4
[23] .shstrtab STRTAB 00000000 00223c 0000ee 00 0 0 1
[24] .symtab SYMTAB 00000000 00273c 000660 10 25 74 4
[25] .strtab STRTAB 00000000 002d9c 00056b 00 0 0 1
Key to Flags:
W (write), A (alloc), X (execute), M (merge), S (strings)
I (info), L (link order), G (group), T (TLS), E (exclude), x (unknown)
O (extra OS processing required) o (OS specific), p (processor specific)The above output of readelf shows us that the kernel module includes both string and symbol tables (sections 23-25) but neither are marked loadable even though it is clear from the code (not shown) that they are loaded into memory before the sections are hashed (which makes me question the meaning of these flags). It appears that when the signature section is added to the ELF, the string table is augmented to include the section's name (".module_sig") and a symbol referencing the signature section is added to the symbol table thus modifying those tables and making them harder to sign. I also speculate that this is why neither the section headers of the string and symbol tables nor their contents are fully hashed -- only strings and symbols that are referenced by relocation entries are added to the hash.
v2
Two similar kernel module signing patches were submitted to a Linux developer mailing list in 2011 within a week of each other (Howells, 2011; Howells, 2011). I will only be focusing on the second, slightly-younger patch because I did not see the older patch included in any Red Hat/Fedora releases. The slightly younger patch, which I will refer to as v2, is used in RHEL 6. The relevant sources are kernel/module*.c. An rpm containing the source code can be found here
Where the signature is located and what metadata are trusted
In v2 they wrapped the signature in a notes section (of type SHT_NOTE), which is located by the code signing mechanism using its human-friendly name ("module.sig"). To extract the signature, not only must it locate the correct section but it also should parse the note-section specific metadata that describes the signature. The note section metadata is defined as follows (in elf.h):
/* Note header in a PT_NOTE section */
typedef struct elf32_note {
Elf32_Word n_namesz; /* Name size */
Elf32_Word n_descsz; /* Content size */
Elf32_Word n_type; /* Content type */
} Elf32_Nhdr;Notice that size field (n_descsz)? I wonder what happens when it disagrees with the length field in the note's section header. Perhaps nothing interesting, but I have not taken any time to examine this.
The following code snippet illustrates how the signature note section is located:
1 int module_verify_signature(struct module_verify_data *mvdata, int *_gpgsig_ok)
2 {
3 ...
4 _debug("looking for sig section '%s'\n", modsign_note_section);
5
6 for (loop = 1; loop < mvdata->nsects; loop++) {
7 switch (sechdrs[loop].sh_type) {
8 case SHT_NOTE:
9 if (strcmp(mvdata->secstrings + sechdrs[loop].sh_name,
10 modsign_note_section) == 0)
11 mvdata->sig_index = loop;
12 break;
13 }
14 }
15 ...
16 }We can see that it resembles how the signature is located in v0 and v1 except that it looks for a section of type SHT_NOTE named "module.sig".
What is signed
Slightly more metadata gets signed in v2 than in v1. For example, v1 does not sign section headers for sections that are not both allocatable and non-empty, this is not the case in v2. The following shows that empty and allocatable sections now have their section headers hashed.
1 /* include the headers of BSS sections */
2 if (sh_type == SHT_NOBITS && sh_flags & SHF_ALLOC) {
3 crypto_digest_update_data(mvdata, sh_name, strlen(sh_name));
4 crypto_digest_update_val(mvdata, sechdrs[sect].sh_type);
5 crypto_digest_update_val(mvdata, sechdrs[sect].sh_flags);
6 crypto_digest_update_val(mvdata, sechdrs[sect].sh_size);
7 crypto_digest_update_val(mvdata, sechdrs[sect].sh_addralign);
8 goto digested;
9 }Linux 3.7 and beyond
Not long before the 2012 Kernel Summit, David Howells published a kernel module signing implementation that appended the signature to the end of the module file so that it could be located without parsing ELF metadata and also allowing for the entire module to be signed (Howells, 2012). This patch does not appear to be used in any of the major RHEL or Fedora releases so I will not discuss its implementation here. However not long after this patch was released we can find an email where David Howells discusses module signing design challenges. It turns out that Red Hat previously avoided signing whole modules because doing so would break their existing packaging and installation infrastructure (Howells, 2012).
At the 2012 Kernel Summit, developers announced that they would incorporate module signing into the mainstream kernel, an implementation that signs the entire module (Edge, 2012). Linux 3.7 was the first mainstream release that included kernel module signing support, which can be found in kernel/module_signing.c. This implementation was also incorporated into Fedora Core 18-20 releases (and perhaps beyond, I haven't checked the newer releases). You can find the source code here.
In this code snippet from the mainstream Linux implementation we can see that the signature is located at the end of the module and that everything but the signature itself is included in the signed hash.
1 /* Verify the signature on a module. */
2 int mod_verify_sig(const void *mod, unsigned long * modlen) {
3 // data declarations and sanity checks
4 ...
5 // copy bytes at end of file into signature structure
6 memcpy(&ms, mod + (modlen sizeof(ms)), sizeof(ms));
7 // do work to calculate length of module (modlen)
8 ...
9 sig = mod + modlen;
10 // add all module contents (but signature) to signature
11 pks = mod_make_digest(ms.hash, mod, modlen);
12 if (IS ERR(pks)) { ret = PTR_ERR(pks); goto error; }
13 ...
14 // Extract actual signature (in form of MPI array) from signature data
15 ret = mod_extract_mpi_array(pks, sig + ms.signer_len + ms.key_id_len, sig_len);
16 if (ret < 0) goto error;
17
18 ret = verify_signature(key, pks);
19 error:
20 return ret;
21 }Concluding remarks
An ELF file does not just contain data and code, it also contains instructions on how the code and data should be loaded into memory, patched, and executed. Many implementations of Linux kernel module signing schemes signed only subsets of the ELF metadata and section contents. Those same implementations also needed to consult the module's ELF metadata in order to locate the signature itself. It takes a deep understanding of the kernel module loading process to understand how the unsigned metadata can affect how the module appears in memory so we must be careful about what metadata we trust outright. Problems may also arise when there are multiple parsers handling and interpreting the same data, each may have its own interpretation (i.e. a parser differential) causing vulnerabilities. The decision to hash the entire ELF and append the signature to the end of the file removes unnecessary complexity from the signing process and makes the signing process easier to understand and analyze, however this does not guarantee that the scheme is unbreakable. There are many other ways to break or weaken a signing scheme and the format it uses. Nevertheless, if we do not design our signature schemes to be trivial to parse and verify then we are likely setting ourselves up for failure.
Acknowledgments
I'd like to thank Sergey Bratus for the feedback and edits he provided for this blog post.
References
- Kroah-Hartman, G. (2004, January 1). Signed kernel modules. Linux Journal. http://www.linuxjournal.com/article/7130.
- corbet. (2004, July 7). Cryptographic signatures on kernel modules. https://lwn.net/Articles/92617.
- Freeman, J. (2013). Exploit (& Fix) Android "Master Key". saurik. http://www.saurik.com/id/17.
- Howells, D. (2007, February 14). MODSIGN: Apply signature checking to modules on module load. https://lkml.org/lkml/2007/2/14/164.
- Howells, D. (2011, November 29). [RFC][PATCH 00/16] Crypto keys and module signing [ver #2]. https://lkml.org/lkml/2011/11/29/475.
- Howells, D. (2011, December 2). MODSIGN: Apply signature checking to modules on module load [ver #3]. https://lkml.org/lkml/2011/12/2/251.
- Howells, D. (2012, May 22). Crypto keys and module signing. https://lkml.org/lkml/2012/5/22/471.
- Howells, D. (2012, August 16). [21/25] MODSIGN: Module signature verification. https://lkml.org/lkml/2012/8/15/738.
- Edge, J. (2012, September 6). KS2012: Module signing. https://lwn.net/Articles/515007.