writeups/hah/asis2019.md

   1 # ASIS CTF Finals 2019
   2 ## Retrospective
   3 Luckily I could spend two afternoons to work uninterruptedly on challenges during the Asis CTF. Even though I started with a bit of delay on saturday I quickly found a pwn challenge that was already available and still unsolved that looked interesting which I ultimately finished in the late afternoon. I didn't expect to get far on sunday due to less time but decided to take on a Reverse/Misc-challenge because the full python source code was available and it seemed easier to get into than some others, and I managed to finish it in time before the CTF ended as well. I had some cursory looks at other challenges as well but did not seriously attempt any of them.
   4 All in all the challenges I solved weren't extremely complicated and I spent more time on them than was probably necessary figuring some things out; especially "Cursed app" was simpler when I analyzed it after having finished it than it seemed like during working on it, but both were interesting nonetheless and were fun to figure out. I was slowed down by not being too familiar with all the relevant assembly instructions in "Cursed app", and wasted some time on both challenges by not analyzing them closely enough before taking them on, but it was a good learning experience.
   5
   6 ## Challenges
   7 ### Cursed app
   8 * Category: Reverse
   9 * 60 solves / 90 points
  10 * Time spent: ~4 hours
  11 ```
  12 If we want to say 100, should we start at 1 and count until 100?
  13
  14 sha256(flag) = dd791346264fc02ddcd2466b9e8b2b2bba8057d61fbbc824d25c7957c127250d
  15 ```
  16
  17 The "cursed app" was a ELF binary that analyzed the contents of a file passed as an argument; depending on whether it contained the correct file or not it printed a message to let the user know.
  18 Looking at the binary in cutter revealed a lot of similar looking blocks that all ended in a conditional jump to the program section that printed the message indicating a wrong flag; the blocks iterated over an ever increasing variable that was probably the content read from the file, and in total 59 positions were handled suggesting that the flag was 59 characters long, of which the first 5 and the last one were known. Storing "ASIS{" in the file provided to the executable and stepping through indeed showed that the first five blocks in question passed successfully but the check in the sixth one jumped to the error message. Now knowing for sure that each code block analyzed a character by reading the byte value, doing calculations based on it and finally checking the results to decide whether to proceed or fail it was simply a matter of reversing the calculations to retrieve the correct characters one by one.
  19 The calculations had a similar structure but seemed to vary a bit so I transferred the to python one after another in order to iterate over all printable characters and find the ones for which the calculations worked out; only after having retrieved the flag and cleaning up the script did I realize that not only could most parts be copy-pasted with some values exchanged, but they actually all had the exact same structure if fed with the appropriate values. For example some blocks were missing instructions that were present in most others, but they could simply be performed by the same function by providing parameters that simply neutralized those instructions, such as multiplying values by 1 to simply prevent any changes taking place.
  20 The basic structure of the function was as follows:
  21
  22 - Read character byte value into EAX, multiply it by some value and then add to it.
  23 - Perform a CDQ instruction which sign-extends the value in EAX by copying the sign bit into every bit of the EDX register. Because we know that our bytes are all positive due to representing printable characters and only being multiplied by positive numbers this effectively serves as a way to zero out EDX.
  24 - An IDIV instruction is performed which divides EAX by the provided argument and stores the result in EAX and, more importantly, the remainder in EDX. Because EDX wasn't explicitely mentioned in the assembly code this was a bit tricky to figure out when just translating the obvious calculation steps into python because they obviously didn't match and no characters for which they worked out could be found.
  25 - The value of EDX is then copied to EAX and, multiplied by some value, into ESI.
  26 - EAX and EDX are multiplied by some values.
  27 - Values are added to EAX and ESI, this time not by ADD instructions but by way of LEAs.
  28 - Finally there's another EAX IDIV followed by a TEST on EDX and a JNE conditional jump; effectively at this point EAX has to be a multiple of the divisor, thus writing a remainder of 0 into EDX which is the only way to avoid a jump to the error message, instead continuing into the next block loading and analyzing the following character.
  29
  30 Most of the calculation steps were pretty straight forward, but some such as IDIV and CDQ had some side effects that weren't easily spotted in the disassembly and required some analysis. In some blocks certain instructions were changed, such as a multiplication being replace by a shift, which made them look more different than they actually were. The challenge description was probably a hint to that fact.
  31 Transcribing the calculations to python this way allowed for bruteforcing the character in each position, with some being obvious due to the flag format. The following script is a heavily cleaned up version that defines the basic structure that is common to each calculation and provides the appropriate values visible in the disassembly to construct a function for each position into which characters can be passed to check whether they pass the test (returning the remainder of the final division):
  32
  33 ```python
  34 #!/usr/bin/env python
  35
  36 import string
  37
  38 def calc(char, eax_m_1, eax_a_1, esi_m, edx_m_1, eax_m_2, eax_s_1, esi_s_1):
  39     ecx = 0x100
  40     eax = ord(char)
  41     eax *= eax_m_1
  42     eax += eax_a_1
  43     edx = eax % ecx
  44     eax = edx
  45     esi = edx * esi_m
  46     eax *= edx
  47     edx *= edx_m_1
  48     eax *= eax_m_2
  49     eax = eax + esi + eax_s_1
  50     esi = edx + esi_s_1
  51     edx = eax % esi
  52     return edx
  53
  54 calculations = [
  55     lambda char: 0 if c == "A" else 1,
  56     lambda char: 0 if c == "S" else 1,
  57     lambda char: 0 if c == "I" else 1,
  58     lambda char: 0 if c == "S" else 1,
  59     lambda char: 0 if c == "{" else 1,
  60     lambda char: calc(char, 91, 2, 0x2f7, 0x30e, 5, 0x4b, 0x55),
  61     lambda char: calc(char, 0x43, 0x76, 0xed, 0x106, 0x37d, 0x1f1, 0xdd),
  62     lambda char: calc(char, 0xe7, 0x74, 0x287, 0xf5, 0x213, 0x3e5, 0x184),
  63     lambda char: 0 if c == "_" else 1,
  64     lambda char: calc(char, 0xcb, 0x88, 0x95, 0x78, 0x336, 0x3bd, 0x230),
  65     lambda char: calc(char, 0x51, 0x96, 0x2b0, 0x144, 0x9d, 0x21a, 0x265),
  66     lambda char: calc(char, 0x29, 0x8d, 0x2db, 0x15, 0x56, 0xcb, 0x203),
  67     lambda char: calc(char, 0x73, 0x5f, 0x178, 0x116, 0x2df, 0x88, 0x262), # _
  68     lambda char: calc(char, 0xf3, 0xe4, 0xdd, 0xca, 0x31b, 0x37c, 0x33b),
  69     lambda char: calc(char, 0x4f, 0x51, 0x345, 0x234, 0x66, 0x366, 0xf9),
  70     lambda char: calc(char, 0x7b, 0x8e, 0x2b0, 5, 0x12e, 0x282, 0xd5),
  71     lambda char: calc(char, 0xa9, 0x59, 0x272, 0x96, 0xe, 0x2a8, 0x1c8), #_
  72     lambda char: calc(char, 0xad, 0xe6, 0x214, 0x19f, 0x33e, 0x12e, 0x1f1),
  73     lambda char: calc(char, 0xab, 0x9a, 0x72, 2**5, 0x10f, 0xe2, 0x292),
  74     lambda char: calc(char, 0x4b, 0xb8, 0x35a, 0x37d, 0x366, 0x39, 0x1a8),
  75     lambda char: calc(char, 0xf5, 0x5b, 0x2f3, 0x6a, 0x375, 0x9d, 0x3d7),
  76     lambda char: 0 if c == "_" else 1,
  77     lambda char: calc(char, 0x3d, 0x69, 0x3c0, 0x3e, 0x3cb, 0x214, 0x390),
  78     lambda char: calc(char, 0x9f, 0x2c, 0x1d8, 0x29, 0x215, 0x7a, 0x32),
  79     lambda char: calc(char, 0x77, 0xef, 0x21f, 0x38, 0xa7, 0x308, 0x290), #_
  80     lambda char: calc(char, 0xb3, 0x70, 0x3ce, 0x87, 0xf8, 0x19e, 0x52),
  81     lambda char: calc(char, 0x47, 0xae, 0x1cf, 0xa, 0x2f3, 0x115, 0x113),
  82     lambda char: calc(char, 0xbf, 0x90, 0x2a6, 0x37, 0xe3, 0x234, 0x27a),
  83     lambda char: calc(char, 0x51, 0x9b, 0x210, 0x173, 0x379, 0x330, 0x2ea),
  84     lambda char: calc(char, 0x57, 0xc8, 0x2e0, 0x2e6, 0x14d, 0x25, 0xd),
  85     lambda char: calc(char, 0xa7, 0xa0, 0xc8, 0x382, 0x27c, 0xd5, 0x265),
  86     lambda char: 0 if c == "_" else 1,
  87     lambda char: calc(char, 0x71, 0xd9, 0x34b, 0x14d, 0x8a, 0xfc, 0x244),
  88     lambda char: calc(char, 0xaf, 9, 0x164, 0x69, 0x1ae, 0x2cb, 0x1fc),
  89     lambda char: calc(char, 0xdb, 0xa6, 0x2ca, 2, 0xac, 0x32c, 0x124),
  90     lambda char: calc(char, 0xb3, 0x39, 0x3be, 0x1f1, 0x358, 0x2b9, 0x3be),
  91     lambda char: 0 if c == "_" else 1,
  92     lambda char: calc(char, 0x3d, 0xf0, 0x3b9, 0x78, 0x141, 0x1ec, 0x199),
  93     lambda char: calc(char, 0x29, 0x76, 0x10c, 0x4a, 0x7b, 0x3c4, 0x14e),
  94     lambda char: calc(char, 0x2d, 0x96, 0x210, 0xd, 0x264, 0x16c, 0x27d),
  95     lambda char: 0 if c == "_" else 1,
  96     lambda char: calc(char, 0x3f, 0xa0, 0x15a, 0xf0, 0x388, 0x34d, 0x3d),
  97     lambda char: calc(char, 0xd3, 0x72, 0x22a, 0x93, 0x22f, 0x299, 0x379),
  98     lambda char: calc(char, 0x79, 2, 0x3df, 0x82, 0x2cf, 0x32b, 0x195),
  99     lambda char: calc(char, 0x75, 0xe6, 0x134, 0x27, 0x21d, 0x12c, 0x29),
 100     lambda char: calc(char, 0x51, 0x52, 0x253, 0x23, 0x234, 0x229, 0x205),
 101     lambda char: 0 if c == "_" else 1,
 102     lambda char: calc(char, 0xed, 0xa5, 0x306, 0x24, 0x203, 0x14b, 0x28c),
 103     lambda char: calc(char, 0x81, 0x7f, 0x1a4, 0xb, 0x362, 0x14, 0x15a),
 104     lambda char: calc(char, 0x19, 0xeb, 0x67, 0x211, 0xb8, 0x140, 0x17e),
 105     lambda char: calc(char, 0x9b, 0x3a, 0x33c, 0x46, 0x357, 0xa0, 0x10e),
 106     lambda char: calc(char, 0x55, 0xf0, 0x234, 0xa, 0x3b7, 0xd5, 0x207),
 107     lambda char: calc(char, 0x49, 0x3d, 0x79, 0x7, 0x282, 0x362, 0x142),
 108     lambda char: calc(char, 0x81, 0x56, 0x326, 0x17, 0x3d, 0x181, 0x14f),
 109     lambda char: calc(char, 0x9b, 0xb1, 0xc4, 0x65, 0x18f, 0x24, 0xda),
 110     lambda char: calc(char, 0x99, 0x7e, 0x116, 0x3c, 0x360, 0x2aa, 0x142),
 111     lambda char: calc(char, 0xe3, 0xf5, 0x152, 0x51, 0x123, 0x1f8, 0x2bc),
 112     lambda char: calc(char, 0xc3, 0x16, 0x3ca, 0x148, 0x300, 0x13, 0x1e1)
 113 ]
 114
 115 possible_chars = string.printable
 116
 117 for i in range(len(calculations)):
 118     for c in possible_chars:
 119         if calculations[i](c) == 0:
 120             print("Found character for index {}: {}".format(i, c))
 121 ```
 122
 123 ### Yet funny (Misc/Reverse / 154pts / 29 solves)
 124 * Category: Misc/Reverse
 125 * 29 solves / 154 points
 126 * Time spent: ~7 hours
 127 ```
 128 Sometimes you come up with something incredibly stupid yet funny.
 129 Don`t ignore it!
 130
 131 nc 76.74.177.238 7777
 132 ```
 133
 134 This challenge was a python script running on a remote server that consisted of two parts: A proof of work as well as the possibility to modifiy C++-code in a limited way that then was compiled and executed on the server; only if it exited with status 0 the flag was read and printed.
 135
 136 #### Proof of work
 137 The proof of work generated a random string of a random length between 10 and 40, hashed it with one randomly selected function out of five and printed the final 6 characters; the task was to find and enter the correct random string.
 138 This was easily solvable by parsing the provided information and bruteforcing strings of the appropriate lengths and hash functions. The actual work that had to be proven wasn't massive bcause the strings mainly consisted of zeroes and only a couple of relevant characters at the end; this was pretty straight forward and mainly a speedbump.
 139
 140 #### Randomized C++-program
 141 After clearing the proof of work the second part of the program could be accessed: Here a simple C++-function was filled with four randomly generated integers and could be displayed. To get to the flag two of thos values had to be replaced by user input, and only if they then matched a simple formula the information would be displayed.
 142
 143 ```c++
 144 #include <stdio.h>
 145 int main(){
 146     int c = 0, d = 0;
 147     c = first_number, d = second_number;
 148     int a = first_random, b = second_random;
 149     if((a*c + b*d) == 1)
 150         return 0;
 151     return -1;
 152 }
 153 ```
 154
 155 ```first_random` and ```second_random``` were immutable random numbers while ```first_number``` and ```second_number``` would be replaced by user input. However this user input was filtered: Besides making sure that only printable characters were present, there was an additional function that was executed on each input:
 156
 157 ```python
 158 def aux(inp):
 159     pm = set(inp)
 160     try:
 161         vux = inp.replace(list(pm)[0] * 2, chr(0)).replace(list(pm)[1] * 2, chr(1))
 162         if set(vux) == set([chr(0), chr(1)]) and len(inp) <1<<10:
 163             return True and len(inp) > 4
 164     except:
 165         pass
 166     return False
 167 ```
 168
 169 This had me stumbling around for a bit: At first I thought the first two characters of each input had to be 0 and 1, but at some point I realized that the conversions to and from sets indeed had a point: They reduced the input to the unique values present, and by replacing the first two and then comparing the sets this effectively ensured that only two different characters were present; the multiplication of course didn't alter those characters but ensured that only pairs would be replaced, further limiting the input to strings of at least 4 characters, consisting only of pairs of two unique characters.
 170 Having cleared that hurdle it was time to think about possible inputs. The first obvious idea was to insert two slashes to comment out parts of the code to alter the variables and thus the calculations, but there was no way to get legal C++-code this way and get the compilation pass. However the compiler errors were helpfully printed out and pointed out a peculiarity in the way the user input was used to subsitute program parts that was present in the available python code:
 171
 172 ```python
 173     tmp_code = code
 174     tmp_code = str(tmp_code).replace("first_random", str(first_rand))
 175     tmp_code = str(tmp_code).replace("second_random", str(second_rand))
 176     tmp_code = str(tmp_code).replace("first_number", str(first_var) + "c+" + str(first_number))
 177     tmp_code = str(tmp_code).replace("second_number", str(second_var) + "d+" + str(second_number))
 178 ```
 179
 180 Instead of replacing the placeholder text in the source code the script actually inserted the user input followed by the variable name and another addition, resulting in a line like:
 181
 182 ```c++
 183 c = <USER_INPUT>c+<first_number>, d = <USER_INPUT>d+<second_number>;
 184 ```
 185
 186 Considering the input could only consist of pairs of the same character there was no way to end the statement early by inserting a semicolon or commenting parts of it out, but there are pairs of characters that could immediately preceed variables and result in legal code: Pre-increments and pre-decrements.
 187 While I at first only tested with up to six characters because thats what I had used to analyze the ```aux```-function I at some point realized that it also explicitely checked the input length and not only limited it to being at least 6 characters but also added an upper bound of 1024. Because two different characters were required to be present, resulting in an increment and a decrement that cancelled each other out, this left 509 operations that could be performed on either variable which opened up a huge range of values that could possibly be used in the program.
 188 With this information it was again down to bruteforcing the values by iterating over them until a combination was found that satisfied the formula, then generating and submitting the appropriate string.
 189
 190 The following steps combine both tasks and exploit the remote server fully automatted retrieving the flag:
 191
 192 ```python
 193 #!/usr/bin/env python
 194
 195 from pwn import *
 196 import string
 197 from parse import *
 198 from hashlib import *
 199 from itertools import chain, product
 200
 201 prompt1_template = "Please submit a printable string X, such that {}(X)[-6:] = {} and len(X) = {}"
 202 vars_cd_template = "           c = {}, d = {};"
 203 vars_ab_template = "           int a = {}, b = {};"
 204 HASH = {"md5": md5, "sha1": sha1, "sha224": sha224, "sha256": sha256, "sha384": sha384, "sha512": sha512}
 205
 206 def pow(algo, hash, len):
 207     candidates = product(string.printable, repeat=int(len))
 208     for candidate in candidates:
 209         if HASH[algo](''.join(candidate)).hexdigest()[-6:] == hash:
 210             return ''.join(candidate)
 211
 212 def find_solution_strings(a, b, c, d):
 213     solution_string = "++--"
 214     for c_diff in range(-509, 509):
 215         for d_diff in range(-509, 509):
 216             if a*(c + c_diff) + b*(d + d_diff) == 1:
 217                 print("Solution found!")
 218                 solution_string_c = abs(c_diff)*"--" if c_diff < 0 else c_diff*"++"
 219                 solution_string_d = abs(d_diff)*"--" if d_diff < 0 else d_diff*"++"
 220                 return solution_string + solution_string_c, solution_string + solution_string_d
 221
 222 def exploit():
 223     r = remote("76.74.177.238", "7777")
 224
 225     print("##### Step 1: Proof of work #####")
 226     prompt1_request = r.recvline()
 227     prompt1_data = parse(prompt1_template, prompt1_request)
 228     print("Attempting PoW: {}(X) = {}, len(X) = {}".format(prompt1_data[0], prompt1_data[1], prompt1_data[2]))
 229     correct_X = pow(prompt1_data[0], prompt1_data[1], prompt1_data[2])
 230     print("Found PoW: {}".format(correct_X))
 231     r.sendline(correct_X)
 232
 233     print("##### Step 2: Find equation solution #####")
 234     r.recvline_endswith("[Q]uit!")
 235     r.sendline("g")
 236     r.recvline_endswith("d = 0;")
 237     vars_cd_line = r.recvline()
 238     vars_ab_line = r.recvline()
 239     vars_cd_data = parse(vars_cd_template, vars_cd_line)
 240     vars_ab_data = parse(vars_ab_template, vars_ab_line)
 241     a = int(vars_ab_data[0])
 242     b = int(vars_ab_data[1])
 243     c = int(vars_cd_data[0])
 244     d = int(vars_cd_data[1])
 245     print("Challenge: a = {}, b = {}, c = {}, d = {}".format(a, b, c, d))
 246     solution_c, solution_d = find_solution_strings(a, b, c, d)
 247     r.recvline_endswith("[Q]uit!")
 248     r.sendline("t")
 249     r.recvline_endswith("first variable:")
 250     r.sendline(solution_c)
 251     r.recvline_endswith("second variable:")
 252     r.sendline(solution_d)
 253     flag_line = r.recvline()
 254     r.close()
 255     print(flag_line)
 256
 257 if __name__ == "__main__":
 258     exploit()
 259 ```