Add hxp36c3 writeup

[pub/jan/ctf-seminar.git] / writeups / aliponti / asis19.md

# ASIS CTF Finals 2019

While playing ASIS CTF Finals 2019, I worked on the following challenges.

## Protected Area

| Points | Solves | Category |
|--------|--------|----------|
| 119    | 41     | web      |

Description:

> We have built an area protected by a hard password
> 
> Note: DO NOT Brute force the server (the rate limit will ban you), the question may need an OFFLINE brute-force!

This challenge presents us with a webpage, that displays some text and after an instance, some more text appears. Therefore, we immediately look at the source code and find the responsible javascript in `app.js`:

```
var file_check = function(file){

    $.ajax({
        url: '/check_perm/readable/',
        data: {'file': file}
    }).done(function(data){
        if (data == "True") {
            file_read(file)
        }else{
            console.log('fail')
        }
    })
}

var file_read = function(file){

    $.ajax({
        url: '/read_file/',
        data: {'file': file}
    }).done(function(data){
        update_page(data)
    })

    return
}

var update_page = function(text){
    $("#t").append(text)
}

$(document).ready(function() {
    console.log("ready!");

    file_check('public.txt');
});
```

So there appear to exist at least two endpoint, `/check_perm/readable/` and `/read_file/`. We look at the first one and notice that it returns `True` supposedly if the requested file exists and we can read it, otherwise `0` is returned. The way of writing `True` with capital `T` strongly suggested that we are dealing with a python backend, probably flask. 

The other endpoint returns the content of the requested file. Just out of curiosity we try `http://66.172.33.148:8008/read_file/?file=private.txt` but no flag there. Requests for files like `flag.txt` returns `500`, while `flag` without ending returns `Security`. Strange. Further investigation shows that all non-txt file requests return `500` (probably file does not exists) while requests for other file endings return `Security`. Therefore we suppose, only txt files can be returned.

A common vulnerability of file access systems like this is path traversal, where we use a relative path to break out of the current directory and access files outside of the normal scope. We can try this by requesting `../../../../../../../../../../etc/passwd` for both endpoints. The first one does return `True`, so we know that path traversal is possible, however no luck on the second one, that returns `Security` as expected, since it's no txt file. Adding a `.txt` ending to the file turns this into a `500` response, since that file does not exist.

My guess now was that we need to exploit some weird behaviour of the file open function in python, maybe including wildcards like `*` or `?`, but no luck there. This would only work if the app uses the `glob` function. However we notice something interesting, namely the second endpoint does strip out `../`, while the first one does not. We can gain path traversal on the second endpoint with `..././`. I also tried to exploit this fact to bypass the txt-only check with requests for files like `/etc/passwd.tx../t` but this does not help in any way. This is where everything got stuck a bit and I continued with mapping out what files are on the system and trying to find out where our current working directory is but no juicy information was to be found.

We came to a solution when someone in the mattermost chat found the trick to include non-txt files, like so `http://66.172.33.148:8008/read_file/?file=....//....//....///app/main.py&test=ha.txt`. This means the app is checking the whole argument string for a txt ending and not only the relevant parameter. With this, we where able to download the app code, which, apart from the stuff we already figured out, had some interesting functionality included:

```
from .functions import *
...
@app.route('/protected_area_0098', methods=['GET'])
@check_login
def app_protected_area() -> str:
    return Config.FLAG
```

and looking at `functions.py`, we see:

```
def check_login(f):
    """
    Wraps routing functions that require a user to be logged in
    """
    @wraps(f)
    def wrapper(*args, **kwds):
        try:
            ah = request.headers.get('ah')

            if ah == hashlib.md5((Config.ADMIN_PASS + Config.SECRET).encode("utf-8")).hexdigest():
                return f(*args, **kwds)
            else:
                return abort(403)
        except:
            return abort(403)
    return wrapper
```

So we finally check `http://66.172.33.148:8008/read_file/?file=....//....//....///app/config.py&test=ha.txt`:

```
    FLAG       = os.environ.get('FLAG')
    SECRET     = "s3cr3t"
    ADMIN_PASS = "b5ec168843f71c6f6c30808c78b9f55d"
```

So we can craft the request as follows `curl -H "ah: cbd54a3499ba0f4b221218af1958e281" http://66.172.33.148:8008/protected_area_0098` and jackpot: `ASIS{f70a0203d638a0c90a490ad46a94e394}`

## Secrets

| Points | Solves | Category             |
|--------|--------|----------------------|
| 304    | 10     | misc, forensics      |

