Beginner Google CTF-2020

So I was playing google ctf for first time i am tried and stuck at many places may be this might be helpful for you … 🙂

In the task we get a classic 64bit ELF linux binary which checks the flag for us.

Try to Decompiled code and then Disassembled

The code we get from Ghidra is pretty short, but also a bit weird:

ulong main(void)
{
  int cmp_result;
  uint cmp_result2;
  int shuffled_input [4];
  undefined auVar1 [16];
  char user_input [16];
  int decrypted_flag [4];
  
  printf("Flag: ");
  __isoc99_scanf("%15s",user_input);
  shuffled_input = pshufb(user_input,SHUFFLE);
  auVar1 = CONCAT412(SUB164(shuffled_input >> 0x60,0) + ADD32[3],
                     CONCAT48(SUB164(shuffled_input >> 0x40,0) + ADD32[2],
                              CONCAT44(SUB164(shuffled_input >> 0x20,0) + ADD32[1],
                                       SUB164(shuffled_input,0) + ADD32[0]))) ^ XOR;
  decrypted_flag[0] = SUB164(auVar1,0);
  decrypted_flag[1] = SUB164(auVar1 >> 0x20,0);
  decrypted_flag[2] = SUB164(XOR >> 0x40,0);
  decrypted_flag[3] = SUB164(XOR >> 0x60,0);
  cmp_result = strncmp(user_input,(char *)decrypted_flag,0x10);
  if (cmp_result == 0) {
    cmp_result2 = strncmp((char *)decrypted_flag,EXPECTED_PREFIX,4);
    if (cmp_result2 == 0) {
      puts("SUCCESS");
      goto LAB_00101112;
    }
  }
  cmp_result2 = 1;
  puts("FAILURE");
LAB_00101112:
  return (ulong)cmp_result2;
}

It’s also not particularly accurate, but we can get some basic info from it:

• The input flag we provide is supposed to have 15 characters
• The flag starts with CTF{ prefix
• Our input is somehow transformed and the result is compared again with the input

If we look at disassembly of this function, it’s actually much cleaner. Especially the part which decompiled to all those CONCAT412 and SUB164. Assembly code is just:

001010ae 66  0f  6f       MOVDQA     XMM0 ,xmmword ptr [RSP ]=>user_input
         04  24
001010b3 48  89  ee       MOV        RSI ,RBP
001010b6 4c  89  e7       MOV        RDI ,R12
001010b9 ba  10  00       MOV        EDX ,0x10
         00  00
001010be 66  0f  38       PSHUFB     shuffled_input[0] ,xmmword ptr [SHUFFLE ]         = 
         00  05  a9 
         2f  00  00
001010c7 66  0f  fe       PADDD      shuffled_input[0] ,xmmword ptr [ADD32 ]           = 
         05  91  2f                                                                   = null
         00  00
001010cf 66  0f  ef       PXOR       shuffled_input[0] ,xmmword ptr [XOR ]             = 
         05  79  2f 
         00  00
001010d7 0f  29  44       MOVAPS     xmmword ptr [RSP  + decrypted_flag[0] ],shuffled

The idea is pretty simple:

• our input is loaded to XMM0
• it’s then shuffled using constant SHUFFLE array
• then constant ADD32 value is added
• finally it’s xored with constant XOR value

Note that we have xmmword ptr everywhere, and this means everything is actually happening for 128-bit data slices at once!

However due to how mathematics work, we can actually consider those operations to be done on single bytes, but it might cause issues with carry-over. To sum up, the flag is passed via simple out_byte = (flag_byte+const1) ^ const2 and initially flag characters are shuffled.

Since we know that encryption/decryption process is just out_byte = (in_byte+const1) ^ const2 and we know that this has to match our initial input, we can easily invert this logic thanks to the shuffling! Because the shuffle makes out_byte and in_byte to be different values, from different positions in the flag input buffer.

Constants are:

xor = map(ord, '76 58 B4 49 8D 1A 5F 38 D4 23 F8 34 EB 86 F9 AA'.replace(' ', '').decode("hex")) add = map(ord, 'EF BE AD DE AD DE E1 FE 37 13 37 13 66 74 63 67'.replace(' ', '').decode("hex")) shuffle = map(ord, '02 06 07 01 05 0B 09 0E 03 0F 04 08 0A 0C 0D 00'.replace(' ', '').decode("hex"))

Notice that at index 0 in shuffle table there is 2, in add table EF and in xor table 76 This means that:

flag[0] == ((flag[2]+add[0]) ^ xor[0]) & 0xff

And we will get some

flag[0] == ((ord(‘F’)+0xEF) ^ 0x76) & 0xff

We can run this and we get as expected value 67 so C!

The idea is to use this approach to uncover characters we don’t know. Notice for example that in shuffle table value 03 is somewhere in the middle – this means we could use a known 3rd flag character { to uncover this middle byte. Hopefully the 4 chars we know will be enough to propagate all others.

We want to loop over the flag we know, and propagate every flag char we can:

data = 'CTF{' + ''.join(chr(0xff) for i in range(12))
result = list(data)
for target_index in range(16):
    src_index = shuffle[target_index]
    known_char = result[src_index]
    if known_char != '\xff' and result[target_index] == '\xff':
        a = add[target_index]
        x = xor[target_index]
        val = ((ord(known_char) + a) ^ x)
        result[target_index] = chr(val % 256)

If we run this only once, it will propagate only 2 additional characters. We need to run this at most 12 times, to uncover all the missing 12 characters, if each iteration would propagate only a single byte. We could also include trailing } and nullbyte at the end, in case we didn’t have enough, but it’s just fine with only prefix.

This code prints almost-perfect flag -> CTF{S1NCf0rM3!}.

The problem is that we’re totally dismissing carry! Addition and xor of some lower byte might have overflown and modified the upper byte.

But if we print out val/256 we can see that there were only a handful and only by 1 so we can guess the right flag. We can also place this broken flag into the binary and look under debugger at the flag generated for comparison. Either way we get 

CTF{S1MDf0rM3!}