Tags: hash arm
Rating:
[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 challenge
challenge: 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-multiarch
sudo dpkg --add-architecture arm64
sudo apt update
sudo apt install libc6:arm64
```
After doing all this magic we can run the binary on our x64 linux:
```
$ ./rejection
Automatic Rejection Machine v1.0
Please give me a flag: test
Sorry, 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 aarch64
The target architecture is set to "aarch64".
pwndbg> target remote localhost:1234
Remote debugging using localhost:1234
warning: 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`.
```C
int __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.
```C
void __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()`:
```C
void __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()`:
```C
void __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:
```python
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))
```
_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:
```python
alphabet = (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.py
found
(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:
```python
import string
import 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.py
b'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 *0x5500001270
Breakpoint 3 at 0x5500001270
pwndbg> target remote localhost:1234
[...]
pwndbg>
Breakpoint 1, 0x0000005500001270 in ?? ()
pwndbg> x/s $x0+0x38
0x5501812eb8: "albgefdhijkcmwyprqstvxnuo3210z45"
```
Now we're just another small python script from the flag:
```python
plain = "abcdefghijklmnopqrstuvwxyz012345"
swapped = "albgefdhijkcmwyprqstvxnuo3210z45"
flag = "put05m{l_chmn3u_m50l5ck_5}y71rpu"
result = ''
for c in plain:
result += flag[swapped.index(c)]
print(result)
```
```
$ python3 deswap.py
ptm{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:
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:
```python
inp0 += ((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 downloaded
21:48 uncropped shift introduced
22:20 uncropped shift fixed
22:25 itertools.combinations_with_replacement introduced
23:28 itertools.product used
23:43 flag
```
