diff options
Diffstat (limited to 'posts/Writeups for Dennis Yurichev's Reverse Engineering Challenges (#2-#11)/challenges-re-writeups-1.org')
| -rw-r--r-- | posts/Writeups for Dennis Yurichev's Reverse Engineering Challenges (#2-#11)/challenges-re-writeups-1.org | 1238 |
1 files changed, 0 insertions, 1238 deletions
diff --git a/posts/Writeups for Dennis Yurichev's Reverse Engineering Challenges (#2-#11)/challenges-re-writeups-1.org b/posts/Writeups for Dennis Yurichev's Reverse Engineering Challenges (#2-#11)/challenges-re-writeups-1.org deleted file mode 100644 index 6ea207c..0000000 --- a/posts/Writeups for Dennis Yurichev's Reverse Engineering Challenges (#2-#11)/challenges-re-writeups-1.org +++ /dev/null @@ -1,1238 +0,0 @@ -#+TITLE: Writeups for Dennis Yurichev's Reverse Engineering Challenges (#2-#11) -#+DATE: <2019-03-10 Sun> -#+TAGS: writeup, reverse-engineering, arm, x86 - -As mentioned in the post I wrote [[http://jakob.space/posts/new-ambitions-for-a-new-year/][describing my plans for 2019]], one of my goals -this year is to get through at least 50 of the exercises on Dennis Yurichev's -[[https://challenges.re/][challenges.re]]. I've decided to document my progress in the form of writeups for -the challenges I complete, batched in sets of ten exercises. For each challenge, -I'll try to explain the intuitions that brought me closer to answering the -recurring question from Yurichev, "[w]hat does this code do?" - -* Challenge #2 - -In nearly all of the challenges available on the site, we're given equivalent -disassembly listings of a function, =f=, as generated by different compilers on -different processor architectures, and we're asked to describe what the code -does. For now, I've decided to take it easy and only pay attention to the -disassemblies for GCC on x86, as that's what I've done the most work with. We -aren't given a target operating system, but I think it's reasonable to assume -that the x86 code uses the [[https://en.wikipedia.org/wiki/X86_calling_conventions#cdecl][cdecl calling convention]]. - -Although I stayed within my comfort zone in terms of instruction set -architecture, I refrained from my usual habit of converting the disassembly -listing to AT&T syntax for once. - -#+BEGIN_EXPORT html -<div class="mastodon"> - <iframe height="180" src="https://cmpwn.com/@sir/100574012321451958/embed"></iframe> -</div> -#+END_EXPORT - -Below is a rough translation of the disassembly listing to C. My process is -relatively unchanged from the workflow I described in an [[http://jakob.space/posts/decompilation-by-hand/][older post]]. - -#+BEGIN_SRC c :hl_lines 0 -unsigned f(unsigned a) -{ - // mov eax,DWORD PTR [esp+0x4] - // bswap eax - a = ((a & 0xff) << 24) - | ((a & 0xff00) << 8) - | ((a & 0xff0000) >> 8) - | ((a & 0xff000000) >> 24); - - // mov edx,eax - // and eax,0xf0f0f0f - // and edx,0xf0f0f0f0 - // shr edx,0x4 - // shl eax,0x4 - // or eax,edx - a = ((a & 0xf0f0f0f) << 4) | ((a & 0xf0f0f0f0) >> 4); - - // mov edx,eax - // and eax,0x33333333 - // and edx,0xcccccccc - // shr edx,0x2 - // shl eax,0x2 - // or eax,edx - a = ((a & 0x33333333) << 2) | ((a & 0xcccccccc) >> 2); - - // and eax,0x55555555 - // and edx,0xaaaaaaaa - // add eax,eax - // shr edx,1 - // or eax,edx - a = ((a & 0x55555555) << 1) | ((a & 0xaaaaaaaa) >> 1); - - // ret - return a; -} -#+END_SRC - -I think it should make sense that =add eax,eax= is mathematically equivalent to -=imul eax, 2=, but it takes another step to see that it's [[https://math.stackexchange.com/questions/1610667/why-shifting-left-1-bit-is-the-same-as-multiply-the-number-by-2][equivalent]] to =shl eax,1=, -which is represented in the C code as =<< 1=. This isn't terribly complicated, but -it's an optimization detail that some might not be familiar with. =bswap= is an -instruction I was unfamiliar with, so I consulted my [[https://c9x.me/x86/html/file_module_x86_id_21.html][favorite x86 reference]]. It -converts the endianness of the word in the register. If you don't know what that -means, I'd suggest you read the page in the ISA reference. - -The code seems nonsensical at first, but we can compile it and inspect the -output given some test values. - -#+BEGIN_SRC c :hl_lines 0 -#include <stdio.h> - -void main(void) -{ - unsigned i; - - for (i = 0; i <= 256; i++) { - printf("%010u %08x\n", i, i); - printf("%010u %08x\n", f(i), f(i)); - printf("\n"); - } -} -#+END_SRC - -Which produces: - -#+BEGIN_SRC -0000000000 00000000 -0000000000 00000000 - -0000000001 00000001 -2147483648 80000000 - -0000000002 00000002 -1073741824 40000000 - -0000000003 00000003 -3221225472 c0000000 - -0000000004 00000004 -0536870912 20000000 -... -#+END_SRC - -What's happening might not be immediately obvious, but there's a pattern in the -column of input/output represented in hexadecimal. Let's have a look at the -binary representations of a few pairs: - -#+BEGIN_SRC python -bin(0x00000001) # --> '0b00000000000000000000000000000001' -bin(0x80000000) # --> '0b10000000000000000000000000000000' - -bin(0x00000003) # --> '0b00000000000000000000000000000011' -bin(0xc0000000) # --> '0b11000000000000000000000000000000' - -# ... - -bin(0x0000004d) # --> '0b00000000000000000000000001001101' -bin(0xb2000000) # --> '0b10110010000000000000000000000000' -#+END_SRC - -My answer to the question is that =f= reverses the bits of the word it is given. - -* Challenge #3 - -This time, we're given an array of 64 32-bit integers and a hint that "[t]he -algorithm is well-known, but I've changed [the] constant so it wouldn't be -googleable." - -#+BEGIN_SRC c :hl_lines 0 -int f(unsigned n) -{ - unsigned a, b; - - // mov edx, edi - // shr edx - // or edx, edi - // mov eax, edx - a = b = (n >> 1) | n; - - // shr eax, 2 - // or eax, edx - // mov edx, eax - a = b = (a >> 2) | b; - - // shr edx, 4 - // or edx, eax - // mov eax, edx - a = b = (b >> 4) | a; - - // shr eax, 8 - // or eax, edx - // mov edx, eax - a = b = (a >> 8) | b; - - // shr edx, 16 - // or edx, eax - b = (b >> 16) | a; - - // imul eax, edx, 79355661 ; 0x4badf0d - // shr eax, 26 - a = (b * 0x4badf0d) >> 26; - - // mov eax, DWORD PTR v[0+rax*4] - // ret - return v[a]; -} -#+END_SRC - -The first thing that stood out to me was the presence of =-1= in the array of -integers. Testing from =0= to =UINT_MAX=, the only =n= that returns =-1= is =0=. -Interesting. It's also worth noting that the array contains every integer from -0, 31, so this function is using /some rule/ to map the input space onto [0, 31]. - -If we inspect the values of =f= for test values from =0= to =UINT_MAX=: - -#+BEGIN_SRC :hl_lines 0 - f(1) = 31 - f(2) = 30 - f(3) = 30 - f(4) = 29 - f(5) = 29 - f(6) = 29 - f(7) = 29 - f(8) = 28 - f(9) = 28 -f(10) = 28 -f(11) = 28 -f(12) = 28 -f(13) = 28 -f(14) = 28 -f(15) = 28 -f(16) = 27 -f(17) = 27 -f(18) = 27 -f(19) = 27 -f(20) = 27 -f(21) = 27 -f(22) = 27 -f(23) = 27 -f(24) = 27 -f(25) = 27 -f(26) = 27 -f(27) = 27 -f(28) = 27 -f(29) = 27 -f(30) = 27 -f(31) = 27 -#+END_SRC - -There's a pattern of exponential growth here -- every result occurs twice as -frequently as the previous result. Mathematically, this is \(31 - [log_2(n)]\) -where the brackets represent the Greatest Integer Function (\(f(x)\) returning -the largest integer less than or equal to \(x\)). This can be verified by -comparing the result of =f= to the following function for some test values: - -#+BEGIN_SRC c :hl_lines 0 -int my_f(unsigned n) -{ - return 31 - ((int) (log(n) / log(2))); -} -#+END_SRC - -* Challenge #4 - -This time around we're given an additional question to answer: "Some versions -have the =0x1010101= constant, some do not. Why?" I decided that I'd reverse the -x86 disassembly first, and then compare it to the other architectures. - -#+BEGIN_SRC c :hl_lines 0 -unsigned f(unsigned a) -{ - // mov edx,edi - // shr edx,1 - // and edx,0x55555555 - // sub edi,edx - a -= ((a >> 1) & 0x55555555); - - // mov eax,edi - // shr edi,0x2 - // and eax,0x33333333 - // and edi,0x33333333 - // add edi,eax - a = (a & 0x33333333) + ((a >> 2) & 0x33333333); - - // mov eax,edi - // shr eax,0x4 - // add eax,edi - // and eax,0xf0f0f0f - // imul eax,eax,0x1010101 - // shr eax,0x18 - // ret - return (((a + (a >> 4)) & 0xf0f0f0f) * 0x1010101) >> 0x18 -} -#+END_SRC - -The past few challenges have shown us that a good way of reversing these -bit-twiddling functions is to test a few input values and look at the binary -representations of the input and output values. - -#+BEGIN_SRC - In: 00000000 -Out: 0 - - In: 00000001 -Out: 1 - - In: 00000010 -Out: 1 - - In: 00000011 -Out: 2 - -... - - In: 00001100 -Out: 2 - - In: 00001101 -Out: 3 - - In: 00001110 -Out: 3 - - In: 00001111 -Out: 4 -#+END_SRC - -It doesn't take much effort to see that the function is counting the number of -bits set in the input. This was particularly interesting to me as I was asked to -derive this algorithm for a past job interview (though I wasn't able to in the -time given). - -This falls apart for numbers larger than =0xff=, however. It returns the number of -bits plus some constant that changes depending on which bits in the higher bytes -are set. I'll assume that =f= is only meant to be called with 8-bit integers. - -With that, we can move onto the second question. The disassemblies for x86, -ARM64, and Thumb have the =0x1010101= constant, while the disassemblies for ARM -and MIPS do not. - -Returning to the strategy of inspecting binary representations: - -#+BEGIN_SRC -00000000 00000000 00000000 00000000 -00000000 00000000 00000000 00000000 - -00000000 00000000 00000000 00000001 -00000001 00000001 00000001 00000001 - -00000000 00000000 00000000 00000010 -00000010 00000010 00000010 00000010 - -... - -00000000 00000000 00000000 00010000 -00010000 00010000 00010000 00010000 - -00000000 00000000 00000000 00010001 -00010001 00010001 00010001 00010001 - -00000000 00000000 00000000 00010010 -00010010 00010010 00010010 00010010 - -... - -00000000 00000000 00000000 11111101 -11111101 11111101 11111101 11111101 - -00000000 00000000 00000000 11111110 -11111110 11111110 11111110 11111110 - -00000000 00000000 00000000 11111111 -11111111 11111111 11111111 11111111 -#+END_SRC - -It would appear that multiplying a 32-bit integer by =0x1010101= propagates the -low byte to the three bytes above it. This makes sense when you notice that the -multiplication is paired with a =shr= of =0x18= -- moving the highest byte into the -lowest byte. - -Though, this doesn't really answer the question. What difference is there -between the architectures that use the =0x1010101= and the architectures that -don't? ARM and MIPS still do a shift by =0x18=, so what's going on? - -Looking at the ARM example, the instructions around the shift are: - -#+BEGIN_SRC asm :hl_lines 0 -ADD r0,r0,r0,LSL #16 -ADD r0,r0,r0,LSL #8 -LSR r0,r0,#24 -#+END_SRC - -For MIPS, it looks like: - -#+BEGIN_SRC asm :hl_lines 0 -sll $3,$2,8 -addu $2,$3,$2 -sll $3,$2,16 -addu $2,$2,$3 -j $31 -srl $2,$2,24 -#+END_SRC - -Both of these (humor me, I know the orders are different) are equivalent to: - -#+BEGIN_SRC c :hl_lines 0 -a = (a << 8) + a; -a = (a << 16) + a; -a >> 24; -#+END_SRC - -And, with some test values, we can see that this is equivalent to multiplication -by =0x1010101= and shifting by 24. - -#+BEGIN_SRC c :hl_lines 0 -unsigned a(unsigned n) -{ - n = (n << 8) + n; - n = (n << 16) + n; - return n >> 24; -} - -unsigned b(unsigned n) -{ - return (n * 0x1010101) >> 24; -} - -void main(void) -{ - for (unsigned i = 0; i < UINT_MAX; i++) { - if (a(i) != b(i)) { - printf("%u\n", i); - } - } -} -#+END_SRC - -I suspect the reason it doesn't show up in the ARM or MIPS disassemblies is due -to the fixed-width instruction encoding. The compiler likely decided it would be -less efficient to work with the =0x1010101= constant than to break it up into a -pair of shifts and additions. - -* Challenge #5 - -This is the first challenge we're given that has loops and conditionals, as -indicated by the telltale labels starting with ".L". Another initial observation -is that the first instruction in =f= operates on =%rsi=, and the third operates on -=%rcx=, so it's very likely that this function has four parameters. - -Translation to C is more involved than it was with the previous challenges, but -it is valuable as it makes the purpose of =f= very clear. In lieu of an analysis -of inputs and outputs, I'll provide a few notes on the process of translation. -First, =cmp= gave me a bit of trouble as I've been out of practice for some time -and the difference between AT&T and Intel syntax threw me for a loop. -Fortunately, the [[https://en.wikibooks.org/wiki/X86_Assembly/Control_Flow#Comparison_Instructions][wikibooks]] for x86 assembly covers this in detail. In AT&T -syntax, the order is =cmp subtrahend, minuend=, while in Intel syntax, the order -is =cmp minuend, subtrahend=. The subtrahend is subtracted from the minuend, so, -in Intel syntax, =cmp rcx, rsi; ja .L10= will jump if =%rcx= is greater than =%rsi=. - -Looking further into the function, there is some dereferencing with =BYTE PTR=, -which tipped me off that this was probably a function operating on a string. - -There's a curious =push rbx=, followed by a =pop rbx= before the =ret=. I ignored this -initially, taking it to be register preservation. It was. An intuition of what's -worth ignoring is valuable in reverse engineering. - -Upon reaching =.L16=, there are a lot of registers in use. It helped to look at -each register in isolation and see how they were used. For example, =%r10= is used -in the following instructions: =xor r10d, r10d=, =add r10, 1=, =lea rax, [rdi+r10]=, -and =cmp r10, r11=. This is very typical of a for-loop counter. =%r9= on the other -hand only shows up in two instructions: =mov r9d, 1=, and =cmovne r8d, r9d=. =%r9= is -just used as a source of 1 for =cmovne=, since there are no encodings for =cmovne= -that have an immediate source. - -=cmovne= was unfamiliar to me, so I did look it up in my favorite [[https://c9x.me/x86/html/file_module_x86_id_34.html][x86 reference]]. -It's a conditional move. =movz= was similarly unfamiliar. It simply loads =%bl= with -the source byte and zeroes out the higher portions of the register. - -#+BEGIN_SRC c :hl_lines 0 -char *f(char *a, unsigned b, char *c, unsigned d) -{ - // cmp rcx, rsi - // ja .L10 - if (d >= b) { - // .L10: - // xor eax, eax - // ret - return NULL; - } - - - // sub rsi, rcx - // add rsi, 1 - // mov r11, rsi - b = b - d + 1; - - // je .L10 - if (b == 0) { - // .L10: - // xor eax, eax - // ret - return NULL; - } - - // test rcx, rcx - // jne .L16 - // mov rax, rdi - // ret - if (d == 0) { - return a; - } - - // .L16: - // push rbx - // xor r10d, r10d - // mov r9d, 1 - // ... - // cmp r10, r11 - // jne .L4 - for (int i = 0; i != b; i++) { - // xor r8d, r8d - unsigned ret = 0; - - // .L4: - // lea rax, [rdi+r10] - // xor esi, esi - // ... - // add rsi, 1 - // cmp rsi, rcx - // jne .L8 - for (int j = 0; j != d; j++) { - // movzx ebx, BYTE PTR [rdx+rsi] - // cmp BYTE PTR [rax+rsi], bl - // cmovne r8d, r9d - if (a[i] != c[j]) { - ret = 1; - } - } - - // test r8d, r8d - // je .L12 - if (!ret) { - // .L12: - // pop rbx - // ret - return a + i; - } - } - - // xor eax, eax - // pop rbx - // ret - return NULL; -} -#+END_SRC - -The variable names I chose are pretty opaque, but if you stare at this long -enough, it should be pretty clear that =f= returns the offset of =c= in =a=. =b= and =d= -are just the lengths of =a= and =c= respectively. - -* Challenge #6 - -An additional hint given for this exercise is that, "[t]his is one of the -simplest exercises I made, but still this code can be served as useful library -function and is certainly used in many modern real-world applications." I'll -leave the relative addresses in my annotations of the disassembly, as it appears -to be PIC. - -For the sake of showing the mapping between assembly instructions and C code, -I'll first give a translation that uses =goto=, followed by a cleaned up version. - -#+BEGIN_SRC c -// 0: push rbp -// 1: mov rbp,rsp -// 4: mov QWORD PTR [rbp-0x8],rdi -// 8: mov QWORD PTR [rbp-0x10],rsi -int f(char *a, char *b) -{ -_start: - // c: mov rax,QWORD PTR [rbp-0x8] - // 10: movzx eax,BYTE PTR [rax] - // 13: movsx dx,al - // 17: mov rax,QWORD PTR [rbp-0x10] - // 1b: mov WORD PTR [rax],dx - *b = *a; - - // 1e: mov rax,QWORD PTR [rbp-0x10] - // 22: movzx eax,WORD PTR [rax] - // 25: test ax,ax - // 28: jne 2c - // 2a: jmp 38 - if (*a & 0xffff != 0) { - // 2c: add QWORD PTR [rbp-0x8],0x1 - // 31: add QWORD PTR [rbp-0x10],0x2 - // 36: jmp c - a++; - b++; - goto _start; - } - - // 38: pop rbp - // 39: ret -} -#+END_SRC - -#+BEGIN_SRC c -int f(char *a, char *b) -{ - while (*a != '\0') { - *b++ = *a++; - } -} -#+END_SRC - -Cool. Yurichev wasn't lying, this is a damn simple exercise, but it is something -that's used in nearly every C program. It's =strcpy=! - -* Challenge #7 - -This exercise gives the same hint as last time, and similarly uses address -offsets instead of symbols. - -Control flow isn't as initially obvious as some of the past exercises, but the -first instruction is a pretty good tell that this function takes a =char *= as a -parameter, and the =test dl,dl= was a good tell that the control flow depends on -the individual characters in that parameter. The =0x41= in that ==lea -esi,[rdx-0x41]= instruction stood out to me, as =0x41= is 'A' in ASCII, and the -=0x20= in the =add edx,0x20= was also a big clue, as ='a' - 'A'= is =0x20=. - -#+BEGIN_SRC c -void f(char *a) -{ - char *cur; - - // 0: movzx edx,BYTE PTR [rdi] - // 3: mov rax,rdi - // 6: mov rcx,rdi - // 9: test dl,dl - // b: je 29 - // 29: repz ret - if (*a == '\0') - return; - - // 6: mov rcx,rdi - cur = a; - - // 25: test dl,dl - // 27: jne 10 - while (*cur != '\0') { - // 10: lea esi,[rdx-0x41] - // 13: cmp sil,0x19 - // 17: ja 1e - // 19: add edx,0x20 - // 1c: mov BYTE PTR [rcx],dl - if (*cur - 0x41 <= 0x19) - *cur += 0x20; - - // 1e: add rcx,0x1 - // 22: movzx edx,BYTE PTR [rcx] - cur++; - } - - // 29: repz ret -} -#+END_SRC - -Just from the tells outlined in the previous paragraph, I don't even need to run -=f= to know that it converts =a= to lowercase, albeit only capable of transforming -capital ASCII characters (producing garbage for, say, a space character). - -* Challenge #8 - -The hint we're given this time is, "[t]his is one of the busiest algorithms -under the hood, though, usually hidden from programmers. It implements one of -the most popular algorithms in computer science. It features recursion and a -callback function." - -In preparation for an exercise that's would likely be more difficult than the -past few, I did a couple quick perusals to get a basic idea of the control flow, -the parameters, and the return values. The =mov rbp,rdx= early on indicates that -there are at least three parameters. - -There's a =push rbp= instruction, but [[https://en.wikipedia.org/wiki/Function_prologue][explicit creation of a stack frame]]. There -are also =push r12= and =push rbx= instructions. These all occur at the beginning of -the function, so we see some register preservation and an indication that these -are the registers that are going to be used in the code. - -I find that a lot of reverse engineering involves getting good footing, so -this is the information you want when starting out. - -What I normally try to find out next is whether the parameters and return type -are integers or pointers: =mov rsi,QWORD PTR [rbx]=, after =%rsi= was moved into -=%rbx= is a good tell that the second parameter is a pointer, likely to an array -of pointer as it's dereferenced as =QWORD PTR=, and the =call r12= tells me that the -first parameter is the callback that was mentioned in the hint. The =js 40= after -testing the callback's return value tells me that its return value is signed -- -probably an int, not a pointer -- and the pair of =mov rsi,QWORD PTR [rbx]= and -=mov rdi,rbp= before the call indicate that it takes two parameters. - -#+BEGIN_SRC c -void *f(int (*a)(void *, int), void **b, int c) -{ - int ret; - // 0: push r12 - // 2: test rsi,rsi - // ... - // 10: je 32 - if (b == 0) { - // 32: pop rbx - // 33: pop rbp - // 34: xor eax,eax - // 36: pop r12 - // 38: ret - return NULL; - } - - // r12 <- a - // rbx <- b - // rbp <- c - - while (1) { - // (This code path is also duplicated at 49-54. The branch that - // contains the duplicated code has been omitted, as the same - // effect arises from this loop continuing to iterate. - // - // 18: mov rsi,QWORD PTR [rbx] - // 1b: mov rdi,rbp - // 1e: call r12 - ret = a(*b, c); - - // 21: test eax,eax - // 23: je 56 - if (ret == 0) { - // 56: mov rax,rbx - // 59: pop rbx - // 5a: pop rbp - // 5b: pop r12 - // 5d: ret - return b; - } - - // 25: js 40 - else if (ret < 0) { - // 40: mov rbx,QWORD PTR [rbx+0x10] - b = b[4]; - - // 44: test rbx,rbx - // 47: je 32 - if (b == NULL) { - // 32: pop rbx - // 33: pop rbp - // 34: xor eax,eax - // 36: pop r12 - // 38: ret - return NULL; - } - } - - else { - // 27: mov rbx,QWORD PTR [rbx+0x18] - b = b[6]; - - // 2b: test rbx,rbx - // 30: jne 18 - if (b == NULL) { - // 32: pop rbx - // 33: pop rbp - // 34: xor eax,eax - // 36: pop r12 - // 38: ret - return NULL; - } - } - } -} -#+END_SRC - -In deriving meaning from this, I have a bit of an advantage; I've just recently -implemented this exact algorithm for my university's computer systems principle -course. This is the search function for a binary search tree, which takes an -arbitrary comparison function, =a=,, and returns the first node for which =a= -returns 0. The function returns =NULL= if the item is not in the tree. =c= is some -sort of "data" parameter for the callback function, hence why it isn't used in -the algorithm. - -=b= is probably a pointer to a struct looking something like the following: - -#+BEGIN_SRC c -struct tree_node { - char data[0x10]; - struct tree_node *left; - struct tree_node *right; -} -#+END_SRC - -as =QWORD PTR [rbx+0x10]= is followed when =a= returns something less than 0 -(represented in the struct as =left=), and =QWORD PTR [rbx+0x18]= is followed when =a= -returns something greater than 0 - (represented in the struct as =right=). - -This exercise is a little unusual. The hint mentions recursion, but this -algorithm is entirely iterative. Perhaps it was implemented recursively in C, -and the compiler performed some sort of tail-call optimization? I honestly have -no idea. - -* Challenge #9 - -The hint we're given this time is, "[n]ow that's easy." I certainly hope it is. - -This is the first challenge we're given that uses libc. It's also the first -challenge in which we see the compiler using [[https://en.wikipedia.org/wiki/Switch_statement#Compilation][binary search]] to optimize a -conditional with more than one branch. I tend to write these out as =switch= -statements whenever I see them, but it's perfectly reasonable for a compiler to -optimize an =if= in the same way. - -#+BEGIN_SRC c -#include <stdio.h> -#include <stdlib.h> - -int f(char a) -{ - // sub rsp, 8 - // movzx eax, BYTE PTR [rdi] - switch (a) { - // cmp al, 89 - // je .L3 - case 'Y': - // cmp al, 121 - // jne .L2 - case 'y': - // .L3: - // mov eax, 1 - // add rsp, 8 - // ret - return 1; - - // jle .L21 - // ... - // .L21: - // cmp al, 78 - // je .L6 - case 'N': - // ... - // cmp al, 110 - // je .L6 - case 'n': - // .L6: - // xor eax, eax - // add rsp, 8 - // ret - return 0; - - default: - // .L2: - // mov edi, OFFSET FLAT:.LC0 - // call puts - // xor edi, edi - // call exit - puts("error!"); - exit(0); - } -} -#+END_SRC - -Yurichev wasn't lying, this was an easy challenge. In fact, if I were reverse -engineering a binary and came across something like this, I probably wouldn't -bother translating the assembly to equivalent C. It's a function that converts a -character to a boolean (in the sense of a prompt that asks the user for 'Y' or -'N' -- "Yes" or "No") and exits prematurely if the character wouldn't make sense -in that context. - -* Challenge #10 - -The hint time is "[t]his code snippet is short, but tricky. What does it do? -It's used heavily in low-level programming and is well-known to many low-level -programmers. There are several ways to calculate it, and this is the one of -them." - -The snippet really is short, clocking in at only four instructions, but I still -felt the need to break out [[https://godbolt.org/][Compiler Explorer]] for this one. The part about being -"used heavily in low-level programming" threw me off a bit, since I saw =neg= and -thought that perhaps that'd correspond to the =~= operator in C, which I've only -seen used in very low-level bit shifting code. This initial assumption would've -led me astray, however, and I'm glad I took the extra minute to verify. - -#+BEGIN_SRC c -int f(int a) -{ - return -a; -} -#+END_SRC - -#+BEGIN_SRC asm -f(int): - push rbp - mov rbp, rsp - mov DWORD PTR [rbp-4], edi - mov eax, DWORD PTR [rbp-4] - neg eax - pop rbp - ret -#+END_SRC - -#+BEGIN_SRC c -int f(int a) -{ - return ~a; -} -#+END_SRC - -#+BEGIN_SRC asm -f(int): - push rbp - mov rbp, rsp - mov DWORD PTR [rbp-4], edi - mov eax, DWORD PTR [rbp-4] - not eax - pop rbp - ret -#+END_SRC - -=not= corresponds to =~=, and =neg= corresponds to =-= We're dealing with =neg= here. - -The equivalent C code for the snippet is given. Because I had Compiler Explorer -open already, I decided to throw this in there for kicks and giggles. x86-64 gcc -8.3 with =-O2= spits out the exact same series of instructions as the challenge. I -love the predictability of C compilers. - -#+BEGIN_SRC c -int f(int a, int b) -{ - return (a + b - 1) & -b; -} -#+END_SRC - -This doesn't answer our question, though. What does this do? We can test a few -values of =a= and =b= with the following snippet, replacing =2<<0= with various -constants. - -#+BEGIN_SRC c -int main(void) -{ - int i, j; - j = 2 << 0; - for (i = 0; i < 256; i++) { - printf("%-8x %-8x %-8x\n", i, j, f(i, j)); - } -} -#+END_SRC - -#+BEGIN_SRC -0 2 0 -1 2 2 -2 2 2 -3 2 4 -4 2 4 -5 2 6 -6 2 6 -7 2 8 -8 2 8 -9 2 a -a 2 a -b 2 c -c 2 c -d 2 e -e 2 e -f 2 10 -... -0 8 0 -1 8 8 -2 8 8 -3 8 8 -4 8 8 -5 8 8 -6 8 8 -7 8 8 -8 8 8 -9 8 10 -a 8 10 -b 8 10 -c 8 10 -d 8 10 -e 8 10 -f 8 10 -10 8 10 -11 8 18 -12 8 18 -#+END_SRC - -It would seem that this is some sort of "least multiple of \(b\) such that \(b < -a\) given that \(b\) is a power of two, but I feel as though I'm grasping at -straws here. - -As a Gentoo user, I have the Linux source tree checked out at =/usr/src/linux=, -and because the hint mentions low-level programming, I decided to create a -regular expression for the C I came up with and let =ag= have a go at it. - -=ag "\\(.*-[^>].*\\).*&.*\\-" /usr/src/linux= yielded quite a few results. Before -I ran the command, I wasn't expecting much, thinking that my regex was too -permissive, but the first result I saw looked remarkably like the C expression I -had come up with -- right at the beginning of =sysv_readdir= in =fs/sysv/dir.c=: - -#+BEGIN_SRC c -static int sysv_readdir(struct file *file, struct dir_context *ctx) -{ - unsigned long pos = ctx->pos; - struct inode *inode = file_inode(file); - struct super_block *sb = inode->i_sb; - unsigned long npages = dir_pages(inode); - unsigned offset; - unsigned long n; - - ctx->pos = pos = (pos + SYSV_DIRSIZE-1) & ~(SYSV_DIRSIZE-1); - if (pos >= inode->i_size) - return 0; -#+END_SRC - -Hm. Remember how I mentioned that I expected =neg= to correspond to a =~=? Well, -jumping back to Compiler Explorer: - -#+BEGIN_SRC c -int f(int a) -{ - return ~a; -} -#+END_SRC - -#+BEGIN_SRC asm -f(int): - mov eax, edi - not eax - ret -#+END_SRC - -#+BEGIN_SRC c -int f(int a) -{ - return ~(a - 1); -} -#+END_SRC - -#+BEGIN_SRC asm -f(int): - mov eax, edi - neg eax - ret -#+END_SRC - -Modifying our search slightly to =ag "\\(.*-[^>].*\\).*&.*\\~.*\\-.*1"= yields a -massive number of results, some of which are named macros. Here's one of them, -in =include/uapi/linux/if_packet.h=: - -#+BEGIN_SRC c -#define TPACKET_ALIGN(x) (((x)+TPACKET_ALIGNMENT-1)&~(TPACKET_ALIGNMENT-1)) -#+END_SRC - -Cool. That makes me feel much more confident in my answer. - -* Challenge #11 - -The hint for this exercise is: "[t]his is a somewhat large function (in contrast -to the other exercises in this blog), but heavily used nowadays in various -software. As it can be clearly seen, it uses standard C/C++ functions including -strlen() and sscanf(). Some other helper function is also used. I intentionally -gave it this name to conceal its real function. So what does the whole code -snippet do?" - -I'd like to apologize in advance for the sloppiness of the code that follows. -Also, I've renamed =helper= to =is_hex_digit=, as it makes the code for =f= clearer. - -#+BEGIN_SRC c -#include <string.h> -#include <stdio.h> - -int is_hex_digit(char a) -{ - // lea edx, [rdi-48] - // mov eax, 1 - // cmp edx, 9 - // jbe .L2 - if (a <= '9') { - // .L2: - // ret - return 1; - } - - // and edi, -33 - // xor eax, eax - // sub edi, 65 - // cmp edi, 5 - // setbe al - // .L2: - // ret - return (a & -33) <= 'F' ? 1 : 0; -} - -int f(char *a, char *b) -{ - int len; - int local_12; - char *cur; - char *end; - char *dst; - char *next; - - // push r15 - // xor eax, eax - // or rcx, -1 - // push r14 - // push r13 - // push r12 - // mov r12, rsi - // push rbp - // mov rbp, rsi - // push rbx - // mov rbx, rdi - // sub rsp, 24 - // repnz scasb - // not rcx - dst = b; - cur = a; - len = strlen(a); - - // lea r14, [rbx-1+rcx] - // .L6: - // cmp rbx, r14 - // ja .L24 - while (cur <= end) { - // movsx eax, BYTE PTR [rbx] - // ... - // mov DWORD PTR [rsp+12], eax - local_12 = (int) *cur; - - // lea r13, [rbx+1] - next = cur + 1; - - // mov r15, r13 - // cmp eax, 43 - // jne .L7 - if (*cur == '+') { - // mov DWORD PTR [rsp+12], 32 - local_12 = ' '; - // jmp .L8 - } else { - // .L7: - // cmp eax, 37 - // jne .L8 - // movsx edi, BYTE PTR [rbx+1] - // call helper - // test eax, eax - // jne .L9 - if (*cur == '%' && is_hex_digit(*(cur + 1))) { - // .L9: - // movsx edi, BYTE PTR [rbx+2] - // lea r13, [rbx+3] - next = cur + 3; - - // call helper - // test eax, eax - // je .L11 - if (!is_hex_digit(*(cur + 2))) { - // .L11: - // or eax, -1 - // jmp .L10 - // .L10: - // add rsp, 24 - // pop rbx - // pop rbp - // pop r12 - // pop r13 - // pop r14 - // pop r15 - // ret - return -1; - } - - // lea rdx, [rsp+12] - // xor eax, eax - // mov esi, OFFSET FLAT:.LC0 - // mov rdi, r15 - // call __isoc99_sscanf - // test eax, eax - // je .L11 - if (!sscanf(cur + 1, "%2X", &local_12)) { - // .L11: - // or eax, -1 - // jmp .L10 - // .L10: - // add rsp, 24 - // pop rbx - // pop rbp - // pop r12 - // pop r13 - // pop r14 - // pop r15 - // ret - return -1; - } - } - - } - - // .L8: - // test r12, r12 - // je .L12 - if (b != NULL) { - // mov eax, DWORD PTR [rsp+12] - // mov BYTE PTR [rbp+0], al - *dst = local_12; - } - - // .L12: - // inc rbp - // mov rbx, r13 - // jmp .L6 - dst++; - cur = next; - } - - // .L24: - // mov eax, ebp - // sub eax, r12d - // .L10: - // add rsp, 24 - // pop rbx - // pop rbp - // pop r12 - // pop r13 - // pop r14 - // pop r15 - // ret - return dst - b; -} -#+END_SRC - -This could very well be cleaned up. In fact, I'm not even sure that my -translation is completely correct, but I got to the point where I felt it was -"good enough" and I could explain that =f= is a function for decoding a -[[https://en.wikipedia.org/wiki/Percent-encoding][percent-encoded]] string, where =a= is the encoded string and =b= is a destination to -decode to. If not for the telltale ='+'= corresponding to a =' '= and use of a ='%'= -character, I probably would have spent more time cleaning up my translation and -making sense of it. But I've seen code like this many times in my life, it -really is "heavily used nowadays in various software." - -I began this challenge by reversing =helper=, which I think was a good move as it -gave me some footing. I didn't even notice '%' or '+' in =f= at first, but the -realization that =helper= worked with hexadecimal digits got me started on ideas -for what =f= might do. - -On the topic of =helper=, the reason I was able to pick out that it's checking for -hexadecimal digits was realizing that \(a - 48 \leq 9\) is equivalent to \(a -\leq 49 + 9\). The comparison is otherwise pretty unclear. And I suspect that -the =-33= is related to how ASCII is encoded. - -The control flow for =f= is pretty intimidating with its 8 labels. When it came -time to look at =f=, I drew out a rudimentary control flow graph on paper -- -scribbling down the label names and drawing arrows between the different labels. -I found this to be very useful in identifying which jumps are loops (cycles in -the graph), which are conditionals (branches), and which labels are related -(linear relationships). - -#+BEGIN_EXPORT html -<script src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/latest.js?config=TeX-MML-AM_CHTML"></script> -#+END_EXPORT |