Reverse Engineering: forest
Took a look at another reversing challenge with a few small interesting bits. More practice allowing me to explore a little more radare2 functionality.
Binary: Forest | Author: MKesenheimer
A quick run to see our standard output.
$ ./forest
The forest is dark and dangerous. Be careful!
Please enter the flag:testthismess
The forest is unforgiving.
Flag not correct.
Crack it open
Load up our binary in radare2, analyze all, and disassemble our main function as is my normal workflow.
$ radare2 ./forest
Warning: run r2 with -e bin.cache=true to fix relocations in disassembly
-- Are you a wizard?
[0x000011a0]> aaa
[x] Analyze all flags starting with sym. and entry0 (aa)
[x] Analyze function calls (aac)
[x] Analyze len bytes of instructions for references (aar)
[x] Finding and parsing C++ vtables (avrr)
[x] Type matching analysis for all functions (aaft)
[x] Propagate noreturn information (aanr)
[x] Use -AA or aaaa to perform additional experimental analysis.
[0x000011a0]> afl
0x000011a0 1 47 entry0
0x000011d0 4 41 -> 34 sym.deregister_tm_clones
0x00001200 4 57 -> 51 sym.register_tm_clones
0x00001240 5 65 -> 55 sym.__do_global_dtors_aux
0x00001290 1 9 entry.init0
0x00001000 3 27 sym._init
0x00001310 1 5 sym.__libc_csu_fini
0x00001318 1 13 sym._fini
0x000012a0 4 101 sym.__libc_csu_init
0x00001080 19 288 main
0x00001030 1 6 sym.imp.puts
0x00001040 1 6 sym.imp.__stack_chk_fail
0x00001050 1 6 sym.imp.printf
0x00001060 1 6 sym.imp.__isoc99_scanf
0x00001070 1 6 sym.imp.sqrt
[0x000011a0]> s main
[0x00001080]> pdf
;-- section..text:
; DATA XREF from entry0 @ 0x11c1
┌ 288: int main (int argc, char **argv, char **envp);
│ ; var uint32_t var_ah @ rsp+0x12
│ ; var int64_t var_bh @ rsp+0x13
│ ; var int64_t var_ch @ rsp+0x14
│ ; var int64_t var_dh @ rsp+0x15
│ ; var uint32_t var_eh @ rsp+0x16
│ ; var uint32_t var_fh @ rsp+0x17
│ ; var uint32_t var_10h @ rsp+0x18
│ ; var uint32_t var_11h @ rsp+0x19
│ ; var uint32_t var_12h @ rsp+0x1a
│ ; var uint32_t var_13h @ rsp+0x1b
│ ; var uint32_t var_14h @ rsp+0x1c
│ ; var uint32_t var_15h @ rsp+0x1d
│ ; var uint32_t var_16h @ rsp+0x1e
│ ; var int64_t var_18h @ rsp+0x20
│ 0x00001080 4883ec28 sub rsp, 0x28 ; [14] -r-x section size 661 named .text
│ 0x00001084 488d3d7d0f00. lea rdi, str.The_forest_is_dark_and_dangerous._Be_careful_ ; 0x2008 ; "The forest is dark and dangerous. Be careful!" ; const char *s
│ 0x0000108b 64488b042528. mov rax, qword fs:[0x28]
│ 0x00001094 4889442418 mov qword [var_18h], rax
│ 0x00001099 31c0 xor eax, eax
│ 0x0000109b e890ffffff call sym.imp.puts ; int puts(const char *s)
│ 0x000010a0 488d3dee0f00. lea rdi, str.Please_enter_the_flag: ; 0x2095 ; "Please enter the flag:" ; const char *format
│ 0x000010a7 31c0 xor eax, eax
│ 0x000010a9 e8a2ffffff call sym.imp.printf ; int printf(const char *format)
│ 0x000010ae 31c0 xor eax, eax
│ 0x000010b0 488d74240a lea rsi, [var_ah]
│ 0x000010b5 488d3df00f00. lea rdi, str._13s ; 0x20ac ; "%13s" ; const char *format
│ 0x000010bc e89fffffff call sym.imp.__isoc99_scanf ; int scanf(const char *format)
│ 0x000010c1 807c240a72 cmp byte [var_ah], 0x72
│ ┌─< 0x000010c6 7514 jne 0x10dc
│ │ 0x000010c8 660fbe44240b movsx ax, byte [var_bh]
│ │ 0x000010ce ba0a000000 mov edx, 0xa
│ │ 0x000010d3 f6fa idiv dl
│ │ 0x000010d5 0fb6c4 movzx eax, ah
│ │ 0x000010d8 2c01 sub al, 1
│ ┌──< 0x000010da 7429 je 0x1105
│ ││ ; XREFS: CODE 0x000010c6 CODE 0x00001127 CODE 0x00001129 CODE 0x00001135 CODE 0x0000113c CODE 0x00001143
│ ││ ; XREFS: CODE 0x0000114a CODE 0x00001151 CODE 0x00001158 CODE 0x0000115f CODE 0x0000116a CODE 0x00001175
│ ││ ; XREFS: CODE 0x00001180
│ ┌┌┌┌┌─└─> 0x000010dc 488d3d850f00. lea rdi, str.The_forest_is_unforgiving._nFlag_not_correct. ; 0x2068 ; "The forest is unforgiving.\nFlag not correct." ; const char *format
│ |||||│ 0x000010e3 31c0 xor eax, eax
│ |||||│ 0x000010e5 e866ffffff call sym.imp.printf ; int printf(const char *format)
│ |||||│ ; CODE XREF from main @ 0x1194
│ |||||│┌─> 0x000010ea 488b442418 mov rax, qword [var_18h]
│ |||||│| 0x000010ef 64482b042528. sub rax, qword fs:[0x28]
│ ────────< 0x000010f8 0f859b000000 jne 0x1199
│ |||||│| 0x000010fe 31c0 xor eax, eax
│ |||||│| 0x00001100 4883c428 add rsp, 0x28
│ |||||│| 0x00001104 c3 ret
│ |||||│| ; CODE XREF from main @ 0x10da
│ |||||└──> 0x00001105 0fbe44240c movsx eax, byte [var_ch]
│ ||||| | 0x0000110a 660fefc0 pxor xmm0, xmm0
│ ||||| | 0x0000110e f20f2ac0 cvtsi2sd xmm0, eax
│ ||||| | 0x00001112 e859ffffff call sym.imp.sqrt ; floating_point sqrt(arithmetic x)
│ ||||| | 0x00001117 f20f5905990f. mulsd xmm0, qword [0x000020b8]
│ ||||| | 0x0000111f 660f2e05990f. ucomisd xmm0, qword [0x000020c0]
│ ────────< 0x00001127 7ab3 jp 0x10dc
│ ────────< 0x00001129 75b1 jne 0x10dc
│ ||||| | 0x0000112b 0fb644240d movzx eax, byte [var_dh]
│ ||||| | 0x00001130 83e801 sub eax, 1
│ ||||| | 0x00001133 3c71 cmp al, 0x71
│ ────────< 0x00001135 77a5 ja 0x10dc
│ ||||| | 0x00001137 807c240e69 cmp byte [var_eh], 0x69
│ ────────< 0x0000113c 759e jne 0x10dc
│ ||||| | 0x0000113e 807c240f64 cmp byte [var_fh], 0x64
│ ────────< 0x00001143 7597 jne 0x10dc
│ ||||| | 0x00001145 807c241069 cmp byte [var_10h], 0x69
│ ────────< 0x0000114a 7590 jne 0x10dc
│ ||||| | 0x0000114c 807c24116e cmp byte [var_11h], 0x6e
│ ────────< 0x00001151 7589 jne 0x10dc
│ ||||| | 0x00001153 807c241267 cmp byte [var_12h], 0x67
│ └───────< 0x00001158 7582 jne 0x10dc
│ |||| | 0x0000115a 807c241368 cmp byte [var_13h], 0x68
│ └──────< 0x0000115f 0f8577ffffff jne 0x10dc
│ ||| | 0x00001165 807c24146f cmp byte [var_14h], 0x6f
│ └─────< 0x0000116a 0f856cffffff jne 0x10dc
│ || | 0x00001170 807c24156f cmp byte [var_15h], 0x6f
│ └────< 0x00001175 0f8561ffffff jne 0x10dc
│ | | 0x0000117b 807c241664 cmp byte [var_16h], 0x64
│ └───< 0x00001180 0f8556ffffff jne 0x10dc
│ | 0x00001186 488d3dab0e00. lea rdi, str.You_escaped_the_forest._nFlag_is_correct. ; 0x2038 ; "You escaped the forest.\nFlag is correct." ; const char *format
│ | 0x0000118d 31c0 xor eax, eax
│ | 0x0000118f e8bcfeffff call sym.imp.printf ; int printf(const char *format)
│ └─< 0x00001194 e951ffffff jmp 0x10ea
│ ; CODE XREF from main @ 0x10f8
│ ────────> 0x00001199 e8a2feffff call sym.imp.__stack_chk_fail
└ 0x0000119e 6690 nop
1st byte - simple comparrison
From the jump, it looks like we take our user input and then compare the first byte to 0x72 (72 = r) as the initial check. If we fail this check at the jump-not-equal (jne) instruction we are redirected to 0x10dc which contains the “the forest is unforgiving” message.
│ 0x000010bc e89fffffff call sym.imp.__isoc99_scanf ; int scanf(const char *format)
│ 0x000010c1 807c240a72 cmp byte [var_ah], 0x72 ; Character "r"
│ ┌─< 0x000010c6 7514 jne 0x10dc
... cut ...
│ ┌┌┌┌┌─└─> 0x000010dc 488d3d850f00. lea rdi, str.The_forest_is_unforgiving._nFlag_not_correct. ; 0x2068 ; "The forest is unforgiving.\nFlag not correct." ; const char *format
So the first byte of our solution is “r”, moving on the second and third byte are less straightforward.
2nd byte - signed divide
The second byte is validated with a signed divide instruction (idiv) which I needed to look into. I read up on the instruction here (https://www.felixcloutier.com/x86/idiv).
An important thing to note from the reference material.
| Divisor Operand Size | Dividend | Quotient | Remainder |
|---|---|---|---|
| byte | AX | AL | AH |
| word | DX:AX | AX | DX |
| long | EDX:EAX | EAX | EDX |
First, we move our byte into the ax register with movsx, this allows us to move the smaller byte into a larger register by way of sign-extending the data. For instance, if our byte was another “r” (0x72) it might look something like movsx ax, byte 0x72 and as a result, our ax register would then contain 00000072.
Then we move 0xa (10) into the edx register. Followed by our signed divide instruction referencing an 8-byte register dl which is the lowest 8 bytes of our edx register containing 0xa (10).
So we are dividing our byte 0x72 by 0xa (decimal 114 / 10) and then moving the value of the remainder (4) into eax.
After moving our reminder we subtract 1 from that value and check if it equals 0 with the je (jump if equal) instruction.
So we can conclude that any character that returns a remainder of 1 when divided by 10 is a valid character.
Some valid characters: 3, ), =, [, e, o, y, G, Q
│ │ 0x000010c8 660fbe44240b movsx ax, byte [var_bh] ; Move our 2nd byte into ax
│ │ 0x000010ce ba0a000000 mov edx, 0xa ; moxe 0xa (10) into edx
│ │ 0x000010d3 f6fa idiv dl ; signed divide ax / dl
│ │ 0x000010d5 0fb6c4 movzx eax, ah ; move remainder into eax
│ │ 0x000010d8 2c01 sub al, 1 ; subtract one
│ ┌──< 0x000010da 7429 je 0x1105 ; jump if zero
3rd byte - floating point arithmetic
For the third byte, we have some floating-point arithmetic and doubles to deal with. You can read more about some of these instructions here, although a strong understanding is not needed for this challenge.
- cvtsi2sd: https://www.felixcloutier.com/x86/cvtsi2sd
- sqrt: https://www.felixcloutier.com/x86/fsqrt
- mulsd: https://www.felixcloutier.com/x86/mulsd
- ucomisd: https://www.felixcloutier.com/x86/ucomisd
For our purposes, we will work backward starting at the ucomisd instruction which is just a compare instruction for double-precision floating-point values.
In radare2 items in square brackets like [0x000020b8] are references to memory, so if we know we are dealing with doubles we can print out that data in the appropriate format quite easily. Here I go ahead and print both references in this section.
Help strings from radare2 for reference.
| pf[?][.nam] [fmt] print formatted data (pf.name, pf.name $<expr>)
...cut...
| pf fmt Show data using the given format-string. See 'pf??' and 'pf???'.
...cut...
| F double value (8 bytes)
Retreiving our values stored in memory.
[0x00001080]> pf F @ 0x000020b8
0x000020b8 = 5
[0x00001080]> pf F @ 0x000020c0
0x000020c0 = 50
Putting it all together.
│ |||||└──> 0x00001105 0fbe44240c movsx eax, byte [var_ch] ; move our character into eax
│ ||||| | 0x0000110a 660fefc0 pxor xmm0, xmm0 ; zero out xmm0
│ ||||| | 0x0000110e f20f2ac0 cvtsi2sd xmm0, eax ; convert into double-precision floating-point and store in xmm0
│ ||||| | 0x00001112 e859ffffff call sym.imp.sqrt ; floating_point sqrt(arithmetic x) ; get sqrt of our value
│ ||||| | 0x00001117 f20f5905990f. mulsd xmm0, qword [0x000020b8] ; multiply by 5
│ ||||| | 0x0000111f 660f2e05990f. ucomisd xmm0, qword [0x000020c0] ; compare to 50
│ ────────< 0x00001127 7ab3 jp 0x10dc
So we can see that the square root of our input multiplied by 5 must be 50, with this information we know that our number must be 100 which is “d”.
Ascii “d” = decimal 100
√100 = 10
10 * 5 = 50
4th byte - subtract and compare
Our final indirect comparison is on byte 4, we simply compare our value with “0x71” after subtracting 1, so our character is “0x72” or “r”.
│ ||||| | 0x0000112b 0fb644240d movzx eax, byte [var_dh]
│ ||||| | 0x00001130 83e801 sub eax, 1 ; subtract 1
│ ||||| | 0x00001133 3c71 cmp al, 0x71 ; compare to 0x71 "q" so if we add the subtracted one back we get 0x72 "r"
│ ────────< 0x00001135 77a5 ja 0x10dc
Remaining bytes
The remaining bytes are all straightforward comparisons.
│ ||||| | 0x00001137 807c240e69 cmp byte [var_eh], 0x69 ; char "i"
│ ────────< 0x0000113c 759e jne 0x10dc
│ ||||| | 0x0000113e 807c240f64 cmp byte [var_fh], 0x64 ; char "d"
│ ────────< 0x00001143 7597 jne 0x10dc
│ ||||| | 0x00001145 807c241069 cmp byte [var_10h], 0x69 ; char "i"
│ ────────< 0x0000114a 7590 jne 0x10dc
│ ||||| | 0x0000114c 807c24116e cmp byte [var_11h], 0x6e ; char "n"
│ ────────< 0x00001151 7589 jne 0x10dc
│ ||||| | 0x00001153 807c241267 cmp byte [var_12h], 0x67 ; char "g"
│ └───────< 0x00001158 7582 jne 0x10dc
│ |||| | 0x0000115a 807c241368 cmp byte [var_13h], 0x68 ; char "h"
│ └──────< 0x0000115f 0f8577ffffff jne 0x10dc
│ ||| | 0x00001165 807c24146f cmp byte [var_14h], 0x6f ; char "o"
│ └─────< 0x0000116a 0f856cffffff jne 0x10dc
│ || | 0x00001170 807c24156f cmp byte [var_15h], 0x6f ; char "o"
│ └────< 0x00001175 0f8561ffffff jne 0x10dc
│ | | 0x0000117b 807c241664 cmp byte [var_16h], 0x64 ; char "d"
│ └───< 0x00001180 0f8556ffffff jne 0x10dc
Conclusion
So after all that we have the following valid flags.
r3dridinghood
r)dridinghood
r=dridinghood
r[dridinghood
redridinghood
rodridinghood
rydridinghood
rGdridinghood
rQdridinghood
proof:
$ while read p; do echo "$p" && echo "$p" | ./forest; done < forest_list | grep -Eo "r.dridinghood|Flag is correct."
r3dridinghood
Flag is correct.
r)dridinghood
Flag is correct.
r=dridinghood
Flag is correct.
r[dridinghood
Flag is correct.
redridinghood
Flag is correct.
rodridinghood
Flag is correct.
rydridinghood
Flag is correct.
rGdridinghood
Flag is correct.
rQdridinghood
Flag is correct.