These are the slides from my vBSDcon talk on GELI work.
About a month ago, I started a discussion on freebsd-hackers and freebsd-security about a system for signed executables, with a focus on signed kernels and kernel modules. This is part of a larger agenda of mine to equip FreeBSD with OS-level tamper resistance features.
While the initial use of this is for signing the kernel and its modules, and checking signatures during the loader process as well as at runtime when kernel modules are loaded. However, it is desirable to build a system that is capable of growing in likely directions, such as executable and library signing.
This article details the current state of the design of this system.
I originally outlined a number of goals for this system:
- Be able to check for a correct cryptographic signature for any kernel or modules loaded at boot time for some platforms (EFI at a minimum)
- Be able to check for a correct cryptographic signature for any kernel module loaded during normal operations (whether or not to do this could be controlled by a sysctl, securelevel, or some similar mechanism)
- Work with what’s in the base system already and minimize new additions (ideally, just a small utility to sign executables)
- Minimize administrative overhead and ideally, require no changes at all to maintain signed kernel/modules
- Have a clear path for supporting signed executables/libraries.
- The design must support the case where a system builds locally and uses its own key(s) for signing kernels and modules (and anything else) and must allow the administrator complete control over which key(s) are valid for a given system (ie. no “master keys” controlled by central organizations)
- The design must allow for the adoption of new ciphers (there is an inevitable shift to post-quantum ciphers coming in the near future)
I also specified a number of non-goals:
- Hardware/firmware-based attacks are considered out-of-scope (there is no viable method for defending against them at the OS level)
- Boot platforms that don’t provide their own signature-checking framework up to loader/kernel can’t be properly secured, and are considered out-of-scope
- Boot platforms that impose size restrictions prohibiting incorporation of RSA and ED25519 crypto code (ex. i386 BIOS) are considered out-of-scope
- GRUB support is desirable, however it is not necessary to support GRUB out-of-the-box (meaning a design requiring reasonable modifications to GRUB is acceptable
There are several considerations that should weigh in on the design.
FreeBSD Base System
Unlike linux, FreeBSD has a base operating system which contains a number of tools and libraries which provide a set of operating system utilities. Most notably, the base system contains the OpenSSL (or in some cases, LibreSSL) crypto suite. This includes an encryption library as well as tools capable of creating and managing key-pairs and other cryptographic data in a variety of formats.
Additionally, the FreeBSD base system contains libelf, which is a library that provides mechanisms for manipulating ELF binaries. Additionally, the base system provides the binutils suite, including objcopy, which are command-line tools capable of manipulating ELF binaries.
Note that only some of these components (namely the signelf tool) exist at the present; the rest of the components exist only as man pages that describe them at present.
The FreeBSD kernel does not currently incorporate code for public-key cryptography, and direct incorporation of OpenSSL into the kernel has proven infeasible. Additionally, parsing code needs to be incorporated into the kernel for any formats that are used. Options here include incorporation of code from the NaCl library, which provides a very lightweight implementation of both RSA 4096 and Ed25519, as well as creating a minimal library out of code harvested from OpenSSL or LibreSSL.
A note on elliptic curve cryptography: the state of support for safe elliptic curves is sad. In my drafts of the man pages, I have mandated that the only acceptable curves are those that satisfy the security properties described by the SafeCurves project. At this time, these include M-221, E-222, Curve1174, Curve25519, E-382, M-383, Curve383187, Curve41417, Goldilocks-448, M-511, and E-521. Unfortunately, none of these is supported by OpenSSL at this time, though Curve25519 support is supposedly coming soon. However, I would prefer to write specs that mandate the right curves (and thus put pressure on crypto libraries) than cave to using bad ones.
Modifications to GRUB
GRUB provides the best option for FreeBSD coreboot support at this time. It also provides an existing mechanism for signing binaries. However, this mechanism is deficient in two ways. First, it relies on external signatures, which would complicate administration and require modification of virtually all installer programs, as well as run the risk of stale signatures. Second, it relies on the gnupg toolset, which is not part of the FreeBSD base system. Thus, it is inevitable that GRUB will need to be patched to support the signed executables proposed by this design. However, we should make efforts to keep the necessary changes as minimal as possible.
Signing and Trust System Design
The signing and trust system consists of a number of components, some of which are standards, some of which are interfaces, and some of which are tools. The core feature, of course, is the signed ELF convention. The signelf tool provides a one-stop tool for signing large numbers of executables. The trust system provides a system-level mechanism for registering and maintaining verification keys that are used to check signatures on kernel modules. Finally, the portable verification library provides a self-contained code package that can be dropped into the kernel, the loader, or a third-party codebase like GRUB.
Note that this design is not yet implemented, so it may be subject to change. Also, it has not yet undergone review on the FreeBSD lists, so it should be considered more of a proposal.
Signed ELF Binaries
The ELF format is very flexible, and provides a generic mechanism for storing metadata. The signed ELF convention utilizes this to store signatures in a special section within the binary itself. A signed ELF binary contains a section named .sign, which contains a detached PKCS#7 signature in DER encoding for the file. This signature is computed (and checked) on the entire file, with the .sign section itself being replaced by zero data of equal size and position.
Signing an ELF binary is somewhat involved, as it requires determining the size of a signature, creating a new section (along with its name), recomputing the ELF layout, computing the signature, and writing it into the section. Checking a signature is considerably simpler: it involves merely copying the signature, overwriting the .sign section with zeros, and then checking the signature against the entire file.
The PKCS#7 format was chosen because it is an established standard which supports detached signatures as well as many other kinds of data. The signatures generated for signed ELF files are minimal and do not contain certificates, attributes, or other data (a signature for RSA-4096 is under 800 bytes); however, the format is extensible enough to embed other data, allowing for future extensions.
The signelf Tool
Signed ELF binaries can be created and checked by adroit usage of the objcopy and openssl command-line tools. This is quite tedious, however. Moreover, there are certain use cases that are desirable, like signing a batch of executables using an ephemeral key, discarding the key, and generating a certificate for verification. The signelf tool is designed to be a simplified mechanism for signing batches of executables which provides this additional functionality. It is a fairly straightforward use of libelf and OpenSSL, and should be able to handle the binaries produced by normal compilation. Additionally, the signelf tool can verify signed ELF files. The signelf code is currently complete, and works on a kernel as well as modules.
The Trust System
In order to check signatures on kernel modules (and anything else), it is necessary to establish and maintain a set of trusted verification keys in the kernel (as well as in the boot loader). In order for this system to be truly secure, at least one trust root key must be built into the kernel and/or the boot loader, which can then be used to verify other keys. The trust system refers to the combination of kernel interfaces, standard file locations, and conventions that manage this.
System Trust Keys and Signing Keys
The (public) verification keys used to check signatures as well as the (private) signing keys used to generate signatures are kept in the /etc/trust/ directory. Verification keys are stored in /etc/trust/certs, in the X509 certificate format, and private keys are stored in /etc/trust/keys in the private key format. Both are stored in the PEM encoding (as is standard with many OpenSSL applications).
There is no requirement as to the number, identity, or composition of verification or signing keys. Specifically, there is not and will never be any kind of mandate for any kind of verification key not controlled by the owner of the machine. The trust system is designed to be flexible enough to accommodate a wide variety of uses, from machines that only trust executables built locally, to ones that trust executables built on an in-house machine only, to those that trust executables built by a third party (such as the FreeBSD foundation), or any combination thereof.
The preferred convention, however, is to maintain a single, per-machine keypair which is then used to sign any additional verification keys. This keypair should be generated locally for each machine, and never exported from the machine.
Trust Keys Library
Keys under /etc/trust/certs will be converted into C code constants and subsequently compiled into a static library providing the raw binary data for the keys during the buildworld process. This provides the mechanism for building keys into the kernel, loader, and other components. These keys are known as trust root keys, as they provide the root set for all trusted keys.
Kernel Trust Interface
The kernel trust interface provides access to the set of verification keys trusted by the kernel. This consists of an in-kernel interface as well as a user-facing device interface. The in-kernel interface looks like an ordinary key management system (KMS) interface. The device interface provides two primary mechanisms: access to the current set of trusted keys and the ability to register new keys or revoke existing ones.
Access to the existing database is accomplished through a read-only device node which simply outputs all of the existing trusted keys in PEM-encoded X509 format. This formatting allows many OpenSSL applications to use the device node itself as a CA root file. Updating the key database is accomplished by writing to a second device node. Writing an X509 certificate signed by one of the existing trusted keys to this device node will cause the key contained in the certificate to be added to the trusted key set. Writing a certificate revocation list (CRL) signed by a trusted key to the device node will revoke the keys in the revocation list as well as any keys whose signature chains depend on them. Trust root keys cannot be revoked, however.
This maintains the trusted key set in a state where any trusted key has a signature chain back to a trust root key.
Portable Verification Library
The final piece of the system is the portable verification library. This library should resemble a minimal OpenSSL-like API that performs parsing/encoding of the necessary formats (PKCS#7, X509, CRL), or a reduced subset thereof and public-key signature verification. I have not yet decided whether to create this from harvesting code from OpenSSL/LibreSSL or write it from scratch (with code from NaCl), but I’m leaning toward harvesting code from LibreSSL.
The trust system performs two significant roles in the system as planned, and can be expanded to do more things in the future. First, it ensures that loader only loads kernels and modules that are signed. Second, it can serve as a kind of system-wide keyring (hence the device node that looks like a typical PEM-encoded CAroot file for OpenSSL applications). The following is an overview of how it would operate in practice.
Signature Checking in the loader
In an EFI environment, boot1.efi and loader.efi have a chain of custody provided by the EFI secure boot framework. This is maintained from boot1.efi to loader.efi, because of the use of the EFI loaded image interface. The continuation of the chain of custody must be enforced directly by loader.efi. To accomplish this, loader will link against the trust key library at build time to establish root keys. These in turn can either be used to check the kernel and modules directly, or they can be used to check a per-kernel key (the second method is recommended; see below).
Per-Kernel Ephemeral Keys
The signelf utility was designed with the typical kernel build process in mind. The kernel and all of its modules reside in a single directory; it’s a simple enough thing to run signelf on all of them as the final build step. Additionally, signelf can generate an ephemeral key for signing and write out the verification certificate after it finishes.
This gives rise to a use pattern where every kernel is signed with an ephemeral key, and a verification certificate is written into the kernel directory. This certificate is in turn signed by the local trust root key (signelf does this as part of the ephemeral key procedure). In this case, the loader first attempts to load the verification certificate for a kernel, then it loads the kernel and all modules.
Signed Configuration Files
The FreeBSD loader relies on several files such as loader.4th, loader.conf, loader.menu, and others that control its behavior in significant ways. Additionally, one can foresee applications of this system that rely on non-ELF configuration files. For loader, the simplest solution is to store these files as non-detached PKCS#7 messages (meaning, the message and file contents are stored together). Thus, loader would look for loader.conf.pk7, loader.4th.pk7, and so on. A loader built for secure boot would look specifically for the .pk7 files, and would require signature verification in order to load them.
The keybuf Interface
The kernel keybuf interface was added in a patch I contributed in late March 2017. It is used by GELI boot support to pass keys from the boot phases to the kernel. However, it was designed to support up to 64 distinct 4096-bit keys without modification; thus it can be used with RSA-4096. An alternative to linking the trust key library directly into the kernel is to have it receive the trusted root key as a keybuf entry.
This approach has advantages and disadvantages. The advantage is it allows a generic kernel to be deployed to a large number of machines without rebuilding for each machine. Specifically, this would allow the FreeBSD foundation to publish a kernel which can make use of local trust root keys. The primary disadvantage is that the trust root keys are not part of the kernel and thus not guaranteed by the signature checking. The likely solution will be to support both possibilities as build options.
The preferred scheme for trust root keys is to have a local keypair generated on each machine, with the local verification certificate serving as the sole trust root key. Any vendor keys that might be used would be signed by this keypair and loaded as intermediate keys. Every kernel build would produce an ephemeral key which would be signed by the local keypair. Kernel builds originating from an organization would also be signed by an ephemeral key, whose certificate is signed by the organization’s keypair. For example, the FreeBSD foundation might maintain a signing key, which it uses to sign the ephemeral keys of all kernel builds it publishes. An internal IT organization might do the same.
It would be up to the owner of a machine whether or not to trust the vendor keys originating from a given organization. If the keys are trusted, then they are signed by the local keypair. However, it is always an option to forego all vendor keys and only trust locally-built kernels.
An alternate use might be to have no local signing key, and only use an organizational trust root key. This pattern is suitable for large IT organizations that produce lots of identical machines off of a standard image.
This design for the trust system and kernel/module signing is a comprehensive system-wide public-key trust management system for FreeBSD. Its initial purpose is managing a set of keys that are used to verify kernels and kernel modules. However, the system is designed to address the issues associated with trusted key management in a comprehensive and thorough way, and to leave the door open to many possible uses in the future.
I’ve posted about my work on EFI GELI support. This project is actually the first step in a larger series of changes that I’ve been sketching out since April. The goal of the larger effort is to implement tamper-resilience features at the OS level for FreeBSD. The full-disk encryption capabilities provided by GELI boot support represent the first step in this process.
Before I talk about the work I’m planning to do, it’s worth discussing the goals and the rationale for them. One of the keys to effective security is an accurate and effective threat model; another is identifying the scope of the security controls to be put in place. This kind of thinking is important for this project in particular, where it’s easy to conflate threats stemming from vulnerable or malicious hardware with vulnerabilities at the OS level.
Regarding terminology: “tamper-resistance” means the ability of a device to resist a threat agent who seeks to gain access to the device while it is inactive (in a suspended or powered-off state) in order to exfiltrate data or install malware of some kind. I specifically use the term “tamper-resilience” to refer to tamper-resistance features confined to the OS layer to acknowledge the fact that these features fundamentally cannot defeat threats based on hardware or firmware.
In our threat model, we have the following assets:
- The operating system kernel, modules, and boot programs.
- Specifically, a boot/resume program to be loaded by hardware, which must be stored as plaintext.
- The userland operating system programs and configuration data.
- The user’s data.
We assume a single threat agent with the following capabilities:
- Access and write to any permanent storage medium (such as a disk) while the device is suspended or powered off.
- Make copies of any volatile memory (such as RAM) while the device is suspended.
- Defeat any sort of physical security or detection mechanisms to do so.
Specifically, the following capabilities are considered out-of-scope (they are to be handled by other mechanisms):
- Accessing the device while powered on and in use.
- Attacks based on hardware or firmware tampering.
- Attacks based on things like bug devices, reading EM radiation (van Eyck phreaking), and the like.
- Attacks based on causing users to install malware while using the device.
Thus, the threat model is based on an attacker gaining access to the device while powered-off or suspended and tampering with it at the OS level and up.
It is important to note that hardware/firmware tampering is a real and legitimate threat, and one deserving of effort. However, it is a separate and parallel concern that requires its own effort. Moreover, if the OS level has weaknesses, no amount of hardware or firmware hardening can compensate for it.
The tamper resilience plan is based around the notion of protecting as much data as possible through authenticated encryption, using cryptographic verification to ensure that any part of the boot/resume process whose program must be stored as plaintext is not tampered with, and ensuring that no other data is accessible as plaintext while suspended or powered off.
The work on this breaks down into roughly three phases, one of which I’ve already finished.
Data Protection and Integrity
All data aside from the boot program to be loaded by the hardware (known in FreeBSD as boot1) can be effectively protected at rest by a combination of ZFS with SHA256 verification and the GELI disk encryption scheme. Full-disk encryption protects data from theft, and combining it with ZFS’ integrity checks based on a cryptographically-secure hash function prevents an attacker from tampering with the contents (this can actually be done even on encrypted data without an authentication scheme in play).
There is always at least one program that must remain unprotected by full-disk encryption: the boot entry-point program. Fortunately, the EFI platform provides a mechanism for ensuring the integrity of the boot program. EFI secure boot uses public-key crypto to allow the boot program to be signed by a private key and verified by a public key that is provided to the firmware. If the verification fails, then the firmware informs the user that their boot program has been tampered with and aborts the boot.
In an open-source OS like FreeBSD, this presents an effective protection scheme along with full-disk encryption. On most desktops and laptops, we build the kernel and boot loaders on the machine itself. We can simply store a machine-specific signing key on the encrypted partition and use it to sign the boot loader for that machine. The only way an attacker could forge the signature would be to gain access to the signing key, which is stored on an encrypted partition. Thus, the attacker would have to already have access to the encrypted volume in order to forge a signature and tamper with the boot program.
To achieve the baseline level of protection, we need to ensure that the plaintext boot program is signed, and that it verifies the signature of a boot stage that is stored on an encrypted volume. Because of the way the EFI boot process works, it is enough to sign the EFI boot1 and loader programs. The loader program is typically stored on the boot device itself (which would be encrypted), and loaded by the EFI LOAD_IMAGE_PROTOCOL interface, which performs signature verification. Thus, it should be possible to achieve baseline protection without having to modify boot1 and loader beyond what I’ve already done.
There is, of course, a case for doing signature verification on the kernel and modules. One can even imagine signature verification on userland programs. However, this is out-of-scope for the discussion here.
Suspend/resume represents the most significant tamper weakness at the present. Suspend/resume in FreeBSD is currently only implemented for the suspend-to-memory sleep state. This means that an attacker who gains access to the device while suspended effectively has access to the device at runtime. More specifically, they have all of the following:
- Access to the entire RAM memory state
- Sufficient data to decrypt all mounted filesystems
- Sufficient data to decrypt any encrypted swap partitions
- Possibly the signing key for signing kernels
There really isn’t a way to protect a system that’s suspended to memory. Even if you were to implement what amounts to suspend-to-disk by unmounting all filesystems and booting the kernel and all programs out to an encrypted disk storage, you still resume by starting execution at a specified memory address. The attacker can just implant malware in that process if they have the ability to tamper with RAM.
Thus, the only secure way to do suspend/resume is to tackle suspend-to-disk support for FreeBSD. Of course, it also has to be done securely. The scheme I have in mind for doing so looks something like this:
- Allow users to specify a secure suspend partition and set a resume password. This can be done with a standard GELI partition.
- Use the dump functionality to write out the entire kernel state to the suspend partition (because we intend to resume, we can’t do the usual trick of dumping to the swap space, as we need the data that’s stored there)
- Alternatively, since the dump is being done voluntarily, it might be possible to write out to a filesystem (normally, dumps are done in response to a kernel panic, so the filesystem drivers are assumed to be corrupted).
- Have the suspend-to-disk functionality sign the dumped state with a resume key (this can be the signing key for boot1, or it can be another key that’s generated during the build process)
- Make boot1 aware of whatever it needs to know for detecting when resuming from disk and have it request a password, load the encrypted dumped state, and resume.
There are, of course, a lot of issues to be resolved in doing this sort of thing, and I imagine it will take quite some time to implement fully.
Once these three things are implemented, we’d have a baseline of tamper-resilience in FreeBSD. Of course, there are ways we could go further. For one, signed kernels and modules are a good idea. There has also been talk of a signed executable and libraries framework.
My GELI EFI work is complete and waiting for testing before going through the integration process. There are already some EFI signing utilities in existence. I’m currently testing too many things to feel comfortable about trying out EFI signing (and I want to have a second laptop around before I do that kind of thing!); however, I plan on getting the baseline signed boot1 and loader scheme working, then trying to alter the build process to support automatically generating signed boot1 and loader programs.
The kernel crypto framework currently lacks public-key crypto support, and it needs some work anyway. I’ve started working on a design for a new crypto library which I intend to replace the boot_crypto code in my GELI work and eventually the code in the kernel. I’ve also heard of others working on integrating LibreSSL. I view this as a precursor to the more advanced work like secure suspend/resume and kernel/module signing.
However, we’re currently in the middle of the 11 release process and there are several major outstanding projects (my GELI work, the i915 graphics work). In general, I’m reluctant to move forward until those things calm down a bit.
There has been a lot of work on better cryptography libraries in the wake of a number of OpenSSL bugs. One of the major steps forward in this realm is NaCl, or the Networking and Cryptography Library. NaCl aims to address the fact that most older crypto libraries are quite difficult to use, and misuse is often the source of vulnerabilities.
In my recent work on FreeBSD, I ran into the kernel crypto code. It is worth mentioning that older crypto, particularly kernel crypto frameworks tend to hearken back to days when things were different than they are now. For one, strong crypto was classified as a munition, and exporting it from various countries ran afoul of international arms trafficking laws. Second, CPUs were much slower back then, crypto represented a more significant overhead, and most hardware crypto devices were attached to the PCI bus. In the modern world, we have Bernstein v. United States (publication of crypto is protected free speech), CPUs are much faster, and hardware crypto typically takes the form of special CPU instructions, not devices that have to be accessed through kernel interfaces.
This state of affairs tends to lead to fairly fragmented crypto codebases, which is exactly what the FreeBSD kernel crypto codebase looks like. Moreover, it completely lacks any public-key algorithms, which are necessary for kernel and driver signing. Lastly, existing userland crypto libraries tend not to fair so well when being converted into kernel libraries, as they tend to rely on userland utilities to operate.
To address this, I recently started working on ideas for a lightweight, embeddable crypto library I’m calling LiCl. The name of course is the chemical symbol for lithium chloride: a salt similar to sodium chloride (NaCl). An interpretation of the name could be “lightweight interoperable crypto library”, though it occurred to me that “Lego-inspired crypto library” also works, as the design involves building cryptosystems out of “blocks”.
LiCl aims to produce a lightweight crypto library that is easy to use and also easy to drop into any application (userland, kernel, or embedded). It has several design goals, which I’ll discuss here.
Control over Crypto through Policies
Aspects of the library should be governed by policies which can be set both at library build time as well as in any application that uses the library. Policies should be as fine-grained as “don’t use these specific algorithms”, all the way up to things like “don’t use hardware random number generators”, or “only use safecurves-approved ECC”. If done right, this also captures the configuration options necessary to say things like “don’t use anything that depends on POSIX userland”.
This is done in the implementation through a variety of C preprocessor definitions that control which implementations are present in the library, and which can be used by an application.
NaCl-Style Easy Interfaces
NaCl is designed to eliminate many bugs that can arise from improper use of crypto by providing the simplest possible interface through its “box” functions. In NaCl, this works, as it aims to provide a crypto interface for network applications.
LiCl, on the other hand, aims to provide a more general toolbox. Thus, it needs a way to build up a NaCl-style box out of components. As we’ll see, I have a plan for this.
Curate Crypto, Don’t Implement It
Most of LiCl will be the code devoted to assembling the external crypto interfaces. The actual crypto implementations themselves will be curated from various BSD-compatible licensed or public-domain source. Now, of course, I may run into some algorithms that require direct implementation; however, I intend to actually write crypto code myself as a last resort.
My plans for LiCl actually draw on programming language concepts to some degree, where objects describing components of a crypto scheme represent an AST-like structure that is used to generate a NaCl-style interface. I’ll go into the various components I’ve worked out, and how they all fit together.
It should be remembered that this is a design in progress; I’m still considering alternatives.
The User-Facing Crypto Interfaces
Right now, there are six user-facing interfaces, all of which take the form of structs with function pointers, each of which take a user data pointer (in other words, the standard method for doing object-oriented programming in C). The exact length of the user data depends on the components from which the interface was built. The six interfaces are as follows:
- Symmetric-key encryption (stream cipher or block cipher with a mode)
- Symmetric-key authenticated encryption
- Symmetric-key authentication (hashing with a salt)
- Public-key encryption
- Public-key authenticated encryption (encryption with signature checking)
- Public-key authentication (signature verification)
These interfaces represent the combination of multiple crypto methods to create a complete package that should handle all the details in a secure fashion. The result is that we can support encryption/decryption and signing/verification in a NaCl box-like interface.
Creating User-Facing Interfaces
A user creates one of the above interfaces by assembling components, each of which represents some cryptographic primitive or method (for example, a hash function, or a block cipher mode). The key is ensuring that users assemble these components in a way that is valid and secure. This will be guaranteed by a “build cryptosystem” function that performs a consistency check on the specification it’s given. For example, it shouldn’t allow you to encrypt an authenticated message (encrypt-then-MAC). Another reason for this is for supporting hardware crypto, which may impose various limits on how the primitives those implementations provide can be used.
I come from a programming language background, so I like to think about this in those terms. The “build cryptosystem” function acts similarly to a compiler, and the rules are similar to a type system. The key here is figuring out exactly what the “types” are. This is an ongoing task, but it starts with figuring out what the basic component model looks like. I have a good start on that, and have identified several kinds of components.
Ultimately, we’ll build up a cryptosystem out of components. A components is essentially a “block” of crypto functionality, which itself may be built out of other components. For example, a keystore may require a random source. I’ve sketched a list of components so far, and will discuss each one here:
Random sources are essential in any cryptosystem. In LiCl, I want to support an HSM-style interface for key generation and storage, so it’s necessary to provide a random source for generating keys. There are also concerns such as padding that require random bits. Random sources are the only thing in the GitHub repo at the moment, and the only one is the POSIX urandom source. The first curation task is to identify a high-quality software random number generator implementation that’s BSD/MIT licensed or public domain.
LiCl’s interfaces are built around an assumption that there’s a layer of indirection between keys and their representation in memory. This is done to enable use of HSMs and other hardware crypto. A keystore interface represents such an indirection.
Keystores have a notion of an external representation for keys. In the “direct” keystore implementation, this is the same as the actual representation; in an HSM-based keystore, it might be an ID number. Keystores provide the ability to generate keys internally, add keys to the store, delete keys, and extract a key given its external representation.
The only implementation so far is the “direct” keystore, which is just a passthrough interface. It requires a random source for its keygen functionality.
One major building block is the ability to perform a given operation on arbitrary-sized data. This is innate in some primitives, such as stream ciphers and hash functions. In others, it involves things like modes of operation and padding.
This is where the type-like aspects begin to become visible. For example, the GCM block cipher mode takes a fixed-size symmetric-key encryption operation and produces an arbitrary-sized symmetric-key authenticated encryption operation. We could write this down in a semi-formal notation as “symmetric enc fixed size (n) -> symmetric auth enc variable block size(n)”. Padding operations would eliminate the restriction on input size, and could be written as “algo variable block size (n), randsrc -> algo output variable output block size (n)”.
Of course, we wouldn’t write down this notation anywhere in the actual implementation (except maybe in the documentation). In the code, it would all be represented as data structures.
Ultimately, we’d need to assemble components to get an arbitrary-sized operation with no input block size restriction. We’d also need to match the algorithm type of the scheme we’re trying to build (so if we want authenticated symmetric key encryption, we need to ensure that’s what we build).
MAC Schemes and Signing
MAC schemes and signing algorithms both take a hash function and an encryption scheme and produce an authenticated encryption scheme. Signing algorithms also require a public-key crypto scheme. In the semi-formal notation, a MAC scheme might look something like this: “symmetric enc variable, hash -> symmetric auth enc variable”
Ciphers and Hashes
Ciphers are of course the basic building blocks of all this. Ciphers may have different characteristics. Block ciphers might be written as “symmetric enc fixed size(n)”. An authenticated stream cipher would be written as “symmetric auth enc variable”.
Putting it All Together
Ultimately, the “build cryptosystem” functions will take a tree-like structure as an argument that describes how to combine all the various components to build a cryptosystem. They then perform a consistency check on the whole tree to ensure that everything is put together correctly and then fill up a cryptosystem structure with all the implementation functions and data necessary to make it work.
With the design I’ve described, it should be possible to build a crypto library that will serve the needs of kernel and systems developer, but will also make it easier to use crypto in a manner that is correct.
The biggest remaining question is whether this design can effectively deal with the legacy interfaces that kernel developers must deal with. However, it seems at least plausible that the model of assembling components should be able to handle this. Afterall, even legacy systems are ultimately just assembling crypto primitives in a particular way; if a particular system can’t be modeled by the components LiCl provides, it should be possible to implement new components within the model I’ve described.
The repository for the project is here, however, there isn’t much there at this point.
I have completed my work to add support for the GELI disk encryption system to the FreeBSD EFI boot loader. This work started off intending to be a “simple” patch, but it became a much larger undertaking that ended up refactoring a significant portion of the EFI boot loader.
Regardless, the changeset is now usable and ready for testing. It can be accessed on my GitHub. I will be merging this periodically with the FreeBSD master in order to keep it up to date.
I am not recommending this for inclusion in the 11 release; it’s too big a change to incorporate this late in the game.
This work breaks down into roughly four different components: EFI refactoring, boot crypto framework, GELI support, and kernel key injection. I’ll cover each of these in turn.
I have already written extensively about my EFI refactoring here. The reason for undertaking this effort, however, was driven by GELI support. Early in my work on this, I had implemented a non-EFI “providers” framework in boot1 in order to support the notion of disk partitions that may contain sub-partitions. This was deeply unsatisfying to me for several reasons:
- It implemented a lot of the same functionality that exists in the EFI framework.
- It involved implementing a GPT partition driver to deal with partition tables inside GELI partitions (GPT detection and support is guaranteed by the EFI spec).
- The interface between the EFI framework and the custom “providers” framework was awkward.
- The driver was completely boot1-specific, and exporting it to something like GRUB probably involved a total rewrite.
- Implementing it within loader was going to involve a lot of code duplication.
- There was no obvious was to pass keys between boot1, loader, and the kernel.
Doing the EFIzation work eliminated these problems, and in my opinion, cleaned things up in boot1 as well. The results were pleasing:
- The GELI driver can be extracted from the FreeBSD codebase without too much trouble.
- While I was unable to go all the way to the EFI driver model, the only blocker is the bcache code, and once that is resolved, we can have hotplug support in the boot loader!
- The boot1 and loader codebases are now sharing all the backend drivers, and boot1 has been reduced to one very small source file.
As I previously mentioned, my only reservation about this is increased dependence on (historically flaky) vendor-specific BIOS code. However, with things like CoreBoot on the rise, I’m less concerned about this.
There are a couple of open questions and future work items coming out of this refactoring:
- Might it be a good idea to move the backend drivers out of boot and loader completely, and have them be wholly-separate EFI drivers that get installed by boot/loader?
- Provide EFI drivers for GELI and FreeBSD filesystems to projects like CoreBoot, TianoCore, and GRUB.
- Refactor the bcache code to support dynamic device detection and complete the transition to the EFI driver model.
- Play with possibilities that arise from hot-plugging, like pluggable USB dongles containing access credentials.
The boot crypto refactoring was a small effort to pull the crypto code out of the BIOS GELI code and put it in a common place for all boot utilities. My hope is that boot_crypto becomes the go-to place for boot-time crypto code.
However, I’m a bit displeased with the state of crypto code in general. I deemed it too ambitious to take that on in addition to everything else, but it seems that the crypto framework could profit from some work. The problems I see are as follows:
- The codebase seems rather disorganized. There are crypto and opencrypto in the kernel, and there doesn’t seem to be a common interface for all ciphers.
- There are insecure ciphers and algorithms (RC4, SHA1, MD5, DES) as well as missing modern ciphers (ChaCha20-Poly1305, stronger RipeMD variants, etc).
- The procedure for linking against the crypto codebase is harder than it could be.
The core crypto code should be usable in userland, kernel, and boot environments, with the only difference being the ABI for which it is compiled (native for user and kernel, MSABI for EFI, 32-bit for x86 BIOS, etc). It should be possible to have a single codebase that gets turned into static libraries for each ABI and a shared library for userland.
It might be worth an experiment to replace the current crypto code with something like NaCL (libsodium) and use the scheme I describe above.
The GELI EFI driver is a straightforward EFI bus driver that detects the presence of a GELI volume on a device handle and creates a new device handle bearing an EFI_BLOCK_IO_PROTOCOL interface that provides access to the encrypted data. This involves getting ahold of a password or a key, which I manage through the KMS driver (actually, the GELI driver currently contains the code to ask for a password directly, though this could and probably should be moved into the KMS driver).
: EFI considers any driver that creates new handles to be a “bus driver”, even if it is something like a partition driver.
Kernel Key Injection and Boot KMS
Passing keys between boot1, loader, and the kernel was one of the key challenges of this work. I also wanted to do this in a way that could be extended to support hardware security modules with a minimum of effort. The EFI_KMS_PROTOCOL interface provided a means to accomplish this.
I provided another EFI driver that implements a software-based EFI_KMS_PROTOCOL interface. This allows boot services to register keys, look them up later, and ultimately have them injected into the kernel. This code is a fairly simple key table manager internally, and uses the file metadata functionality in loader to communicate keys to the kernel.
The current implementation leaves the task of asking for passwords up to the individual drivers, but I am seriously considering bringing that into the KMS driver as well, under the auspices of the CreateKey function.
On the kernel side, I added an interface to the crypto framework that provides access to the key buffer provided to the kernel by the KMS driver. This allows keys to be passed from boot to kernel in a safer manner than the environment variable currently used by the BIOS GELI implementation. It also provides a generic interface going forward for accomplishing this task.
This also puts things in such a state that a hardware-based key management system could be integrated. Because boot1 and loader use EFI_KMS_PROTOCOL, which was specifically designed for key management systems, it is easy to add support for a device that supports this. On the kernel side, we would simply expect the hardware KMS to be initialized with the keys we need.
Using and Testing EFI GELI Support
The changeset should be usable for most people. I have tested the core functionality and have successfully loaded and booted kernels from ZFS volumes inside a GELI partition. I am not actively using this, however, as I want to participate in the tests of the drm2 4.6 update, and I don’t want to assume the risks involved in merging two experimental branches.
If you want to use or test the changeset, I strongly recommend the following procedure:
- Be aware of the risks: this is full-disk encryption, so a problem may result in your files becoming inaccessible by any means.
- Read and understand the basics of EFI and the FreeBSD boot architecture.
- Install an EFI Shell program on your EFI System Partition, know how to run it from your BIOS menu.
- Install boot1 to an alternate location (like /efi/boot/bootx64.tst).
- Install loader to /boot/loader.tst on your main partition (I have left the LOADER_PATH variable set to /boot/loader.tst to facilitate this kind of testing)
- Start the EFI shell and run /efi/boot/bootx64.tst
- Try creating an empty GELI partition, and verify that boot1 and loader detect it
- Try creating a filesystem in the GELI partition, copy your /boot/ directory from your main partition, see if boot1 and loader can read files from it
- Try loading and booting a kernel from your GELI partition
- Once you have succeeded at these, back up all your files, try converting your main disk into a GELI partition, and see if you can boot from it.
: The EFIzed loader (with GELI support) should work fine even when loaded by the old boot1 (or by a tool such as GRUB)
Looking Forward: Tamper-Resilience
This changeset adds the first of three major capabilities that are needed to realize a longer-term tamper-resilience that I would very much like to see be a part of FreeBSD. The steps toward this are as follows:
- Support full-disk encryption from boot, with the ESP being the only non-encrypted partition on the system
- Support EFI secure boot of boot1, combined with signature checking for loader, the kernel, and device drivers, with the ability to designate a machine-specific signing key to be used to generate the signatures
- Support secure suspend-to-disk
These three features when combined and implemented on a ZFS-based system create a powerful tamper-resilience scheme. Because secure boot is used with a machine-specific platform key, this key can be stored on the encrypted disk. This ensures that only someone with the ability to decrypt the disk is able to create a boot1 program that will run on the machine. This prevents anyone from tampering with boot1 and hijacking the boot process. Moreover, with suspend-to-disk, the machine is only vulnerable to data exfiltration when it is in active use. When suspended or powered-off, everything is encrypted and protected by the secure boot scheme.
Obviously, this is not perfect; anyone able to overwrite the firmware or mess with the hardware can hijack the secure boot process and tamper with boot1. This is why I call it tamper-resilience as opposed to tamper-proofing. However, this scheme guarantees that the OS does not open any vulnerabilities to an attacker who wants to tamper with the system.
: With projects like CoreBoot, it may become possible to have the firmware itself load programs from an encrypted volume
Almost all disk encryption systems today follow a similar design pattern. Symmetric-key block ciphers are used, with the initialization vector being derived entirely from the block index to which the data is stored. Often times, the disk is broken up into sections, each of which has its own key. However, the point of this is that the key and IV are static across any number of writes.
This preserves the atomicity of writes and allows the design to work at the block layer as opposed to the filesystem layer. However, it also restricts the modes of operation to those that are strong against reuse of IVs. Typically, this means CBC mode. This block-level design also makes it quite difficult to integrate a MAC. Modes like AES-XTS go some distance to mitigating this, and the problem can be mitigated completely by using a filesystem with inherent corruption-resistance like ZFS.
The problem is that this scheme completely prohibits the use of stream ciphers such as ChaCha20 or modes of operation such as CTR or OFB that produce stream cipher-like behavior. This would be a footnote but for recent results that demonstrate a quantum period-finding attack capable of breaking basically all modes other than CTR or OFB. This suggests that to implement quantum-safe encrypted storage, we need to come up with a scheme capable of using stream ciphers.
The Problem of Disk Encryption
The fundamental problem with using stream ciphers for block-layer disk encryption stems from the fact that the initialization vector (and ideally the key) must be changed every time the block is written, and this key must be available at an arbitrarily later time in order to read.
In general, there are basically three ways to manage keys in the context of disk encryption:
- Derive the key and IV from the block index
- Store the keys in a separate location on disk, look this up when needed
- Alter the interface for block IO to take a key as a parameter
Most current disk encryption schemes use option 1; however, this ends up reusing IVs, which prohibits the use of stream ciphers (and modes like CTR and OFB). Option 2 guarantees that we have a unique IV (and key, if we want it) every time we write to a given block; we simply change keys and record this in our key storage. The price we pay for this is atomicity: every incoming block write requires a write to two separate disk blocks. This effectively undermines even atomic filesystems like ZFS. The only example of this sort of scheme of which I am aware is FreeBSD’s older GBDE system.
Option 3 eschews the problem to someone else. Of course, this means they have to solve the problem somehow. The only way this ends up not being wholly equivalent to options 1 or 2 is if the consumer of the block-layer interface (the filesystem) somehow organizes itself in a way that a key and IV are always readily available whenever a read or write is about to take place. This of course, requires addressing full-disk encryption in the filesystem itself. It also places certain demands on the design of the filesystem.
Atomic Snapshot Filesystems
Atomic filesystems are designed in such a way that all I/O operations appear to be atomic. With regard to writes, this means that the sort of filesystem corruption that necessitates tools like fsck cannot happen. Either an operation takes place, or it does not.
Of course, a given write operation may actually perform many block writes; however, the filesystem’s on-disk data structures are carefully designed in such a way that one single write causes all of the operations that lead up to it to “take effect” at once. Typically, this involves building up a number of “shadow” objects representing the new state, then switching over to them in a single write.
Note that in this approach, we effectively get snapshots for free. We have a data structure consisting of a mutable spine that points to a complex but immutable set of data structures. We never overwrite anything until the single operation that updates the mutable spine, causing the operation to take effect.
Atomic Key/IV Updates
The atomic snapshot filesystem design provides a way to effectively change the keys and IVs for every node of a filesystem data structure every time it is written. Because we are creating a shadow data structure, then installing it with a single write, it is quite simple to generate new keys or IVs every time we create a node in this shadow structure. Conversely, because the filesystem is atomic, and every node contains the keys and IVs for any node to which it points, anyone traversing the filesystem always has the information they need to decrypt any object they can reach.
This scheme has advantages over conventional disk or filesystem encryption. Unlike conventional disk encryption, each filesystem object has its own key and IV, and these are uniquely generated every time a write takes place. Nothing about the key and IV can be inferred by any attacker looking at an arbitrary disk block. Unlike conventional filesystem encryption which typically only encrypts file contents, everything is encrypted.
Possible ZFS Extension
The ZFS filesystem is a highly advanced filesystem and volume management scheme that provides fully atomic operations and snapshots. I am admittedly not familiar enough with its workings to know for absolute certain whether the scheme I describe above could be added to it, but I am fairly confident that it could. I am also aware that ZFS provides an encryption system already, but I am also fairly confident that it is not equivalent to the scheme I describe above.
ZFS would also need to be extended to support a broader range of ciphers and modes of operation to take advantage of this scheme. Support for CTR and OFB modes are absolutely essential, of course. I would also recommend support for ciphers beyond AES. Camellia and ChaCha20 would make good additions, among others.
Quantum-safe disk encryption is arguably not as critical to develop as quantum-safe encryption for network communications. With network communications, it is reasonable to assume that all traffic is being recorded and will be subject to quantum attacks once those become available. The same it not true of disk storage. However, the technology does need to be developed, and the recent results about the period-finding attack on symmetric cipher modes demonstrate a workable attack against nearly all disk encryption schemes.
I would urge all filesystem projects to consider the scheme I’ve laid out and integrate concerns for quantum-safe encryption into their design.
As a final note, should anyone from Illumos run across this blog, I’d be more than willing to discuss more details of this scheme with them.