2026-01-31

30 Linear Coffee Generator - official writeup

Daily AlpacaHackという毎日0時に1題ずつ公開される常設CTFの1月30日の問題、「Linear Coffee Generator」の作問を担当したので、公式writeupを書きます。当日に解けた方も解けなかった方もぜひ復習に利用していただけると嬉しいです。

alpacahack.com

問題ソースコードは以下の通り。

import os
import hashlib
from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad

flag = os.environ.get("FLAG", "Alpaca{dummy}").encode()

# You don't need to focus on encrypt_flag/decrypt_flag :)
def encrypt_flag(pt, params):
    key = hashlib.sha256(str(params).encode()).digest()
    cipher = AES.new(key, AES.MODE_CBC)
    return cipher.iv + cipher.encrypt(pad(pt, 16))

def decrypt_flag(ct, params):
    key = hashlib.sha256(str(params).encode()).digest()
    cipher = AES.new(key, AES.MODE_CBC, iv=ct[:16])
    return unpad(cipher.decrypt(ct[16:]), 16)

class LCG:
    def __init__(self):
        self.p = getPrime(64)
        self.a = getRandomRange(1, self.p)
        self.b = getRandomRange(1, self.p)
        self.s = getRandomRange(1, self.p)

    def serve_coffee(self):
        self.s = (self.a * self.s + self.b) % self.p
        return self.s


lcg = LCG()
enc_flag = encrypt_flag(flag, (lcg.p, lcg.a, lcg.b, lcg.s)).hex()

print("#1 order:", lcg.serve_coffee())
print("#2 order:", lcg.serve_coffee())
print("#3 order:", lcg.serve_coffee())
print("#4 order:", lcg.serve_coffee())
# If you can recover p, a, b, and s, you can get the flag using decrypt_flag(bytes.fromhex(enc_flag), (p, a, b, s))!
print("encrypted flag:", enc_flag)

64bitのランダムな素数 $p$ 、および $p$ 未満のランダムな整数 $a, b, s$ を用いて、以下のようにしてserve_coffeeの出力が計算されています。
$s_{n+1} = (a \cdot s_n + b) \mod p$
与えられた4つの出力から $p, a, b, s$ をすべて復元することができたらdecrypt_flagでフラグが得られます。
これはLCG(Linear Congruential Generator)という疑似乱数生成器の一種です。

encrypt_flagとdecrypt_flagは(p, a, b, s)を使ってflagを暗号化/復号していますが、
特定の値を計算できたらフラグが得られる、という形式の問題ではよくあるパターンで、これらの関数には特に脆弱性はありません。

まずは、与えられた4つの出力から式を立てましょう。出力をそれぞれ $s_1, s_2, s_3, s_4$ とすると、以下の4つの式が成り立ちます。

$\begin{align*} s_1 &\equiv a \cdot s + b \pmod p \\ s_2 &\equiv a \cdot s_1 + b \pmod p \\ s_3 &\equiv a \cdot s_2 + b \pmod p \\ s_4 &\equiv a \cdot s_3 + b \pmod p \end{align*}$

これらの式を変形して $\text{(既知の値からなる式)} \equiv 0 \pmod p$ の形に持っていきます。
まず隣接する式同士を引き算して、 $b$ を消去します。
$\begin{align*} s_2 - s_1 &\equiv a (s_1 - s) \pmod p \\ s_3 - s_2 &\equiv a (s_2 - s_1) \pmod p \\ s_4 - s_3 &\equiv a (s_3 - s_2) \pmod p \end{align*}$
さらにこれらの式を使って、 $a$ も消去します。
2つ目と3つ目の式を使うと、
$(s_4 - s_3)(s_2 - s_1) \equiv (s_3 - s_2)^2 \pmod p$
が成り立ちます。ここから、 $(s_4 - s_3)(s_2 - s_1) - (s_3 - s_2)^2$ が $p$ の倍数であることが分かります。
具体的にこの値を計算すると $18015186145068426177274734295463492132$ となります。これは素数ではなく、124bit程度と大きいため、pと別の数の積となっていると考えられます。
この値を素因数分解してみると、 $2^2 \times 9197623 \times 37447334611 \times 13076220846716751461$ となります。
ちなみに、ある程度高速な素因数分解アルゴリズムを使わないと時間がかかります。例えば、 $O(\sqrt N)$ 時間の試し割りアルゴリズムでは計算しているうちに地球が滅亡してしまいます。Daily AlpacaHackなのでせめて24時間以内には終わってほしいです。
Pythonであればsympy.ntheory.factorintや、SageMathのfactor関数を使うと一瞬で答えが求まります。それすら面倒であれば https://factordb.com などのオンラインサービスもあります。

さて、素因数のうち、64bitの素数は1つしかないので、 $13076220846716751461$ が $p$ であると分かります。
次は $a$ を求めましょう。 $s_3 - s_2 \equiv a (s_2 - s_1) \pmod p$ という式から、
$a \equiv (s_3 - s_2) \cdot (s_2 - s_1)^{-1} \pmod p$ と求まります。 $(s_2 - s_1)^{-1} \pmod p$ はPythonであればpow(s2 - s1, -1, p)で計算できます。
$a$ も求まりました。次は $b$ です。 $s_2 \equiv a \cdot s_1 + b \pmod p$ という式を変形して、 $b \equiv (s_2 - s_1 \cdot a) \pmod p$ と求まります。
最後に $s$ を求めましょう。 $s_1 \equiv a \cdot s + b \pmod p$ という式を変形して、 $s \equiv (s_1 - b) \cdot a^{-1} \pmod p$ と求まります。
これで $p, a, b, s$ がすべて求まりました。あとはdecrypt_flagに与えてフラグを得ましょう。

これを実装したソルバは以下の通りです。

import hashlib
from sympy.ntheory import factorint
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad

s1 = 4052328936969804578
s2 = 8676271689691567645
s3 = 2647032430467963079
s4 = 6612596210231769351
flag_enc = "0c5355c5bb76b2a86aa7cf53279fb2350883865f2ca7423ff47512278a59a8db1ed85e82e0d84c2fec52e29d0b3aefd97d791f11edf18efdf1febc07ae860b8b"

def decrypt_flag(ct, params):
    key = hashlib.sha256(str(params).encode()).digest()
    cipher = AES.new(key, AES.MODE_CBC, iv=ct[:16])
    return unpad(cipher.decrypt(ct[16:]), 16)

d1 = s2-s1
d2 = s3-s2
d3 = s4-s3

p = max(factorint(d2*d2 - d1*d3).keys())
a = d2*pow(d1,-1,p)%p
b = (s2-s1*a)%p
s = (s1-b)*pow(a,-1,p)%p
print(decrypt_flag(bytes.fromhex(flag_enc), (p,a,b,s)))

ちなみに、SageMathを使うと面倒な式変形を一切せずに、グレブナー基底を計算する関数に与えられた式をそのまま投げるだけで解けます。

PR = PolynomialRing(ZZ, "a, b, s")
a, b, s = PR.gens()
I = PR.ideal([
    s*a+b - s1,
    s1*a+b - s2,
    s2*a+b - s3,
    s3*a+b - s4,
]).groebner_basis()
print(I) # [a + 1466936314606773311942879293366691031, b + 3280619628752045602450999089964835177, s + 2922826573297502520907432861726796897, 4503796536267106544318683573865873033]
mul_p = int(I[3])
p = max(factorint(mul_p).keys())
a = int(I[0].univariate_polynomial().roots()[0][0] % p)
b = int(I[1].univariate_polynomial().roots()[0][0] % p)
s = int(I[2].univariate_polynomial().roots()[0][0] % p)
print(p, a, b, s) # 13076220846716751461 6534081916410610007 12854780772490122855 12938961673315310206
print(decrypt_flag(bytes.fromhex(flag_enc), (p, a, b, s)))

2026-01-25

【Daily AlpacaHack】2026/01/24 Paca Paca Authenticator - official writeup

Daily AlpacaHackという毎日0時に1題ずつ公開される常設CTFの1月24日の問題、「Paca Paca Authenticator」の作問を担当したので、公式writeupを書きます。当日に解けた方も解けなかった方もぜひ復習に利用していただけると嬉しいです。

alpacahack.com

問題ソースコードは以下の通り。

from Crypto.Util.Padding import pad, unpad
from Crypto.Cipher import AES
import os
import json

aes_key = os.urandom(16)
flag = os.environ.get("FLAG", "Alpaca{dummy}")

def register(username, message):
    data = json.dumps({"name": username, "message": message}).encode()
    cipher = AES.new(aes_key, AES.MODE_CBC)
    token = cipher.encrypt(pad(data, 16))
    print("[debug]", cipher.iv.hex())
    return token

def login(iv, token):
    data = unpad(AES.new(aes_key, AES.MODE_CBC, iv=iv).decrypt(token), 16)
    data = json.loads(data)
    return data["name"], data["message"]


token = register("alpaca", "paca paca!")
print("This is your login token:", token.hex())

print("Oops! I forgot to save the iv, so I can't decrypt the token! Do you know it?")
iv = bytes.fromhex(input("help me> "))

try:
    username, message = login(iv, token)
except Exception as e:
    print("something wrong:", e)
    exit(1)

if username == "alpaca":
    print("paca paca!")
    print("Thanks! That really helped!")
elif username == "llama":
    print("llama!?!!?", flag)
    print("Oh no, I accidentally leaked the flag...")
else:
    print(f"{username}... who are you?")

AESという共通鍵暗号を使った認証システムのコードです。
json.dumps({"name": "alpaca", "message": "paca paca!"}).encode()
をAES-CBCモードで暗号化してトークンとして返しています。
それをaes_keyとユーザーから与えられたivを使って復号し、得られたjsonのnameがllamaであればフラグを返すようになっています。

AES暗号（特に今回使われているAES128）は16byteの鍵と16byteの平文ブロックをもとに16byteの暗号文ブロックを生成する共通鍵暗号です。

ja.wikipedia.org

