home

Writeups for Dennis Yurichev's Reverse Engineering Challenges (#36-#74)

December 29, 2019 ❖ Tags: writeup, reverse-engineering, x86

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_00400bb5 parses the key into a buffer (I renamed this to parse_key)
    • Calls out to a charcode function 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.
  • fcn_0040085e does further verification and enables features based on the parsed key (I renamed this to enable_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 checksum function.
#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!

Webmentions for this Page