Potsdam Cyber Games CTF'24

PartyPass

Ziel dieser Aufgabe war es, die Flag aus den SIMD-Instruktionen in einer x86-64-ELF-Datei zurückzurechnen. Dabei ist die Flag das Party-Passwort:

Nachdem du von der geheimen Party in der geheimen Lounge gehört hast, stehst du nun davor. Von innen dröhnt die Musik. Aber hier kommst du nicht weiter: Dir fehlt das Passwort. Kannst du Bowser, den digitalen Bouncer vom Gegenteil überzeugen und dir Zugang zur Party und zum Partyfood verschaffen?

Führen wir das shuffler-Binary aus, werden wir nach einem Passwort gefragt:

$ chmod +x ./shuffler && ./shuffler
I am Bowser, the Bouncer. Show me the party password:
> password?
Nope, that's not right. You should go home. 😡

Wie prüft das Programm aber, welches Passwort gültig ist? Werfen wir einen Blick auf das Binary in einem Disassembler, beispielsweise objdump und fokussieren uns auf call-Instruktionen zu Funktionen der Standardbibliothek glibc:

$ objdump -d shuffler

[...]
Disassembly of section .text:

0000000000001080 <.text>:
    109b:	ff 15 1f 3f 00 00    	call   *0x3f1f(%rip)        # 4fc0 <__cxa_finalize@plt+0x3f50>
    1142:	e8 29 ff ff ff       	call   1070 <__cxa_finalize@plt>
    1147:	e8 64 ff ff ff       	call   10b0 <__cxa_finalize@plt+0x40>
    23cb:	e8 60 ec ff ff       	call   1030 <puts@plt>
    23da:	e8 81 ec ff ff       	call   1060 <aligned_alloc@plt>
    23fa:	e8 41 ec ff ff       	call   1040 <memset@plt>
    2415:	e8 36 ec ff ff       	call   1050 <fgets@plt>
    2429:	e8 02 ec ff ff       	call   1030 <puts@plt>
    2442:	e8 19 ec ff ff       	call   1060 <aligned_alloc@plt>
    2c28:	e8 03 e4 ff ff       	call   1030 <puts@plt>
    2c3e:	e8 ed e3 ff ff       	call   1030 <puts@plt>

Von Interesse ist hier die fgets-Instruktion, mit der wir unser Passwort eingeben:

  23ff:	48 8b 15 ea 2c 00 00 	mov    0x2cea(%rip),%rdx        # 50f0 <stdin@GLIBC_2.2.5>
  2406:	48 8b 85 08 ff ff ff 	mov    -0xf8(%rbp),%rax
  240d:	be 31 00 00 00       	mov    $0x31,%esi
  2412:	48 89 c7             	mov    %rax,%rdi
  2415:	e8 36 ec ff ff       	call   1050 <fgets@plt>

Wie wir sehen können, nimmt fgets(char *str, int n, FILE *stream) drei Parameter in %rax, %esi und %rdx entgegen, fgets liest also 48 Bytes in einen Buffer auf dem Stack an Position -0xf8 ein: fgets(-0xf8(%rbp), 49, stdin). Derselbe Buffer wurde vorher mit aligned_alloc alloziiert und mit memset genullt.

Verfolgen wir die Verwendung des Buffers im Binary, so lässt sich erkennen, dass der Buffer in drei 16-Byte Blöcke geteilt wird, die jeweils in ein 128-Bit SSE-Vektorregister geladen werden. Diese Blöcke werden mit einer Vielzahl an umkehrbaren mathematischen SSE-Instruktionen und jeweils einer vergleichenden Operation transformiert und letztendlich in einen zweiten alloziierten Buffer von 48 Byte Länge geschrieben. Auf diesem wird in einer Schleife popcnt aggregiert, also alle gesetzten Bits summiert. Wenn dieser Wert 384 entspricht - also alle Bits gesetzt sind wird uns die korrekte Nachricht >That's right. Let the party begin!< ausgegeben.

Um das korrekte Passwort zu bestimmen müssen wir also einen genaueren Blick auf die SIMD-Operationen für jeden der Teilblöcke werfen und erreichen, dass die in den Output-Buffer geschriebenen Bits alle gesetzt sind. Um den Datenfluss zu verfolgen, bietet es sich an, das Binary in z.B. Ghidra zu laden und die Speicheradressen für die Load- und Store-Operationen zu den jeweiligen %xmm-Registern vor relevanten Operationen zu benennen.

Block I

Die SSE-Instruktionen im ersten Block entsprechen den folgenden Intrinsics:

