MapleCTF 2022 Writeup

Sanity Check (Misc)

Discordに入り、#generalチャネルのトピックを見ると、フラグが書いてあった。

maple{w3lc0m3_t0_m4pl3_c7f!}

brsaby (Crypto)

RSA暗号。以下のhintの値を使ってNを素因数分解する。

hint = p**4 - q**3

hint * p**3 = p**7 - p**3 * q**3 = p**7 - n**3
　　　　↓
p**7 - hint * p**3 - N**3 = 0

この7次方程式を解くと、p, qがわかり、通常通り復号することができる。

#!/usr/bin/env sage
from Crypto.Util.number import *

N = 134049493752540418773065530143076126635445393203564220282068096099004424462500237164471467694656029850418188898633676218589793310992660499303428013844428562884017060683631593831476483842609871002334562252352992475614866865974358629573630911411844296034168928705543095499675521713617474013653359243644060206273
e = 65537
enc = 110102068225857249266317472106969433365215711224747391469423595211113736904624336819727052620230568210114877696850912188601083627767033947343144894754967713943008865252845680364312307500261885582194931443807130970738278351511194280306132200450370953028936210150584164591049215506801271155664701637982648648103
hint = 20172108941900018394284473561352944005622395962339433571299361593905788672168045532232800087202397752219344139121724243795336720758440190310585711170413893436453612554118877290447992615675653923905848685604450760355869000618609981902108252359560311702189784994512308860998406787788757988995958832480986292341328962694760728098818022660328680140765730787944534645101122046301434298592063643437213380371824613660631584008711686240103416385845390125711005079231226631612790119628517438076962856020578250598417110996970171029663545716229258911304933901864735285384197017662727621049720992964441567484821110407612560423282

p = var('p')
sol = solve(p**7 - hint * p**3 - N**3, p)
p = int(sol[0].rhs())
q = N // p
assert N == p * q

phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m = int(pow(enc, d, int(N)))
flag = long_to_bytes(m).decode()
print(flag)

maple{s0lving_th3m_p3rf3ct_r000ts_1s_fun}

jwt (Crypto)

app.pyの処理を整理する。

・dbに以下のユーザを登録する。
　username: "admin"
　password: ランダム32バイトの16進数

■/register (GET/POST)
[POST]
・username: POSTデータのusername
・password: POSTデータのpassword
・usernameとpasswordのどちらかががない場合、エラー
・usernameが登録済みである場合、エラー
・username, passwordでユーザ登録する。
[GET]
・登録画面表示

■/login (GET/POST)
[POST]
・username: POSTデータのusername
・password: POSTデータのpassword
・登録済みのユーザとusername, passwordが一致した場合
　・token = jwt.sign({"user": username})
　・tokenをクッキーにセットして、/homeにリダイレクト
[GET]
・ログイン画面表示

■/logout (GET/POST)
・クッキーのtokenを空にセット
・ログイン画面にリダイレクト

■/home (GET)
・"admin"だったら、フラグを表示

adminのtokenを算出することができたら、フラグが得られる。次にjwtのsignの仕組みも確認する。

■パラメータ
・G = secp256k1.G
・order = secp256k1.q
・private: 固定値(不明)
・public: G * private

■sign
・header: '{"alg":"ES256","typ":"JWT"}'のURLセーフbase64エンコード
・data: '{"user":"[username]"}'のURLセーフbase64エンコード
・r, s = _sign(header + "." + data)
　・z: header + "." + dataのsha256ダイジェスト
　・k: private
　・z: zの数値化
　・r: (k * G).x
　・s: inverse(k, order) * (z + r * private) % order
　・r, sを返却
・signature = r.to_bytes(32, "little") + s.to_bytes(32, "little")
・header + "." + data + "." + signatureのURLセーフbase64エンコード

signはECDSAを使用しているが、kは固定なため、異なるユーザのtokenを入手すれば、kを算出できる。

z1 = int(sha256(header + "." + data1).hexdigest(), 16)
z2 = int(sha256(header + "." + data2).hexdigest(), 16)
k = (z1 - z2) * inverse(s1 - s2, order) % order

kを算出すれば、どのユーザのsignも算出できる。このため2ユーザのtokenを入手する。
noraユーザを登録すると以下のtokenが設定される。

