In deze aflevering laat ik zien hoe we met een binair programma van minder dan 512 bytes in vijf tussenstappen een moderne Linux-distributie kunnen compileren. Op dit moment is het alleen nog voor de i386 en x86_64-processoren, maar er wordt hard gewerkt om hetzelfde ook voor arm en riscv te realiseren.
Henk van de Kamer
De vorige keer namen we voor het gemak aan dat broncode geen achterdeurtjes bevat. Of dat terecht is, moet iedereen voor zichzelf beslissen. De beschikbaarheid van de broncode is in ieder geval een enorme stap richting dit vertrouwen. Het alternatief is namelijk Windows of macOS en dat zijn vele gigabytes aan binaire bestanden.
hex0
In ruim zeven jaar tijd is in Guix – de Linux-distributie van het GNU-project – de binaire basis teruggebracht naar 25 megabyte plus een viertal zaadjes – seeds in het Engels – voor de i386, x86_64, arm en riscv-systemen. Persoonlijk zou ik graag de laatste in mijn desktopcomputer zien, maar net als bij velen van jullie heeft deze helaas nog steeds een Intel-processor. Deze startte bijna vijftig jaar terug in de tijd als een 8086. Vanwege die bagage is het bootstrappen tot in de kleine details bekend en het is dan ook logisch om met deze te beginnen.
Het zaadje voor de x86_64 – ook wel bekend als AMD64, en diens uitbreidingen zijn ook aanwezig in de meeste Intel-processoren – is in binaire vorm 405 bytes groot. De eerste 120 bytes zijn voor de ELF-header, ofwel informatie die de Linux-kernel gebruikt om het programma in het geheugen te laden en starten. Windows en macOS hebben iets vergelijkbaars. De overige 285 bytes zetten de hex0-broncode om naar een binaire versie. Zoals we straks zullen zien, kan dit deel ook op andere manieren gestart worden.
De hex0-taal is zeer simpel. Commentaar begint met een # of ; en daarin wordt meestal de assembly-versie getoond. Deze kan – eventueel handmatig – worden omgezet naar hexadecimale waardes en dat is gewoon machinetaal in stenovorm. De start van de hex0-compiler ziet er zo uit:
#:_start
58 ; POP_RAX # Get the number of arguments
5F ; POP_RDI # Get the program name
5F ; POP_RDI # Get the actual input name
stage0-posix
In figuur 1 zien we het resultaat dat in april 2023 werd bereikt. De ovalen onderaan bevatten de binairies om alles daarboven te kunnen compileren. Dit gaat van onder naar boven, ofwel als eerste wordt bootar@1b gedaan. Tar staat voor Tape ARrchive en is niets anders dan bestanden aan elkaar plakken tot één geheel. In de praktijk gebruiken we meestal ook compressie, maar wie de blokken bestudeert, ziet dat dit pas veel later wordt toegevoegd.
Figuur 1: Bootstrap voor GCC 2.95.3 (stand april 2023)
De pijlen verwijzen naar waar een blok van afhankelijk is, vandaar dat je maar één roodbruine pijl zult ontdekken. De tekst achter de @ is een versienummer en het resultaat is in dit geval de GCC die in 2001 uitkwam. Zoals we de vorige keer hebben gezien, betekend self hosting dat we over een oudere, binaire versie moeten beschikken om een nieuwere te compileren.
De guile-bootstrap is zoals gezegd nog steeds 25 megabyte aan binaire bestanden groot. Guix gebruikt deze om hun variant van pakketbeheer te regelen. Die is absoluut interessant te noemen en waarschijnlijk zul je deze in een toekomstige aflevering tegenkomen.
Omdat pakketbeheer pas interessant begint te worden zodra we programma’s gaan compileren voor een nieuwere versie van een distributie, rijst de vraag of we met de bootstrap-seeds niet de sprong naar stage0-posix kunnen bereiken zonder – of met sterk uitgeklede versies – de onderste drie rechthoeken. De stage0-posix-omgeving is zeer minimalistische met een shell, een aantal programma’s en cc_x86 ofwel een zeer eenvoudige C-compiler. Dit alles heeft echter een Linux (compatibel) kernel nodig.
builder-hex0
Het builder-hex0 project (https://github.com/ironmeld/builder-hex0) heeft een minder dan vier kilobyte grote Linux-compatibel kernel. Het bevat een uitgeklede versie van de 15 belangrijkste systeemaanroepen. Veel van deze lijken te werken, maar doen in de praktijk alleen het absoluut noodzakelijke of melden vrolijk succes terwijl er niets wordt gedaan. Dit alles is geen probleem: het is een bootstrap en daarin kunnen en moeten we dingen versimpelen.
Ik ben ruim veertig uur bezig geweest om de Makefile uit te zoeken. De naamgeving van de bestanden en hun tussenresultaten was niet altijd duidelijk. Verder zijn er twee versies en daar kwam ik pas achter toen ik de proof of concept-variant zelf kon controleren. Voor de lezers van PC-Active heb ik een Bash script (http://files.armorica.tk/pc-active/build.sh.txt) geschreven die de andere, veel nuttigere variant in drie stappen maakt en controleert via een virtuele machine en het hierboven beschreven hex0-zaadje. Uiteraard moet je de builder-hex0-broncode – bijvoorbeeld via de zip-optie onder de groene codeknop – downloaden en uitpakken.
In de eerste stap converteer ik de broncode van hex0 via sed en xxd naar een binaire vorm. Vervolgens gebruik ik deze om nogmaals de broncode te compileren. Dit is te vergelijken met een compiler die een nieuwere versie van zichzelf compileert. Deze versie gebruiken we om nogmaals het geheel te compileren. In dit bijzondere geval zijn alle drie identiek, maar dat is lang niet altijd het geval. Wie de theorie achter deze stap wilt weten, kan naar dit YouTube-filmpje (https://www.youtube.com/watch?v=PjeE8Bc96HY) kijken.
Bootstrap
Nu we onze hex0-compiler hebben, kunnen we deze gebruiken om builder-hex0-x86-stage1.hex0 om te toveren naar een Master Boot Record (MBR). Inderdaad, dit is de eerste sector op een harddisk of floppy waarmee een besturingssysteem gestart kan worden. Het MBR bevat wederom een werkende hex0-vertaler. Omdat er nog genoeg ruimte over is, bevat het ook instructies om hex0-broncode vanaf de volgende sector in te lezen naar uitvoerbare machinetaal in het geheugen. De broncode is builder-hex0-x86-stage2.hex0 en die bevat de genoemde micro-Linux-kernel. Na het compileren wordt deze gestart.
Naast de genoemde 15 systeemaanroepen bevat de kernel ook een shell met een drietal interne opdrachten. Deze volgen na de broncode van de kernel en daarmee kan de kernel – die eveneens een kopie van de hex0-compiler bevat – de rest van een besturingssysteem via broncode bootstrappen! Inderdaad, alles wordt gecompileerd via het binaire hex0-zaadje in de MBR en broncode.
Vertrouwen?
In stap 2 en 3 van mijn script wordt als eerste nogmaals de MBR, kernel en de builder-hex0-x86-stage1.hex0- of builder-hex0-x86-stage2.hex0-broncode doorgegeven. Zodra de kernel de laatste – in dit geval dus enige – broncode heeft verwerkt, wordt de harddisk overschreven met het resultaat. Omdat we beide ook via het gemaakte zaadje kunnen compileren, moet beide identiek zijn. Zo ja, zijn er in beide geen achterdeurtjes aanwezig!
Stel dat het een veiligheidsdienst lukt om in de broncode van hex0 een achterdeur in te bouwen. Gezien diens grootte zal dat lastig worden. In mijn opzet moeten ze dit vervolgens ook doorvoeren in builder-hex0 – zowel voor de MBR als de kernel – en dat maakt deze aanval een paar horden moeilijker. Veel waarschijnlijker is de achterdeur doorvoeren in een Linux-onderdeel met toegang tot de broncode. Nu lijkt deze nodig, maar voor het prepareren van een harddisk die zichzelf kan bootstrappen, zie ik weinig problemen om dat bijvoorbeeld in FreeDOS te doen, waarmee deze aanval zo goed als onmogelijk wordt.
Helaas bevatten moderne computers nog veel meer binaire zooi waar de meeste van ons nooit over nadenken. Zo verwacht builder-hex0 een DOS compatibel BIOS en deze zit tegenwoordig verstopt in UEFI. Die is op mijn systeem reeds 16 megabyte groot en daarin kunnen we een volledige Windows 3.1 for Workgroups kwijt. Als we ook de verborgen processor in Intel- en AMD-exemplaren niet vergeten, mag duidelijk zijn waarom ik naar een RISC-V desktop wil overstappen.
live-bootstrap
Als laatste wil ik wijzen op het live-bootstrap (https://github.com/fosslinux/live-bootstrap/blob/master/README.rst) project. Deze gebruikt het builder-hex0 project om via stage0-posix de Fiwix (https://github.com/mikaku/Fiwix) kernel te compileren. Deze is compatibel met een Linux 2.x-kernel en tezamen met de nodige GNU-onderdelen een besturingssysteem om uiteindelijk een moderne Linux-distributie te compileren.
In 2001 gebruikte ik LFS (https://www.linuxfromscratch.org) – Linux from scratch – om ActiveLinux te maken met als idee om deze op de toenmaals maandelijkse cd-rom te verspreiden. Dat was de lfs_30pre2 ofwel een bèta van wat uiteindelijk het 3.0 boek opleverde. Die versie is in hun museum terug te vinden en gebruikt versie 2.4.8 van de Linux kernel versie 2.95.3 (!) van GCC. Kortom, een moderne Linux-distributie vanaf een enkel zaadje kleiner dan 512 bytes behoort absoluut tot de mogelijkheden!
