writeups/hah/asis2019.md

   1 # Retrospective
   2 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.
   3 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.
   4
   5 # Challenges
   6 ## Cursed app
   7 ```
   8 If we want to say 100, should we start at 1 and count until 100?
   9
  10 sha256(flag) = dd791346264fc02ddcd2466b9e8b2b2bba8057d61fbbc824d25c7957c127250d
  11 ```
  12
  13 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.
  14 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.
  15 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.
  16 The basic structure of the function was as follows:
  17
  18 - Read character byte value into EAX, multiply it by some value and then add to it.
  19 - 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.
  20 - 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.
  21 - The value of EDX is then copied to EAX and, multiplied by some value, into ESI.
  22 - EAX and EDX are multiplied by some values.
  23 - Values are added to EAX and ESI, this time not by ADD instructions but by way of LEAs.
  24 - 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.
  25
  26 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.
  27 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):
  28
  29 ```python
  30 #!/usr/bin/env python
  31
  32 import string
  33
  34 def calc(char, eax_m_1, eax_a_1, esi_m, edx_m_1, eax_m_2, eax_s_1, esi_s_1):
  35     ecx = 0x100
  36     eax = ord(char)
  37     eax *= eax_m_1
  38     eax += eax_a_1
  39     edx = eax % ecx
  40     eax = edx
  41     esi = edx * esi_m
  42     eax *= edx
  43     edx *= edx_m_1
  44     eax *= eax_m_2
  45     eax = eax + esi + eax_s_1
  46     esi = edx + esi_s_1
  47     edx = eax % esi
  48     return edx
  49
  50 calculations = [
  51     lambda char: 0 if c == "A" else 1,
  52     lambda char: 0 if c == "S" else 1,
  53     lambda char: 0 if c == "I" else 1,
  54     lambda char: 0 if c == "S" else 1,
  55     lambda char: 0 if c == "{" else 1,
  56     lambda char: calc(char, 91, 2, 0x2f7, 0x30e, 5, 0x4b, 0x55),
  57     lambda char: calc(char, 0x43, 0x76, 0xed, 0x106, 0x37d, 0x1f1, 0xdd),
  58     lambda char: calc(char, 0xe7, 0x74, 0x287, 0xf5, 0x213, 0x3e5, 0x184),
  59     lambda char: 0 if c == "_" else 1,
  60     lambda char: calc(char, 0xcb, 0x88, 0x95, 0x78, 0x336, 0x3bd, 0x230),
  61     lambda char: calc(char, 0x51, 0x96, 0x2b0, 0x144, 0x9d, 0x21a, 0x265),
  62     lambda char: calc(char, 0x29, 0x8d, 0x2db, 0x15, 0x56, 0xcb, 0x203),
  63     lambda char: calc(char, 0x73, 0x5f, 0x178, 0x116, 0x2df, 0x88, 0x262), # _
  64     lambda char: calc(char, 0xf3, 0xe4, 0xdd, 0xca, 0x31b, 0x37c, 0x33b),
  65     lambda char: calc(char, 0x4f, 0x51, 0x345, 0x234, 0x66, 0x366, 0xf9),
  66     lambda char: calc(char, 0x7b, 0x8e, 0x2b0, 5, 0x12e, 0x282, 0xd5),
  67     lambda char: calc(char, 0xa9, 0x59, 0x272, 0x96, 0xe, 0x2a8, 0x1c8), #_
  68     lambda char: calc(char, 0xad, 0xe6, 0x214, 0x19f, 0x33e, 0x12e, 0x1f1),
  69     lambda char: calc(char, 0xab, 0x9a, 0x72, 2**5, 0x10f, 0xe2, 0x292),
  70     lambda char: calc(char, 0x4b, 0xb8, 0x35a, 0x37d, 0x366, 0x39, 0x1a8),
  71     lambda char: calc(char, 0xf5, 0x5b, 0x2f3, 0x6a, 0x375, 0x9d, 0x3d7),
  72     lambda char: 0 if c == "_" else 1,
  73     lambda char: calc(char, 0x3d, 0x69, 0x3c0, 0x3e, 0x3cb, 0x214, 0x390),
  74     lambda char: calc(char, 0x9f, 0x2c, 0x1d8, 0x29, 0x215, 0x7a, 0x32),
  75     lambda char: calc(char, 0x77, 0xef, 0x21f, 0x38, 0xa7, 0x308, 0x290), #_
  76     lambda char: calc(char, 0xb3, 0x70, 0x3ce, 0x87, 0xf8, 0x19e, 0x52),
  77     lambda char: calc(char, 0x47, 0xae, 0x1cf, 0xa, 0x2f3, 0x115, 0x113),
  78     lambda char: calc(char, 0xbf, 0x90, 0x2a6, 0x37, 0xe3, 0x234, 0x27a),
  79     lambda char: calc(char, 0x51, 0x9b, 0x210, 0x173, 0x379, 0x330, 0x2ea),
  80     lambda char: calc(char, 0x57, 0xc8, 0x2e0, 0x2e6, 0x14d, 0x25, 0xd),
  81     lambda char: calc(char, 0xa7, 0xa0, 0xc8, 0x382, 0x27c, 0xd5, 0x265),
  82     lambda char: 0 if c == "_" else 1,
  83     lambda char: calc(char, 0x71, 0xd9, 0x34b, 0x14d, 0x8a, 0xfc, 0x244),
  84     lambda char: calc(char, 0xaf, 9, 0x164, 0x69, 0x1ae, 0x2cb, 0x1fc),
  85     lambda char: calc(char, 0xdb, 0xa6, 0x2ca, 2, 0xac, 0x32c, 0x124),
  86     lambda char: calc(char, 0xb3, 0x39, 0x3be, 0x1f1, 0x358, 0x2b9, 0x3be),
  87     lambda char: 0 if c == "_" else 1,
  88     lambda char: calc(char, 0x3d, 0xf0, 0x3b9, 0x78, 0x141, 0x1ec, 0x199),
  89     lambda char: calc(char, 0x29, 0x76, 0x10c, 0x4a, 0x7b, 0x3c4, 0x14e),
  90     lambda char: calc(char, 0x2d, 0x96, 0x210, 0xd, 0x264, 0x16c, 0x27d),
  91     lambda char: 0 if c == "_" else 1,
  92     lambda char: calc(char, 0x3f, 0xa0, 0x15a, 0xf0, 0x388, 0x34d, 0x3d),
  93     lambda char: calc(char, 0xd3, 0x72, 0x22a, 0x93, 0x22f, 0x299, 0x379),
  94     lambda char: calc(char, 0x79, 2, 0x3df, 0x82, 0x2cf, 0x32b, 0x195),
  95     lambda char: calc(char, 0x75, 0xe6, 0x134, 0x27, 0x21d, 0x12c, 0x29),
  96     lambda char: calc(char, 0x51, 0x52, 0x253, 0x23, 0x234, 0x229, 0x205),
  97     lambda char: 0 if c == "_" else 1,
  98     lambda char: calc(char, 0xed, 0xa5, 0x306, 0x24, 0x203, 0x14b, 0x28c),
  99     lambda char: calc(char, 0x81, 0x7f, 0x1a4, 0xb, 0x362, 0x14, 0x15a),
 100     lambda char: calc(char, 0x19, 0xeb, 0x67, 0x211, 0xb8, 0x140, 0x17e),
 101     lambda char: calc(char, 0x9b, 0x3a, 0x33c, 0x46, 0x357, 0xa0, 0x10e),
 102     lambda char: calc(char, 0x55, 0xf0, 0x234, 0xa, 0x3b7, 0xd5, 0x207),
 103     lambda char: calc(char, 0x49, 0x3d, 0x79, 0x7, 0x282, 0x362, 0x142),
 104     lambda char: calc(char, 0x81, 0x56, 0x326, 0x17, 0x3d, 0x181, 0x14f),
 105     lambda char: calc(char, 0x9b, 0xb1, 0xc4, 0x65, 0x18f, 0x24, 0xda),
 106     lambda char: calc(char, 0x99, 0x7e, 0x116, 0x3c, 0x360, 0x2aa, 0x142),
 107     lambda char: calc(char, 0xe3, 0xf5, 0x152, 0x51, 0x123, 0x1f8, 0x2bc),
 108     lambda char: calc(char, 0xc3, 0x16, 0x3ca, 0x148, 0x300, 0x13, 0x1e1)
 109 ]
 110
 111 possible_chars = string.printable
 112
 113 for i in range(len(calculations)):
 114     for c in possible_chars:
 115         if calculations[i](c) == 0:
 116             print("Found character for index {}: {}".format(i, c))
 117 ```
 118
 119 ## Yet funny
 120 ```
 121 Sometimes you come up with something incredibly stupid yet funny.
 122 Don`t ignore it!
 123
 124 nc 76.74.177.238 7777
 125 ```
 126
 127 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.
 128
 129 ### Proof of work
 130 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.
 131 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.
 132
 133 ### Randomized C++-program
 134 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.
 135
 136 ```c++
 137 #include <stdio.h>
 138 int main(){
 139     int c = 0, d = 0;
 140     c = first_number, d = second_number;
 141     int a = first_random, b = second_random;
 142     if((a*c + b*d) == 1)
 143         return 0;
 144     return -1;
 145 }
 146 ```
 147
 148 ```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:
 149
 150 ```python
 151 def aux(inp):
 152     pm = set(inp)
 153     try:
 154         vux = inp.replace(list(pm)[0] * 2, chr(0)).replace(list(pm)[1] * 2, chr(1))
 155         if set(vux) == set([chr(0), chr(1)]) and len(inp) <1<<10:
 156             return True and len(inp) > 4
 157     except:
 158         pass
 159     return False
 160 ```
 161
 162 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.
 163 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:
 164
 165 ```python
 166     tmp_code = code
 167     tmp_code = str(tmp_code).replace("first_random", str(first_rand))
 168     tmp_code = str(tmp_code).replace("second_random", str(second_rand))
 169     tmp_code = str(tmp_code).replace("first_number", str(first_var) + "c+" + str(first_number))
 170     tmp_code = str(tmp_code).replace("second_number", str(second_var) + "d+" + str(second_number))
 171 ```
 172
 173 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:
 174
 175 ```c++
 176 c = <USER_INPUT>c+<first_number>, d = <USER_INPUT>d+<second_number>;
 177 ```
 178
 179 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.
 180 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.
 181 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.
 182
 183 The following steps combine both tasks and exploit the remote server fully automatted retrieving the flag:
 184
 185 ```python
 186 #!/usr/bin/env python
 187
 188 from pwn import *
 189 import string
 190 from parse import *
 191 from hashlib import *
 192 from itertools import chain, product
 193
 194 prompt1_template = "Please submit a printable string X, such that {}(X)[-6:] = {} and len(X) = {}"
 195 vars_cd_template = "           c = {}, d = {};"
 196 vars_ab_template = "           int a = {}, b = {};"
 197 HASH = {"md5": md5, "sha1": sha1, "sha224": sha224, "sha256": sha256, "sha384": sha384, "sha512": sha512}
 198
 199 def pow(algo, hash, len):
 200     candidates = product(string.printable, repeat=int(len))
 201     for candidate in candidates:
 202         if HASH[algo](''.join(candidate)).hexdigest()[-6:] == hash:
 203             return ''.join(candidate)
 204
 205 def find_solution_strings(a, b, c, d):
 206     solution_string = "++--"
 207     for c_diff in range(-509, 509):
 208         for d_diff in range(-509, 509):
 209             if a*(c + c_diff) + b*(d + d_diff) == 1:
 210                 print("Solution found!")
 211                 solution_string_c = abs(c_diff)*"--" if c_diff < 0 else c_diff*"++"
 212                 solution_string_d = abs(d_diff)*"--" if d_diff < 0 else d_diff*"++"
 213                 return solution_string + solution_string_c, solution_string + solution_string_d
 214
 215 def exploit():
 216     r = remote("76.74.177.238", "7777")
 217
 218     print("##### Step 1: Proof of work #####")
 219     prompt1_request = r.recvline()
 220     prompt1_data = parse(prompt1_template, prompt1_request)
 221     print("Attempting PoW: {}(X) = {}, len(X) = {}".format(prompt1_data[0], prompt1_data[1], prompt1_data[2]))
 222     correct_X = pow(prompt1_data[0], prompt1_data[1], prompt1_data[2])
 223     print("Found PoW: {}".format(correct_X))
 224     r.sendline(correct_X)
 225
 226     print("##### Step 2: Find equation solution #####")
 227     r.recvline_endswith("[Q]uit!")
 228     r.sendline("g")
 229     r.recvline_endswith("d = 0;")
 230     vars_cd_line = r.recvline()
 231     vars_ab_line = r.recvline()
 232     vars_cd_data = parse(vars_cd_template, vars_cd_line)
 233     vars_ab_data = parse(vars_ab_template, vars_ab_line)
 234     a = int(vars_ab_data[0])
 235     b = int(vars_ab_data[1])
 236     c = int(vars_cd_data[0])
 237     d = int(vars_cd_data[1])
 238     print("Challenge: a = {}, b = {}, c = {}, d = {}".format(a, b, c, d))
 239     solution_c, solution_d = find_solution_strings(a, b, c, d)
 240     r.recvline_endswith("[Q]uit!")
 241     r.sendline("t")
 242     r.recvline_endswith("first variable:")
 243     r.sendline(solution_c)
 244     r.recvline_endswith("second variable:")
 245     r.sendline(solution_d)
 246     flag_line = r.recvline()
 247     r.close()
 248     print(flag_line)
 249
 250 if __name__ == "__main__":
 251     exploit()
 252 ```