Description:

> An Album Full of Secrets is left for the most curious ones to reveal its secrets!

This challenge consited of a bunch of PNG pictures of famous people. I started by check the exif data with `exiftool -a`, which gave me the following output for one of the images: `Warning: [minor] Trailer data after PNG IEND chunk`. So I checked that with `xxd` and found that a base64 encoded string was appended to the image data. Decoded it revealed `The password is: atalmatal`. But for now, I had no idea where to use that password. Another thing we can note from the exiftool output is that all but 3 of the images had a text comment added saying `no SecDrive`. Again, this didn't tell me anything so I just left it be. I proceeded by using the tools `binwalk` and `foremost` to look for embedded files, maybe a ZIP archive which is password protected, but no luck. I also extracted the binary palette data two of the images included but this did not look suspicious. 

My next thought was that some kind of steganography was used in order to hide data in the images themselves. This website has a list of stegano tools and a very useful docker container shipping them too. [0](https://github.com/DominicBreuker/stego-toolkit) I tried the relevant ones for the PNG format, especially the ones that can be used with a password, but again no luck. The only promising output that I got was from the zsteg tool that reported a DOS executable it found, so I extracted it, tried to get it running on a Win10 VM as well as a DOS emulator for Linux but couldn't get it to work, possibly a false alarm by the tool. 

Next I tried one of the useful online tools. [https://aperisolve.fr/](https://aperisolve.fr/) let's you upload images for analysis. So I did that for all the images and bingo, 3 of them (exactly the ones with no text comment) had some suspicious looking least significant bit (LSB) values. When split into plains for every bit of every color channel, one could see that the least-significant bits where almost all black, except for a single line at the beginning. This is a very common technique to hide data in images, since the change introduced is almost invisible to the naked eye. I used the website and also some scripts to extract the data but it did not make any sense. I tried several permutations and different was of extracting it, without any luck. I also checked different CTF challenges from previous contests ([1](https://github.com/krx/CTF-Writeups/blob/master/CSAW%2016%20Quals/for250%20-%20Watchword/jk_actual_writeup.md), [2](https://hexpresso.wordpress.com/2014/05/10/asis-ctf-quals-2014-stego-100-blocks-write-up/), [3](https://honeysec.blogspot.com/2019/05/writeup-csactf19-challenges.html?m=1), [4](https://veteransec.com/2018/10/18/vetsec-takes-first-in-the-hacktober-ctf-summary-steganography-write-up/), [5](https://shankaraman.wordpress.com/category/ctf/stegano/) to find any other method I could use but did not find anything so after some time I gave up.

![Image split into planes](asis19/plain_analysis.png)

After the CTF was over, I checked the write ups and found a [solution to this challenge by p4](https://github.com/p4-team/ctf/tree/master/2019-11-16-asis-finals/secrets). Apparently the authors used [this tool](https://github.com/mgeitz/albumfs) from github to create the challenge. It's a steganography tool that hides a file system in a bunch of images, using the LSB method as well as XOR-encryption with a key. I never saw this tool before as I do not think it is very popular, judging by the relatively few stars and forks it got on github. However, now it became clear that the challenge name was a hint to this tool, as well as the comment I found. With more profound research from my side I should have been able to find this tool and make more sense of this challenge. I tried using the tool to solve the challenge at this point but apparently the code does not compile without editing and since my C skills are scary low, I did not proceed with it.


## Serifin

| Points | Solves | Category             |
|--------|--------|----------------------|
| 140    | 33     | crypto               |

Description:

> A sincere gift for cryptographers, enjoy solving it!

This crypto challenge presents us with some code used to encrypt a flag, we also get the output of said encryption operation:

```
#!/usr/bin/env python

from Crypto.Util.number import *
from flag import flag
import gmpy2

def serifin(a, l):
    S, s = a, a
    while True:
        S += float(a)/float(l)
        if S - s < .0001:
            return int(S) + 1
        else:
            s, a = S, float(a)/float(l)

def genPrime(nbit):
    while True:
        p = getPrime(512)
        if p % 9 == 1 and p % 27 >= 2:
            q = gmpy2.next_prime(serifin(p, 3) + serifin(p, 9) + serifin(p, 27))
            if q % 9 == 1 and q % 27 >= 2:
                return int(p), int(q)

def encrypt(m, n):
    m = bytes_to_long(m)
    assert m < n
    return pow(m, 3, n)

nbit = 512
p, q = genPrime(nbit)
n = p * q
c = encrypt(flag, n)

print 'c =', c
print 'n =', n
```
```
c = 78643169701772559588799235367819734778096402374604527417084323620408059019575192358078539818358733737255857476385895538384775148891045101302925145675409962992412316886938945993724412615232830803246511441681246452297825709122570818987869680882524715843237380910432586361889181947636507663665579725822511143923
n = 420908150499931060459278096327098138187098413066337803068086719915371572799398579907099206882673150969295710355168269114763450250269978036896492091647087033643409285987088104286084134380067603342891743645230429893458468679597440933612118398950431574177624142313058494887351382310900902645184808573011083971351
```

So at a first glance, this looks like textbook-RSA with `e = 3`. What is even more suspicious is that the primes get derived with some weird, fishy looking algorithm. Without further analysing that I checked [factordb](http://www.factordb.com/) if the `n` has known factors and indeed, we get lucky:

```
>>> p
10718841513477905819120058147135847238291365362593720675636253771082993743788743083816117407101738585993985506647694375447285228211151896705183442597773779L
>>> q
39268063621491165558293370755773815300739539018598511154583095766289789691669875090357609442626770422364550257841199885538175542665396553281747272813511469L
```

So this should be easy from there, just do regular RSA decryption and we are done here.

But wait, not so fast. As it turns out, `gcd(3, phi(n)) = 3`. Doh! So RSA decryption does no work since there is no multiplicative inverse `e^-1 mod n`. So I searched the web for this problem of RSA and found two relevant CTF challenges that look similar [here](https://github.com/p4-team/ctf/tree/master/2016-03-12-0ctf/rsa) and [here](https://github.com/p4-team/ctf/tree/master/2015-10-18-hitcon/crypto_314_rsabin#eng-version)

The first link looks especially promising so I tried to implement their code used to solve it. On of the main problems is finding the cube root `mod n` boils down to find the cube root `mod p` or `mod q` accordingly, thanks to the Chinese Remainder Theorem. Unfortunately I had less luck than the authors of the write up, since Wolfram Alpha was not able to calculate the roots for me. So I ended up using this code I found on Stackoverflow: 

```
#assumes p prime, it returns all cube roots of a mod p
def cuberoots(a, p):

    #Non-trivial solution of x^r=1
    def onemod(p,r):
        t=p-2
        while pow(t,(p-1)/r,p)==1: t-=1
        return pow(t,(p-1)/r,p)

    def solution(p,root):
        g=onemod(p,3)
        return [root%p,(root*g)%p,(root*g^2)%p]

    #---MAIN---
    a=a%p

    if p in [2,3] or a==0: return [a]
    if p%3 == 2: return [pow(a,(2*p - 1)/3, p)]

    #There are 3 or no solutions

    #No solution
    if pow(a,(p-1)/3,p)>1: return []


    if p%9 == 4:                                #[13, 31, 67]
        root = pow(a,(2*p + 1)/9, p)
        if pow(root,3,p) == a: return solution(p,root)
        else: return []

    if p%9 == 7:                                #[7, 43, 61, 79, 97
        root = pow(a,(p + 2)/9, p)
        if pow(root,3,p) == a: return solution(p,root)
        else: return []

    if p%27 == 10:                              #[37, 199]
        root = pow(a,(2*p +7)/27, p)
        h=onemod(p,9)
        for i in xrange(9):
            if pow(root,3,p) == a: return solution(p,root)
            root*=h
        return []

    if p%27 == 19:                              #[19, 73, 127, 181]
        root = pow(a,(p + 8)/27, p)
        h=onemod(p,9)
        for i in xrange(9):
            if pow(root,3,p) == a: return solution(p,root)
            root*=h
        return []
    #We need an algorithm for the remaining cases
    return tonelli3(a,p,True)
```

Here I noticed some similarities with the original code, namely the line `if q % 9 == 1 and q % 27 >= 2`. This looks like we are on the right track and indeed, `p` and `q` are equal to `10`, `19` `mod 27` respectively. Si we know we will find the roots if the exist and indeed we find 3 roots for `p` but none for `q` so this leads is also a dead end. I looked into the other link, namely Rabin's Algorithm, where we can decrypt a similar text if `e` is a power of 2, but I could no come up with a way to get rid of the factor 3, which remains always regardless of the factor we multiply it with. I also read more about CRT and found some more interesting links [here](http://www.math.clemson.edu/~sgao/crypto_mod/node3.html) and [here](https://www.rootnetsec.com/picoctf-weird-rsa) but nothing led anywhere so this is how far I came during the CTF.

Afterwards, [a write-up](https://github.com/p4-team/ctf/tree/master/2019-11-16-asis-finals/serifin) got published by p4.

So apparently I was not that far off, I just made a mistake at calculating the roots, somehow the algorithm I used failed me. What we learn is, never blindly trust code. Also my understanding of the matter was not profound enough to really reflect on what is going on, I mostly just mimicked what other people where doing, still lot's to learn. Also sage is such a powerful tool, I would really like to learn how to use it at some point.

## Ema's secret

| Points | Solves | Category |
|--------|--------|----------|
| 233    | 16     | crypto   |

Description:

> Ema, a talented, young but inexperienced cryptographer, who has been working on her own cryptosystem, has just released the system for testing , try to break her cryptosystem and find her secret message. Good luck!!!

For this challenge we can connect via `nc` to a remote service. Here we can see the code used for encryption and key-generation. In order to communicate with the service we need to solve a proof-of-work first, luckily a colleague of mine was so nice to provide a script for that.

Since the key-generation function does not simply use random number, but ensures certain constraints are satisfied, we infer that this is a vulnerability exploitable somehow.

```python
def keygen(nbit):
    while True:
        p = getPrime(nbit)
        a, b, c, d = [random.randint(1, p-1) for _ in range(4)]
        key = p, a, b, c, d
        if gcd(a, b) * gcd(c, d) == 1 and isPrime(p) > 0 and a*d - b*c != 0:
            return key
```

```python
def encrypt(msg, key):
    msg = bytes_to_long(msg)
    p, a, b, c, d = key
    assert msg < p
    m_d = (msg * a + b) % p
    m_n = (msg * c + d) % p
    if m_n > 0:
        return int(m_d * inverse(m_n, p)) % p
    else:
        return 'encryption failed'
```

We can input arbitrary strings to encrypt, so what we are looking at is probably a choosen-plaintext attack. I looked around a bit to try to figure out some properties of the system that we can infer, but the only thing I found is that encrypting the empty string results in `m_d = b` and `m_n = d`, so we get parts of the key in a weird form. I further discussed with my colleagues what we would need in order to decrypt messages, since to me this is always the first step in such a crypto challenge. From there one can check how to obtain the necessary values without wasting time on unhelpful functionality.

Unfortunately I did not work any further on this challenge and the team could not solve it, also there is not write up available on CTFtime. I only found [github gist containing sage code](https://gist.github.com/samueltangz/ae5c0a8b7046b643da053d0e4a892841#file-asis-ctf-finals-2019-emas-secret-sage) that apparently solves the challenge but without context I can't figure out what is going on.


## Close primes

| Points | Solves | Category |
|--------|--------|----------|
| 136    | 34     | ppc      |

Description:

> The people who can do you the most damage are the ones who are closest to you.

This was a programming challenge where one had to find two large neighboring primes that where not too close. It used a proof-of-work, so I reused the script from the previous challenge. Unfortunately I misread the challenge description and though one had to lock for primes that where extra close, `<` instead of `>`. So I researched the web for home to compute the next prime give one and found [1](https://math.stackexchange.com/questions/35300/what-is-the-most-efficient-algorithm-to-find-the-closest-prime-less-than-a-given). Also I looked at twin primes, since they should satisfy the condition in any case [2](https://stackoverflow.com/questions/10143431/finding-the-nth-twin-prime). I ended up using a very naive approach, generating primes and checking the manually for closeness using the following python script with the gmpy2 library.

```python
from Crypto.Util.number import *
from gmpy2 import sqrt

p = getPrime(512)
q = getPrime(512)

sp = sqrt(p)
sq = sqrt(q)

print(sq-sp)
```

This did indeed give me a hit at the first try, but only since I misread the condition as stated before and I was wondering why my solution did not get accepted.

Overall, the challenge should not have been that hard, give some programming skills and systematic approach to solving it, give e.g. [this write up by p4](https://github.com/p4-team/ctf/tree/master/2019-11-16-asis-finals/close_primes)

## Time report and summary

Overall, this CTF was pretty fun. Unfortunately I could not solve any challenges, but I managed to immerge myself into some of them deep enough such that I could actually work on them while understanding more or less what was going on. Also a bit of a learning experience was involve, since I got to know new tools for forensics/stego and learn about new concepts during the crypto challenges such as CRT.

As I played this CTF before I got to know that we should keep time I do not have a precise timesheet for it, but I played basically throughout the whole weekend, so I would estimate around 8-9 hour a day. Reporting and postprocessing of the CTF also took around 10-12 hours.