Hack.lu 2013: ELF

by Valodim & coco

We encountered a drunk human which had this binary file in his possession. We do not really understand the calculation which the algorithm does. And that is the problem. Can you imagine the disgrace we have to suffer, when we robots, based on logic, can not understand an algorithm? Somehow it seems that the algorithm imitates their masters and behaves …. drunk! So let us not suffer this disgrace and reverse the algorithm and get the correct solution.

Here is your challenge: https://ctf.fluxfingers.net/static/downloads/elf/reverse_me (alt link)

This was a weird one. The binary takes a parameter, and tells you if it is a correct flag. Opening the file in IDA, it seemed straightforward enough, a couple of reversible transformations on the input string mostly XORing in constants or different bytes together, a sleep(1s) here and there, and a check at the end if the result matched a couple of hardcoded numbers.

In a number of operations, an integer value was factored in which was set to different static values in the process. There was also an anti debugging function which changed this number if it detected a ptrace or LD_PRELOAD. Skiping that was no problem, but the value still kept incrementing all the time. We found the responsible code with a watchpoint, but at that point we couldn’t figure out where the responsible thread was spawned. We later found out the elf header was manipulated in a way readelf and ida didn’t recognize, but the elf loader did. The challenge author squall published the ElfParserLib library he used for that purpose after the ctf.

Since we didn’t really care about where it was changed from, but only what it was changed to, we traced the values of the variable at each point it was read. We used the pint library to get accurate timings while avoiding the anti-debugging code. Using those traced values, we ended up with our reversed code:

reverse_me reversed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

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

const char xor_string[]  = "fluxFluxfLuxFLuxflUxFlUxfLUxFLUxfluXFluXfLuXFLuXflUXFlUXfLUXFLUX";

int main() {

   unsigned int len_argv_1; // eax@4
   char *somethin_w_cryptoString, *solution; // [sp+368h] [bp-34h]@13
   int validate_4; // [sp+378h] [bp-24h]@40
   int validate_3; // [sp+37Ch] [bp-20h]@40
   int validate_2; // [sp+380h] [bp-1Ch]@40
   int validate_1; // [sp+384h] [bp-18h]@40
   unsigned int j; // [sp+388h] [bp-14h]@23
   int i; // [sp+38Ch] [bp-10h]@4

   len_argv_1 = 16;

   somethin_w_cryptoString = ( char *)malloc(len_argv_1);
   solution = ( char *)malloc(len_argv_1);

   // reverse 1 (tested)
   for( i = 0; i <= 3; ++i )
       somethin_w_cryptoString[i] = (1479696401 >> 8*i) & 0xff;
   for( i = 0; i <= 3; ++i )
       somethin_w_cryptoString[i +4] = (575759713 >> 8*i) & 0xff;
   for( i = 0; i <= 3; ++i )
       somethin_w_cryptoString[i +8] = (1584095846 >> 8*i) & 0xff;
   for( i = 0; i <= 3; ++i )
       somethin_w_cryptoString[i +12] = (1433290059 >> 8*i) & 0xff;

   // reverse 2
   for ( j = 0; j < len_argv_1; j++ ) {
       solution[(j - 18) % len_argv_1] =
           (58) ^ somethin_w_cryptoString[j]
           ^ xor_string[(j +  5) % len_argv_1]
           ^ xor_string[(j +  9) % len_argv_1]
           ^ xor_string[(j + 15) % len_argv_1]
           ^ xor_string[j % len_argv_1];
   }

   // output flag(?)
   for ( j = 0; j < len_argv_1; j++ ) {
       printf("%c", (char) solution[j]);
   }
   printf("\n");

   // testing

   // forward 2
   for ( j = 0; j < len_argv_1; j++ )
       somethin_w_cryptoString[j] = 38 ^ xor_string[( j + 9) % len_argv_1] ^
           xor_string[(j + 15) % len_argv_1] ^ 28 ^ xor_string[j] ^
           solution[(j - 18) % strlen(solution)] ^ xor_string[(j + 5) %
           len_argv_1];

   // forward 1
   validate_1 = 0;
   validate_2 = 0;
   validate_3 = 0;
   validate_4 = 0;
   for ( i = 0; i <= 3; ++i )
       validate_1 |= *(somethin_w_cryptoString + i) << 8 * i;
   for ( i = 0; i <= 3; ++i )
       validate_2 |= *(somethin_w_cryptoString + i + 4) << 8 * i;
   for ( i = 0; i <= 3; ++i )
       validate_3 |= *(somethin_w_cryptoString + i + 8) << 8 * i;
   for ( i = 0; i <= 3; ++i )
       validate_4 |= *(somethin_w_cryptoString + i + 12) << 8 * i;

   // debug values
   // printf("0x%x 0x%x 0x%x 0x%x\n", 1479696401,575759713, 1584095846,1433290059);
   // printf("0x%x 0x%x 0x%x 0x%x\n", validate_1, validate_2, validate_3, validate_4);

   if ( validate_1 != 1479696401 || validate_2 != 575759713 || validate_3 != 1584095846 || validate_4 != 1433290059 ) {
      // puts("Flag wrong!");
      return 1;
   } else {
      // puts("Flag correct!");
      return 0;
   }

}

