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 | 1258 |
1 files changed, 1258 insertions, 0 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 new file mode 100644 index 0000000..bb8f54d --- /dev/null +++ b/posts/Writeups for Dennis Yurichev's Reverse Engineering Challenges (#2-#11)/challenges-re-writeups-1.org @@ -0,0 +1,1258 @@ +#+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 type="text/x-mathjax-config"> +MathJax.Hub.Config({ + displayAlign: "center", + displayIndent: "0em", + + "HTML-CSS": { scale: 100, + linebreaks: { automatic: "false" }, + webFont: "TeX" + }, + SVG: {scale: 100, + linebreaks: { automatic: "false" }, + font: "TeX"}, + NativeMML: {scale: 100}, + TeX: { equationNumbers: {autoNumber: "AMS"}, + MultLineWidth: "85%", + TagSide: "right", + TagIndent: ".8em" + } +}); +</script> +<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.0/MathJax.js?config=TeX-AMS_HTML"></script> +#+END_EXPORT |