https://hiikunz.hatenablog.com/entry/SECCON-13-Finals

parabola0149 さん・st98 さん・mora さんとチーム BunkyoWesterns として参加しました。

参加の経緯は st98 さんのブログを参照してください。

自分が得意な傾向の問題が多く出題され、チームメンバーの皆さんが強かったのもあって優勝できました。

SECCON CTF 13 Domestic Finalsで優勝しました！#SECCON #CTF #文京区 pic.twitter.com/dBv370BxL6
— BunkyoWesterns (@BunkyoWesterns) March 3, 2025

参加記 + WriteUp を書きます。なお、WriteUp を書くにあたり一部の問題の解法/ソルバーを説明しやすいようにリファクタリングしています。

Day 0

会場のネットワークに接続するのに必要と言われた LAN ケーブル、そして LAN-USB の変換ケーブルを買いました。*1

Day 1

起床〜競技開始

大事な大会なので、遅刻しないように早めに出発したら、受付開始 30 分前ぐらいに着いてしまいました。既にどこかの海外勢と思われる方がいました。国内では到着 First Blood だったっぽいです。

受付開始時間になっても特になにかがあるわけでもなく、人々が自分のチームの席に向かっていったので従いました。

アルパカと kurenaif さんのパネルがありました。

もふもふのかわいいアルパカとちょっとだけ写っている kurenaif さんのパネル

開始直前に、Hardware 問題で使うであろう機材が配られました。

競技開始

まずは Welcome を通します(First Blood でした)。そして、King of the Hill (以降 KotH) の問題が 2 問あるのを確認しました。「HECCON」はCrypto、「Allegro」は Reversing + 競プロのような見た目をしていたので、「HECCON」を隣にいた parabola0149 さんに任せて mora さんと「Allegro」を担当することにしました。

あと、得点のビジュアライザがかっこよかったです。

Allegro phase 1

この KotH の概要は、次の通りでした。

コンパイルされた実行ファイル (実行がすごく遅い) が与えられるので、同じ挙動をするより早い実行ファイルを提出してください。
だいたい 30 分おきにテストケースが強くなっていきます。
5 分おきに評価され、各評価時点での 1 位に 20pts, 2 位に 16pts, 3 位に 12 pts, 4 位に 9 pts ... 入ります。

各フェーズで、最初に順位表を掲載してからやったことの解説をしていきます。順位表の色は、緑が Success、赤が Wrong Output、黄色が Timeout です。

まずは与えられたファイルを Reversing する必要があったので、正面にいた mora さんに~~丸投げ~~お任せしてルールを読んでいました。そのうちに mora さんは実行ファイルに意味なく入っていた sleep を消すなど自明な改善をしてくれていました。(Tick: 4〜)

挙動を理解してからが私の仕事です。どうやら次の関数 $f(n)$ を $\bmod 2^{64}$ で計算するプログラムのようです。

$f(n) = \begin{cases} 1 & (n = 0,1,2) \\ f(n-3) + f(n-2) - f(n-1) + n & (3 \leq n) \end{cases}$

とりあえず私が考察している間にテストケースが強くなってしまったので、mora さんが再帰関数をメモ化したやつを提出してくれました。(Tick: 10〜)

そんなこんなで自分は yosupo judge の問題の提出をパクって線形漸化式を求めました。

$f(n) = f(n-1) + 2 \cdot f(n-2) - 2 \cdot f(n-3) - f(n-4) + f(n-5)$

ということで行列累乗を実装して提出すると、不正解扱いになりました。なんで… (Tick: 13〜)

mora さんが「最後に改行してないからでは?」と教えてくれて、修正したら正解判定になりました。(Tick: 16〜)

その後、実は簡易的な正誤判定スクリプトが問題と一緒に配布されてたことを知りました。もったいないことをした…

Allegro phase 2

ここからは Reversing の難易度も上がっていくようです。

入力の CRC32 hash を 1 バイトずつ計算するプログラムのようです。

とりあえず mora さんが _mm_crc32_u8 関数を使って書いてくれました。(Tick: 27〜)

バグらせながらも入力を高速化してもらい (Tick: 32〜)、さらに私が _mm_crc32_u64 を使えば 8 ビットずつ計算できることに気づいて高速化できました。 (Tick: 39〜)

組み込み命令が私の mac で動かないので、この辺から実装 / コンパイルを mora さんに丸投げするようになっていきます。

RSA+

Allegro の phase 2 は割と mora さんがやってくれていたので、暇なうちに Jeopardy の問題に取り組むことにしました。

