justCTF 2019 write-ups by @terjanq
===
## Dominoes [misc, 51 solves]
Dominoes was a fun challenge. It was an introduction challenge to two harder ones if someone had only connected the dots :) The idea of the challenge comes from these two hard ones actually. I was glad that many teams solved it because that was my intention all along.
### Challenge
The player had to assemble a given set of puzzles into a meaningful sentence. Each domino had three letters on it. I didn't want the challenge to be too guessy so I included a hint in the challenge's description:
It shows how one should assemble the pieces.
For example, from DOM, OMI, MIN, INO, NOE, OES you create:
```
DOM
OMI
MIN
INO
NOE
OES
```
After overlapping, you see the word `DOMINOES`.
### The solution
I used the `backtracking` algorithm to find all the possible solutions where the correctness function is the existence of each word in the `english top 10000` dictionary.
After running the algorithm, it produced `7296` correct solutions, which is a lot. Impossible to bruteforce all combinations when submitting the flag.
From reading the first lines of the produced file we can notice that each sentence consists of the same words but in the permutated order.
```
there_the_player_like_you_shall_solve_doubt_great_in_my_mind_that_puzzle_was_no_single
there_the_player_like_you_shall_solve_doubt_in_my_mind_that_great_puzzle_was_no_single
there_the_player_like_you_shall_solve_was_no_single_doubt_great_in_my_mind_that_puzzle
there_the_player_like_you_shall_solve_was_no_single_doubt_in_my_mind_that_great_puzzle
there_the_player_like_you_shall_single_was_no_solve_doubt_great_in_my_mind_that_puzzle
there_the_player_like_you_shall_single_was_no_solve_doubt_in_my_mind_that_great_puzzle
there_the_player_like_you_solve_doubt_great_in_my_mind_that_puzzle_was_no_shall_single
```
The idea of the challenge is to find the correct flag from these `7296` lines. From the challenge description
> I suspect the key to be a semantically correct and meaningful sentence consisted of lowercase english words only. Can you help me uncover the key?
it was clear that the flag is in the unusual format, and that it consists of English words which when combined produce a grammatically correct meaningful sentence.
The approach I had in mind, was to reduce the number of lines via filtering out all "strange" sentences.
For example, I manually regex-removed the lines in the form:
```
Start: 7296
^.*(the_was).*$\n - 1632
^.*(the_you).*$\n - 1632
^.*(the_that).*$\n - 528
^.*(was_no_shall).*$\n - 1752
^.*(was_no_solve).*$\n - 875
^.*(solve_doubt_great).*$\n - 90
^the_there.*$\n - 40
^that_in_my_mind.*$\n - 86
^.*there_doubt_great.*$\n - 36
^.*that_great_in_my_mind.*$\n - 192
^.*player_like_there.*$\n - 28
^.*puzzle_the_doubt.*$\n - 12
^.*great_puzzle_player.*$\n - 13
^.*player_like_the_doubt.*$\n - 19
^.*player_like_doubt.*$\n - 65
^.*shall_solve_doubt.*$\n - 39
^.*player_like_the_puzzle.*$\n - 5
^.*there_doubt_in_my_mind.*$\n - 21
^.*was_no_single$\n - 116
^.*the_doubt_great.*$\n - 48
Left: 67
```
The above approach reduced the number of solutions to 67, from where it was relatively easy to find the best candidate for the flag, which is **justCTF{there_was_no_single_doubt_in_my_mind_that_great_player_like_you_shall_solve_the_puzzle}**
## Scam generator [web, 2 solves (unfixed) & 1 solve (fixed)]
I've got a nice idea of combining Server-Side Template Injection (SSTI) and Cross-site Search (XS-Search) when solving a `Safe Ninja` challenge from [hack.cert.pl](https://hack.cert.pl/challenge/safeninja). In the challenge, you had a clear `SSTI` in `Jinja2` parser, but you couldn't use any of the `'"()|` characters. I won't reveal the solution to the challenge here since it's quite different than what I will be presenting but rather present my idea. What I noticed was that I only needed `a-z[space].` characters to solve the challenge. The idea was to use XS-Search and do injection like `{{ O.o if title in request.cookies else 0 }}` which throws `HTTP 500` (*O is undefined*) if `title` was found in `cookies`, and returns `HTTP 200` otherwise.
### Challenge
My challenge was a bit more complex - SSTI wasn't that obvious and the charset was very limited (originally `[\w\.\ ]`. You had a field in the form of `scam.scammer.full_name` which was a hint for a possible SSTI. If you tried `scam.scammer` you would notice an object displayed. During the CTF, when there were still 0 solves, I released a hint that the server runs on `Python:2.7` which was helpful information to solve the challenge.
### The oracle
As mentioned already, the solution for the challenge was supposed to be a XS-Search. You could easily throw an error in `Jinja2` by providing `O.o` for instance. This would normally result in `HTTP 500` but in my challenge instead of throwing the error, a message `Hacking detected!` was displayed. The only difference in the response was the header `X-Content-Type: nosniff`. This header means that strict content-type checking should be enabled and therefore scripts included in the page cannot arrive with `text/html` MIME type.
### The solution
Browsers do not turn the `nosniff` feature on by default, so including a and html page `Hacking detected` as a script will result in the following error `Uncaught SyntaxError: Unexpected identifier` which can be caught using `window.onerror` listener. Otherwise, the resource will be blocked by `CORB` mechanism and will not throw any errors.
As for the SSTI, the player was supposed to first discover [standard context](https://flask.palletsprojects.com/en/1.1.x/templating/#standard-context) variables such as `config` where I hide `PROMO_CODE` that gives a player more time of bot usage. Then, sending the payload `O.o if request.args.p in request.cookies.session else g` as victim's type should give the URL like http://scam-generator.web.jctf.pro/gen_scam?scammer=5fea79a4-d1f2-464b-bac1-66c7808962ff&victim=49fb91c4-0e33-4304-89e5-8eb76e800da2. Now appending a parameter `p=smth` will either return `Hacking detected` if `smth` was found in `session` cookie or the SCAM message will be displayed otherwise.
The intended solution involved taking advantage of `Dominoes` challenge, and requesting all triples from the range `[a-f0-f-]` and then recover the session cookie from it. The character-by-character approach was supposed to be too slow, and the cookie was changing with each new admin's session (that guaranteed you could use multiple instances of the bot to solve the challenge in parts).
Then, after recovering the cookie, all you had to do was to log in as admin, copy scammer identity and display the template in `gen_scam`, where the flag was hidden in scammer's phone number. **justCTF{Oh_I_didnt_realize__GLOBAL__was_a_thing_without_parentheses_Hope_this_time_you_found_the_expected_XS-Search?!}**
### Unintended solution
During the CTF, we got a message from a player that they are confused because a flag says something about `xs-search` but they found the flag in globals... using a payload like `scam.scammer.__class__.to_dict.__globals__.FLAG`. I acted very quickly and managed to clone the challenge before any other team solved it. In the original challenge, I disabled the intended solution by removing the flag from DB (instead it stated that the same approach should provide a correct flag in the harder challenge). This created two different challenges, which you couldn't both solve using the same payload. The patch in the FIXED version was to remove `_` from allowed characters. The original flag was **justCTF{XS-Search_is_s0o_fr3aKING_Aw3s0m3!!!11}**
## md5service [misc, 28 solves]
The idea for this challenge was this one-liner shellcode that I wrote when solving a challenge from one CTF.
```sh
read x;y=`md5sum $x`;echo $y;
```
The original challenge was about Local File Inclusion (LFI) and I used similar code to retrieve files from the server. I then tried wildcarded `/etc/passwd` in the form of `/etc/*wd` and to my surprise, it worked. I wasted some time before I realized that it was my script that was expanding the path locally and sending the expanded path to the server... I think it's a very funny bug so I decided to create a challenge that takes advantage of this funny hole in the code. Although you cannot achieve Remote Code Execution (RCE) by abusing the bug, you can pass wildcarded paths and flags to the command and with that, discover hidden files on the server. In the challenge, I created a vulnerable `MD5` command that was calculating hashsum of the file from the provided path and safe `READ` command that was just reading the file when the correct path was provided.
The idea of the challenge was to read `md5service.py` file, from there read vulnerable code and discover a hint ``The flag is hidden somewhere on the server, it contains `flag` in its name``. Then running the following will display the prefix location of the flag.
```sh
Welcome to md5service!
I have two commands:
MD5 <file> -- will return a md5 for a file
READ <file> -- will read a file
Cmd: MD5 --tag /*/*flag*
Executing MD5 on '--tag /*/*flag*'
Result:
b'MD5 (/0c8702194e16f006e61f45d5fa\n'
```
With that, it's easy to bruteforce character after character and discover the full path of the flag which is `/0c8702194e16f006e61f45d5fa0cd511/flag_a6214417905b7d091f00ff59b51d5d78.txt`
More detailed [write-up](https://github.com/hyperreality/ctf-writeups/tree/master/2019-justctf#md5service) by Cr0w team.
## p&q service [crypto, 3 solves]
I will not lie, this is not a challenge fully invented by me. The idea of the challenge comes from Dragon Sector team and was used during DS Finals in 2018, but I've done further math and extended the challenge to be more challenging and fun.
### the original challenge
In the original challenge we could give any `p`, `q` and `cipher` in the RSA algorithm and the server would respond whether it was deciphered to the chosen plaintext or not (after stripping trailing spaces). The intended solution was to use any `p=hex(chosen_text+spaces)`, `q=3` and `cipher=p`. Without any math, you could basically solve the challenge with 75% chances just by trying this combination. Let's write some math:
$$\text{cipher}^{d}\ mod(p*q) = \text{message}$$
This is how you decipher ciphertext in RSA algorithm. When using the combination mentioned above, we get:
$$p^{d}\ mod(3*p) = message$$
Let say `message=m`, the above eqation can be written as:
$$p^{d} = m + 3*k*p$$ for some `k`.
We can notice that when moduling the equation by `mod(p)`, we get:
$$p^{d}\ mod(p) = m\ mod(p) + 0$$
which implies `m = lp` for some `l`. When doing `mod(3)` we get:
$$ p^{d}\ mod(3) = m\ mod(3) + 0$$
If `p mod(3) = 1`, and we control that, it implies that `m = lp + 1` for some `l` and every `d`, because:
$$1^{d} = m\ mod(3)$$
We can quickly notice that `p` fulfils both conditions `m = 1p` and `m mod(3) = 1`. From the Chinese Reminder Theorem, this is also the only solution in the adequate range.
If `p mod(3) = 2` it is not true for every `d`. That is because:
$$2^{d} = m\ mod(3)$$
has two different solutions, depending on the `d`. With 50% chances though we will hit the interesting number.
### the solution
As we could notice, we would want to have
$$1^{d} = m\ mod(q)$$
For `q = 3` it was relatively easy, but I wanted to generalize the solutions to more numbers. Let's see what happens when `q = p-1`. We get:
$$p^{d}\ mod(p-1) = m\ mod(p-1)$$
We see that `p mod(p-1) = 1` and therefore we achieved exactly what we wanted:
$$1^{d} = m\ mod(p-1)$$ and which only has one solution from CRT.
It would be nice, but it's impossible for `p` and `p-1` to be both primes.
Let's see what happens for `q= (p-1)/2 `:
$$ p^d\ mod(\frac{p-1}{2}) = l$$
which we can write as:
$$ p^d = l * m*\frac{p-1}{2} $$ for some `m`. By multplying by `2` we get:
$$2*p^d = 2*l + m*(p-1)$$
By doing `mod(p-1)` we get:
$$2*(1)^d = 2*l\ mod(p-1) + 0$$
While `l` is smaller than `p/2` it implies that `l = 1`, and therefore we got once again:
$$1^{d} = m\ mod(\frac{p-1}{2})$$
So the solution is `p`, `q = (p-1)/2`, `cipher = p`, while preserving the condition that `q` is prime.
### The actual challenge
I believe that the challenge created by me is significantly different than the original one, hence knowing the solution for the original would not give a significant advantage to other teams. Instead of *trailing spaces* I used *unsafe padding* and created strict requirements for `p` and `q` to both be very strong primes. A well-explained solution (without math proof) can be found [here](https://github.com/hyperreality/ctf-writeups/tree/master/2019-justctf#pq-service). After solving the challenge, the flag would pop out **justCTF{pure_math_is_better_than_insecure_crypto_:)_shout_out_to_DS_for_giving_me_the_idea!}**
Sign in with Wallet
Connect another wallet