ふるつき

v(*'='*)v かに

TSG CTF 2019 Writeup

insecureとしてTSG CTFに出ていました。868点で18位でした。難しくて実力不足を感じました。泣いた。

[Forensics 92 + 178 pts (90 + 61)Solves] Obliterated File & Obliterated File Again

※ This problem has unintended solution, fixed as "Obliterated File Again". Original problem statement is below.

Working on making a problem of TSG CTF, I noticed that I have staged and committed the flag file by mistake before I knew it. I googled and found the following commands, so I'm not sure but anyway typed them. It should be ok, right?

※ この問題は非想定な解法があり，"Obliterated File Again" で修正されました．元の問題文は以下の通りです．

TSG CTFに向けて問題を作っていたんですが，いつの間にか誤ってflagのファイルをコミットしていたことに気付いた！とにかく，Google先生にお伺いして次のようなコマンドを打ちこみました．よくわからないけどこれできっと大丈夫...？

$ git filter-branch --index-filter "git rm -f --ignore-unmatch problem/flag" --prune-empty -- --all
$ git reflog expire --expire=now --all
$ git gc --aggressive --prune=now

Difficulty Estimate: easy

I realized that the previous command had a mistake. It should be right this time...?

さっきのコマンドには間違いがあったことに気づきました．これで今度こそ本当に，本当に大丈夫なはず......？

$ git filter-branch --index-filter "git rm -f --ignore-unmatch *flag" --prune-empty -- --all
$ git reflog expire --expire=now --all
$ git gc --aggressive --prune=now

Difficulty Estimate: easy - medium

要するにgitで丁寧に削除したファイルを復元してみろという問題です。

1個目は

[https://stackoverflow.com/a/6018043:title]

を見てこれで探してみると、削除漏れらしきコミットが見えるので、その一つ前のコミットにcheckoutして中身を覗きました。zlib compressedなデータの読み方をPHP以外に知らないので、gzuncompressed を使いました。

$ git log --diff-filter=D --summary
commit 266f4148e4cf37bdbfb57da379ea49b2f106e6b2 (HEAD -> master)
Author: tsgctf <info@tsg.ne.jp>
Date:   Fri May 3 04:33:22 2019 +0900

   delete .travis.yml

delete mode 100644 .travis.yml

commit 28d2b74b0c40583a87cf275f9f0cdfd55042884d
Author: tsgctf <info@tsg.ne.jp>
Date:   Thu May 2 05:45:41 2019 +0900

   add problem statement

delete mode 100644 flag
php -a
Interactive mode enabled

php > $a = file_get_contents("flag");
php > echo gzuncompress($a);
TSGCTF{$_git_update-ref_-d_refs/original/refs/heads/master}

2問目はコマンドが少し変わって、1問目と同じ解き方ができなくなっています。最早 .git以下のオブジェクトを全部見て回るしか無いと思ってそういう手段を探すと git show - Git - how to list ALL objects in the database - Stack Overflow を見つけたのでやりました。

user@box:~/TSGCTF/obliterated_file_again/easy_web$ {
>     git rev-list --objects --all
>     git rev-list --objects -g --no-walk --all
>     git rev-list --objects --no-walk \
>         $(git fsck --unreachable |
>           grep '^unreachable commit' |
>           cut -d' ' -f3)
> } | sort | uniq | grep flag
Checking object directories: 100% (256/256), done.
Checking objects: 100% (101/101), done.
c1e375244c834c08d537d564e2763a7b92d5f9a8 problem/flag
user@box:~/TSGCTF/obliterated_file_again/easy_web$ git cat-file -p c1e375244c834c08d537d564e2763a7b92d5f9a8 > flag
user@box:~/TSGCTF/obliterated_file_again/easy_web$ php -a
Interactive mode enabled

php > echo gzuncompress(file_get_contents("flag"));
TSGCTF{$_git_update-ref_-d_refs/original/refs/heads/master_S0rry_f0r_m4king_4_m1st4k3_0n_th1s_pr0bl3m}

[Crypto 497pts (10 Solves)] OPQRX

Can you decrypt RSA? I'll give a hint value, XOR.

ここにRSAの暗号文がありますが、XORをあげるので、代わりに平文をください。

Difficulty Estimate: Easy

単純なRSAですが、 N, C, E に加えて X = P xor Q としたXも与えられています。次のようなスクリプトで上位bitから候補を絞っていきました。少し待つとP, Qが得られます。p, qは順不同なのでそれをやると探索範囲が半分になりますね。今気が付きました。

exec(open("flag.enc").read())

K = 1 << 4095

kouhos = [[0, 0]]
count = 4095
while K > 0:
    next_kouho = set()
    for kouho in kouhos:
        P, Q = kouho
        p = P | K
        q = Q | K
        if X & K:
            if p * Q <= N:
                next_kouho.add((p, Q))
            if P * q <= N:
                next_kouho.add((P, q))
        else:
            if p * q <= N:
                next_kouho.add((p, q))
            else:
                next_kouho.add((P, Q))
    assert len(next_kouho) > 0

    kouhos = []
    for n in next_kouho:
        P, Q = n
        p = P | (K - 1)
        q = Q | (K - 1)
        if p * q >= N and P * Q <= N:
            kouhos.append(n)

    print(count, len(kouhos))
    count -= 1
    K >>= 1

print(kouhos)

あとはやるだけです。

exec(open("primes").read())
exec(open("flag.enc").read())

from Crypto.Util.number import *

print(len(primes))
for prime in primes:
    p, q = prime
    phi = (p - 1) * (q - 1)
    d = inverse(E, phi)
    m = pow(C, d, N)
    print(long_to_bytes(m))

フラグは TSGCTF{Absolutely, X should be 'S' in 'OPQRX'.} でした。