note

CakeCTF 2023 Writeup

Table of Contents

はじめに

2023/11/11-12にかけて開催されたCakeCTF 2023にチームBunkyoWesternsのメンバーとして参加しました。Internationalでは3/729位でした。

例によってチームメンバーが強すぎて僕はほぼ何もしていないのですが、名ばかりのWriteupを残しておきます。

proたちのWriteupは以下の通りです。

Rev

Cake Puzzle(56 solved/128pts)

Someone cut a cake and scrambled. nc others.2023.cakectf.com 14001

チームメンバーのpr0xyさんが次のメモを残してくれていたので続きを巻き取りました。

0x4080のMの配列を0x11b5関数のチェックを満たすように(降順にソート)できれば勝ち

M = [0x445856db,0x4c230304,0x0022449f,0x671a96b7,0x6c5644f7,0x7ff46287,0x6ee9c829,0x5cda2e72,0x00000000,0x698e88c9,0x33e65a4f,0x50cc5c54,0x1349831a,0x53c88f74,0x25858ab9,0x72f976d8]

def check():
    for i in range(3):
        for j in range(3):
            if M[i*4 + j] >= M[i*4 + j+1]:
                return 1
            if M[i*4 + j] >= M[(i+1)*4 + j]:
                return 1
    return 0

def exchange(idx1, idx2):
    M[idx1], M[idx2] = M[idx2], M[idx1]

def search0():
    for i in range(3):
        for j in range(3):
            if M[i*4 + j] == 0:
                return (i,j)

def win():
    print("OK")

def chall():
    while True:
        if check() == 0:
            win()
            break

        c = input()[0]
        idx1, idx2 = search0()
        if c == 'U':
            exchange(idx1*4 + idx2, (idx1-1)*4 + idx2)
        elif c == 'R':
            exchange(idx1*4 + idx2, (idx1-1)*4 + idx2+1 )
        elif c == 'D':
            exchange(idx1*4 + idx2, (idx1+1)*4 + idx2)
        elif c == 'L':
            exchange(idx1*4 + idx2, (idx1-1)*4 + idx2-1)

chall()

はい、スライドパズルですね。

上記のスクリプトのバグっている部分を修正して、手動で操作したログを同時に出力してくれるスクリプトは以下の通りです。

# M = [
#     0x445856DB,
#     0x4C230304,
#     0x0022449F,
#     0x671A96B7,
#     0x6C5644F7,
#     0x7FF46287,
#     0x6EE9C829,
#     0x5CDA2E72,
#     0x00000000,
#     0x698E88C9,
#     0x33E65A4F,
#     0x50CC5C54,
#     0x1349831A,
#     0x53C88F74,
#     0x25858AB9,
#     0x72F976D8,
# ]

# Mの値をスライドパズルの0〜15に置き換える
# sorted_indices = sorted(range(len(M)), key=lambda i: M[i])
# sorted_M = [M[i] for i in sorted_indices]
# ans = [0 for i in range(len(M))]
# for i in range(len(M)):
#     for j in range(len(M)):
#         if sorted_M[i] == M[j]:
#             ans[j] = i
#             break

# Mの値をスライドパズルの0〜15に置き換えたもの
M = [5, 6, 1, 10, 12, 15, 13, 9, 0, 11, 4, 7, 2, 8, 3, 14]

inp = []


def printM(m=M):
    for i in range(4):
        for j in range(4):
            print(f"{m[i*4+j]:11d}", end="")
        print()
    print("".join(inp))
    print("-" * 43)


def check():
    for i in range(4):
        for j in range(4):
            if M[i * 4 + j] >= M[i * 4 + j + 1]:
                return 1
            if M[i * 4 + j] >= M[((i + 1) * 4 + j) % 16]:
                return 1
    return 0


def exchange(idx1, idx2):
    M[idx1], M[idx2] = M[idx2], M[idx1]


def search0():
    for i in range(4):
        for j in range(4):
            if M[i * 4 + j] == 0:
                return (i, j)


def win():
    print("OK")


def chall():
    while True:
        printM()
        if check() == 0:
            win()
            break
        c = input()[0]
        inp.append(c)
        idx1, idx2 = search0()
        if c == "U":
            exchange(idx1 * 4 + idx2, (idx1 - 1) * 4 + idx2)
        elif c == "R":
            exchange(idx1 * 4 + idx2, idx1 * 4 + idx2 + 1)
        elif c == "D":
            exchange(idx1 * 4 + idx2, (idx1 + 1) * 4 + idx2)
        elif c == "L":
            exchange(idx1 * 4 + idx2, idx1 * 4 + idx2 - 1)


chall()
print(inp)

一応ソルバを書こうかと思ったのですが、ググるとめぼしいソルバが見つからなかったので、手動でガチャガチャして解きました。スライドパズル　コツなどでググると、解き方を履修できるので30分くらい履修して解きました。

手元でガチャガチャすると、UURRRDLLDDLURRRULDDRUULDDLRRULLDRULLDRRRULDRULLDRRULDLLURRRUULDLDRRUULDDRUULDRULLLDDRRRULLURDRULLDRURDLULDRULDRRULLRDLLURRRDLLLURRDLLURRDLLURDRULDLURDRRULLLDRRRLLURRDLULDUDLUDRRRULLDLU というペイロードが得られるので、それを投げるとflagが得られます。

(*'-') < solve.py   
s = "UURRRDLLDDLURRRULDDRUULDDLRRULLDRULLDRRRULDRULLDRRULDLLURRRUULDLDRRUULDDRUULDRULLLDDRRRULLURDRULLDRURDLULDRULDRRULLRDLLURRRDLLLURRDLLURRDLLURDRULDLURDRRULLLDRRRLLURRDLULDUDLUDRRRULLDLU"

from pwn import *

io = remote("others.2023.cakectf.com", 14001)

for ch in s:
    io.recvuntil(b"> ")
    io.sendline(ch.encode())
print(io.recvuntil(b"\n"))
(*'-') < python solve.py
[+] Opening connection to others.2023.cakectf.com on port 14001: Done
b'CakeCTF{wh0_at3_a_missing_pi3c3_0f_a_cak3}\n'
[*] Closed connection to others.2023.cakectf.com port 14001

絶対にもっと綺麗な解き方がありますが、綺麗な解き方にこだわってflagが取れなければ本末転倒だと思うので、今回はガチャガチャしました。

これ、Rev問題ですけど実質Miscという気がしました。

Posted on Nov 12, 2023