CSEC-742 Presentation

<p>https://p.rscha.nz/csec742</p>
<img src="csec742/qrcode.png" />

---

<h3>Reflections on Trusting Trust</h3>
<hr>
<p>A Retrospective</p>
<small style="margin-top: 1.5rem; color: gray">Ryan Schanzenbacher</small>

---

<h3>Reflections on Trusting Trust</h3>
<div style="display: inline-flex">
<p class="fragment" data-fragment-index="2">Turing Award Lecture by</p> <p style="margin-left: 1rem" data-id="ken1" class="fragment" data-fragment-index="2">Ken Thompson</p>
</div>

----

<div style="display: inline-flex">
<p data-id="ken1" style="font-size: 64px; color: var(--r-heading-color)">Ken Thompson</p>
</div>
<h3 style="margin: 0"></h3>
<img class="r-stretch" data-src="https://cdn.facesofopensource.com/wp-content/uploads/2017/03/23214126/faces.KenThompson20449.web_.jpg">
<p>Founder of UNIX and Co-Creator of C.</p>

----

<h3>Ken Thompson</h3>
<ul>
<li>Worked at Bell Labs from 1966-2000</li>
<li>Works at Google from 2006-Present</li>
<li>Also created Golang, UTF-8 encoding, etc.</li>
<li>Won a Turing Award with Dennis Richie</li>
</ul>

----

### Reflections on Trusting Trust
- Acceptance Lecture by Ken in 1983
- Can you actually trust anything?
    - Looking at software, can you trust it's secure?

----

<h3>Trusting Software</h3>
<ul>
<li class="fragment" data-fragment-index="1">How do you know if software is secure?</li>
<ul>
<li class="fragment" data-fragment-index="2">Look at the source code!</li>
</ul>
<li class="fragment" data-fragment-index="3">Well, how do you execute it?</li>
<ul>
<li class="fragment" data-fragment-index="4">You compile* the executable!</li>
<li class="fragment" data-fragment-index="5">...Where does the compiler come from?</li>
</ul>
</ul>
<small class="fragment" data-fragment-index="4">*For compiled languages, I'm going to stay away from interpreted.</small>

----

<h3>Can you trust the compiler?</h3>
<ul>
<li class="fragment">How can you tell if a compiler is secure?</li>
<ul>
<li class="fragment">Look at the source code!</li>
</ul>
<li class="fragment">Well, how do you execute the compiler?</li>
<ul>
<li class="fragment">You... compile it....</li>
</ul>
</ul>
<img class="fragment" data-src="csec742/recursion.gif" width="480" height="300"></img>

----

<h3>An example</h3>
<p class="fragment" data-fragment-index="2">Let's take a look at Golang's toolchain (Ken again!)</p>
<p class="fragment" data-fragment-index="2">How do you build go?</p>

----

<p>Remember! Current Go is written completely in Go. It is <i>self-hosting</i>
<p class="fragment">Given this... how do we start without Go?</p>
<div class="mermaid mermaid-fill fragment">
%%{init: {'theme': 'dark', 'themeVariables': {'darkMode': true }}}%%
flowchart LR
gcc(GCC);
goold(Go 1.4);
gocur(Current Go);
gcc --> goold;
goold --> gocur;
</div>

----

<h4>Delving deeper... How do we begin without <i>GCC</i>?</h4>
<ul>
<li class="fragment">Is trustable computing gone forever?</li>
</ul>

---

<h3>Reproducibility</h3>
<p>Can you gurarantee "correctness"?</p>

----

### What is considered correct?
* Different systems must come to the same conclusion
* It must be verifiable and repeatable
    * Run a build 3-4 times, is the binary exactly the same?

----

### How is this done?
* Keep variables to a minimum 
* Have well defined build-environments

----

### "Commandments" of reproducible builds
1. Strip ALL references to build hostname and user
1. Reset ALL file dates to epoch start (Jan 1 1970)
1. No Address Space Layout Randomization
1. Do work predictably and in order

----

1. Do not utilize any random numbers or other sources that require entropy
1. Keep parallelism deterministic
1. No CPU specific features
1. No CPU specific optimizations

----

1. Allow for offline builds using pre-downloaded artifacts
1. Take note of your environment

----

