[Link to original writuep](https://wrecktheline.com/writeups/m0lecon-2021/#automatic_rejection)
# Automatic Rejection Machine (19 solves, 217 points)by JaGoTu
```I'm sorry, your flag is rejected.
Author: mr96```
We get a `challenge` file:
```$ file challengechallenge: ELF 64-bit LSB shared object, ARM aarch64, version 1 (SYSV), dynamically linked, interpreter /lib/ld-linux-aarch64.so.1, BuildID[sha1]=855fc043635ad0ec0182bdd24b6a38624a704401, for GNU/Linux 3.7.0, stripped```
Now is as good time as any to remind ourselves how to run foreign architecture binaries using `qemu-user`. There are quite a few references online for statically built binaries, but I spent a few minutes staring at `aarch64-binfmt-P: could not open '/lib/ld-linux-aarch64.so.1': No such file or directory` (I'm partly writing this down for my own future reference ?):
```sudo apt install qemu-user qemu-user-static gcc-aarch64-linux-gnu binutils-aarch64-linux-gnu binutils-aarch64-linux-gnu-dbg build-essential gdb-multiarchsudo dpkg --add-architecture arm64sudo apt updatesudo apt install libc6:arm64```
After doing all this magic we can run the binary on our x64 linux:```$ ./rejection Automatic Rejection Machine v1.0Please give me a flag: testSorry, your flag is rejected.```
And even debug it using `gdb-multiarch` (I'm using pwndbg):
```$ qemu-aarc64-static -g 1234 rejection```
```$ gdb-multiarch rejection pwndbg: loaded 193 commands. Type pwndbg [filter] for a list.pwndbg: created $rebase, $ida gdb functions (can be used with print/break)Reading symbols from rejection...(No debugging symbols found in rejection)pwndbg> set architecture aarch64The target architecture is set to "aarch64".pwndbg> target remote localhost:1234Remote debugging using localhost:1234warning: remote target does not support file transfer, attempting to access files from local filesystem.Reading symbols from /lib/ld-linux-aarch64.so.1...(No debugging symbols found in /lib/ld-linux-aarch64.so.1)0x0000005501815140 in ?? () from /lib/ld-linux-aarch64.so.1```
Reverse engineering the binary starting with `main()`: it inits two arrays, which I called `key` and `outersalt`.
```Cint __cdecl main(int argc, const char **argv, const char **envp){  __int64 outersalt[2]; // [xsp+18h] [xbp+18h] BYREF  _QWORD key[4]; // [xsp+28h] [xbp+28h] BYREF
  outersalt[0] = 0x9E3779B917181920LL;  outersalt[1] = 0x9E3779B912881288LL;  key[0] = 0xDEADBEEFFEEDBEEFLL;  key[1] = 0x1BADB002FACECAFELL;  key[2] = 0xFEEDFACE08920892LL;  key[3] = 0xCAFEFEED12401240LL;  verify_flag(key, outersalt);  return 0;}```
`verify_flag()` inits an array of target values, asks for a flag, shuffles the bytes around a bit for added reversing fun, and then generates an array of hashes. If the generated hashes are identical to the target values, it gives a nice smiley face and we should have the flag.
```Cvoid __fastcall verify_flag(_QWORD *key, _QWORD *outersalt){  char v4; // [xsp+2Fh] [xbp-1091h]  int i; // [xsp+30h] [xbp-1090h]  unsigned int flaglen; // [xsp+34h] [xbp-108Ch]  _QWORD output[256]; // [xsp+38h] [xbp-1088h] BYREF  _QWORD target[256]; // [xsp+838h] [xbp-888h] BYREF  unsigned __int8 flag[128]; // [xsp+1038h] [xbp-88h] BYREF
  memset(target, 0, sizeof(target));  target[0] = 0xB4D8846071AC9EE5LL;  target[1] = 0x1E1FF00814E134FELL;  target[2] = 0x6B198E7941B7002ELL;  target[3] = 0xBC6FA839EFE36443LL;  /* [...] shortened */  target[58] = 0x239DCF030B3CE09BLL;  target[59] = 0x24556A34B61CA998LL;  puts("Automatic Rejection Machine v1.0");  printf("Please give me a flag: ");  __isoc99_fscanf(stdin, "%s", flag);  shuffle_bytes((char *)flag);  flaglen = strlen((const char *)flag);  flag[flaglen] = flag[0];  flag[flaglen + 1] = flag[1];  generate_hashes(flag, flaglen, key, outersalt, output);  v4 = 1;  for ( i = 0; i < (int)(2 * flaglen); ++i )  {    if ( output[i] != target[i] )      v4 = 0;  }  if ( v4 )    puts("Yay! You can submit your flag :)");  else    puts("Sorry, your flag is rejected.");}```
Also we can see that for each character of the flag it generates 2 hash values, as the comparison is done for `i` from `0` to `2 * flaglen`.
Let's take a look at `generate_hashes()`:
```Cvoid __fastcall generate_hashes(unsigned __int8 *flag, unsigned int flaglen, _QWORD *key, _QWORD *outersalt, _QWORD *output){  signed int curr_offset; // [xsp+48h] [xbp+48h]  int v11; // [xsp+4Ch] [xbp+4Ch]
  curr_offset = 0;  v11 = 0;  while ( curr_offset < flaglen )  {    *outersalt = (flag[curr_offset + 2] << 16) | (flag[curr_offset + 1] << 8) | flag[curr_offset] | 0xAABBCCDD11000000LL;    do_hash(outersalt, &output[v11], key);    ++curr_offset;    v11 += 2;  }}```
It takes 3 characters at a time, ORs them with an inner salt, and then replaces the first element of the outersalt array with it. What this means is we'll always be hashing `[0xAABBCCDD11XXYYZZ, 0x9E3779B912881288]` where `XXYYZZ` are the next 3 characters.
The final piece of the puzzle is `do_hash()`:
```Cvoid __fastcall do_hash(_QWORD *input, _QWORD *output, _QWORD *key1){  unsigned __int64 v3; // x0  __int64 inp0; // [xsp+38h] [xbp+38h]  __int64 inp1; // [xsp+40h] [xbp+40h]  unsigned __int64 i; // [xsp+48h] [xbp+48h]  __int64 round_key; // [xsp+50h] [xbp+50h]  __int64 cipher_state[4]; // [xsp+58h] [xbp+58h]
  inp0 = *input;  inp1 = input[1];  cipher_state[0] = *key1;  cipher_state[1] = key1[1];  cipher_state[2] = key1[2];  cipher_state[3] = key1[3];  for ( i = 0LL; i <= 0xF; ++i )  {    v3 = i & 3;    cipher_state[v3] = cipher_state[0]                     + cipher_state[1]                     + ((cipher_state[2] + cipher_state[3]) ^ (cipher_state[0] << SLOBYTE(cipher_state[2])));    round_key = cipher_state[v3];    inp0 += ((round_key + inp1) << 9) ^ (round_key - inp1) ^ ((round_key + inp1) >> 14);    inp1 += ((round_key + inp0) << 9) ^ (round_key - inp0) ^ ((round_key + inp0) >> 14);  }  *output = inp0;  output[1] = inp1;}```
Now one observation to make is that the hashing used has no feedbacking - between hashings, no information from the previous hashing is kept, therefore each hashing can be considered completely separately.
I first reimplemented the hashing function 1:1 in python, but while debugging some other issues I had in my code (more on that later), I noticed that the big key is just used to generate 0xF round keys which are then crossingly added/subtracted from the inputs, so I just calculated them once and used them without the addition-xor shenanigans:
```pythonround_keys = [3219635032107427007, 6218263913405319823, 10442084089971362336, 269167876992306094, 15170038263011673372, 13552892002036573561, 2440776016958275683, 12200225424595105446, 9413572991142977950, 7501180621166657056, 1449469240296740551, 15523165193068945963, 11895360271610058672, 8006228610147169986, 8511276599127682916, 15596717701864595457]
def get_to_add(round_key, val):    sumed = (round_key + val) & 0xFFFFFFFFFFFFFFFF    difed = (round_key - val) & 0xFFFFFFFFFFFFFFFF    return ((sumed << 9) ^ (difed) ^ (sumed >> 14)) & 0xFFFFFFFFFFFFFFFF
def do_hash(inp):    inp0 = inp[0]    inp1 = inp[1]     for i in range(16):              round_key = round_keys[i]        inp0 += get_to_add(round_key, inp1)        inp0 &= 0xFFFFFFFFFFFFFFFF        inp1 += get_to_add(round_key, inp0)        inp1 &= 0xFFFFFFFFFFFFFFFF
    return (inp0, inp1)
def hash_chars(test):    inp = (test[2] << 16) | (test[1] << 8) | test[0] | 0xAABBCCDD11000000    return do_hash((inp, 0x9e3779b912881288))```
_Beautiful ANDing with `0xFFFFFFFFFFFFFFFF` everywhere, right?_
When we have the hashing function implemented, we can bruteforce the first three characters to match the first target value:
```pythonalphabet = (string.ascii_letters + string.digits + '_{}').encode()for attempt in itertools.product(alphabet, repeat=3):    res = hash_chars(attempt)    if(res[0] == targets[0]):        print("found")        print(attempt)        print(list(map(lambda x : hex(x), res)))```
```$ python3 rejection.pyfound(112, 117, 116)['0xb4d8846071ac9ee5', '0x1e1ff00814e134fe']```
Looking at the second value, it also matches the target. Bingo! `(112, 117, 116)` corresponds to `put`. For the rest of the targets, the 3-character window moves by 1, so we can only bruteforce one letter at a time for a faster experience. Here is the full bruteforcing script:
```pythonimport stringimport itertools
targets = [0xB4D8846071AC9EE5, 0x1E1FF00814E134FE, 0x6B198E7941B7002E, 0xBC6FA839EFE36443, 0xC3C71AD9A664B6C3, 0x5692A2F09C98D986, 0xF084A1A59CD01E68, 0xBC52E78A7E4DF2DF, 0xDA219D93290B91A8, 0x5703D0286FA5D32F, 0x6274B1B118DA82B2, 0xA746EBFB0954EBBC, 0x5F6DF7BD4F1967A2, 0x16D5B5BDEE98CF8E, 0x52E8B6DF7E62E39A, 0x99F9455FB0C8D933, 0x05FFD82D53AF933D, 0xFF9084A16FF0141C, 0xE17C5F0781D52F9B, 0x1A0F4431548E51D1, 0xF2E8573D8F0F01DD, 0x250039177F4DEF91, 0x8851491ECBC7AF7C, 0xAD427C6695B91D24, 0x5E0071D97D98D094, 0x264DDA52B0C37B03, 0xA5811271D6D7C428, 0xE0133FC719F34136, 0xE508ACE2412B2633, 0x74321A3E9FACE34C, 0xFF5B8A59E8EBF70B, 0x76275A516F88C986, 0x1604D76F74599CC4, 0xF744BCD8F2016F58, 0xA0B6A7A0239E4EA7, 0xF1EFC57F15CB9AB4, 0xB0D1AD4FB4ED946A, 0x81CA31324D48E689, 0xE6A9979C51869F49, 0xA666637EE4BC2457, 0x6475B6AB4884B93C, 0x5C033B1207DA898F, 0xB66DC7E0DEC3443E, 0xE4899C99CFA0235C, 0x3B7FD8D4D0DCAF6B, 0xB1A4690DB34A7A7C, 0x8041D2607129ADAB, 0xA6A1294A99894F1A, 0xDDE37A1C4524B831, 0x3BC8D81DE355B65C, 0x6C61AB15A63AD91E, 0x8FA4E37F4A3C7A39, 0x268B598404E773AF, 0x74F4F040AE13F867, 0x4DF78E91FD682404, 0xABE1FC425A9A671A, 0x1BB06615C8A31DD5, 0x9F56E9AEF2FA5D55, 0x239DCF030B3CE09B, 0x24556A34B61CA998]
round_keys = [3219635032107427007, 6218263913405319823, 10442084089971362336, 269167876992306094, 15170038263011673372, 13552892002036573561, 2440776016958275683, 12200225424595105446, 9413572991142977950, 7501180621166657056, 1449469240296740551, 15523165193068945963, 11895360271610058672, 8006228610147169986, 8511276599127682916, 15596717701864595457]
def get_to_add(round_key, val):    sumed = (round_key + val) & 0xFFFFFFFFFFFFFFFF    difed = (round_key - val) & 0xFFFFFFFFFFFFFFFF    return ((sumed << 9) ^ (difed) ^ (sumed >> 14)) & 0xFFFFFFFFFFFFFFFF
def do_hash(inp):    inp0 = inp[0]    inp1 = inp[1]     for i in range(16):              round_key = round_keys[i]        inp0 += get_to_add(round_key, inp1)        inp0 &= 0xFFFFFFFFFFFFFFFF        inp1 += get_to_add(round_key, inp0)        inp1 &= 0xFFFFFFFFFFFFFFFF
    return (inp0, inp1)
def hash_chars(test):    inp = (test[2] << 16) | (test[1] << 8) | test[0] | 0xAABBCCDD11000000    return do_hash((inp, 0x9e3779b912881288))
known = b"put"i = 2
alphabet = (string.ascii_letters + string.digits + '_{}').encode()while True:    for attempt in itertools.product(alphabet, repeat=1):        res = hash_chars((known[-2],known[-1]) + attempt)        if(res[0] == targets[i] and res[1] == targets[i+1]):            known += bytes([attempt[0]])            print(known)            i +=2            break
```
```$ python3 rejection.pyb'put0'b'put05'b'put05m'b'put05m{'b'put05m{l'b'put05m{l_'b'put05m{l_c'b'put05m{l_ch'b'put05m{l_chm'b'put05m{l_chmn'b'put05m{l_chmn3'b'put05m{l_chmn3u'b'put05m{l_chmn3u_'b'put05m{l_chmn3u_m'b'put05m{l_chmn3u_m5'b'put05m{l_chmn3u_m50'b'put05m{l_chmn3u_m50l'b'put05m{l_chmn3u_m50l5'b'put05m{l_chmn3u_m50l5c'b'put05m{l_chmn3u_m50l5ck'b'put05m{l_chmn3u_m50l5ck_'b'put05m{l_chmn3u_m50l5ck_5'b'put05m{l_chmn3u_m50l5ck_5}'b'put05m{l_chmn3u_m50l5ck_5}y'b'put05m{l_chmn3u_m50l5ck_5}y7'b'put05m{l_chmn3u_m50l5ck_5}y71'b'put05m{l_chmn3u_m50l5ck_5}y71r'b'put05m{l_chmn3u_m50l5ck_5}y71rp'b'put05m{l_chmn3u_m50l5ck_5}y71rpu'Traceback (most recent call last):  File "rejection.py", line 36, in <module>    if(res[0] == targets[i] and res[1] == targets[i+1]):IndexError: list index out of range```
_Who needs bounds checks when you can `while True` your way to an `IndexError`_ ?
That doesn't look too flag-ish, but no worries, we still have the `shuffle_bytes()` function to reverse. At this point, I didn't feel like reversing the substition array the code uses, so I got the permutation dynamically by feeding in `abcdefghijklmnopqrstuvwxyz012345`:
```pwndbg> b *0x5500001270Breakpoint 3 at 0x5500001270pwndbg> target remote localhost:1234[...]pwndbg> Breakpoint 1, 0x0000005500001270 in ?? ()pwndbg> x/s $x0+0x380x5501812eb8:	"albgefdhijkcmwyprqstvxnuo3210z45"```
Now we're just another small python script from the flag:
```pythonplain = "abcdefghijklmnopqrstuvwxyz012345"swapped = "albgefdhijkcmwyprqstvxnuo3210z45"
flag = "put05m{l_chmn3u_m50l5ck_5}y71rpu"
result = ''
for c in plain:    result += flag[swapped.index(c)]
print(result)```
```$ python3 deswap.pyptm{5m0l_chunk5_5m0l_53cur17y}pu```
So we just strip the last two characters and submit the flag!
## Mistakes were made
From the moment I downloaded the challenge to flag took me 2 hours and 40 minutes. Most of that time was occupied by 2 simple but critical mistakes I made.
First of all, when rewriting `C` calculations to `python`, you have to somehow deal with fixed-bits integers - in `C` all calculations will inherently be limited to 8/16/32/64 bits while python will let your integers go big. As you've seen, I choose the "easiest" of the solutions to this problem, which could be summed up by this image:
![Sprinkling &0xFFFFFFFFFFFFFFFF meme](https://wrecktheline.com/writeups/m0lecon-2021/fff.jpg)
I just "strategically" sprinkle `&0xFFFFFFFFFFFFFFFF` at positions where I _feel_ like a cropping is necessary. Turns out my feelings aren't always the best. I introduced a bug by writing this code:
```pythoninp0 += ((round_key + inp1) << 9) ^ (round_key - inp1) ^ ((round_key + inp1) >> 14)inp0 &= 0xFFFFFFFFFFFFFFFF```
Spot the mistake? The first member of the xor is fine, it will shift in zeros from the right and will eventually get cropped. The second member of the xor is fine, it will get cropped too. However, in the third member, `round_key + inp1` can be (and will be) bigger than 64-bit, but the `>> 14` will shift those additional bits (that should be gone already) in! I fixed it by sprinkling more `&0xFFFFFFFFFFFFFFFF` as you can see in the final code. I promise I'll try to look into a BitVector library for future CTFs! ?
The second critical mistake I made was even dumber: in what is an unexplainable bad judgement I used `itertools.combinations_with_replacement` to generate the possibilities instead of `itertools.product`. I mean, the bruteforce was faster with just combinations, but it came at the cost of never finding the correct input, which is not a good deal.
So, how long did I exactly spend on those mistakes? Here is a timeline in my local timezone:
```21:04 challenge downloaded21:48 uncropped shift introduced22:20 uncropped shift fixed22:25 itertools.combinations_with_replacement introduced23:28 itertools.product used23:43 flag```