eyJhbGciOiJFUzI1NiIsInR5cCI6IkpXVCJ9.eyJ1c2VyIjoibm9yYSJ9.75J83TiCMONIDtDLvDQ8FKHa4wx7DNHkauX-Izu11S-5p2wPx1oWQfa4r7s7R8jwRocJgrEr397mhlUZ39x1lw

necoユーザを登録すると以下のtokenが設定される。

eyJhbGciOiJFUzI1NiIsInR5cCI6IkpXVCJ9.eyJ1c2VyIjoibmVjbyJ9.75J83TiCMONIDtDLvDQ8FKHa4wx7DNHkauX-Izu11S-YiA-7ZjLf5wJUld4EO_p-3JM9aryUSeL45R4JqaKLCQ

この情報を使って、adminのtokenを算出する。

#!/usr/bin/env python3
from Crypto.Util.number import bytes_to_long as bl, inverse
from fastecdsa.curve import secp256k1
from base64 import urlsafe_b64decode, urlsafe_b64encode
from hashlib import sha256
from json import loads, dumps

def b64decode(msg: str) -> bytes:
    if len(msg) % 4 != 0:
        msg += "=" * (4 - len(msg) % 4)
    return urlsafe_b64decode(msg.encode())

def b64encode(msg: bytes) -> str:
    return urlsafe_b64encode(msg).decode().rstrip("=")

G = secp256k1.G
order = secp256k1.q

token1 = 'eyJhbGciOiJFUzI1NiIsInR5cCI6IkpXVCJ9.eyJ1c2VyIjoibm9yYSJ9.75J83TiCMONIDtDLvDQ8FKHa4wx7DNHkauX-Izu11S-5p2wPx1oWQfa4r7s7R8jwRocJgrEr397mhlUZ39x1lw'
token2 = 'eyJhbGciOiJFUzI1NiIsInR5cCI6IkpXVCJ9.eyJ1c2VyIjoibmVjbyJ9.75J83TiCMONIDtDLvDQ8FKHa4wx7DNHkauX-Izu11S-YiA-7ZjLf5wJUld4EO_p-3JM9aryUSeL45R4JqaKLCQ'

_header1, _data1, _signature1 = token1.split('.')
_header2, _data2, _signature2 = token2.split('.')
header1 = loads(b64decode(_header1))
header2 = loads(b64decode(_header2))
data1 = loads(b64decode(_data1))
data2 = loads(b64decode(_data2))
signature1 = b64decode(_signature1)
signature2 = b64decode(_signature2)
assert header1['alg'] == 'ES256' and header1['typ'] == 'JWT'
assert header2['alg'] == 'ES256' and header2['typ'] == 'JWT'
assert data1['user'] == 'nora'
assert data2['user'] == 'neco'

r1 = int.from_bytes(signature1[:32], 'little')
r2 = int.from_bytes(signature2[:32], 'little')
s1 = int.from_bytes(signature1[32:], 'little')
s2 = int.from_bytes(signature2[32:], 'little')
assert r1 == r2

z1 = sha256((_header1 + '.' + _data1).encode()).digest()
z2 = sha256((_header2 + '.' + _data2).encode()).digest()
z1 = bl(z1)
z2 = bl(z2)
k = (z1 - z2) * inverse(s1 - s2, order) % order

username = 'admin'
data = {"user": username}
header = b64encode(
    dumps({"alg": "ES256", "typ": "JWT"}).replace(' ', '').encode()
)
data = b64encode(dumps(data).replace(' ', '').encode())
z = sha256((header + '.' + data).encode()).digest()
z = bl(z)
r = (k * G).x
s = inverse(k, order) * (z + r * k) % order
signature = r.to_bytes(32, 'little') + s.to_bytes(32, 'little')
token = header + '.' + data + '.' + b64encode(signature)
print(token)

adminのtokenの算出結果は以下の通り。

eyJhbGciOiJFUzI1NiIsInR5cCI6IkpXVCJ9.eyJ1c2VyIjoiYWRtaW4ifQ.75J83TiCMONIDtDLvDQ8FKHa4wx7DNHkauX-Izu11S8IDLHy2P7MGS7FfPJpZagBzl8OHNHGZalfdll8sV55Kg

