Reproducible but individually signed?

Posted Mar 7, 2025 23:13 UTC (Fri) by SLi (subscriber, #53131)
Parent article: Hash-based module integrity checking

This sounds to me like one of those problems that, if defined the way I'd guess from the article, is not just technically impossible but definitionally impossible.

A signature is a piece of data that satisfies these properties:

1. Given your private key, you can produce it efficiently.
2. It can be verified efficiently without access to your private key.
3. It cannot be produced efficiently without your private key.

In other words, non-reproducibility without private data is a very essential part of what a signature is.

We might be able to get reproducibility in the sense that the outputs are identical given the same secret key, but that doesn't really sound very useful.

I like both reproducibility and signatures a lot. I think both are necessary. But they seem clearly mutually exclusive, unless you manage to move the signature out of the part for which you require reproducibility, or are happy with "reproducibility if you can access the key".

This does feel like a problem where I'd say the only way to have this in general would be for the reproducibility projects to define sufficiently general means to ship signatures outside the measured blob.

Reproducible but individually signed?

Posted Mar 8, 2025 1:29 UTC (Sat) by JoeBuck (subscriber, #2330) [Link]

Seems that if there were an efficient way to segregate everything that is expected to be reproducible and bit-for-bit identical, from the small amount of data (signatures, perhaps build info) that is expected not to be, in such a way to guarantee that all of the code falls into the first bucket, we could satisfy both requirements. So, instead of just running the equivalent of 'cmp' on everything, there'd be a smarter compare tool.

I recall that the GCC bootstrap procedure, where it checks that the stage 2 and stage 3 compilers are bit-for-bit identical, had a way to exclude time stamps on OSes that add time stamps to object files and only compare the rest. So, something like that.

Reproducible but individually signed?

Posted Mar 10, 2025 8:33 UTC (Mon) by Niflmir (subscriber, #175249) [Link] (1 responses)

I don't think you need to be able to reproduce a signature to verify that a build is reproducible. The verification of the signature itself proves that if I had the private key I could reproduce the signature which proves that the entire build with the signature is reproducible if the signed content has been proven reproducible.

I don't ever actually need to reproduce the entire build to gain the benefits of reproducible builds, I just need to prove that I could. That is the asymmetry of PKI: zero knowledge proofs as opposed to constructive proofs.

Reproducible but individually signed?

Posted Mar 10, 2025 10:11 UTC (Mon) by SLi (subscriber, #53131) [Link]

I'm not entirely sure if I understood correctly what you are saying, but I'll respond to what I think you are. Is this a fair rephrasing of your comment?

> If you have independently verified that a build is reproducible, then having an external signature does not in practice harm the reproducibility; and if you trust the signer to have signed the authentic output, verifying that signature against your build guarantees that you have the same result.

If so:

I think that depends on whether we want to have signatures _within_ the artifact being reproduced (such as the kernel) or external to it. If the signatures need to be inside what we measure *and* what we want to be reproducible, I don't think that's feasible. I think your comment aligns with what I suggested about moving the signature outside the reproducibility scope.

That is, if we have a package that doesn't itself contain PKI that you are supposed to be in control of inside the scope of reproducibility, then, yes, we could verify an external signature against the build artifact. But that's not the use case here. Here we want to have a kernel package that inherently contains a public key and verifies signatures on modules that are loaded. It needs this to implement the functionality of verifying that the modules it loads are legitimate (blessed by you).

Sure, we could make a "reproducible" kernel build where we just embed a key that someone else generated and have all kernel modules contain a signature by this third party, as long as we never modify them. This would allow us to load exactly these blessed versions. It would also enable us to rebuild that precise kernel and load exactly those modules, but we couldn't modify a module's source code and load it because the signature check would fail. On the other hand, this third party would be able to sign a malicious module and load it the computer. I find this less than ideal.

And my point is that unless we have a method to have the signatures and the public key outside the scope of reproducibility, that is fundamentally, *definitionally* incompatible with the user having control over the signatures (it's by definition not a useful cryptographic signature if anyone can reproduce it).

OTOH what I think could be done, in principle, is to move the signing part out of the kernel building part, but that would require some infrastructure. We could have a "kernel with holes for signatures" that is reproducible and that could be turned into a non-reproducible "kernel with signatures". If something like this were to happen, I'd hope the mechanism would be generic enough that it's not a one-off for the kernel use case, since the problem is clearly more generic than that.

But I also don't think it's possible to just wave hands here and say that the kernel people or cryptographers need to find a solution that satisfies the constraints the way we now measure reproducibility, because that is actually very deeply, definitionally impossible, like a square with three sides.