とりあえず正解が出ていた RSA+ に挑戦することにしました。

import os
import signal
from secrets import randbelow

from Crypto.Util.number import isPrime

flag = os.getenv("FLAG", "SECCON{this_is_not_a_flag}")


if __name__ == "__main__":
    signal.alarm(120)

    p = int(input("Your favorite prime p (hex) > "), 16)
    if not isPrime(p) and p.bit_length() >= 512:
        print("p must be a prime")
        exit()
    q = int(input("Your favorite prime q (hex) > "), 16)
    if not isPrime(q) and q.bit_length() >= 512:
        print("q must be a prime")
        exit()
    n = p * q

    g = n // 2
    h = n // 3
    x = randbelow(2**512)
    r = (pow(x, g, n) + pow(x, h, n)) % n
    print(f"{r = }")

    guess_x = int(input("Guess x > "))
    if x == guess_x:
        print(flag)
    else:
        print("Wrong...")

512 bit 未満の素数 $p,q$ が指定できる*2ので、 $n=pq, g = \left\lfloor \frac{n}{2} \right\rfloor, h = \left\lfloor \frac{n}{3} \right\rfloor$ として、 $r = x^{g} + x^{h} \bmod n$ から $x$ (512 bit 乱数)を復元せよという問題です。

片方の項がなければただの RSA 暗号だなぁ〜、という気持ちになります。

また $p,q$ の下限チェックがないので $2,3$ あたりを入れるんじゃないかな〜、という気持ちにもなります。

結論から書くと、 $p \equiv 1 \pmod{3}, q = 2$ のとき、

$\varphi(n) = p - 1, h = \left\lfloor \frac{n}{3} \right\rfloor = \frac{2(p - 1)}{3}$ となって $h = \frac{2}{3} \cdot \varphi(n)$ となります。

すると、 $(x^g)^3 \equiv x^{3g} \equiv x^{2 \cdot \varphi(n)} \equiv (x^{\varphi(n)})^2 \equiv 1 \pmod{n}$ なので $x^g$ は $\bmod n$ における $1$ の $3$ 乗根です。

実験すると、そこそこの確率で $x^g \equiv 1 \pmod{n}$ なので、 $1$ だと決めつけてもそこそこの確率で解くことができました。

from Crypto.Util.number import isPrime
from pwn import *

io = process(['python3', 'server.py'])
# io = remote('rsaplus.dom.seccon.games', 11337)

p = 2 ** 511
while not isPrime(p) or p % 3 != 1:
    p -= 1
q = 2
n = p * q
io.sendlineafter(b'> ', hex(p)[2:].encode())
io.sendlineafter(b'> ', hex(q)[2:].encode())
r = int(io.recvline().strip().split(b' = ')[1])

print(f"p = {p}")
print(f"q = {q}")
print(f"r = {r}")

g = n // 2
h = n // 3

d = pow(g, -1, (p - 1) * (q - 1))
x = pow(r - 1, d, n)

io.sendline(str(x).encode())
io.interactive()

flag: SECCON{R4d1c4lly_Sum_i5_Ab5urd}

DLP+

その後 Allegro の phase 3 が始まりましたが、競プロ要素はなさそうだったので RSA+ と似たタイトルの DLP+ に挑戦することにしました。

import os
import signal
from secrets import randbelow

from Crypto.Util.number import isPrime

flag = os.getenv("FLAG", "SECCON{this_is_not_a_flag}")


if __name__ == "__main__":
    signal.alarm(120)

    p = int(input("Your favorite prime (hex) > "), 16)
    if not isPrime(p):
        print("p must be a prime")
        exit()

    g = p // 2
    h = p // 3
    x = randbelow(2**512)
    r = (pow(g, x, p) + pow(h, x, p)) % p
    print(f"{r = }")

    guess_x = int(input("Guess x > "))
    if x == guess_x:
        print(flag)
    else:
        print("Wrong...")

任意の素数 $p$ が指定できるので、 $g= \left\lfloor \frac{p}{2} \right\rfloor, h = \left\lfloor \frac{p}{3} \right\rfloor$ として、 $r = g^{x} + h^{x} \bmod p$ から $x$ (512 bit 乱数)を復元せよという問題です。

とりあえずまた片方の項の候補を減らしたい気持ちになります。

$g^k \equiv 1 \pmod{p}$ または $h^k \equiv 1 \pmod{p}$ が小さめの $k$ で成り立ってくれると候補が $k$ 通りに絞れて嬉しそうです。

$p$ が $3$ 以上の素数のとき、次のように変形できます。