// 24de: punpcklbw %xmm0,%xmm1
// 2514: psubb %xmm1,%xmm0
// 254a: pxor %xmm1,%xmm0
// 2583: pcmpeqw %xmm1,%xmm0

__m128i op1 = _mm_unpacklo_epi8(c2, c3);
__m128i op2 = _mm_sub_epi8(op1, c1);
__m128i op3 = _mm_xor_si128(op2, c4);
__m128i test1 = _mm_cmpeq_epi16(in1, op3);

_mm_storeh_pd((double *)out, (__m128d)test1);
_mm_storel_pd((double *)(out + 8), (__m128d)test1);

Im ersten Block sind die ersten 2x8 Bytes des Ausgabe-Buffers das Ergebnis eines 8x16-Bit-Vergleiches zwischen den ersten 16 Bytes der Eingabe und dem Ergebnis einer Sequenz an SIMD-Operationen. Wir müssen also die ersten 16 Bytes genau auf diesen Wert setzen. Der Wert bestimmt sich aus vier Konstanten C1-C4, die in dem Ausdruck IN1 = (((C2 unpacklo8 C3) sub8 C1) xor C4) miteinander verbunden sind.

Wenn wir die relevanten Konstanten aus der Prelude der Funktion extrahieren (Byte-Order beachten!), können wir also beispielsweise mit Python und numpy die korrekte Eingabe berechnen:

import numpy as np

c1 = np.array([0xe9,0x3e,0x44,0xbc,0x2d,0x4e,0x6e,0xb9,0x3a,0xe,0x17,0x26,0xec,0x1f,0x56,0xe], dtype=np.uint8)
c2 = np.array([0xf7,0xf1,0x96,0xa0,0xe3,0xe,0x48,0x6b,0x95,0xcc,0x9c,0x94,0x3,0xc3,0x56,0xff], dtype=np.uint8)
c3 = np.array([0xeb,0x89,0x8c,0xbe,0xc0,0xb5,0x4f,0x6,0x8e,0x46,0x49,0xfa,0x2f,0x25,0x10,0x83], dtype=np.uint8)
c4 = np.array([0x5e,0xee,0xea,0xb6,0x19,0xa,0x40,0x71,0xd0,0x9f,0x91,0xbf,0x6c,0x54,0x38,0x96], dtype=np.uint8)

def unpacklo8(vec1, vec2):
  return np.ravel(np.column_stack(((vec1[0:8], vec2[0:8]))))

in1 = (unpacklo8(c2, c3) - c1) ^ c4

Block II

__m128i all_bits = _mm_set1_epi8(0xff);

// 2875: pandn -0x4e0(%rbp),%xmm0
// 28b3: pmuludq %xmm1,%xmm0
// 28ed: psubb %xmm1,%xmm0
// 2921: psllw %xmm0,%xmm1
// 295e: pxor %xmm1,%xmm0
// 2997: pxor %xmm1,%xmm0
// 29d0: pxor %xmm1,%xmm0
// 2a09: pcmpeqb %xmm1,%xmm0

__m128i neg_in2 = _mm_andnot_si128(in2, all_bits);
__m128i op4 = _mm_mul_epu32(c5, c5);
__m128i op5 = _mm_sub_epi8(c6, c8);
__m128i op6 = _mm_slli_epi16(op5, 2);
__m128i op8 = _mm_xor_si128(op4, op6);
__m128i op10 = _mm_xor_si128(op8, c7);
__m128i op11 = _mm_xor_si128(op10, neg_in2);
__m128i test2 = _mm_cmpeq_epi8(op11, all_bits);

_mm_storeh_pd((double *)(out + 16), (__m128d)test2);
_mm_storel_pd((double *)(out + 24), (__m128d)test2);

Im zweiten Block sind die nächsten 2x8 Bytes des Ausgabe-Buffers das Ergebnis eines eines 16x8-Bit-Vergleichs zwischen einem Vektor in dem alle Bits gesetzt sind und dem Ergebnis der Sequenz an SIMD-Operationen. Folglich müssen wir den dahinterlegenden Ausdruck so umstellen, dass in ihm alle Bits gesetzt sind. Auch hier bestimmt sich der Ausdruck aus Konstanten, diesmal C5-C8: TRUE = ((!IN2 and TRUE) xor (((C5 mul32 C5) xor ((C6 sub8 C8) slli16 2)) xor C7))). Diesen Ausdruck können wir umstellen um die nächsten 16 Byte der Eingabe zu erhalten: IN2 = (C5 mul32 C5) xor ((C6 sub8 C8) slli16 2)) xor C7. Auch hier lässt sich die Lösung mit einem kleinen Skript bestimmen:

