Show HN: Gegner mit einem RISC-V-Assembly-Tisch-Brettspiel hacken

 (punkx.org)
3 Punkte von GN⁺ 2023-10-01 | 1 Kommentare | Auf WhatsApp teilen
  • PROJEKT: OVERFLOW ist ein Lernspiel, das RISC-V-Assembly und Buffer Overflow in Brettspielregeln übersetzt, sodass man Speicher, Stack und die Manipulation von Rücksprungadressen direkt nachvollziehen kann
  • Die Spieler konkurrieren, indem sie sich denselben Speicher und dasselbe Programm teilen und ohne virtuellen Speicher in einem präemptiven Scheduling-Modell pro Zug nur 10 Befehle ausführen
  • Der Spielverlauf entscheidet sich daran, vorhandene Befehle zu kopieren, um Shellcode zu bauen, und die Rücksprungadresse des Gegners zu überschreiben, um ihn zu game_over() zu schicken
  • Falsche Speicherzugriffe, unaligned Lese-/Schreibzugriffe und illegale Befehle führen zu Abstürzen und zur Ausführung des Exception-Handlers; das Ändern der Trap-Adresse und nop-Monkeypatching sind zentrale strategische Variablen
  • Es gibt Web-Play, ein druckbares Spielbrett sowie ESP32- und Mobile-Game-Helfer, aber einige Regeln werden noch angepasst, sodass es eher einem experimentellen Hacking-Puzzle ähnelt

Spielziel und Ausführungsmodell

  • PROJEKT: OVERFLOW ist ein Projekt, das RISC-V-Assembly und Buffer Overflow als Tisch-Brettspiel behandelt
  • Das Kernziel ist, vorhandene Befehle zu kopieren, um kleinen Shellcode im Speicher zu erzeugen, per Buffer Overflow zu diesem Code zu springen und dann die Rücksprungadresse des Gegners zu überschreiben, sodass die Funktion game_over() aufgerufen wird
  • Die Strategie umfasst nicht nur einfache Codeausführung, sondern auch das Einrichten von Exception-Handlern und Monkeypatching
  • Alle Spieler teilen sich denselben Speicher und dasselbe Programm und verwenden denselben Prozessor im Time-Sharing-Modell
    • Pro Zug werden 10 Befehle ausgeführt
    • Der Stack Pointer jedes Spielers startet an einer anderen Position
    • Es gibt keinen virtuellen Speicher

Build- und Board-Erzeugungsablauf

  • Der Code wird mit riscv64-unknown-elf-gcc für das RV32-Ziel kompiliert
    • Wichtige Optionen sind unter anderem -march=rv32g, -mabi=ilp32, -ffreestanding, -nostdlib, -nostartfiles, -O0
    • Dank -O0 ist der Maschinencode ausführlich, aber leicht nachzuvollziehen
  • Die Materialien für das Spielbrett werden durch Parsen der Ausgabe von riscv64-unknown-elf-objdump -S -l -fd game erzeugt
    • ▲- und ✎-Befehle werden angepasst
    • Jump-Offsets werden von Hexadezimal in Dezimal umgewandelt
    • Das Assembly wird bereinigt und mit dem Quellcode abgeglichen
    • Danach wird ein SVG erzeugt und mit Inkscape in PDF umgewandelt

Druck und Materialien

  • Das Brett wird als in linke und rechte Hälfte geteiltes PDF gedruckt und verwendet
  • A3 wird zum Drucken bevorzugt, A4 ist ebenfalls möglich, aber klein
  • Benötigt werden 1 Spielstein für den nop-Befehl, 1 Spielstein für die Trap-Adresse, pro Spieler 2 Spielsteine für Program Counter und Stack Pointer sowie Bleistift und Radiergummi
  • Die Web-Version unterstützt Solo-Spiel und Spiel mit Freunden; außerdem gibt es einen ESP32- und Mobile-Game-Helfer

