This is the fourth and final set of for my self-imposed challenge of completing at least fifty of the exercises on Dennis Yurichev's challenges.re by the end of the year. The previous set is available here.
We'll actually be covering twenty challenges in this one. I'd been so busy with school that I forgot to make a post when I hit forty.
Challenge #36
The description this time describes that this is "[a] well-known algorithm again. What does it do? Also, take notice that the code for x86 uses FPU, but SIMD instructions are used instead in the x64 code. That's OK."
long state = 0x12345678; float f1(void) { state = state * 0x19660d + 0x3c6ef35f; return ((float) ((state & 0x7fffff) | 0x40000000)) - 3.0f; } void f(void) { int i; int count; float a; float b; for (i = 0, count = 0; i < 1000000; i++) { a = f1(); b = f1(); if (a * a + b * b > 1.0f) { count++ } } ((float) (((double) count) * 2.25) / 10.9073486328125); }
I thought this was a lame challenge. The floating point operations of f1 have
been optimized to the point that it's unrecognizable, so if you aren't familiar
with the standard bit-twiddling tricks that GCC uses to speed up floating-point
operations, you aren't going to be able to come up with anything meaningful –
especially since neither function take parameters. My response? f returns the
constant value 206282.937500.
I thought this might be the fast inverse square root, but I don't believe it is.
Challenge #37
Ah, another challenge for which the description is that it is a "[w]ell-known function" and only x86 disassembly given is from MSVC. Fortunately, this one is not too difficult.
int f(int a, int b) { int i; int n; if (a == 0) { return b + 1; } n = b; i = a; do { if (n == 0) { n = 1; } else { n = f(i, n - 1); } } while (--i != 0); return n + 1; }
This is the Ackermann function, albeit using a loop rather than a direct translation of the Ackermann–Péter function to code.
To answer Yurichev's additional questions, a stack overflow occurs if 4 and 2 are supplied as input because those are absurd parameters for this function, and this function bears the error of not enforcing the constraints given in the definition of the Ackermann–Péter function.
Challenge #38
Fun. Another challenge provided as a binary.
jakob@Upsilon ~ $ sha256sum 17 8f73f329e0988968a9fa40f61da906e83b46817bcb5c0e93f7e95aa74c30e8e0 17 jakob@Upsilon ~ $ file 17 17: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, for GNU/Linux 2.6.18, BuildID[sha1]=bdeac54f2d98db38d7a63a43f1c41857432686c4, stripped
I stopped a bit early because, for once, the question wasn't "[w]hat does this code do?", but was instead, "[t]his program prints some information to stdout, each time different. What is that?"
#include <stdlib.h> #include <time.h> static time_t current_time; int fcn.004006c4(void) { return current_time = current_time * 0x19660d * 0x3c6ef35f; } int main(int argc, char **argv) { char *s2; void **s1; int var_1ch; int var_18h; int var_11h; s2 = malloc(230); s1 = malloc(80); var_1ch = 0; while (var_1ch <= 9) { s1[var_1ch++] = calloc(230, 1); } current_time = time(NULL); var_1ch = 0; while (var_1ch <= 230) { var_11h = fcn.00400b60(fcn.004006c4()); s2[var_1ch++] = var_11h & 1; } var_1ch = 0; while (1) { fcn.00400970(s2, 230); fcn.0040072a(s2, 230, 110); var_18h = 0; while (var_18h <= 8) { if (!memcmp(s1[var_18h++], s2, 230)) { exit(0); } } var_18h = 0; while (var_18h <= 8) { memcpy(s1[var_18h], s1[++var_18h], 230); } memcpy(s1[9], s2, 230); var_1ch++; } }
The only nondeterminism I saw in the disassembly was from time. The actual
output of the program is incomprehensible – appearing to be some sort of
ASCII-art fractal. For this reason, I'm concluding that the information printed
to stdout is the current time.
Challenge #39
The description for this challenge got me excited. "This program requires a password. Find it."
jakob@Upsilon ~ $ sha256sum password2 8c8365f316de896c453511c5f484755600208b87ad0f1595a2900cbf5a36db24 password2
main is simple enough that I feel I can omit the: it reads in a password with
scanf, and then checks it with the following snippet.
│ 0x0804853e e87affffff calll fcn.080484bd │ 0x08048543 3df8010000 cmpl $0x1f8, %eax ; 504
We want to find some password such that fcn.080484bd(password) = 0x1f8.
Peeking into fcn.080484bd, I was a little disappointed.
┌ (fcn) fcn.080484bd 46 │ fcn.080484bd (int32_t arg_8h); │ ; var int32_t var_4h @ ebp-0x4 │ ; arg int32_t arg_8h @ ebp+0x8 │ ; CALL XREF from main @ 0x804853e │ 0x080484bd 55 pushl %ebp │ 0x080484be 89e5 movl %esp, %ebp │ 0x080484c0 83ec10 subl $0x10, %esp │ 0x080484c3 c745fc000000. movl $0, var_4h │ ┌─< 0x080484ca eb10 jmp 0x80484dc │ │ ; CODE XREF from fcn.080484bd @ 0x80484e4 │ ┌──> 0x080484cc 8b4508 movl arg_8h, %eax ; [0x8:4]=-1 ; 8 ; edx │ ╎│ 0x080484cf 0fb600 movzbl 0(%eax), %eax │ ╎│ 0x080484d2 0fbec0 movsbl %al, %eax │ ╎│ 0x080484d5 0145fc addl %eax, var_4h │ ╎│ 0x080484d8 83450801 addl $1, arg_8h ; [0x8:4]=-1 ; 1 │ ╎│ ; CODE XREF from fcn.080484bd @ 0x80484ca │ ╎└─> 0x080484dc 8b4508 movl arg_8h, %eax ; [0x8:4]=-1 ; 8 ; edx │ ╎ 0x080484df 0fb600 movzbl 0(%eax), %eax │ ╎ 0x080484e2 84c0 testb %al, %al │ └──< 0x080484e4 75e6 jne 0x80484cc ; likely │ 0x080484e6 8b45fc movl var_4h, %eax ; edx │ 0x080484e9 c9 leave ; edx └ 0x080484ea c3 retl ; edx
Do I even need to provide a C translation? The disassembly should be glaringly obvious: this "check" function just returns the sum of the string argument's individual bytes. Coming up with a valid password is trivial.
jakob@Upsilon ~ $ ./password2 enter password: AAAAAAA1 password is correct
The problem also suggests that I "try to change the password by patching the
executable file," but this doesn't invokve anything more than changing the word
at 0x08048544.
Challenge #41
The question this time is: "[t]his program prints some numbers to stdout. What is it?"
jakob@Upsilon ~ $ file problem problem: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, for GNU/Linux 2.6.24, BuildID[sha1]=a89ecf1ae2f2474548d09ca3ebccd7db4162fa1e, stripped jakob@Upsilon ~ $ sha256sum problem ab3864e8fceeffe4b166cb7481332e88a1fe90b6a406e635c6921119c91a00fd problem
I wrote a C translation without running the program. In retrospect, this wasn't
a bad idea. The calculation is a function of some integer, but the binary spits
out subsequent numbers with no sort of delimitation. Having the C translation
means that I could add a printf("\n"); after the call to fcn_00400536(var_4h++);
and get output similar to the following:
jakob@Upsilon ~ $ /tmp/test 1 2 1 3 10 5 16 8 4 2 1 4 2 1 5 16 8 4 2 1
Here's the C translation.
void fcn_00400536(int a) { printf("%d\n", a); while (a != 1) { if (a & 1 != 0) { a = a * 3 + 1; } else { a >>= 1; } printf("%d\n", a); } } int main(int argc, char **argv) { int var_4h; var_4h = 1; while (var_4h <= 15) { fcn_00400536(var_4h++); } return var_4h; }
We can pick any interesting sequence and plug it into OEIS, which identifies
fcn_00400536 as "A070165: Irregular triangle read by rows giving trajectory of n
in Collatz problem." Ah, yes. This is looking familiar now. This is the famously
unsolved problem in mathematics, the Collatz conjecture.
Challenge #43
jakob@Upsilon ~ $ file unknown_utility_2_3 unknown_utility_2_3: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), dynamically linked, interpreter /lib/ld-linux.so.2, for GNU/Linux 2.6.24, BuildID[sha1]=cb74037dd37694879f6250bfb5623c273ef68ca6, stripped jakob@Upsilon ~ $ sha256sum unknown_utility_2_3 9d3df3be78f21971059ba2d9973a1358865ccbe2f47f78fc5800779d6f6083fe unknown_utility_2_3
I really wasn't feeling it today, so I took the easy way out and just ran the binary provided on a test file. It spits out a floating point number, which seems to decrease as the file becomes less interesting. Just a hunch, but maybe it's binary entropy?
jakob@Upsilon ~ $ python -c "print('a' * 256)" > test.txt
jakob@Upsilon ~ $ ./unknown_utility_2_3 test.txt
0.036753
jakob@Upsilon ~ $ rahash2 -a entropy test.txt
test.txt: 0x00000000-0x00000100 entropy: 0.03675295
jakob@Upsilon ~ $ dd bs=256 count=1 if=/dev/urandom > test.txt
1+0 records in
1+0 records out
256 bytes copied, 7.0438e-05 s, 3.6 MB/s
jakob@Upsilon ~ $ ./unknown_utility_2_3 test.txt
7.069718
jakob@Upsilon ~ $ rahash2 -a entropy test.txt
test.txt: 0x00000000-0x000000ff entropy: 7.06971784
Well, that's an answer I'm certainly happy with.
Challenge #48
It looks like we're starting to get into the realm of win32. The question for
this challenge is, "[w]hat does this win32-function do?"
main: push 0xFFFFFFFF call MessageBeep xor eax,eax retn
This is pretty simple. It's a wrapper for MessageBeep. According to MSDN, the
0xFFFFFFFF parameter produces "[a] simple beep. If the sound card is not
available, the sound is generated using the speaker."
Challenge #49
Another rather simple one. The disassembly for this challenge is given in AT&T syntax, which is my preferred way of reading x86 assembly.
main: pushq %rbp movq %rsp, %rbp movl $2, %edi call sleep popq %rbp ret
A wrapper around sleep, presumably the only provided by unistd.h, calling it
with an argument of two seconds.
Challenge #52
Another simple disassembly:
$SG3103 DB '%d', 0aH, 00H _main PROC push 0 call DWORD PTR __imp___time64 push edx push eax push OFFSET $SG3103 ; '%d' call DWORD PTR __imp__printf add esp, 16 xor eax, eax ret 0 _main ENDP
To copy straight from MSDN, this prints the number of "seconds elapsed since midnight (00:00:00), January 1, 1970, Coordinated Universal Time (UTC)."
MSDN also answers the follow-up question: "time is a wrapper for _time64 and
time_t is, by default, equivalent to __time64_t. If you need to force the
compiler to interpret time_t as the old 32-bit time_t, you can define
_USE_32BIT_TIME_T. This is not recommended because your application may fail
after January 18, 2038; the use of this macro is not allowed on 64-bit
platforms."
Challenge #53
I thought this was an interesting challenge. "This code, compiled in Linux x86-64 using GCC is crashing while execution (segmentation fault). It's also crashed if compiled by MinGW for win32. However, it works in Windows environment if compiled by MSVC 2010 x86. Why?"
#include <string.h> #include <stdio.h> void alter_string(char *s) { strcpy (s, "Goodbye!"); printf ("Result: %s\n", s); }; int main() { alter_string ("Hello, world!\n"); };
The code is modifying a string constant, which GCC tends to put in a read-only
memory segment (.rodata) in the resultant executable. Writing to a read-only
memory segment will cause a segmentation fault. I haven't tested it, but the
question statement makes me think that MSVC puts string constants in a writable
segment, so this would work just fine.
Challenge #54
No disassembly is given for this challenge. The only thing on the page is "[w]hy
isn't the x86 LOOP instruction used by modern compilers anymore?" Some searching
yields this Stack Overflow answer. Basically, loop is from the time before x86
became horribly complex, and so on modern processors, it's slow.
Challenge #56
I decided to skip challenge #55, as it would really just be a walkthrough of which r2 commands I used. Challenge #56 is not particularly difficult. I went along with the disassembly from MSVC.
#include <stdio.h> int main(void) { int n; n = 100; do { printf("%d", n); } while (n-- != 0); return 0; }
The code prints the integers from 100 to 0.
Challenge #57
This is almost the same disassembly as last time.
#include <stdio.h> int main(void) { int n; n = 1; do { printf("%d", n); n += 3; } while (n < 100); return 0; }
Challenge #58
This time, we're fortunate enough to be given a disassembly from GCC 4.8.1,
albeit with -O3.
int f(char *a) { int count; count = 0; while (*a != '\0') { if (*a++ == ' ') { count++; } } return count; }
f counts the number of spaces in a given string. As an aside, when I was first
learning to read assembly, I recall someone describing -O3 as "unintelligible to
humans." The more reverse engineering I've done, the more I've realized that the
optimizations at that level tend to not be as absurd as people make them out to
be. I considered this to be an easy challenge.
Challenge #59
This one was really easy.
_a$ = 8 _f PROC mov ecx, DWORD PTR _a$[esp-4] lea eax, DWORD PTR [ecx*8] sub eax, ecx ret 0 _f ENDP
The function just returns a * 7. I suspect the multiplication followed by
subtraction was an optimization, since multiplication by a power of two can be
implemented as a left shift.
Challenge #61
Perhaps the most difficult part of this challenge was going out my way to ensure that the constant really was 5.0.
double f(double a, double b, double c, double d, double e) { return (a + b + c + d + e) / 5; }
f simply averages five numbers.
Challenge #62
The challenge notes that the compiler was optimizing for space, which may explain the pointless nested loop.
void f(float *a, float *b, float *c) { int i; int j; long coffee; long cake; coffee = a - b; cake = c - b; for (i = 200; i > 0; i--) { for (j = 100; j > 0; j--) { b[cake] = b[0] + b[coffee]; b += 8; } } }
f adds 20000 elements from a and b, storing their sums in c.
Challenge #64
I was swamped with preparing for finals this weekend, so I decided to skip challenge #63 in favor of something less arduous. The question for this one is, "[a]n array of array[x][y] form is accessed here. Try to determine the dimensions of the array, at least partially, by finding y."
double f(double *array, int x, int y) { return array[y + x * 15]; }
The array has some number of rows each containing 15 elements.
Challenge #65
The question here is the same as the previous challenge.
int f(int *array, int x, int y, int z) { return array[z + 5 * 16 * (y + 4 * 15 * x)]; }
Assuming an array of integers, the dimensions of the array are 15 x 20 x …
Challenge #74
I skipped way ahead this time because I was done with finals and knew that this was the last of the challenges I'd be doing this year. So I looked through what remained in search of something difficult, but interesting, and settled on this one.
We're given a binary,
jakob@Epsilon ~ $ sha256sum challenge74 6d2ac11d1e6200d6a2cca988189764b6acdb7811d24619e8e66f1796c8c27394 challenge74 jakob@Epsilon ~ $ file challenge74 challenge74: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, for GNU/Linux 2.6.24, BuildID[sha1]=7fa3bd4aa738bced5aaccb161090818646e07704, stripped
as well as a few valid keys.
2Z7A7-EK270-TMHR4-BHC71-CEB52-HELL0-HELL0-EONP9 2Z7A7-6I7R9-MZGO9-FDQJ3-JN0Q6-HELL0-HELL0-72KJ9
I took this as an opportunity to try out the r2ghidra-dec plugin for Radare. Let's see how it does.
// WARNING: Could not reconcile some variable overlaps // WARNING: [r2ghidra] Detected overlap for variable var_20h// WARNING: [r2ghidra] Failed to match type signed int64_t for variable var_10h to Decompiler type: Unknown type // identifier signed // WARNING: [r2ghidra] Detected overlap for variable var_ch // WARNING: [r2ghidra] Failed to match type signed int64_t for variable var_8h to Decompiler type: Unknown type // identifier signed // WARNING: [r2ghidra] Detected overlap for variable var_8h // WARNING: [r2ghidra] Failed to match type signed int for variable var_4h to Decompiler type: Unknown type identifier // signed // WARNING: [r2ghidra] Detected overlap for variable var_4h // WARNING: [r2ghidra] Detected overlap for variable var_bh undefined8 main(uint32_t argc, char **argv) { int64_t iVar1; char cVar2; int32_t iVar3; int64_t in_FS_OFFSET; int64_t var_30h; int64_t var_24h; int64_t var_8h; iVar1 = *(int64_t *)(in_FS_OFFSET + 0x28); var_24h._0_4_ = argc; sym.imp.puts("Crackme/keygenme by Dennis Yurichev, http://challenges.re/74"); sym.imp.putchar(10); if ((uint32_t)var_24h == 1) { sym.imp.puts("Command line: <serial number>"); // WARNING: Subroutine does not return sym.imp.exit(0); } iVar3 = sym.imp.memcmp(argv[1] + 0x1e, "HELL0-HELL0", 0xb); if (iVar3 != 0) { sym.imp.puts("SN format is incorrect"); // WARNING: Subroutine does not return sym.imp.exit(0); } iVar3 = fcn.00400bb5((int64_t)argv[1], (int64_t)&var_24h + 4); if (iVar3 == -1) { sym.imp.puts("SN format is incorrect"); // WARNING: Subroutine does not return sym.imp.exit(0); } cVar2 = fcn.0040085e((void *)((int64_t)&var_24h + 4)); if (cVar2 == '\0') { sym.imp.puts("SN is not valid"); } else { sym.imp.puts("SN valid"); } if (iVar1 != *(int64_t *)(in_FS_OFFSET + 0x28)) { // WARNING: Subroutine does not return sym.imp.__stack_chk_fail(); } return 0; }
When I saw this, I was blown away. Damn. The NSA did a great job with this. Here's my cleaned up version.
#include <stdint.h> int main(int argc, char **argv) { char buf[24]; printf("Crackme/keygenme by Dennis Yurichev, http://challenges.re/74\n\n"); if (argc == 1) { puts("Command line: <serial number>"); exit(0); } if (memcmp(argv[1] + 0x1e, "HELL0-HELL0", 0xb)) { puts("SN format is incorrect"); exit(0); } if (fcn_00400bb5(argv[1], buf) == -1) { puts("SN format is incorrect"); exit(0); } if (fcn_0040085e(buf) == '\0') { puts("SN is not valid"); } else { puts("SN valid"); } return 0; }
Aside from getting rid of temporary variables, I removed iVar1 as it's no more
than a stack canary, and I fixed up a few "errors" that the decompiler made. As
an example, notice that strange assignment to var_24h._0_4_? Let's see what the
disassembly says.
pushq %rbp movq %rsp, %rbp subq $0x30, %rsp movl %edi, var_24h ; argc movq %rsi, var_30h ; argv
This is the only write to var_24h, so the line should have been var_24h = argv.
For some reason, the decompiler saw this as assignment to a struct field. I
ended up removing it anyway. Using 'argc' is clearer.
There's also that odd (void *)((int64_t)&var_24h + 4), but if we look at the
disassembly,
leaq var_20h, %rdx movq %rdx, %rsi movq %rax, %rdi callq fcn.00400bb5 ... leaq var_20h, %rax movq %rax, %rdi callq fcn.0040085e
So that should've just been var_20h in the decompilation. Regardless, I'm
impressed. And I have to say, as a plugin, r2ghidra is really good. pdg takes a
few seconds, but if you rename some variables with afvn and run it again, it
spits out the updated version instantly, which makes me think that it's probably
doing some sort of caching and quick substitution.
Anyway, back to the challenge. We can tell from the decompilation already that
the sixth and seventh components must be "HELL0-HELL0". It also has to contain
eight components, delimited by '-', as we can see from fcn_00400bb5:
var_10h._0_4_ = 0; while ((int32_t)var_10h < 7) { if (*(char *)(arg1 + (int64_t)((int32_t)var_10h * 6) + 5) != '-') { return 0xffffffff; } var_10h._0_4_ = (int32_t)var_10h + 1; }
Here's the gist of the key verification algorithm:
fcn_00400bb5parses the key into a buffer (I renamed this toparse_key)- Calls out to a
charcodefunction which maps numerals to their numeric values ('0' becomes 0) and letters 'A' through 'Z' to 10-35. - The buffer is written with 3 bytes per component. I thought this was a decompiler mistake at first, but I checked the disassembly and it really is 3 bytes per component. 24 bytes total.
- Calls out to a
fcn_0040085edoes further verification and enables features based on the parsed key (I renamed this toenable_features).- The resultant parsed buffer needs to start with 0xdeadbabe.
- The 4th and 5th bytes give a numerical year, the 6th a numerical month, and
the 7th a numerical day.
- There's a sanity checks to ensure that the day is between 1 and 31, that the month is between 1 and 12, and that the year is between 2016 and 2101.
- The 7th bit of byte 8 enables feature A
- The 1st bit of byte 9 enables feature B
- The 2nd bit of byte 10 enables feature C
- The 4th bit of byte 11 enables feature D
- The 1st bit of byte 12 enables feature E
- There's one final check of the last 8 bytes against a
checksumfunction.
#include <stdint.h> uint64_t checksum(int64_t init, char *parsed, int64_t length) { uint64_t ret; char *cur; int i; int j; cur = parsed; ret = ~init; i = length; while (i != 0) { ret = ret ^ (uint64_t) *cur; j = 0; while (i--, cur++, j < 8) { if ((ret & 1) == 0) { ret = ret >> 1; } else { ret = ret >> 1 ^ 0x42f0e1eb0badbad0; } j++; } } return ~ret; }
I actually didn't realize that last part until I'd already hacked together a quick key verifier.
(use-package :cl-utilities) (defun charcode (c) (let ((value (char-code c))) (cond ((<= (char-code #\0) value (char-code #\9)) (- value #x30)) ((<= (char-code #\A) value (char-code #\Z)) (- value #x37))))) (defun hash-component (component) (let* ((characters (coerce component 'list)) (values (mapcar #'charcode characters))) (unless (or (/= 5 (length values)) (find nil values)) (+ (* #x000001 (nth 0 values)) (* #x000024 (nth 1 values)) (* #x000510 (nth 2 values)) (* #x00b640 (nth 3 values)) (* #x19a100 (nth 4 values)))))) (defun parse-key (key) (reduce #'append (mapcar #'(lambda (component) (let ((hash (hash-component component))) (list (logand hash #xff) (logand (ash hash -8) #xff) (logand (ash hash -16) #xff)))) (split-sequence #\- key)))) (defun key-valid-p (key) ;; Must begin with 0xdeadbabe, and have HELL0 for components 6 and 7. (and (equal (subseq key 0 4) '(222 173 186 190)) (equal (subseq key 15 21) '(153 95 15 153 95 15)))) (defun key-attributes (key) (let ((parsed (parse-key key))) (list :valid (key-valid-p parsed) :expiry-year (logior (ash (nth 4 parsed) 8) (nth 5 parsed)) :expiry-month (nth 6 parsed) :expiry-day (nth 7 parsed) :feature-a (plusp (logand (nth 8 parsed) (ash 1 6))) :feature-b (plusp (logand (nth 9 parsed) (ash 1 0))) :feature-c (plusp (logand (nth 10 parsed) (ash 1 1))) :feature-d (plusp (logand (nth 11 parsed) (ash 1 2))) :feature-e (plusp (logand (nth 12 parsed) (ash 1 0)))))) (key-attributes "2Z7A7-EK270-TMHR4-BHC71-CEB52-HELL0-HELL0-EONP9") ;; (:VALID T :EXPIRY-YEAR 2053 :EXPIRY-MONTH 5 :EXPIRY-DAY 22 :FEATURE-A T ;; :FEATURE-B T :FEATURE-C T :FEATURE-D T :FEATURE-E NIL) (key-attributes "2Z7A7-6I7R9-MZGO9-FDQJ3-JN0Q6-HELL0-HELL0-72KJ9") ;; (:VALID T :EXPIRY-YEAR 2042 :EXPIRY-MONTH 2 :EXPIRY-DAY 21 :FEATURE-A T ;; :FEATURE-B T :FEATURE-C T :FEATURE-D T :FEATURE-E T)
We can verify our results.
jakob@Epsilon ~ $ ./challenge74 "2Z7A7-EK270-TMHR4-BHC71-CEB52-HELL0-HELL0-EONP9" Crackme/keygenme by Dennis Yurichev, http://challenges.re/74 Expiration date: 2053-05-22 Feature A: ON Feature B: ON Feature C: ON Feature D: ON Feature E: OFF SN valid jakob@Epsilon ~ $ ./challenge74 "2Z7A7-6I7R9-MZGO9-FDQJ3-JN0Q6-HELL0-HELL0-72KJ9" Crackme/keygenme by Dennis Yurichev, http://challenges.re/74 Expiration date: 2042-02-21 Feature A: ON Feature B: ON Feature C: ON Feature D: ON Feature E: ON SN valid
But, as I mentioned, I'd missed the checksum, so we'll need to deal with that in developing a keygen. What makes this so difficult is that the bytes of the checksum are incorporated in the checksum value. So, I thought this might be an opportunity to add something else to my toolbox: the Z3 Theorem Prover.
I'd never used it before, but it seems to show up in CTF writeups quite frequently. I did a bit of reading (this, this and this) and put together this:
from z3 import * s = Solver() def checksum(init, key): result = BitVecVal(~init, 64) for byte in key: result ^= ZeroExt(56, byte) for i in range(8): result = (result >> 1 & 0x7fffffffffffffff) ^ (0x42f0e1eb0badbad0 * (result & 1)) result = ~result return result def unpack(word): result = BitVecVal(0, 64) result |= ZeroExt(56, word[0]) result |= ZeroExt(56, word[1]) << 8 result |= ZeroExt(56, word[2]) << 16 result |= ZeroExt(56, word[3]) << 24 result |= ZeroExt(56, word[4]) << 32 result |= ZeroExt(56, word[5]) << 40 result |= ZeroExt(56, word[6]) << 48 result |= ZeroExt(56, word[7]) << 56 return result key = [BitVec("bv{}".format(i), 8) for i in range(24)] FEATURE_A = False FEATURE_B = False FEATURE_C = False FEATURE_D = False FEATURE_E = False s.add(key[0] == 222) s.add(key[1] == 173) s.add(key[2] == 186) s.add(key[3] == 190) s.add(key[4] == ((2019 & 0xff00) >> 8)) s.add(key[5] == 2019 & 0x00ff) s.add(key[6] == 12) s.add(key[7] == 25) s.add(key[8] & 0b100000 == (1 if FEATURE_A else 0)) s.add(key[9] & 0b000001 == (1 if FEATURE_B else 0)) s.add(key[10] & 0b000010 == (1 if FEATURE_C else 0)) s.add(key[11] & 0b001000 == (1 if FEATURE_D else 0)) s.add(key[12] & 0b000001 == (1 if FEATURE_E else 0)) s.add(key[15] == 153) s.add(key[16] == 95) s.add(key[17] == 15) s.add(key[18] == 153) s.add(key[19] == 95) s.add(key[20] == 15) s.add(unpack(key[16:]) == checksum(0, key)) s.check() print(s.model())
Accurately translating the checksum function was a pain in the tuckus. The right
shift was giving me a hard time since the Z3 right shift doesn't prepend with
zeroes. The & 0x7fffffffffffffff is my attempt at dealing with that.
As an aside, I just want to say that GDB's call functionality is godsend. It
made verifying my translation so much easier.
(gdb) p (unsigned long long) $checksum(0, &{'\xff', '\xff', '\xff'}, 3)
$14 = 18446742974197923840
So, I let this run overnight, which brought me back to when I was more active with CTF and would let my half-complete solutions run while I slept.
jakob@Epsilon ~ $ python solver.py [bv22 = 196, bv13 = 18, bv21 = 216, bv23 = 130, bv14 = 209, bv8 = 130, bv10 = 108, bv9 = 170, bv11 = 208, bv12 = 240, bv20 = 15, bv19 = 95, bv18 = 153, bv17 = 15, bv16 = 95, bv15 = 153, bv7 = 24, bv6 = 12, bv5 = 227, bv4 = 0, bv3 = 190, bv2 = 186, bv1 = 173, bv0 = 222]
This was waiting for me when I got back from the gym the next morning.
(string-join
(mapcar #'ahash-component-inverse
(mapcar #'triplet-to-number '((222 173 186)
(190 0 27)
(12 24 13)
(170 108 208)
(240 18 20)
(153 95 15)
(153 95 15)
(216 196 130))))
"-")
CL-USER> (string-join
(mapcar #'ahash-component-inverse
(mapcar #'triplet-to-number '((222 173 186)
(190 0 27)
(12 24 13)
(170 108 208)
(240 18 20)
(153 95 15)
(153 95 15)
(216 196 130))))
"-")
"2Z7A7-AHX11-S4EI0-6LR48-K37S0-HELL0-HELL0-KPO35"
CL-USER> (key-attributes "2Z7A7-AHX11-S4EI0-6LR48-K37S0-HELL0-HELL0-KPO35")
(:VALID NIL :EXPIRY-YEAR 27 :EXPIRY-MONTH 12 :EXPIRY-DAY 24 :FEATURE-A NIL
:FEATURE-B NIL :FEATURE-C NIL :FEATURE-D NIL :FEATURE-E NIL)
Oh no…
... s.add(key[4] == 2019 & 0xff00) ...
That should've been s.add(key[4] = ((2019 & 0xff00) >> 8))=…
;-;
Let's try this again.
jakob@Epsilon ~ $ python solver.py [bv22 = 80, bv13 = 39, bv21 = 204, bv23 = 133, bv14 = 124, bv8 = 140, bv10 = 12, bv9 = 168, bv11 = 183, bv12 = 184, bv20 = 15, bv19 = 95, bv18 = 153, bv17 = 15, bv16 = 95, bv15 = 153, bv7 = 25, bv6 = 12, bv5 = 227, bv4 = 7, bv3 = 190, bv2 = 186, bv1 = 173, bv0 = 222]
This time it actually ran for a whole two days.
CL-USER> (mapcar #'hash-component-inverse
(mapcar #'triplet-to-number
'((222 173 186)
(190 7 227)
(12 25 140)
(168 12 183)
(184 39 124)
(153 95 15)
(153 95 15)
(204 80 133))))
("2Z7A7" "YFWU8" "CGSG5" "CF457" "K9EU4" "HELL0" "HELL0" "OH975")
CL-USER> (key-attributes "2Z7A7-YFWU8-CGSG5-CF457-K9EU4-HELL0-HELL0-OH975")
(:VALID T :EXPIRY-YEAR 2019 :EXPIRY-MONTH 12 :EXPIRY-DAY 25 :FEATURE-A NIL
:FEATURE-B NIL :FEATURE-C NIL :FEATURE-D NIL :FEATURE-E NIL)
jakob@Epsilon ~ $ ./challenge74 "2Z7A7-YFWU8-CGSG5-CF457-K9EU4-HELL0-HELL0-OH975"
Crackme/keygenme by Dennis Yurichev, http://challenges.re/74
Expiration date: 2019-12-25
Feature A: OFF
Feature B: OFF
Feature C: OFF
Feature D: OFF
Feature E: OFF
SN valid
There we go. A working keygen! (Provided you're willing to wait).
An End-of-Year Reflection
This was fun, but I think in planning this out, I should have preferred depth over breadth, like getting through some of the challenges on reversing.kr. The challenges I got the most out of were the ones I had to spend more than a day reversing. Another thing that made regret the choice of Dennis Yurichev's challenges is the significance of context in reverse engineering. Most of these challenges give little more than a disassembly. There are exceptions – challenge #33, for example, was one I was able to solve because the description said that it was a cryptographic function. But for the most part, I think being able to see the "big picture" would have been a more realistic way to practice my reverse engineering chops.
One idea I've been toying with is putting out a crackme on a monthly basis. Infrequent enough that it wouldn't be overwhelming, and I'd be able to make it a sizeable challenge. I'd be able to give out hints every week, and post the solution at the end of the month. Actually, I may do this through the wargames site we're putting together at university. Stay tuned!
Comment form