Developing a cryptographically secure bootloader for RISC-V in Rust

SentinelBoot is a demonstrative, cryptographically secure RISC-V bootloader written in Rust. This project forms a final-year project at The University of Manchester sponsored by Codethink.

Motivation

Memory safety is a persistent issue in software, especially system software, such as bootloaders. Implementing some kinds of run-time safety checks can be very computationally expensive, as such, programming languages which employ them to promote memory safety are incompatible with system software due to performance degradation¹. That said, exploiting vulnerabilities that arise from a lack of memory safety leads to a myriad of issues, including data leaks, denial-of-service, and arbitrary code execution². Until recently, there has been no viable memory-safe alternative to C/C++/Assembly for such applications. However, the Rust programming language, which performs static analysis at compile time, has been presented as a viable alternative and has begun being explored for such applications, with projects such as Rust for Linux.

SentinelBoot is a cryptographically secure bootloader aimed at enhancing boot flow safety of RISC-V through memory-safe principles, predominantly leveraging the Rust programming language with its ownership, borrowing, and lifetime constraints. Additionally, SentinelBoot employs public-key cryptography to verify the integrity of a booted kernel (digital signature), by the use of the RISC-V Vector Cryptography extension, establishing secure boot functionality. SentinelBoot achieves these objectives with a 20.1% hashing overhead (approximately 0.27s additional runtime) when compared to an example U-Boot binary (mainline at time of development), and produces a resulting binary one-tenth the size of an example U-Boot binary with half the memory footprint.

Background

There are three main principles employed by Rust that aid in reducing the likelihood of memory safety vulnerabilities. Note, however, the keyword ‘reduce’: a developer can overrule these checks, and even then, vulnerabilities can still exist in allegedly 100% safe, non-overruled Rust code, they’re just less likely³. The three principles are:

1. Ownership: aims to ensure that a piece of memory has a single 'owner'. This is primarily to allow automatic deallocation when the owner goes out of scope, helping to prevent vulnerabilities such as memory leaks.

2. Borrowing: allows a variable that does not own a certain piece of memory to access the memory location, by 'borrowing' from the owner, helping to prevent vulnerabilities such as data races due to the two types of borrowing that exist:

   • Non-mutable (shared) borrows, where the borrower can read the data in the memory location but not write to it, any number of non-mutable borrows can exist simultaneously.

   • Mutable (exclusive) borrows, where the borrower can read and write to the memory location. If a mutable borrow exists, no other borrows (mutable or non-mutable) may exist.

3. Lifetimes: defines the 'duration' of a memory location (i.e. a variable has a lifetime from when it is declared to when it is last used) or of a borrow of that location (i.e. all borrows have a lifetime associated with them). This allows Rust to avoid using a garbage collector, as the memory location can be automatically deallocated when its lifetime expires, and it also allows the static analysis to determine if a program could be at risk of accessing a freed memory location, helping to prevent use-after-free errors.

The Linux kernel's bootflow can be viewed as a sequential series of steps that load and execute the following stage, as seen below.

Threat Model

SentinelBoot's threat model focuses on thin client devices which do not store their own OS and over-the-air updates (e.g. how phones are updated): both of these cases involve executable code being sent over a network, usually the internet. We ignore the risk of direct hardware modification, as an attacker can just swap out the bootloader (making any potential defence implemented by SentinelBoot in vain). Instead, SentinelBoot focuses on defending against a subclass of social engineering and Evil Maid attack vectors, where the goal is to modify the root-of-trust. As well as defending against Man-In-The-Middle attacks which undermine secure communication, shown below. Finally, SentinelBoot aims to prevent exploitation by minimising memory safety vulnerabilities.

Assembly to Rust

Firstly, it is necessary to write a linker script to format the resulting binary into an ELF format. Next, it is necessary to write RISC-V assembly to initialise hardware, including handling multiple hardware threads (HARTs), setting control and status registers, disabling interrupts, etc. The control flow is shown below.

As a final-year university project, a decision was taken to limit the projects' scope by allowing U-Boot to perform TFTP operations on SentinelBoot's behalf. To support this decision, additional assembly was needed to handle executing from supervisor mode.

'Unsafe' to 'Safe' Rust

The assembly code has now jumped to the Rust entry point, which is nominally memory-safe. The next two steps in the initialisation - initialising a serial driver and a memory allocator - both require a lot of unsafe work, which can be done in Rust with an unsafe overrule (this tells the compiler that certain operations it would otherwise be unprepared to permit are acceptable and that the programmer has verified that at the end of the overrule block memory-safety rules are now being observed). After that, there is a symbolic change from this "unsafe" Rust to "truly safe" Rust.

The serial driver implements UART, a simple protocol for asynchronous communication that groups data in frames according to an agreed configuration. The actual transmission is handled by a memory-mapped chip, so we need to set the configuration and wrap the raw register interactions with an API in order to enforce checks around unsafe operations. The control flow of the API is shown below.

To allow dynamic memory allocation we need a memory allocator: doing so allows for more advanced data structures, such as vectors. By implementing the GlobalAlloc trait and therefore facilitating more advanced data structures, SentinelBoot provides wider support for Rust crates. SentinelBoot implements a simple memory allocator based upon a doubly linked list of memory allocation structures. The doubly linked list data structure is useful as it allows bidirectional traversal of the data structure, allowing efficient amalgamation of allocations, as shown below.