Grundregeln und Zugablauf

  • Der Startzustand ist wie folgt
    • Alle Register starten mit 0, aber das Return-Address-Register ra startet mit 1000
    • sp von Player 1 wird auf 2244 initialisiert, sp von Player 2 auf 3844
    • pc beider Spieler startet bei Adresse 1000, also am Beginn der Funktion main
    • Der Trap-Spielstein wird auf Adresse 1000 gesetzt
    • Alle Speicheradressen außer dem vorab geladenen Programm sind 0
    • Der nop-Befehlsstein wird anfangs nicht auf das Brett gelegt
  • In einem Zug müssen 10 Befehle ausgeführt werden; Sprünge wie jal oder beq müssen dabei unverändert verfolgt werden
  • Ein Spieler kann den Zug nach mindestens 1 ausgeführten Befehl beenden und die übrigen Befehle auf den nächsten Zug übertragen
    • Die maximal ansammelbare Befehlszahl beträgt 20

Monkeypatch und Siegbedingungen

  • Zu Beginn jedes Zuges kann nach genau 1 ausgeführten Befehl der nop-Befehlsstein auf eine beliebige Adresse in einer Funktion gelegt werden, die von den aktuellen Spielern nicht gerade ausgeführt wird
  • Wenn pc diese Adresse erreicht, verhält sich der Befehl dort als no-operation
  • Wer den nop-Stein versetzt, verliert den aktuellen und den nächsten Zug, und der Gegner kann im nächsten Zug bis zu 20 Befehle ausführen
  • Die Monkeypatch-Regel ist noch nicht ausbalanciert und wird alle paar Tage leicht verändert
  • Im Hard Mode endet das Spiel, wenn man den Gegner hackt und die Funktion game_over() aufrufen lässt
  • Wenn keine Seite den Gegner mehr zu game_over() schicken kann, endet das Spiel unentschieden
  • Im Easy Mode gewinnt der erste Spieler, der in main ret ausführt und damit die Main-Loop verlässt

Besondere Symbole und Exception-Handling

  • ✎ erlaubt es, als Immediate-Wert eines li-Befehls eine beliebige 12-Bit-Zahl von 0 bis 4095 zu wählen
  • ▲ erlaubt es, bei Load-Befehlen einen Wert im Bereich von ±128 Byte relativ zum eigenen Stack Pointer zu wählen
    • Wenn sp zum Beispiel 2180 ist, kann man von 2052 bis 2308 wählen
  • Verbotene Aktionen führen zum Absturz des Programms
    • Überschreiben von Speicheradressen unterhalb von 1192
    • Unaligned Lese- oder Schreibzugriffe auf Adressen, die kein Vielfaches von 4 sind
    • Ausführung illegaler Befehle
  • Bei einem Absturz wird der Exception-Handler ausgeführt und zur Trap-Adresse gesprungen
    • Die Trap-Adresse ist anfangs 1000, kann aber in der Funktion set_trap() überschrieben werden
    • Wenn eine Exception auftritt, wird der Program Counter auf einen bestimmten Wert gesetzt und die Ausführung fortgesetzt
  • Wenn Betrug oder Fehler entdeckt werden, werden Programmzustand, Speicher und Register des betreffenden Spielers zurückgesetzt

Erweiterungsregeln für 3 bis 4 Spieler

  • sp von Player 3 wird auf 2116 gesetzt
  • sp von Player 4 wird auf 3716 gesetzt
  • Bei 3 oder mehr Spielern darf das Symbol ▲ nur für den Bereich verwendet werden, der 128 Byte unter dem Stack Pointer liegt
  • Mit mehr als 2 Spielern wird das Spiel ziemlich instabil und beschädigt sich schnell
  • Die Siegbedingung zu erreichen wird schwieriger, aber das Spiel wird unterhaltsamer und chaotischer

