2019-09-03

TokyoWesterns CTF 5th 2019 Writeup

TokyoWesterns CTF 5th 2019にチーム./Vespiaryとして参加して、正の点数を入れた53位/1005チーム、日本国内のチームに限れば4位/131チームでした。以下はそのWriteupになります。

Challenges

challenges	genre	score
real-baby-rsa	Crypto	40
Simple Logic	Crypto	95
Happy!	Crypto	242

見ての通りCryptoしか解いてません、CryptoジャンルでRevとの複合問題以外は全部解けたので満足しています。

real-baby-rsa

RSA暗号による暗号化をフラグに対し1文字ずつ施したものが与えられる。
もちろん公開鍵である $e, N$ は与えられている。というわけでprintableな文字を片っ端から暗号化したものを辞書として持ち与えられた暗号文に対し照合を行って各文字を復元し、それをつなげればフラグとなる。

使用コード

import string


if __name__ == '__main__':
    # "pubkey"
    N = 36239973541558932215768154398027510542999295460598793991863043974317503405132258743580804101986195705838099875086956063357178601077684772324064096356684008573295186622116931603804539480260180369510754948354952843990891989516977978839158915835381010468654190434058825525303974958222956513586121683284362090515808508044283236502801777575604829177236616682941566165356433922623572630453807517714014758581695760621278985339321003215237271785789328502527807304614754314937458797885837846005142762002103727753034387997014140695908371141458803486809615038309524628617159265412467046813293232560959236865127539835290549091
    e = 65537

    flag = ""

    # list up
    with open("output") as f:
        c_list = [int(c.strip()) for c in f.readlines()]

    print(c_list)

    char_dic = {}
    for char in string.printable:
        c_char = pow(ord(char), e, N)
        char_dic[c_char] = char

    for c in c_list:
        flag += char_dic[c]

    print(flag)

Flag

TWCTF{padding_is_important}

Simple Logic

フラグを下記に示すアルゴリズムで暗号化したものと別の平文- 暗号文ペアが6つ与えられる。
また、暗号化のアルゴリズムは鍵 $key$ と平文 $plain$ に対し $(plain + key) \oplus key$ を765回行うことである。
ここで、暗号化の処理の中では、平文の最下位のバイト(下位8ビット)は下の位からの繰り上がりが無いことから256通りの総当りを行って6つのペアで比較することで鍵の最下位バイトを推測(いくつか候補があるため確定ではない)することができる。
鍵の下位2バイト(下位16ビット)は鍵の下位 $i$ バイト目を $key_i$ とおくと $key_2 \times 256 +key_1$ のようになる。これによって下位2バイトまでの鍵の候補は下位1バイトの鍵候補数(ちなみにこれは2通り) * 256通りである。これを下位2バイトに対して総当りすることでまた鍵の候補を手に入れることができる。
これを下位3バイト(下位24ビット)に対しても同様に行い、以下同様にして16バイト分の鍵の候補を導出したものを復号アルゴリズムに適用してフラグを導出することができる。

使用コード

def encrypt(msg, key, bits):
    mask = (1 << bits) - 1
    enc = msg
    for _ in range(765):
        enc = (enc + key) & mask
        enc = enc ^ key
    return enc


def decrypt(msg, key, bits):
    mask = (1 << bits) - 1
    enc = msg
    for _ in range(765):
        enc = enc ^ key
        enc = (enc - key) & mask
    return enc


def all_pairs_check(pairs, key, bits):
    mask = (1 << bits) - 1
    for pair in pairs:
        if encrypt(pair['plain'], key, bits) != (pair['enc'] & mask):
            return False

    return True


