The fixed-point project

The fixed-point project

[Ludovic Courtès]

[-- Attachment #1: Type: text/plain, Size: 3147 bytes --]

Hello!

Our wonderful manual, under “Building the Bootstrap Binaries” [0],
questions when we reach fixed point.  I rebuilt the bootstrap binaries
in an attempt to answer that question.

Basically, after two runs I got the bit-for-bit identical tarball for
Binutils, but the other 4 tarballs differed.  The differences were a
4-byte CRC related to .gnu_debuglink (for files that had that), a
timestamp in Guile, and non-determinism in the way Guile generates
identifiers at macro-expansion time.

I’ve fixed some of that, and the rest should be easy to fix.  Then we
quickly reach fixed point.  Neat, no?  :-)


Actually it’s Christian Grothoff who prompted me to look at this during
the GHM, for several good reasons.

First, when we achieve fixed-point, users can just run ‘guix build
bootstrap-tarballs’ at home and notice that they get tarballs that are
bit-for-bit identical to those referred to in bootstrap.scm.  That tells
them that the recipe they have is really the one that was used to build
those tarballs (whereas currently they have to trust me.)

However, in theory, that doesn’t save us from trusting-trust
attacks [1]: the bootstrap GCC could contain a trap, such that the trap
is always preserved across recompilations of GCC, even if it’s absent
From the GCC source being compiled.

David A. Wheeler’s thesis [2] addresses this topic.  Roughly, it shows
that a compiler can be tested for traps by relying on a “trusted”
compiler [3].

For Guix, though, another variable is time: if the current bootstrap
binary is taken for “trusted”, then it may be enough to build the whole
chain of trust, for the rest of time.  That is: we may be able to show
that we obtain the same bootstrap binaries regardless of whether we use
the current bootstrap binaries (taken for trusted), or those just built
(under test).

Even better, Guix can cross-compile, so we could inject cross-compiled
bootstrap binaries as the input, and use them as the starting point to
rebuild bootstrap binaries.  These should be bit-for-bit identical to
those obtained with other bootstrap binaries.


A next step would be generalized bit-for-bit reproducibility [4].
That’s going to be more work, because each package may have
non-determinism issues of its own that need to be fixed.  This is also
something the Nix people have been looking at [5].


Anyway, that opens up a whole lot of perspectives that seem very useful
now that the (arguably unsurprising) state surveillance has been
exposed.

Thoughts? Comments?

Thanks again to Christian for insisting ;-) and for the enlightening
discussions we’ve had, and to Mark H. Weaver for pushing some more.

Ludo’.

[0] http://www.gnu.org/software/guix/manual/guix.html#Bootstrapping
[1] http://cm.bell-labs.com/who/ken/trust.html
[2] http://www.dwheeler.com/trusting-trust/
[3] https://www.schneier.com/blog/archives/2006/01/countering_trus.html
[4] https://blog.torproject.org/blog/deterministic-builds-part-one-cyberwar-and-global-compromise
[5] https://nixos.org/wiki/Long-term_open_issues:build_determinism

[-- Attachment #2: Type: application/pgp-signature, Size: 197 bytes --]

Re: The fixed-point project

[Ludovic Courtès]

[-- Attachment #1: Type: text/plain, Size: 291 bytes --]

ludo@gnu.org (Ludovic Courtès) skribis:

> Thanks again to Christian for insisting ;-) and for the enlightening
> discussions we’ve had, and to Mark H. Weaver for pushing some more.

... and I forgot to thank Andreas for his insightful comments in Paris
and afterward.

Ludo’.

[-- Attachment #2: Type: application/pgp-signature, Size: 197 bytes --]

Re: The fixed-point project

[Alex Sassmannshausen]

Wow, and here I thought this would be the announcement of the intention to be starting to work on this... Awesome - congrats on this first milestone.

Alex 

On Fri Sep 20 00:10:31 2013 Ludovic Courtès <ludo@gnu.org> wrote:
> ludo@gnu.org (Ludovic Courtès) skribis:
> 
> > Thanks again to Christian for insisting ;-) and for the enlightening
> > discussions we’ve had, and to Mark H. Weaver for pushing some more.
> 
> ... and I forgot to thank Andreas for his insightful comments in Paris
> and afterward.
> 
> Ludo’.

Re: The fixed-point project

[Mark H Weaver]

Hi Ludovic,

ludo@gnu.org (Ludovic Courtès) writes:

> However, in theory, that doesn’t save us from trusting-trust
> attacks [1]: the bootstrap GCC could contain a trap, such that the trap
> is always preserved across recompilations of GCC, even if it’s absent
> From the GCC source being compiled.
>
> David A. Wheeler’s thesis [2] addresses this topic.  Roughly, it shows
> that a compiler can be tested for traps by relying on a “trusted”
> compiler [3].

I don't think this is an adequate summary of David's technique for
defeating Thompson viruses.  Under his method, one needn't trust any
single compiler.  Instead, one uses several different compilers to
bootstrap a single compiler, and checking that the results of all of
those bootstraps yield the same result.  One need only trust that the
first-stage compilers aren't _all_ compromised with the same Thompson
virus.  This is much more reasonable than expecting everyone to trust
the Guix bootstrap tarballs.  In order to defeat this method, a Thompson
virus would have to be sophisticated enough to hide itself in all of the
compilers, and be able to jump from one compiler to another.

    Regards,
      Mark

Re: The fixed-point project

[Ludovic Courtès]

Mark H Weaver <mhw@netris.org> skribis:

> Hi Ludovic,
>
> ludo@gnu.org (Ludovic Courtès) writes:
>
>> However, in theory, that doesn’t save us from trusting-trust
>> attacks [1]: the bootstrap GCC could contain a trap, such that the trap
>> is always preserved across recompilations of GCC, even if it’s absent
>> From the GCC source being compiled.
>>
>> David A. Wheeler’s thesis [2] addresses this topic.  Roughly, it shows
>> that a compiler can be tested for traps by relying on a “trusted”
>> compiler [3].
>
> I don't think this is an adequate summary of David's technique for
> defeating Thompson viruses.  Under his method, one needn't trust any
> single compiler.  Instead, one uses several different compilers to
> bootstrap a single compiler, and checking that the results of all of
> those bootstraps yield the same result.

Right.

> One need only trust that the first-stage compilers aren't _all_
> compromised with the same Thompson virus.  This is much more
> reasonable than expecting everyone to trust the Guix bootstrap
> tarballs.  In order to defeat this method, a Thompson virus would have
> to be sophisticated enough to hide itself in all of the compilers, and
> be able to jump from one compiler to another.

Yes, you’re right (I may have been fooled by the wording in
<http://www.dwheeler.com/trusting-trust/dissertation/html/wheeler-trusting-trust-ddc.html#4.2.Informal%20description%20of%20DDC>.)

In Guix we can use different variants of the bootstrap compiler to build
the tarballs, but in practice I suspect these would have to remain
variants of the same thing (GCC), not completely different compilers.

Ludo’.