Additionally, implementing the doubly linked list comes with its own problems: it violates Rust's borrowing rules as each allocation structure has mutable pointers to the next and previous structures, and therefore each structure is mutably borrowed twice. That said, it is possible to still safely implement the doubly linked list by wrapping the mutable borrows in a mutex and performing accesses through them, shown below; however, the project deadline meant this feature was not implemented, as SentinelBoot only runs on a single HART, so a race is not possible.

Verifying & Booting

Utilising a hashing function that provides properties such as collision resistance, preimage resistance, and second pre-image resistance, it is possible to be extremely confident of the integrity of a binary object. An example of a hashing algorithm that provides such properties is SHA256, and therefore it was suitable for SentinelBoot. To hash the kernel we need to accurately determine the size of the kernel binary from just a pointer, as including a single extra memory location will completely change the result (due to the avalanche effect). Therefore, functionality to parse the kernel’s ELF header and sum the section sizes was required, shown below.

Hashing only goes so far: if we are sent a binary and an accompanying hash, we can verify they match - ensuring integrity - however, we need to ensure authenticity too. Currently, an attacker can simply intercept the kernel, inject malicious code, rehash, and then forward the malicious kernel and valid hash for that malicious kernel to SentinelBoot.

Therefore, to enhance the security model, we can utilise public key cryptography (PKC). PKC utilises a pair of keys, one widely known and one secret, which are mathematically linked. Additionally, a trusted 3rd party can verify the public key by using certificates. The operation of an example PKC system is shown below.

This would allow us to fully encrypt the kernel binary, ensuring it cannot be altered without the secret key. However, PKC works on fixed block sizes, only 245 bytes for RSA, and performs expensive mathematical operations with very large numbers - as such it is far too slow.

However, by modifying PKC slightly, we only need to encrypt a small chunk of data: when the server hashes the kernel it can encrypt the hash with its private key (this is a "digital signature"). When SentinelBoot receives the hash, SentinelBoot will decrypt it with the server's public key (which can be verified by a certificate from a trusted 3rd party) to compare hashes, thereby authenticating the server (as an attacker would not be able to sign the kernel correctly without access to the server's private key). Further, as the hash could not have been re-encrypted, we also verify the integrity. This operation is shown below.

Finally, once the kernel has been verified, we can set up for the kernel jump by setting a0 to contain the HARTID and a1 to contain the address of the DTB. After debugging using Ghidra to decompile the kernel, and then comparing the decompiled instructions against the control flow shown in GDB, it was possible to achieve full booting, as shown below.

Accelerating SHA256

It is possible, due to support in QEMU, to emulate the RISC-V Vector Cryptography extension to 'accelerate' the SHA256 hashing of the kernel. The QEMU implementation is not optimised for speed, however, the extension is fully supported and therefore demonstrates functionality for future hardware support. The extension utilises SIMD principles to improve throughput.

As the extension was only ratified in September 2023, tooling is still in its infancy, so the vector cryptography assembly instructions had to be pre-assembled to be included.

With the assembly instructions pre-assembled, the raw binary word could be included into Rust. Finally, the full SHA256 algorithm had to be implemented in vector cryptography assembly where the control flow operated on 512 bit chunks with 16 quad rounds. The SHA256 algorithm control flow is shown below.

Continuous Integration

Throughout the development process, GitHub actions were employed to verify all of SentinelBoot's targets were buildable, the code met clippy standards, and that SentinelBoot executed as expected both under emulation and on a VisionFive 2 connected to a Raspberry Pi which acted as a rig controller.

Analysis

SentinelBoot achieves the secure boot mechanism with only a 20.1% performance overhead, compared to an example U-Boot binary.

Secondly, ~80% of lines were marked safe for the serial hashing implementation and ~68% of lines marked safe for vector cryptography implementation (due to SHA256 needing to be implemented in assembly).

Thirdly, SentinelBoot's resulting binary is approximately one-tenth the size of an example U-Boot binary at about 70kB.

Finally, SentinelBoot compiles in approximately one-quarter the time of an example U-Boot binary, compiled with -j8, whereas Rust's toolchain does not fully utilise parallelism yet.

Conclusion

By developing SentinelBoot, the utilisation of the Rust programming language (and memory-safe principles) to improve the memory safety of RISC-V bootflow has been shown, all while additionally implementing a cryptographic secure boot mechanism. SentinelBoot is able to execute both on hardware and under emulation, where the SHA256 implementation in QEMU is accelerated via the RISC-V Vector Cryptography extension. SentinelBoot achieves this functionality with ~80% of serial and ~68% vector cryptography safe line proportions. Even with the additional functionality and safety provided by SentinelBoot, when compared to an example U-Boot binary, SentinelBoot is one-tenth the size with only a 20.1% performance overhead.

Concluding Remarks

This blog post summarises the SentinelBoot Thesis and the corresponding SentinelBoot GitHub. Additionally, if you'd like to discuss RISC-V or Codethink's work in Rust, contact sales@codethink.co.uk.