Boston Key Party CTF 2013 – randy

Boston Key Party CTF 2013 - randy - task description

Bei der Challenge “randy” wird uns eine Binärdatei bereit gestellt und auf “Zufälligkeit” hingeweisen. Nach dem Download starten wir das Programm direkt um dessen Funktionalität zu beobachten.

root@linux64:~# ./randy
Password: rup0rt
:(

Das Binary verlangt nach der Eingabe eines Passwortes. Bei Eingabe einer beliebigen (falschen) Zeichenfolge erhalten wir nur ein trauriges Smiley. Um zu erfahren, wie das Programm das Passwort verarbeitet und die Korrektheit bestimmt, nutzen wir objdump um den Assembler-Code zu erzeugen.

Darin fingen wir unter anderem folgende Abschnitte:

0000000000400884 <main>:
[...]
  400958:  e8 c3 fc ff ff  call   400620 <strlen@plt>
  40095d:  48 83 f8 1c     cmp    rax,0x1c
[...]
  400983:  b8 00 00 00 00  mov    eax,0x0
  400988:  e8 97 fe ff ff  call   400824 <wrong>

Zunächst wird die Funktion strlen() aufgerufen um die Länge des von uns eingegebenen Passwortes zu bestimmen. Anschließend wird das Ergebnis mit 0x1c (28) verglichen und bei Misserfolg, das Programm mit der <wrong> Funktion beendet. Wir wissen also, dass das Passwort 28 Zeichen lang sein muss.

Nachdem das Passwört die Längenprüfung bestanden hat, wir die Funktion <keygen> aufgerufen, die folgendermaßen aussieht:

0000000000400a20 <keygen>:
  400a20:  49 bc 00 00 00 00 00  movabs r12,0x0
  400a2a:  49 89 fd              mov    r13,rdi

0000000000400a2d <do_1>:
  400a2d:  4b 8b 44 a5 00        mov    rax,QWORD PTR [r13+r12*4+0x0]
  400a32:  48 89 c7              mov    rdi,rax
  400a35:  e8 d6 fb ff ff        call   400610 <srandom@plt>
  400a3a:  e8 51 fc ff ff        call   400690 <random@plt>
  400a3f:  48 3d 7a 83 58 73     cmp    rax,0x7358837a
  400a45:  0f 85 19 02 00 00     jne    400c64 <bad>
  400a4b:  e8 40 fc ff ff        call   400690 <random@plt>
  400a50:  48 3d 58 26 1b 6e     cmp    rax,0x6e1b2658
  400a56:  0f 85 08 02 00 00     jne    400c64 <bad>
  400a5c:  e8 2f fc ff ff        call   400690 <random@plt>
  400a61:  48 3d ff c5 00 3c     cmp    rax,0x3c00c5ff
  400a67:  0f 85 f7 01 00 00     jne    400c64 <bad>
  400a6d:  e8 1e fc ff ff        call   400690 <random@plt>
  400a72:  48 3d aa d4 c0 08     cmp    rax,0x8c0d4aa
  400a78:  0f 85 e6 01 00 00     jne    400c64 <bad>
  400a7e:  49 ff c4              inc    r12

Die Funktion <keygen> schriebt unser Passwort in das Register R13 und geht dann direkt in die Funktion <do_1> über. Hier werden die ersten 4 Bytes des Passwortes in RAX eingelesen (Adresse 0x400a2d) und anschließend an die Funktion srandom() übergeben.

srandom() setzt damit den Seed des Zufallszahlengenerators und bestimmt somit die Sequenz von Zufallszahlen, die beim Aufruf der Funktion random() entstehen. Ein gleicher Seed auf unterschiedlichen Systemen führt dabei zu gleichen Zufallszahlen. Das Programm prüft ob unser Passwort als Seed die im Assembler-Code hinterlegten Zufallszahlen erzeugt.

Diese sind für die ersten vier Bytes des Passwortes:

  • 0x7358837a (Adresse 0x400a3f)
  • 0x6e1b2658 (Adresse 0x400a50)
  • 0x3c00c5ff (Adresse 0x400a61)
  • 0x8c0d4aa (Adresse 0x400a72)

Mit einem Brute Force über alle durckbaren Zeichen eines 4-Byte-Passwortes sollte sich damnach die korrekte Zeichenkette für den Seed bestimmen lassen. Dies realisiert folgendes C-Programm:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main() {

  unsigned long check;
  unsigned int rand;

  // start with four spaces
  check = 0x20202020;

  for (;;check++) {

    // ascii increment
    if ((check%256)==128) check+=160;

    srandom(check);

    rand = random();

    if (rand == 0x7358837a) {
      rand = random();
      if (rand == 0x6e1b2658) {
        rand = random();
        if (rand == 0x3c00c5ff) {
          rand = random();
          if (rand == 0x8c0d4aa) {
            printf("PART1: %lu!\n", check);
          }
        }
      }
    }

  }

}

Da es noch sieben weitere do_ Funktionen gibt, müsste man dieses Programm für jeden 4-Byte-Block des Passwortes neu erstellen. Um den Prozess zu beschleunigen und alle Blöcke zeitgleich zu berechnen, nehmen wir vor Ausführung daher noch einige Änderungen vor.

Zunächst sollte es genügen (und Zeit sparen) nur jeweils die erste Überprüfung der random()-Funktion zu entnehmen, da es unwahrscheinlich ist, sehr oft die gleichen Zufallszahlen zu erhalten. Nun extrahieren wir aus allen do_ Funktionen die Vergleiche und lassen alle Blöcke mit folgendem C-Programm prüfen:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main() {

  unsigned long check;
  unsigned int rand;

  // start with four spaces
  check = 0x20202020;

  for (;;check++) {

    // ascii increment
    if ((check%256)==128) check+=160;

    srandom(check);

    rand = random();

    if (rand == 0x7358837a) printf("PART1: %lu!\n", check);
    if (rand == 0x34d8c3b5) printf("PART2: %lu!\n", check);
    if (rand == 0x1f49456c) printf("PART3: %lu!\n", check);
    if (rand == 0x1fea6614) printf("PART4: %lu!\n", check);
    if (rand == 0x4e81abc7) printf("PART5: %lu!\n", check);
    if (rand == 0x683d3f5d) printf("PART6: %lu!\n", check);
    if (rand == 0x28c9a8fe) printf("PART7: %lu!\n", check);

  }

}

Nachdem wir dieses Programm kompiliert und gestartet haben, erhalten wir diese Ausgabe:

root@linux64:~# ./randycrack
PART1: 544485486!
PART7: 555819297!
PART4: 639600210!
PART3: 811888180!
PART6: 825319712!
PART4: 874524781!
PART6: 1899109733!
PART2: 1914712179!
PART5: 1915974758!

Diese Werte müssen nun nur noch in hexadezimale Schreibweise und anschließend in ASCII-Zeichen umgewandelt werden.

PART1: 544485486!   ==  0x2074306e  ==  "n0t "
PART2: 1914712179!  ==  0x72203073  ==  "s0 r"
PART3: 811888180!   ==  0x30646e34  ==  "4nd0"
PART4: 874524781!   ==  0x3420306d  ==  "m0 4"
PART5: 1915974758!  ==  0x72337466  ==  "ft3r"
PART6: 825319712!   ==  0x31316120  ==  " a11"
PART7: 555819297!   ==  0x21212121  ==  "!!!!"

PART4: 639600210!   ==  0x261f8652  ==  (no ascii) -> FALSE POSITIVE
PART6: 1899109733!  ==  0x71321d65  ==  (no ascii) -> FALSE POSITIVE

Bis auf zwei “False Positives”, die nicht druckbare Zeichen enthalten, konnte für jeden Zufallswert ein Seed in Form eines Passwortanteils gefunden werden! Diese müssen nun nur noch zusammen gesetzt werden.

Die Lösung lautet somit “n0t s0 r4nd0m0 4ft3r a11!!!!“.

Leave a Reply

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