#+TITLE: Writeups for Dennis Yurichev's Reverse Engineering Challenges (#23-#35) #+DATE: <2019-08-18 Sun 10:42> #+TAGS: writeup reverse-engineering x86 This is the third set of solutions for my self-imposed challenge of completing at least fifty of the exercises on Dennis Yurichev's [[https://challenges.re][challenges.re]] by the end of the year. The previous set is available [[http:///jakob.space/challenges-re-writeups-2.html][here]]. * Challenge #23 The problem is prefaced with, "[t]his is another implementation of a well-known library function, works only in a 64-bit environment." Translating the disassembly directly to C reveals unrolled loops, but the intent isn't too difficult to figure out. #+BEGIN_SRC c int f(char *a) { int i; if (a[0] == '\0') { return 0; } if (a[1] == (char) 0xff) { return 1; } if (a[2] == (char) 0xff) { return 2; } if (a[3] == (char) 0xff) { return 3; } if (a[4] == (char) 0xff) { return 4; } if (a[5] == (char) 0xff) { return 5; } i = 0; while (a[6] != (char) 0xff) { if (a[7] == (char) 0xff) { return i + 7; } i += 8; a += 8; if (a[1] == (char) 0xff) { return i; } if (a[1] == (char) 0xff) { return i + 1; } if (a[2] == (char) 0xff) { return i + 2; } if (a[3] == (char) 0xff) { return i + 3; } if (a[4] == (char) 0xff) { return i + 4; } if (a[5] == (char) 0xff) { return i + 5; } } return i + 6; } #+END_SRC =f= returns the index of the first occurrence of =0xff= in =a=. In addition to asking for the purpose of the code, the challenge poses a few additional questions. First: "The code may crash under some specific circumstances. Which are...?" =f= will crash in the case that there isn't a 0xff character in the string. Second: "The code can be easily optimized using SSEx. How?" =movq= can be used to dereference the characters of =a=, and the location of the =0xff= character can be found using =pcmpeqb=. Actually implementing this is left as an exercise to the reader. And I'm not saying that just because writing SIMD by hand makes me want to break down and cry... or anything like that... Finally: "The code will not work correctly on big-endian architectures. How to fix it?" In the disassembly, the LSB of =rdx= (=dl=) is treated as the _first_ character in the sliding window. On a big-endian system, dereferencing the window as an integer would mean that the LSB would correspond with the _last_ character in the window. To fix this, you would need to change which parts of the register are being looked at. I realize that's a rather anemic answer, but the alternative would be going all-in and implementing =f= on a big-endian platform, which I don't really want to do right now. * Challenge #26 I decided to skip challenges #24 and #25 as they were listed as "Level 2" and "Level 3" respectively in terms of difficulty. Challenge #25 in particular seemed particularly demanding. Challenge #26, on the other hand, was a relatively straightforward bytecode reverse engineering task. Like Challenge #14, disassemblies for both .NET and the JVM are given, and as I'm more familiar with Java than C# (unfortunately), that's the disassembly I chose to work with. #+BEGIN_SRC java public static byte f(byte a) { return (byte) ((((long) a * 8623620610L) & 1136090292240L) % 1023L); } #+END_SRC Again, I'm not familiar with JVM bytecode, so I broke out [[https://en.wikipedia.org/wiki/Java_bytecode_instruction_listings][my favorite JVM reference]]. Here are the instructions we're concerned with: #+BEGIN_SRC java iload_0 // load an int value from local 0 i2l // convert an int to a long l2i // convert a long to an int i2b // convert an int to a byte ldc2_w // push a constant onto the stack lmul // multiply two longs land // perform a bitwise and on two longs lrem // perform remainder division on two longs #+END_SRC Even if you don't know how the JVM works, I think the purpose of =f= is fairly clear as soon as you know what those few instructions do. I've typically been using Matt Godbolt's amazing [[https://godbolt.org/][Compiler Explorer]] to check my solutions, but this time around I used [[http://javabytes.io/][Javabytes]]. The disassembly of my translation for =f= matches what was given for the challenge, so I'm quite confident in my answer. As for what it does: I began my analysis as I typically do, giving the function some test values and observing the output. #+BEGIN_SRC java public static void main(String[] args) { for (int i = 0; i < 256; i++) { System.out.printf("%3i: b\n", i, f((byte) i)); } } // 0: 0 // 1: -128 // 2: 64 // 3: -64 // 4: 32 // ... // 253: 63 // 254: -65 // 255: 127 #+END_SRC That isn't very telling, but the oscillating sign gives me an idea. #+BEGIN_SRC java public static String toPaddedBinary(byte a) { String s = String.format("%8s", Integer.toBinaryString(a)); s = s.replace(' ', '0'); return s.substring(s.length() - 8, s.length()); } public static void main(String[] args) { for (int i = 0; i < 256; i++) { System.out.printf("%s: %s\n", toPaddedBinary((byte) i), toPaddedBinary(f((byte) i))); } } // 00000000: 00000000 // 00000001: 10000000 // 00000010: 01000000 // ... // 11111101: 10111111 // 11111110: 01111111 // 11111111: 11111111 #+END_SRC So =f= reverses the bits of =a=. * Challenge #27 This challenge threw me for a bit of a loop, as it didn't give the usual amd64 output from GCC 4.9. Rather an i386 disassembly from MSVC 2010 was given, alongside an arm64 disassembly from GCC 4.9. I tried both, but had some significant trouble with the MSVC disassembly as it seemed to be dealing with 64-bit integers on a 32-bit architecture. After quickly reviewing CDOT's [[https://wiki.cdot.senecacollege.ca/wiki/Aarch64_Register_and_Instruction_Quick_Start#General-Purpose_Registers][AArch64 reference]] to get an idea of register widths, this is the translation came up with: #+BEGIN_SRC c int f(int a) { return (((int) (((long) a * 0xc64b2279) >> 32)) + a) >> 9 - (a >> 31); } #+END_SRC I'm not particularly confident in this, however, as the behavior of =f= is to return \(floor(a / 289)\). I suspect my poor understanding of the [[http://infocenter.arm.com/help/topic/com.arm.doc.dui0068b/CIHBEAGE.html][flexible second operand]] (i.e. in =sub w0, w1, w0, asr 31=) is what gave me me the most trouble. Perhaps this is a challenge I should return to when I properly learn ARM. I tried a more direct translation to Python, #+BEGIN_SRC python def test_f(a): result = a * 0xc64b2279 upper = result & 0xffffffff00000000 lower = result & 0xffffffff return ((upper + lower) >> 9) + \ (((upper + lower) >> 9) >> 31) fmt = lambda n: bin(n)[2:].rjust(32, '0') for i in range(256): print("{}\n{}\n".format(fmt(i), fmt(test_f(i)))) #+END_SRC which didn't yield any recognizable patterns. Actually, before implementing it in Python, I implemented it in Emacs Lisp (I might have been waiting on Python to compile? I don't remember). #+BEGIN_SRC elisp (defun test-f (a) (let* ((result (* a #xc64b2279)) (upper (logand result #xffffffff00000000)) (lower (logand result #xffffffff))) (+ (ash (+ upper lower) 9) (ash (ash (+ upper lower) 9) 31)))) #+END_SRC Either way, this challenge wasn't fruitful. * Challenge #28 I suspect that this challenge was made a bit easier by GCC's optimizations. The amd64 disassembly includes two unused functions, =f2= and =my_memdup= -- they're used in some of the other disassemblies, but I chose to ignore them. #+BEGIN_SRC c #include #include int f1(int *a, int *b) { return *a > *b ? 0 : -1; } int f_main(void *src, int n) { int tmp; char *dst; dst = malloc(n * sizeof(int)); memcpy(dst, src, n * sizeof(int)); qsort(dst, n, sizeof(int), f1); if (n > 1) { tmp = dst[n >> 1] + \ dst[n >> 1 - 1]; return (tmp + (tmp >> 31)) >> 1; } return dst[0]; } #+END_SRC I've started to see this =(tmp + (tmp >> 31)) >> 1= idiom rather frequently, so I decided to finally look it up, coming across [[https://stackoverflow.com/questions/40638335/why-does-the-compiler-generate-a-right-shift-by-31-bits-when-dividing-by-2][this]] Stack Overflow answer. I'm glad I did, because realizing that it carries out signed integer division by two makes this exercise far more clear. #+BEGIN_SRC c #include #include int f1(int *a, int *b) { return *a > *b ? 0 : -1; } int f_main(void *src, int n) { char *dst; dst = malloc(n * sizeof(int)); memcpy(dst, src, n * sizeof(int)); qsort(dst, n, sizeof(int), f1); if (n > 1) { return (dst[n / 2] + dst[n / 2 - 1]) / 2; } return dst[0]; } #+END_SRC =f_main= returns the [[https://en.wikipedia.org/wiki/Median][median]] of a set of values. * Challenge #30 I have, once again, skipped another challenge that was being listed as "level 2," which brings us to the thirtieth challenge. This one is strikingly different from the other challenges I've covered here; rather than being asked to describe what a program does, the instruction read: "This program requires a password. Try to find it. As an additional exercise, try to change the password by patching the executable file. Also try using one with a different length. What is the shortest possible password here? Also try to crash the program using only string input." We're given several links to downloads. Binaries are provided for 32-bit Microsoft Windows, Mac OS X, and i386/mips Linux. I went with i386 Linux, as I'd be able to run the challenge natively.q #+BEGIN_SRC jakob@Epsilon /tmp $ sha256sum password1 96b8110208d61c7ac586910ebad22ef2e4bbeb867e6d6429967846698b9d02fc password1 #+END_SRC Being faced with a binary, I was tempted to use this as an opportunity to try out [[https://ghidra-sre.org/][Ghidra]], but while I waited for OpenJDK 11 to download, I peered inside with radare2 and decided that it wasn't worth the trouble. Here's the disassembly, according to radare: #+BEGIN_SRC [0x080484ed]> pdf ;-- eip: ┌ (fcn) main 149 │ main (); │ ; var int local_4h @ esp+0x4 │ ; var int local_1ch @ esp+0x1c │ ; var int local_9ch @ esp+0x9c │ ; DATA XREF from 0x08048407 (entry0) │ 0x080484ed 55 pushl %ebp │ 0x080484ee 89e5 movl %esp, %ebp │ 0x080484f0 83e4f0 andl $0xfffffff0, %esp │ 0x080484f3 81eca0000000 subl $0xa0, %esp │ 0x080484f9 65a114000000 movl %gs:0x14, %eax ; [0x14:4]=-1 ; 20 │ 0x080484ff 8984249c0000. movl %eax, local_9ch │ 0x08048506 31c0 xorl %eax, %eax │ 0x08048508 c70424208604. movl $str.enter_password:, 0(%esp) ; [0x8048620:4]=0x65746e65 ; "enter password:" │ 0x0804850f e89cfeffff calll sym.imp.puts ; int puts(const char *s) │ 0x08048514 8d44241c leal local_1ch, %eax ; 0x1c ; 28 │ 0x08048518 89442404 movl %eax, local_4h │ 0x0804851c c70424308604. movl $0x8048630, 0(%esp) ; [0x8048630:4]=0x6e007325 │ 0x08048523 e8b8feffff calll sym.imp.__isoc99_scanf │ 0x08048528 83f801 cmpl $1, %eax ; 1 │ ┌─< 0x0804852b 740c je 0x8048539 │ │ 0x0804852d c70424338604. movl $str.no_password_supplied, 0(%esp) ; [0x8048633:4]=0x70206f6e ; "no password supplied" │ │ 0x08048534 e877feffff calll sym.imp.puts ; int puts(const char *s) │ │ ; JMP XREF from 0x0804852b (main) │ └─> 0x08048539 c74424044886. movl $str.metallica, local_4h ; [0x8048648:4]=0x6174656d ; "metallica" │ 0x08048541 8d44241c leal local_1ch, %eax ; 0x1c ; 28 │ 0x08048545 890424 movl %eax, 0(%esp) │ 0x08048548 e843feffff calll sym.imp.strcmp ; int strcmp(const char *s1, const char *s2) │ 0x0804854d 85c0 testl %eax, %eax │ ┌─< 0x0804854f 750e jne 0x804855f │ │ 0x08048551 c70424528604. movl $str.password_is_correct, 0(%esp) ; [0x8048652:4]=0x73736170 ; "password is correct" │ │ 0x08048558 e853feffff calll sym.imp.puts ; int puts(const char *s) │ ┌──< 0x0804855d eb0c jmp 0x804856b │ ││ ; JMP XREF from 0x0804854f (main) │ │└─> 0x0804855f c70424668604. movl $str.password_is_not_correct, 0(%esp) ; [0x8048666:4]=0x73736170 ; "password is not correct" │ │ 0x08048566 e845feffff calll sym.imp.puts ; int puts(const char *s) │ │ ; JMP XREF from 0x0804855d (main) │ └──> 0x0804856b 8b94249c0000. movl local_9ch, %edx ; [0x9c:4]=-1 ; 156 │ 0x08048572 653315140000. xorl %gs:0x14, %edx │ ┌─< 0x08048579 7405 je 0x8048580 │ │ 0x0804857b e820feffff calll sym.imp.__stack_chk_fail ; void __stack_chk_fail(void) │ │ ; JMP XREF from 0x08048579 (main) │ └─> 0x08048580 c9 leave └ 0x08048581 c3 retl #+END_SRC As you can see, this is just like any other "easy crackme." A simple string comparison. radare2 doesn't automatically decode 0x8048630 as a string, but it's trivial to obtain its value. #+BEGIN_SRC :> psz @ 0x8048630 %s #+END_SRC Translating it into C is similarly trivial. #+BEGIN_SRC c #include #include int main(void) { char buf[128]; puts("enter password:"); if (scanf("%s", buf) != 1) { puts("no password supplied"); } if (strcmp(buf, "metallica") == 0) { puts("password is correct"); } else { puts("password is not correct"); } } #+END_SRC I do have to complement Yurichev's choice of strong passwords. \m/ One may wonder where I pulled =128= from. Our stack layout looks something like this: #+BEGIN_SRC prog +-------------------------------------+ |%esp | |Scratch space for function arguments.| +-------------------------------------+ |%esp + 0x1c | |Buffer starts here | |... | |Buffer ends here | +-------------------------------------+ |%esp + 0x9c | |Stack canary, perhaps? | +-------------------------------------+ |%esp + I DON'T CARE ANYMORE | |Here be dragons. | +-------------------------------------+ #+END_SRC radare2 is kind enough to automatically name local variables according to their position in the stack layout, so I was able to derive this from the names =local_1ch= and =local_9ch=. =local_4h= isn't really a local variable -- it looks like one, but that's just how the compiler decided to set up arguments for the various function calls (dereferencing the stack pointer, as opposed to using =push=). Anyway, subtracting =0x9c= from =0x1c= gets you 128 -- hence, the buffer size in my translation. It's pretty easy to patch the password, since =strcmp= operates on C strings. Just patch the characters. No sort of length needs to be adjusted since they're null-terminated. The shortest possible password would be zero characters long, which would be achieved by patching in a null byte at the 'm' in "metallica". This can be done however you like, though radare makes it easy if you've opened the file in "write mode": just seek to the location of the 'm' and =wx 00=. Crashing the program is similarly easy, since there are no bounds checks on the call to =scanf=. #+BEGIN_SRC jakob@Epsilon /tmp $ python -c "print('a' * 256)" | ./test enter password: password is not correct Segmentation fault #+END_SRC * Challenge #31 Yowch. We're only given disassemblies from MSVC this time. #+BEGIN_SRC c double f(double a, int b) { double cur; cur = 1.0; while (((double) (((int) (cur - a)) - b)) <= 0.001) cur = (a + 1.0) * 0.5; return cur; } #+END_SRC Once again, I deferred to [[https://float.exposed/][float.exposed]] to decode the floating-point constant values. =__real@3ff0000000000000= is =1.0=, =__real@3f50624dd2f1a9fc= is approximately =0.001=, and =__real@3fe0000000000000= is =0.5=. I also needed to look up most of the SIMD instructions. =cvttsd2si= converts a double to an int, =cdq= converts an int into a long, =cvtdq2pd= converts an int to a double, and =comisd= is comparable to =cmp=. This converges for very few values. Which is a pain, since this translation gives me some very promising output in [[https://godbolt.org/][Compiler Explorer]]. But considering the value that the loop gets stuck on, I suspect that =f= averages =a= and =b=. * Challenge #32 We're given a hint that, "[t]his is a standard C library function. The source code is taken from MSVC 2010." #+BEGIN_SRC c #include char *f(char *a, char *b) { char *cur; char *a_cur; char *b_cur; cur = a; if (*b == '\0') { return a; } while (*cur != '\0') { a_cur = cur; b_cur = b; while (*a_cur != '\0' && *b_cur != '\0' && *a_cur == *b_cur) { a_cur++; b_cur++; } if (*b_cur == '\0') { return cur; } cur++; } return NULL; } #+END_SRC I think the translation makes the purpose of this function reasonably clear, but the hint means I can verify my work against C's tiny standard library. =f= is obviously one of the library's [[https://en.wikipedia.org/wiki/C_string_handling][string functions]]. Can you guess which one? (My answer is that =f= is an implementation of =strstr=.) * Challenge #33 What gave it away for me this time was the "crypto" tag. I stopped in my translation efforts about here, #+BEGIN_SRC c void f(void *a, void *b, void *c) { int mushroom; // _k0 int bean; // _k1 int tomato; // _k2 int corn; // _k3 // eax = a[0] // ecx = a[1] mushroom = b[0]; bean = b[1]; // esi = b[3]; // edx = 0; tomato = b[2]; corn = b[3]; // edi = 32; // LL8 esi = ecx >> 5 + bean; ebx = ecx << 4 + mushroom; edx -= 0x61c88647; esi ^= ebx; ebx = ecx + edx; esi ^= ebx; eax += esi; esi = eax >> 5 + corn; ebx = eax << 4 + tomato; esi ^= ebx; ebx = eax + edx; esi ^= ebx; ecx += esi; edi--; // When edi == 0: c[0] = eax, c[1] = ecx } #+END_SRC and decided to do a search for '0x61c88647 hash'. This yields a few interesting results, such as [[https://stackoverflow.com/questions/38994306/what-is-the-meaning-of-0x61c88647-constant-in-threadlocal-java][one]] describing the constant used in ThreadLocal.java's implementation Fibonacci hashing and [[https://softwareengineering.stackexchange.com/questions/63595/tea-algorithm-constant-0x9e3779b9-said-to-be-derived-from-golden-ratio-but-the][another]] describing the constants used in the Tiny Encryption Algorithm. This immediately set off bells for me. I read Bruce Schneier's /Applied Cryptography/ some years back and was instantly reminded that TEA uses [[https://en.wikipedia.org/wiki/Block_cipher#Operations][ARX]] with shifts of =5= and =4=. If you pull up Wikipedia's reference code for TEA encryption, you'll be greeted with the following: #+BEGIN_SRC c void encrypt (uint32_t v[2], uint32_t k[4]) { uint32_t v0=v[0], v1=v[1], sum=0, i; /* set up */ uint32_t delta=0x9E3779B9; /* a key schedule constant */ uint32_t k0=k[0], k1=k[1], k2=k[2], k3=k[3]; /* cache key */ for (i=0; i<32; i++) { /* basic cycle start */ sum += delta; v0 += ((v1<<4) + k0) ^ (v1 + sum) ^ ((v1>>5) + k1); v1 += ((v0<<4) + k2) ^ (v0 + sum) ^ ((v0>>5) + k3); } /* end cycle */ v[0]=v0; v[1]=v1; } #+END_SRC Armed with this, I can confidently say that =f= is an implementation of TEA encryption with a schedule constant of =0x61c88647=. * Challenge #34 Another crypto challenge. This time, we're told that "[t]his is a well-known cryptographic algorithm from the past." The disassembly was simple enough that I thought to translate it into standard mathematical notation rather than C, but it turned out to be far less helpful than the equivalent C. #+BEGIN_SRC c uint16_t f(uint16_t a) { uint16_t tmp; tmp = a << 2; tmp ^= a; tmp <<= 1; tmp ^= a; tmp <<= 2; tmp ^= a; return ((tmp & 32) << 10) | (a >> 1); } #+END_SRC That said, I'm not familiar with the particular algorithm. There's a clear pattern, but I'm not sure where to start looking. Is it a hash function? Some kind of bastardized XOR encryption? Who knows. * Challenge #35 This was a tough one. I'll give my initial translation to C and explain where I went wrong: #+BEGIN_SRC c #include #include int f(int x, int y) { int a, b; if (x == 0) { return y; } if (y == 0) { return x; } a = x >> ffs(x); b = y >> ffs(y); while (a != b) { if (a < b) { SWAP(a, b); } if (a == 1) { break; } b = (b - a) >> ffs(b - a); } return a << ffs(x | y); } #+END_SRC One thing worth remarking on in the disassembly is this: #+BEGIN_SRC asm xor esi, edx xor edx, esi xor esi, edx #+END_SRC This is the [[https://en.wikipedia.org/wiki/XOR_swap_algorithm][XOR swap algorithm]]. In an attempt to make the translation more clear, I replaced it with a (non-existent) =SWAP= macro. =ffs= is also a POSIX extension that [[https://stackoverflow.com/questions/757059/position-of-least-significant-bit-that-is-set][corresponds nicely]] to the =bsf= instruction. The issue? I've been reading these MSVC disassemblies wrong the whole time. Take this instruction, for example: =mov edx, DWORD PTR _y$[esp+4]=. I'd never actually done out the calculations. As it turns out, =_rt$2[esp+8]= aliases with =y=. I thought that =_rt$2= was a distinct variable and that the compiler was storing to some local variable but never using it. This isn't the case, hence why the translation doesn't work as intended. What I need to start doing for these MSVC disassemblies is translating them into something I can assemble. #+BEGIN_SRC asm global f f: push ecx push esi mov esi, DWORD [esp+12] test esi, esi jne init mov eax, DWORD [esp+16] pop esi pop ecx ret init: mov edx, DWORD [esp+16] mov eax, esi test edx, edx je exit or eax, edx push edi bsf edi, eax bsf eax, esi mov ecx, eax mov DWORD [esp+8], eax bsf eax, edx shr esi, cl mov ecx, eax shr edx, cl mov DWORD [esp+16], eax cmp esi, edx je return lp: jbe skip xor esi, edx xor edx, esi xor esi, edx skip: cmp esi, 1 je return sub edx, esi bsf eax, edx mov ecx, eax shr edx, cl mov DWORD [esp+16], eax cmp esi, edx jne lp return: mov ecx, edi shl esi, cl pop edi mov eax, esi exit: pop esi pop ecx ret 0 #+END_SRC Actually, I should be doing this for all of the challenges... Anyway, observing a few test values for =f=: #+BEGIN_SRC prog f(1, 1) = 1 f(1, 2) = 1 f(1, 3) = 1 f(1, 4) = 1 f(1, 5) = 1 f(1, 6) = 1 f(1, 7) = 1 f(1, 8) = 1 f(1, 9) = 1 ... f(1, 252) = 1 f(1, 253) = 1 f(1, 254) = 1 f(1, 255) = 1 f(2, 1) = 1 f(2, 2) = 2 f(2, 3) = 1 f(2, 4) = 2 f(2, 5) = 1 f(2, 6) = 2 f(2, 7) = 1 f(2, 8) = 2 f(2, 9) = 1 f(2, 10) = 2 f(2, 11) = 1 f(2, 12) = 2 ... f(9, 1) = 1 f(9, 2) = 1 f(9, 3) = 3 f(9, 4) = 1 f(9, 5) = 1 f(9, 6) = 3 f(9, 7) = 1 f(9, 8) = 1 f(9, 9) = 9 ... f(10, 1) = 1 f(10, 2) = 2 f(10, 3) = 1 f(10, 4) = 2 f(10, 5) = 5 f(10, 6) = 2 f(10, 7) = 1 f(10, 8) = 2 f(10, 9) = 1 f(10, 10) = 10 f(10, 11) = 1 f(10, 12) = 2 ... #+END_SRC It took me a while, but I eventually noticed the pattern. =f= is the [[https://en.wikipedia.org/wiki/Greatest_common_divisor][greatest common divisor]] function. #+BEGIN_EXPORT html #+END_EXPORT