From 1506f7993e0c0e1c7000247c4e46fdd881f725e7 Mon Sep 17 00:00:00 2001 From: Hannes Hauer Date: Sun, 19 Jan 2020 17:16:08 +0100 Subject: [PATCH] Add OTW Advent Bonanza write-up, update older writeups with additional information --- writeups/hah/asis2019.md | 19 +- writeups/hah/otw-advent-2019.md | 698 ++++++++++++++++++++++++++++++++ writeups/hah/seccon19.md | 11 + 3 files changed, 722 insertions(+), 6 deletions(-) create mode 100644 writeups/hah/otw-advent-2019.md diff --git a/writeups/hah/asis2019.md b/writeups/hah/asis2019.md index 0bdb325..474a1be 100644 --- a/writeups/hah/asis2019.md +++ b/writeups/hah/asis2019.md @@ -1,9 +1,13 @@ -# Retrospective +# ASIS CTF Finals 2019 +## Retrospective 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. 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. -# Challenges -## Cursed app (Reverse / 90pts / 60 solves) +## Challenges +### Cursed app +* Category: Reverse +* 60 solves / 90 points +* Time spent: ~4 hours ``` If we want to say 100, should we start at 1 and count until 100? @@ -116,7 +120,10 @@ for i in range(len(calculations)): print("Found character for index {}: {}".format(i, c)) ``` -## Yet funny (Misc/Reverse / 154pts / 29 solves) +### Yet funny (Misc/Reverse / 154pts / 29 solves) +* Category: Misc/Reverse +* 29 solves / 154 points +* Time spent: ~7 hours ``` Sometimes you come up with something incredibly stupid yet funny. Don`t ignore it! @@ -126,11 +133,11 @@ nc 76.74.177.238 7777 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. -### Proof of work +#### Proof of work 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. 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. -### Randomized C++-program +#### Randomized C++-program 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. ```c++ diff --git a/writeups/hah/otw-advent-2019.md b/writeups/hah/otw-advent-2019.md new file mode 100644 index 0000000..8fa9b91 --- /dev/null +++ b/writeups/hah/otw-advent-2019.md @@ -0,0 +1,698 @@ +# OverTheWire Advent Bonanza 2019 +## Retrospective +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. +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. + +## Challenges +### Day 5: Sudo Sudoku +* Category: misc/sudoku +* 231 solves / 85 points +* Time spent: ~30 minutes +``` +Santa's little helpers are notoriously good at solving Sudoku puzzles, so they made a special variant... +``` + +A downloadable text file contained a partial sudoku with some additional constraints that when solved revealed the flag: +``` +Santa's little helpers are notoriously good at solving Sudoku puzzles. +Because regular Sudoku puzzles are too trivial, they have invented a variant. + + 1 2 3 4 5 6 7 8 9 + +-------+-------+-------+ +A | . . . | . . . | . . 1 | +B | . 1 2 | . . . | . . . | +C | . . . | . . . | 2 . . | + +-------+-------+-------+ +D | . . . | . . . | . . 2 | +E | . 2 . | . . . | . . . | +F | . . . | . . . | . . . | + +-------+-------+-------+ +G | . . . | . . . | 1 2 . | +H | 1 . . | . . 2 | . . . | +I | . . . | 1 . . | . . . | + +-------+-------+-------+ + +In addition to the standard Sudoku puzzle above, +the following equations must also hold: + +B9 + B8 + C1 + H4 + H4 = 23 +A5 + D7 + I5 + G8 + B3 + A5 = 19 +I2 + I3 + F2 + E9 = 15 +I7 + H8 + C2 + D9 = 26 +I6 + A5 + I3 + B8 + C3 = 20 +I7 + D9 + B6 + A8 + A3 + C4 = 27 +C7 + H9 + I7 + B2 + H8 + G3 = 31 +D3 + I8 + A4 + I6 = 27 +F5 + B8 + F8 + I7 + F1 = 33 +A2 + A8 + D7 + E4 = 21 +C1 + I4 + C2 + I1 + A4 = 20 +F8 + C1 + F6 + D3 + B6 = 25 + +If you then read the numbers clockwise starting from A1 to A9, to I9, to I1 and +back to A1, you end up with a number with 32 digits. Enclose that in AOTW{...} +to get the flag. +``` + +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: + +```prolog +day5(Rows) :- + sudoku(Rows), + Rows = [A, B, C, D, E, F, G, H, I], + A = [_,A2,A3, _,A5,_, _,_,1], + B = [_,B2,B3, _,_,B6, _,_,B9], + C = [_,_,C3, C4,_,_, C7,_,_], + D = [_,_,_, _,_,_, _,_,2], + E = [_,2,_, E4,_,_, _,_,E9], + F = [F1,F2,_, _,F5,F6, _,_,_], + G = [_,_,G3, _,_,_, 1,G8,_], + H = [1,_,_, _,_,2, _,_,H9], + I = [I1,I2,_, I4,I5,_, _,I8,_], + G8 #= 2, + B3 #= 2, + B2 #= 1, + C7 #= 2, + I4 #= 1, + B9 + B8 + C1 + H4 + H4 #= 23, + A5 + D7 + I5 + G8 + B3 + A5 #= 19, + I2 + I3 + F2 + E9 #= 15, + I7 + H8 + C2 + D9 #= 26, + I6 + A5 + I3 + B8 + C3 #= 20, + I7 + D9 + B6 + A8 + A3 + C4 #= 27, + C7 + H9 + I7 + B2 + H8 + G3 #= 31, + D3 + I8 + A4 + I6 #= 27, + F5 + B8 + F8 + I7 + F1 #= 33, + A2 + A8 + D7 + E4 #= 21, + C1 + I4 + C2 + I1 + A4 #= 20, + F8 + C1 + F6 + D3 + B6 #= 25, + labeling([], A), + labeling([], B), + labeling([], C), + labeling([], D), + labeling([], E), + labeling([], F), + labeling([], G), + labeling([], H), + labeling([], I). + +sudoku(Rows) :- + length(Rows, 9), maplist(same_length(Rows), Rows), + append(Rows, Vs), Vs ins 1..9, + maplist(all_distinct, Rows), + transpose(Rows, Columns), + maplist(all_distinct, Columns), + Rows = [A,B,C,D,E,F,G,H,I], + blocks(A, B, C), blocks(D, E, F), blocks(G, H, I). + +blocks([], [], []). +blocks([A,B,C|Bs1], [D,E,F|Bs2], [G,H,I|Bs3]) :- + all_distinct([A,B,C,D,E,F,G,H,I]), + blocks(Bs1, Bs2, Bs3). +``` + +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. + +### Day 6: Genetic Mutation +* Category: pwn/misc +* 101 solves / 142 points +* Time spent: ~2 hours +``` +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? + +Service: nc 3.93.128.89 1206 +``` +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. + +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. +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. + +### Day 7: Naught or Nice V2 +* Category: pwn/crypto +* 29 solves / 389 points +* Time spent: ~15 hours +``` +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... + +Service: nc 3.93.128.89 1207 +``` +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): +``` +After last year's embarrassment, Santa decided to simplify how he authenticated letters. + "What's the point of hashing the message first, if the message is short? + We can just encrypt the message itself with the private key! + It should be fine as long as we use a secure padding scheme like PKCS#1 1.5, right?" +So, what would you like for Christmas? +``` +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. + +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. + +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. +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. +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. + +### Day 10: ChristmaSSE KeyGen (rev/math / 45 solves / 271 points) +* Category: rev/math +* 45 solves / 271 points +* Time spent: ~20 hours +``` +I ran this program but it never finished... maybe my computer is too slow. Maybe yours is faster? +``` +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. + +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. + +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. + +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. + +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. +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. + +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: + +``` python +def pseudocode(): + # Static data store + dqw_601040 = [1, 2, 3, 4] + dqw_601050 = [5, 6, 7, 8] + dqw_601060 = [9, 10, 11, 12] + dqw_601070 = [13, 14, 15, 16] + dqw_601080 = [1, 0, 0x96433d, 0] + + # Doublewods in XMM-registers + xmm3 = [1, 0, 0, 0] + xmm2 = [0, 1, 0, 0] + xmm1 = [0, 0, 1, 0] + xmm0 = [0, 0, 0, 1] + + # Initial flag data + flag_pt1 = [0xfc, 0x14, 0xeb, 0x09, 0xbc, 0xae, 0xe7, 0x47, 0x4f, 0xe3, 0x7c, 0xc1, 0x52, 0xa5, 0x0, 0x8e] + flag_pt2 = [0x89, 0x71, 0xc8, 0x8d, 0x96, 0x23, 0x01, 0x6d, 0x71, 0x40, 0x5a, 0xea, 0xfd, 0x46, 0x1d, 0x23] + + outer_loop_iterations = 1234567890123456789 + + for o in range(0, outer_loop_iterations): + xmm3_t = 4*xmm0 + 3*xmm1 + 2*xmm2 + 1*xmm3 + xmm2_t = 8*xmm0 + 7*xmm1 + 6*xmm2 + 5*xmm3 + xmm1_t = 0xc*xmm0 + 0xb*xmm1 + 0xa*xmm2 + 9*xmm3 + xmm0_t = 10*xmm0 + 0xf*xmm1 + 0xe*xmm2 + 0xd*xmm3 + + xmm4 = [0x96433d, 0x96433d, 0x96433d, 0x96433d] + xmm5 = [1,1,1,1] + + xmm3_t = xmm3_t % xmm4 + xmm2_t = xmm3_t % xmm4 + xmm1_t = xmm3_t % xmm4 + xmm0_t = xmm3_t % xmm4 + + xmm0 = xmm0_t + xmm1 = xmm1_t + xmm2 = xmm2_t + xmm3 = xmm3_t + + # For final XOR-operations treat data in XMM-registers as bytes, not doublewords + flag_pt1 = flag_pt1 ^ xmm3 + flag_pt2 = flag_pt2 ^ xmm2 +``` + +@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): + +``` python +import numpy as np +import struct +m = np.matrix("1 2 3 4; 5 6 7 8; 9 10 11 12; 13 14 15 16") +exponent = 1234567890123456789 +prime = 0x96433d +flag_pt1 = [0xfc, 0x14, 0xeb, 0x09, 0xbc, 0xae, 0xe7, 0x47, 0x4f, 0xe3, 0x7c, 0xc1, 0x52, 0xa5, 0x02, 0x8e] +flag_pt2 = [0x89, 0x71, 0xc8, 0x8d, 0x96, 0x23, 0x01, 0x6d, 0x71, 0x40, 0x5a, 0xea, 0xfd, 0x46, 0x1d, 0x23] +flag = flag_pt1 + flag_pt2 + +def mmulmod(a, b, c): + return np.mod(np.matmul(a, b), c) +def mexpm(a, b, c): + if b == 0: + return np.matrix("1 0 0 0; 0 1 0 0; 0 0 1 0; 0 0 0 1") + if b % 2 == 1: + return mmulmod(a, mexpm(a, b-1, c), c) + d = mexpm(a, b//2, c) + return mmulmod(d, d, c) +pos = mexpm(m, exponent, prime).tolist() +pos_added = [i for s in pos for i in s] +key = [i for s in [list(struct.pack(" push 0xff, else: push 0 +inst == 0x82: pop 2 from data, push a & b +inst == 0x83: pop 2 from data, push a | b +inst == 0x84: pop 2 from data, push a ^ b +inst == 0x90: pop 2 from data, push in reverse +inst == 0x91: pop 1 from data, push twice +inst == 0xa0: push 1 from data (index); pop values until 0xa1 from data and push them onto function[index] stack +inst == 0xb0: pop 1 from data, push onto output +inst >= 0xc0: and < 0xe0: index = inst - 0xc0; push values from function[index].data onto code stack in reverse +inst >= 0xe0: index = inst - 0xe0; if data stack can be popped (and discarded!) push values from function[index].data onto code stack in reverse +``` + +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: + +``` prolog +:- use_module(library(clpfd)). + +valid_functions_length([], _). +valid_functions_length([Function|Functions], MaxLength) :- + Length #=< MaxLength, + length(Function, Length), + Function ins 0..255, + valid_functions_length(Functions, MaxLength). + +function_at_index(Function, [Function|_], 0). +function_at_index(Function, [_|Functions], N) :- + N #=< 20, + NN #= N - 1, + function_at_index(Function, Functions, NN). + +:- function_at_index([1], [[1]], 0). +:- function_at_index([1], [[],[1]], 1). + +set_function_at_index(Function, 0, PreviousFunctions, [_|AfterFunctions], Result) :- + %append(PreviousFunctions, Function, FFs), + append(PreviousFunctions, [Function|AfterFunctions], Result). +set_function_at_index(Function, N, PreviousFunctions, [F|AfterFunctions], Result) :- + NN #= N - 1, + append(PreviousFunctions, [F], NewPrevious), + set_function_at_index(Function, NN, NewPrevious, AfterFunctions, Result). + +:- set_function_at_index([1], 0, [], [[2]], [[1]]). +:- set_function_at_index([2], 1, [], [[1], [1]], [[1],[2]]). + +pop_data_until_a1([161|RemainingData], RemainingData, _). +pop_data_until_a1([D|Remaining], OrigData, [D|PoppedData]) :- + pop_data_until_a1(Remaining, OrigData, PoppedData). + +:- pop_data_until_a1([161], [], _). +:- pop_data_until_a1([161, 1], [1], _). +:- pop_data_until_a1([1,161, 1], [1], [1]). +:- pop_data_until_a1([1,2,161, 1], [1], [1,2]). + +program_step([], [], Empty_Functions, []) :- + Empty_Functions = [[], [], [], [], [], [], [], [], [], [], + [], [], [], [], [], [], [], [], [], [], + [], [], [], [], [], [], [], [], [], [], + [], []]. + +% Inst < 0x80: Push inst to data stack +program_step([Inst|Instructions], [Inst|Data], Functions, Output) :- + 128 #> Inst, + Inst #>= 0, + length([Inst|Instructions], InputLength), + valid_functions_length(Functions, InputLength), + program_step(Instructions, Data, Functions, Output). + +% inst == 0x80: push pop(data) ^ 0x80 to data stack +program_step([128|Instructions], [XOR_T|Data], Functions, Output) :- + T #=< 255, + XOR_T #= xor(T, 128), + length([128|Instructions], InputLength), + valid_functions_length(Functions, InputLength), + program_step(Instructions, [T|Data], Functions, Output). + +% inst == 0x81: pop(data), if 0 -> push 0xff, else: push 0 +program_step([129|Instructions], [255|Data], Functions, Output) :- + length([129|Instructions], InputLength), + valid_functions_length(Functions, InputLength), + program_step(Instructions, [0|Data], Functions, Output). +program_step([129|Instructions], [0|Data], Functions, Output) :- + length([129|Instructions], InputLength), + valid_functions_length(Functions, InputLength), + program_step(Instructions, [_|Data], Functions, Output). + +% inst == 0x82: pop 2 from data, push a & b +program_step([130|Instructions], [AND_T1_T2|Data], Functions, Output) :- + T1 #=< 255, + T2 #=< 255, + AND_T1_T2 #= T1 /\ T2, + length([130|Instructions], InputLength), + valid_functions_length(Functions, InputLength), + program_step(Instructions, [T1,T2|Data], Functions, Output). + +% inst == 0x83: pop 2 from data, push a | b +program_step([131|Instructions], [OR_T1_T2|Data], Functions, Output) :- + T1 #=< 255, + T2 #=< 255, + OR_T1_T2 #= T1\/T2, + length([131|Instructions], InputLength), + valid_functions_length(Functions, InputLength), + program_step(Instructions, [T1,T2|Data], Functions, Output). + +% inst == 0x84: pop 2 from data, push a ^ b +program_step([132|Instructions], [XOR_T1_T2|Data], Functions, Output) :- + T1 #=< 255, + T2 #=< 255, + XOR_T1_T2 #= xor(T1, T2), + length([132|Instructions], InputLength), + valid_functions_length(Functions, InputLength), + program_step(Instructions, [T1,T2|Data], Functions, Output). + +% inst == 0x90: pop 2 from data, push in reverse +program_step([144|Instructions], [T1,T2|Data], Functions, Output) :- + T1 #=< 255, + T2 #=< 255, + length([144|Instructions], InputLength), + valid_functions_length(Functions, InputLength), + program_step(Instructions, [T2,T1|Data], Functions, Output). + +% inst == 0x91: pop 1 from data, push twice +program_step([145|Instructions], [T1,T1|Data], Functions, Output) :- + T1 #=< 255, + length([145|Instructions], InputLength), + valid_functions_length(Functions, InputLength), + program_step(Instructions, [T1|Data], Functions, Output). + +% inst == 0xa0: pop(?) 1 from data (index); +% pop values until 0xa1 encountered from data and push them onto function[index] stack +program_step([160|Instructions], [Index|Data], Functions, Output) :- + Index #< 32, + length([160|Instructions], InputLength), + valid_functions_length(Functions, InputLength), + pop_data_until_a1(Data, RemainingData, PoppedData), + set_function_at_index(PoppedData, Index, [], Functions, NewFunctions), + % TODO + program_step(Instructions, RemainingData, NewFunctions, Output). + +% inst == 0xb0: pop 1 from data, push onto output +program_step([176|Instructions], Data, Functions, [T1|Output]) :- + T1 #=< 255, + length([176|Instructions], InputLength), + valid_functions_length(Functions, InputLength), + program_step(Instructions, [T1|Data], Functions, Output). + +% inst >= 0xc0: and < 0xe0: index = inst - 0xc0; +% push values from function[index].data onto code stack in reverse +program_step([Inst|Instructions], Data, Functions, Output) :- + Inst #>= 192, + Inst #=< 224, + Index #= Inst - 192, + length([Inst|Instructions], InputLength), + valid_functions_length(Functions, InputLength), + function_at_index(Function, Functions, Index), + reverse(Function, ReversedFunction), + append(ReversedFunction, Instructions, LinkedInstructions), + program_step(LinkedInstructions, Data, Functions, Output). + +% inst >= 0xe0: index = inst - 0xe0; if data stack can be popped (and discarded!) +% push values from function[index].data onto code stack in reverse +program_step([Inst|Instructions], [A|Data], Functions, Output) :- + Inst #>= 224, + Inst #=< 255, + A #=< 255, + Index #= Inst - 224, + length([Inst|Instructions], InputLength), + valid_functions_length(Functions, InputLength), + function_at_index(Function, Functions, Index), + reverse(Function, ReversedFunction), + append(ReversedFunction, Instructions, LinkedInstructions), + program_step(LinkedInstructions, Data, Functions, Output). + +find_solution(Input) :- + Max_Length #= 10, + program_step(Input, Data, Functions, Input), + length(Functions, 32), + length(Input, Max_Length). + +% Tests +:- program_step([1], [1], [[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]], []). +:- program_step([144, 2, 1], [1,2], [[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]], []). +:- program_step([145, 1], [1,1], [[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]], []). +:- program_step([176,1], [], [[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]], [1]). +%:- program_step([193], [1], [], [[],[1],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]], []). +:- program_step([1], [1], [[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]], []). +``` + +I tried the other way around as well, executing an Assemblium-program using logic rules and validating whether the output sequence matche the input: + +``` prolog +:- use_module(library(clpfd)). + +valid_opcode(Opcode) :- + Opcode #>= 0, + Opcode #< 256. + +valid_function_index(Index) :- + Index #>= 0, + Index #< 32. + +output_part_of_input(_, []). +output_part_of_input([I1|Input], Output) :- + reverse(Output, [O1|RevOutput]), + I1 = O1, + reverse(RevOutput, NextOutput), + output_part_of_input(Input, NextOutput). + +get_function(Index, [f-Index:Function|_], Function). +get_function(Index, [_|Functions], Function) :- + get_function(Index, Functions, Function). + +set_function(Index, Function, PreviousFunctions, [f-Index:_ | RemainingFunctions], NewFunctions) :- + append(PreviousFunctions, [f-Index:Function | RemainingFunctions], NewFunctions). +set_function(Index, Function, PreviousFunctions, [], [f-Index:Function | PreviousFunctions]). +set_function(Index, Function, PreviousFunctions, [F | RemainingFunctions], NewFunctions) :- + append(PreviousFunctions, [F], NewPreviousFunctions), + set_function(Index, Function, NewPreviousFunctions, RemainingFunctions, NewFunctions). + +%pop_data_until(Data, Until, PoppedData) +pop_data_until([Until|_], Until, []). +pop_data_until([D|Data], Until, [D|PoppedData]) :- + pop_data_until(Data, Until, PoppedData). + +%pop_data_until_remaining(Data, Until, PoppedData, RemainingData) +pop_data_until_remaining([Until|RemainingData], Until, [], RemainingData). +pop_data_until_remaining([D|Data], Until, [D|PoppedData], RemainingData) :- + pop_data_until_remaining(Data, Until, PoppedData, RemainingData). + +% Base case: Valid program +program_execute(Input, [], _Data, _Functions, Output) :- + reverse(Input, Output). +% Base case: Any result +%program_execute(_, [], _, _, _). +% Instructions < 0x80 +program_execute(Input, [Op|Code], Data, Functions, Output) :- + Op #< 128, + program_execute(Input, Code, [Op|Data], Functions, Output). +% Instruction 0x80 +program_execute(Input, [128|Code], [D|Data], Functions, Output) :- + XOR_D #= xor(128, D), + program_execute(Input, Code, [XOR_D|Data], Functions, Output). +% Instruction 0x81: Pop 1 value from Data; if 0 push 0xff, else push 0 +program_execute(Input, [129|Code], [0|Data], Functions, Output) :- + program_execute(Input, Code, [255|Data], Functions, Output). +program_execute(Input, [129|Code], [D|Data], Functions, Output) :- + D #< 256, + program_execute(Input, Code, [0|Data], Functions, Output). +% Instruction 0x82: Pop 2 values from Data, push a & b +program_execute(Input, [130|Code], [D1,D2|Data], Functions, Output) :- + AND_D = D1 /\ D2, + program_execute(Input, Code, [AND_D|Data], Functions, Output). +% Instruction 0x83: Pop 2 values from Data, push a | b +program_execute(Input, [131|Code], [D1,D2|Data], Functions, Output) :- + OR_D = D1 \/ D2, + program_execute(Input, Code, [OR_D|Data], Functions, Output). +% Instruction 0x84: Pop 2 values from Data, push a ^ b +program_execute(Input, [132|Code], [D1,D2|Data], Functions, Output) :- + XOR_D = xor(D1,D2), + program_execute(Input, Code, [XOR_D|Data], Functions, Output). +% Instruction 0x90: Pop 2 values from Data, push them onto Data in reverse +program_execute(Input, [144|Code], [D1,D2|Data], Functions, Output) :- + program_execute(Input, Code, [D2,D1|Data], Functions, Output). +% Instruction 0x91: Pop 2 values from Data, push them onto Data twice +program_execute(Input, [145|Code], [D1|Data], Functions, Output) :- + program_execute(Input, Code, [D1,D1|Data], Functions, Output). +% Instruction 0xa0: Pop 1 value from Data, use it as index; +% Pop values from Data until 0xa1 is encountered, push everything except 0xa1 onto function[index] stack +program_execute(Input, [160|Code], [Index|Data], Functions, Output) :- + valid_function_index(Index), + pop_data_until_remaining(Data, 161, PoppedData, RemainingData), + set_function(Index, PoppedData, [], Functions, NewFunctions), + program_execute(Input, Code, RemainingData, NewFunctions, Output). +% Instruction 0xb0: Pop 1 value from Data, push it onto Output +program_execute(Input, [176|Code], [D|Data], Functions, Output) :- + program_execute(Input, Code, Data, Functions, [D|Output]). +% Instruction >= 0xc0 and < 0xe0: Push values from function[Instruction - 0xc0] onto Code in reverse +program_execute(Input, [Op|Code], Data, Functions, Output) :- + valid_opcode(Op), + Op #>= 192, + Op #< 224, + Index #= Op - 192, + valid_function_index(Index), + get_function(Index, Functions, FunctionAtIndex), + reverse(FunctionAtIndex, FunctionAtIndexReversed), + append(FunctionAtIndexReversed, Code, NewCode), + program_execute(Input, NewCode, Data, Functions, Output). +% Instruction >= 0xe0: Pop value from stack and discard, push values from function[Insruction - 0xe0] onto Code in reverse +% Otherwise return! +program_execute(Input, [Op|Code], [], Functions, Output) :- + valid_opcode(Op), + Op #>= 224, + Op #< 256, + program_execute(Input, Code, [], Functions, Output). +program_execute(Input, [Op|Code], [_|Data], Functions, Output) :- + valid_opcode(Op), + Op #>= 224, + Op #< 256, + Index #= Op - 224, + valid_function_index(Index), + get_function(Index, Functions, FunctionAtIndex), + reverse(FunctionAtIndex, FunctionAtIndexReversed), + append(FunctionAtIndexReversed, Code, NewCode), + program_execute(Input, NewCode, Data, Functions, Output). + + + +% Tests +:- valid_opcode(0). +:- valid_opcode(10). +:- valid_opcode(255). +%:-/ valid_opcode(256). +%:-/valid_opcode(-1). +:- valid_function_index(0). +:- valid_function_index(1). +:- valid_function_index(31). +%:-/ valid_function_index(32). +%:-/ valid_function_index(-1). +:- pop_data_until([1], 1, []). +:- pop_data_until([2,1], 1, [2]). +:- output_part_of_input(_, []). +:- output_part_of_input([_,_|_], []). +:- output_part_of_input([1], [1]). +:- output_part_of_input([1,2], [2,1]). +:- output_part_of_input([1,2,3], [2,1]). +:- set_function(0, [1,1,1], [], [f-0:[2,2]], [f-0:[1,1,1]]). +``` + +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. + +### Day 18: Impressive Sudoku (pwn/math / 33 solves / 350 points) +* Category: pwn/math +* 33 solves / 350 points +* Time spent: ~4 hours +``` +First we asked you to solve a sudoku, now we want you to make one. + +Service: nc 3.93.128.89 1218 +``` +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. + +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. + +Looking through the sourcecode there's a suspicious comment to be found in the function ```checkrow()```: + +```c +bool checkrow(uint nums[9]) { + uint sum = 0; + uint prod = 1; + for (int i = 0; i < 9; i++) { + sum += nums[i]; + prod *= nums[i]; + } + // Lazy way to check nums is a permutation of 1 - 9. + return sum == 45 && prod == 362880; +} +``` + +"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. +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: + +``` prolog +:- use_module(library(clpfd)). + +sudoku(Rows) :- + length(Rows, 9), + maplist(same_length(Rows), Rows), + maplist(valid_sum(), Rows), + maplist(valid_product(), Rows), + transpose(Rows, Columns), + maplist(valid_sum(), Columns), + maplist(valid_product(), Columns), + Rows = [As,Bs,Cs,Ds,Es,Fs,Gs,Hs,Is], + blocks(As, Bs, Cs), + blocks(Ds, Es, Fs), + blocks(Gs, Hs, Is). + +valid_sum(Row) :- + Row = [N1,N2,N3,N4,N5,N6,N7,N8,N9], + %sum_list(Row, Sum), + N1 + N2 + N3 + N4 + N5 + N6 + N7 + N8 + N9 #= Sum, + Max #= 8589934592, + 45 #= mod(Sum, Max). + +valid_product(Row) :- + Row = [N1,N2,N3,N4,N5,N6,N7,N8,N9], + N1 * N2 * N3 * N4 * N5 * N6 * N7 * N8 * N9 #= Product, + Max #= 8589934592, + 362880 #= mod(Product, Max) . + +blocks([], [], []). +blocks([N1,N2,N3|Ns1], [N4,N5,N6|Ns2], [N7,N8,N9|Ns3]) :- + Blocklist = [N1,N2,N3,N4,N5,N6,N7,N8,N9], + valid_sum(Blocklist), + valid_product(Blocklist), + blocks(Ns1, Ns2, Ns3). +``` + +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: + +```c +void score() { + puts("Let me take a look..."); + for (int i = 0; i < 8; i++) { + scorer[sudoku[i][i]] = sudoku[i + 1][i + 1]; + } + uint score = 1; + for (int i = 1; i <= 9; i++) { + score *= scorer[i]; + } + if (score >= 1000000) { + win(); + } else { + puts("That is an unimpressive sudoku."); + exit(0); + } +} +``` + +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. +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. + +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. +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. + +### Day 20: Strike a pose (fun / 31 solves / 368 points) +* Category: fun +* 31 solves / 368 points +* Time spent: ~30 minutes +``` +Time to show off those ugly xmas sweaters! + +Service: https://github.com/OverTheWireOrg/advent2019-strikeapose +``` +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. diff --git a/writeups/hah/seccon19.md b/writeups/hah/seccon19.md index 8cc407e..9c8eee5 100644 --- a/writeups/hah/seccon19.md +++ b/writeups/hah/seccon19.md @@ -1,7 +1,12 @@ # SECCON 2019 ## Retrospective +SECCON offered a nice array of challenges and while I had a quick look at most, I mainly concentrated on a crypto/web and a pwn one. Unfortunately not being able to solve either I spent most of my time on "lazy" which consisted of two stages, the first of which I solved rather quickly, but then getting totally stuck on the second part. While some of the other challenges, especially the stego ones, looked interesting they didn't seem very accessible without having experience in their domain, offering very little hints at possible avenues to test. ## lazy +* Category: pwn +* 332 points +* Time spent: ~6 hours + lazy.chal.seccon.jp 33333 lazy was a binary challenge whose description only contained a server address. After connecting a simple menu was presented that offered options to login, access Public contents or disconnect. The public area contained part of the challenge source code related to the login: @@ -71,6 +76,9 @@ Using those the login menu option could be used to access a private content area The download prompt contained another printf-vulnerability, and exploring it further I found that some environment variables were stored on the stack, including pwd and the home-directory which was used to define which folder was presented for downloading. Thinking the flag might be stored in another folder I thought about overwriting those paths, but because "/q/private" was appended to it arbitrary path access would still not have been possible. I also considered overwriting the GOT-entry of a linked function to divert program flow and skip some checks in the code and download other files, but because the binary had RELRO enabled (which it took me way to long to remember to check after having worked on the challenge for a while already) this option was out as well. In the end I was unable to get the final step of downloading the flag in time. lazy_solve.py contains a solution up to the final part which automatically downloads the login source code, leaks the username and password and downloads the challenge binary. ## ZKPay +* Category: Crypto +* 345 points +* Time spent: ~3 hours ZPKay was a crypto challenge consisting of a website that offered registered users to send custom currency to other users by use of generated QR codes. After registration each user was given 500 units of the currency, and 1 million was required to reveal the flag. Registering multiple accounts and pooling the currency was possible but would have taken too long; the intended path seemed to be to fake a QR code that allowed for withdrawal of high enough amounts from the admin account that sent the initial batch to each new user. Generating a couple of QR codes revealed that they encoded the username, the amount to be transferred, a proof and an hash: @@ -174,4 +182,7 @@ Interestingly neither the proof nor the hash seemed to depend on the amount as b The javascript of the page showed that other than the amount and the user password (as well as the session cookie) no information was sent to the server in order to generate the QR codes, which meant that the proof was generated once and stored serverside or was reconstructed with each request; however I did not find out how to get to the admin proof. Other teams seem to have solved it by simply generating QR codes with negative amounts encoded which would lead to the sending account getting credits added instead of subtracted, but I'm not sure whether that was the intended solution because the challenge name seemed to hint at some kind of zero knowledge-protocol being involved. ## Sandstorm +* Category: Misc +* 279 points +* Time spent: ~1 hour Sandstorm was a forensics challenge consisting of a grainy black-and-white-picture that contained some short text. Thinking the monochromatic pixels might encode a binary message I tried finding some relevant data using [zsteg](https://github.com/zed-0xff/zsteg) and stegsolve, but nothing interesting turned up. As it [turns out](https://github.com/10secTW/ctf-writeup/tree/master/2019/SECCON%20CTF%20quals/Sandstorm) I was on the wrong track and the image hid a QR code of the flag. \ No newline at end of file -- 2.43.0