このtokenをクッキーにセットして、http://jwt.ctf.maplebacon.org/homeにアクセスすると、フラグが表示された。

maple{3ll1pt!c_c2rv3s_f7w!!!}

Spiral-baby (Crypto)

サーバの処理概要は以下の通り。

・key: ランダム16バイト
・cipher = Spiral(key, rounds=1)
　・cipher.rounds = 1
　・self.keys = [bytes2matrix(key)]
　・self.BLOCK_SIZE = 16
　・self.keys.append(spiralLeft(self.keys[-1]))
　　行列を90°左回転したものを追加
・メニュー表示
・以下繰り返し
　・option: 入力
　・optionが1の場合
　　・ciphertext = cipher.encrypt(flag)→16進数表記で表示
　・optionが2の場合
　　・plaintext: 16進数表記で入力→デコード
　　・ciphertext = cipher.encrypt(plaintext)→16進数表記で表示

■cipher.encrypt(plaintext)
・plaintext: plaintextの長さを16で割り切れない場合はパディング
・16バイトごとにencrypt_block([平文ブロック])して結合
　・self.state: [平文ブロック]を4x4の行列に整形
　・self.add_key(0)
　　・self.stateの行列の各要素で(state[i][j] + keys[0][i][j]) % 255を設定
　・self.substitute()
　　・self.stateの行列の各要素でSBOXの値を設定
　・self.rotate()
　　・self.stateの行列を右回転
　・self.add_key(1)
　　・self.stateの行列の各要素で(state[i][j] + keys[1][i][j]) % 255を設定

いくつか試したところ、鍵の各文字を変更すると、暗号が変わる文字が決まり、以下のようになる。

・鍵：0文字目→暗号：3, 12文字目
・鍵：1文字目→暗号：7, 8文字目
・鍵：2文字目→暗号：11, 4文字目
・鍵：3文字目→暗号：15, 0文字目
・鍵：4文字目→暗号：2, 13文字目
・鍵：5文字目→暗号：6, 9文字目
・鍵：6文字目→暗号：10, 5文字目
・鍵：7文字目→暗号：14, 1文字目
・鍵：8文字目→暗号：1, 14文字目
・鍵：9文字目→暗号：5, 10文字目
・鍵：10文字目→暗号：9, 6文字目
・鍵：11文字目→暗号：13, 2文字目
・鍵：12文字目→暗号：0, 15文字目
・鍵：13文字目→暗号：4, 11文字目
・鍵：14文字目→暗号：8, 7文字目
・鍵：15文字目→暗号：12, 3文字目

このことを元に、ブルートフォースで鍵を求めることができる。鍵がわかれば、あとはその鍵で復号すればよい。その際、spiral.pyに復号コードを追加して、以下のコードでspiral_plus.pyとして保存する。

from utils import *


class Spiral:
    def __init__(self, key, rounds=4):
        self.rounds = rounds
        self.keys = [bytes2matrix(key)]
        self.BLOCK_SIZE = 16

        for i in range(rounds):
            self.keys.append(spiralLeft(self.keys[-1]))

    def encrypt(self, plaintext):
        if len(plaintext) % self.BLOCK_SIZE != 0:
            padding = self.BLOCK_SIZE - len(plaintext) % self.BLOCK_SIZE
            plaintext += bytes([padding] * padding)

        ciphertext = b""
        for i in range(0, len(plaintext), 16):
            ciphertext += self.encrypt_block(plaintext[i : i + 16])
        return ciphertext

    def encrypt_block(self, plaintext):
        self.state = bytes2matrix(plaintext)
        self.add_key(0)

        for i in range(1, self.rounds):
            self.substitute()
            self.rotate()
            self.mix()
            self.add_key(i)

        self.substitute()
        self.rotate()
        self.add_key(self.rounds)

        return matrix2bytes(self.state)

    def add_key(self, idx):
        for i in range(4):
            for j in range(4):
                self.state[i][j] = (self.state[i][j] + self.keys[idx][i][j]) % 255

    def substitute(self):
        for i in range(4):
            for j in range(4):
                self.state[i][j] = SBOX[self.state[i][j]]

    def rotate(self):
        self.state = spiralRight(self.state)

    def mix(self):
        out = [[0 for _ in range(4)] for _ in range(4)]
        for i in range(4):
            for j in range(4):
                for k in range(4):
                    out[i][j] += SPIRAL[i][k] * self.state[k][j]
                out[i][j] %= 255

        self.state = out

