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 gave a talk at IEEE SecDev on Nov 3 about my vision for how to combine industrial programming language pragmatics with formal methods. The slides can be found here.
This was a 5-minute talk, but I will be expanding it into a 30-minute talk with more content.
Yesterday saw a major distributed denial-of-service (DDoS) attack against the DNS infrastructure that crippled the internet for much of the east coast. This attack disabled internet access for much of the Northeastern US, as well as other areas. These sorts of attacks are nothing new; in fact, this attack came on the anniversary of a similar attack fourteen years ago. Yesterday’s attack is nonetheless significant, both in its scope and also in the role of the growing internet of things (IoT) in the attack.
The attack was facilitated by the Mirai malware suite, which specifically targets insecure IoT devices, applying a brute-force password attack to gain access to the machines and deploy its malware. Such an attack would almost certainly fail if directed against machines with appropriate security measures in place and on which passwords had been correctly set. IoT devices, however, often lack such protections, are often left with their default login credentials, and often go unpatched (afterall, who among even the most eager adopters of IoT can say that they routinely log in to every lightbulb in their house to change the passwords and download patches). Yesterday, we saw the negative consequences of the proliferation of these kinds of devices
Public Health and Pollution Analogies
Industry regulation- whether self-imposed or imposed by the state -is an widely-accepted practice among modern societies. The case for this practice lies in the reality that some actions are not limited in their effect to oneself and one’s customers, but rather that they have a tangible effect on the entire world. Bad practices in these areas leads to systemic risks that threaten even those who have nothing to do with the underlying culprits. In such a situation, industry faces a choice of two options, one of which will eventually come to pass: self-regulate, or have regulations imposed from without.
Two classic examples of such a situation come in the form of public health concerns and environmental pollution. Both of these have direct analogs to the situation we now face with insecure IoT devices and software (in)security in the broader context.
IoT and Pollution
After the third attack yesterday, I posted a series of remarks on Twitter that gave rise to this article, beginning with “IoT is the carbon emissions of infosec. Today’s incident is the climate change analog. It won’t be the last”. I went on to criticize the current trend of gratuitously deploying huge numbers of “smart” devices without concern for the information security implications.
The ultimate point I sought to advance is that releasing huge numbers of insecure, connected devices into the world is effectively a form of pollution, and it has serious negative impacts on information security for the entire internet. We saw one such result yesterday in the form of one of the largest DDoS attacks and the loss of internet usability for significant portions of the US. As serious as this attack was, however, it could be far worse. Such a botnet could easily be used in far more serious attacks, possibly to the point of causing real damage. And of course, we’ve already seen cases of “smart” device equipped with cameras being used to surreptitiously capture videos of unsuspecting people which are then used for blackmail purposes.
These negative effects, like pollution, affect the world as a whole, not just the subset of those who decide they need smart lightbulbs and smart brooms. They create a swarm of devices ripe for the plucking for malware, which in turn compromises basic infrastructure and harms everyone. It is not hard to see the analogies between this and a dirty coal-burning furnace contaminating the air, leading to maladies like acid rain and brown-lung.
Platforms, Methodologies, and Public Health
Of course, few consumers really care what sort of language or development methodology is used, so long as they get their product, or at least the current conventional wisdom goes. When we consider the widespread information security implications, however, the picture begins to look altogether different. Put another way, Zuckerburg’s addage “move fast and break things” becomes irresponsible and unacceptable when the potential exists to break the entire internet.
Since the early 1900’s, the US has had laws governing healthcare-related products as well as food, drugs and others. The reasons for this are twofold: first, to protect consumers who lack insight into the manufacturing process, and second, to protect the public from health crises such as epidemics that arise from contaminated products. In the case of the Pure Food and Drug act, the call for this regulation was driven in a large part by the extremely poor quality standards of large-scale industrial food processing as documented in Upton Sinclair’s work The Jungle.
The root cause of the conditions that led to the regulation of food industries and the conditions that have led to the popularization of insecure platforms and unsound development methodologies is, I believe, the same. The cause is the competition-induced drive to lower costs and production times combined with a pathological lack of accountability for the quality of products and the negative effects of quality defects. When combined, these factors consistently lead nowhere good.
Better Development Practices and Sustainability
These trends are simply not sustainable. They serve to exacerbate an already severe information security crisis and on a long enough timeline, they stand to cause significant economic damage as a result of attacks like yesterdays, if not more severe attacks that pose a real material risk.
I do not believe government-imposed regulations are a solution to this problem. In fact, in the current political climate, I suspect such a regulatory effort would end up imposing regulations such as back-doors and other measures that would do more damage to the state of information security that they would help.
The answer, I believe, must come from industry itself and must be led by infosec professionals. The key is realizing that as is the case with sustainable manufacturing, better development practices are actually more viable and lead to lower eventual costs. Sloppy practices and bad platforms may cut costs and development times in the now, but in the long run they end up costing much more. This sort of paradigm shift is neither implausible nor unprecedented. Driving it is a matter of educating industrial colleagues about these issues and the benefits of more sound platforms and development processes.
Yesterday’s attack brought the potential for the proliferation of insecure devices and software to have a profound negative effect on the entire world to the forefront. A key root cause of this is an outdated paradigm in software development that ignores these factors in favor of the short-term view. It falls to the infosec community to bring about the necessary change toward a more accurate view and more sound and sustainable practices.
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.