if __name__ == '__main__':
    enc_flag = 0x43713622de24d04b9c05395bb753d437
    _list = [
        {'plain': 0x29abc13947b5373b86a1dc1d423807a, 'enc': 0xb36b6b62a7e685bd1158744662c5d04a},
        {'plain': 0xeeb83b72d3336a80a853bf9c61d6f254, 'enc': 0x614d86b5b6653cdc8f33368c41e99254},
        {'plain': 0x7a0e5ffc7208f978b81475201fbeb3a0, 'enc': 0x292a7ff7f12b4e21db00e593246be5a0},
        {'plain': 0xc464714f5cdce458f32608f8b5e2002e, 'enc': 0x64f930da37d494c634fa22a609342ffe},
        {'plain': 0xf944aaccf6779a65e8ba74795da3c41d, 'enc': 0xaa3825e62d053fb0eb8e7e2621dabfe7},
        {'plain': 0x552682756304d662fa18e624b09b2ac5, 'enc': 0xf2ffdf4beb933681844c70190ecf60bf}
    ]

    bits = 128
    key = 0
    candidate_keys = [0]

    for _bytes in range(bits // 8):
        _bits = _bytes * 8
        current_candidate_keys = []
        for byte_key in range(256):
            for candidate_key in candidate_keys:
                _key = candidate_key + byte_key * (2 ** _bits)
                if all_pairs_check(_list, _key, (_bytes + 1) * 8):
                    current_candidate_keys.append(_key)

        candidate_keys = [x for x in current_candidate_keys]

    print("[+]: candidate_keys -> {}".format(list(map(lambda x: hex(x), candidate_keys))))

    for key in candidate_keys:
        print("[+]: flag is here -> TWCTF{{{}}}".format(hex(decrypt(enc_flag, key, bits))[2:]))

Flag

TWCTF{ade4850ad48b8d21fa7dae86b842466d}

Happy!

CRT-RSAの問題。普通のCRT-RSAと違うのは公開鍵 $N$ の生成に外部から与えたパラメータ $k$ を用いて $N = pq^{k}$ としているところである。
また、ソースコードによれば $p,q$ のビット数は700以上であり、 $N$ のビット数が2295bitであったことから $p,q$ のビット数は765bitであると推測され、同時に $k= 2$ であることも推測される。以下ではこの推測に基づいて考える。
この問題では公開鍵の保存方法に問題があり、秘密鍵である $cf := p^{-1} \mod q^{k}$ が漏れてしまっている。これを利用して $N, cf$ から $p,q$ を求めることを考える。
$cf \equiv p^{-1} \mod q^{k}$ であるから両辺に $p$ を掛けると $p \cdot cf \equiv 1 \mod q^{k}$ である。これを合同式を使わずに表すと整数 $l$ を用いて $p \cdot cf = 1 + lq^{k}$ 。
これに更に両辺に $p$ を掛け、 $N = pq^{k}$ を用いると $p^{2} \cdot cf = p + ln$ である。これを合同式にすると $p^{2} \cdot cf - p \equiv 0 \mod n$ 。
$\mod n$ 上での $cf^{-1}$ はEuclid互除法を用いることで求めることができるのでこれを求め、先程の合同式の両辺に掛けると $p^{2} - p \cdot cf^{-1} \equiv 0 \mod n$ となる。
$p$ を解とするモニック合同方程式の形に持ち込むことができたのでCoppersmith's Theoremを利用することを考える。この方程式は2次なので $|p| \lt N^{1/2}$ であれば良く、 $p, N$ のビット数よりこれは満たされている。
SageMathを用いて $p$ が求まるので後は $q = \sqrt{N/ p}$ を求め、与えられたソースコードの $p,q$ を上書きし復号すればフラグが出現する。使用するコマンドは

> ruby happy keygen 765 2 prikey pubkey
> ruby happy decrypt prikey flag.enc output

使用コード

sage: n = 5452318773620154613572502669913080727339917760196646730652258556145398937256752632887555812737783373177353194432136071770417979324393263857781686277601413222025718171529583036919918011865659343346014570936822522629937049429335236497295742667600448744568785484756006127827416640477334307947919462834229613581880109765730148235236895292544500644206990455843770003104212381715712438639535055758354549980537386992998458659247267900481624843632733660905364361623292713318244751154245275273626636275353542053068704371642619745495065026372136566314951936609049754720223393857083115230045986813313700617859091898623345607326632849260775745046701800076472162843326078037832455202509171395600120638911
sage: cf = 25895436290109491245101531425889639027975222438101136560069483392652360882638128551753089068088836092997653443539010850513513345731351755050869585867372758989503310550889044437562615852831901962404615732967948739458458871809980240507942550191679140865230350818204637158480970417486015745968144497190368319745738055768539323638032585508830680271618024843807412695197298088154193030964621282487334463994562290990124211491040392961841681386221639304429670174693151
sage: K = Zmod(n)
sage: PR.<x> = Polynomialring(K)
sage: cf_inv = xgcd(cf, n)[1]
sage: cf_inv  -2249345702092523066854742350215149116416859677618194270409191492480933128500527239002357382040286220628542908633760619718020318862762179160313205310065653124053891797903672229971967453188884376088470963333006057687741241573722015848262880741528030132669466984038867943213123080605122134845253150074165551805580583789437805883858045929618356220833327713859151787929015040819461870240823640707071318502251137747082685885265753285753429622655389962762875765839373176940943904189083878886577385177994761666798781194931165369158189904098832117847743192922856376144912379516797927684252737181470545077929510269532122946061866421139568441244990499842647843345736439336484949373015531153085847596295
sage: cf_inv += n
sage: f = x^2 - cf_inv * x
# ここsmall_rootsのパラメータいじれば(確かbetaっていう名前だった気が)0を検出せずに済みそう
sage: f.small_roots(X=2^765)
[0,  166878663790065040663149504970052368124427462024107500159158464138407657299730521908976684364578086644682045134207945137293534705688910696520830729908263578233018529387676221035298300775812585471932551347478303730822844748034186479]
sage: p = 166878663790065040663149504970052368124427462024107500159158464138407657299730521908976684364578086644682045134207945137293534705688910696520830729908263578233018529387676221035298300775812585471932551347478303730822844748034186479

以下、qを求めて復号するだけなので略

Flag

TWCTF{I_m_not_sad__I_m_happy_always}

感想

難易度が高い問題が多く、最近の学生向けCTFに出ていた時とは違った感覚で楽しむことができました。特にHappy!はRSAの既存の攻撃方法に加えて数学的な側面も求められる問題で非常に楽しかったです。
反省点としてはHappy!を解いた時点で解ける問題が無く(pwnもrevも苦手、というかチームメイトに任せきりで触ったことが無い)長い時間手持ち無沙汰になってしまったことです。これを機に低レイヤーに触れていきたいと思っています(これ毎回言ってる気がする)。
最後になりますが、このような楽しいCTFを開いてくださったTokyoWesternsの皆様、本当にありがとうございました。

2019-08-15

InterKosenCTF Writeup

InterKosenCTF_2019

2019年8月11日から8月12日にかけて開催されたInterKosenCTFにチーム./vespiaryで参加しました。順位は得点を入れたチームに限定すると4位/91チームでした。
チームメイトが低レイヤー(Pwn, Rev)を並行してやってくれたのと私が寝てる間にWebを全部解いてくれたおかげで満足行く順位に達せました。
この記事以外にもGitHubにもソースコード付きでWriteupをあげています。
なお、公式の皆さんが全問Writeupを書いています(https://hackmd.io/@theoldmoon0602/H1QJUrgVr)

Challenges

challenges	genre	score
Hugtto!	Forensics	238
Kurukuru Shuffle	Crypto	200
Temple of Time	Forensics	285
Lost World	Forensics	303
Pascal Homomorphicity	Crypto	333
saferm	Forensics	434

Hugtto! (InterKosenCTF)

既存のツールを使うだけで解決するようなStegoでは無く独自形式のStego。埋め込む色はランダムで決定するが問題のソースを読むとシード値がコード実行時の時間だったのでファイルが作成された時間から少しずつずらすことで正しいシードを使うことができると思われる。

score	genre
238	Forensics

添付ファイル

steg.py: steganographyを行うファイル
steg_emiru.png: steg.pyによって生成された画像ファイル

手順

乱数によって画素のどの色に情報を仕込むか決まるがその仕込み方は r = (r & 0xFE) | bin_flag[i % len(bin_flag)] のように一定(rは赤色、gは緑色、bは青色に関する値が入っている)
ここで8bit整数と0xFEの論理積を取るとこの整数は末尾1桁が0になる。
また、bin_flag[i]は0か1であるので上記値は0|0 = 0か0|1 = 1となりbin_flag[i]の値に依存する
従ってどの色に仕込まれたのかさえ判明すればbin_flag[i]の値を復元可能。復元方法は単純に色の値の最下位ビットの偶奇である
random.seed(int(datetime.now().timestamp()))よりこのファイルが作られる直前の時刻をシードとして乱数を生成していることからファイル生成時刻のUNIX時間、int(datetime(2019, 8, 6, 11, 44, 18).timestamp())からこれより少し小さい値をシードとして乱数を生成するとこのファイルが作られた時と同じ埋め込み方が可能だと考えられる
1秒ずつ早い時間にしていったところ3秒早い時刻で復号したところフラグのようなものが表示された

使用コード

from PIL import Image
from datetime import datetime
import random
 
 
def bit_array_to_string(bit_array):
    try:
        if len(bit_array) != 8:
            raise ValueError("argument 'bit_array' must be 8 length" )
    except ValueError as e:
        print(e)

    bit_str = "".join(list(map(str, bit_array)))
    return chr(int(bit_str, 2))
 
 
if __name__ == '__main__':
    img = Image.open("./steg_emiru.png")
    new_img = Image.new("RGB", img.size)

    w, h = img.size
    # 誤差が1sぐらいあるかもしれない
    seed_time = int(datetime(2019, 8, 6, 11, 44, 15).timestamp())
    print(seed_time)
    random.seed(seed_time)
 
    i = 0
    bit_array = []
    current_bit_array = []
    for x in range(w):
        for y in range(h):
            r, g, b = img.getpixel((x, y))
            rnd = random.randint(0, 2)
            if rnd == 0:
                current_bit_array.append(r % 2)
            elif rnd == 1:
                current_bit_array.append(g % 2)
            elif rnd == 2:
                current_bit_array.append(b % 2)
            i += 1
            if i % 8 == 0:
                bit_array.append(current_bit_array)
                current_bit_array = []

    str_arr = []
    for i, arr in enumerate(bit_array):
        if i < 100:
            str_arr.append(bit_array_to_string(list(reversed(arr))))

    print("".join(str_arr))

Flag

KosenCTF{Her_name_is_EMIRU_AISAKI_who_is_appeared_in_Hugtto!PreCure}

KuruKuru Shuffle

3つのパラメータa, b, kによって文字数回分の転置規則(何回目にどの文字とどの文字を転置するか)が定まる。これらのパラメータはどれもrange(len(flag))の範囲内であるため、全通り考えたとしても高々10万通りとちょっと。よって総当りが可能でると考えられる。

score	genre
200	Crypto

添付ファイル

shuffle.py: 暗号化する際のソースコード
encrypted: 暗号化されたファイル

手順

各パラメータ毎にどの文字とどの文字を何回目で置換するかを配列で格納する
各転置規則に対してそれを逆順に実行して復号を行う
復号結果にKosenCTF{を含むかを確認する

使用コード

from copy import copy
 
 
def make_st_list(a, b, k, L):
    _list = []
    i = k
    for _ in range(L):
        s = (i + a) % L
        t = (i + b) % L
        i = (i + k) % L
        _list.append([s, t])

    return _list
 
 
def dec(_enc_list, _st_list):
    for _ in range(len(_st_list)):
        st = _st_list.pop()
        s = st[0]
        t = st[1]
        _enc_list[s], _enc_list[t] = _enc_list[t], _enc_list[s]

    return "".join(_enc_list)
 
 
if __name__ == '__main__':
    enc = "1m__s4sk_s3np41m1r_836lly_cut3_34799u14}1osenCTF{5sKm"
    L = len(enc)

    enc_list = list(enc)

    for a in range(L):
        for b in range(L):
            for k in range(1, L):
                st_list = make_st_list(a, b, k, L)
                tmp_enc_list = copy(enc_list)
                dec_str = dec(tmp_enc_list, st_list)
                if dec_str[0:9] == "KosenCTF{":
                    print(dec_str)

Flag

KosenCTF{us4m1m1_m4sk_s3np41_1s_r34lly_cut3_38769915}

Lost World

vdiを渡されそれをVirtualbox等で読み込ませるとログインパスワードを要求される。ログインパスワード自体を入手するのは骨が折れそうなので内部の暗号化されたログイン情報が入っている/etc/shadowを書き換えてログインできるようにする。なお、フラグ自体はログイン成功時のメッセージに入っているらしくログインに成功した後にdmesg | grep KosenCTF{で抽出が可能。

score	genre
303	Forensics

添付ファイル

ディスクイメージ(.vdi)

手順

下記参考文献に従ってroot:でヒットする箇所をこちらで用意した鍵に置き換える(今回は下記参考文献の物を流用したが、皆さんがお使いのLinuxの/etc/shadowを流用して問題ないと思われる)
VirtualBoxで書き換え後のイメージを読み込み、起動
用意したパスワードを入力しdmesg | grep KosenCTF{をしてフラグを入手

Flag

KosenCTF{u_c4n_r3s3t_r00t_p4ssw0rd_1n_VM}

参考文献

write-ups/Hack.lu CTF 2015/Dr.Bob https://github.com/RandomsCTF/write-ups/tree/master/Hack.lu%20CTF%202015/Dr.%20Bob%20%5Bforensics%5D%20(150)

補足

後から運営の皆さんのTwitterを見て知ったのだが次のような非想定解があったらしい

lost worldはフラグを出力してるのがカーネルモジュールだから一回起動するとkern.logに記録されてstringsで解けるのか。bashrcとかに書くと取り出して解析する人が出そうだからカーネルモジュールにしたのが裏目に出たな...... #InterKosenCTF
— ptr-yudai (@ptrYudai) August 13, 2019

pascal homomorphicity

Paillier暗号で使われている合同式を利用した問題。最初にフラグを暗号化した数字が表示されその後ユーザー入力で渡された数字を暗号化する。求めるKeyが指数となっているが、nが判明しているなら、剰余を考えると離散対数問題を解かなくてもkeyを求めることができる。nはこちらからの入力によって求めることができるのでそれを利用すれば良い。

score	genre
333	Crypto

添付ファイル

サーバー側で動いてるコード

方針

二項定理より $(1+n)^ k \equiv 1 + kn \mod n^ 2$ であることがわかる。これを使えば $1 + kn \lt n^ 2$ である時に $(1+n)^ k$ と $n$ がわかっていれば $k$ を求めることができる(逆も同様)。
今回のプログラムではサーバー側に小さい数字を渡すと、警告と共に $key$ の長さを教えてくれて、 $key \lt n$ であったことから $1 + kn \lt n^ 2$ の条件が適用されるので剰余を考慮しなくても解くことができる。

手順

鯖に接続するとpow(1 + n, key, n**2)が表示される
数値を入力するとpow(1 + n, int(input), n**2)が表示されるので $(1+n)^ k \equiv 1 + kn \mod n^ 2$ を利用しnを導出する
nが求まったので最初に表示されたpow(1 + n, key, n**2)からkeyを導出できる

当然ながらPythonを利用して解きましたがPythonターミナル上で全てを行ったので使用コードはありません。

Flag

KosenCTF{Th15_15_t00_we4k_p41ll1er_crypt05y5tem}

参考文献

Paillier暗号 - Wikipedia: https://ja.wikipedia.org/wiki/Paillier%E6%9A%97%E5%8F%B7

saferm

最初Forensics(ディスクダンプの解析), 中盤Rev(抽出したバイナリの解析), 終盤Forensics(Zipのファイル構造から複合キーを割り出す)の3段構え複合問題。Revパートについてはチームメイトが秒殺してくれたので説明を割愛。

score	genre
434	Forensics, Reversing

添付ファイル

ディスクダンプ

手順

FTK Imagerにこのイメージを読ませるとsafermというバイナリと削除されたdocument.zipというファイルが見つかる
safermをリバーシングすると(ここはチームメイトがやってくれた、感謝)、64bitのキーを用いて暗号化(encrypted[index] = file[index] ^ key[index % 64])してから元のファイルを削除していることがわかる。
FTK Imagerは削除済みのファイルも吸い出せるので唯一削除済みと表示されたファイルであるdocument.zipを抽出する。
ここでzipファイルのシグネチャは頭4バイトは確定しており残りの4バイトもバージョン情報(単にdeflate圧縮であれば14 00)と圧縮形式ごとに用いる特殊ビット(特にオプション指定が無ければ00 00)であることから容易に候補を絞ることができる
※この候補を絞る過程ではファイル名がdocument.pdfであるという仮定も用いた
これにより幾つかキーの候補を絞り復号化を行うとあるキーでzipが開くことができ、中に入っていたdocument.pdfを見るとフラグが(但し、手元のアーカイバでは開かずチームメイトが使っているツールでは開くことができた、感謝)
※公式Writeupによれば暗号化の際、末尾の64bitに満たない部分は暗号化されないのでここだけ元のバイト列のままで良いらしい

使用コード

過去に出場したCTFでXORによる暗号化を実装していたので(https://github.com/Xornet-Euphoria/HSCTF_6/tree/master/Hidden_Flag)キーを変えて流用

if __name__ == '__main__':
    key = [46, 87, 173, 46, 255, 200, 202, 73]
    f = open('document.zip', 'rb')
    enc_bytes = f.read()
    f.close()

    f = open('dec.zip', 'wb')
    for i, byte in enumerate(enc_bytes):
        f.write((int(byte) ^ key[i % len(key)]).to_bytes(1, 'big'))

    f.close()

Flag

KosenCTF{p00r_shr3dd3r}

補足

公式Writeupによればディスクダンプの解析にThe Sleuth Kitというものを使っていた。復習時に使ってみたところ、割と使いやすかったので今後はこのような解析をする際に頻繁に使っていきたい

Temple of Time

ForensicsメインだがWebの知識も要求される複合問題。前述のsafermもそうだが強引な複合問題では無く非常に良問だった。
パケットを解析するとどうやらSQLインジェクションの痕跡が見える。それもTime-BasedのブラインドSQLインジェクションだと思われる。攻撃者は1文字ずつ情報を探索しているので調査している文字が切り替わったタイミングのパケットを読めば攻撃者が判明させた文字がわかる。

score	genre
285	Forensics, Web

添付ファイル

pcapng

手順

Wiresharkにpcapngを読ませ、プロトコルをHTTPに絞る
GET /index.php?portal=%27OR%28SELECT%28IF%28ORD%28SUBSTR%28%28SELECT+password+FROM+Users+WHERE+username%3D%27admin%27%29%2C1%2C1%29%29%3D48%2CSLEEP%281%29%2C%27%27%29%29%29%23 HTTP/1.1というリクエストからTime-Based SQL injectionを行っているように思われる
なお、これをデコードすると GET /index.php?portal='OR(SELECT(IF(ORD(SUBSTR((SELECT+password+FROM+Users+WHERE+username='admin'),1,1))=48,SLEEP(1),'')))# HTTP/1.1 であることからこれは1文字目が文字コードで48('0')であるかを判定していると思われる
該当パケットを解析しやすいようにCSV形式で出力する
IFの条件はusernameがadminのレコードのpasswordのある位置の文字コードがn(上記例では48)であるかであり、このnをパケットを送るごとに1ずつ変化させている
SUBSTRの引数に注目するとあるパケットとパケットの間で引数が変わっているが、この代わり目である位置の文字コードが判明したことになるのでそこのパケットを抽出する
抽出したパケットから文字コードの部分を読んで文字に戻し、繋げるとフラグが現れる

使用コード

ここでは5. の抽出だけ行いフラグの復旧は人力で行ったので割愛、6.も自動化した方がWriteupとして見栄えが良かったと反省

import csv
 
if __name__ == '__main__':
    payloads = []
    with open('export.csv') as f:
        reader = csv.reader(f)
        for row in reader:
            payload = row[6]
            if payload[0:10] == "GET /index":
                payloads.append(payload)
 
    index = 1
    for j, payload in enumerate(payloads):
        search_word = "GET /index.php?portal=%27OR%28SELECT%28IF%28ORD%28SUBSTR%28%28SELECT+password+FROM+Users+WHERE+username%3D%27admin%27%29%2C" + str(index)
        if search_word not in payload:
            print(payloads[j - 1])
            index += 1

Flag

KosenCTF{t1m3_b4s3d_4tt4ck_v31ls_1t}

感想

2ヶ月ぶりのCTFということと寝不足もあり開始6時間ぐらいはゴミみたいなミス(コードの文法エラー等)を繰り返して絶望していましたが、Temple of Timeのようなmedium問が解けた辺りから楽しくなり全体を通して良いCTFでした。作問者の方が色々なCTFで上位に入賞しているということもあり少なくとも自分が解いた問題に関しては解きづらい(≠難しい)問題は無く全体的に良問が多かったです。
冬にも同じ運営で難易度の高いCTFを開催するらしいので精進してまた参加したいです。

自身の課題として、ツールで解決できるところを人力でやったり、低レイヤーを全部チームメイトに任せたりと色々残りましたが、本当に良いCTFでした。運営の皆さん、本当にありがとうございました。