#### add decrypt functions ####
    def decrypt_round1(self, ciphertext):
        plaintext = b""
        for i in range(0, len(ciphertext), 16):
            plaintext += self.decrypt_block_round1(ciphertext[i : i + 16])

        padding = plaintext[-1]
        if padding < 16:
            plaintext = plaintext[:- padding]

        return plaintext

    def decrypt_block_round1(self, ciphertext):
        self.state = bytes2matrix(ciphertext)

        self.sub_key(self.rounds)
        self.rev_rotate()
        self.rev_substitute()
        self.sub_key(0)

        return matrix2bytes(self.state)

    def sub_key(self, idx):
        for i in range(4):
            for j in range(4):
                self.state[i][j] = (self.state[i][j] - self.keys[idx][i][j]) % 255

    def rev_substitute(self):
        for i in range(4):
            for j in range(4):
                self.state[i][j] = SBOX.index(self.state[i][j])

    def rev_rotate(self):
        self.state = spiralLeft(self.state)

#!/usr/bin/env python3
import socket
from spiral_plus import Spiral

def recvuntil(s, tail):
    data = b''
    while True:
        if tail in data:
            return data.decode()
        data += s.recv(1)

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('spiral-baby.ctf.maplebacon.org', 1337))

data = recvuntil(s, b'message\n').rstrip()
print(data)

data = recvuntil(s, b'>>> ')
print(data + '1')
s.sendall(b'1\n')
data = recvuntil(s, b'\n').rstrip()
print(data)
flag_ct = bytes.fromhex(data)

try_pt1 = b'a' * 16
data = recvuntil(s, b'>>> ')
print(data + '2')
s.sendall(b'2\n')
print(try_pt1.hex())
s.sendall(try_pt1.hex().encode() + b'\n')
data = recvuntil(s, b'\n').rstrip()
print(data)
try_ct1 = bytes.fromhex(data)

try_pt2 = b'b' * 16
data = recvuntil(s, b'>>> ')
print(data + '2')
s.sendall(b'2\n')
print(try_pt2.hex())
s.sendall(try_pt2.hex().encode() + b'\n')
data = recvuntil(s, b'\n').rstrip()
print(data)
try_ct2 = bytes.fromhex(data)

ct_index = [[3, 12], [7, 8], [11, 4], [15, 0], [2, 13], [6, 9], [10, 5], [14, 1]]

key = [bytes([0])] * 16
for i in range(8):
    found = False
    for k1 in range(256):
        for k2 in range(256):
            try_key = [bytes([0])] * 16
            try_key[i] = bytes([k1])
            try_key[15 - i] = bytes([k2])
            try_key = b''.join(try_key)

            cipher = Spiral(try_key, rounds=1)
            ct = cipher.encrypt(try_pt1)
            index1 = ct_index[i][0]
            index2 = ct_index[i][1]
            if ct[index1] == try_ct1[index1] and ct[index2] == try_ct1[index2]:
                ct = cipher.encrypt(try_pt2)
                if ct[index1] == try_ct2[index1] and ct[index2] == try_ct2[index2]:
                    found = True
                    key[i] = try_key[i]
                    key[15 - i] = try_key[15 - i]
                    break
        if found:
            break

key = b''.join([bytes([k]) for k in key])

cipher = Spiral(key, rounds=1)
flag = cipher.decrypt_round1(flag_ct).decode()
print(flag)

実行結果は以下の通り。

Options:
1. Get encrypted flag
2. Encrypt message
>>> 1
239dc87cec599517111cbd9e48775c9cd0a081b05ee50778271cfbb2cd53e013ee82cab620f70aa1570f95b8170168f0
>>> 2
61616161616161616161616161616161
f0df0c3a34942517eba7992d00560d46
>>> 2
62626262626262626262626262626262
d01b9ab95b86d1a0a4e2424be0c639b6
maple{0nt0_th3_r34l_sp!r4l_0be088}

maple{0nt0_th3_r34l_sp!r4l_0be088}