Pandora 2012, Bonuspuzzel 1: Brainfuck

Bij het einde van dag 1 was er een bonuspuzzel: download de file van http://www.iapandora.nl/brainfuck.zip (kopie: brainfuck.zip) en zoek de rest maar uit. Zoals te verwachten viel zat er in de zip een bestand met brainfuck-code, een interpreter voor windows en een README. Dit laatste bestand gaf aan dat je bij de meegeleverde interpreter een bepaalde setting voor errors uit moest zetten en dat je mogelijk gibberish kreeg aangezien het niet allemaal heel netjes gebouwd is. Bij het juiste codewoord als invoer zou er een logische tekst uit komen.

De taal brainfuck is zeer beperkt, er zijn in totaal 8 instructies, en je werkt met een grote geheugenset en een pointer. Je kunt de pointer bewegen, waardes in het geheugen ophogen en verlagen en while-loopjes maken. Voor interactie de gebruiker is er ook een mogelijkheid tot een getchar en een putchar, om input te vragen en karakters af te drukken.

Ondanks de beperkingen van de taal is de syntax echt verschrikkelijk slecht leesbaar, wat gezien de naam niet heel erg toevallig is. Gelukkig bestaat er een python-script dat brainfuck om kan zetten naar enigszins versimpelde C (indien mogelijk worden contanten toegevoegd, en optellingen worden bij elkaar gepakt, zodat iets als “+++++” gewoon vertaald wordt naar “+= 5”) zodat de code al iets leesbaarder werd. Het resultaat zag er uit als dit:

  while (p[0]) {
    p[0] += 11;
    p[1] += 6*p[0]-3;
    p[2] += 6*p[0];
    p[3] += p[0];
    p[0] = 3*p[3]-4;
    PUTC(p[1]);
    ...

Nog steeds niet fantastisch goed leesbaar, maar al een hele verbetering. Aan de gegenereerde code zijn twee wijzigingen gedaan. Ten eerste volgde onze invoer niet meer vanaf het toetsenbord maar kon je de invoer als argument meegeven (om makkelijker tegen de tools op de site te kunnen scripten), als tweede is er een functie gebouwd om makkelijk het geheugen en de locatie van de geheugenpointer te kunnen bekijken:

#define MAX_SIZE 30000

void dumpmem(uint8_t *m, uint8_t *p) {
  int i;
  for (i=0; i<MAX_SIZE; i)) {
    if (m[i]) {
      fprintf(stderr, "m[%i] = %i", i, m[i]);
      if (m[i] >= 32 && m[i] < 127) fprintf(stderr, "   (%c)", m[i]);
      fprintf(stderr, "\n");
    }
  }
  fprintf(stderr, "Value of P: %i\n", p-m);
  fflush(stderr);
}

Niet alleen konden we hiermee makkelijk zien welke waardes er in het geheugen staan, maar ook konden we bij de gegenereerde while-loopjes makkelijk kijken of ze uitgevoerd zouden worden, en zo nee, waarom niet.

Verder kijkend in de gegenereerde C-code kwamen we eigenlijk maar op 1 plek iets tegen dat een zinnige print-opdracht leek te geven, met het volgende stuk code:

            PUTC(p[-22]);
            PUTC(p[-21]);
            PUTC(p[-23]);
            PUTC(p[-20]);
            PUTC(p[-18]);
            PUTC(p[-19]);
            PUTC(p[-17]);
            PUTC(p[-23]);
            PUTC(p[-16]);
            PUTC(p[-15]);

Hieruit valt te leren dat de uitkomst bestaat uit 10 tekens, en dat op positie 3 en 8 hetzelfde teken moet staan. Aangezien we al in de mail de melding hadden gekregen dat er een windrichting bij hoort zou hier een gebouwnaam uit kunnen komen. We hebben dit vergeleken met alle gebouwnamen op de campus, en bij hoRsttoRen was een match. Hier zit echter geen toegankelijke zuidzijde aan, dus we moesten verder zoeken.

Inspectie van wat codepaden leverde op dat bepaalde codepaden enkel werden uitgevoerd bij invoer bestaande uit 3, 5 en 8 karakters. Bij invoer van 3 en 5 kwam het echter voor dat er links van ons geheugengebied gelezen werd. Dit mag natuurlijk niet, dus hieruit konden we concluderen dat het wachtwoord 8 tekens had. Dat is toch wat veel om te brute-forcen.

Meer geheugendumps bekijkend kwamen we er achter dat er bij de invoer van een wachtwoord van 8 tekens de tekst “brainfck” in het geheugen wordt geschreven, ongeacht de invoer. Het gebruik van “brainfck” als wachtwoord gaf wel iets van output (namelijk “3SVJTRFUUYQTI#HNQUJYNVMURFHJ+”) maar dit was geen puzzelcode en dan zou de zuidzijde ook nergens op slaan. Het antwoord was dus niet “brainfck”, maar hier moesten we vast wel iets mee doen.

Bij het proberen van wat extreme waardes “aaaaaaaa” en “zzzzzzzz” bleek dat zodra elk karakter hoger was dan de invoer op de respectievelijke plaatsen het verschil in een ander stuk geheugen opgeslagen werd. (dus bij “crainfck” is het verschil “10000000”, bij “dsainfck” is het verschil “21000000”, etc). Als er ook maar 1 karakter lager was (bijvoorbeeld “brainfcj”) werd dit codepad niet uitgevoerd. Blijkbaar was het dus 8 karakters lang en hand het brainfck als ondergrens. Het totaal aantal mogelijkheden was hiermee al minder dan toen we enkel wisten dat het 8 karakters moesten zijn, maar alsnog te veel om het te kunnen brute-forcen. Verder zoeken dus

De volgende poging was om te starten met de input “brainfck” en letter voor letter op te hogen, om zo maar te kijken wat er gebeurde. Bij de invoer “prainfck” werd er 1 geheugenwaarde met verschillen op 0 gezet, maar de rest van de letters gaven dit effect niet. Dus toch maar iets verder in de code zoeken.

Vlak voor het print-statement stond nog een loopje, die er behoorlijk ingewikkeld uit zag. De geheugenpointers gaven aan dat het iets uitlas met de verschillen die eerder berekend waren. En bij bepaalde verschillen werd het loopje vaker uitgevoerd. Hierna was het een kwestie van iets afdrukken als het loopje gedaan werd, de letters van het woord “brainfck” 1 voor 1 ophogen en zodra het loopje vaker werd uitgevoerd doorgaan naar de volgende letter. Zo werd het password “prainfck”, “pwainfck” en uiteindelijk “pwdzomgz”, dit laatste gaf de uitvoer “Ga naar TP”, ofwel tennispark. Achteraf weer in de code kijken leert dat deze verschillen gewoon letterlijk werden toegevoegd, en dat het hieruit berekend had kunnen worden.

        p[12] += 14;
        p[13] += 5;
        p[14] += 3;
        p[15] += 17;
        ++p[16];
        p[17] += 7;
        p[18] += 4;
        p[19] += 15;

Comments are closed.