c5 = np.array([0x79,0x28,0xde,0x33,0xd0,0xa,0xd8,0xed,0x7f,0xf7,0xd6,0xb0,0x8c,0x9,0x13,0x1b], dtype=np.uint8)
c6 = np.array([0xf9,0x18,0xa4,0x0,0x99,0x38,0x1d,0xd2,0x70,0xd7,0x7,0x5d,0x5,0xc0,0xe5,0xb7], dtype=np.uint8)
c7 = np.array([0x6c,0x2e,0xe8,0x7a,0xf0,0x80,0xb9,0xdf,0xf,0x98,0x7c,0x4a,0xa7,0x1,0xe7,0x45], dtype=np.uint8)
c8 = np.array([0x1d,0x8,0x2e,0xb7,0xbc,0xcd,0xb,0x94,0xde,0xee,0xe2,0x11,0x41,0xb2,0xa6,0xb4], dtype=np.uint8)

def mul32(vec1, vec2):
  a = vec1.view(np.uint32)
  b = vec2.view(np.uint32)
  return np.array([(int(a[0]) * int(b[0])), (int(a[2]) * int(b[2]))], dtype=np.uint64).view(np.uint8)

def slli16(vec, shift):
  return np.left_shift(vec.view(np.uint16), shift).view(np.uint8)

in2 = mul32(c5, c5) ^ slli16(c6 - c8, 2) ^ c7

Block III

// 2ab3: pabsb %xmm0,%xmm0
// 2ae5: pandn -0x3a0(%rbp),%xmm0
// 2b23: paddb %xmm1,%xmm0
// 2b5c: paddb %xmm1,%xmm0
// 2b95: pcmpeqb %xmm1,%xmm0

__m128i op12 = _mm_abs_epi8(c9);
__m128i op13 = _mm_andnot_si128(op12, c10);
__m128i op14 = _mm_add_epi8(op13, in3);
__m128i op15 = _mm_add_epi8(op14, c11);
__m128i test3 = _mm_cmpeq_epi8(op15, all_bits);

_mm_store_si128((__m128i *)(out + 32), test3);

Im dritten Block ergibt sich die Berechnung der nächsten 16 Byte des Ausgabe-Buffers erneut aus einem 16x8-Bit-Vergleich zwischen dem Vektor mit allen gesetzten Bits und einer Sequenz an SIMD-Operationen. Diesmal entspricht der Ausdruck TRUE = (((!abs8(C9) and C10) add8 IN3) add8 C11). Auch dieser Ausdruck lässt sich zur nötigen Eingabe umstellen: IN3 = ZERO sub8 ((!abs8(C9) and C10) add8 C11 sub8 TRUE).

c9 = np.array([0x37,0x71,0x71,0x87,0x1c,0x9d,0xe,0x12,0x6d,0xac,0xc3,0xcc,0x30,0xf6,0x5e,0x36], dtype=np.uint8)
c10 = np.array([0xc9,0x18,0x18,0xf6,0xdd,0xa8,0x6a,0x50,0x25,0x12,0xcc,0xeb,0x8d,0x39,0x74,0x28], dtype=np.uint8)
c11 = np.array([0xfd,0xbd,0xaa,0x1f,0xb,0x45,0x4f,0x60,0x8a,0x94,0xcb,0xcd,0x40,0x74,0x62,0xd7], dtype=np.uint8)

all_bits = np.array([0xff for x in range(0, 16], dtype=np.uint8)
in3 = -((np.invert(np.abs(c9)) & c10) + c11 - all_bits)

flag = ''
for chunk in [in1, in2, in3]:
  for c in chunk:
    flag += chr(int(c))
print(flag)

Entlassene Admins

Ziel dieser Aufgabe war es, eine versteckte Funktion in einer minimalen x86-64-ELF-Datei mit Anti-Debugging-Eigenschaften zu finden und auszuführen, sowie die nach der ELF-Datei angefügte Keepass-Datei zu öffnen. Einen kleinen Hinweis darauf erhalten wir auch schon in der Beschreibung:

[...] Da geht es schon los! Passwörter sind nun natürlich auch mit dem ganzen Know-How verschwunden. Gefunden wurde aber eine unbekannte, ausführbare Datei. Sieht auf den ersten Blick nicht wirklich nützlich aus, oder?

Flag I: Anti-Debug Binary

Führt man das Binary auf einem x86-64 Linux-System aus, gibt dieses eine Nachricht aus und beendet sich anschließend selbst:

$ ./passwords
No passwords here... ;)

Um mehr Informationen zu erhalten, könnten wir versuchen das Programm disassemblieren:

$ objdump -d ./passwords
objdump: ./passwords: file format not recognized