Beispiele für Hacking-Strategien

  • Abstürze können als offensive Strategie genutzt werden, um den Fortschritt des Gegners zu blockieren
  • Wenn der Trap-Handler auf die Funktion game_over geändert wird, verliert der Spieler, der zuerst abstürzt
    • In diesem Zustand ist der nop-Stein sehr stark
    • Wenn der Gegner nop auf das ret in der aktuell ausgeführten Funktion legt, kann der andere Spieler verlieren
  • Wenn in der Funktion bug() der Index mit 400 oder -400 zum Overflow gebracht wird, kann man auf den Stack des Gegners zugreifen und dessen Rücksprungadresse überschreiben
    • Um beispielsweise von Adresse 3784 zu 2184 zu gelangen, gilt (3784 - 2184) / 4 = 400, also wird Index -400 benötigt
  • Mit der Funktion copy() kann man bestimmte Befehle kopieren und kurzen Shellcode im Speicher erzeugen
    • Beispielhafter Shellcode führt mit der Kombination li a4, ✎, li a5, ✎, sw a4, 0(a5), ret einen beliebigen Schreibzugriff aus
    • Wenn der ret-Befehl kopiert wird, wird die Rücksprungadresse auf den Startpunkt des Shellcodes gesetzt, was zu einer Endlosschleife führt
  • Wenn in der Funktion bug() der Index auf 6 gesetzt wird, kann die Variable value über die im Stack gespeicherte Rücksprungadresse 28(sp) geschrieben werden
    • Bei der Rückkehr aus bug() wird der Wert von 28(sp) in das Return-Address-Register kopiert
    • Setzt man dort die Adresse des erzeugten Shellcodes ein, kann man in den Speicher springen

Befehlsinterpretation und Änderungen

  • Alle Sprünge sind relativ zum aktuellen Program Counter, auch wenn sie im Disassembler wie absolute Adressen aussehen
    • Zum Beispiel wird der Maschinencode 1903 für jal a4, 0 bei der Ausführung zu einer Endlosschleife
  • Die Liste gültiger Spielbefehle ist auf RV32-JRI-Befehle mit Maschinencode 0 bis 4095 beschränkt, in Formen, die unter anderem a0, a4, a5, sp und ra verwenden
  • Das Änderungsprotokoll 0.0.6 enthält eine Änderung von while(run) zu while(*prun)
    • Dadurch kann der Gegner über eine unaligned Dereferenzierung einen erzwungenen Absturz auslösen
    • Die NOP-Regel wurde so geändert, dass sie nur in Funktionen platziert werden darf, die gerade nicht ausgeführt werden

