Bei dieser Challenge (Supercomputer 1) wird uns ein Programm zur Verfügung gestellt, dass angeblich vier riesige Zahlen berechnen soll. Um die Aufgabe zu lösen, müssen wir an die erste Zahl gelangen.
Bei der Software handelt es sich um ein 64bit-Linux-Binary mit einer Größe von circa 10 Kilobytes. Ein erster Testlauf in einer virtuellen Maschine liefert folgende Ausgabe:
rup0rt@linux64:~$ ./supercomputer Calculating the first key......This could take long..........^C
Das Programm lässt sich also ausführen und scheint im Hintergrund irgendetwas zu tun, was eine entsprechend lange Zeit dauert bzw. dauern soll. Ein Blick auf die Prozessorauslastung zeigt jedoch, dass dieser nicht sonderlich beansprucht ist, was eher auf eine Pseudo-Berechnung hindeutet.
Starten wir das Programm einmal mit dem GDB und sehen uns an, in welcher Funktion wir landen, wenn wir die Verarbeitung mit STRG+C abbrechen.
(gdb) r
Starting program: /root/supercomputer
Calculating the first key.....^C
Program received signal SIGINT, Interrupt.
0x00007ffff7b1da00 in nanosleep () from /lib/libc.so.6
Ahja, alles klar! Die Berechnung des Programmes wird künstlich verlangsamt, indem die Funktion “nanosleep()” aufgerufen wird. Um die Berechnung zu beschleunigen werden wir nun quick&dirty die nanosleep-Funktion durch das Einfügen einer Return (RET) Anweisung direkt wieder Beenden lassen. Dazu suchen wir uns zunächst die exakte Adresse heraus.
(gdb) disas nanosleep
Dump of assembler code for function nanosleep:
0x00007ffff7b1d9f0 <nanosleep+0>: cmp DWORD PTR [rip+0x2c0c11],0x0 # 0x7ffff7dde608
0x00007ffff7b1d9f7 <nanosleep+7>: jne 0x7ffff7b1da09 <nanosleep+25>
0x00007ffff7b1d9f9 <nanosleep+9>: mov eax,0x23
Den Vergleich (CMP) ändern wir nun live im GDB auf den Opcode von RET (0xc3).
(gdb) set *(char*)0x00007ffff7b1d9f0=0xc3 (gdb) disas nanosleep Dump of assembler code for function nanosleep: 0x00007ffff7b1d9f0 <nanosleep+0>: ret
Anschließend lassen wir das Programm weiter laufen und stellen fest, dass sich der Programmablauf deutlich beschleunigt hat. Dennoch scheint das Programm auch nun nicht schnell zu einem Ende zu kommen, jedoch ist die CPU-Auslastung diesmal bei 100%. Wir brechen erneut den Programmfluss mit STRG+C ab und sehen uns die Ursache an.
(gdb) c Continuing. ...This could take long..........Too long............................. ............................................................^C Program received signal SIGINT, Interrupt. 0x0000000000400ce9 in ?? () (gdb) x/10i 0x0000000000400ce9-20 0x400cd5: mov eax,DWORD PTR [rbp+0x28] 0x400cd8: add rax,0x1 0x400cdc: mov QWORD PTR [rbp+0x28],rax 0x400ce0: add QWORD PTR [rbp-0x8],0x1 0x400ce5: mov rax,QWORD PTR [rbp-0x8] 0x400ce9: cmp rax,QWORD PTR [rbp-0x20] 0x400ced: jne 0x400cb0 0x400cef: mov rax,QWORD PTR [rbp-0x18] 0x400cf3: mov rdx,QWORD PTR [rbp+0x10] 0x400cf7: mov QWORD PTR [rax],rdx
Scheinbar sind wir in einer Programmschleife gelandet, die wirklich Berechnungen durchführt und somit den Schlüssel zur Challenge ermitteln soll. (Der Versuch auch diese Funktion aus dem Programmfluss heraus zu nehmen, funktioniert übrigens nicht und liefert eine Fehlermeldung bzw. den falschen Schlüssel.)
Um zu einer gültigen Lösung der Challenge zu gelangen bleibt uns also nichts anderes übrig, als uns die Berechnung dieser Schleife genau anzusehen mit dem Ziel, Rechenschritte so weit zu optimieren, dass die Berechnung des Schlüssels in akzeptabler Zeit erfolgt. Sehen wir uns also als nächstes die gesamte Schleife an.
(gdb) x/20i 0x400cb0-10 0x400ca6: mov QWORD PTR [rbp-0x8],0x0 0x400cae: jmp 0x400ce5 0x400cb0: mov rax,QWORD PTR [rbp+0x10] 0x400cb4: add rax,0x1 0x400cb8: mov QWORD PTR [rbp+0x10],rax 0x400cbc: mov rax,QWORD PTR [rbp+0x18] 0x400cc0: add rax,0x1 0x400cc4: mov QWORD PTR [rbp+0x18],rax 0x400cc8: mov rax,QWORD PTR [rbp+0x20] 0x400ccc: add rax,0x1 0x400cd0: mov QWORD PTR [rbp+0x20],rax 0x400cd4: mov rax,QWORD PTR [rbp+0x28] 0x400cd8: add rax,0x1 0x400cdc: mov QWORD PTR [rbp+0x28],rax 0x400ce0: add QWORD PTR [rbp-0x8],0x1 0x400ce5: mov rax,QWORD PTR [rbp-0x8] 0x400ce9: cmp rax,QWORD PTR [rbp-0x20] 0x400ced: jne 0x400cb0 0x400cef: mov rax,QWORD PTR [rbp-0x18] 0x400cf3: mov rdx,QWORD PTR [rbp+0x10]
Die Schleife scheint sich mit vier Variablen zu beschäftigen, die an den Positionen $RBP-0x10, $RBP-0x18, $RBP-0x20 und $RBP-0x28 im Speicher liegen. Pro Schleifendurchlauf werden diese Variablen um Eins erhöht, so lange bis der Schleifenzähler ($RBP-0x8) gleich dem Wert [$RBP-x20] ist. In Zeile 0x400ca6 sehen wir zusätzlich, dass der Schleifenzähler mit Null initialisiert wird. Als Pseudocode würde diese Schleife dann wie folgt aussehen:
for (i=0; i!=[$RBP-0x20]; i++) {
[$RBP+0x10]++;
[$RBP+0x18]++;
[$RBP+0x20]++;
[$RBP+0x28]++;
}
Die Optimierung dieses Quellcodes erscheint relativ simpel. Anstatt [$RBP-0x20] mal auf jeden Wert Eins zu addieren, addieren wir einmalig [$RBP-0x20]. Der Code sollte dann so hier aussehen:
[$RBP+0x10] += [$RBP-0x20]; [$RBP+0x18] += [$RBP-0x20]; [$RBP+0x20] += [$RBP-0x20]; [$RBP+0x28] += [$RBP-0x20];
Ein entsprechend angepasster Assembler Code, wäre dann zum Beispiel:
BITS 64 mov rax, [rbp+0x10] add rax, [rbp-0x20] mov [rbp+0x10],rax mov rax, [rbp+0x18] add rax, [rbp-0x20] mov [rbp+0x18],rax mov rax, [rbp+0x20] add rax, [rbp-0x20] mov [rbp+0x20],rax mov rax, [rbp+0x28] add rax, [rbp-0x20] mov [rbp+0x28],rax
Compiliert man diesen Code nun mit dem Werkzeug “nasm” erhält man folgende Bytes als Opcode unserer neuen Berechnungsfunktion:
rup0rt@linux64:~$ nasm supercomputer1.asm rup0rt@linux64:~$ xxd -E -c4 -g4 supercomputer1 0000000: 488b4510 .... 0000004: 480345e0 ...\ 0000008: 48894510 .i.. 000000c: 488b4518 .... 0000010: 480345e0 ...\ 0000014: 48894518 .i.. 0000018: 488b4520 .... 000001c: 480345e0 ...\ 0000020: 48894520 .i.. 0000024: 488b4528 .... 0000028: 480345e0 ...\ 000002c: 48894528 .i..
Diese Bytes schreiben wir nun ab der Position 0x400cae und löschen die restlichen Operationen bis einschließlich Position 0x400cee, indem wir den Bereich mit “no operation” (NOP == 0x90) auffüllen. Da wir zur Zeit jedoch in der Schleife selbst angehalten haben, müssen wir diese vor dem Ändern per Breakpoint wieder verlassen. Anschließend führen wir die folgenden Kommandos im GDB aus, um das Überschreiben durchzuführen:
set *(int*)0x400cae=0x10458b48 set *(int*)0x400cb2=0xe0450348 set *(int*)0x400cb6=0x10458948 set *(int*)0x400cba=0x18458b48 set *(int*)0x400cbe=0xe0450348 set *(int*)0x400cc2=0x18458948 set *(int*)0x400cc6=0x20458b48 set *(int*)0x400cca=0xe0450348 set *(int*)0x400cce=0x20458948 set *(int*)0x400cd2=0x28458b48 set *(int*)0x400cd6=0xe0450348 set *(int*)0x400cda=0x28458948 set *(int*)0x400cde=0x90909090 set *(int*)0x400ce2=0x90909090 set *(int*)0x400ce6=0x90909090 set *(int*)0x400cea=0x90909090 set *(char*)0x400cee=0x90
Nun haben wir die Schleife optimiert und setzen den Programmablauf fort.
(gdb) c
.....................................................................
[...]
.....................................................................
................................................................
Yay! The first key is 414e0d423f5fcd195a579f95f1ff6525
Unsere Optimierung war scheinbar erfolgreich und hat uns den Schlüssel innerhalb weniger Sekunden berechnet! Das Schreiben einen Patches um die Änderungen am Programm persistent durchzuführen überspringe ich an dieser Stelle.
Die Lösung lautet also “414e0d423f5fcd195a579f95f1ff6525“.