今回は中でもCBCモード（Cipher Block Chaining mode）という動作モードが使われています。CBCモードでは、暗号化の際に各平文ブロックを前の暗号文ブロックとXORしたものを暗号化します。最初のブロックについては前の暗号文ブロックが存在しないため、IV（Initialization Vector）と呼ばれる値を使ってXORします。
復号の際には、各暗号文ブロックを復号した後に、前の暗号文ブロック（最初のブロックについてはIV）とXORすることで平文ブロックを得ます。
つまり、最初の暗号文ブロックは、最初の平文ブロックを $P_1$ 、IVを $IV$ 、最初の暗号文ブロックを $C1$ とすると、以下のように復号されます。
$P_1 = \mathrm{Dec}(C_1) \oplus IV$
ここで、 $\mathrm{Dec}(C_1)$ はC1を復号した値を表します。
IVが単純にXORされているため、例えばIVのあるビットを反転させると、復号後の平文ブロックの同じビットも反転します。
今回の問題では、IVとしてユーザーから与えられた値を使っているかつ、元のIVが出力されているため、復号後の最初の平文ブロックを任意の値に書き換えることが可能です。
$IV'$ を自由に決められる場合、新しく復号結果としたい平文ブロックを $P_1'$ として、
$IV' = IV \oplus P_1 \oplus P_1'$
と $IV$ を決めれば、復号後の最初の平文ブロックを $\mathrm{Dec}(C_1) \oplus IV' = \mathrm{Dec}(C_1) \oplus (IV \oplus P_1 \oplus P_1') = P_1'$ に変更できます。
今回の問題は、jsonのnameの値を"alpaca"から"llama"に変更したいという状況でした。
nameの値は最初のブロックの16byteに収まっているため、前述した最初のブロックを書き換える方法で達成できます。
{"name": "alpacaから{ "name": "llamaに変更すればよい（llamaのほうが一文字短いため、適当に空白をいれることによって16byteに揃えました）ので、新しいIVを以下のように計算します。
iv = xor(b"{\"name\": \"alpaca", b"{ \"name\": \"llama", original_iv)
これを実装したソルバは以下の通りです。pwntoolsのxor関数を使っています。

from pwn import *

sc = remote(..., ...)
sc.recvuntil(b"[debug] ")
original_iv = bytes.fromhex(sc.recvline().decode())
sc.recvuntil(b"token: ")
token = bytes.fromhex(sc.recvline().decode())
iv = xor(b"{\"name\": \"alpaca", b"{ \"name\": \"llama", original_iv)
sc.sendlineafter(b"> ", iv.hex())
print(sc.recvline())

このように、CBCモードのAES暗号では鍵を知らなくてもIVを書き換えることで復号結果を改竄できてしまいます。同様に、暗号文ブロックを書き換えることでも完全に任意ではありませんが復号結果を改竄できます。
おまけとして、この性質を使った有名な攻撃手法としては、他にもpadding oracle attackなどがあります。

ちなみに、フラグの元ネタはこれです。アルパカとラマは似てるけど、アルパカとオカピは別に似てません。
www.youtube.com

2025-12-09

【Daily AlpacaHack】2025/12/08 Fully Padded RSA - official writeup

Daily AlpacaHackという毎日0時に1題ずつ公開される常設CTFの8日目の問題、「Fully Padded RSA」の作問を担当したので、公式writeupを書きます。当日に解けた方も解けなかった方もぜひ復習に利用していただけると嬉しいです。

初心者向けCTFということで、Crypto分野で最初の一歩として登場するRSAでよく出題される攻撃を題材にしました。一方で複数の攻撃方法を組み合わせたり少しひねったりしたことで、ただ既知の攻撃方法を実装するだけというのは避けて、中級者にも楽しめる難易度にしたつもりです。

alpacahack.com

問題ソースコードは以下の通り。

import os
from Crypto.Util.number import *
from math import gcd

flag = os.environ.get("FLAG", "Alpaca{dummy}")
assert len(flag) <= 40

e1 = 65517
e2 = 65577
while True:
    p = getPrime(512)
    q = getPrime(512)
    if gcd((p-1)*(q-1), e1) == gcd((p-1)*(q-1), e2) == 1:
        break
n = p * q

padded_flag = long_to_bytes(n)[:-len(flag)] + flag.encode()
m = bytes_to_long(padded_flag)
assert m < n
c1 = pow(m, e1, n)
c2 = pow(m, e2, n)

print(f"{n = }")
print(f"{c1 = }")
print(f"{c2 = }")

以下の記事に、RSAの問題においてよく出題される攻撃手法が列挙されている。

zenn.dev

今回の問題に適用できる攻撃がないか調べてみると、以下が該当する。

Common Modulus Attack
同一の平文を同一の $N$ 異なる $e$ で暗号化した暗号文を与えてはいけない

この攻撃を適用すると、より小さな $e$ の暗号文を作ることができる。実際に適用してみよう。
今回の問題では、e1 = 65517, e2 = 65577となっている。これらについて、拡張ユークリッドの互除法を適用する。

実際に計算すると、
$\mathrm{gcd}(e_1, e_2) = 3 = -1093 e_1 + 1092 e_2$ という式が得られる。
これを使って、 $m^g = m^{-1093 e_1 + 1092 e_2} = c_1^{-1093} c_2^{1092} \pmod n$ という形で $m^g$ の値が計算できる。
e1とe2が互いに素だった場合はこれだけで $m^1$ 、つまりフラグが得られるが、今回は最小公倍数 $g$ が3なため、 $m^3$ が得られた。

再度攻撃可能なケースのリストを見てみると、 $m^3$ の値が計算できたことから、以下の状況に合致する。

Low Public Exponent Attack
公開鍵 $e$ が小さすぎてはいけない

これは、 $m^e < n$ という条件を満たす場合に直接 $m^e$ の $e$ 乗根を計算することによって $m$ の値が計算出来てしまうという攻撃だ。しかし、これは今回の問題には直接は適用できない。 $m$ の値がパディングによって大きな値となっているためだ。
パディングはflagの前にnと同じビット列を結合することによって計算されている。これだと $m$ と $n$ は上位bitが完全に一致し、 $m$ が $n$ と非常に近い値になることとなる。実際に手元で $m$ と $n$ の値を計算して出力してみると、 $m$ が $n$ より少し小さい値になっていることがわかる。

n = 0x5080c9faff634e8018c4a6c367b257fad5cb95797a00c663b277af51926b72b41f0aebf8b8d7760842c3b3be9d28da7b50c173deb2017f7c733fa0442ee298a4721311168af7fca9f21d1673d2a64c8948c3e57befad0fff4cb991dedd05f7bf2d9eb3d7803344b6adb5a768bd47b825395c7630f4c3ce665b2dc315665de735
m = 0x5080c9faff634e8018c4a6c367b257fad5cb95797a00c663b277af51926b72b41f0aebf8b8d7760842c3b3be9d28da7b50c173deb2017f7c733fa0442ee298a4721311168af7fca9f21d1673d2a64c8948c3e57befad0fff4cb991dedd05f7bf2d9eb3d7803344b6adb5a768bd47b825395c76416c706163617b64756d6d797d

この $m$ と $n$ の差を $m'$ とすると、 $m = n-m'$ という式が立つ。すると、 $m^3 = (n-m')^3 = -m'^3 \pmod n$ となることから、 $n-m^3 = m'^3$ 、つまり $n-m^3$ が $m'$ の暗号文となることがわかる。
$m'$ はフラグが40byte以下という制約から320bit程度のかなり小さい値となる。 $n$ は1024bitなので、Low Public Exponent Attackが成立する条件である $m^e < n$ を満たす。よって、 $n-m^3$ の3乗根を計算すれば、 $m'$ の値が求まり、そこから $m$ の値も求めることができる。

ソルバの全体は以下の通り。
拡張ユークリッドの互除法は自分で実装してもいいが、SageMathのxgcd関数や、gmpy2のgcdext関数を利用すると簡単に計算できる。
同様に、3乗根を求めるのにはgmpy2のiroot関数を使うと簡単。int(x**(1/3))のような方法だと精度の問題で正しく計算できないので注意。

from Crypto.Util.number import long_to_bytes
from gmpy2 import gcdext, iroot

n = ...
c1 = ...
c2 = ...

g, x, y = gcdext(65517, 65577)
c = pow(c1, x, n) * pow(c2, y, n) % n
m_dash, _ = iroot(n-c, 3)
m = n-m_dash
print(long_to_bytes(m))

LLMと対話して解いた人や、中級者以上の人の中には、この問題をCoppersmith methodというアルゴリズムを使って解いた方もいるかもしれません。実際、今回説明した方法よりも難しいですが、Coppersmith methodを使うことも想定解法の一つでした。実はこの方法では、パディングがlong_to_bytes(n)[:-len(flag)]でなくても、既知の（攻撃者が計算できる）値であれば解くことが出来ます。

2025-07-27

SECCON Beginners CTF 2025 作問者Writeup (Crypto)

SECCON Beginners CTF 2025の01-Translator, Elliptic4b, Golden Ticketの作問をさせていただきました。私の作問した問題の解説( $+\alpha$ )をしたいと思います。

01-Translator (280 solves)
Elliptic4b (171 solves)
Golden Ticket (35 solves)
mathmyth (79 solves)

01-Translator (280 solves)

問題ソースコード（クリックで展開）

import os
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import bytes_to_long


def encrypt(plaintext, key):
    cipher = AES.new(key, AES.MODE_ECB)
    return cipher.encrypt(pad(plaintext.encode(), 16))

flag = os.environ.get("FLAG", "CTF{dummy_flag}")
flag_bin = f"{bytes_to_long(flag.encode()):b}"
trans_0 = input("translations for 0> ")
trans_1 = input("translations for 1> ")
flag_translated = flag_bin.translate(str.maketrans({"0": trans_0, "1": trans_1}))
key = os.urandom(16)
print("ct:", encrypt(flag_translated, key).hex())

フラグがbytes_to_long関数によって01列に変換されたあと、0と1をそれぞれ別の文字列に置換でき、置換後の文字列をAESのECBモードを使って暗号化された文字列が得られます。
AESのECBモードは16byteごとにブロックに分割し、それぞれ暗号化するという処理になっていますが、このとき同じ16byteの文字列は同じ暗号文に暗号化されるという性質があります。そのため、0と1を16byteの任意の文字列に置換しておくと、各暗号文のブロックが元の01列の文字と対応します。よって、最初のブロックと比較することでブロックごとに平文が0と1のどちらだったかを判別できます。最後のブロックはpaddingによって付加された文字列を暗号化したものなのでスキップする必要があります。
ソルバは以下の通りです。

import os
from pwn import *
from Crypto.Util.number import long_to_bytes

sc = remote("01-translator.challenges.beginners.seccon.jp", 9999)
sc.recvuntil(b"> ")
sc.sendline(b"a"*16)
sc.recvuntil(b"> ")
sc.sendline(b"b"*16)
sc.recvuntil(b": ")
ct = bytes.fromhex(sc.recvline().decode())
binary = ""
for i in range(0, len(ct)-16, 16):
    if ct[:16] == ct[i:i+16]:
        binary += "1"
    else:
        binary += "0"
print(long_to_bytes(int(binary, 2)))

Elliptic4b (171 solves)

問題ソースコード（クリックで展開）

import os
import secrets
from fastecdsa.curve import secp256k1
from fastecdsa.point import Point

flag = os.environ.get("FLAG", "CTF{dummy_flag}")
y = secrets.randbelow(secp256k1.p)
print(f"{y = }")
x = int(input("x = "))
if not secp256k1.is_point_on_curve((x, y)):
    print("// Not on curve!")
    exit(1)
a = int(input("a = "))
P = Point(x, y, secp256k1)
Q = a * P
if a < 0:
    print("// a must be non-negative!")
    exit(1)
if P.x != Q.x:
    print("// x-coordinates do not match!")
    exit(1)
if P.y == Q.y:
    print("// P and Q are the same point!")
    exit(1)
print("flag =", flag)

まずは与えられたy座標を持つ楕円曲線上の点を計算する必要があります。
secp256k1という楕円曲線上の点は $y^2 \equiv x^3 + 7 \pmod p$ という関係式を満たすため、 $x^3 \equiv y^2-7 \pmod p$ となるように $x$ を選べばよいです。これには $\bmod p$ 上での $y^2-7$ の3乗根を計算すればよいです。3乗根の計算にはsympyのnthroot_mod関数やSageMathのnth_root関数などが使えます。3乗根が存在しない場合もあるため、その場合は接続しなおして別の $y$ で計算し直します。
次にQ = a * PがP.x == Q.xかつP.y != Q.yを満たす点となるようなaを求めたいです。
$x^3 = y^2-7$ をxy平面にプロットしたグラフを考えると、これを満たすのはPをx軸で反転させた点 $(x,-y)$ ですが、この点はPの逆元にほかなりません。

Pの逆元とはつまりPを-1倍した点ですが、aは負にできないためこれを回避する方法を考える必要があります。
有限体上の楕円曲線の点は有限個であり、楕円曲線上の点を $n+1$ 倍すると必ず元の点に戻ってくるような $n$ が存在することが知られています（楕円曲線の位数と呼ばれます）。
これを使い、 $-1$ 倍の代わりに $n-1$ 倍すればよいです。これですべての条件を満たし、フラグが得られます。
ソルバは以下の通りです。

import os
from pwn import *
from sympy.ntheory.residue_ntheory import nthroot_mod
from fastecdsa.curve import secp256k1
from fastecdsa.point import Point

while True:
    with remote("elliptic4b.challenges.beginners.seccon.jp", 9999) as sc:
        sc.recvuntil(b"y = ")
        y = int(sc.recvline())
        x = nthroot_mod(y**2 - 7, 3, secp256k1.p)
        if x is None:
            continue
        sc.recvuntil(b"x = ")
        sc.sendline(str(x).encode())
        sc.recvuntil(b"a = ")
        a = secp256k1.q - 1
        sc.sendline(str(a).encode())
        print(sc.recvline())
        break

楕円曲線の問題を見たらそっ閉じしているとツイートしている方がいたので作問しました。解いてもらえて良かったです。

Golden Ticket (35 solves)

問題ソースコード（クリックで展開）

import os
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad


flag = os.environ.get("FLAG", "ctf4b{dummy_flag}")
iv = os.urandom(16)
key = os.urandom(16)
challenge = os.urandom(16 * 6)
ENC_TICKET = 3
DEC_TICKET = 3
GOLDEN_TICKET = 0

def menu() -> int:
    print("Your tickets:")
    if ENC_TICKET > 0:
        print(f"{ENC_TICKET} encryption ticket(s)")
    if DEC_TICKET > 0:
        print(f"{DEC_TICKET} decryption ticket(s)")
    if GOLDEN_TICKET > 0:
        print(f"{GOLDEN_TICKET} golden ticket(s)")
    print()
    print(f"1. Encrypt")
    print(f"2. Decrypt")
    print(f"3. Get ticket")
    print(f"4. Get flag")
    print(f"5. Quit")
    while True:
        i = int(input("> "))
        if 1 <= i <= 5:
            return i
        print("Invalid input!")

def consume_ticket(enc: int = 0, dec: int = 0, golden: int = 0):
    global ENC_TICKET, DEC_TICKET, GOLDEN_TICKET
    if ENC_TICKET < enc or DEC_TICKET < dec or GOLDEN_TICKET < golden:
        print("Not enough tickets.")
        exit(1)
    ENC_TICKET -= enc
    DEC_TICKET -= dec
    GOLDEN_TICKET -= golden

while True:
    i = menu()

    if i == 1:
        consume_ticket(enc=1)
        pt = bytes.fromhex(input("pt> "))
        if len(pt) > 16:
            print("Input must not be longer than 16 bytes.")
            continue
        cipher = AES.new(key, AES.MODE_CBC, iv=iv)
        print(f"ct:", cipher.encrypt(pad(pt, 16)).hex())

    if i == 2:
        consume_ticket(dec=1)
        ct = bytes.fromhex(input("ct> "))
        if len(ct) > 16:
            print("Input must not be longer than 16 bytes.")
            continue
        cipher = AES.new(key, AES.MODE_CBC, iv=iv)
        print("pt:", cipher.decrypt(pad(ct, 16)).hex())

    if i == 3:
        print("challenge:", challenge.hex())
        answer = bytes.fromhex(input("answer> "))
        if len(answer) != len(challenge) + 16:
            print("Wrong length.")
            continue
        cipher = AES.new(key, AES.MODE_CBC, iv=answer[:16])
        if cipher.decrypt(answer[16:]) == challenge:
            print("Correct!")
            GOLDEN_TICKET += 1337
        else:
            print("Wrong :(")

    if i == 4:
        consume_ticket(golden=1)
        print("flag:", flag)

    if i == 5:
        print("Bye!")
        exit(0)

AES-CBCの3回の暗号化オラクルと3回の復号オラクルを使って $16 \times 6$ byteの特定の平文を暗号化した文字列を計算することができればフラグが得られます。
最初にGet ticketからchallengeの値を取得します。
次に、ivの値を特定しましょう。オラクルに与える文字列がpaddingされていることに注目します。b"\x10"*16を平文として暗号化すると、paddingによってb"\x10"*32が暗号化されます。
このとき、2つの出力されるブロックd1,d2はそれぞれxor(encrypt(b"\x10"*16), iv)とxor(encrypt(b"\x10"*16), b"\x10"*16)になります。よって、xor(d1, d2, b"\x10"*16)としてivを求めることができます。これを使うと、ivのないAES_ECBとしての単純な暗号化/復号オラクルが得られます。
b"\x10"*16を暗号文の3ブロック目として固定します。すると、暗号文の4ブロック目として与えるべき値は
encrypt(xor(b"\x10"*16, chal[3]))と1回の暗号化オラクルを使って計算できます（ここで、encryptはAES-ECBとしての暗号化を表し、問題で与えられているAES-CBCのオラクルを使ってenc_oracle(xor(pt, iv))[:16]と計算できます）
また、暗号文の2ブロック目として与えるべき値はxor(f3, d2, chal[2])で計算できます。同様にして1回の復号/暗号化オラクルを使って一つ前/後のブロックとして与えるべき値を計算することができます。
これを使うと5回の追加のオラクル呼び出しで暗号文全体を計算することができ、golden ticketを得ることができます。
ソルバは以下の通りです。

import os
from pwn import *

sc = remote("golden-ticket.challenges.beginners.seccon.jp", 9999)

def enc_oracle(pt):
    sc.recvuntil(b"> ")
    sc.sendline(b"1")
    sc.recvuntil(b"> ")
    sc.sendline(pt.hex().encode())
    sc.recvuntil(b": ")
    return bytes.fromhex(sc.recvline().decode())

def dec_oracle(pt):
    sc.recvuntil(b"> ")
    sc.sendline(b"2")
    sc.recvuntil(b"> ")
    sc.sendline(pt.hex().encode())
    sc.recvuntil(b": ")
    return bytes.fromhex(sc.recvline().decode())

def get_ticket(answer):
    sc.recvuntil(b"> ")
    sc.sendline(b"3")
    sc.recvuntil(b": ")
    challenge = bytes.fromhex(sc.recvline().decode())
    sc.recvuntil(b"> ")
    sc.sendline(answer.hex().encode())
    sc.recvline()
    return challenge

chal = get_ticket(b"a")
chal = [chal[i:i+16] for i in range(0, len(chal), 16)]

f3 = b"\x10"*16
d = dec_oracle(f3)
iv = xor(b"\x10"*16, d[:16], d[16:])
f2 = xor(f3, d[16:], chal[2])
f1 = xor(dec_oracle(f2)[:16], iv, chal[1])
f0 = xor(dec_oracle(f1)[:16], iv, chal[0])
f4 = enc_oracle(xor(f3, iv, chal[3]))[:16]
f5 = enc_oracle(xor(f4, iv, chal[4]))[:16]
f6 = enc_oracle(xor(f5, iv, chal[5]))[:16]

get_ticket(f0+f1+f2+f3+f4+f5+f6)

sc.recvuntil(b"> ")
sc.sendline(b"4")
print(sc.recvline().decode())

フラグはウォンカのチョコレート工場をイメージしていましたが、気づいた方はいたでしょうか？

mathmyth (79 solves)

作問者ではありませんが、mathmythについても少しだけ面白い解法を紹介しようと思います。
56bitの素数4つの積としてrが生成されており、それを使って $p = q^2 \cdot \mathrm{next\_prime}(r) + g(q, \mathrm{salt}) \cdot r$ , $n = p q$ とRSAの鍵が計算されています。
想定解は $n \cdot \mathrm{next\_prime}(r)^{-1} \bmod r$ を考えて各素因数ごとに3乗根を計算し中国剰余定理を使って復元、得られた $Q := q \bmod r$ の値から $q = Q + k r$ と表し、 $q$ の近似値 $(n / \mathrm{next\_prime}(r))^{1/3}$ を使って効率的にありえる $k$ の値を探索、という流れでした。
SageMathには直接 $\bmod r$ での3乗根を計算する関数が存在します（内部で素因数分解し各素因数ごとに計算しています）。
更に、 $k$ の値はCoppersmith's methodを使って計算することも可能です。
最近公開されたcusoというライブラリを使うと簡単に計算できます。
このライブラリは多変数版のMultivariate Coppersmithに特化したものですが、機能が充実しており単変数の $\beta$ を使ったCoppersmith's methodも簡単に計算できます。
ソルバは以下の通りです。

from sage.all import *
from Crypto.Util.number import long_to_bytes
import cuso
import ast

with open("output.txt", "r") as f:
    n = ast.literal_eval(f.readline().removeprefix("n = "))
    e = ast.literal_eval(f.readline().removeprefix("e = "))
    c = ast.literal_eval(f.readline().removeprefix("c = "))
    r = ast.literal_eval(f.readline().removeprefix("r = "))

a = next_prime(r) - r
for Q in Zmod(r)(n/a).nth_root(3, all=True):
    Q = int(Q)
    x, p = var("x, p")
    roots = cuso.find_small_roots(
        relations=[Q+x*r],
        bounds={x: (0, 2**61)},
        modulus_multiple=n,
        modulus_lower_bound=2**279,
        modulus_upper_bound=2**280
    )
    for root in roots:
        p = int(root[p])
        q = n // p
        print(long_to_bytes(pow(c, pow(e, -1, (p-1)*(q-1)), n)))
        break

2025-07-06

AlpacaHack Round 12 (Crypto) 作問者writeup

AlpacaHack Round 12 (Crypto)の作問を担当しました。
実はこれがほとんど初めてのCTF作問でしたがいかがでしたでしょうか。楽しんでいただけていれば幸いです。
各問題の解説を書いていこうと思います。

RSARSARSARSARSARSA (39 solves)
OTEC (21 solves)
Flag Sharing (6 solves)
Zero-sum game (3 solves)
総評

RSARSARSARSARSARSA (39 solves)

次のスクリプトとその実行結果が与えられます。

from math import gcd
import os
from Crypto.Util.number import getPrime, bytes_to_long

e = 19
while True:
    p = getPrime(2048)
    q = getPrime(2048)
    if gcd((p - 1) * (q - 1), e) == 1:
        break
n = p * q

flag = os.environ.get("FLAG", "Alpaca{**** REDACTED ****}")
assert len(flag) == 26 and flag.startswith("Alpaca{") and flag.endswith("}")

m = bytes_to_long((flag * 1337).encode())
c = pow(m, e, n)

print(f"{n = }")
print(f"{e = }")
print(f"{c = }")

フラグを1337回繰り返した文字列がRSAによって暗号化されており、公開鍵 $n$ , $e$ と暗号文 $c$ が与えられています。
フラグの代わりに"flag"という文字列で実験してみましょう。"flag"をbytes_to_long関数で整数に変換すると $\mathrm{666c6167}_{(16)}$ となります。では2回結合した"flagflag"はどうなるでしょうか。実験してみると $\mathrm{666c6167666c6167}_{(16)}$ となり、"flag"の場合の $\mathrm{100000001}_{(16)}$ 倍となります。
同様に3回結合した"flagflagflag"は $\mathrm{666c6167666c6167666c6167}_{(16)}$ で"flag"の $\mathrm{10000000100000001}_{(16)}$ 倍、1337回結合した場合 $\sum_{i=0}^{1336} 256^{4i}$ 倍となります。
フラグは26文字であることが分かっているので、得られる暗号文はフラグを $\sum_{i=0}^{1336} 256^{26i}$ 倍した値を暗号化したものとなります。
よって暗号化は $m$ をフラグとして、

$\left(m \sum_{i=0}^{1336} 256^{26i}\right)^e = c \pmod n$

と表すことができます。式変形すると、

$m^e = c \left((\sum_{i=0}^{1336} 256^{26i})^e\right)^{-1} \pmod n$

となり、フラグを直接暗号化した場合の暗号文が計算できました。

更に、 $e$ が19と小さいことに注目します。一般的に $e$ としては65537が選ばれることが多いです。 $e$ が小さいことは直接的にはRSAの安全性には影響を与えませんが、
CTF crypto 逆引きなどにもある通り、 $m^e < n$ を満たす場合には、単純に $c$ の $e$ 乗根を計算することによって平文が復元できてしまい脆弱であることが知られています。
実際、フラグは26文字であるため $\lg m^e < \lg \left(256^{26}\right)^e = 3952$ から $m^e$ は3952bitしかなく、これは $n$ の4096bitを下回るため条件を満たします。
ソルバは以下の通りです。sympyのroot関数を使って $e$ 乗根を計算しています。

import ast
from sympy import root
from Crypto.Util.number import long_to_bytes

with open("./output.txt", "r") as f:
    n = ast.literal_eval(f.readline().removeprefix("n = "))
    e = ast.literal_eval(f.readline().removeprefix("e = "))
    c = ast.literal_eval(f.readline().removeprefix("c = "))

t = 0
for _ in range(1337):
    t = t * 256 ** 26 + 1
c_flag = c * pow(t, -e, n) % n
eth_root = root(c_flag, e)
print(long_to_bytes(eth_root).decode())

一問目に置ける難易度の問題を作るのは正直ボス問を作るより難しかったです。典型問題そのままではなくちょっとひねった感じであまり見たことがない問題となっておりお気に入りの一問です。

OTEC (21 solves)

次のスクリプトが与えられます。

import os
import signal
import secrets
from fastecdsa.curve import secp256k1
from fastecdsa.point import Point
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import long_to_bytes

signal.alarm(60)

flag = os.environ.get("FLAG", "Alpaca{**** REDACTED ****}").encode()

# Oblivious Transfer using Elliptic Curves
G = secp256k1.G
a = secrets.randbelow(secp256k1.q)
A = a * G

print(f"{A.x = }")
print(f"{A.y = }")

x, y = map(int, input("B> ").split(","))
B = Point(x, y, secp256k1)

k0 = long_to_bytes((a * B).x, 32)
k1 = long_to_bytes((a * (B - A)).x, 32)

def encrypt(message, key):
    return AES.new(key, AES.MODE_ECB).encrypt(pad(message, 16))

print(encrypt(flag[0::3], k0).hex())
print(encrypt(flag[1::3], k1).hex())
print(encrypt(flag[2::3], bytes(c0 ^ c1 for c0, c1 in zip(k0, k1))).hex())

楕円曲線を使った1-out-of-2 Oblivious Transferが実装されています。
1-out-of-2 OTは送信者が持つ2つのメッセージのうち、受信者がどちらか一方を選んで受け取ることができ、

送信者は受信者がどちらを受け取ったかはわからない
選ばなかったほうのメッセージに関する情報は一切得られない

という性質を満たすプロトコルです。今回の問題においては1つ目の性質は特に関係なく、"選ばなかったほうのメッセージに関する情報は一切得られない"という点が重要になります。

サーバーと複数回通信することができるため、flag[0::3]とflag[1::3]はそれぞれで通常のOblivious Transferのプロトコルに沿って通信することによって求めることができます。
$k_b (b \in \{0,1\})$ を求めたい場合、 $B = G + b A$ を送ると、
$k_0 = a B = a (G + b A) = A + b a A$
$k_1 = a (B - A) = a (G + b A - A) = A + (b - 1) a A$
となり、 $b = 0$ の場合には $k_0$ を、 $b = 1$ の場合には $k_1$ をA.xとして求めることができます。*1
もう一方の値を求めるためには $a A$ を求める必要がありますが、これには楕円曲線上の離散対数問題を解く必要があり、secp256k1のような安全な楕円曲線のパラメータに対しては現実的な時間では困難であることが知られています。
では、k0とk1のxorされた値を求めることができるでしょうか？というのがこの問題の本質的な部分です。
前述した通り、k0とk1を両方同時に求めることは困難です。よって、それぞれの値を知ることなくk0^k1を求める必要があります。
これを満たす方法として、k0^k1 == 0、つまりk0 == k1となるようにBの値を決めることができないか考えてみましょう。
$A / 2$ を $B$ として与えると、 $aB = aA / 2$ , $a(B - A) = a(A / 2 - A) = -aA / 2$ となり、互いに逆数の関係になります。ここで、楕円曲線ではある点 $A$ とその逆元 $-A$ は共通のx座標を持ち、y座標のみが異なる値となることから、x座標のみを鍵として用いるこのプロトコルにおいてはk0 == k1となります。
よってflag[2::3]は0000...0000で暗号化されることとなり、フラグのすべての部分が復元できます。
$A/2$ を求める際、代わりにsecp256k1.qを法とした2の逆元pow(2, -1, secp256k1.q)を掛けることによって計算する必要があることに注意してください。
ソルバは以下の通りです。

from pwn import *
from fastecdsa.curve import secp256k1
from fastecdsa.point import Point
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad

HOST = os.getenv("HOST", "localhost")
PORT = int(os.getenv("PORT", "9999"))
LOCAL = os.getenv("LOCAL")

G = secp256k1.G

def oracle(b_func):
    if LOCAL: sc = process(["python", "../rawdistfiles/server.py"])
    else: sc = remote(HOST, PORT)
    sc.recvuntil(b"A.x = ")
    x = int(sc.recvline())
    sc.recvuntil(b"A.y = ")
    y = int(sc.recvline())
    A = Point(x, y, secp256k1)
    B = b_func(A)
    sc.sendlineafter(b"B> ", f"{B.x},{B.y}".encode())
    ct0 = bytes.fromhex(sc.recvline().decode())
    ct1 = bytes.fromhex(sc.recvline().decode())
    ct2 = bytes.fromhex(sc.recvline().decode())
    return ct0, ct1, ct2, A

ct0, _, _, A0 = oracle(lambda A: G)
_, ct1, _, A1 = oracle(lambda A: A + G)
_, _, ct2, A2 = oracle(lambda A: A * pow(2, -1, secp256k1.q))

k0 = long_to_bytes(A0.x, 32)
k1 = long_to_bytes(A1.x, 32)
k2 = b"\0" * 32

pt0 = unpad(AES.new(k0, AES.MODE_ECB).decrypt(ct0), 16)
pt1 = unpad(AES.new(k1, AES.MODE_ECB).decrypt(ct1), 16)
pt2 = unpad(AES.new(k2, AES.MODE_ECB).decrypt(ct2), 16)
print(bytes([[pt0, pt1, pt2][i%3][i//3] for i in range(len(pt0) + len(pt1) + len(pt2))]).decode())

よくわからない暗号プロトコルと楕円曲線と、どちらも難しいがちで初心者には忌避されるように思いますが、解法はかなりシンプルで試行錯誤の中でたどり着ける範囲ではあるのかなと思います。
見た目はすごく安全そうでも実は脆弱というのはCryptoジャンルの問題の面白いところの一つで、そんなところを感じていただけたら嬉しいです。

次のスクリプトとその実行結果が与えられます。

import os
import secrets
from Crypto.Util.number import getPrime, bytes_to_long

N = 10

def random_poly(t):
    return [secret] + [secrets.randbelow(p) for _ in range(t - 1)]

def evaluate(f, x):
    return sum(c * pow(x, i, p) for i, c in enumerate(f)) % p

p = getPrime(512)
flag = os.environ.get("FLAG", "Alpaca{************* REDACTED *************}")
assert len(flag) == 44 and flag.startswith("Alpaca{") and flag.endswith("}")
secret = bytes_to_long(flag.encode())

xs = [secrets.randbelow(p) for _ in range(N)]
f = random_poly(N)
shares = [evaluate(f, x) for x in xs]

print(f"{p = }")
print(f"{xs = }")

for i, share in enumerate(shares, 1):
    print(hex(share)[:-i] + "?" * i)

定数項にフラグを持つランダムな多項式 $f$ に対し、10個の $x$ とその $x$ で評価した値 $f(x)$ の上位bitが得られています。
これはShamir's secret sharingという秘密分散のアルゴリズムに似ています。
通常のShamir's secret sharingのプロトコルでは多項式の次数+1個のシェア（ $x, f(x)$ の組）を集めると共有した値 $a_0$ が復元できますが、この際どうやって復元するのかを考えると、ラグランジュ補間を使って以下のように計算されています。
$a_0 = \sum_{i=0}^{N-1} s_i \prod_{j=0, j \neq i}^{N-1} x_j / (x_j - x_i) \pmod p$

$x$ はすべて得られていることから、 $s$ に関する線形和でフラグを表すことができます。また、シェアのうち未知の部分が小さいことから、LLLを使ってシェアとフラグを復元できそうと考えることができます。では、LLLの格子の基底行列の構成方法について考えましょう。
まず、 $s_i$ を既知の部分 $k_i$ と $u_i$ に分割して $s_i = 16^{i+1} k_i + u_i$ と表します。
フラグのうちAlpaca{}の部分は既知なので、
$a_0 = \mathrm{416c70616361}_{(16)} \times 256^{37} + 256 f + \mathrm{7d}_{(16)}$ とおきます。

これで、未知の値は $u_i$ と $f$ だけになりました。

先程の式に代入すると、
$c + 256 f = \sum_{i=0}^9 \lambda_i (16^{i+1} k_i + u_i) \pmod p$
となります。

（ $\lambda_i = \prod_{j=0, j \neq i}^9 x_j / (x_j - x_i), c = \mathrm{416c70616361}_{(16)} \times 256^{37} + \mathrm{7d}_{(16)}$ とおきました。）

ここで、未知数の大きさを計算すると、 $u_i$ は $4i$ bit、 $f$ は $36$ byte（最上位bitは0のため $36 \times 8 - 1 = 287$ bit）であり、合計で
$287 + \sum_{i=1}^{10} 4i = 507$ bit となります。
$p$ の大きさは512bitなので、507bitの自由度であれば解が一意に特定できそうです。

$f$ と $u_i$ からなるベクトルを含むように格子を構成すると、例えば以下のようにできます。

$C = -c+\sum_{i=0}^9 \lambda_i k_i 16^{i+1}$

$[u, 1, k] \begin{pmatrix} 256^{-1} \lambda_0 & 1 & 0 & \dots & 0 & 0 \\ 256^{-1} \lambda_1 & 0 & 1 & \dots & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 256^{-1} \lambda_9 & 0 & 0 & \dots & 1 & 0 \\ 256^{-1} C & 0 & 0 & \dots & 0 & 1 \\ p & 0 & 0 & \dots & 0 & 0 \end{pmatrix} \\ = (f, u_0, u_1, \dots, u_9, 1)$

更に、縮約されたベクトルの各要素の大きさを揃えるため、次のようにスケーリングします。

$[u, 1, k] \begin{pmatrix} 256^{-1} \lambda_0 & 2^{283} & 0 & \dots & 0 & 0 \\ 256^{-1} \lambda_1 & 0 & 2^{279} & \dots & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 256^{-1} \lambda_9 & 0 & 0 & \dots & 2^{247} & 0 \\ 256^{-1} C & 0 & 0 & \dots & 0 & 2^{286} \\ p & 0 & 0 & \dots & 0 & 0 \end{pmatrix} \\ = (f, 2^{283} u_0, 2^{279} u_1, \dots, 2^{247} u_9, 2^{286})$

この行列に対してLLLなどの格子基底簡約を適用したいですが、残念ながらこの行列では目的のベクトルは得られません（この問題はかなりboundが厳しめになるようにしています）。
スケーリング後の目的のベクトルは各値が $[0, 2^{287}$ ]に分布します。この値から $2^{286}$ を引いて $[-2^{286}, 2^{286}$ ]の分布に移動させると目的のベクトルのノルムを平均的に小さくすることができ、より簡約後の格子の基底ベクトルとして現れやすくできます。

$[u, 1, k] \begin{pmatrix} 256^{-1} \lambda_0 & 2^{283} & 0 & \dots & 0 & 0 \\ 256^{-1} \lambda_1 & 0 & 2^{279} & \dots & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 256^{-1} \lambda_9 & 0 & 0 & \dots & 2^{247} & 0 \\ 256^{-1} C - 2^{286} & -2^{286} & -2^{286} & \dots & -2^{286} & 2^{286} \\ p & 0 & 0 & \dots & 0 & 0 \end{pmatrix} \\ = (f - 2^{286}, 2^{283} u_0 - 2^{286}, 2^{279} u_1 - 2^{286}, \dots, 2^{247} u_9 - 2^{286}, 2^{286})$

この行列にLLLを適用することにより、目的のベクトル、そしてフラグが得られます。
ソルバは以下の通りです。

import ast
import string
from sage.all import *
from Crypto.Util.number import long_to_bytes, bytes_to_long

with open("../distfiles/output.txt", "r") as f:
    p = ast.literal_eval(f.readline().removeprefix("p = "))
    xs = ast.literal_eval(f.readline().removeprefix("xs = "))
    share = []
    for line in f.readlines():
        share.append(int(line.rstrip("?\n"), 16))

N = 10
c = bytes_to_long(b"Alpaca{".ljust(44 - 1, b"\0") + b"}")
lam = [product(-xs[j] * pow(xs[i]-xs[j], -1, p) % p for j in range(N) if i != j) for i in range(N)]

inv256 = pow(256, -1, p)
const = (sum(share[i]*2**(4*(i+1)) * lam[i] for i in range(N)) - c) % p

M = block_matrix([
    [Matrix([lam[i] * inv256 % p for i in range(N)]).T, diagonal_matrix([2**(287-4*(i+1)) for i in range(N)]), zero_matrix(N, 1)],
    [(const*inv256-2**286) % p, Matrix([-2**286]*N), 2**286],
    [p, zero_matrix(1, N), 0]
])

for row in M.LLL():
    f = long_to_bytes(int(row[0]) + 2**286)
    if all(ch in string.printable.encode() for ch in f):
        print(f"Alpaca{{{f.decode()}}}")
        break

$2^{286}$ を引く方法以外に、フラグの一文字目を全探索することでも目的のベクトルの大きさを小さくすることができ、同様にフラグが得られます。
LLLの問題はboundに余裕を持たせてあることも多いですが、もう少しのところで目的のベクトルが得られないというときにどうしますか？というところを考えるのもなかなかおもしろいと思います。

Zero-sum game (3 solves)

次のスクリプトが与えられます。

import os
import random
import signal
from functools import lru_cache


@lru_cache
def _nimber_mul(x, y, p=512):
    assert x.bit_length() <= p and y.bit_length() <= p
    if x == 0 or y == 0:
        return 0
    if x == 1:
        return y
    if y == 1:
        return x
    p >>= 1
    lx, rx = x >> p, x & (1 << p) - 1
    ly, ry = y >> p, y & (1 << p) - 1
    rr = _nimber_mul(rx, ry, p)
    ll = _nimber_mul(lx, ly, p)
    lz = _nimber_mul(lx ^ rx, ly ^ ry, p) ^ rr
    rz = _nimber_mul(1 << (p - 1), ll, p) ^ rr
    return lz << p | rz

class Nimber:
    def __init__(self, value):
        self.value = value
    def __add__(self, other):
        return Nimber(self.value ^ other.value)
    def __sub__(self, other):
        return Nimber(self.value ^ other.value)
    def __mul__(self, other):
        return Nimber(_nimber_mul(self.value, other.value))
    def __pow__(self, e):
        assert e >= 0
        a = self
        r = Nimber(1)
        while e > 0:
            if e % 2 == 1:
                r = r * a
            a *= a
            e //= 2
        return r
    def __repr__(self):
        return str(self.value)


signal.alarm(90)
flag = os.environ.get("FLAG", "Alpaca{**** REDACTED ****}")
atk = Nimber(random.getrandbits(512))
hp = Nimber(random.getrandbits(512))

print(f"Your ATK: {atk}")
print("Show your power!")
for turn in range(4):
    print(f"Turn #{turn+1}")
    print(f"Enemy HP: {hp}")
    power = int(input("> "))
    assert 0 <= power < 2**512
    hp -= atk ** power
    if hp.value == 0:
        print("You win!")
        print(f"Reward: {flag}")
        exit()
print("You lose...")

atk,hpがランダムな512bitのNimberとして与えられており、
$a^{p_1} \oplus a^{p_2} \oplus a^{p_3} \oplus a^{p_4} = h$ となるような $p$ を求める問題です。
ただし和、積はNimberの和、積演算です。
ほとんどの人はNimberというものに初めて触れたと思いますが、Nimberは組み合わせゲーム理論で出てくる謎の体です。競技プログラミングの世界では高度典型として一部で知られて(?)います。
Nimberの世界では、和はビットごとのXORで求まります。一方、積は $x \otimes y := \mathrm{mex}\left(\{(x' \otimes y) \oplus (x \otimes y') \oplus (x' \otimes y') : x' < x, y' < y\}\right)$ と定義されています。これは意味が分からないので、謎の演算で定義されているんだなあだとブラックボックス的に理解してもこの問題では特に問題ありません。

この問題で使うNimberの性質は主に以下の5つです。

1. $2^n$ bit以下のNimberは和と積について閉じており、有限体 $\mathrm{GF}(2^{2^n})$ と同型
2. $P = 2^{2^{n-1}}, x < 2^{2^{n-1}}$ とすると、 $x \otimes P$ は通常の積 $x \times P$ に等しい
3. 任意のNimber $x$ は $x_h, x_l < 2^{2^{n-1}}$ を用いて $x = x_h P \oplus x_l$ と一意に表せる
4. $2^n$ bit以下任意のNimber $a$ に対して、 $a^{2^{2^{n-1}}+1}$ は $2^{n-1}$ bit以下となる
5. $a^{-1} = a^{2^{2^n}-2}$ と逆元が計算できる

まず、直接DLPを解くことによって $a^p = h$ となるような $p$ が求まるか考えたいです。しかし、これができてしまうと $\mathrm{GF}(2^{512})$ から同型写像で行き来することによって $\mathrm{GF}(2^{512})$ 上のDLPも解けてしまうことから、おそらく不可能だと結論付けることができます。逆に、 $\mathrm{GF}(2^{2^{n}})$ 上のDLPが解けるのであれば、同型写像で行き来して $2^n$ bitのNimber上のDLPも解くことができそうです。 $\mathrm{GF}(2^m)$ のDLPは関数体篩法などの高速なアルゴリズムの実装がすでに存在し、 $m=128$ であればSageMathのlog関数などを使って10秒程度で解くことができます*2。
よって、

1. 128bit Nimberから $\mathrm{GF}(2^{128})$ への同型写像を構成する
2. 128bit NimberのDLP oracleが呼び出せる状況で $a^{p_1} \oplus a^{p_2} \oplus a^{p_3} \oplus a^{p_4} = h$ となるような $p$ を構成する

の2つができればこの問題を解くことができます。

1. 同型写像の構成
$\mathrm{GF}(2^{128})$ 、つまり $\mathbb{F}_2[x]/(P(x))$ から128bit Nimberへの同型写像を $f(a)$ とします。
$a = \sum_i x^{e_i}$ と分解できるとしたとき、 $f(a) = \sum_i f(x^{e_i})$ が成り立ちます。つまり、各項 $x^i$ があるNimberに対応しており、その和で写像が表せます。
ここで、適当な128bitのNimber $\alpha$ が $x$ と対応付けられると仮定します。
このとき、 $x^i (0 \leq i < 128)$ に対応するNimberは $\alpha^i$ となります。よって、
$f(a) = \sum_i \alpha^{e_i}$ と計算できます。
128bit Nimberから $\mathrm{GF}(2^{128})$ への同型写像はこの逆写像です。 $\alpha^i$ の各ビットを要素とする128要素のベクトルを並べた $\mathrm{GF}(2)$ 上の $128 \times 128$ 行列を考え、その逆行列を計算すると構成できます。
このとき、 $\mathrm{GF}(2^{128})$ の生成多項式は $P(x)=f^{-1}(\alpha^{128})+x^{128}$ となります。

2. $p$ の構成
まず256bitのNimber $a', h'$ に対してDLPオラクル2回の呼び出しによって $a'^{p_1} \oplus a'^{p_2} = h'$ となるような $p$ を求めます。
$h' = h'_1 a' \oplus h'_2$ と分解します（ $h'_1, h'_2$ は128bitのNimber）。この分解は存在する場合一意で、 $h'_1 = h'_h a'^{-1}_h, h'_2 = h' \oplus h'_1 a'$ と計算できます。
あとは $h'_1 = a'^p$ となるような $p$ （ $h'_2$ についても同様）を求めることができればよいですが、 $h_1$ が128bitであることから $p_1$ は必ず $2^{128}+1$ の倍数となります。よって、 $h'_1$ と $a'^{2^{128}+1}$ の間のDLPをオラクルに問い合わせて解けば $p_1, p_2$ が求まります。

さて、この議論は512bitのNimberに対しても同様に適用できます。つまり、512bitのNimber $a, h$ に対して
$h = h_1 a \oplus h_2$ と分解し、
$a^{p_1} \oplus a^{p_2} = h_1$ , $a^{p_3} \oplus a^{p_4} = h_4$ となるような $p_1$ 〜 $p_4$ を求めることで $h = a^{p_1+1} \oplus a^{p_2+1} \oplus a^{p_3} \oplus a^{p_4}$ と表すことができます。
ソルバは以下の通りです。

from functools import lru_cache
from sage.all import *
from pwn import *

HOST = os.getenv("HOST", "localhost")
PORT = int(os.getenv("PORT", "9999"))
LOCAL = os.getenv("LOCAL")

@lru_cache
def nimber_mul(x, y, p=512):
    assert x.bit_length() <= p and y.bit_length() <= p
    if x == 0 or y == 0:
        return 0
    if x == 1:
        return y
    if y == 1:
        return x
    p >>= 1
    lx, rx = x >> p, x & (1 << p) - 1
    ly, ry = y >> p, y & (1 << p) - 1
    rr = nimber_mul(rx, ry, p)
    ll = nimber_mul(lx, ly, p)
    lz = nimber_mul(lx ^ rx, ly ^ ry, p) ^ rr
    rz = nimber_mul(1 << (p - 1), ll, p) ^ rr
    return lz << p | rz

def nimber_div(x, y, p=256):
    return nimber_mul(x, nimber_power(y, 2**p-2))

def nimber_power(a, e):
    r = 1
    while e > 0:
        if e % 2 == 1:
            r = nimber_mul(r, a)
        a = nimber_mul(a, a)
        e //= 2
    return r

m = 128
a = random.randrange(1, 1<<m)
mat = []
for i in range(m):
    x = nimber_power(a, i)
    mat.append([x >> i & 1 for i in range(m)])
mat = Matrix(GF(2), mat)
x = nimber_power(a, m)
x = vector(GF(2), [x >> i & 1 for i in range(m)])
u = x * mat ** -1
F = GF(2**m, "a", modulus=list(u) + [1])

def to_field(x):
    x = vector(GF(2), [x >> i & 1 for i in range(m)])
    u = x * mat ** -1
    return F(u)

def to_nimber(x):
    x = x.to_integer()
    x = vector(GF(2), [x >> i & 1 for i in range(m)])
    u = x * mat
    return sum(int(u[i]) << i for i in range(m))

def make(P, Q, p):
    if p == 64:
        return [to_field(Q).log(to_field(P))]
    ph, pl = P>>p, P&(2**p-1)
    qh, ql = Q>>p, Q&(2**p-1)
    n = 2**p
    P2 = nimber_power(P, n+1)
    t = make(P2, nimber_div(qh, ph, p), p>>1)
    a = 0
    for v in t:
        a ^= nimber_power(P, (n+1)*v+1)
    u = make(P2, ql ^ (a % n), p>>1)
    return [(n+1)*v+1 for v in t] + [(n+1)*v for v in u]

while True:
    start = time.time()
    if LOCAL: sc = process(["python", "../rawdistfiles/server.py"])
    else: sc = remote(HOST, PORT)
    sc.recvuntil(b": ")
    P = int(sc.recvline())
    sc.recvuntil(b": ")
    Q = int(sc.recvline())
    try:
        s = make(P, Q, 256)
    except ValueError:
        print("failed")
        sc.close()
        continue
    print(time.time() - start)
    for v in s:
        sc.sendlineafter(b"> ", str(v).encode())
    sc.recvline()
    print(sc.recvline())
    print(time.time() - start)
    break

ところで、この問題はNimberの話を一切出さずに $\mathrm{GF}(2^{512})$ の問題として出題することも可能でした。
その場合 $\mathrm{GF}(2^{256})$ からの二次拡大を考えると概ね同様の解法で解くことができるのですが、この問題ではNimberの性質を使うことでより解法の方針が立ちやすくなっています。
最初は「CTFでNimberが出たら面白いやろ！w」みたいなノリで作った問題でしたが、First Bloodのsoon-haariさんにもone of the most memorizable chall to me this yearと言っていただき、結果的にかなり面白い問題に昇華できて良かったと思います。

総評

CTFtime運営の対応が遅くCTFtimeに掲載されなかったようで、参加者数が想定の1/3くらいでした。許せねえ。
最終的に解かれた数は前から39-21-6-3でした。開始前の予想は100-65-20-3だったので全体を3倍したら大体当たってますね。AlpacaHackのRoundは4問しかないのもあって毎回崖ができがちですが、かなり理想的な傾斜になったのではないかと思います。
もともと5問出題予定だったのですが、セット的に5問だとさすがに6時間では重すぎるということで4問目が消え、今の4問になりました。結果的に4問に減らして正解だったように思います。消えた問題はまたいつかどこかで出そうと思います。

また、筑波大学のCTFチームTPCでtkbctfというCTFを冬ごろ開催予定です。そちらにもCryptoなどの問題をいくつか出す予定ですので是非ご参加ください。6時間CTFでは重くて出せない難易度の問題もあり、それなりに骨のあるセットになるかなと思います。よろしくお願いします。

*1:通常は $B = k G + b A$ としますが、この問題では"送信者は受信者がどちらを受け取ったかはわからない"というのを満たす必要はないため単純に $k=1$ としてよいです

*2:古いバージョンだと遅い実装が使われておりもう少し時間がかかるようです https://github.com/sagemath/sage/issues/32842

2024-10-28

Hackceler8 2024 優勝参加記

10/18-20に開催されたHackceler8（Google CTF 2024の決勝イベント）にチームKijitoraとして参加し、優勝することができた。賞金7331ドル*1も得た。これはそのWriteup兼参加記。*2
KijitoraはGoogle CTFのために結成された日本人合同の大きなチームで、私は今年からkeymoonさんに誘われて参加した。

予選は6/22-24に開催された。Kijitoraには強いCTFプレイヤーが沢山おり、私が焼きなマシーンをしていたら*3すごい勢いで問題が解かれて2位になり、ここでも賞金5432.1ドルを獲得した。8位以内だったため決勝に招待される。
決勝のオンサイト参加に立候補する人が全然おらず、他に行く人が居なかったら行きたいけど…と思っていたらkeymoonさんに引っ張り出された*4。結局keymoonさんとptr-yudaiさん、同様に引っ張り出されたArataさんの4人でスペインに行くことになった。内ptr-yudaiさんを除く3人は全員筑波大学生。

Hackceler8は予選とは全くルールが違い、CTFとSpeedrun(日本ではRTAと呼ばれることが多い？)を組み合わせたような感じで、ゲームに埋められたバグを見つけ出し、それを使ってステージをクリアするまでを競うというような大会である。
ルールを聞いただけでもかなり私の好きそうなコンテストで、せっかくスペインまで行くなら頑張ろうという気持ちだった。

~Day0
Day1
Day2
Day3
- Semifinals
- Finals
Day4

~Day0

9/14 にベースとなるゲームが公開された。本番ではこのゲームのステージやギミックの一部が改変されるため、それに対応できるよう予め色々なチートを準備する。
軽く触ってみると、マリオとかのような所謂プラットフォーマーと言われるジャンルのゲームらしい。例として用意されているマップも単純に難易度が高いものが多く、チートなしの人力では確かにクリアするのは厳しそうだった。

いくつかマップがあり、各マップにいるNPCまでたどり着くとスターが貰える。スターを一定数集めるとボスへのポータルが解放されるという感じのようだった。また、毎試合いくつかコインが配置されており、それを取る事で以降の試合で相手チームに対して妨害アイテムが買えるらしい。
とりあえず前年のゲームや配信、公開されている出場チームのツールを見て、どのようなチートを実装する必要があるのか考える。
試合は45分の準備フェーズと、リモートサーバーにつないで実際にステージをクリアする45分の後半フェーズに分かれている。基本的にすべてのチームは準備フェーズ中にローカルでステージをクリアし、そのときのキー入力のリプレイを記録しておいて後半ではそれをリプレイするという流れになる。
そのためにキー入力を記録/再生する機能はほぼ必須である他、当たり判定の表示やゲームを1tickずつ進めるといったチートはどのチームも実装しており、確かにあると便利そうだった。
他に、フィールドにお絵描きできるアイテムがあったので自動でお絵描きできるツールを描いた。色合いがpietっぽいしpietを描かせる問題が出そうだなあと思っていたら本番では本当にpietを書かされた。

その他、ゲームを数tick前の状態に戻すといったUndo機能も実装した。これにはゲームの状態全てを保存しておく必要があり、更にゲームコードの変更にロバストでなければいけない。色々試行錯誤した結果、ゲームオブジェクトを丸々pickleしてunpickleすることにした。中にはネットワークまわりなどいくつかpickleできないオブジェクトも存在するため、それらは別で保存しておいてunpickleする時に元に戻す。

ほかのチームメイトは学園祭実行委員やCTFプラットフォームの運営などで非常に忙しそうにしている中、私はずっと暇人だったので一人ツールづくりに勤しんでいた。結果としてコードベースを一番把握しているのが自分になり、競技中にコードを書く必要があった場合は大体私の担当になった。

Day1

1日目は全チームが同時にプレイする形式の試合が3回行われた。この結果で順位が付き、1,2位、3,4位、はそれぞれ2日目以降のトーナメントで2試合、1試合分のシード権が与えられる。

3試合の結果はそれぞれ2位、1位、6位で、全体2位通過と悪くない結果だった。

面白かったのは2試合目のruinsステージ。鍵付き扉2つの先にNPCがいるが鍵は一つしかなく、どうにか鍵を増殖させるなどして両方の扉を開けなければいけない。
一度開けた扉をもう一度閉じると鍵が再度もらえるが、この際入口側に押し出されるため扉の中から鍵を抜くといったことはできなそうだ。
ここで、扉の開閉状態と鍵の所持状態はsave_fileファイルで管理されているのが気になった。サーバーにつなぎ直した時、扉と所持アイテムの状態はsave_fileファイルから読み取って初期化される。save_fileファイルはサーバー側でtickごとの一番最初で更新されているが、アイテムを取得した際などにも追加でセーブされる処理が走っている。
処理をよく読んでみると、扉を閉じたとき、扉の開閉状態が更新される処理は鍵の再取得の後であり、それがセーブされるのは次tickでのセーブ時である。よって、次tickの情報をサーバーに送信する前にゲームを切断すれば、サーバー側での最後のセーブは鍵を再取得した直後、扉が閉まる直前のものになる。よって、次回のゲーム開始時には鍵を持っていてかつ最初の扉が空いている状態になり、2つ目の扉も開けられるということになる。
この他にもこういうバグ実際のゲームでもありそうだな〜みたいな問題多く出題されており、それこそRTAとかが好きな人は有利だったかもしれない。

3試合目のボスはCTFでよくあるpath traversalでキーワードをリークする問題だった。なんとか倒せたものの、用意していた「サーバーにパケットを送るのを遅延させるチート」にボスを倒すとその後のパケットが送られないというバグがあり、クリアした判定にならなかった。それを直して再度ボスを倒すも、試合終了に数秒の差で間に合わなかった。

開始前は｢2日目で負けると3日目暇になって嫌だな〜｣とか思っていたので、とりあえず3日目まで行けることが確定して安心した。それと同時に、この時点で賞金圏内が確定したらしくびっくりだった。また、この時点で22枚とかなりコインを稼げていたのも良かった。
この日実際にツールを使ってみて、改善が必要な点を一通り洗い出して実装していった。

Day2

2試合分のシード権を得ているのでこの日は試合はないが、問題は全てのチームに配布との事なので練習として本番と同様の状況で問題を解いた。

オンラインで参加していたメンバーが少なかったのもあったが*5、2戦目では実際に対戦していたチームの全てに負けており、かなり次の日が不安になった。

特に、ゲーム内で別プロセスが実行されるarcadeというステージでは色々なチート機能を無効にするようにしており、ほとんど何も対策していなかったため、単純な解法の問題が解けなかった。どんな問題が出るか全く想像できなかったため安全側に倒していたが裏目に出た。その場でコードを書き換えてarcadeでもtickrate変更とtick停止を使えるようにしたが間に合わなかった。

試合後、すでに敗退したチームが既に自分たちのコードを公開していた。マジかよと思ったがどうやらCTFではそういうもんらしい。C4T BuT S4Dのツールを見ていると、経路探索機能のドキュメントとして登れないはずの壁を登っている動画を貼っていた。ベースのゲームには意図されたバグは仕込まれていないはずなのでかなり驚いたが、実際に手元で動かしてみると確かに壁を登れている。
ベースのゲームでそんなことができてしまうといくつかのスターが非想定で簡単に取れてしまうほか、なんなら実は意図的に仕込まれていて最後の大謎として出題されるのではないかと思い、挙動を解析して自分達のツールでも使えるよう組み込んだ。
どうやら2年前にもあらゆる壁を抜けられるバグがベースのゲームに存在しており、その時はすぐにパッチされて使えなくなったらしい。

https://github.com/C4T-BuT-S4D/hackceler8-2024

色々解析した結果、次のようなことがわかった。

まず、このゲームでは重力は移動によってプレイヤーが壁や床に触れてめり込んだ時、上下左右4方向に対して、その方向にどれだけ押し出せばプレイヤーが壁にめり込んでいない状態になるかを計算し、最も小さい方向（min push vectorと呼ぶ）に押し出すというロジックが存在する。

ジャンプ可能かの判定は、プレイヤーの座標を1だけ下にずらした時、min push vectorが上方向であるような当たり判定が存在するならcan_jumpをTrueにする。
というように処理している。

壁に向かってジャンプしてめり込み、ふたつの壁の境目でcan_jump判定を更新すれば壁ジャンプができそうである。ところが、ゲーム処理は、

ジャンプ可能判定の更新
プレイヤーの入力を反映
min push vector方向に押し出してめり込みを解除

という順番で行われているため、ジャンプ可能判定の処理時点ではめり込みが解除されており一見壁ジャンプは不可能である。

しかし、コードをよく読むと、プレイヤーを押し出す時push vectorをintに丸めた値が0であれば押し出さないという処理がある。
これによって、1未満であれば壁にめり込むことができる。*6
プレイヤーの移動速度は2.3/tick、ダッシュすると1.5倍の3.45/tickのため、プレイヤーの座標 mod 1.15は常に一定となる。しかし、壁に当たることによってこの座標 mod 1.15の値(これをsubpixelと呼んでいた)を変えることができる。
これによって、適切な壁があれば、壁にめり込む量を1未満の間で0.05単位で調整することができる。

まとめると、
「上下に重なるふたつの壁境目で、1だけ下にずれたときに横方向のpush vectorより上方向のpush vectorの方が小さくなるように、予め適切な壁にぶつかってsubpixelを揃えておき、ちょうど壁にめり込みむところまで移動し、ちょうどジャンプ可能判定がTrueになるタイミングでジャンプキーを入力する。」

という手順で壁ジャンプが可能となる。

左下の座標の表示を見ると、左方向のpush vectorは $3064.45-3064.00=0.45$ 、上方向のpush vectorは $4410.00-(4410.70-1.00)=0.30$ であり、 $0.45>0.30$ なためcan_jump判定がTrueになる。このタイミングでジャンプキーを押すとジャンプできる。

左下の座標の表示を見ると、左方向のpush vectorは $3064.45-3064.00=0.45$ 、上方向のpush vectorは $4410.00-(4410.70-1.00)=0.30$ であり、 $0.45>0.30$ なためcan_jump判定がTrueになる。このタイミングでジャンプキーを押すとジャンプできる。

壁ジャンプするためのsubpixelが揃っている壁のビジュアライズと、ちょうど壁にめり込む所までだけ移動するのの自動化、can_jump判定がTrueになるタイミングでのジャンプの自動化を書いた。

決勝で実際に出題されたが、その時はcan_jumpの判定方法が変更されていて若干簡単になっていたようだった。
また、これについて解析している途中で、can_jumpがTrueになるタイミングですぐにジャンプするとlast_ground_posの値が更新されないバグも見つけ、これも決勝で出題されたため役に立った。

Day3

2日目までとは違いYouTubeに配信されているため、大きな講堂のようなところで箱に入れられて競技をすることになった。2日目までは他のチームの声でオンラインメンバーと繋いでいたVCが全然聞こえなかったが、今度はちゃんと防音されておりその点ではかなり良かった。

会場準備が押したらしく準決勝の開始10分前に会場入りして慌ててpcなどのセットアップをした。

Semifinals

準決勝はKalmarunionenとの対戦だった。
modをゲームクライアントに自動で適用させるpatcherが上手く動かず序盤で躓いたが、準備フェーズ中にocean、ruins、arcadeがクリアされた。

ボスに入った時点ではリードしていたが、相手に先にボスを倒されると負けるため全く油断できなかった。

しかし、オンラインのxrekkusuさんが突然「倒した」と言ってキー入力ファイルを上げた。早すぎて全く意味がわからなかったが、どうやらoceanのステージをクリアするのに使った｢しゃがみながらだと攻撃のクールタイムがなくなり秒間30回攻撃できる｣というバグがボスにも使えたらしい。急いでサーバーに繋いでボスを倒し、こちらのチームが勝利した。

あとから聞いた話だと相手チームも数分差でボス部屋まで到達しており、同じ方法を試そうとしていたところだったとの事で、本当に危なかった。

他のチームが戦っていた2試合目はバグを直しながら客席で観戦した。ボス問としてNPCとインタラクティブに会話するpwnが出るなど、うちのチームが得意そうな問題群が出て｢こっちの問題がやりたかった｣などと話していた。

Finals

決勝はZer0RocketWrecksとの対戦だった。

決勝までは30分ほど時間があると聞いておりゆっくり準備をしていたらいきなり問題ファイルが共有されて試合が始まり、慌ててpcなどのセットアップをした。

開始から15分ほど、ruinsが前日に用意した2段ジャンプチートでクリアできるらしい。
beachも前日に用意した自動ジャンプを使うと上手くいくらしく、25分ほどで準備フェーズ中にクリアされた。
cloudもサーバーに接続可能になる直前にクリアできたらしく、あとはarcadeかmazeのステージがクリアできるとボスポータルを解放できる。
今までのarcade問は全てPythonだったが、ここではバイナリが実行されていた。arcadeは私が担当するつもりだったが、バイナリでpwnっぽいとなると自分より適任がいるのでその人達に任せる。
mazeのpiet問がローカルで解けたと報告が入る。その後リモートでも特にバグらずに動き、これでボスが開放された。この時点で残り30分程度、得たスターの数は7-3で勝っていた。

ボスは一見ベースゲームから何も変更がないように見えたが、hpを半分まで減らすと第2形態に移行し全くダメージが入らなくなった。ボスに重なって攻撃する、近接攻撃する、第1形態の間に弾を貯めて一気に攻撃する、など色々試したが最後まで倒せず、ゲームが終わった。
終わった瞬間はボス倒せなかった……という気持ちだったが、よく考えるとボスに入る時点では勝っており、その後逆転された様子もないのでどうやら勝ったらしい。実感がわかないうちにインタビュワーが部屋に入ってきた。

優勝できるとは思っておらず、また予選はかなりキャリーされ気味だったので、ちゃんと活躍した結果の優勝というのもありかなり嬉しかった。

書いたツールはかなり便利に動いてくれた。ただし、ノリで適当に機能を継ぎ足していったら自分でも汚いと思う感じのコードになり、チームの人にももうちょっと手加減してくれと言われながらリファクタリングされるなどしたのはかなり反省だった。その割に本番は大きなバグなく動いてくれてよかった。

優勝チームは毎年ツールを公開してるよ！みたいな圧をかけられた(?)ので、作ったツールはGitHubに公開している。cloneして適当にmod.pyを実行すれば動くようになっているはずなのでぜひ触ってみてください。
github.com

Day4

決勝翌日は一日空いていたので、マラガ県内を観光した。ホテル近くの海で海水浴をしたり（めちゃくちゃ寒かった）、ゲームミュージアムに行ってファミコンやCHUNITHMをしたり、デカい砦の前で本物のKijitora猫に挨拶したりした。

*1:もっと欲しい

*2:とはいえ、私が直接解いた問題はそう多くない

*3:https://x.com/Yu_212_MC/status/1804941678173966570

*4:ありがとう

*5:オンサイトでゲームをプレイするのは4人だが、オンラインで他のチームメンバーに問題を共有して大人数で取り組むことが可能

*6:ただし壁に向かって歩き続けているとpush vectorが1以上になるためすぐに押し出される

2024-09-15

AlpacaHack Round 3 (Crypto) writeup

2024/9/15に開催されたAlpacaHack Round 3 (Crypto)のwriteupです。全完して6位でした。
主に競技プログラミング界隈から来て最近CTFを始めたという方に向けて、CTF特有の考え方といった部分を丁寧めに書いてみます。

qrime
- ソルバ
- おまけ
Rainbow Sweet Alchemist
- ソルバ
A Dance of Add and Mul
- ソルバ
Hat Trick
- ソルバ

qrime

RSA暗号をベースにした問題ですが、 $n$ の素因数 $p$ の生成方法が特殊です。
$p = q \cdot \mathrm{nextPrime}(r) + \mathrm{nextPrime}(q) \cdot r$ として生成され、 $n, e, c$ に追加で $r$ が与えられています。
RSA暗号は $p$ または $q$ を求めることができてしまうと任意の暗号文を復号できます。
この式と $n = pq$ の $2$ つの式を用いて $n$ の素因数 $p, q$ を求めることができないでしょうか。
ここで、 $\mathrm{nextPrime}$ が数式として表しにくく邪魔なため、ある整数 $a, b$ を用いて $\mathrm{nextPrime}(q) = q + a, \mathrm{nextPrime}(r) = r + b$ と表すことを考えてみます。
すると、 $p$ に関する最初の式は $p = q (r + b) + (q + a) r$ となり、未知数が $2$ つ増えてしまう代わりに式として扱いやすくなります。*1
では、式に出てくる値それぞれの大きさ(bit数)を考えてみましょう。 $q, r$ はコードにある通り256ビットのランダムな値を取ります。 $n$ が $766$ ビットであることから $p$ は $510$ ビットです。では $a, b$ はどうでしょうか。
次のようなコードを実行すると、 $a, b$ がどれくらいの大きさの値になるかわかります。

x = getRandomNBitInteger(256)
print(nextPrime(x) - x)

何度か実行してみると、高々1000とかなり小さい値をとっています。*2 $a, b$ 両方を十分高速に全探索できそうです。*3
ここまでをまとめると、 $p, q$ を未知数として連立方程式
$\begin{equation} \left\{ \, \begin{aligned} & n = p q \\ & p = q (r + b) + (q + a) r \end{aligned} \right. \end{equation}$
を解くことができればよいです。
これを変形していくと $(2 r + b) q^2 + a r q - n = 0$ と、 $q$ に関する二次方程式が得られます。これを解くことで $q$ を求めることができました。

ソルバ

from Crypto.Util.number import long_to_bytes
from math import isqrt

n=200697881793620389197751143658858424075492240536004468937396825699483210280999214674828938407830171522000573896259413231953182108686782019862906633259090814783111593304404356927145683840948437835426703183742322171552269964159917779
e=65537
c=77163248552037496974551155836778067107086838375316358094323022740486805320709021643760063197513767812819672431278113945221579920669369599456818771428377647053211504958874209832487794913919451387978942636428157218259130156026601708
r=30736331670163278077316573297195977299089049174626053101058657011068283335270

def solve_rsa(p, q):
    phi = (p - 1) * (q - 1)
    d = pow(e, -1, phi)
    m = pow(c, d, n)
    return long_to_bytes(m)

def solve():
    for a in range(1000):
        for b in range(1000):
            aa = 2 * r + b
            bb = a * r
            cc = -n
            q = (-bb + isqrt(bb * bb - 4 * aa * cc)) // (aa * 2)
            if q > 0 and n % q == 0:
                p = n // q
                print(p, q)
                print(solve_rsa(p, q))
                return
solve()

Crypto.Util.number は pycryptodome のモジュールです。この問題ではバイト列と整数の間の変換に使われていましたが、pycryptodome はこの問題に限らず多くの問題で使われます。

おまけ

ちなみに、sagemathをうまく使うと、二つの式を求めた後人力で式変形をする必要なく簡単に解くことができます。二つの式の終結式を求めてそれを解かせています。（私はこちらの方法で解きました）

from sage.all import *

PR = PolynomialRing(ZZ, ["p", "q"])
p, q = PR.gens()
for a in range(1000):
    for b in range(1000):
        f1 = n - p * q
        f2 = q * (r + b) + (q + a) * r - p
        rr = f1.resultant(f2).univariate_polynomial().roots()
        if len(rr) > 0:
            q = rr[0][0]
            p = n // q
            print(solve_rsa(p, q))

Rainbow Sweet Alchemist

RSA暗号をベースにした問題で、 $n$ の素因数 $p, q$ の生成方法が特殊です。
シードを固定した乱数生成器を用いていくつかの素数を生成した後、 $1024/64=16$ 個の値を使って $p = 2 \prod_{i=0}^{15} \mathrm{factors}_i + 1$ のようにして $p, q$ を生成しています。
random.choice はシードを固定した乱数生成器を使っていないため、同じコードを実行して $p, q$ を得るというのは不可能そうです。
ここで、 $\varphi(n) = (p-1)(q-1) = 2 \prod_{i=0}^{15} \mathrm{factors}_i \cdot 2 \prod_{i=16}^{31} \mathrm{factors}_i$ の素因数としてあり得るものが全て求まることに注目します。実験してみるとgetPrimeは多めに見積もっても $1000$ 回程度のループで答えを返すため、deterministicGetPrime が返す最初の $2000$ 個の値を手元で計算しておくと、 $\varphi(n)$ の素因数は $2^2$ とこのリストの中の値のみを含みます。
つまり、 $4$ とこのリストすべての値の積を $P$ と置くと、これは $\varphi(n)$ の倍数となります。この性質の何が嬉しいかというと、オイラーの定理より、 $a$ を $n$ と互いに素な整数として $a^P \equiv 1 \pmod n$ が成り立ちます。
このリストから素数を一つずつ消していくと、 $\varphi(n)$ の素因数 $r$ が消された場合にのみ $a^{P/r} \not\equiv 1 \pmod n$ となり、各素数が $p, q$ の生成に使われたかを判定することができます。
逆に、リストに一つずつ素数を追加していき $a^P \equiv 1 \pmod n$ となったタイミングを調べていくという方法でも解くことができ、こちらのほうが高速です。

考え方としてはポラードのp-1因数分解法に近く、このアルゴリズムを知っている人であれば早く思いつけるのかなと思います。

ソルバ

from Crypto.Util.number import long_to_bytes
import random

r = random.Random(0)
def deterministicGetPrime():
    while True:
        if isPrime(p := r.getrandbits(64)):
            return p

def solve_rsa(p, q):
    phi = (p - 1) * (q - 1)
    d = pow(e, -1, phi)
    m = pow(c, d, n)
    return long_to_bytes(m)

assert deterministicGetPrime() == 2710959347947821323

ps = [deterministicGetPrime() for _ in range(2000)]
factors = []
while len(factors) < 16:
    prd = 1
    x = pow(2, 4, n)
    for p in factors:
        x = pow(x, p, n)
    if x == 1:
        break
    for p in ps:
        x = pow(x, p, n)
        if x == 1:
            factors.append(p)
            break
    print(factors)
tmp = 1
for p in factors:
    tmp *= ps[i]
p = tmp * 2 + 1
q = n // p
print(solve_rsa(p, q))

A Dance of Add and Mul

楕円曲線の問題です。
いくつかの有名なパラメータの楕円曲線には名前がついており、問題コードに書いてあるBLS12-381もその一つです*4。検索してみるとペアリングの計算をする際によく用いられるとわかります。
ペアリングについての説明は（私もあんまりよくわかっていないため）省略するので、このページなどを見てください。

さて、隣接する $c$ について $\mathrm{xs}$ から共通の値を使っていることから、各 $c$ に対して $0$ か $1$ か求めるよりも、隣接する二つの $c$ について同じ値を取るかを求めるほうが見通しがよさそうです。
$\mathrm{cs}_i$ と $G_1, G_2$ の間でペアリングの計算をすることを考えると、例として $i = 0, c = 0$ のとき $f(\mathrm{cs}_0, G_1) = f(x_1 G_1 + x_2 G_2, G_1) = f(G_1, G_1)^{x_1} f(G_2, G_1)^{x_2} = f(G_2, G_1)^{x_2}$ のようになります。
更に、 $i = 1, c = 1$ のときについて考えると $f(\mathrm{cs}_1, G_1) = f(x_3 G_1 + x_2 G_2, G_1) = f(G_1, G_1)^{x_3} f(G_2, G_1)^{x_2} = f(G_2, G_1)^{x_2}$ のようになり、先ほどの結果と一致します。
このことから、 $G_1$ とのペアリングを計算した結果が隣接する二つの $\mathrm{cs}$ で一致した場合、その二つの $c$ の値は異なることが分かります。 $G_2$ とのペアリングを計算した結果についても同様です。
これと一つ目の $c$ が $0$ であることから、すべての $c$ の値を求めることができます。
上述のサイトでは $\mathbb{F}_{p^{12}}$ に拡大した体を用いていましたが、この問題では $\mathbb{F}_{p}$ で十分なようです。

ソルバ

from pwn import *

cs = eval(read("a-dance-of-add-and-mul/chall.txt").decode())

p = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
K = GF(p)
E = EllipticCurve(K, (0, 4))
cs = [E(x, y) for x, y in cs]

G1, G2 = E.gens()
o1, o2 = G1.order(), G2.order()

r = 0x5f19672fdf76ce50d28e776116d47d5841f8c5f1fba8d33881bfa40089fc5bffd1ffffff00010001
A1 = [c.weil_pairing(G1, r) for c in cs]
A2 = [c.weil_pairing(G2, r) for c in cs]

v = 0
vs = []
for i in range(len(A1) - 1):
    vs.append(v)
    if A1[i] == A1[i+1] or A2[i] == A2[i+1]:
        v = 1 - v
vs.append(v)
print(unbits(vs))

readやunbitsはpwntoolsにある関数で、それぞれバイト列としてファイルを読む関数とビットのリストをバイト列に変換する関数です。pwntoolsには他にもいくつか便利な関数があるのでリファレンスに目を通しておくと便利かもしれません。

Hat Trick

三つのRollingHashについてハッシュが特定の値を取るような長さ54以下の英小文字列を求める問題です。

まずは与えられた条件から使えそうな式を立てていきます。
使う文字数については多いほうが考えられる状態が広く条件を満たすように値を取りやすくなるため、とりあえず最大の54文字を決め打ちで考えていきましょう。
$s_i$ は英小文字であることから、 $97 \leq s_i \leq 122　(0 \leq i < 54)$ です。
更にRollingHashの式を考えると、 $\sum_{i=0}^{53} s_i \mathrm{base}^i \equiv \mathrm{target}_j \pmod {p_j}$ というような式が $3$ つ立ちます。
一度ずつしか登場しない値 $p_j$ が法として使われているのはあまりうれしくないので、未知の整数 $k_j$ を用いて $\sum_{i=0}^{53} s_i \mathrm{base}^i \equiv \mathrm{target}_j + k_j p_j$ というように変形します。
ここで、 $s_i (0 \leq i < 54)$ が未知の値で、他に出てくる値はすべて既知です。よって、すべての条件は線形な式で表されています。*5

未知数がとる値の範囲が他の値と比べて小さい、出てくる式が線形である、といった点から、LLLを使って解くことができそうだとあたりを付けることができます。

LLLはCTFにおいてかなり頻出のアルゴリズムで、競技プログラマであれば使うのはそれほど難しくないため、早めに慣れておくと便利かなと思います。*6
LLLについて非常に雑に説明すると、行列 $M$ に対し、行ベクトル $a$ を $b = a M$ 　のノルムが"いい感じに小さく"なるようにとったときの $b$ の値を求めることができます。
（LLL自体の説明ではなく、LLLを使ってできることについての説明。詳しい説明については他の記事を参照してください。）

計算量は重めの多項式時間で、行列のサイズが $200 \times 200$ くらいまでなら動くと思っておけばいいと思います。
問題に"いい感じに小さい"値が出てきたときは、その値が右辺に来るような線型方程式をうまく立てることによってLLLで解ける形に持っていくことができることが多いです。

それでは、LLLに使う式を立てていきます。

RollingHashの式はそのまま使って $\sum_{i=0}^{53} s_i \mathrm{base}^i - \mathrm{target}_j - k_j p_j = 0$ です。
更に、 $s_i$ は値域の中心である $\lfloor (97+122)/2 \rfloor = 109$ に近い値を取ってほしい、つまり $s_i - 109$ が小さい値になってほしいです。次のような行列を立てます。

$M = \begin{pmatrix} 1 & & & B \cdot \mathrm{base}_0^0 & B \cdot \mathrm{base}_1^0 & B \cdot \mathrm{base}_2^0 & \\ & \ddots & & \vdots & \vdots & \vdots & \\ & & 1 & B \cdot \mathrm{base}_0^{53} & B \cdot \mathrm{base}_1^{53} & B \cdot \mathrm{base}_2^{53} & \\ & & & B \cdot p_0 & & & \\ & & & & B \cdot p_1 & & \\ & & & & & B \cdot p_2 & \\ 109 & 109 & 109 & B \cdot \mathrm{target}_0 & B \cdot \mathrm{target}_1 & B \cdot \mathrm{target}_2 & 1 \\ \end{pmatrix} \\ a = \begin{pmatrix} s_0 & \cdots & s_{53} & k_0 & k_1 & k_2 & -1 \end{pmatrix}, \\ b = \begin{pmatrix} s_0-109 & \cdots & s_{53}-109 & 0 & 0 & 0 & -1 \end{pmatrix}$
$M$ に左から $a$ を掛けるとノルムの小さいベクトル $b$ になるため、LLLの出力には $b$ が現れることが期待できます。LLLは実際には行ベクトルではなく行列を出力としていて、各行が $b$ としてありうるノルムの小さいベクトルとなっています。それぞれの行を見て $s_i$ の値域が条件を満たさないものなどを除くと解が得られます。
LLLではベクトルの各要素が同程度の大きさ(bit数)の値になるように重みを調節することが大切です。 $55$ から $57$ 列目には $0$ が出てきてほしいため、他の列より小さくなるよう $B = 128$ 倍しています（特に $128$ という数字に意味があるわけではありません）。
LLLはsagemathのライブラリを使うのが簡単です。

ソルバ

from sage.all import *
from pwn import *
import json

so = remote("xxx.xxx.xxx.xxx", 0)
params = json.loads(so.recvline().removeprefix(b"params: "))
for _ in range(3):
    target_hash = json.loads(so.recvline().removeprefix(b"target: "))
    print(target_hash)

    MAX_LEN = 54
    B = 128
    M = Matrix(ZZ, MAX_LEN+4, MAX_LEN+4)
    for i in range(MAX_LEN):
        M[i, i] = 1
        M[MAX_LEN+3, i] = 109
        M[i, MAX_LEN+0] = pow(params[0]["base"], i, params[0]["p"]) * B
        M[i, MAX_LEN+1] = pow(params[1]["base"], i, params[1]["p"]) * B
        M[i, MAX_LEN+2] = pow(params[2]["base"], i, params[2]["p"]) * B
    M[MAX_LEN+0,MAX_LEN+0] = params[0]["p"] * B
    M[MAX_LEN+1,MAX_LEN+1] = params[1]["p"] * B
    M[MAX_LEN+2,MAX_LEN+2] = params[2]["p"] * B
    M[MAX_LEN+3,MAX_LEN+0] = target_hash[0] * B
    M[MAX_LEN+3,MAX_LEN+1] = target_hash[1] * B
    M[MAX_LEN+3,MAX_LEN+2] = target_hash[2] * B
    M[MAX_LEN+3,MAX_LEN+3] = 1

    M = M.LLL()
    for row in M:
        if row[-1] != -1:
            continue
        s = [chr(ch + 109) for ch in row[:MAX_LEN]]
        if not ('a' <= min(s) and max(s) <= 'z'):
            continue
        if list(row[MAX_LEN:-1]) != [0, 0, 0]:
            continue
        s = "".join(s)
        print(s)
        so.sendlineafter(b"> ", s.encode())
        break
print(so.recvline())

*1:当たり前ですが重要なこととして、未知数は少ないほうが嬉しいです

*2:素数定理から言えますが、こういうのは色々実験して発見するほうが早いと思います

*3:この問題では $a, b$ 以外の値の大きさは重要ではありませんが、出てくるの値の大きさを考えるというのはCTFにおいてはかなり重要な考察です

*4:Cryptoに限らないCTF典型として、ソースコードに書かれているコメントは大体ヒントです

*5:未知数に関する二次式は条件としてかなり扱いにくく、線形だと結構うれしいことが多いです。そういう場合はCoppersmith's Methodとかを持ち出したりすることもあります

*6:アルゴリズム自体の理論や証明は難しめです

01-Translator (280 solves)

Elliptic4b (171 solves)

Golden Ticket (35 solves)

mathmyth (79 solves)

RSARSARSARSARSARSA (39 solves)

OTEC (21 solves)

Flag Sharing (6 solves)

Zero-sum game (3 solves)

総評

~Day0

Day1

Day2

Day3

Semifinals

Finals

Day4

qrime

ソルバ

おまけ

Rainbow Sweet Alchemist

ソルバ

A Dance of Add and Mul

ソルバ

Hat Trick

ソルバ