plaidCTF 2012 –
Supercomputer 1

plaidCTF 2012 - Supercomputer 1 - task description

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“.

Leave a Reply

Your email address will not be published. Required fields are marked *