Rating:

# Beginner (re, 50p, 482 solved)

## Description

In the task we get a classic 64bit ELF [linux binary](https://raw.githubusercontent.com/TFNS/writeups/master/2020-08-24-GoogleCTF/beginner/beginner) which checks the flag for us.

## Static analysis

### Decompiled code

The code we get from Ghidra is pretty short, but also a bit weird:
c
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

### Disassembly

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:

asm
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
24 10


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.

## Solution

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"))


### Example

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

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


and thus:

python
flag[0] == ((ord('F')+0xEF) ^ 0x76) & 0xff


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

### Full solver

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:

python
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':
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.

### Carry issue

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!}