Saturday, April 27, 2013

PlaidCTF 2013 - kavihk (binary 400) write-up

Here is another PlaidCTF write-up, in this case for a challenge that we didn't solve but had almost finished by the time the CTF ended (except for a couple (mostly stupid) things I'll mention later on). In this case it was kavihk, which was a binary worth 400 points. In the archive we can see both the kavihk binary and the source code it is based on, avih.

Avih "is a roguelike game whose source code fits in exactly 1024 bytes". So as you can imagine, the C code itself looks awful... everything in one line, abusing macro's, etc.

Luckily for us, there is a file named 'avih-commented.c' in the archive, that breaks the code down into pieces that we can more easily digest. Just for giving you a taste of it (you can see the whole thing in the archive), this is what the portion that draws the screen looks like:

  /* draw screen */
  D(
   /* determine tile colour */
   b=1;while(G^k[b++]&&b<8);
   /* check for visibility */
   F(c,u)d[f+(x-f)*c/u][g+(y-g)*c/u]-35||(b=z[x][y]<L?1:5);
   /* memory */
   b>6&&G<64&&(z[x][y]=L);
   /* draw */
   mvaddch(y,x,G|b*K)
  )

The code is using ncurses, and presents the user with a mesh filled with monsters, gold, talismans, etc. Now, looking at the binary the first thing we notice is that when the game finishes the following code (I'll call it 'youwin') is executed:

int __cdecl sub_8049581()
{
  int result; // eax@12
  char dest; // [sp+2Fh] [bp-9h]@2

  while ( (unsigned int)dword_804CB14 <= 0x1D )
  {
    if ( sub_804A1A5((int)&unk_80549C0, 0, 0, &dest, 8) )
      exit(1);
    byte_804CAD0[dword_804CB14] ^= dest;
    ++dword_804CB14;
  }
  if ( byte_804CAD5 != '_'
    || byte_804CADB != '_'
    || byte_804CADE != '_'
    || byte_804CAE2 != '_'
    || byte_804CAE7 != '_'
    || byte_804CAED )
    result = (int)"WIN    ...but no flag for you.";
  else
    result = (int)byte_804CAD0;
  return result;
}

So it seems the buffer at 0x0804CAD0 is actually our (30 bytes long) flag, but it is XORed with something that comes out of the function at 0x0804A1A5. The flag contains a few underscores and ends in a null byte, and this format is used to sanity check the result of the XOR before printing it. If the sanity check doesn't pass, then we are told we won the game, but there is no flag for us :(.

Based on these observations, patching the game to win it won't work. We'll need to reverse further and understand how the XOR key is generated. For this, I tracked cross-references to 'unk_0x80549C0' and found that only three functions use it: the main function, a function that's called in main during initialization, and the function that checks the flag.

I renamed this variable as 'state' so I could easily follow it later on in my idb, and looked at main and compared it to the code we are given:

int __cdecl main()
{
  char v0; // dl@18
  signed int v1; // eax@23
  int v2; // eax@36
  bool v3; // edx@43
  bool v4; // eax@46

  if ( sub_804A134(&state, 34, 1566) )
    exit(1);
  initscr();
  raw();
  start_color();
  for ( *(_DWORD *)&dword_805C958 = 0; *(_DWORD *)&dword_805C958 <= 7; ++*(_DWORD *)&dword_805C958 )
    init_pair(dword_805C958 + 1, dword_805C958, 0);
  uses_state(); //This function uses 'state' internally
  while ( *(_DWORD *)&dword_805C958 != 27 ) {
  /* ... */
}

The first function seems to be some initialization, as diving into it shows that it initializes some tables and so on... maybe some cryptographic function? In any case, this is what the function looks like:

signed int __cdecl sub_804A134(void *s, unsigned int a2, int a3)
{
  signed int result; // eax@2

  if ( a2 + a3 == 1600 )
  {
    if ( a2 && a2 <= 1600 )
    {
      sub_804B397();
      *((_DWORD *)s + 50) = a2;
      *((_DWORD *)s + 51) = a3;
      *((_DWORD *)s + 52) = a2 - 2;
      sub_804B4D9(s);
      result = 0;
    }
    else
    {
      result = 1;
    }
  }
  else
  {
    result = 1;
  }
  return result;
}

I dove into the other two sub-functions, and saw they were initializing some global arrays... but I didn't really attempt to understand them yet. I wanted to get a bigger picture of what is going on before diving into the details. So I called this function 'init_state', noted the 1600 magic (together with the 34 and 1566 passed into it) and went on to the next function.

Now, this function is much bigger, but we see that it passes the state into 'sub_804A1A5' (remember, this is the same function that generated our XOR key) and uses an output from it as a random seed:

int __cdecl uses_state()
{
  bool v0; // eax@19
  bool v1; // eax@23
  signed int v2; // ebx@36
  int result; // eax@37
  int dest; // [sp+3Ch] [bp-Ch]@7

  if ( sub_804A1A5((int)&state, &dword_80549B0, 32, 0, 0) )
    exit(1);
  if ( sub_804A1A5((int)&state, &dword_804CABC, 32, 0, 0) )
    exit(1);
  if ( sub_804A1A5((int)&state, &dword_8054AA8, 32, 0, 0) )
    exit(1);
  if ( sub_804A1A5((int)&state, 0, 0, &dest, 32) )
    exit(1);
  srand(dest);
  /* ... */

At this point I first followed the actual game logic and compared all variables with the commented avih source code we were given. This allowed me to find out that the values passed to sub_804A1A5 actually contain the current level, the maximum health points our character can have at this moment, and the amount of gold collected so far.

This seems to indicate that we'll have to 'play' one specific game (i.e. collecting the right amount of gold, right amount of talismans at each level) so we can get the key. Before I went on with that, I first wanted to understand what it was that it was using for generating the XOR key... so I dove into sub_804A1A5, which I now call do_sha3.

Going in, after a couple levels of calls, you see this:

int __cdecl sub_804A6CB(int a1)
{
  char v2; // [sp+18h] [bp-D0h]@1

  sub_80489B5(1, "Input of permutation", a1);
  sub_804A51C(&v2, a1);
  sub_804A795(&v2);
  sub_804A603(a1, &v2);
  return sub_80489B5(1, "State after permutation", a1);
}

Additionally, if you dive into the second call (sub_804A795) you see this code:

int __cdecl sub_804A795(int a1)
{
  int result; // eax@1
  unsigned int i; // [sp+1Ch] [bp-Ch]@1

  result = sub_80489DE(3, "Same, with lanes as pairs of 32-bit words (bit interleaving)", a1);
  for ( i = 0; i <= 0x17; ++i )
  {
    sub_8048BBE(3, i);
    sub_804A94D(a1);
    sub_80489DE(3, "After theta", a1);
    sub_804ABE9(a1);
    sub_80489DE(3, "After rho", a1);
    sub_804AD90(a1);
    sub_80489DE(3, "After pi", a1);
    sub_804AF85(a1);
    sub_80489DE(3, "After chi", a1);
    sub_804B175(a1, i);
    result = sub_80489DE(3, "After iota", a1);
  }
  return result;
}

So at this point I just decided to google for cryptographic functions (I thought it was likely to be a hash) that contained a permutation, lanes and blocks called theta, rho, pi, chi, iota. This search leads very fast to Keccak, or SHA-3 (notice the k's in the same place as the challenge name? :) ).

Good, it seems we have our hash function that will help generate the key. Now we need a bit more reversing to figure out what options we have for the different variables involved. The first one is the game level... this is easy, since we can track the 'youwin' function back to its caller and see under what condition it is called:

    if ( current_level == 9 )
      v2 = youwin();
    else
      v2 = (int)"kavihk";
    mvprintw(
      dword_804CA60,
      0,
      "H:%d/%d W:d%d L:%d $%d %s",
      dword_804CAB8,
      dword_804CABC,
      dword_804CAC0,
      current_level,
      dword_8054AA8,
      v2); 

So we have levels 0 to 9. In the level initialization function, we find that the level starts at 0 but is increased during initialization. Thus, the level value is 1-8 while we play the game, and is 9 when we have won.

Next, we need to figure out what happens with the gold... so we go back to the initialization function and check cross-references to the gold_collected variable. This brings us to the main loop, where this check is performed:

    if ( dword_804CB20[90 * (a1 + dword_80549B4) + a2 + dword_8054AA0] == '$' )
    {
      gold_collected += current_level;

Ok, this means that each time we find a dollar sign, we will increase our gold by a number equal to the current level. Something similar happens with the max_life_points when finding a talisman:

   if ( dword_804CB20[90 * (a1 + dword_80549B4) + a2 + dword_8054AA0] == tailsman )
    {
      max_health_points += current_level;
      dword_804CB20[a2 + dword_8054AA0 + 90 * (a1 + dword_80549B4)] = empty_space;
    }

Allright...next question: how many dollar signs and how many talisman signs can we find at each level? For this we need to go to the level initialization code again. I reversed this function quite a bit, comparing with the original code, so I knew that there is a function to fill in random empty spots, and an array with elements used to fill in the game grid.

So looking at this code, we find the following:

  player_y = 0;
  for ( b_tmp_var = 0; b_tmp_var <= 8; ++b_tmp_var )
  {
    if ( current_level <= 8 )
      fill_random_position(elems[b_tmp_var]);   // fill objects
  }
  for ( b_tmp_var = 0; ; ++b_tmp_var )
  {
    result = b_tmp_var;
    if ( 2 * current_level <= b_tmp_var )       // 2*level monsters!
      break;
    r = rand();
    fill_random_position(r % (7 * current_level / 5) + 'c');// Fill monsters
  }
  return result;
}

So this shows that we use the 9 initial items of 'elems' to fill in objects for the level. These are the contents of the array:

.data:0804CA80 elems           dd '$'                  ; DATA XREF: init_level+31A r
.data:0804CA80                                         ; main+163 r
.data:0804CA84                 dd '`'
.data:0804CA88                 dd '*'
.data:0804CA8C                 dd '$'
.data:0804CA90                 dd '.'
.data:0804CA94                 dd '@'
.data:0804CA98                 dd '`'
.data:0804CA9C                 dd '>'
.data:0804CAA0                 dd ']'

This tells us that there are two dollar signs and two talismans (the ` sign) in each level. So now we have all the information required to solve the level... except for implementing the proper flavor of SHA3. It turns out this costed me quite some time, and several stupid mistakes were made during that time (yes... after ~40 hours of CTF my mind is not in a very fresh state anymore :( ).

I first downloaded a python reference implementation from the Keccak website... but soon found out that the 34 and 1566 values (rate and capacity) were not supported by it (they had to be multiples of 8). So I moved into the C reference implementation... and found there was A LOT of code and it was very confusing to me at that moment.

So I decided to take 'a shortcut': reuse the implementation in the binary by means of injecting a dynamic library. I created a file implementing a 'start_color' function, which is called near the beginning of the game. From there, I could call the different functions in the game in a loop by means of function pointers. This is how the initial code looked (it is still missing some of the logic, but I don't have it at hand anymore) like:

#include 

int (*do_sha3)(void *state,void *in, int insize, void *out, int outsize);

int  start_color(void){
  int current_level=0,max_health_points=18,gold_collected=0;
  int dest;
  char buffer[16]; //This is for the last one
  const char *key = "\\\xf7\x8f/ny\xccy\xdc \x12\x0euj\x89\xd72P\xb2\xd2\xb1\x16\xd9\xe0\xde\xbf?\xf6\x1b\x08";
  // int level;
  do_sha3 = 0x0804A1A5;
  void * sha3_State = 0x080549C0;
  for(current_level=0;current_level<9;current_level++){
    do_sha3(sha3_State, ¤t_level, 32u, 0, 0);
    do_sha3(sha3_State, &max_health_points, 32u, 0, 0);
    do_sha3(sha3_State, &gold_collected, 32u, 0, 0);
    do_sha3(sha3_State, 0, 0, &dest, 32u);
    // current_level++;
    printf("Level: %d = %.8x\n", current_level+1, dest);
  }
  exit(-1);
  return 0;
}

From this code, I implemented a brute-forcer to go through the options... but it turned out to be awfully slow (specially within a single-core VM where I couldn't really paralellize anything). This means we need a faster implementation... so I had to dive into the damn Keccak reference code in C.

Now, during the CTF I couldn't find the exact functions that our binary was using, so I used lower level functions and made wrappers around them to look like the ones in the binary. However, I failed at restoring the encrypted flag and also I failed at the number of iterations through the levels.

It turns out that, although there are only 8 levels that the user plays, the level initialization routine is called 9 times. This means that the sha3 over the current_level, max_health_points and gold_collected is performed 9 times, not 8. Yes, in the code above it looks ok. But no, in my bruteforcer I failed to do it and set it to 8 (shame on me!), which is one of the reasons it failed during the CTF.

During the CTF I asked a couple stupid questions to clockish (who created the challenge) to check that I was still relatively sane... when the CTF ended. At this point, he told me I should have used the 'Duplex' functions from Keccak, which are exactly the ones used in the game!

Even then, I had failed at the number of iterations through the loop, and also at memcpy'ing over the global flag (shame on me again! I do too much AES stuff with 16 byte blocks at work, so I used 16 b ytes in the memcpy instead of 30...). Anyway, after the CTF I had some time to fix the problems, and I got to the solution.

The good news is, I was on the right track and had it almost done except for stupid mistakes (if it would have been slightly earlier in the weekend I'm quite confident I'd have finished it). The bad news is we didn't score those 400 points :-/

So in the end, here is the main code that does it:

int main(int ac, char **argv){
    int rate=34;
    int capacity=1600-34;
    uint32_t current_level,max_health_points,gold_collected;
    uint32_t dest=0;
    int i,j,gold,points;
    char *msg;
    
    const char *key = "\x5c\xf7\x8f\x2f\x6e\x79\xcc\x79\xdc\x20\x12\x0e\x75\x6a\x89\xd7\x32\x50\xb2\xd2\xb1\x16\xd9\xe0\xde\xbf\x3f\xf6\x1b\x08";

    // spongeState   state;
    current_level=0;
    gold_collected=0;
    max_health_points = 0x12;
       
    for(i=atoi(argv[1]);i<6561;i++){
        printf("[*] i = %d\n" , i);
        fflush(stdout);
        for(j=0;j<6561;j++){

         //Reinitialize game options
            max_health_points = 18;
            gold_collected = 0;
            memcpy(xored_flag,key,30);

            //Reinitialize state
            init_state(state, 34, 1566);

            //Obtain current guess
            gold = i;
            points = j;

            //Iterate through the levels, increasing gold and max health depending on current guess
            for(current_level=0;current_level<8;current_level++){
                // printf("%d %d %d\n", current_level, max_health_points, gold_collected);
                do_sha3(state, ¤t_level, 32, 0, 0);
                do_sha3(state, &max_health_points, 32, 0, 0);
                do_sha3(state, &gold_collected, 32, 0, 0);
                do_sha3(state, 0, 0, &dest, 32);
                // printf("Computed hash for level %d: %x\n", current_level+1,dest);
                gold_collected += (gold % 3)*(current_level+1);
                max_health_points += (points%3)*(current_level+1);
                points /= 3;
                gold /= 3;

            }

            do_sha3(state, ¤t_level, 32, 0, 0);
            do_sha3(state, &max_health_points, 32, 0, 0);
            do_sha3(state, &gold_collected, 32, 0, 0);
            do_sha3(state, 0, 0, &dest, 32);

            // printf("\n");
            // exit(-1);
            msg = youwin();
            // printf("msg = %s " , msg);
            if(strcmp(msg,"WIN    ...but no flag for you.")){
                printf("msg = %s \n" , msg);
                exit(0);
            }
        }
    }
}

The rest of the code can be found in this archive. This code comes from the KeccakRefernceAndOptimized distribution, a bit cleaned up so that it only contains my brute-forcer. If you run it starting at offset 2946 you'll see the solution:

sfx@deb64:~/dev/pctf2013/KeccakReferenceAndOptimized$ bin/KeccakOptimized64 2946
[*] i = 2946
msg = b2ute_f0rce_1s_7he_b3st_f0rce 
sfx@deb64:~/dev/pctf2013/KeccakReferenceAndOptimized$ 

Although we didn't finish it on time, it was a fun challenge to look at (albeit frustrating because I failed at solving it!)

No comments:

Post a Comment