So ... that's a bit of a nondescript title huh? About a month ago I was reading the "autopen’s design from a Nix perspective" document. It's quite a nice read! You should go read it if digital signatures and Nix interest you in any capacity. It's a very practical, down to earth description of the properties of Nix, Nix derivations, digital signatures, autopen and how we best provide digital signatures of Nix build outputs, while doing the actual signing in Nix derivations (unlike existing solutions) but also still avoiding putting the private key in the Nix store (since that would defeat the whole point). If you know anything about Nix your gut is probably telling you that this isn't possible without violating the core promises of Nix. Mine certainly was! But as it turns out this is actually possible!1 As I said the document above does a great job of giving a pretty hands on description of what properties we care about and how these "signing derivations" aim to uphold them despite this seemingly inherently impure access to an out-of-store private signing key. It seems to me like it pretty deliberately puts some of the theory to the side a little to instead describe things in practical terms based on the properties of Nix derivations that purity give us that we actually care about. This is honestly probably the right call. However if you know me, you know I love me some theory! So of course I immediately began thinking about what this new kind of derivation looks like from a theoretical perspective. This rambling is the result of that. An attempt to give a more theoretically based2 description of why the thing that autopen does is okay actually and doesn't resolve in making everything impure and bad and evil. It's also somewhat my own way of saying thank you to the people working on this, by getting really nerdy about their work cause it's really cool!!
What does "pure" even mean?
If you've heard of Nix at all you've almost certainly heard it described as "a purely functional package manager". But what does that actually mean?
The core idea of Nix is to treat building and packaging software as evaluating "pure functions". The idea of a "pure function" has it's roots in mathematics. A "pure" function is a function whose output depends solely on its input, that is the inputs fully specify the output of the function. Give a pure function the same input twice and it will both times give you the same output. Nix represents building software as pure functions. That is in the Nix model build GNU bash means getting the bash source code, all it's dependencies and some build instructions and using those to build bash. This might sound trivial, that is just how you build software after all. But the magic lies in how we treat a built bash as the output of a function which has the source, dependencies and build instructions as inputs. The dependencies themselves are also specified as pure functions from their source, dependencies and build instructions to the built dependency. So on and so forth all the way down to the bootstrap seeds. This means that the final output, built software is fully specified by the inputs. This model gives us a lot of power! That power is what makes Nix so desirable. However I'm not going to spend time discussing all of that. The document I linked above gives a great overview and there exists tons of existing blog posts, documentation, heck even the original Nix PhD on the matter. Why purely functional build descriptions are desirable has been well documented. Go read all that it's very interesting!
What I care about here in my theory mind palace is how on earth we can make pure derivations out of inherently impure access to a private signing key. That doesn't make any sense at first glance! The key isn't (and for security reasons can't be) part of the inputs to the build, so how on earth can the build be pure? Well ... in the strictest sense it isn't! But the magic is that it doesn't have to be actually pure to behave just as if it was.
FODs: The OG impure derivations
To understand how that can be true I think it's easiest to start by describing the very similar case of fixed output derivations. One thing I glossed over a bit above is how we get the source code for a piece of software. We need it to build the software but how do we purely pull it down from the internet? The internet is inherent impure since it's the big scary unpredictable outside. We can't just willy nilly give derivations access to the internet, that would open up for impurity.
The old-school way of dealing with this in Nix is to download the source manually first and then provide it as part of the build description. This makes it pure. Great! solved! ... but it also means we have to download the whole source manually, separately, before a build, before we can even know the build graph! Wouldn't it be great if we could just tell Nix where it could fetch the source from the internet and let it do that itself at build time and pull in the source as a dependency? Now the question becomes ... how do we do that while keeping our software build pure? The answer is fixed output derivations or FODs!
The core idea of a FOD is that, while the actual "contents" or "implementation" of a FOD is impure, it gets a network location to fetch stuff from and has access to the internet so it can do that, if we fully specify with a hash what the output of the FOD must be, that is we fix the output, then we can treat it as if it was pure!
From a more theoretical point of view: If I have a function wibble that is impure and I call a pure function wobble with the output of calling wibble, ie. wobble(wibble()) that makes the whole expression impure. The impurity of wibble spread to make the whole thing impure even though wobble is pure. But if I define an expression that says to call wibble and only accept the output if it hashes to something specific then we have still fully specified that wibble must return that specific thing, this is not that useful for something small but it is very useful for bigger things like source code. The thing we're saying here is that wobble(wibble() if is <hash>) behaves the same as wobble(pibble()) if pibble() is a hypothetical pure version of wibble that outputs the same thing, if wibble doesn't do as we said it should, then we reject it wholesale. In a sense we have contained the impurity such that we can have it when we need it, but it won't spread out and loose us all of those nice properties that we are doing all this pure function stuff to have. When we specify the hash as part of the impure functions inputs and enforce that the output complies to the hash, then the inputs still fully specify the output, just as if the function was pure. The autopen "signing derivations" work on the same core principle: contain the impurity by fully specifying the impure derivations output.
Signing derivations
The idea of a signing derivation is also to fix the output of the derivation. But we don't do it with a hash. The whole point is that we don't actually know the output signature, that's why we're running this whole signing derivation at all! So how do we fully specify something we don't actually know? We exploit the properties of digital signatures!
A digital signature is a concept from asymmetric cryptography. The idea is that we have a big number called a private key, we keep this secret, from the private key we can derive it's one and only3 public key, this is safe to share. A signature is some piece of data that can be derived from a "message" and the private key and that is constructed such that the public key can be used to mathematically prove that it's corresponding private key was used to make the signature for that exact message. It might not be immediately obvious but this actually means that we can use the public key (which is safe to include in the derivation) to fully specify the output of the derivation even before we know it!
A signing derivation is defined in terms of what is to be signed as well as the public key that corresponds to the private key we want to sign with. We can only build this derivation if we have that private key (same as how we can only build a FOD if the specified network location is still online and has the source code that we wanted), but we can use the signing key to guarantee once we have the output, that the corresponding private key was used to build it! That is message + public key is enough to fully specify the private key too, since the output signature is only valid if the right private key was used to build. The public key essentially plays the same role as the hash does for a FOD. Sure the build might be impure, but we don't have to care because the output is only ever valid for one specific set of output bytes! It's kind of magical when you think about it. Without ever giving up the private key we have made a derivation that is fully specified by it's inputs even if it has impure access to more data that isn't provided in it's inputs!
I am very very excited to see where the autopen work, the overall official NixOS secure boot work which it is a part of, and all the other things people can think to use autopen for, end up! Go tell emilazy (Emily) and ElvishJerricco (Will Fancher) how cool this work is and go help them if you can. Ummm meow! Have a great rest of your day!!