Design und Lernmaterialien

  • Die Rechtecke links und rechts auf dem Brett sind eine als ASCII codierte Binärnachricht
    • Weiße Rechtecke stehen für 1, schwarze Rechtecke für 0
  • Die Farben beschränken sich auf Rot, Blau, Schwarz und Weiß, um günstigen Druck und gute Lesbarkeit auf Schwarzweißdruckern zu ermöglichen
  • Syntax-Highlighting wird nicht verwendet
    • So soll vermieden werden, dass Teile des Codes je nach Theme wichtiger wirken, und stattdessen eigene Beurteilung und Konzentration gefördert werden
  • Als Lernmaterialien für RISC-V-Assembly dienen riscv-programming.org, cs3410 risc-v interpreter, rvcodecjs von luplab
  • Als Lernmaterial für C wird der erste Teil von Beej's Guide to C Programming verwendet
  • Es gibt druckbare Assembly-Übungs-PDFs zu Variablen, Funktionsaufrufen, Pointern, Strings, Strukturen, Arrays und Rekursion sowie eine Lückentext-Version als „assembly hangman“

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2023-10-01
Hacker-News-Kommentare

  • Wirklich beeindruckend. Besonders großartig finde ich, dass er seine 12-jährige Tochter dazu gebracht hat, das mitzuspielen.
    Wann können wir mit einer CHERI-Version rechnen? :-D

    • Da es bei CHERI in etwa darum geht, „die Sicherheit der modernen C-Sprach-TCB durch Prozessorunterstützung für feingranularen Speicherschutz und skalierbare Software-Isolation deutlich zu verbessern“, mit drei zentralen Designzielen und teils widersprüchlichen Anforderungen, die eine sorgfältige Abstimmung im Design nötig machten, dürfte eine CHERI-Version schwierig werden :)
    • Mit 12 habe ich 6502-Assembler geschrieben. In heutigen Computerumgebungen ist es für 12-Jährige nicht leicht, so etwas zu tun.
    • In der 8-Bit-Ära war das ein übliches Alter für den Einstieg in Computer.

  • Core War ist ein Spiel in einer Speicherarena einer virtuellen Maschine, die eine einfache simulierte Assemblersprache unterstützt. Ich habe es 1984 zum ersten Mal in Scientific American gesehen, und da ich damals schon etwa 15 Jahre programmiert hatte, erkannte ich, dass es vom älteren Bell-Labs-Spiel Darwin inspiriert war.
    Darwin wurde 1961 entwickelt und lief auf dem IBM 7090. Programme konkurrierten um Ressourcen; das Programm, das den gesamten zugewiesenen Bereich durch Replikation übernahm, gewann. Nachdem Robert Morris Sr. ein unschlagbares Programm geschrieben hatte, hielt es sich nicht mehr lange. Siehe [2].
    Mitte der 1970er war Software Practice and Experience eines meiner liebsten Informatik-Journals, und es enthielt oft die Kolumne Computer Recreations, geschrieben unter dem Pseudonym Aleph-Null. Während meiner Zeit als Doktorand habe ich mehrere Spiele aus dieser Kolumne implementiert und viel Spaß damit gehabt. Das Journal ist teuer, aber als Studierender findet man es wahrscheinlich, so wie ich damals, in der Universitätsbibliothek. Die Ausgaben aus den 1970ern waren mit Themen wie Pascal-Compilern, Algol 68 und nebenläufiger Programmierung gut lesbar und interessant; über Texte von N. Wirth lernte ich Module[3,4] und später Oberon[5] kennen.
    [1] https://en.wikipedia.org/wiki/Core_War
    [2] https://en.wikipedia.org/wiki/Darwin_(programming_game)
    [3] https://onlinelibrary.wiley.com/doi/abs/10.1002/spe.43800701...
    [4] https://onlinelibrary.wiley.com/doi/abs/10.1002/spe.43800701...
    [5] https://onlinelibrary.wiley.com/doi/abs/10.1002/spe.43801909...

  • Ich hatte einen Freund, der Spiele mochte, aber meinte, er habe keinen Kopf fürs Coden. Durch Human Resource Machine hat er im Grunde doch programmiert, und einige seiner Lösungen waren besser als meine nach mehreren Jahren Erfahrung.

    • Manchmal hilft eine neue Perspektive viel mehr, als man denkt.
      Mein 12-jähriges Kind hasst Mathe, ist aber erstaunlich gut in Human Resource Machine und SpaceChem. Da fragt man sich, ob Schulmathematik und die Mathematik des Programmierens grundlegend verschieden sind.

  • Sehr interessant. Angesichts heutiger Speichergrößen bei Computern habe ich kurze Mnemonics immer als technisch schlechte Entscheidung empfunden.
    Auch hier ist das Erste, was man tun muss, zu lernen und sich zu merken, was die Instruktionen machen. Wenn man die Namen in ausgeschriebenere Formen ändert, werden Lernen, Merken und Lesen des Codes viel einfacher. Dass Leute das nicht häufiger tun, macht mich misstrauisch.
    Auch die Tatsache, dass diese Art von Schwachstelle möglich ist, deutet für mich auf ein Versagen des Gesamtsystemdesigns hin. Das heißt nicht, dass es kein unterhaltsames Spiel oder keine gute Art zu lernen wäre, aber im Engineering werden strukturelle Probleme viel zu leicht akzeptiert. Die meisten sehen diesen strukturellen Fehler nicht einmal.

    • In der ersten Version gab es einen deutlich besser lesbaren Pseudo-Assembler, und ich habe auch über diese Richtung nachgedacht. Am Ende wollte ich aber, dass meine Tochter die objdump-Ausgabe bequem lesen kann, und ich sehe es nicht als großes Problem, ein paar Mnemonics zu lernen.
      Ich glaube, Kinder reagieren wirklich gut, wenn man sie nicht unterschätzt. Zumindest war das bei meinem Kind so.
      Glaubst du, es gibt jemanden, der beliebiges Lesen und Schreiben nicht als strukturellen Fehler betrachtet? Tausende arbeiten an diesem Problem und haben schon einiges erreicht. Gleichzeitig finde ich peek und poke immer noch spaßig.

  • Das ist wirklich cool. Würde ich gern in der Firma ausprobieren.

  • Sieht ziemlich interessant aus. Für welche Altersgruppe würdest du es empfehlen?

    • Die einfache Siegbedingung, also per schnellem Buffer Overflow in bug() aus der Hauptschleife auszubrechen, können meiner Meinung nach auch 10- bis 15-Jährige schaffen.
      Meine Tochter ist 12, und wir haben zusammen Spaß daran. Die schwierige Siegbedingung, also den Gegner dazu zu bringen, in die Funktion game_over() zu springen, ist schwerer, aber ich denke, wir können sie innerhalb von 5–6 Monaten erreichen.
      Bei Erwachsenen bin ich mir nicht sicher. Manche haben vor Assembler Angst, als wäre er vom Teufel, und es könnte schwieriger sein, sie zum Spielen zu bringen als Kinder.

  • Interessant ist, dass wir dazu neigen, die Welt als Spiegel unserer selbst zu sehen.
    Wie wahrscheinlich ist es, dass meine Tochter selbstverständlich ebenfalls großes Interesse daran hat, nur weil ich mich für Buffer Overflows und Programmierung interessiere? Wenn es das erste Kind ist und das zweite eine Tochter, scheint die Wahrscheinlichkeit noch geringer, und trotzdem sehe ich viele Väter, die das durchziehen.
    Bei solchen Projekten frage ich mich, ob man sich zumindest teilweise bewusst ist, dass es ein Eitelkeitsprojekt ist. Wie auch immer: Ich interessiere mich für so etwas, daher freue ich mich, dass es veröffentlicht wurde.

    • Noch interessanter ist, wie selbstverständlich Menschen riesige Annahmen treffen, um ihre eigene These plausibel wirken zu lassen.
      Du deutest an, der Projektersteller zwinge seiner Tochter das aus eigener Eitelkeit auf – wo ist die Grundlage dafür? Ich habe mir ein paar Seiten der Website angesehen und nichts gefunden, was darauf hindeutet; im Gegenteil gab es mehrfach sanfte Formulierungen, dass die Tochter Spaß daran hat und sehr interessiert ist.
      Warum schließt du aus, dass es damit begann, dass die Tochter ständig neugierig war, was ihr Vater am Computer macht? Es könnte klein angefangen haben und sich dann zu einem beidseitigen Prozess zwischen jemandem, der sein Interesse teilt, und einer jungen Mitentdeckerin entwickelt haben.
      Wie es tatsächlich ist, weiß ich nicht, aber du weißt es auch nicht. Aus ein paar Jahren Erfahrung im Bildungsbereich kann ich sagen, dass Kinder im Allgemeinen viel bessere Lernende sind, als man gemeinhin glaubt. Die Schulstruktur ist sicher ein Grund, aber im Kern könnten auch solche begrenzenden Überzeugungen stehen. Ich möchte diesem Vater applaudieren, der versucht hat, seine Interessen und seine Leidenschaft mit seiner Tochter und der Welt zu teilen.
    • Als Vater versuche ich nur, alles weiterzugeben, was ich kann. Manchmal ist es Programmieren, manchmal Kampfsport, manchmal Meditation.
      Einiges davon wird wertvoll sein, anderes nicht. Die Chancen stehen immer schlecht. So ist das Leben nun einmal.

  • Wenn der 64-Bit-RISC-V-Codepfad stabilisiert ist, ausreichend gut funktioniert und sogar der „Buffer Overflow“ verschwindet: Wie will man dann geplante Obsoleszenz betreiben, wenn C/C++ nicht ständig die Syntax ändert? Arme Seelen …

  • Moment mal.
    Ein Tabletop-Brettspiel mit Assembler-Coding? Warum bin ich da nicht früher draufgekommen? :D

  • PL/I hat Dinge wie Grenzprüfungen für Strings/Arrays und einen Stack, der nach oben statt nach unten wächst, richtig gemacht.
    https://www.acsac.org/2002/papers/classic-multics.pdf