Crackme 18: BinaryNewbie’s cr4ckm3_0x
Seeing how I thought the previous crackme by BinaryNewbie was pretty interesting, I figured I would give a shot to this other challenge from the same author. Once again the original archive is hosted on crackmes.one, but you can also download the binary here.
The README mentions two “helpful links”: Numbermatics (a website about the properties of various numbers), and a SHA-256 hashing tool. There might be some math involved.
The program asks for a single password, which has some length constraints:
$ ./cr4ckm3_0x
[+] Welcome to cr4ckm3_0x
[+] Try to get the correct password
[+] I hope that will be funny
[+] Developed by Binary Newbie
Enter the password: hello
[-] Wrong length
Entering a longer string produces a 256-bit hash:
$ ./cr4ckm3_0x
[+] Welcome to cr4ckm3_0x
[+] Try to get the correct password
[+] I hope that will be funny
[+] Developed by Binary Newbie
Enter the password: hello-world
Here is your hash: 01d3393d50682838c7a0567aa4053766c0d5b108229a6d8b7a1c367d9d9e0e31
[-] Oh no, try again :/
Starting the analysis ¶
Before disassembling, let’s quickly examine the binary: strace doesn’t reveal any suspicious calls like ptrace or fork, and readelf -a produces a long output with a lot of metadata, which might be helpful.
On the other hand, strings prints out almost 6,000 lines, and most seem completely unrelated to this program. I suspect this is due to the static linking of glibc.
Disassembling the program, we easily find the welcome strings in sub_4005d0 with what seems like two puts calls followed by a read of some kind (fgets, maybe?). The function allocates a pretty large buffer on the stack, and points rbx to rbp-0x9a before reading what seems to be 10 bytes. We also see the code setting the byte at rbp-0x91 to zero:
00000000004005d9 lea rdi, qword [aWelcomeToCr4ck] ; "[+] Welcome to cr4ckm3_0x..."
; (some instructions skipped)
00000000004005ef lea rbx, qword [rbp-0x9a] ; note where rbx points
00000000004005f6 sub rsp, 0x90
00000000004005fd mov rax, qword [fs:0x28]
0000000000400606 mov qword [rbp-0x28], rax
000000000040060a xor eax, eax
000000000040060c call sub_417e00+384 ; presumably puts or equivalent
0000000000400611 lea rsi, qword [aEnterThePasswo] ; "Enter the password: "
0000000000400618 mov edi, 0x1
000000000040061d xor eax, eax
000000000040061f call sub_453bd0+416 ; also a write
0000000000400624 mov rdx, qword [qword_6c17a8]
000000000040062b mov esi, 0xa ; 10 bytes
0000000000400630 mov rdi, rbx ; this is the actual buffer parameter
0000000000400633 call sub_417870 ; fgets or equivalent
0000000000400638 test rax, rax
000000000040063b je loc_400789 ; jumps further down
0000000000400641 mov byte [rbp-0x91], 0x0 ; this is rbx + 9 bytes
so something like:
char buffer[10];
// likely a few more variables on the stack
puts("[+] Welcome...");
puts("Enter the password");
if (fgets(buffer, 10, stdin) != NULL) {
buffer[9] = 0;
}
It looks like our password will be 9 characters long.
Finding constraints to limit our search space ¶
Following the fgets call, a loop goes over each character with different individual conditions for various bytes, ultimately all checking that none of the input characters are null. We start with the input string in rax, and the first block makes rdx point to rax+1 and checks the byte at rdx-1 – the first one in the string.
The conditions are easy to follow, even if this sort of unrolled loop is a bit verbose:
We then have a second length check, and the actual input validation starts. Recall that rbp - 9a points to the first character of our input: the first condition is whether it is equal to the character '2'.
00000000004006ba cmp byte [rbp-0x9a], '2'
00000000004006c1 je loc_40079c ; continue to next condition
Then comes a sequence of 6 function calls, after which half of them check the return value in al and interrupt the sequence if it is not zero. This is pretty clear when we look at the control flow graph and highlight the common jumps that all break the sequence:
Note also how the byte at rbp - 0x99 (which is our second input second character) is compared to 0x70 and we branch out if the difference is strictly greater than 3. This leaves only the range 0x70 to 0x73 as valid characters, which are the letters p, q, r, s.
Indeed, a single encouragement message is printed if we try the password 2AAAAAAAA:
Enter the password: 2AAAAAAAA
[+] Yes, keep going :)
Here is your hash: a87e9cefa585405929d6c5277ae827e7976ed73f15b13ba4a92d3ce16692b0e2
[-] Oh no, try again :/
But if the second letter is in the range we just found, a second message appears:
Enter the password: 2pAAAAAAA
[+] Yes, keep going :)
[+] Yes, keep going :)
Here is your hash: 70442c43c67b9da1de7be700206027c5b412916bfe11fd6e58a884149f4fd80a
[-] Oh no, try again :/
Since the two function calls made after the checks on 2 and 0x70 both went to sub_400f30, we can probably assume that this procedure only prints the progress message. A quick look reveals a couple of suspicious constants:
0000000000400f39 movabs rdx, 0xd1d99ecedbdbd59e ; this looks like it might be a string
0000000000400f43 mov ecx, 0xffff9784 ; maybe this one too
0000000000400f48 mov r11d, 0xffffffbe ; /!\ note the last byte of r11: 0xbe
; (a bunch of other instructions omitted)
0000000000400f64 mov dword [rbp-0x20], 0x9ed9d0d7 ; this one also looks unusual
; (some more instructions skipped)
0000000000400f7a movabs rax, 0x92cddbe79ee395e5 ; and more magic numbers
Shortly after these constants are installed into various registers, we jump straight into the core of a loop that XORs bytes with r11b (the low 8 bits of r11):
0000000000400f97 jmp loc_400ffb
; instructions in-between omitted)
0000000000400ffb xor byte [r8], r11b ; remember that we've just set this to 0xbe
Predictably, the decryption loop ends with a call to puts.
Let’s decrypt the values we found, after re-ordering them and converting from little-endian:
>>> ''.join(chr(b ^ 0xbe) for b in [0x92, 0xcd, 0xdb, 0xe7, 0x9e, 0xe3, 0x95, 0xe5][::-1] +
... [0xd1, 0xd9, 0x9e, 0xce, 0xdb, 0xdb, 0xd5, 0x9e][::-1] +
... [0x9e, 0xd9, 0xd0, 0xd7][::-1] +
... [0x97, 0x84][::-1])
'[+] Yes, keep going :)'
Perfect! So sub_400f30 is indeed what prints this message.
The next call goes to sub_4016a0, preceded by a mov rdi, rbx which makes rdi point to our input. This function looks somewhat similar to sub_400f30 with what looks like a string being decoded, but not before a range comparison validates the byte at rdi + 2 (the third character of our input):
00000000004016b7 movzx edx, byte [rdi+2] ; make edx point to input + 2
; (some code omitted)
00000000004016ca cmp dl, 0x6a ; this is 'j'
00000000004016cd je loc_401708
00000000004016cf cmp dl, 0x6b ; 'k'
00000000004016d2 je loc_401708
00000000004016d4 cmp dl, 0x6c ; 'l'
00000000004016d7 je loc_401708
00000000004016d9 cmp dl, 0x6d ; 'm'
00000000004016dc je loc_401708
00000000004016de cmp dl, 0x6e ; 'n'
00000000004016e1 je loc_401708
Any of these characters makes us jump to loc_401708, which has the same constants as in the “keep going” function. With this range of valid values for the third input character, we can use it to get a third progress message to print:
Enter the password: 2pkAAAAAA
[+] Yes, keep going :)
[+] Yes, keep going :)
[+] Yes, keep going :)
Here is your hash: 119a7d0e8372c3cda43a2619f7ae6e5a4b6aaeedb83869d694480728f5ea5fa8
[-] Oh no, try again :/
Let’s continue with sub_4017d0. Interestingly, we see a call to __ctype_tolower_loc followed by a comparison of the entry for the character at input[3] with the value 8, which is something we explored recently in crackme 16.
00000000004017fa call __ctype_tolower_loc ; the function used for isascii/isdigit/etc
00000000004017ff movsx rcx, byte [rbx+0x3] ; move input[3] into rcx
0000000000401804 mov rdx, qword [rax] ; rax points to the ctype table
0000000000401807 xor eax, eax ; unused here
0000000000401809 test byte [rdx+rcx*2+0x1], 0x8 ; compare the table entry for input[3] with 8
000000000040180e jne loc_401830
This comparison validates the third character with isdigit. As with the other functions, this is followed by code to print a progress message. We now have a constraint for our fourth byte, so let’s again validate our progress with one more valid character:
Enter the password: 2pk7AAAAA
[+] Yes, keep going :)
[+] Yes, keep going :)
[+] Yes, keep going :)
[+] Yes, keep going :)
Here is your hash: a9980a331d6f6c7bd6c9824b3b92f3b3534a70996afb7e870c88d4b73feb638e
[-] Oh no, try again :/
The next call goes to sub_401900, which starts by looking at characters 4 and 5:
0000000000401917 movzx ecx, byte [rdi+4] ; move input[4] to ecx (cl, really)
; [...] (3 irrelevant instructions skipped)
000000000040192a cmp cl, byte [rdi+5] ; and we compare it to input[5]
000000000040192d je loc_401950 ; jump off without the next comparisons
We can see from the control flow graph that the next success message depends at least on these two matching, but there’s a bit more:
0000000000401950 movsx si, cl ; move input[4] to si
0000000000401954 mov r8d, ecx ; and to r8
0000000000401957 lea edx, dword [rsi*8] ; edx = input[4] * 8
000000000040195e sar r8b, 0x7 ; shift right lowest 8 bits of r8 by 7
0000000000401962 sub edx, esi ; edx = edx - esi, or edx = input[4] * 7
0000000000401964 lea edi, dword [rsi+rdx*8] ; edi = rsi + rdx * 8, or edi = input[4] + (input[4] * 7) * 8
0000000000401967 sar di, 0x9 ; shift right by 9
000000000040196b sub edi, r8d ; edi = edi - 16 bits or r8
000000000040196e lea r9d, dword [rdi+rdi*8] ; e9 = rdi * 9
0000000000401972 cmp cl, r9b ; check if cl matches this value
0000000000401975 jne loc_40192f ; jump *over* the success message
Decoding this sort of thing is always a bit tedious, but we can simplify it a little. The sar r8b, 0x7 will likely set it to zero, since most printable ASCII characters are in the 0-127 range. We can therefore remove all the r8 references, and after a few simple β-reductions we end up with the rule ((input[4] + (input[4] * 7) * 8) >> 9) * 9 == input[4].
There are several values that could satisfy this constraint, but we might be able to reduce the search space further if we take the size of each register into consideration. Ghidra applies these reduction rules automatically and does an excellent job of simplifying this code, ending up with a trivial condition:
char input_4 = input[4];
if (input_4 == input[5]) {
if ((input_4 == (char)((input_4 / '\t') * '\t')) && ((double)(int)(input_4 / '\t') == 5.0)) {
Since '\t' is 9, we’re doing input[4] % 9 == 0 && input[4] / 9 == 5. The only matching value is 45, which is the hyphen-minus character -.
Once again, let’s validate our progress:
Enter the password: 2pk7--AAA
[+] Yes, keep going :)
[+] Yes, keep going :)
[+] Yes, keep going :)
[+] Yes, keep going :)
[+] Yes, keep going :)
Here is your hash: 8a4fa0f6d51d678fbe4807d3208db9e633585a4a73308210b92293f9f4362442
[-] Oh no, try again :/
We now have six out of the nine characters. It feels like we’re getting close, but we still haven’t explored the SHA-256 hashing part.
The next (and last!) function call is to sub_401a50, which is a bit more complex than the ones we’ve seen so far. It starts by resetting errno, and saves input[6], input[7], and input[8] into r13, r14, and r15:
0000000000401a6c mov rbx, rdi ; make rbx point to our input, which we had in rdi so far
; skipping a few instructions...
0000000000401a82 call sub_4084d0 ; this is actually calling __errno_location()
0000000000401a87 mov dword [rax], 0x0 ; and setting errno to zero
0000000000401a8d movsx r13, byte [rbx+6] ; input[6]
0000000000401a92 mov r12, rax
0000000000401a95 movsx r14, byte [rbx+7] ; input[7]
0000000000401a9a movsx r15, byte [rbx+8] ; input[8]
It’s interesting to note the call to __errno_location(). Even though the function was not recognized by any of the tools I used for this problem, its contents give it away:
sub_4084d0:
00000000004084d0 mov rax, 0xffffffffffffffc0 ; sets rax to -64
00000000004084d7 add rax, qword [fs:0x0] ; offset it by FS
00000000004084e0 ret
The FS segment is generally used for thread-local storage, so this is returning a pointer to a thread-local variable and then setting it to zero at 0x401a87 with mov dword [rax], 0x0. This could of course be any other thread-local variable, but considering the functions called below it is highly likely to be the address of errno.
Much like for input[3] above, the function calls __ctype_b_loc to validate that the last three characters are numeric:
0000000000401aaf call sub_408650+80 ; this is __ctype_b_loc
0000000000401ab4 mov rax, qword [rax] ; rax points to the table
0000000000401ab7 test byte [rax+r13*2+1], 0x8 ; performs table[r13] & 8
0000000000401abd je loc_401cbc ; jumps out if equal to zero, so not matching
0000000000401ac3 test byte [rax+r14*2+1], 0x8 ; same for input[7]
0000000000401ac9 je loc_401cbc
0000000000401acf test byte [rax+r15*2+1], 0x8 ; same for input[8]
0000000000401ad5 je loc_401cbc
We then call the unknown function sub_4159f0 with input+6, NULL, and 10 as parameters. This is immediately followed by an error check that prints a message if strtol failed, which pretty much gives it away:
0000000000401adb lea rdi, qword [rbx+6] ; input + 6
0000000000401adf xor esi, esi ; null
0000000000401ae1 mov edx, 0xa ; 10
0000000000401ae6 call sub_4159f0 ; strtol(const char *nptr, char **endptr, int base)
0000000000401aeb mov ecx, dword [r12] ; maybe errno?
0000000000401aef mov rbx, rax ; presumably the return value is in rax
0000000000401af2 test ecx, ecx ; if non-zero (failed)
0000000000401af4 jne loc_401e28 ; jump (see below)
;
; (a large block omitted to show where we'd land with this jump)
;
loc_401e28:
0000000000401e28 lea rdi, qword [aStrtolErr] ; "strtol err: "
0000000000401e2f call sub_416ab0+352 ; perror
A long list of numeric comparisons come after the call to strtol. The program seems to be structured to make the validation intentionally complex, as the control flow graph demonstrates:
Yes, there’s a lot more. At this point I switched to Ghidra, since it was the tool that seemed to produce the cleanest output for this massive function. After cleaning it up as much as I could, I ended up with the following validation code in Python:
def validate(n):
x = 2
y = 1
calc_and_7 = ((n + 1) - 2) & 7
if calc_and_7 == 0: return False
if calc_and_7 != 1:
if calc_and_7 != 2:
if calc_and_7 != 3:
if calc_and_7 != 4:
if calc_and_7 != 5:
if calc_and_7 != 6:
x = 3
if n % 2 == 0: y = 3
if n % x == 0: y = y + x
x = x + 1
if n % x == 0: y = y + x
x = x + 1
if n % x == 0: y = y + x
x = x + 1
if n % x == 0: y = y + x
x = x + 1
if n % x == 0: y = y + x
x = x + 1
if n % x == 0: y = y + x
x = x + 1
while n + 1 != x:
z = y + x
if n % x != 0: z = y
if n % (x + 1) == 0: z = x + 1 + z
y = x + 2 + z
if n % (x + 2) != 0: y = z
if n % (x + 3) == 0: y = x + 3 + y
z = y + x + 4
if n % (x + 4) != 0: z = y
if n % (x + 5) == 0: z = x + 5 + z
y = x + 6 + z
if n % (x + 6) != 0: y = z
if n % (x + 7) == 0: y = x + 7 + y
x = x + 8
return y == 0x32a
for i in range(100, 1000): # we know it's 3 digits
if validate(i):
print('FOUND:', i)
Running this code produces two solutions, 424 and 538. But not so fast! sub_401a50 doesn’t actually end there, we see it swapping input[6] and input[8] before calling strtol again:
0000000000401ce8 movzx r8d, byte [rbp-0x52] ; r8 = input[8]
0000000000401ced movzx r11d, byte [rbp-0x54] ; r11 = input[6]
0000000000401cf2 lea rdi, qword [rbp-0x54]
0000000000401cf6 xor esi, esi
0000000000401cf8 mov edx, 0xa
0000000000401cfd mov byte [rbp-0x52], r11b ; input[8] = r11
0000000000401d01 mov byte [rbp-0x54], r8b ; input[6] = r8
0000000000401d05 call strtol
Finally, it compares the result of the first strtol with the second and jumps over the progress message if they don’t match. This means that the last 3 characters have to be a palindrome, so only 424 would be valid.
Validating the hash ¶
The sequence of validation functions that we analyzed offers a few branching points for the program to exit early. But if we make it through all of them, a hash is printed and compared to a long hex string:
0000000000400705 lea rsi, qword [aHereIsYourHash] ; "Here is your hash: %s\\n"
000000000040070c mov rdx, r12
000000000040070f mov edi, 0x1
0000000000400714 xor eax, eax
0000000000400716 call sub_453bd0+41 ; maybe prints our hash?
000000000040071b lea rdi, qword [aD867f9f78c62e0] ; constant hash
0000000000400722 mov edx, 0x40 ; 64 bytes, the length of a SHA-256 hash in hex
0000000000400727 mov rsi, r12
000000000040072a call sub_400478 ; comparison?
000000000040072f test eax, eax ; the return value is checked
0000000000400731 jne loc_400780 ; with a jump
The string referenced at 0x40071b looks like a SHA-256 hash written in hex and lowercased: "d867f9f78c62e060f741670ae2cdb4873f1645a33f13347f0bb240bc4d36f9a2".
With tight constraints on all the characters, let’s see if we can generate a password that also matches this constant:
import hashlib
def find_password():
# c0 is '2'
for c1 in map(chr, [0x70, 0x71, 0x72, 0x73]):
for c2 in map(chr, [0x6a, 0x6b, 0x6c, 0x6d, 0x6e]):
for c3 in map(chr, range(ord('0'), 1 + ord('9'))):
# c4 and c5 are both '-'
# c6, c7, c8 are '424'
password = '2' + c1 + c2 + c3 + '--' + '424'
hashed = hashlib.sha256(password.encode('utf-8')).hexdigest()
if hashed == 'd867f9f78c62e060f741670ae2cdb4873f1645a33f13347f0bb240bc4d36f9a2':
print('password found: ' + password)
And at last, we have the full password:
$ ./validate.py
password found: (redacted)
Impressions ¶
I enjoyed this crackme, it had some challenging parts without being impossible to solve. It felt good to recognize the use of isdigit that I had recently learned about, and to apply these lessons to solve this second one more quickly than I expected.
Once again Ghidra did not disappoint, and its superior decompilation abilities were very helpful. I recently bought The Ghidra Book, and am looking forward to becoming more proficient with this tool.