f0rizen's Hash checker 0x01
Decompile
Dump the binary into Radare2 and decompile it, we get
ulong main(ulong argc, int64_t argv)
{
canary = *(in_FS_OFFSET + 0x28);
s = argv;
var_74h._0_4_ = argc;
/* Check it's pure numeric & length = 6 */
/* Begining of Useful Code */
var_5ch._0_4_ = sym.imp.strlen(*(s + 8)); /* slen = strlen(argv[1]) */
var_50h = *(s + 8); /* s = argv[1] a.k.a our input */
var_48h = var_5ch + -1; /* temp = slen - 1 */
uVar4 = (var_5ch * 8 + 0xfU) / 0x10; /* halflen = slen / 2 */
iVar1 = uVar4 * -0x10; /* probably a decompiler issue */
var_40h = &main::s + uVar4 * -2; /* long buf[6] */
*var_40h = 1; /* buf[0] = 1 */
for (var_60h = 1; var_60h < var_5ch; var_60h = var_60h + 1) {
/* buf[i] = (buf[i-1] * 0x83) % 0x3b9aca09 */
var_40h[var_60h] = (var_40h[var_60h + -1] * 0x83) % 0x3b9aca09;
}
/* at this point buffer look like */
/* buf = { 0x1, 0x83, 0x4309, 0x224d9b, 0x118db651, 0x228a4e1d } */
stack0xffffffffffffffa0 = *var_50h; /* sum = argv[1][0] */
for (var_64h = 1; var_64h < var_5ch; var_64h = var_64h + 1) {
/* sum = sum + ((input[i] % 0x3b9aca09) * buf[i]) % 0x3b9aca09 */
stack0xffffffffffffffa0 =
stack0xffffffffffffffa0 + ((var_50h[var_64h] % 0x3b9aca09) * var_40h[var_64h]) % 0x3b9aca09;
}
/* check sum == 0x3c0431a5 */
if (stack0xffffffffffffffa0 == 0x3c0431a5) {
*(&stack0xffffffffffffff70 + iVar1) = 0x1396;
sym.imp.puts("Key is valid");
}
else {
*(&stack0xffffffffffffff70 + iVar1) = 0x13a4;
sym.imp.puts("Wrong key!");
}
/* End of Useful Code */
uVar3 = 0;
goto canary_check;
canary_check:
/*...*/
}
Werid Stack Behavior
From the decompiled code we can see that this code is doing something werid
using argv
and slen
.
uVar4 = (var_5ch * 8 + 0xfU) / 0x10; /* halflen = slen / 2 */
iVar1 = uVar4 * -0x10; /* probably a decompiler issue */
var_40h = &main::s + uVar4 * - 2; /* char buf[6] */
*var_40h = 1; /* buf[0] = 1 */
After looking at the assembly, I think this may be a decompiler’s misbehavior.
0x0000127d 488d14c50000. lea rdx, [rax*8] /* rdx = slen * 8 */
0x00001285 b810000000 mov eax, 0x10 /* rax = 0x10 */
0x0000128a 4883e801 sub rax, 1 /* rax = rax - 1 = 0xf */
0x0000128e 4801d0 add rax, rdx /* rax = slen * 8 + 0xf */
0x00001291 be10000000 mov esi, 0x10
0x00001296 ba00000000 mov edx, 0
0x0000129b 48f7f6 div rsi /* rax = slen / 2 = 3 */
0x0000129e 486bc010 imul rax, rax, 0x10/* rax = 3 * 0x10 = 0x30 */
0x000012a2 4829c4 sub rsp, rax /* allocate 0x30 stack for buf! */
0x000012a5 4889e0 mov rax, rsp
Looks like buf
is well-formed now, this werid code is just allocating 0x30
bytes
to it, which is exactly 6 * sizeof(long)
.
I dnk math, but I know bruteforce
After resolving the decompliation myth. we can take a proper look at the checksum.
It first generates a buffer containing 6
magic numbers.
buf = { 0x1, 0x83, 0x4309, 0x224d9b, 0x118db651, 0x228a4e1d };
Then, without using the first, it uses the rest to multiply elementwisely with our input’s ASCII code, then sum them up.
I genuinely dnk how to reverse this hash process, but we can esstially speed iterate up to bruteforce out the checksum.
We can create a table storing the multiplication of ('1',..,'9') * buf
, totaling
9 * 5 = 45
numbers as '0'
and buf[0]
is unused.
Then iterate all combination from 111111
to 999999
to sum different entries
in the previous table to crack it.
#!/usr/bin/python3
from pprint import pprint
buf = [1]
for i in range(1, 6):
buf.append((buf[i-1] * 0x83) % 0x3b9aca09)
for k in buf:
print(hex(k))
d = {}
for i in range(1, 6):
d[i] = {}
for j in range(1, 10):
d[i][j] = hex(buf[i] * (ord("0") + j) % 0x3b9aca09)
pprint(d)
for l in range(111111, 1000000):
k = str(l).zfill(6)
s = ord("0") + int(k[0])
for (i, j) in enumerate(k[1:]):
if int(j) == 0:
continue
s += int(d[i+1][int(j)], 16)
print(f'{k}: {hex(s)}')
if s == 0x3c0431a5:
print(f'cracked, the code is {l}')
break
The result is 231337
.