\begin{align} g^k \equiv 1 \pmod{p} \\ \left( \left\lfloor \frac{p}{2} \right\rfloor\right)^k \equiv 1 \pmod{p} \\ \left(\frac{p-1}{2} \right)^k \equiv 1 \pmod{p} \\ \left(\frac{-1}{2} \right)^k \equiv 1 \pmod{p} \\ (-1)^k \equiv 2^k \pmod{p} \\ 2^k - (-1)^k \equiv 0 \pmod{p} \end{align}

$k$ が偶数のとき、 $p = 2^k - 1$ だと嬉しそうです。これはメルセンヌ素数の形です。…なのですが、 $k$ が偶数のとき $p = 2^k - 1$ は素数になりません (証明略)。ただ $k$ が偶数の方が嬉しそうなので $k = 2l$ とおいてもう少し式変形してみましょう。

\begin{align} 2^k - (-1)^k \equiv 0 \pmod{p} \\ 2^{2l} - 1 \equiv 0 \pmod{p} \\ (2^l - 1)(2^l + 1) \equiv 0 \pmod{p} \end{align}

ということで、 $p = 2^l - 1$ のとき、 $g^{2l} \equiv 0 \pmod{p}$ となって $g^x \equiv 0 \bmod p$ の候補を $2l$ 通りにできます。

$p = 2^{2281} - 1$ のとき、 $\mathrm{order}(p) = p - 1$ に小さい素因数がいっぱいあるので、Pohlig–Hellman 法で 512 bit 分ぐらいの情報は得られそうです。

ただ、今度は $g^{x} \bmod p$ の候補が $4562$ 個になってしまい、これらに対して 1 つずつ Pohlig–Hellman 法を実行する時間はありません。

ここで、以下の性質を用います。

$p = 2^l - 1$ が素数であるとき、 $\mathrm{order}(p) = p - 1$ は $l$ で割り切れる (証明略)。

すると、Pohlig–Hellman 法の一部を応用すれば $x \bmod 2l$ の候補をさらにいい感じに絞ることができます。(詳細はコードを読んでください)

from pwn import *

io = process(["python3", "server.py"])
# io = remote("dlpplus.dom.seccon.games", 13337)

l = 2281
p = 2 ^ l - 1
assert is_prime(p)
g = p // 2
h = p // 3


# p-1 の小さい素因数 (の一部)
factors = [5, 7, 11, 13, 17, 31, 41, 61, 151, 191, 229, 241, 331, 457, 571, 761, 1217, 1321, 2281, 4561, 32377, 54721, 61681, 90289, 131101, 148961, 160969, 174763, 185821, 247381, 524287, 525313, 1101811, 1212847, 160465489, 420778751, 3996146881, 4562284561, 9036489073, 30327152671, 275415303169]

# 十分な情報が得られることを確認
fmul = 1
for f in factors:
    fmul *= f
assert fmul > 2 ^ 512

io.recvuntil(b"Your favorite prime (hex) > ")
io.sendline(hex(p)[2:].encode())
r = int(io.recvline().strip().split(b" = ")[1])


# https://tex2e.github.io/blog/crypto/DLP を借りた

# Baby-step Giant-step法
def babystep_giantstep(g, y, p, q=None):
    if q is None:
        q = p - 1
    m = int(q**0.5 + 0.5)
    # Baby step
    table = {}
    gr = 1  # g^r
    for r in range(m):
        table[gr] = r
        gr = (gr * g) % p
    # Giant step
    try:
        gm = pow(g, -m, p)  # gm = g^{-m}
    except:
        return None
    ygqm = y                # ygqm = y * g^{-qm}
    for q in range(m):
        if ygqm in table:   # 左辺と右辺が一致するとき
            return q * m + table[ygqm]
        ygqm = (ygqm * gm) % p
    return None

