この大会は2022/8/27 9:00(JST)～2022/8/29 9:00(JST)に開催されました。
今回もチームで参戦。結果は1411点で618チーム中33位でした。
自分で解けた問題をWriteupとして書いておきます。
brsaby (Crypto)
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}
