# 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:```culong 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:
```asm001010ae 66  0f  6f       MOVDQA     XMM0 ,xmmword ptr [RSP ]=>user_input         04  24001010b3 48  89  ee       MOV        RSI ,RBP001010b6 4c  89  e7       MOV        RDI ,R12001010b9 ba  10  00       MOV        EDX ,0x10         00  00001010be 66  0f  38       PSHUFB     shuffled_input[0] ,xmmword ptr [SHUFFLE ]         =          00  05  a9          2f  00  00001010c7 66  0f  fe       PADDD      shuffled_input[0] ,xmmword ptr [ADD32 ]           =          05  91  2f                                                                   = null         00  00001010cf 66  0f  ef       PXOR       shuffled_input[0] ,xmmword ptr [XOR ]             =          05  79  2f          00  00001010d7 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:
```pythonflag[0] == ((flag[2]+add[0]) ^ xor[0]) & 0xff```
and thus:
```pythonflag[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:
```pythondata = '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.
### 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!}`