# Pohlig–Hellman法
def pohlig_hellman_DLP(g, y, p):
    crt_moduli = []
    crt_remain = []
    # for q, _ in factor(p-1):
    for q in factors: # ここだけもとのコードと置き換えた
        x = babystep_giantstep(pow(g,(p-1)//q,p), pow(y,(p-1)//q,p), p, q)
        if (x is None) or (x <= 1):
            continue
        crt_moduli.append(q)
        crt_remain.append(x)
    x = crt(crt_remain, crt_moduli)
    return x



assert (p - 1) % l == 0

e = (p - 1) // l

for i in range(0, l * 2):
    a = pow(g, i, p)
    r_ = pow(r - a, e, p)
    g_ = pow(h, e, p)
    if pow(g_, i, p) == r_ % p:
        x = pohlig_hellman_DLP(h, (r - a) % p, p)
        if (pow(g, x, p) + pow(h, x, p)) % p == r % p:
            print(x)
            break

io.recvuntil(b"Guess x > ")
io.sendline(str(x).encode())
print(io.recvline())

flag: SECCON{y37_4n07h3r_4bn0rm4l_pr1m35}

解けはしましたが、解けた頃にはこの日は終盤で、もうすぐ KotH だけが休みになる長い夜が始まろうとしていました。現状国内部門でこの問題が解けているのは私だけです。ここでこの問題のフラグを提出してしまうと、他のチームに「この問題は解ける」という情報を与えてしまい、夜に解かれやすくなるだろうと考えた結果、Flag Hoarding をすることにしました。

1 日目終了〜夜

この日の最後の方に自分たちが予約した Hardware 問題の枠が回ってきましたが、特に進捗はなかったのでチーム全員で下見を 3 分ぐらいだけして終わりました。すごい機械がありました。

競技終了後、Hardware の機材を誰が持ち帰るかという話になり、st98 さんは Web、mora さんは pwn で忙しく、空いているのは私と parabola0149 さんだけでした。parabola0149 さんは帰宅する予定だった一方、私は徒歩 10 分ぐらいのところにあるカプセルホテルに泊まることになっていたので、「最悪忘れても回収しやすい」という理由で僕が持ち帰りました。チェックインをしてシャワーを浴び、再び問題を解く時間がやってきました。

SECCON Glitch Gate

今回の Hardware 問題です。フラグは 2 つありましたが、明らかに 2 つ目は難しそうなので、1 つ目だけを狙うことにしました。1 つ目だけならさっきのすごい機械を使わなくて済むことをお祈りしました。

Arduino nano でプログラムが動作しているので、プログラムを Reversing してフラグをいい感じに手に入れてね、という問題でした。

Reversing は mora さんに丸投げしようと思いましたが、mora さんが pwn の方へ行ってしまったため、自分で ChatGPT と相談しながら解析しました。

だいたいこんな感じのプログラムでした。

const key = (不明);

int main(){
    
    // なんか初期化処理
    
    byte pinb = PINB; // PINB の入力を受け取る
    byte pind = PIND; // PIND の入力を受け取る
    byte result = (pinb & 0x1f) | (pind & 0xe0);
    if(result ^ key == 0x63){
        printf("[+] The hardware configuration is correct. The first flag: SECCON{***********************}");
    }
    else{
        printf("[!] ERROR: Incorrect hardware configuration detected. No flag for you!");
    }

    // 2 つ目のフラグのための処理

}

まずは key を特定するためにエミュレータを導入して gdb でデバッグします。key の値は 0xbe なので result が 0xdd になればいいことがわかりました。

そうしたら次に実機と通信する必要があります。codegate で badge hack をやったときのことを思い出して、Arduino IDE のシリアルモニタを使って通信しました。なんかボーレートを変えるとうまくいきました。

最後にフラグが表示される条件を満たす物理的配線を探します。入力を常に表示し続けるスクリプトを書いて手作業でガチャガチャしてました。途中電気がバチンってなりました。怖かったです。なんだかんだで正解の配線を見つけられたので、あとは次の日に実践するだけです。大量の機材が配られた割には、結局ジャンパ線 2 本しか使いませんでした… (残りはたぶん 2 つ目のフラグ用です)

フラグを手に入れたのは次の日ですが、一応ここに書いておきます。

flag: SECCON{Two_wires_swap_two_bits}

hell_summon

この問題は Hardware の Reversing 待ちの間に考えていました。しかし途中で詰まってしまい、SECCON Glitch Gate も解けたし寝ようかな… と思ったのですが緊張で眠れませんでした。仕方がないので簡単めな CTF であるところの AlpacaHack の決勝観戦CTF を解いて心を落ち着かせることにしました。10 問ぐらい解いたところで眠くなってきたのでベッドに入り、寝ようとしたところ急にアイデアが降りてきました。AlpacaHack でリラックスできたおかげかもしれません。

from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes
from Crypto.Util.strxor import strxor
import os
import signal

FLAG = os.getenv('FLAG', 'SECCON{dummy}')

chunk_size = 5

def gen_key():
    p = getPrime(64)
    r = bytes_to_long(os.urandom(8))
    H = os.urandom(5)
    pub = p
    priv = (p,r,H)
    return pub, priv

def encrypt(message,priv):
    p,r,H = priv
    assert len(message) % 5 == 0

    message_chunks = [message[i:i + chunk_size] for i in range(0, len(message), chunk_size)]

    ciphertext = b""
    mac = 0
    for chunk in message_chunks:
        temp = strxor(chunk, H)
        mac = (r*(mac + bytes_to_long(temp))) % p
        ciphertext += temp

    return ciphertext, long_to_bytes(mac)

def decrypt(ciphertext, mac, priv):
    mac = bytes_to_long(mac)
    p,r,H = priv
    ciphertext_chunks = [ciphertext[i:i + chunk_size] for i in range(0, len(ciphertext), chunk_size)]

    message = b""
    expected_mac = 0
    for chunk in ciphertext_chunks:
        expected_mac = (r*(expected_mac + bytes_to_long(chunk))) % p
        message += strxor(chunk, H)
    if mac == expected_mac:
        return message
    else:
        return None
    
def main():
    signal.alarm(120)
    p, priv = gen_key()
    print(f"{p=}")
    messages = []
    truncated_macs = []
    for i in range(42):
        message = os.urandom(5)
        _, mac = encrypt(message, priv)
        messages.append(message.hex())
        truncated_macs.append(mac[:-2].hex())
    print(f"{messages=}")
    print(f"{truncated_macs=}")

    c = bytes.fromhex(input("ciphertext:"))
    mac = bytes.fromhex(input("mac:"))
    return decrypt(c, mac, priv) == b"Kurenaif,gimme flag!"

if main():
    print(FLAG)

問題は、公開された 64 bit の素数 $p$ 、隠された 64 bit の乱数 $r$ と 40 bit の乱数 $H$ があって、ランダムな 40 bit の $m_i$ に対する $t_i = (m_i \oplus H) \cdot r \bmod p$ の上 48 bit $t'_i$ が 42 組与えられるので $r,H$ を復元せよ、というものでした。 xor は各 bit で独立なことを考えると、 $m_i$ を足し算して各 bit で 0 と 1 がちょうど $s$ 個ずつ含まれるようにして、そのときの $t_i$ の和を取ればかならず $(2^{40} - 1) \cdot s \cdot r \bmod p$ になりそうです。

$m_i$ の 2 進数表記を $m_i = \sum_{j=0}^{39} 2^j m_{i,j}$ とします。また、

$m'_{i,j}= \begin{cases} -1 & (m_{i,j} = 0) \\ 1 & (m_{i,j} = 1) \\ \end{cases}$

とします。

$\begin{pmatrix} C \cdot m'_{0,0} & C \cdot m'_{0,1} & \cdots & C \cdot m'_{0,39} & 1 & 0 & \cdots & 0 \\ C \cdot m'_{1,0} & C \cdot m'_{1,1} & \cdots & C \cdot m'_{1,39} & 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \\ C \cdot m'_{41,0} & C \cdot m'_{41,1} & \cdots & C \cdot m'_{41,39} & 0 & 0 & \cdots & 1 \\ \end{pmatrix}$

を格子縮約すると、基底

$\begin{pmatrix} 0 & 0 & \cdots & 0 & a_{i,0} & a_{i,1} & \cdots & a_{i,41} \end{pmatrix}$

が 2 つ ( $i = 0,1$ とします) 得られます。

$s_i = \sum_{j=0}^{41} a_{i,j}, T_i = \sum_{j=0}^{41} t_i a_{i,j}, T'_i = \sum_{j=0}^{41} 2^{16} \cdot t'_i a_{i,j}$ とおくと、

$\frac{s_i}{2} \cdot (2^{40} - 1) \cdot r \equiv T_i \pmod p$ なので、 $\frac{s_i}{2} \cdot (2^{40} - 1) \cdot r \equiv T'_i + \delta_{i} \pmod p$ とかけます。

これは Hidden Number Problem なのですが、このままでは情報が足りずうまく求まりません。(ここで詰まりました)

先程の格子縮約の結果の 3 つ目の基底は

$\begin{pmatrix} 0 & 0 & \cdots & 0 & \pm 2C & 0 & \cdots & 0 & a_{2,0} & a_{2,1} & \cdots & a_{2,41} \end{pmatrix}$

のような形でした。(左側の 40 項のうちいずれかが $\pm 2C$ で残りは $0$ になっている) この情報も使うことにしましょう。 $\pm 2C$ になっている箇所の bit は 0 か 1 の 2 択なので決め打てばいいです。(詳細はコードを読んでください。)

すると Hidden Number Problem を解くのに十分な情報が得られ、 $r$ が求まります。あとは $H$ を求めます。 $t_i$ の値が全探索でき、 $r$ が既知になったためそれに対応した $H$ の候補がわかります。 $H$ が $2^{40}$ 未満なことを使えば、十分な確率で $H$ が一意に定まります。

from pwn import *
from Crypto.Util.number import *
from Crypto.Util.strxor import strxor

io = process(["python3", "server.py"])
# io = remote("hell-summon.dom.seccon.games", 8888)

io.recvuntil(b"p=")
p = int(io.recvline().strip())
print(f"p = {p}")
io.recvuntil(b"messages=")
messages = eval(io.recvline().strip())
io.recvuntil(b"truncated_macs=")
truncated_macs = eval(io.recvline().strip())


ms = []
for m in messages:
    ms.append(int(m, 16))
ts = []
for m in truncated_macs:
    ts.append(int(m, 16))

C = 10^7
M = [[0 for i in range(82)] for j in range(42)]
for i in range(42):
    for j in range(40):
        if ms[i] & (1 << j):
            M[i][j] = C
        else:
            M[i][j] = -C
    M[i][40 + i] = 1

M = Matrix(ZZ, M)

M = M.BKZ()
print(M)

u_list = []
T_list = []
for i in range(3):
    print(f"{M[i][:40]}")
    a = M[i][40:]
    s = 0
    T = 0
    for j in range(42):
        s += a[j]
        T += 2^16 * ts[j] * a[j]
    u = 0
    for j in range(40):
        if M[i][j] == 0:
            u += 2^j * s // 2
        else:
            assert abs(M[i][j]) == 2 * C
            # 変換後 1 のやつが多いと信じる
            u += 2^j * (s // 2 + 1)
    u %= p
    T %= p
    print(f"{u} * r = {T} + delta mod p")
    u_list.append(u)
    T_list.append(T)

C = 10^9
C2 = 10^50
M = [
    [p * C, 0, 0, 0, 0],
    [0, p * C, 0, 0, 0],
    [0, 0, p * C, 0, 0],
    [u_list[0] * C, u_list[1] * C, u_list[2] * C, 1, 0],
    [-T_list[0] * C, -T_list[1] * C, -T_list[2] * C, 0, C2],
]

M = Matrix(ZZ, M)

M = M.BKZ()
print(M)

r = M[-1][-2] % p
print(f"r = {r}")

for t in range(ts[0] * 2^16, ts[0] * 2^16 + 2^16):
    H = ((t * pow(r, -1, p)) % p) ^^ ms[0]
    if H < 2^40:
        break

H = long_to_bytes(H)
print(f"H = {H}")

if len(H) != 5:
    print("Bad luck, try again.")
    exit()

# 問題サーバーと同じ
chunk_size = 5
def encrypt(message,priv):
    p,r,H = priv
    assert len(message) % 5 == 0

    message_chunks = [message[i:i + chunk_size] for i in range(0, len(message), chunk_size)]

    ciphertext = b""
    mac = 0
    for chunk in message_chunks:
        temp = strxor(chunk, H)
        mac = (r*(mac + bytes_to_long(temp))) % p
        ciphertext += temp

    return ciphertext, long_to_bytes(mac)

ciphertext, mac = encrypt(b"Kurenaif,gimme flag!", (p, r, H))
print(f"ciphertext = {ciphertext}")
print(f"mac = {mac}")

io.recvuntil(b"ciphertext:")
io.sendline(ciphertext.hex())
io.recvuntil(b"mac:")
io.sendline(mac.hex())

io.interactive()

flag: SECCON{UOoooO0oOoOo00ooO_RECKLESS_SUMOOOOOOOOON_ooooOOooOooOoo}

解けたあとは普通に寝くなったので寝れました。

Day 2

ちょっと早く起きましたが、前日私が Hardware と格闘しているあいだに parabola0149 さんが x_x を解いてくれていたため、もう Crypto の問題は残っていませんでした。この日の KotH へのウォーミングアップとして AlpacaHack を解きました。2 日間で合計 15 問解けました。残っていたのは明らかに初心者向けでない問題ばかりだったのですが、ウォーミングアップとしてはちょうどいい難易度で良かったです。

解いていたらそろそろ出発したほうが良さそうな時間になったので(本当はもう少しやりたかった)、チェックアウトをして、朝ごはんを会場へ向かう途中にあったやよい軒で食べました。

朝ご飯を食べ会場に向かおうとすると、困ったことにその日は東京マラソンの準備が行われていて、道路の向こう側に渡れなくなっていました。無限に迷子になった後、地下鉄の駅の改札付近にいる駅員さんに言えば地下鉄駅を通過できる券がもらえることを知って事なきを得ました。このせいでかなりギリギリに会場に着きました。

Allegro phase 4

この日は基本的に Allegro と格闘していました。暇になったら Jail や Web の問題を見ていましたが、st98 さんがほぼ丸 2 日かけて解けない難易度の Web を私が解けるはずもなく、進捗は特にありませんでした。

ghidra でのデコンパイル結果にすごく既視感がありました、CODEGATE CTF Finals で解いた PY Lover にそっくりです。過去の自分の記録に感謝しながら解析しました。

hiikunz.hatenablog.com

どうやら hash(指定された prefix + ????) = 指定されたハッシュ値 となるような 4 byte を見つければいいようです。ハッシュには md5, sha256, sha512 のどれかが入力で指定されました。

まず mora さんが愚直解を提出してくれました。(Tick: 90~)

その後私が「先に prefix の部分は前計算しておいて、4 byte の部分だ後から更新すればいい」ことに気づいて実装しました。序盤のテストケースでは prefix が短かったため意味をなしていませんでしたが、テストケースの難易度が上がった途端 1 位を連発できました。(Tick: 97〜)

最後には並列化に挑みましたが、むしろ遅くなってしまったので棄却しました。(自分の手元の環境が悪かっただけかもしれません)

Allegro phase 5

Lua で書かれたコードのようです。正誤判定スクリプトに埋め込まれているテストケースを見ていると、なんとなく競プロっぽいです。

Sample Input 1

Sample Output 1

[1307, 2967]
[1518, 3446]

Sample Input 2

2 -1 2 3 -4 5 -6 -7 8

Sample Output 2

[1307, -2967]
[-1518, 3446]

その後、mora さんが解析してわかった「行列っぽい」という話から、たぶん行列積だろう、というあたりをつけました。

そこで、入力を整数 $N$ と $N$ 行 $N$ 列の行列 $A,B$ だと解釈すると、サンプルの出力の値の大きさ的に行列積を 3 回ぐらいやればよさそうです。

実験して、 $(ABAB)^\mathsf{T}$ を求めるとサンプルと一致するので提出します。他のチームに 15 分ほど差をつけて通せたので、次の改善にもいち早く取りかかれました。(Tick: 114〜)

まず自明な改善として、 $C = AB$ として $(C^2)^\mathsf{T}$ を求めれば行列積の回数が 2 回で良くなります。

その後、mora さんが C++ の行列ライブラリの Eigen を使うコードを書いてくれました。(Tick: 117〜)

私が出力のときに頑張れば実際に転置を計算する必要はないことに気づき、ついでに C++ の入出力高速化をしました。(Tick: 122〜)

最後に mora さんが頑張って avx128 に対応させてくれました。(Tick: 129〜)

この時点で他のチームに対し 5 倍以上の速さだったため、並列化は事故が怖いのでしないことにしました。

結果的に常に 1 位を取ることができ、他のチームに大きく差をつけることができました。

Allegro phase 6

とりあえず mora さんが patch して無意味な命令を消してくれたものを出してくれました。(Tick: 141〜)

実行内容がかなり複雑なので、提出したコードにコメントをつけたものを貼ります。

#include <iostream>
#include <cstdint>

using namespace std;

int main() {
    uint64_t X, Y, Z;
    cin >> X >> Y >> Z;
    
    for (uint64_t itr = 0; itr < X; ++itr) {
        uint64_t tmp = 0;
        // Y の偶数ビット (0,2,4,...) を取り出して下位 32 ビットに配置
        for (uint64_t itr2 = 0; itr2 < 32; ++itr2) {
            tmp += (((Y >> (itr2 * 2)) & 1ULL) << itr2);
        }
        // Y の奇数ビット (1,3,5,...) を取り出して上位 32 ビットに配置
        for (uint64_t itr3 = 0; itr3 < 32; ++itr3) {
            tmp += (((Y >> (itr3 * 2 + 1)) & 1ULL) << (itr3 + 32));
        }
        
        // Z の 64 ビット中、セットされているビットの個数を数える
        unsigned char bitCount = 0;
        for (uint64_t itr4 = 0; itr4 < 64; ++itr4) {
            if ((Z >> itr4) & 1ULL)
                ++bitCount;
        }
        
        // Z を更新
        Z ^= (tmp << (bitCount & 0x3F));
        
        // Z の特定のビットから s を計算
        uint64_t s = ((Z >> 7)  & 1ULL) +
                            (((Z >> 15) & 1ULL) * 2) +
                            (((Z >> 23) & 1ULL) * 4) +
                            (((Z >> 31) & 1ULL) * 8) +
                            (((Z >> 39) & 1ULL) * 16) +
                            (((Z >> 47) & 1ULL) * 32) +
                            (((Z >> 55) & 1ULL) * 64) +
                            ((int64_t(Z) >> 63) * -128);
        
        // Z を更新
        tmp ^= (Z << (s & 0x3F));
        Z = tmp ^ Z;
        
        // tmp の各バイトを並べ替え
        Y = (((tmp & 0xffULL))         << 24) +
            ((((tmp >> 8)  & 0xffULL))   << 56) +
            ((((tmp >> 16) & 0xffULL))   << 48) +
            ((((tmp >> 24) & 0xffULL))   << 8)  +
            (tmp & 0xff00000000ULL)              +
            ((((tmp >> 40) & 0xffULL))   << 16) +
            ((tmp >> 48) & 0xffULL)              +
            ((((tmp >> 56) & 0xffULL))   << 40);
    }
    
    cout << Y << "\n";
    return 0;
}

かなり複雑な演算をしています。まずは行列累乗みたいな形で書けないかと思いましたが、popcount の情報を用いた更新があって厳しそうです。

ここで、とりあえず __builtin_popcountll を使えば popcount は高速にできることに気が付きます。

このように他の部分も高速化できないか調べた結果、奇数 bit と偶数 bit を取り出すのは _pext_u64、バイトの並び替えは _mm_shuffle_epi8 でできることが判明し、いい感じに高速化されました。(Tick: 154〜)

終盤になって、KUDoS に 1.1 倍ぐらい負ける事象が確認され困りました。後から聞いたら、ループアンローリングをしたらしいです。

#pragma GCC optimize("unroll-loops")

を前のラウンドまでは競プロの癖でほぼ無意識で書いていたのに、このラウンドでだけ存在が記憶の彼方にありました。完全に疲れていますね。

Allegro 総括

Allegro 全体の得点推移はこんな感じでした。phase 5 (109〜138)、phase 6 (139〜168) で他のチームに大きく差をつけているのがわかりますね。mora さんとの連携がかなりうまくいって嬉しかったです。

競技終盤

Allegro phase 6 の途中で SECCON Glitch Gate の時間になったので本番環境でフラグを手に入れてきました。

====================================================
|                                                   |
|                SECCON Glitch Gate                 |
|                                                   |
====================================================
[*] Welcome to the SECCON Glitch Gate!
[*] Initializing system...
[+] The hardware configuration is correct. The first flag: SECCON{Two_wires_swap_two_bits}

あとは Flag hoarding をしていたフラグを提出しました。(parabola0149 さんの x_x、私の DLP+ と hell_summon) 正解すると kurenaif さんが順位表に現れるのですが、2回連続で出たり消えたりしてちょっと面白かったです。

競技後

国内優勝でした。うれしい。

盾 (チームで 1 個) とメダル (1 人 1 個)をもらいました。

そのあとアフターパーティーがありました。人と話していた結果、最初に取った寿司以外の写真を取り忘れました。いろいろ食べ物があっておいしかったです。

他の競技者や作問者、その他関係者の方々とたくさん話しました。kurenaif さんの使い魔さんが大量の kurenaif さんのグッズを配っていました。

帰り際に会場にあった QR コードのパズルがなぜかもらえました。

感想

今回私 / チームと問題セットとの相性が良く、かなり点数を稼ぐことができました。私の得意なジャンルである Crypto / 競プロがかなりクリティカルに役立ったのが良かったです。parabola0149 さんと自分で苦手なところを補完しあった結果、Crypto を全完できた + HECCON (KotH) でいい成績を取れたのも良かったと思っています。さらに Allegro で mora さんとの連携がとてもうまくいったのも良かったです。また、苦手ジャンルである Web / Pwn を st98 さん / mora さんがやってくれるという安心感があって心強かったです。

個人としてはもっと難しい Crypto (parabola0149 さんが解いてくれた x_x など)も解けるようになりたいし、Web / Reversing / Pwn ももっとできるようになりたいと思いました。

楽しい 2 日間でした。チームメンバーの皆さん、運営の皆様、本当にありがとうございました!

*1:思ったよりケーブルって高いんですね。勉強になりました。

*2:作問者が実装を間違えて 512 bit 以下の整数 or 任意の素数を受け付ける仕様になってしまっているが、気付かなかった