We were fairly certain with our values. Still, the flag this program outputs contained non-printable characters: ^QOeur5brhIOumB^UP. This was especially weird since the unaltered reverse_me binary said this flag was correct even with the non-printable characters, and since all operations were reversible there was no way this could have been a collision. Curiously, our flag did not verify on an older 32 linux.

As it turned out the application used a self-ptrace trick which didn’t work since ubuntu 10.10 and thus the debug/timing variable (we called it modval for some reason) was off.

So first we simplified the algorithm to the following loop, preserving modval as a variable in appropriate places:

1
2
3
4
5
6

  char something_with_crypt_string[] = {0x11,0x60,0x32,0x58,0x61,0x65,0x51,0x22,0x66,0x62,0x6b,0x5e,0x4b,0x45,0x6e,0x55};
  unsigned char xored_crypt_string[16]={0};
   for (unsigned int j = 0; j<16; j++ )
   {
    xored_crypt_string[j] = key ^ xor_string[j] ^ xor_string[(j + modvals[0]) % 16] ^ xor_string[(1 + j + modvals[1]) % 16] ^ xor_string[(2 + j + modvals[2]) % 16] ^ something_with_crypt_string[j];
   }

This leaves us with three values for modval[i] and the key for bruteforcing. The key is the result of the first two debug values xored. We used the following tool to find all valid [A-Za-z0-9] inputs that would be valid for some time value sequence.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

#include <sys/types.h>
#include <sys/wait.h>
#include <sys/ptrace.h>
#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <string.h>

int main(int argc, char** argv) {

  const char xor_string[]  = "fluxFluxfLuxFLuxflUxFlUxfLUxFLUxfluXFluXfLuXFLuXflUXFlUXfLUXFLUX";
  char something_with_crypt_string[] = {0x11,0x60,0x32,0x58,0x61,0x65,0x51,0x22,0x66,0x62,0x6b,0x5e,0x4b,0x45,0x6e,0x55};
  unsigned char xored_crypt_string[16]={0};
  int modvals[] = {41, 46, 51};
  int ctr = 0;
  while(ctr<0xffffff){
    modvals[0] = ctr%256;
    modvals[1] = modvals[0]+(ctr>>8) % 256;
    modvals[2] = modvals[1]+(ctr>>16) % 256;
    ctr++;
    for(unsigned char key = 0; key < 255; key++){
       for (unsigned int j = 0; j<16; j++ )
       {
        xored_crypt_string[j] = key ^ xor_string[j] ^ xor_string[(j + modvals[0]) % 16] ^ xor_string[(1 + j + modvals[1]) % 16] ^ xor_string[(2 + j + modvals[2]) % 16] ^ something_with_crypt_string[j];
       }

       int valid = 0;
       char *res = &xored_crypt_string[0];
       for(int i=0; i<16; i++){
        if ( (res[i]>='0' && res[i]<='9') ||
            (res[i]>='a' && res[i]<='z') ||
            (res[i]>='A' && res[i]<='Z')){
          valid += 1;
          }else {
          }
       }

       if(valid == 16){
         for (int i=0;i<16;i++)
            printf("%c", xored_crypt_string[i]);
         printf("\n");
       }
    }
  }
}

There were a couple hundreds of such outputs with one class of notable ones:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

4v0idsS3cTionslD
4v0idSS3cTionSlD
4v0iDss3cTioNsLD
4v0iDss3CtIOnSld
4v0iDsS3cTioNslD
4v0iDsS3CtIOnSLd
4v0iDSs3CtIOnsld
4v0iDSS3CtIOnsLd
4v0IDss3CtIonSld
4v0IDsS3CtIonSLd
4v0IDSs3CtIonsld
4v0IDSS3CtIonsLd
4V0idsS3ctionslD
4V0idSs3ctionSLD
4V0idSS3ctionSlD
4V0iDss3CTIOnSld
4V0iDsS3CTIOnSLd
4V0iDSs3CTIOnsld
4V0iDSS3ctioNSlD
4V0iDSS3CTIOnsLd
4V0IdSS3ctiOnSlD
4V0IDss3CTIonSld
4V0IDsS3CTIonSLd
4V0IDSs3CTIonsld
4V0IDSS3ctiONSlD
4V0IDSS3CTIonsLd

After some shifting (from 4voidsectionsld to ld4voidesctions), one of those outputs was the right one.