add theguy/ctfzonequals19.md writeup

[pub/jan/ctf-seminar.git] / writeups / icecrax / asis2019.md

# ASIS 2019
## web: protected-area (unsolved)
A web page is given which printed the content of a file from a directory to the html of the page.

First I looked up the source file of the webpage. It was importing the following JS script:
``` javascript   
    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');
    });
```
The first command `file_check` executed like this `http://66.172.33.148:8008/check_perm/readable/?file=public.txt` gives either `True` or `0`, depending if the file exists. If the file is not found it prints in the console `fail`. If it exists its being passed to the command `file_read`.

The second command `file_read` executed like this `http://66.172.33.148:8008/read_file/?file=public.txt` opens the file. It then passes itas an argument to `update_page`. If the file is not found `security` or `500` is being printed.

The trird command `update_page` takes the passed text and appends to the DOM.

I tried path triversal by encoding the ../ in UTF-8, by replacing ../ with ..././ or ..;/, but it seems the dots and slash are still being replace, bacause `http://66.172.33.148:8008/read_file/?file=../../../public.txt` is being interpreted the same as `http://66.172.33.148:8008/read_file/?file=public.txt`

There was also `private.txt` file in the same directory as `public.txt` with the content `lol haha`.

I tried to mess up with the console:
`update_page("<script>alert()</script>")` executes the script and the pop up shows, hints towards an XSS attack.

I tried looking for a way to list the directory via javascript
``` javascript
const testFolder = './public.txt';
const fs = require('fs');

fs.readdir(testFolder, (err, files) => {
  files.forEach(file => {
    console.log(file);
  });
});
```

## web: cursed-app (unsolved)

An `cursed_app.elf` file is given.
The description of the challenge stated `If we want to say 100, should we start at 1 and count until 100?` and `sha256(flag) = dd791346264fc02ddcd2466b9e8b2b2bba8057d61fbbc824d25c7957c127250d` was given.

First I tried to brute force the hash using variuos websites. No luck there.
Hexdumping the file reveals some readable strings: `hexdump -C cursed_app.elf`. 
After that I found a more useful command `strings`, which filters only the readable strings.
Intressting segment was 
```
[]A\A]A^A_
please locate license file, run ./app license_key
Congratz! You got the correct flag!!
Bummer! You got the wrong flag!!
;*3$"
```
So I tried executing file. If it's being run without arguments the first message is printed: `please locate license file, run ./app license_key`, if a file is specified it prited `Bummer! You got the wrong flag!!`.

So clearly the program was reading the flag file and computing and comparing the string.

I tried `strace` and `ltrace` to understand better what functions and libraries are being called. 

Using `objdump -d cursed_app.elf` showed me that there was no main function.

I then installed `Hopper`, which is a reverse engineering tool that lets me disassemble, decompile and debug the applications. With it I tried to undestand the execution pattern and to find out how and when `Congratz!` is being printed. I figured out that after opening the flag/key file 59 characters are being read and most likely compared (although no cmp function was found). Those 59 chars could be brute forced and encrypted with `sha256` and then compared with the given solution in the description. A brute force of 59 chars seems impossible.

## web: Golden_Delicios (unsolved)

 A `.sage` file is given, containing the following python scrypt. And at the bottom of it, there were the results of the print function commented.

 ``` python
 #!/usr/local/bin/sage

from sage.all import *
from secret import *

print '(A_1, B_1) =', (A_1, B_1)
print '(A_2, B_2) =', (A_2, B_2)

E_1 = EllipticCurve(Zmod(n_1), [A_1, B_1])
E_2 = EllipticCurve(Zmod(n_2), [A_2, B_2])

d_1 = int(flag[:len(flag)/2].encode('hex'), 16)
d_2 = int(flag[len(flag)/2:].encode('hex'), 16)

assert d_1 < n_1 and d_2 < n_2 and n_1 * n_2 % 2 == 1

print 'P_1 =', P_1
print 'P_2 =', P_2

Q_1 = d_1 * P_1
Q_2 = d_2 * P_2

print 'Q_1 =', Q_1
print 'Q_2 =', Q_2
 ```

The EllipticCurve function was interesting. After googling it I found out that there exists a very popular algorithm in cryptography for encrypting public keys.
The formula for an elliptic curve is as follows: `y^2=x^3+ax+b` and the parameters corresponded to those used in the script, so I guessed I was on the right track.
After that I spent time reading wikipedia articles and watching youtube youtibe videos explaining it. But after some time trying to understand it, I gave up... I decided to concetrate more on the other challenges.

## web: Bit_game (unsolved)
The following script was given, together with a text file containing the resulting H and enc variables:
```python
import random
from Crypto.Util.number import *
#from flag import flag

def gen_rand(nbit, l):
    R = []
    while True:
        r = random.randint(0, nbit-1)
        if r not in R:
            R.append(r)
            if len(R) == l:
                break
    R.sort()
    rbit = '1'
    for i in range(l-1):
        rbit += (R[i+1] - R[i] - 1) * '0' + '1'
    rbit += (nbit - R[-1] - 1) * '0'
    return int(rbit, 2)

def genkey(p, l):
    n = len(bin(p)[2:])
    f, skey = gen_rand(n, l), gen_rand(n, l)
    pkey = f * inverse(skey, p) % p 
    return (p, pkey), skey

def encrypt(msg, pkey):
    p, g = pkey
    msg, enc, n = bytes_to_long(msg), [], len(bin(p)[2:])
    print(n)
    for b in bin(msg)[2:]:
        s, t = gen_rand(n, l), gen_rand(n, l)
        c = (s * g + t) % p
        if b == '0':
            enc.append((c, t))
        else:
            enc.append((p-c, t))
    return enc
    
p = 862718293348820473429344482784628181556388621521298319395315527974911
l = 5

pkey, skey = genkey(p, l)
enc = encrypt(flag, pkey)
H = pkey[1] ** 2 % p
print('H =', H)
print('enc =', enc)
```

I think I was on the right track on this one. Sadly this challenge was released on the last day and I didn't get the opportunity to solve it during the CTF. The CTF was over and the challenge was left unsolved. I had an Idea how to begin, but applying what I found didn't produce meaningful output. I continued working on it afterwards, since I spent the most time on it and I wanted to finish it.
Nevertheless this is what I managed to find out during the CTF:
Note: A lot of time the was spent reading articles, researching and understanding the underlying theorems and math applied.  

    1) Numbers produced by the 'gen_rand()' function are not completely random. Their binary representation always have five '1's.
    
    2) Equation of the form x^2 ≡ q (mod n) are called "Quadratic residues".  

    3) Reversing H = pkey[1] ** 2 % p is a hard problem if 'p' was a prime, but since it is not, we could split it into factors and try to find solutions for all the individual factors pi: pkey^2 ≡ H (mod pi).

    4) Legendre symbol or Euler’s Criterion can be used to check if a number is a quadratic residue.

    5) The solutions from the individual factors can be combined via the "Chinese remainder theorem" to find a solution to the original problem, meaning we will find the public key.

    6) For finding solutions to the individual problems there are two approaches:
        - If `'a'` is a quadratic residue (mod p) and `p ≡ 3 (mod 4)` then `a^((p+1)/4)` is a solution to `x^2 ≡ a (mod p)`. 
        - If `a ≡ 1 (mod 4)` there is no analogous formula. In that case, one may use the "Tonelli-Shanks algorithm".

PS: I posted a detailed solution for this challenge as well.