// Loadable segment  [0x28000 - 0x281a8]
// ram:00028000-ram:000281a8
[...]
00028000 7f              db        7Fh                     e_ident_magi
00028001 45 4c 46        ds        "ELF"                   e_ident_magi
00028004 02              db        2h                      e_ident_class
00028005 01              db        1h                      e_ident_data
00028006 01              db        1h                      e_ident_vers
00028007 c7              db        C7h                     e_ident_osabi
00028008 45              db        45h                     e_ident_abiv
00028009 fc 2b ef 32 95  db[7]                             e_ident_pad
         eb 18
00028010 02 00           dw        2h                      e_type
00028012 3e 00           dw        3Eh                     e_machine
00028014 01 00 00 00     ddw       1h                      e_version
00028018 82 80 02 00 00  dq        entry                   e_entry
         00 00 00
00028020 3a 00 00 00 00  dq        Elf64_Ehdr_00028000.e_  e_phoff
         00 00 00
00028028 c7 45 f8 0c fc  dq        EB21FFFC0CF845C7h       e_shoff
         ff 21 eb
00028030 63 90 90 90     ddw       90909063h               e_flags
00028034 40 00           dw        40h                     e_ehsize
00028036 38 00           dw        38h                     e_phentsize
00028038 01 00           dw        1h                      e_phnum
0002803a 01 00           dw        1h                      e_shentsize
0002803c 00 00           dw        0h                      e_shnum
0002803e 05 00           dw        5h                      e_shstrndx
[...]

Zunächst informiert uns Ghidra, dass nur ein Teil der Datei - die ersten 424 Bytes - als einziges Segment in den Speicher an der Adresse 0x28000 geladen wird. Wir werden uns den Rest später noch einmal im Detail ansehen.

Anschließend folgt der Header der ELF-Datei. Während die meisten Felder für die Architektur passend gefüllt sind, sind (1) die OS-ABI, die ABI-Version und die Padding-Bytes auf ungültige Werte gesetzt und (2) zeigt der Section Table Offset, die Flags und alle Section Table-bezogenen Felder auf ungültige Werte. Sehen wir uns also die nächsten Bytes an:

FUN_00028052():
00028052 0f 05           SYSCALL
00028054 b0 3c           MOV        AL,0x3c
00028056 31 ff           XOR        EDI,EDI
00028058 0f 05           SYSCALL
[...]

entry():
00028082 31 c0           XOR        EAX,EAX
00028084 ff c0           INC        EAX
00028086 89 c7           MOV        EDI,EAX
00028088 be 6a 80        MOV        ESI,0x2806a
         02 00
0002808d 31 d2           XOR        EDX,EDX
0002808f b2 18           MOV        DL,0x18
00028091 eb bf           JMP        FUN_00028052

Folgt man dem Programmablauf, so sehen wir, dass im Entrypoint %eax = 1, %edi = 1, %esi = 0x2806a, %edx = 0 und %dl = 0x18 gesetzt werden und im Anschluss am Offset 00028052 mit einem SYSCALL fortgefahren wird. 00028052 gehört eigentlich noch zum Padding nach dem ELF-Header. Entsprechend der x86-64 Calling Conventions für Linux wird die Syscall-Nummer in %rax und die Syscall-Parameter in %rdi, %rsi und %rdx gesetzt werden.

In der x86-64-Architektur werden dieselben Register mit unterschiedlichen Größen unterschiedlich benannt. Die Zuweisungen an die Register aus dem Entrypoint entsprechen also Zuweisungen der geringerwertigen Bytes entsprechend der Register-Mappings für 32-Bit-Namen: %eax = %eax, %edi = %rdi, %esi = %rsi, %edx = rdx. Das 8-Bit %dl-Register entspricht dem unteren Byte von %rdx. Mithilfe einer Syscall-Tabelle für Linux lässt sich daraus schließen, dass hier der Syscall sys_write(1, 0x2806a, 0x18) ausgeführt wird. An der Adresse 0x2806a finden wir den String, mit welchem wir vom Binary begrüßt wurden. Das Handle 1 ist dabei nach Linux-Konvention die Standardausgabe stdout. Der darauf folgende Syscall 60 (sys_exit) beendet das Program. Was ist also mit dem Rest der Speicherregion?

Beim Blick durch die dekompilierbaren Abschnitte, dürfte dieser Abschnitt ins Auge fallen, welcher zwar nicht als Funktion erkannt wird, aber scheinbar Wörter in ein Stack Frame lädt, in einer entrollten Schleife byteweise ge-xored und in einen Buffer schreibt. Anschließend setzt der Code - analog zum Entrypoint - die Parameter für den sys_write-Syscall und springt in dieselbe Funktion um den Buffer auszugeben:

000280e1 c7              ??         C7h

LAB_000280e2:
000280e2 45 c8 0b        ENTER      0x30b,0x16
         03 d6
000280e7 ed              IN         EAX,DX
000280e8 c7 45 c4        MOV        dword ptr [RBP + -0x3c],0xc17f2747
         47 27 7f c1
000280ef c7 45 c0        MOV        dword ptr [RBP + -0x40],0xaa952214
         14 22 95 aa
000280f6 eb 0d           JMP        LAB_00028105

[...]

LAB_00028105:
00028105 48 c7 45        MOV        qword ptr [RBP + -0x70],0x0
         90 00 00
         00 00
0002810d 48 c7 45        MOV        qword ptr [RBP + -0x68],0x0
         98 00 00
         00 00

[... usw ...]

00028125 c6 45 b0 0a     MOV        byte ptr [RBP + -0x50],0xa
00028129 8b 45 fc        MOV        EAX,dword ptr [RBP + -0x4]
0002812c 89 c2           MOV        EDX,EAX
0002812e 8b 45 dc        MOV        EAX,dword ptr [RBP + -0x24]
00028131 31 d0           XOR        EAX,EDX
00028133 89 45 90        MOV        dword ptr [RBP + -0x70],EAX
00028136 8b 45 f8        MOV        EAX,dword ptr [RBP + -0x8]
00028139 89 c2           MOV        EDX,EAX
0002813b 8b 45 d8        MOV        EAX,dword ptr [RBP + -0x28]
0002813e 31 d0           XOR        EAX,EDX

[... usw ...]

00028191 48 8d 75 90     LEA        RSI,[RBP + -0x70]
00028195 ba 21 00        MOV        EDX,0x21
         00 00
0002819a b8 01 00        MOV        EAX,0x1
         00 00
0002819f bf 01 00        MOV        EDI,0x1
         00 00
000281a4 e9 a9 fe        JMP        FUN_00028052
         ff ff

Der Code bildet also eine Art von Entschlüsselungsfunktion für einen geheimen String - aber offensichtlich wird nur ein kleiner Teil der Bytes auf dem Stack geschrieben. Alle MOV dword ptr [RBP + X], Y-Instruktionen haben allerdings eine ähnliche Kodierung, bei der sich die Addresse relativ zum RBP in der Bytefolge c7 45 manifestiert. Diese findet sich an vielen Stellen im Programm, unter anderem direkt vor der falsch erkannten ENTER-Instruktion und an verschiedenen Stellen im Header.

Entfernt man die automatischen Analyseergebnisse von Ghidra (C) und disassembliert (D) den Abschnitt mit einem Byte Offset nach dem Jump manuell entdeckt Ghidra die tatsächlichen Instruktionen. Der tatsächliche Entrypoint findet sich dann durch die Operationen zur Stack-Allokation:

000280f9 48 89 e5        MOV        RBP,RSP
000280fc 48 83 ec 70     SUB        RSP,0x70
00028100 e9 02 ff        JMP        Elf64_Ehdr_00028000.field5_0x7
         ff ff

Wenn wir also den Entrypoint auf unsere Adresse (0x0280f9) patchen, wird - mit einigen Jumps quer durch das Binary und den ELF-Header - der vollständige Schlüssel geladen und die Flag ausgegeben:

$ cp passwords passwords_patched
$ printf "\xf9\x80\x02" > patch
$ dd if=patch of=passwords_patched obs=1 seek=24 conv=notrunc
$ chmod +x passwords_patched && ./passwords_patched
PCG{E-l-f-he4d3r::fAn1NJHpvRX3}

Flag II: Keepass

Uns ist am Anfang aufgefallen, dass das Memory Segment der ELF-Datei nur eine Länge von 424 Bytes hat, die Datei aber deutlich größer ist. Schneiden wir die ersten 425 Bytes von der Datei ab erhalten wir eine neue Datei:

$ tail -c +425 passwords > passwords2
$ file passwords2
passwords2: dBase III DBT, version number 0, next free block index 255
$ hexdump passwords2
0000000 00ff 0000 0000 0000 0000 0000 0000 0000
0000010 0000 0000 0000 0000 0000 0000 0000 0000
*
0000050 0000 0000 0000 0000 d903 9aa2 fb67 b54b
[...]

$ tail -c +89 passwords2 > passwords3
$ file passwords3
passwords3: Keepass password database 2.x KDBX

Danksagung

Vielen Dank an Felix Gohla für die Aufgabenbeschreibungen und die Keepass-Erweiterung.