### Where are we today?
[Reproducible Builds](https://reproducible-builds.org) are growing!
Many popular distros are striving to become fully reproducible

----

<h3>Arch Linux</h3>
<img data-src="csec742/arch_repro.png" class="r-stretch" />

----

<h3>Debian</h3>
<img data-src="csec742/debian_repro.png" class="r-stretch" />

----

----

<h3>NixOS</h3>
<img data-src="csec742/nix_repro.png" class="r-stretch" />

---

<p>How do we build GCC without GCC?</p>

----

<h3>Bootstrapping</h3>
We can <i>bootstrap</i> our system!

----

<h3>One issue...</h3>
<p class="fragment">This is an <i>incredibly</i> difficult problem to solve</p>

----

<h3>Quick aside</h3>
<ul>
<li>GCC is incredibly complex and old</li>
<ul>
<li class="fragment" data-fragment-index="0">The first beta release was made in 1987!</li>
<li class="fragment" data-fragment-index="1">Unsure what it was first compiled with</li>
<ul>
<li class="fragment" data-fragment-index="1">Amsterdam Compiler Kit</li>
<li class="fragment" data-fragment-index="1">Livermore Compiler</li>
</ul>
<li class="fragment" data-fragment-index="2">Contains ~15M LOC around 2019</li>
<ul>
<li class="fragment" data-fragment-index="2">This is around the same as Linux itself!</li>
</ul>
</ul>
<li class="fragment" data-fragment-index="3">It was made to be self-hosting almost immediately</li>
</ul>

----

<h3>Formal definition of Bootstrapping</h3>
<p>"Bootstrapping is about building a compiler (and eventual system) using tools smaller than itself..."</p>

----

<h3>How complicated are systems now?</h3>
<img data-src="csec742/coreutils_deps.png" class="r-stretch" />

----

<h3>Is it possible anymore?</h3>
<p>Short answer: Sort of!</p>

----

<h3>Where are we today?</h3>
<ul>
<li class="fragment" data-fragment-index="0">A small group of people are working on this</li>
<ul>
<li class="fragment" data-fragment-index="1">Very small (111 people in IRC)</li>
</ul>
<li class="fragment" data-fragment-index="2">Main contributions by:</li>
<ul>
<li class="fragment" data-fragment-index="2">Jeremiah Orians (oriansj)</li>
<li class="fragment" data-fragment-index="2">Richard Master</li>
<li class="fragment" data-fragment-index="2">Nicholas Fraser (ludocode)</li>
<li class="fragment" data-fragment-index="2">Googulator</li>
<li class="fragment" data-fragment-index="2">And a handful of others...</li>
</ul>
</ul>

----

<h3>Where are we today?</h3>
<ul>
<li class="fragment">Lots of efforts are disjointed</li>
<li class="fragment">We can (theoretically) bootstrap x86_64</li>
</ul>

----

<pre><code data-trim>
# SPDX-FileCopyrightText: 2023 Richard Master 
# SPDX-License-Identifier: MIT
#
# Builder-Hex0 is a small bootable machine image which acts as
# a bootloader using a hex0 compiler. It compiles hex0 code starting
# at sector 2, placing the compiled code at address 0x7E00 and then
# and then jumps to the resulting binary.
#
# hex0 is a "language" for binary encoding in hexadecimal
# with support for comments.

# Functions:
# _start
# read_sector
# read
# compile

#------------------------------------------------------------
# Memory:
#  9FC00 -  FFFFF BIOS
#   7C00 -   7E00 MBR/code
#   7A00 -   7BFF sector read buffer
# < 7700          real mode stack
#------------------------------------------------------------

# ------------------------------------------------------------
# Stub Entry Point
#
# boot drive is in dl
#
#[7C00][15]
#:_start

# We cannot be sure the registers are initialized to zero so we
# do that first. We far jump to mbr_main in order to set CS.
31 C0           # xor ax, ax
8E D8           # mov ds, ax
8E C0           # mov es, ax
8E D0           # mov ss, ax
BC 00 77        # mov sp, 0x7700
FC              # cld ; clear direction flag

#----------------------------------------
# Compile hex0 to binary
# compile(dl=boot_drive):
#[7C0C]
BF 00 7E        # mov di, 0x7E00

# this flag is set after the first digit is seen
31 DB           # xor bx,bx

#:read_loop
9A 91 7C 00 00  # call read
84 C0           # test al, al
74 4D           # jz finish

3C 23           # cmp al, '#'
74 28           # jz skip_comment

3C 3B           # cmp ';'
74 24           # jz skip_comment

3C 66           # cmp al, 'f'
7F EB           # jg read_loop

3C 61           # cmp al, 'a'
7C 04           # jl maybe_upper

# Handle a to f
2C 57           # sub al, 'a'-10 == 87 = 0x57
EB 23           # jmp maybe_store

#:maybe_upper
3C 46           # cmp al, 'F'
7F DF           # jg read_loop

3C 41           # cmp al, 'A'
7C 04           # jl maybe_digit

# Handle A to F
2C 37           # sub al, 'A'-10 == 55 = x37
EB 17           # jmp maybe_store

#:maybe_digit
3C 39           # cmp al, '9'
7F D3           # jg read_loop

3C 30           # cmp al, '0'
7C CF           # jl read_loop

# Handle 0 to 9
2C 30           # sub al, '0' == x30
EB 0B           # jmp maybe_store

#:skip_comment
9A 91 7C 00 00  # call read
3C 0A           # cmp al, '\n'
75 F7           # jnz skip_comment
EB C0           # jmp read_loop

# only store on second digit
#:maybe_store
84 DB           # test bl, bl
75 09           # jnz second_digit

# If on first digit, record and keep going
#:first_digit
C0 E0 04        # shl al, 4
88 C7           # mov bh, al
FE C3           # inc bl
EB B3           # jmp read_loop

# If on second digit, store and clear state
#:second_digit
08 C7           # or bh, al
88 F8           # mov al, bh
AA              # stosb
31 DB           # xor bx, bx

EB AA           # jmp read_loop

#:finish
EA 00 7E 00 00  # ljmp $0000:7E00       ; jump to stage2

#[7C6C][  ]
#:read_sector(di = *dest_addr, cx=cylinder/sector, dh = head, dl=drive)
#
# returns: di - next byte to write to
#          cx,dh - next disk sector to read from
#
50              # push ax
53              # push bx

89 FB           # mov bx, di      ; int 13 writes to bx

#:read_one_loop
B4 02           # mov ah, 2        ; rw mode = 02 (read)
B0 01           # mov al, 1        ; num_sectors
CD 13           # int 0x13
72 F8           # jnc read_one_loop
3C 01           # cmp al, 1
75 F4           # jnz read_one_loop

80 F9 3F        # cmp cl, 0x3f        ; if sector_num == max_sector
74 04           # jz next_head        ;      goto next_head
FE C1           # inc cl              ; else sector_num++;
EB 04           # jmp cleanup

#next_head:
FE C6           # inc dh              ; else head_num++
B1 01           # mov cl, 1           ; sector = 1

5B              # pop bx
58              # pop ax
CB              # retf

#----------------------------------------
# last_read_location
#[7C8C]
02 00    ; last_cylinder/sector
00       ; last_head
FF 01    ; last_byte

#[7C91]
#:read()
53                    # push bx
51                    # push cx
52                    # push dx
56                    # push si
57                    # push di

# get current position
BB 8C 7C              # mov bx, last_read_location
8B 0F                 # mov cx, [bx]
8A 77 02              # mov dh, [bx+2]
8B 47 03              # mov ax, [bx+3]

#end of sector?
3D FF 01              # cmp ax, 0x01ff
74 03                 # je next sector

#nextchar:
40                    # inc ax
EB 0F                 # jmp getchar

#read next sector
BF 00 78              # mov di, 0x7800
9A 6C 7C 00 00        # call read_sector
# save new location and offset
89 0F                 # mov [bx], cx
88 77 02              # mov [bx+2], dh
31 C0                 # xor ax, ax

#getchar:
89 47 03              # mov [bx+3], ax
BE 00 78              # mov si, 0x7800
89 C3                 # mov bx, ax
8A 00                 # mov al, [si+bx]

#finish:
5F                    # pop di
5E                    # pop si
5A                    # pop dx
59                    # pop cx
5B                    # pop bx
CB                    # ret

# padding to fill a 512 byte sector
00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00
# This is the DOS/MBR identifier at offset 510:
55 AA
</code></pre>

<p>Equivalent to</p><pre><code>sed 's/[;#].*$//g' $input_file | xxd -r -p > $output_file</code></pre>

----

<h3>Our toolchain</h3>
<div class="mermaid mermaid-fill2">
%%{init: {'theme': 'dark', 'themeVariables': {'darkMode': true }}}%%
flowchart LR
h0(hex0);
h1(hex1);
kaem(kaem);
h2(hex2);
catm(catm);
cc86(cc_x86);
m2p(m2-planet);
mescct(mescc-tools);
m2mp(m2-mesoplanet);
mesfirst(mes 0.25);
tccfirst(tinycc 0.9.26);
tccfinal(tinycc 0.9.27);
fwx(fiwix 1.4.0);
cut(coreutils);
musl(musl libc);
gcc4(GCC 4);
lin4(Linux 4.9);
gcc10(GCC 10);
gcc13(GCC 13);
h0 --> h1;
h1 --> kaem;
kaem --> h2;
h2 --> catm;
catm --> cc86;
cc86 --> m2p;
m2p --> mescct;
mescct --> m2mp;
m2mp --> m2p;
m2p --> mesfirst;
mesfirst --> tccfirst;
tccfirst --> tccfinal;
tccfinal --> fwx;
fwx --> cut;
cut --> musl;
musl --> gcc4;
gcc4 --> lin4;
lin4 --> gcc10;
gcc10 --> gcc13;
</div>

----

---

### The future of software distribution
Nix/Guix and declarative package management

----

### Why are they cool?
They are declarative!

----

### What does this mean?
```scheme
(define-public base-operating-system
(operating-system
(kernel linux-6.8)
(firmware (list linux-firmware))
(locale "en_US.utf8")
(timezone "America/New_York")
(keyboard-layout (keyboard-layout "us"))
(host-name "ThisWillChange")

;; The list of user accounts ('root' is implicit).
(users (cons* (user-account
(name "ryan")
(comment "Ryan")
(group "users")
(shell (file-append fish "/bin/fish"))
(home-directory "/home/ryan")
(supplementary-groups '("wheel" "netdev" "audio" "video" "lp" "plugdev" "docker" "libvirt" "kvm" "dialout")))
%base-user-accounts))

(packages (append (map specification->package (list
                            "sway"
                            "hyprland"
                            "swaybg"
                            "fuzzel"
                            "foot"
                            "pinentry-qt"
                            "adwaita-icon-theme"
                            "hicolor-icon-theme"
                            "git"
                            "nss-certs"
                            "waybar"
                            "gnupg"
                            "light"
                            "avahi"
                            "mako"
                            "grim"
                            "grimblast"
                            "slurp"
                            "wl-clipboard"
                            "ldacbt"
                            "libfreeaptx"
                            "libfdk"
                            "opendoas"
                            "xdg-desktop-portal"
                            "xdg-desktop-portal-gtk"
                            "v4l2loopback-linux-module"
                            "pipewire"
                            "docker"
                            "dconf"
                            "wireplumber"
                            "wireshark"
                            "zsh"))
   (list my-ca-certs swaylock-effects-new xdg-desktop-portal-hyprland-ryan virt-manager-ovmf bluez-ryan blueman-ryan swayidle-new)
   %my-base-packages ))

(services
(append (list
(service openssh-service-type)
(service pcscd-service-type)
(service cups-service-type
    (cups-configuration
      (web-interface? #t)))
;; Avahi is only present for CUPS to support "automagic" printing
(service avahi-service-type
   (avahi-configuration
     (publish? #f) ;; do not advertise this machine
     (publish-workstation? #f))) ;; do not advertise, I want this to be as silent as possible
(service docker-service-type)
(service nix-service-type)
(service libvirt-service-type
    (libvirt-configuration
      (libvirt libvirt-ovmf)
      (unix-sock-group "libvirt")))
(service bluetooth-service-type
    (bluetooth-configuration
      (bluez bluez-ryan)
      (experimental #t)
      (fast-connectable? #t)))
(udev-rules-service 'fido2 libfido2 #:groups '("plugdev")))

(name-service-switch %mdns-host-lookup-nss) ;; Enable .local lookup
(setuid-programs
(append (list (file-like->setuid-program
(file-append
;(specification->package "swaylock-effects")
swaylock-effects-new
 "/bin/swaylock"))
(file-like->setuid-program
(file-append
(specification->package "wireshark")
"/bin/dumpcap"))
(file-like->setuid-program
(file-append
(specification->package "spice-gtk")
"/libexec/spice-client-glib-usb-acl-helper"))
(file-like->setuid-program
(file-append
(specification->package "opendoas")
"/bin/doas")))
(delete sudo %setuid-programs)))
(file-systems (cons*
(file-system
(mount-point "/tmp")
(device "none")
(type "tmpfs")
(check? #f))
%base-file-systems))
(bootloader (bootloader-configuration
(bootloader grub-efi-bootloader)
(targets (list "/boot/efi"))
(keyboard-layout keyboard-layout)))))
```

----

### Can't ansible do this?
- Ansible relies on a known starting state!
    - It bakes declaritivity on top of imperative systems
    - Nix and Guix are built from the ground up
```scheme
(bootloader (bootloader-configuration
(bootloader grub-efi-bootloader)
(targets (list "/boot/efi"))
(keyboard-layout keyboard-layout)))))
```

----

<h3>Packages are fully declarative as well!</h3>
<ul>
<li>This solves the issue of reproducibility!</li>
</ul>

<pre data-id="code-animation-1"><code data-trim data-line-numbers>
(define-public wl-mirror
  (package
    (name "wl-mirror")
    (version "0.16.1")
    (source (origin
              (method git-fetch)
              (uri (git-reference
                     (url "https://github.com/Ferdi265/wl-mirror")
                     (commit (string-append "v" version))
                     (recursive? #t)))
              (file-name (git-file-name name version))
              (sha256
                (base32
                  "06i4jrip4q9j1gp81j0jr79cwfj9zdcfcr1n0jpyqlxsysppidlc"))))
    (inputs (list wayland egl-wayland mesa))
    (native-inputs (list pkg-config scdoc wayland-protocols))
    (build-system cmake-build-system)
    (arguments (list
                 #:tests? #f
                 #:phases
                 #~(modify-phases %standard-phases
                    (add-before 'configure 'touch
                      (lambda _
                        (invoke "touch" "proto/wayland-protocols/.git")
                        (invoke "touch" "proto/wlr-protocols/.git"))))))
    (home-page "bleh")
    (synopsis "mirror displays")
    (description "mirror displays")
    (license license:expat)))
</code></pre>

----

<pre data-id="code-animation-1"><code data-trim data-line-numbers>
              (sha256
                (base32
                  "06i4jrip4q9j1gp81j0jr79cwfj9zdcfcr1n0jpyqlxsysppidlc"))))
    (inputs (list wayland egl-wayland mesa))
    (native-inputs (list pkg-config scdoc wayland-protocols))
    (build-system cmake-build-system)
    (arguments (list
                 #:tests? #f
</code></pre>

----

<p>This stops the XZ backdoor!</p>
<p>The entire git repository is verified</p>
<p>Even substitutions (remote builds) can be verified locally</p>

----

<h3>Everything has a known provenance</h3>

----

<h3>Including Guix itself!</h3>
<div style="display: flex; justify-content: center; align-items: center">
<img width="373px" height="62px" style="flex:1; max-width: 373px" data-src="csec742/guix_bootstrap_1.png" />
<img height="403px" width="316px" style="flex:1; max-width: 316px" data-src="csec742/guix_bootstrap_2.png" />
</div>
<p>Bringing the ideally reproducible and bootstrappable system closer to a reality!</p>

---

### Join!
- #bootstrappable on libera.chat
- #guix on libera.chat
- Any of the repos mentioned in the sources!

----

#### Sources
- https://en.wikipedia.org/wiki/Ken_Thompson#Turing_Award
- https://www.cs.cmu.edu/~rdriley/487/papers/Thompson_1984_ReflectionsonTrustingTrust.pdf
- https://reproducible-builds.org/who/projects/
- https://guix.gnu.org/manual/en/html_node/Bootstrapping.html
- https://guix.gnu.org/manual/en/html_node/Invoking-guix-graph.html
- https://go.dev/doc/install/source#go14

----

- https://reproducible-builds.org/docs/commandments/
- https://gcc.gnu.org/wiki/History
- https://en.wikipedia.org/wiki/GNU_Compiler_Collection
- https://bootstrapping.miraheze.org/wiki/Main_Page
- https://www.nature.com/articles/s41597-022-01720-9
- https://guix.gnu.org/en/blog/2023/the-full-source-bootstrap-building-from-source-all-the-way-down/

----

- https://github.com/fosslinux/live-bootstrap
- https://github.com/ironmeld/builder-hex0
- https://github.com/oriansj/stage0-posix

----

## Questions?