writeups/hah/otw-advent-2019.md

   1 # OverTheWire Advent Bonanza 2019
   2 ## Retrospective
   3 The OverTheWire Advent Bonanza 2019 was really, really fun and allowed me to dive deep into some challenges compared to other CTFs due to the unique way it took place over nearly a month. While on most weekends during which competitions took place I had to split my time between work duties and attempting challenges having them last for more than 48 hours made it both more easy to take enough time to test approaches and to step away when getting stuck and having another look at them the next day. The slower release schedule with only one challenge each day also helped in not jumping around between challenges too much, instead forcing me to spend some time getting to know each one I attempted whereas in other CTFs I tended to switch my focus to other tasks in the hope of finding an attack vector sooner there when hitting a roadblock.
   4 While nearly all of the challenges where quite demanding and I didn't actually solve many while the CTF was taking place I definitely got way further than I would have in a typical short-term competition and learned a lot more simply due to the extended time I got to spend and the increased exchange with others that sometimes only had a look at the challenges days or weeks later when they got around to it but were able to offer some valuable fresh new perspective not having looked at the same task for a while.
   5
   6 ## Challenges
   7 ### Day 5: Sudo Sudoku
   8 * Category: misc/sudoku
   9 * 231 solves / 85 points
  10 * Time spent: ~30 minutes
  11 ```
  12 Santa's little helpers are notoriously good at solving Sudoku puzzles, so they made a special variant...
  13 ```
  14
  15 A downloadable text file contained a partial sudoku with some additional constraints that when solved revealed the flag:
  16 ```
  17 Santa's little helpers are notoriously good at solving Sudoku puzzles.
  18 Because regular Sudoku puzzles are too trivial, they have invented a variant.
  19
  20     1 2 3   4 5 6   7 8 9
  21   +-------+-------+-------+
  22 A | . . . | . . . | . . 1 |
  23 B | . 1 2 | . . . | . . . |
  24 C | . . . | . . . | 2 . . |
  25   +-------+-------+-------+
  26 D | . . . | . . . | . . 2 |
  27 E | . 2 . | . . . | . . . |
  28 F | . . . | . . . | . . . |
  29   +-------+-------+-------+
  30 G | . . . | . . . | 1 2 . |
  31 H | 1 . . | . . 2 | . . . |
  32 I | . . . | 1 . . | . . . |
  33   +-------+-------+-------+
  34
  35 In addition to the standard Sudoku puzzle above,
  36 the following equations must also hold:
  37
  38 B9 + B8 + C1 + H4 + H4 = 23
  39 A5 + D7 + I5 + G8 + B3 + A5 = 19
  40 I2 + I3 + F2 + E9 = 15
  41 I7 + H8 + C2 + D9 = 26
  42 I6 + A5 + I3 + B8 + C3 = 20
  43 I7 + D9 + B6 + A8 + A3 + C4 = 27
  44 C7 + H9 + I7 + B2 + H8 + G3 = 31
  45 D3 + I8 + A4 + I6 = 27
  46 F5 + B8 + F8 + I7 + F1 = 33
  47 A2 + A8 + D7 + E4 = 21
  48 C1 + I4 + C2 + I1 + A4 = 20
  49 F8 + C1 + F6 + D3 + B6 = 25
  50
  51 If you then read the numbers clockwise starting from A1 to A9, to I9, to I1 and
  52 back to A1, you end up with a number with 32 digits.  Enclose that in AOTW{...}
  53 to get the flag.
  54 ```
  55
  56 The official SWI-Prolog documentation contains (a Sudoku-example)[https://www.swi-prolog.org/pldoc/man?section=clpfd-sudoku] that allows for the solving of partially filled puzzles. Adding the additional constraint formulas makes solving the challenge trivial:
  57
  58 ```prolog
  59 day5(Rows) :-
  60     sudoku(Rows),
  61     Rows = [A, B, C, D, E, F, G, H, I],
  62     A = [_,A2,A3, _,A5,_, _,_,1],
  63     B = [_,B2,B3, _,_,B6, _,_,B9],
  64     C = [_,_,C3, C4,_,_, C7,_,_],
  65     D = [_,_,_, _,_,_, _,_,2],
  66     E = [_,2,_, E4,_,_, _,_,E9],
  67     F = [F1,F2,_, _,F5,F6, _,_,_],
  68     G = [_,_,G3, _,_,_, 1,G8,_],
  69     H = [1,_,_, _,_,2, _,_,H9],
  70     I = [I1,I2,_, I4,I5,_, _,I8,_],
  71     G8 #= 2,
  72     B3 #= 2,
  73     B2 #= 1,
  74     C7 #= 2,
  75     I4 #= 1,
  76     B9 + B8 + C1 + H4 + H4 #= 23,
  77     A5 + D7 + I5 + G8 + B3 + A5 #= 19,
  78     I2 + I3 + F2 + E9 #= 15,
  79     I7 + H8 + C2 + D9 #= 26,
  80     I6 + A5 + I3 + B8 + C3 #= 20,
  81     I7 + D9 + B6 + A8 + A3 + C4 #= 27,
  82     C7 + H9 + I7 + B2 + H8 + G3 #= 31,
  83     D3 + I8 + A4 + I6 #= 27,
  84     F5 + B8 + F8 + I7 + F1 #= 33,
  85     A2 + A8 + D7 + E4 #= 21,
  86     C1 + I4 + C2 + I1 + A4 #= 20,
  87     F8 + C1 + F6 + D3 + B6 #= 25,
  88     labeling([], A),
  89     labeling([], B),
  90     labeling([], C),
  91     labeling([], D),
  92     labeling([], E),
  93     labeling([], F),
  94     labeling([], G),
  95     labeling([], H),
  96     labeling([], I).
  97
  98 sudoku(Rows) :-
  99         length(Rows, 9), maplist(same_length(Rows), Rows),
 100         append(Rows, Vs), Vs ins 1..9,
 101         maplist(all_distinct, Rows),
 102         transpose(Rows, Columns),
 103         maplist(all_distinct, Columns),
 104         Rows = [A,B,C,D,E,F,G,H,I],
 105         blocks(A, B, C), blocks(D, E, F), blocks(G, H, I).
 106
 107 blocks([], [], []).
 108 blocks([A,B,C|Bs1], [D,E,F|Bs2], [G,H,I|Bs3]) :-
 109         all_distinct([A,B,C,D,E,F,G,H,I]),
 110         blocks(Bs1, Bs2, Bs3).
 111 ```
 112
 113 When trying to come up with this code I hit two small road blocks: At first I mimicked the documentation too closely and wrote down the provided partial solution outside of the "day5"-goal instead of explicitely restraining the fields inside of it which tripped up the solution finding. I also forgot to add the ```labeling()```-rules which resulted in Prolog not offering a numerical solution but just a formulaic one containing variables instead of constants. By the time I had those two errors figured out and fixed @georg had already found the correct sudoku and flag using z3, yet this challenge was definitely the quickest and easiest I worked on during the CTF, requiring only about 30 minutes of more-or-less concentrated effort.
 114
 115 ### Day 6: Genetic Mutation
 116 * Category: pwn/misc
 117 * 101 solves / 142 points
 118 * Time spent: ~2 hours
 119 ```
 120 We just rescued an elf that was captured by The Grinch for his cruel genetic experiments. But we were late, the poor elf was already mutated. Could you help us restore the elf's genes?
 121
 122 Service: nc 3.93.128.89 1206
 123 ```
 124 Upon connecting to the server the hex-encoded version of a zlib compressed ELF was presented together with an option to change up to 4 bytes of the binary after which it was executed. The actual program started with a user input prompt asking for a name, then printed a greeting message containing that input and a song text.
 125
 126 Unzipping and disassembling the file revealed a very short program with basic input and output handling without any obvious flaws. There was a short character array that I considered might hold the flag and which I tried to leak by manipulating some ```mov``` instructions and having it printed instead of the user-provided name, but that attempt was not successfull. I attempted various iterations of getting the executable to print potential flag contents but to no avail.
 127 In the end @georg solved the challenge by not only manipulating the programs instructions but also flags, making the stack executable and changing the maximum length that is read to that shellcode to spawn a shell could be sent; the flag turned out to not be part of the binary but present as a text file that could then be read.
 128
 129 ### Day 7: Naught or Nice V2
 130 * Category: pwn/crypto
 131 * 29 solves / 389 points
 132 * Time spent: ~15 hours
 133 ```
 134 Last year, Santa made a network service to receive instructions for Christmas wishes. Unfortunately it had some security issues, which have now been fixed. Hopefully...
 135
 136 Service: nc 3.93.128.89 1207
 137 ```
 138 Connecting to the server again showed an input prompt, referencing [a challenge from the year before](https://github.com/nononovak/otwadvent2018-ctfwriteup/blob/master/day14.md):
 139 ```
 140 After last year's embarrassment, Santa decided to simplify how he authenticated letters.
 141  "What's the point of hashing the message first, if the message is short?
 142   We can just encrypt the message itself with the private key!
 143   It should be fine as long as we use a secure padding scheme like PKCS#1 1.5, right?"
 144 So, what would you like for Christmas?
 145 ```
 146 The provided binary showed that the user input was "encrypted" with a public key that it contained, the resulting "ciphertext" decoded according to PKCS#1 1.5 and the unpadded "message" executed as code. In short, a way to construct a payload that was correctly padded shellcode "signed" with an unknown private key was required.
 147
 148 The implementation deviated from what the padding scheme is intended to do in some fundamental ways, most obviously in that usually the padding operation takes place before encrypting or signing a plaintext and is only reversed once the mirroring operation of decrypting or verifying the signature had been done, not like the binary did after only one of those had ran. This suggested that the private key wasn't necessarily part of the solution: If it were available it would of course be easy to just transform the intended payload, but even without it reproducing the steps that lead to the code being executed was possible because of the single-way transformation. Variable naming and the block type 02 used in the padding check suggested that this was a public key operation but because no other key was ever used that didn't really make a difference in the way the program worked.
 149
 150 Another implementation shortcoming of the padding scheme turned out to be the missing length check: The unpadding operation correctly checked whether the message started with null byte (which meant that the input had to be exactly 127 of the possible 128 bytes long since it was expanded with nulls in the front if it was shorter, thus resulting in a incorrect padding) and the block type 02, followed by at least 8 bytes of padding and another null byte, all of which were discarded and the rest of the text treated as executable code. However there was never a check whether the padded message was of a valid length, i.e. whether it didn't contain any null bytes (which normaly should indicate the end of the message and increase the length of the padding accordingly) - as long as the total length was correct (meaning there was a non-null byte in the least significatn position) the padding check would pass.
 151 After unsuccessfully searching for possible attacks for a long time these implementation shortcomings at least hinted at the possibility of approximating a "plaintext" that when encrypted with the known public key would result in a "ciphertext" that passes both the padding check and contains the desired payload as a message: Because only some bytes - the two most significant ones whose values were explicitely checked as well as the desired shellcode preceded by a null byte - were relevant for successfull exploitation some deviation in the other bytes - the padding (which nedded to be of a certain minimum length but arbitrary value) and anything after the shellcode - doesn't matter as long as there were no null bytes in inconvenient places.
 152 Theoretically this would allow for taking a desired ciphertext and reversing the exponentiation to receive a possible plaintext through approximation that when encrypted wouldn't result in exactly the same ciphertext, but one close enough and with deviations in bytes that weren't relevant for exploitation; practically I didn't get it to work this way unfortunately. @georg however realized that the user input was also made executable by the program and could be used as a payload and successfully brute-forced a solution that contained the necessary shellcode as well as a random part and when encrypted passed the padding check and resulted in instructions that continued execution with the user-input.
 153
 154 ### Day 10: ChristmaSSE KeyGen (rev/math / 45 solves / 271 points)
 155 * Category: rev/math
 156 * 45 solves / 271 points
 157 * Time spent: ~20 hours
 158 ```
 159 I ran this program but it never finished... maybe my computer is too slow. Maybe yours is faster?
 160 ```
 161 The binary contains the flag in encoded form as well as a couple of starting values which after being transformed in a loop are used as an XOR-mask to decode the flag and print it; due to the large number of iterations (over one quintillion) it doesn't seem feasible to simply wait for it to finish.
 162
 163 Setting out to reverse what the program is doing I discovered that it uses vector instructions to process multiple bytes of the mask at the same time; not having been familiar with SSE it took me quite a while to look up and understand the various instructions and how they worked in detail, especially how they handled integer overflows. Most of them were simple vector versions of basic algebraic operations like addition and multiplication which used the 128 bit XMM-registers to process 4 doubleword-sized integers at the same time. Only the ```pshuffd```-instruction was a bit more complex, taking one value and shuffling the contained values according to a provided bit mask into another register; after spending a while trying to understand the pattern I resorted to dynamic analysis to get a better insight into what the shuffles were doing, and they turned out to be rather simple, copying the same doubleword-value into a 128 bit-register multiple times.
 164
 165 While the calculations seemed very complex at first due to using 15 different XMM-registers it turned out to be a lot less intimidating once it had been translated to pseudo-code, with most of the registers just being used as temporary stores for calculation results. The loop really only operated on four registers of which only two were relevant for the final XOR-operation, but all of which were necessary for correct result calculations.
 166
 167 The main loop ended up being pretty straight forward, but it cointained another inner loop at the end that was iterated 1000 times which threw me off for a long time due to misreading it and thinking it was more complex than it really was.
 168
 169 I considered that the challenge might either be solved by finding a point early on during the program run at which the values returned back to the original ones, meaning it could be terminated earlier by avoiding repeat runs of the same operations over and over again; or by finding a way to directly calculate the result in a mathematical way that didn't require repetition. Because the inner loop seemed too complex to be broken down into a simple mathematical rule I tried checking whether the former solution was possible, now understanding what happened during execution and what values needed to be present.
 170 Using r2 and its Python-bridge I wrote a script that checked the XMM-register values after each loop iteration and let it run for a while, but after letting it go on unattended for a couple of hours I determined that the solution probably wasn't to be found this way, especially considering the likelihood that every register would return to the startng value within the same iteration.
 171
 172 Luckily @georg and @chgue came to the rescue and had a look at the program and my pseudocode, realizing that I severly overcomplicated what the inner loop was doing, thinking it did different subtractions depending on whether the register contents exceeded a certain value or not, which would make it complicated to impossible to generalize and encode this rule in a formula. In reality it was a simple modulo-operation which of course was way easier to formalize. Here's the pseudocode of what we finally devised the binary did:
 173
 174 ``` python
 175 def pseudocode():
 176     # Static data store
 177     dqw_601040 = [1, 2, 3, 4]
 178     dqw_601050 = [5, 6, 7, 8]
 179     dqw_601060 = [9, 10, 11, 12]
 180     dqw_601070 = [13, 14, 15, 16]
 181     dqw_601080 = [1, 0, 0x96433d, 0]
 182
 183     # Doublewods in XMM-registers
 184     xmm3 = [1, 0, 0, 0]
 185     xmm2 = [0, 1, 0, 0]
 186     xmm1 = [0, 0, 1, 0]
 187     xmm0 = [0, 0, 0, 1]
 188
 189     # Initial flag data
 190     flag_pt1 = [0xfc, 0x14, 0xeb, 0x09, 0xbc, 0xae, 0xe7, 0x47, 0x4f, 0xe3, 0x7c, 0xc1, 0x52, 0xa5, 0x0, 0x8e]
 191     flag_pt2 = [0x89, 0x71, 0xc8, 0x8d, 0x96, 0x23, 0x01, 0x6d, 0x71, 0x40, 0x5a, 0xea, 0xfd, 0x46, 0x1d, 0x23]
 192
 193     outer_loop_iterations = 1234567890123456789
 194
 195     for o in range(0, outer_loop_iterations):
 196         xmm3_t = 4*xmm0 + 3*xmm1 + 2*xmm2 + 1*xmm3
 197         xmm2_t = 8*xmm0 + 7*xmm1 + 6*xmm2 + 5*xmm3
 198         xmm1_t = 0xc*xmm0 + 0xb*xmm1 + 0xa*xmm2 + 9*xmm3
 199         xmm0_t = 10*xmm0 + 0xf*xmm1 + 0xe*xmm2 + 0xd*xmm3
 200
 201         xmm4 = [0x96433d, 0x96433d, 0x96433d, 0x96433d]
 202         xmm5 = [1,1,1,1]
 203
 204         xmm3_t = xmm3_t % xmm4
 205         xmm2_t = xmm3_t % xmm4
 206         xmm1_t = xmm3_t % xmm4
 207         xmm0_t = xmm3_t % xmm4
 208
 209         xmm0 = xmm0_t
 210         xmm1 = xmm1_t
 211         xmm2 = xmm2_t
 212         xmm3 = xmm3_t
 213
 214     # For final XOR-operations treat data in XMM-registers as bytes, not doublewords
 215     flag_pt1 = flag_pt1 ^ xmm3
 216     flag_pt2 = flag_pt2 ^ xmm2
 217 ```
 218
 219 @chgue correctly identified that the starting values and operations could be expressed as matrices, and that the program basically came down to a matrix exponentiation, and after tinkering with it (and tripping over my copy-paste-errors which resulted in incorrect flag byte values) they successfully decoded the initial data using the following script (courtesy of @chgue):
 220
 221 ``` python
 222 import numpy as np
 223 import struct
 224 m = np.matrix("1 2 3 4; 5 6 7 8; 9 10 11 12; 13 14 15 16")
 225 exponent = 1234567890123456789
 226 prime = 0x96433d
 227 flag_pt1 = [0xfc, 0x14, 0xeb, 0x09, 0xbc, 0xae, 0xe7, 0x47, 0x4f, 0xe3, 0x7c, 0xc1, 0x52, 0xa5, 0x02, 0x8e]
 228 flag_pt2 = [0x89, 0x71, 0xc8, 0x8d, 0x96, 0x23, 0x01, 0x6d, 0x71, 0x40, 0x5a, 0xea, 0xfd, 0x46, 0x1d, 0x23]
 229 flag = flag_pt1 + flag_pt2
 230
 231 def mmulmod(a, b, c):
 232     return np.mod(np.matmul(a, b), c)
 233 def mexpm(a, b, c):
 234     if b == 0:
 235         return np.matrix("1 0 0 0; 0 1 0 0; 0 0 1 0; 0 0 0 1")
 236     if b % 2 == 1:
 237         return mmulmod(a, mexpm(a, b-1, c), c)
 238     d = mexpm(a, b//2, c)
 239     return mmulmod(d, d, c)
 240 pos = mexpm(m, exponent, prime).tolist()
 241 pos_added = [i for s in pos for i in s]
 242 key = [i for s in [list(struct.pack("<I", x)) for x in pos_added] for i in s]
 243 rax = 0
 244 while rax != 32:
 245     flag[rax] = key[rax*2] ^ flag[rax]
 246     flag[rax+1] = key[rax*2+1] ^ flag[rax+1]
 247     rax = rax + 2
 248 print("AOTW{" + "".join([chr(x) for x in flag]) + "}")
 249 ```
 250
 251 ### Day 15: Self-Replicating Toy (rev / 33 solves / 350 points)
 252 * Category: rev
 253 * 33 solves / 350 points
 254 * Time spent: ~4 hours
 255 ```
 256 Can you design your own self-replicating toy?
 257
 258 Service: nc 3.93.128.89 1214
 259 ```
 260 This challenge introduced "Assemblium", a basic stack-based programming language consisting of a couple of opcodes that allowed various data manipulation operations, with the goal of writing a program that when executed printed itself as a result (i.e. a quine). The various operations using stacks for data, code and output, were not explained in detail but could be gleaned from the provided C-program:
 261
 262 ```
 263 inst < 0x80: push inst to data stack
 264 inst == 0x80: push pop(data) ^ 0x80 to data stack
 265 inst == 0x81: pop(data), if 0 -> push 0xff, else: push 0
 266 inst == 0x82: pop 2 from data, push a & b
 267 inst == 0x83: pop 2 from data, push a | b
 268 inst == 0x84: pop 2 from data, push a ^ b
 269 inst == 0x90: pop 2 from data, push in reverse
 270 inst == 0x91: pop 1 from data, push twice
 271 inst == 0xa0: push 1 from data (index); pop values until 0xa1 from data and push them onto function[index] stack
 272 inst == 0xb0: pop 1 from data, push onto output
 273 inst >= 0xc0: and < 0xe0: index = inst - 0xc0; push values from function[index].data onto code stack in reverse
 274 inst >= 0xe0: index = inst - 0xe0; if data stack can be popped (and discarded!) push values from function[index].data onto code stack in reverse
 275 ```
 276
 277 Once again turning to PROLOG I encoded these operations in various logical rules, hoping to be able to find a solution through constraints. I first started by building a version that would backtrack from a program's output, checking whether it had a valid corresponding input sequence:
 278
 279 ``` prolog
 280 :- use_module(library(clpfd)).
 281
 282 valid_functions_length([], _).
 283 valid_functions_length([Function|Functions], MaxLength) :-
 284     Length #=< MaxLength,
 285     length(Function, Length),
 286     Function ins 0..255,
 287     valid_functions_length(Functions, MaxLength).
 288
 289 function_at_index(Function, [Function|_], 0).
 290 function_at_index(Function, [_|Functions], N) :-
 291     N #=< 20,
 292     NN #= N - 1,
 293     function_at_index(Function, Functions, NN).
 294
 295 :- function_at_index([1], [[1]], 0).
 296 :- function_at_index([1], [[],[1]], 1).
 297
 298 set_function_at_index(Function, 0, PreviousFunctions, [_|AfterFunctions], Result) :-
 299     %append(PreviousFunctions, Function, FFs),
 300     append(PreviousFunctions, [Function|AfterFunctions], Result).
 301 set_function_at_index(Function, N, PreviousFunctions, [F|AfterFunctions], Result) :-
 302     NN #= N - 1,
 303     append(PreviousFunctions, [F], NewPrevious),
 304     set_function_at_index(Function, NN, NewPrevious, AfterFunctions, Result).
 305
 306 :- set_function_at_index([1], 0, [], [[2]], [[1]]).
 307 :- set_function_at_index([2], 1, [], [[1], [1]], [[1],[2]]).
 308
 309 pop_data_until_a1([161|RemainingData], RemainingData, _).
 310 pop_data_until_a1([D|Remaining], OrigData, [D|PoppedData]) :-
 311     pop_data_until_a1(Remaining, OrigData, PoppedData).
 312
 313 :- pop_data_until_a1([161], [], _).
 314 :- pop_data_until_a1([161, 1], [1], _).
 315 :- pop_data_until_a1([1,161, 1], [1], [1]).
 316 :- pop_data_until_a1([1,2,161, 1], [1], [1,2]).
 317
 318 program_step([], [], Empty_Functions, []) :-
 319     Empty_Functions = [[], [], [], [], [], [], [], [], [], [],
 320                       [], [], [], [], [], [], [], [], [], [],
 321                       [], [], [], [], [], [], [], [], [], [],
 322                         [], []].
 323
 324 % Inst < 0x80: Push inst to data stack
 325 program_step([Inst|Instructions], [Inst|Data], Functions, Output) :-
 326     128 #> Inst,
 327     Inst #>= 0,
 328     length([Inst|Instructions], InputLength),
 329     valid_functions_length(Functions, InputLength),
 330     program_step(Instructions, Data, Functions, Output).
 331
 332 % inst == 0x80: push pop(data) ^ 0x80 to data stack
 333 program_step([128|Instructions], [XOR_T|Data], Functions, Output) :-
 334     T #=< 255,
 335     XOR_T #= xor(T, 128),
 336     length([128|Instructions], InputLength),
 337     valid_functions_length(Functions, InputLength),
 338     program_step(Instructions, [T|Data], Functions, Output).
 339
 340 % inst == 0x81: pop(data), if 0 -> push 0xff, else: push 0
 341 program_step([129|Instructions], [255|Data], Functions, Output) :-
 342     length([129|Instructions], InputLength),
 343     valid_functions_length(Functions, InputLength),
 344     program_step(Instructions, [0|Data], Functions, Output).
 345 program_step([129|Instructions], [0|Data], Functions, Output) :-
 346     length([129|Instructions], InputLength),
 347     valid_functions_length(Functions, InputLength),
 348     program_step(Instructions, [_|Data], Functions, Output).
 349
 350 % inst == 0x82: pop 2 from data, push a & b
 351 program_step([130|Instructions], [AND_T1_T2|Data], Functions, Output) :-
 352     T1 #=< 255,
 353     T2 #=< 255,
 354     AND_T1_T2 #= T1 /\ T2,
 355     length([130|Instructions], InputLength),
 356     valid_functions_length(Functions, InputLength),
 357     program_step(Instructions, [T1,T2|Data], Functions, Output).
 358
 359 % inst == 0x83: pop 2 from data, push a | b
 360 program_step([131|Instructions], [OR_T1_T2|Data], Functions, Output) :-
 361     T1 #=< 255,
 362     T2 #=< 255,
 363     OR_T1_T2 #= T1\/T2,
 364     length([131|Instructions], InputLength),
 365     valid_functions_length(Functions, InputLength),
 366     program_step(Instructions, [T1,T2|Data], Functions, Output).
 367
 368 % inst == 0x84: pop 2 from data, push a ^ b
 369 program_step([132|Instructions], [XOR_T1_T2|Data], Functions, Output) :-
 370     T1 #=< 255,
 371     T2 #=< 255,
 372     XOR_T1_T2 #= xor(T1, T2),
 373     length([132|Instructions], InputLength),
 374     valid_functions_length(Functions, InputLength),
 375     program_step(Instructions, [T1,T2|Data], Functions, Output).
 376
 377 % inst == 0x90: pop 2 from data, push in reverse
 378 program_step([144|Instructions], [T1,T2|Data], Functions, Output) :-
 379     T1 #=< 255,
 380     T2 #=< 255,
 381     length([144|Instructions], InputLength),
 382     valid_functions_length(Functions, InputLength),
 383     program_step(Instructions, [T2,T1|Data], Functions, Output).
 384
 385 % inst == 0x91: pop 1 from data, push twice
 386 program_step([145|Instructions], [T1,T1|Data], Functions, Output) :-
 387     T1 #=< 255,
 388     length([145|Instructions], InputLength),
 389     valid_functions_length(Functions, InputLength),
 390     program_step(Instructions, [T1|Data], Functions, Output).
 391
 392 % inst == 0xa0: pop(?) 1 from data (index);
 393 % pop values until 0xa1 encountered from data and push them onto function[index] stack
 394 program_step([160|Instructions], [Index|Data], Functions, Output) :-
 395     Index #< 32,
 396     length([160|Instructions], InputLength),
 397     valid_functions_length(Functions, InputLength),
 398     pop_data_until_a1(Data, RemainingData, PoppedData),
 399     set_function_at_index(PoppedData, Index, [], Functions, NewFunctions),
 400     % TODO
 401     program_step(Instructions, RemainingData, NewFunctions, Output).
 402
 403 % inst == 0xb0: pop 1 from data, push onto output
 404 program_step([176|Instructions], Data, Functions, [T1|Output]) :-
 405     T1 #=< 255,
 406     length([176|Instructions], InputLength),
 407     valid_functions_length(Functions, InputLength),
 408     program_step(Instructions, [T1|Data], Functions, Output).
 409
 410 % inst >= 0xc0: and < 0xe0: index = inst - 0xc0;
 411 % push values from function[index].data onto code stack in reverse
 412 program_step([Inst|Instructions], Data, Functions, Output) :-
 413     Inst #>= 192,
 414     Inst #=< 224,
 415     Index #= Inst - 192,
 416     length([Inst|Instructions], InputLength),
 417     valid_functions_length(Functions, InputLength),
 418     function_at_index(Function, Functions, Index),
 419     reverse(Function, ReversedFunction),
 420     append(ReversedFunction, Instructions, LinkedInstructions),
 421     program_step(LinkedInstructions, Data, Functions, Output).
 422
 423 % inst >= 0xe0: index = inst - 0xe0; if data stack can be popped (and discarded!)
 424 % push values from function[index].data onto code stack in reverse
 425 program_step([Inst|Instructions], [A|Data], Functions, Output) :-
 426     Inst #>= 224,
 427     Inst #=< 255,
 428     A #=< 255,
 429     Index #= Inst - 224,
 430     length([Inst|Instructions], InputLength),
 431     valid_functions_length(Functions, InputLength),
 432     function_at_index(Function, Functions, Index),
 433     reverse(Function, ReversedFunction),
 434     append(ReversedFunction, Instructions, LinkedInstructions),
 435     program_step(LinkedInstructions, Data, Functions, Output).
 436
 437 find_solution(Input) :-
 438     Max_Length #= 10,
 439     program_step(Input, Data, Functions, Input),
 440     length(Functions, 32),
 441     length(Input, Max_Length).
 442
 443 % Tests
 444 :- program_step([1], [1], [[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]], []).
 445 :- program_step([144, 2, 1], [1,2], [[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]], []).
 446 :- program_step([145, 1], [1,1], [[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]], []).
 447 :- program_step([176,1], [], [[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]], [1]).
 448 %:- program_step([193], [1], [], [[],[1],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]], []).
 449 :- program_step([1], [1], [[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]], []).
 450 ```
 451
 452 I tried the other way around as well, executing an Assemblium-program using logic rules and validating whether the output sequence matche the input:
 453
 454 ``` prolog
 455 :- use_module(library(clpfd)).
 456
 457 valid_opcode(Opcode) :-
 458     Opcode #>= 0,
 459     Opcode #< 256.
 460
 461 valid_function_index(Index) :-
 462     Index #>= 0,
 463     Index #< 32.
 464
 465 output_part_of_input(_, []).
 466 output_part_of_input([I1|Input], Output) :-
 467     reverse(Output, [O1|RevOutput]),
 468     I1 = O1,
 469     reverse(RevOutput, NextOutput),
 470     output_part_of_input(Input, NextOutput).
 471
 472 get_function(Index, [f-Index:Function|_], Function).
 473 get_function(Index, [_|Functions], Function) :-
 474     get_function(Index, Functions, Function).
 475
 476 set_function(Index, Function, PreviousFunctions, [f-Index:_ | RemainingFunctions], NewFunctions) :-
 477     append(PreviousFunctions, [f-Index:Function | RemainingFunctions], NewFunctions).
 478 set_function(Index, Function, PreviousFunctions, [], [f-Index:Function | PreviousFunctions]).
 479 set_function(Index, Function, PreviousFunctions, [F | RemainingFunctions], NewFunctions) :-
 480     append(PreviousFunctions, [F], NewPreviousFunctions),
 481     set_function(Index, Function, NewPreviousFunctions, RemainingFunctions, NewFunctions).
 482
 483 %pop_data_until(Data, Until, PoppedData)
 484 pop_data_until([Until|_], Until, []).
 485 pop_data_until([D|Data], Until, [D|PoppedData]) :-
 486     pop_data_until(Data, Until, PoppedData).
 487
 488 %pop_data_until_remaining(Data, Until, PoppedData, RemainingData)
 489 pop_data_until_remaining([Until|RemainingData], Until, [], RemainingData).
 490 pop_data_until_remaining([D|Data], Until, [D|PoppedData], RemainingData) :-
 491     pop_data_until_remaining(Data, Until, PoppedData, RemainingData).
 492
 493 % Base case: Valid program
 494 program_execute(Input, [], _Data, _Functions, Output) :-
 495     reverse(Input, Output).
 496 % Base case: Any result
 497 %program_execute(_, [], _, _, _).
 498 % Instructions < 0x80
 499 program_execute(Input, [Op|Code], Data, Functions, Output) :-
 500     Op #< 128,
 501     program_execute(Input, Code, [Op|Data], Functions, Output).
 502 % Instruction 0x80
 503 program_execute(Input, [128|Code], [D|Data], Functions, Output) :-
 504     XOR_D #= xor(128, D),
 505     program_execute(Input, Code, [XOR_D|Data], Functions, Output).
 506 % Instruction 0x81: Pop 1 value from Data; if 0 push 0xff, else push 0
 507 program_execute(Input, [129|Code], [0|Data], Functions, Output) :-
 508     program_execute(Input, Code, [255|Data], Functions, Output).
 509 program_execute(Input, [129|Code], [D|Data], Functions, Output) :-
 510     D #< 256,
 511     program_execute(Input, Code, [0|Data], Functions, Output).
 512 % Instruction 0x82: Pop 2 values from Data, push a & b
 513 program_execute(Input, [130|Code], [D1,D2|Data], Functions, Output) :-
 514     AND_D = D1 /\ D2,
 515     program_execute(Input, Code, [AND_D|Data], Functions, Output).
 516 % Instruction 0x83: Pop 2 values from Data, push a | b
 517 program_execute(Input, [131|Code], [D1,D2|Data], Functions, Output) :-
 518     OR_D = D1 \/ D2,
 519     program_execute(Input, Code, [OR_D|Data], Functions, Output).
 520 % Instruction 0x84: Pop 2 values from Data, push a ^ b
 521 program_execute(Input, [132|Code], [D1,D2|Data], Functions, Output) :-
 522     XOR_D = xor(D1,D2),
 523     program_execute(Input, Code, [XOR_D|Data], Functions, Output).
 524 % Instruction 0x90: Pop 2 values from Data, push them onto Data in reverse
 525 program_execute(Input, [144|Code], [D1,D2|Data], Functions, Output) :-
 526     program_execute(Input, Code, [D2,D1|Data], Functions, Output).
 527 % Instruction 0x91: Pop 2 values from Data, push them onto Data twice
 528 program_execute(Input, [145|Code], [D1|Data], Functions, Output) :-
 529     program_execute(Input, Code, [D1,D1|Data], Functions, Output).
 530 % Instruction 0xa0: Pop 1 value from Data, use it as index;
 531 %   Pop values from Data until 0xa1 is encountered, push everything except 0xa1 onto function[index] stack
 532 program_execute(Input, [160|Code], [Index|Data], Functions, Output) :-
 533     valid_function_index(Index),
 534     pop_data_until_remaining(Data, 161, PoppedData, RemainingData),
 535     set_function(Index, PoppedData, [], Functions, NewFunctions),
 536     program_execute(Input, Code, RemainingData, NewFunctions, Output).
 537 % Instruction 0xb0: Pop 1 value from Data, push it onto Output
 538 program_execute(Input, [176|Code], [D|Data], Functions, Output) :-
 539     program_execute(Input, Code, Data, Functions, [D|Output]).
 540 % Instruction >= 0xc0 and < 0xe0: Push values from function[Instruction - 0xc0] onto Code in reverse
 541 program_execute(Input, [Op|Code], Data, Functions, Output) :-
 542     valid_opcode(Op),
 543     Op #>= 192,
 544     Op #< 224,
 545     Index #= Op - 192,
 546     valid_function_index(Index),
 547     get_function(Index, Functions, FunctionAtIndex),
 548     reverse(FunctionAtIndex, FunctionAtIndexReversed),
 549     append(FunctionAtIndexReversed, Code, NewCode),
 550     program_execute(Input, NewCode, Data, Functions, Output).
 551 % Instruction >= 0xe0: Pop value from stack and discard, push values from function[Insruction - 0xe0] onto Code in reverse
 552 %   Otherwise return!
 553 program_execute(Input, [Op|Code], [], Functions, Output) :-
 554     valid_opcode(Op),
 555     Op #>= 224,
 556     Op #< 256,
 557     program_execute(Input, Code, [], Functions, Output).
 558 program_execute(Input, [Op|Code], [_|Data], Functions, Output) :-
 559     valid_opcode(Op),
 560     Op #>= 224,
 561     Op #< 256,
 562     Index #= Op - 224,
 563     valid_function_index(Index),
 564     get_function(Index, Functions, FunctionAtIndex),
 565     reverse(FunctionAtIndex, FunctionAtIndexReversed),
 566     append(FunctionAtIndexReversed, Code, NewCode),
 567     program_execute(Input, NewCode, Data, Functions, Output).
 568
 569
 570
 571 % Tests
 572 :- valid_opcode(0).
 573 :- valid_opcode(10).
 574 :- valid_opcode(255).
 575 %:-/ valid_opcode(256).
 576 %:-/valid_opcode(-1).
 577 :- valid_function_index(0).
 578 :- valid_function_index(1).
 579 :- valid_function_index(31).
 580 %:-/ valid_function_index(32).
 581 %:-/ valid_function_index(-1).
 582 :- pop_data_until([1], 1, []).
 583 :- pop_data_until([2,1], 1, [2]).
 584 :- output_part_of_input(_, []).
 585 :- output_part_of_input([_,_|_], []).
 586 :- output_part_of_input([1], [1]).
 587 :- output_part_of_input([1,2], [2,1]).
 588 :- output_part_of_input([1,2,3], [2,1]).
 589 :- set_function(0, [1,1,1], [], [f-0:[2,2]], [f-0:[1,1,1]]).
 590 ```
 591
 592 While both versions work and should be usable to verify legitimate solutions the search space of all possible inputs and outputs was obviously way too large to successfully find a valid one from scratch, realistically being able to only search through programs of at most around 6 instructions. While I tried to come up with further constraints to limit the search space I eventually ended up not pursuing this avenue any further, and @superwayne solved it using another approach.
 593
 594 ### Day 18: Impressive Sudoku (pwn/math / 33 solves / 350 points)
 595 * Category: pwn/math
 596 * 33 solves / 350 points
 597 * Time spent: ~4 hours
 598 ```
 599 First we asked you to solve a sudoku, now we want you to make one.
 600
 601 Service: nc 3.93.128.89 1218
 602 ```
 603 In contrast to the day 5-challenge this binary doesn't ask for the solution of a partially pre-filled sudoku but allows users to enter one themselves, scoring it by adding up the values on the diagonal from top-left to bottom-right, and printing the flag if that sum exceeds 1 million - which obviously isn't possible in a legitimate sudoku containg only values from 1 to 9.
 604
 605 The input handling doesn't seem vulnerable, simply reading nine lines of nine unsigned integers each, then running the ```check()```-function to test whether the sudoku is valid, exiting with an error if not; otherwise the ```score()```-function sums up the diagonal, calling the ```win()```-function which contains a system call to print the flag if it succeeds - and nothing else, which suggests that diverting program flow at some point to this function might be a possible attack vector.
 606
 607 Looking through the sourcecode there's a suspicious comment to be found in the function ```checkrow()```:
 608
 609 ```c
 610 bool checkrow(uint nums[9]) {
 611     uint sum = 0;
 612     uint prod = 1;
 613     for (int i = 0; i < 9; i++) {
 614         sum += nums[i];
 615         prod *= nums[i];
 616     }
 617     // Lazy way to check nums is a permutation of 1 - 9.
 618     return sum == 45 && prod == 362880;
 619 }
 620 ```
 621
 622 "Lazy way" sounds like a shortcut that might be exploitable. Instead of checking whether the provided array is a permutation of the numbers 1-9 it instead uses arithmetic which allows for other values to be present using integer overflows to wrap around the size limitation.
 623 Building upon the PROLOG-solution from day 5 and the documentation example used there allows for a quick way to find sudokus that pass this check instead of the usual permutation check:
 624
 625 ``` prolog
 626 :- use_module(library(clpfd)).
 627
 628 sudoku(Rows) :-
 629         length(Rows, 9),
 630         maplist(same_length(Rows), Rows),
 631         maplist(valid_sum(), Rows),
 632         maplist(valid_product(), Rows),
 633         transpose(Rows, Columns),
 634         maplist(valid_sum(), Columns),
 635         maplist(valid_product(), Columns),
 636         Rows = [As,Bs,Cs,Ds,Es,Fs,Gs,Hs,Is],
 637         blocks(As, Bs, Cs),
 638         blocks(Ds, Es, Fs),
 639         blocks(Gs, Hs, Is).
 640
 641 valid_sum(Row) :-
 642     Row = [N1,N2,N3,N4,N5,N6,N7,N8,N9],
 643     %sum_list(Row, Sum),
 644     N1 + N2 + N3 + N4 + N5 + N6 + N7 + N8 + N9 #= Sum,
 645     Max #= 8589934592,
 646     45 #= mod(Sum, Max).
 647
 648 valid_product(Row) :-
 649     Row = [N1,N2,N3,N4,N5,N6,N7,N8,N9],
 650     N1 * N2 * N3 * N4 * N5 * N6 * N7 * N8 * N9 #= Product,
 651     Max #= 8589934592,
 652     362880 #= mod(Product, Max) .
 653
 654 blocks([], [], []).
 655 blocks([N1,N2,N3|Ns1], [N4,N5,N6|Ns2], [N7,N8,N9|Ns3]) :-
 656         Blocklist = [N1,N2,N3,N4,N5,N6,N7,N8,N9],
 657         valid_sum(Blocklist),
 658         valid_product(Blocklist),
 659         blocks(Ns1, Ns2, Ns3).
 660 ```
 661
 662 Of course being able to pass a sudoku with arbitrary values isn't enough, there needs to be a way to do something useful with those numbers. Considering we've found a way to pass the ```check()```-function there's probably another vulnerability somewhere down the line, such as in the ```score()```-function:
 663
 664 ```c
 665 void score() {
 666     puts("Let me take a look...");
 667     for (int i = 0; i < 8; i++) {
 668         scorer[sudoku[i][i]] = sudoku[i + 1][i + 1];
 669     }
 670     uint score = 1;
 671     for (int i = 1; i <= 9; i++) {
 672         score *= scorer[i];
 673     }
 674     if (score >= 1000000) {
 675         win();
 676     } else {
 677         puts("That is an unimpressive sudoku.");
 678         exit(0);
 679     }
 680 }
 681 ```
 682
 683 This function first copies the diagonal values from the sudoku to global variable ```scorer``` and then loops over them to multiply them. Looking at both for-loops there's a discrepancy between the loop conditions: They start with different indices and use different conditions. As it turns out, the copy-loop copies at most 8 values, but the multiplication-loop reads and multiplies 9 - and since the ```scorer```-array is a global variable and initialized to 0, this multiplication not only cannot return a score high enough when presented with a proper classical sudoku but can't even calculate a "correct" score in any case.
 684 The more important flaw however lies in the way values are copied from the sudoku: Instead of using the loop variable as an index to write to it instead uses the value in that diagonal position as an array index - which means that coupled with the knowledge that values bigger than 9 can be written due to the flawed ```check()```-function arbitrary memory writes are possible. The binary has PIE enabled which should make finding targets easy and only has partial RELRO enabled, suggesting that GOT-overwrites could be a solution.
 685
 686 To avoid having to deal with generating sudokus that pass the check while searching for a working payload I created a patched version of the binary that simply continued execution as long as the ```check()```-function didn't pass and explored some options, aiming to overwrite the (known, fixed) address of the ```win()```-function into the GOT.
 687 One problem remaining was that due to Partial RELRO the GOT was placed before the scorer-array in memory, and since the arbitrary write relied on using an index to this array and the sudoku contents are read as unsigned integers there was no direct way to reach the GOT for a write. I considered overflowing the 32bit address space to have the index wrap around and address memory before the array but couldn't get it to work while debugging in r2 - but as it turns out, this would have been the intended solution and probably would have worked had I tried to execute the program without the debugger attached which I used to check whether the write ended up at the intended location. Having unsuccessfully blown past this solution I experimented with some other possible writes but didn't find a way to have the ```scorer()```-function pass until after the CTF ended.
 688
 689 ### Day 20: Strike a pose (fun / 31 solves / 368 points)
 690 * Category: fun
 691 * 31 solves / 368 points
 692 * Time spent: ~30 minutes
 693 ```
 694 Time to show off those ugly xmas sweaters!
 695
 696 Service: https://github.com/OverTheWireOrg/advent2019-strikeapose
 697 ```
 698 This non-technical challenge asked for a recreation of a famous photograph or poster with an ugly christmas sweater present. @cluosh suggested recreating The Godfather, and after looking at some options I found one common picture that featured Vito's cat; luckily I happened to have both a cat and an ugly christmas sweater lying around, and the pitch-black background in the Godfather posters made it rather easy to recreate the picture without caring about where it was taken. Some quick retouching and adding The Boss, et voila, I finally successfully solved a challenge of OTW Advent Bonanza 2019.