Writeup: DownUnderCTF 2021
今週土日に開催されていたDownUnderCTF 2021に出たので自分が解いたCrypto問題のWriteupを書きます。Crypto問題以外も解きましたが、記憶が無いので書きません。
Table of Contents §
- Table of Contents
- Substitution Cipher I
- Substitution Cipher II
- treasure
- Secuchat
- yadlp
- OTWhat 1
- OTWhat 2
- Links
Substitution Cipher I §
次のようなスクリプトとその実行結果(output.txt)が配布される。
def encrypt(msg, f):
return ''.join(chr(f.substitute(c)) for c in msg)
P.<x> = PolynomialRing(ZZ)
f = 13*x^2 + 3*x + 7
FLAG = open('./flag.txt', 'rb').read().strip()
enc = encrypt(FLAG, f)
print(enc)
フラグの各文字を$c$とおくと、$13x^2 + 3x + 7$を計算して別の文字に置換している。
というわけでフラグになり得る文字から逆変換テーブルを生成すれば良い。
import string
def f(x):
return 13*x**2 + 3*x + 7
def create_table():
cs = string.printable
ret = {}
for c in cs:
_c = ord(c)
ret[f(_c)] = c
return ret
def exploit():
enc = open("./output.txt").read()
table = create_table()
flag = ""
for c in enc:
_c = ord(c)
flag += table[_c]
print(flag)
if __name__ == "__main__":
exploit()
Flag: DUCTF{sh0uld'v3_us3d_r0t_13}
Substitution Cipher II §
次のようなスクリプトとその実行結果が与えられる。
from string import ascii_lowercase, digits
CHARSET = "DUCTF{}_!?'" + ascii_lowercase + digits
n = len(CHARSET)
def encrypt(msg, f):
ct = ''
for c in msg:
ct += CHARSET[f.substitute(CHARSET.index(c))]
return ct
P.<x> = PolynomialRing(GF(n))
f = P.random_element(6)
FLAG = open('./flag.txt', 'r').read().strip()
enc = encrypt(FLAG, f)
print(enc)
I同様1文字ずつの変換なので逆変換テーブルを作ればよいのだが、肝心の式がf = P.random_element(6)で知ることが出来ない。
ここでフラグがDUCTF{<text>}の形であるとすれば、7文字分はどの文字に置換されるかが判明する。fが6次の式という事は未知の係数は7つなので$f(x) = ax^6 + bx^5 + cx^4 + dx^3 + ex^2 + fx + g = y$の$x$にフラグフォーマットの各文字を、$y$に対応する暗号文を入れば7元の連立方程式となり、解く事が出来る。
なお、Dに対応するCHARSET.index()が0である事から$g$だけは自明に求まる。よって残りの6つを使って行列に形にして逆行列を左から掛けて解いた(正確にはDに対応する結果を行列に入れると行列式が0になって逆行列が求められないので排除した)。
from string import ascii_lowercase, digits
# GLOBAL (Don't change, touch and abuse them!!)
CHARSET = "DUCTF{}_!?'" + ascii_lowercase + digits
n = len(CHARSET) # 47
F = GF(n)
def get_known_table():
enc = open("./output.txt").read().strip()
known_former = "DUCTF{"
known_latter = "}"
ret = {}
for j, c in enumerate(known_former):
i = CHARSET.index(c)
enc_c = enc[j]
enc_i = CHARSET.index(enc_c)
ret[i] = enc_i
i = CHARSET.index(known_latter)
enc_c = enc[-1]
enc_i = CHARSET.index(enc_c)
ret[i] = enc_i
return ret
def create_matrix():
mat = []
w = []
table = get_known_table()
for k, v in table.items():
if k == 0:
continue
l = []
for i in range(6, 0, -1):
l.append(F(k**i))
mat.append(l)
w.append(F(v-1))
return (mat, w)
def solve(mat, w):
mat = Matrix(F, mat)
w = vector(F, w)
print(mat)
print(w)
inv = mat^(-1)
coefs = inv * w
return coefs
def check(f):
table = get_known_table()
for k, v in table.items():
assert f(k) == F(v)
def decrypt(f):
table = {}
enc = open("./output.txt").read().strip()
for c in CHARSET:
i = CHARSET.index(c)
enc_c = CHARSET[f(i)]
if enc_c not in table:
table[enc_c] = []
table[enc_c].append(c)
print(len(table))
flag = ""
for c in enc:
cand = table[c]
if len(cand) == 1:
flag += cand[0]
flag += " "
else:
flag += "("
for _c in cand:
flag += _c
flag += ", "
flag = flag[:-2]
flag += ") "
return flag
def exploit():
mat, w = create_matrix()
coefs = solve(mat,w)
print(coefs)
PR.<x> = PolynomialRing(F)
f = 1
for e, coef in zip(range(6,0,-1), coefs):
f += coef * x^e
check(f)
flag = decrypt(f)
print(flag)
if __name__ == "__main__":
exploit()
実行結果は次の通り
$ sage exploit.sage
[ 1 1 1 1 1 1]
[17 32 16 8 4 2]
[24 8 34 27 9 3]
[ 7 37 21 17 16 4]
[21 23 14 31 25 5]
[32 21 27 28 36 6]
(19, 34, 32, 41, 13, 40)
(41, 15, 40, 9, 28, 27)
35
D (U, !) C (T, t) F { g o 0 d _ 0 l ' _ l 4 g r 4 (f, n, p) g (3, 8) }
結果に一意性が無いので重複しているところはそれっぽいのを選んだ。
Flag: DUCTF{go0d_0l'_l4gr4ng3}
よく考えたらラグランジュ補間で解けた、どこかで実装済みのはずなのでこれを流用すれば良かった。
treasure §
次のようなスクリプトが動いている。
#!/usr/bin/python3
import re
from Crypto.Util.number import long_to_bytes
from Crypto.Random import random
from secret import REAL_COORDS, FLAG_MSG
FAKE_COORDS = 5754622710042474278449745314387128858128432138153608237186776198754180710586599008803960884
p = 13318541149847924181059947781626944578116183244453569385428199356433634355570023190293317369383937332224209312035684840187128538690152423242800697049469987
def create_shares(secret):
r1 = random.randint(1, p - 1)
r2 = random.randint(1, p - 1)
s1 = r1*r2*secret % p
s2 = r1*r1*r2*secret % p
s3 = r1*r2*r2*secret % p
return [s1, s2, s3]
def reveal_secret(shares):
s1, s2, s3 = shares
secret = pow(s1, 3, p) * pow(s2*s3, -1, p) % p
return secret
def run_combiner(shares):
try:
your_share = int(input('Enter your share: '))
return reveal_secret([your_share, shares[1], shares[2]])
except:
print('Invalid share')
exit()
def is_coords(s):
try:
return re.match(r'-?\d+\.\d+?, -?\d+\.\d+', long_to_bytes(s).decode())
except:
return False
def main():
shares = create_shares(REAL_COORDS)
print(f'Your share is: {shares[0]}')
print(f'Your two friends input their shares into the combiner and excitedly wait for you to do the same...')
secret_coords = run_combiner(shares)
print(f'The secret is revealed: {secret_coords}')
if not is_coords(secret_coords):
print('"Hey those don\'t look like coordinates!"')
print('Your friends grow a bit suspicious, but you manage to convince them that you just entered a digit wrong. You decide to try again...')
else:
print('"Let\'s go get the treasure!!"')
print('Your friends run off to the revealed location to look for the treasure...')
exit()
secret_coords = run_combiner(shares)
if not is_coords(secret_coords):
print('"This is way too sus!!"')
exit()
if secret_coords == FAKE_COORDS:
print('You\'ve successfully deceived your friends!')
try:
real_coords = int(input('Now enter the real coords: '))
if real_coords == REAL_COORDS:
print(FLAG_MSG)
else:
print('Incorrect!')
except:
print('Incorrect!')
else:
print('You are a terrible trickster!')
if __name__ == '__main__':
main()
秘密を$s$とおいて秘密分散をしているようである。シェアを$s_1, s_2, s_3$、乱数を$r_1, r_2$、素数を$p$とおくと、次のような式が成り立つ。
$$ \begin{aligned} s_1 &\equiv r_1r_2s \bmod p \cr s_2 &\equiv r_1^2r_2s \bmod p \cr s_3 &\equiv r_1r_2^2s \bmod p \end{aligned} $$
この式から$s' \equiv \frac{s_1^3}{s_2s_3} \bmod p$を計算すれば秘密が復元される。
シェアの配布の後、シェアの入力が求められ、そこから復元した秘密が開示される。これがもし特定の形式(つまりis_coords()がTrueになる)を満たしていればその場でプログラムは終了する。当然、配られたシェアを与えるとこのような結果になる。
ではis_coords()がFalseになるようなシェアを与えるとどうなるのかというとシェアの再入力を求められる。それを提出して復元された秘密が、is_coords()がTrueでかつ、REAL_COORDSで無いものであれば座標入力に移り、ここでREAL_COORDSを入力すればフラグが開示sあれる。is_coords()がTrueでかつ、REAL_COORDSでないものはFAKE_COORDSとしてソースコード中になるのでこれを利用する。
最初に与えるシェアを$s_1'$、その提出によって復元された秘密を$s'$とおくと$s' \equiv \frac{s_1'^3}{s_2s_3} \bmod p$が成り立つ。ここから$s_2s_3$を求める事が出来る。
よって、FAKE_COORDSを$s_0$とおくと2回目に送信するシェアを$x$とおけば$s_0 \equiv \frac{x^3}{s_2s_3} \bmod p$が成立し、$s_2s_3$はさっき求めたばかりなので$x$は$s_0s_2s_3$の3乗根を取る事で求められる。
ついでにREAL_COORDSを$s$とおけば$s \equiv \frac{s_1}{s_2s_3} \bmod p$から求めることが出来るので最後にこれを送信してフラグを入手する。
使用コードは次の通り(3乗根を求めるのはターミナルで待機させておいたSageの対話環境でやったので無いです、まあ残りは自明なので...)
from pwn import remote
from Crypto.Util.number import long_to_bytes
from xutil.misc import conn_info
# !!GLOBAL!!
# DON'T TOUCH, CHANGE AND ABUSE THEM
FAKE_COORDS = 5754622710042474278449745314387128858128432138153608237186776198754180710586599008803960884
p = 13318541149847924181059947781626944578116183244453569385428199356433634355570023190293317369383937332224209312035684840187128538690152423242800697049469987
def exploit():
host, port = conn_info("nc pwn-2021.duc.tf 31901")
sc = remote(host, port)
sc.recvuntil(b"Your share is: ")
s1 = int(sc.recvline().strip())
invalid_s1 = 114514 # <- what?
sc.recvuntil(b"Enter your share: ")
sc.sendline(str(invalid_s1).encode())
print(invalid_s1)
sc.recvuntil(b"The secret is revealed: ")
invalid_secret = int(sc.recvline().strip())
print(invalid_secret)
r13r23s2 = invalid_s1**3 * pow(invalid_secret, -1, p) % p
secret = s1**3 * pow(r13r23s2, -1, p) % p
print("[+] r1^3 * r2^3 * s2 =", r13r23s2)
print("[+] secret =", secret)
print("[+] REAL_COORDS:", long_to_bytes(secret))
sc.interactive()
if __name__ == "__main__":
exploit()
Flag: DUCTF{m4yb3_th3_r34L_tr34sur3_w4s_th3_fr13nDs_w3_m4d3_al0ng_Th3_W4y.......}
サラッと大切な事がフラグに書いてある
Secuchat §
secuchat.dbというファイルだけが渡される、fileコマンドで調べるとsqlite3のデータベースのダンプらしいので適当なツールで眺めてみる。DB Browser for SQLiteを使用した。
すると概ね次のような構造になっている事がわかる
| table | columns |
|---|---|
| Conversation | id, initiator, pear, initial_parameters |
| Message | conversation, timestamp, from_initiator, next_parameters,encrypted_message |
| Parameters | id, encrypted_aes_key_for_initiator, encrypted_aes_key_for_peer |
| User | username, rsa_key |
Guessすると通信時に相手のrsa_keyで暗号化したencrypted_aes_key_for_[initiator|peer]を使ってメッセージを暗号化し、送信していると思われる。問題のDescriptionからrsa_keyはRSA2048-OAEPに準拠しているキーらしいのでpycryptodomeを使ってパラメータを取り出すと、どれもこれもe = 65537だったのでnが複数ある時の典型である素数の使い回しを疑って確認すると1組だけ共通素数を利用しているのがあった。
というわけである会話に関しては復号出来る事が判明したので総当りを試みる。存在するAES鍵を全部復号し、正しく復号されたもので全メッセージを復号してDUCTFが含まれているものを探したら1つだけあり、そこにフラグが書かれていた。
なお、データベースから鍵やら何やらを取り出すのが面倒だな～って思ってたらkurenaifさんがそれをやってくれるスクリプトを提供してくれました、感謝。
# codes from @kurenaif
# vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
import sqlite3
from Crypto.Cipher import AES, PKCS1_OAEP
from Crypto.PublicKey import RSA
from itertools import combinations
from math import gcd
from string import printable
con = sqlite3.connect('secuchat.db')
cur = con.cursor()
user = []
for row in cur.execute('SELECT * FROM User'):
user.append({'username': row[0], 'rsa_key': row[1]})
conversation = []
for row in cur.execute('SELECT * FROM Conversation'):
conversation.append({
'id': row[0],
'initiator': row[1],
'peer': row[2],
'initial_parameters': row[3]})
message = []
for row in cur.execute('SELECT * FROM Message'):
message.append({
'conversation': row[0],
'timestamp': row[1],
'from_initiator': row[2],
'next_parameters': row[3],
'encrypted_message': row[4]})
parameters = []
keys = []
for row in cur.execute('SELECT * FROM Parameters'):
keys.append([row[1], row[3]])
keys.append([row[2], row[3]])
parameters.append({
'id': row[0],
'encrypted_aes_key_for_initiator': row[1],
'encrypted_aes_key_for_peer': row[2],
'iv': row[3]})
# for m in message:
# for key in keys:
# c = m['encrypted_message']
# print(key[0])
# crypto = AES.new(key[0], AES.MODE_CBC, key[1])
# print(crypto.decrypt(c))
# ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
ns = []
n_to_name = {}
for record in user:
name = record["username"]
key = RSA.importKey(record["rsa_key"])
n = key.n
e = key.e
assert e == 0x10001
ns.append(n)
n_to_name[n] = name
names_to_cipher = {}
for n1, n2 in combinations(ns, 2):
g = gcd(n1, n2)
if g != 1:
print("[+] Found!!")
for n in [n1, n2]:
assert n % g == 0
p,q = g, n // g
d = pow(0x10001, -1, (p-1) * (q-1))
info = (n, 0x10001, d, p, q)
_key = RSA.construct(info, consistency_check=True)
names_to_cipher[n_to_name[n]] = PKCS1_OAEP.new(_key)
all_aes_keys = []
for params in parameters:
iv = params["iv"]
key1 = params["encrypted_aes_key_for_initiator"]
key2 = params["encrypted_aes_key_for_peer"]
all_aes_keys.append((key1, iv))
all_aes_keys.append((key2, iv))
valid_aes_keys = []
for enc_key, iv in all_aes_keys:
for _, cipher in names_to_cipher.items():
try:
key = cipher.decrypt(enc_key)
except ValueError:
continue
print(len(key), key)
valid_aes_keys.append((key, iv))
print(f"[+] {len(valid_aes_keys)} keys are decrypted")
for record in message:
m = record["encrypted_message"]
for aes_key, iv in valid_aes_keys:
cipher = AES.new(aes_key, AES.MODE_CBC, iv)
pt = cipher.decrypt(m)
print(pt)
Flag: DUCTF{pr1m1t1v35, p4dd1ng, m0d35- wait, 3n7r0py?!}
yadlp §
チームメイトのDronex君との共闘です。
次のようなスクリプトとその実行結果(output.txt)が渡される。
def G_add(A, B):
x1, y1 = A
x2, y2 = B
return ((x1*x2 + D*y1*y2) % p, (x1*y2 + x2*y1 + 2*y1*y2) % p)
def G_mul(A, k):
out = (1, 0)
while k > 0:
if k & 1:
out = G_add(out, A)
A = G_add(A, A)
k >>= 1
return out
def rand_element():
while True:
x = randint(1, p-1)
d = x^2 * (D + 1) - D
if (x & 1 == d & 1) and kronecker(d, p) == 1:
y = (x + sqrt(Zmod(p)(d))) * inverse_mod(D, p) % p
return (x, y)
D = 13337
p = 17568142778435152362975498611159042138909402642078949814477371651322179417849164549408357464774644525711780515232117470272550677945089719112177956836141583
assert p.nbits() >= 512
assert ((p-1)//2).is_prime() # safe prime
FLAG = open('flag.txt', 'rb').read().strip()
assert len(FLAG) % 8 == 0
M = [int.from_bytes(FLAG[i:i+8], 'big') for i in range(0, len(FLAG), 8)]
G = [rand_element() for _ in M]
c = (1, 0)
for m, gi in zip(M, G):
c = G_add(c, G_mul(gi, m))
print(f'{D = }')
print(f'{p = }')
print(f'{G = }')
print(f'{c = }')
楕円曲線上の有理点群と似たような曲線上の有理点群が用意され、その上でDLPを解く問題のようである。有理点が幾つか与えられているので$ax^2 + by^2 + cxy + dx + ey + f \equiv 0 \bmod p$となるような係数を探したところ$x^2 - Dy^2 + 2xy - 1 \equiv 0 \bmod p$である事がわかった。
ちなみに、この形であることは行列を上手く立てて行列式を計算したらわかり、それを伝えたらDronexがパラメータまで特定してくれた。
さて、この形は双曲線と似ており、Dronexによれば双曲線を回転させたものらしい。終了後に知ったが、双曲線の一般的な定義が英語版Wikipediaにあった。
というわけで"hyperbolic curve discrete log"とかで調べるとこの論文に辿り着き、これによれば$p \equiv 3 \bmod 4$の場合、位数は$p+1$になるらしい、FactorDBにこいつを突っ込んでみると如何にもPohlig-Hellmanが使えそうな感じに素因数分解される。
というわけでBaby-Step and Giant-StepとPohlig-Hellmanアルゴリズムを実装すれば離散対数問題は解ける。これはDronexが書いてくれた。
さて、問題は普通だったらc = flag * Gみたいな形でflagが特定出来る事が多いのだが、今回はそうもいかない。具体的にはフラグを複数(6つ)に分割して$m_i$のようにおき、同様にGの各要素も$G_i$のようにおくと$c = \sum_{i=1}^6 m_iG_i$のようになっている。
ここで$G_6$が原始根である事が判明したのでここから各$G_i$に対して離散対数問題を解いた結果を$g_i$、$c$に対して離散対数問題を解いた結果を$n$とおくと次のようになっている($k$は整数)。
$$ \begin{aligned} nG_6 &= \left\{\sum_{i=1}^5 (m_ig_i)\right\}G_6 + m_6G_6 \cr \Rightarrow n &\equiv \sum_{i=1}^5 m_ig_i + m_6 \bmod p+1 \cr \Rightarrow n &- \sum_{i=1}^5 m_ig_i - k(p+1) = m_6 \end{aligned} $$
ここから次のような格子(基底は列ベクトル)を組んで右から$(1, m_1, m_2, m_3, m_4, m_5, k)^\mathrm T$を掛けると$(m_6, m_1, m_2, m_3, m_4, m_5, k)$になる。
$$ \left( \begin{matrix} n & -g_1 & -g_2 & -g_3 & -g_4 & -g_5 & -(p+1) \cr & 1 \cr & & 1 \cr & & & 1 \cr & & & & 1 \cr & & & & & 1 \cr & & & & & & 1 \cr \end{matrix} \right) $$
この格子の体積はだいたい$2^{512}$で、$m_i$は64bitなのでLLLで出てくる小さな基底の上界${2^{512}}^{1/7} \approx 2^{73}$よりも小さく、遠くもない。よって上手く出てくれそうである。
from pwn import remote
from Crypto.Util.number import long_to_bytes, bytes_to_long
import base64
import json
# !!GLOBAL!!
# DON'T TOUCH, CHANGE AND ABUSE THEM
CONN_INFO = ""
D = 13337
p = 17568142778435152362975498611159042138909402642078949814477371651322179417849164549408357464774644525711780515232117470272550677945089719112177956836141583
G = [(8249149405495350491346934933585109414510787432598250096114687570379053133508711862485128035174547571919256235441699899388417666835599315963507480727674285, 10151966144947987666795899106244951506314545969111450078363915090201899029695981970354886015549281568762501638756950135017679627954071369058817947706039379), (10148658254415475588279956574772196898575718154643967163626694400363009168529645860280959810873028393970853643723425023678857408220330929116526467295542507, 3332426625916817700349475905733631656792492189677766534230576987725484499618918928882667666640821403823057239790395654518704427126712280655564669757208129), (1839326681086939925214853980855626023120414606039474419455499625885357274275815189399880356995376514021329118829062071144818562457268892324773839713533977, 17502649671831125396398431215302241914145169143474764941575812028922929277656849105757332346628455059539582448544435155655055157181361580680672298566085040), (3165955958968203879237344349962533642598441044481692770147807839372942715856047580766073222297692574025922260374409920417665600069665162502514403188432579, 9382092026348588885644924948782239369051861025018411316856012639637274661831713783735305424388410778778529413114167923397187236739639802371814632949741663), (8500294063291124527108623281980255870507549734362604259645984044370658620385351338711051998886026260657132944353675335178871934798200163035190278483491633, 7641198814027309580920446604109217188703337221305342467525089149977505415741300885194767452232679123441594451455097533000754553745051816419202345186703390), (12352685673550986453697035560006632628194788902921398545668828437339873544223895997440585227838919968929669738393535610103382084842900404005432007637193943, 2453949984320580417885537763124479618094084392655766673219227195157341323190069350175423869908524758510177197973709821798974003013596311361995273762475822)]
c = (5388567167658786935158413401674168420144429277172064721472662913563775670320298461949979362402157764272762755236320989018989446360740720072488623102776015, 7420389277336940268114831002964626027945367662485419944369852006741899961686908509331719915794976159062761271182318814519641566938538911041229521838799714)
order = p+1
# from factorDB
factors = [(2, 4), (3, 3), (3271, 1), (18119, 1), (23857, 1), (35923, 1), (1505323, 1), (3036643, 1), (3878597, 1), (7306661, 1), (661850419, 1), (696183413, 1), (737026033, 1), (748888849, 1), (764475661, 1), (790916521, 1), (1000657271, 1), (1016247923, 1), (1213865039, 1), (2090081803, 1), (3882107087, 1), (4012893277, 1)]
def G_add(A, B):
x1, y1 = A
x2, y2 = B
return ((x1*x2 + D*y1*y2) % p, (x1*y2 + x2*y1 + 2*y1*y2) % p)
def G_mul(A, k):
out = (1, 0)
while k > 0:
if k & 1:
out = G_add(out, A)
A = G_add(A, A)
k >>= 1
return out
# codes from my team mate: Dronex
# vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
def G_inv(g):
return Matrix(Zmod(p), [[g[0], D*g[1]], [g[1], (g[0]+2*g[1])]]).solve_right(vector(Zmod(p),[1, 0]))
def G_bsgs(base, y, order):
if base == (1, 0):
if y != (1, 0):
raise ValueError("no solution")
return None # このDLPは意味がない
assert G_mul(base, order) == (1, 0)
dic = {}
m = ceil(sqrt(order))
z = (1, 0)
for i in range(m):
dic[z] = i
z = G_add(z, base)
z = G_mul(G_inv(base), m)
for i in range(m):
if y in dic:
return (dic[y] + i*m) % order
y = G_add(y, z)
raise RuntimeError("maybe bug")
def G_log(base, y):
ps = []
ms = []
for f, d in factors:
f = f ** d
phi = (p+1) // f
bb = G_mul(base, phi)
yy = G_mul(y, phi)
order = G_bsgs(bb, yy, f)
assert G_mul(bb, order) == yy
if order is not None:
ps.append(order)
ms.append(f)
order = crt(ps, ms)
assert G_mul(base, order) == y
return order
# ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
# search primitive root
# for g in G:
# is_primitive = True
# for _p, e in factors:
# q = order // _p
# res = G_mul(g, q)
# if res == (1,0):
# is_primitive = False
# break
# print(f"[{is_primitive}] {g}")
# primitive root
g0 = G[5]
def create_conn():
host, port = conn_info(CONN_INFO)
return remote(host, port)
def exploit():
# c = n1 * G1
n1 = G_log(g0, c)
print("[+] n1 =", n1)
ns = []
mat = [
[n1, 0, 0, 0, 0, 0, 0]
]
for i, g in enumerate(G[:-1]):
_n = G_log(g0, g)
ns.append(_n)
row = [-_n, 0, 0, 0, 0, 0, 0]
row[i+1] = 1
mat.append(row)
mat.append([-order, 0, 0, 0, 0, 0, 1])
print("[+] matrix is created")
mat = Matrix(ZZ, mat)
llled = mat.LLL()
print("[+] LLL is completed")
for b in llled:
print("-----" * 20)
for _c in b:
_c = abs(_c)
print(hex(_c), long_to_bytes(_c))
if __name__ == "__main__":
exploit()
実行結果は次の通り。
[+] n1 = 2317225096600917854828607598415895794303123788026147125642911218463153035917102678452039911900753570983303015546163018331388639671559221312084553221137785
[+] matrix is created
[+] LLL is completed
----------------------------------------------------------------------------------------------------
0x335f444c5021217d b'3_DLP!!}'
0x44554354467b615f b'DUCTF{a_'
0x313333375f687970 b'1337_hyp'
0x337262306c615f6d b'3rb0la_m'
0x333374735f746833 b'33ts_th3'
0x5f6d756c7431706c b'_mult1pl'
0x80929f0d32067e74 b'\x80\x92\x9f\r2\x06~t'
----------------------------------------------------------------------------------------------------
フラグ部分を適当に並び替えて復元した
Flag: DUCTF{a_1337_hyp3rb0la_m33ts_th3_mult1pl3_DLP!!}
OTWhat 1 §
secuchat同様にソースコードは無く、今度はWebページのリンクだけが与えられる。URLと署名を提出するフォームがあり、問題文によればhttps://EVILCODE/<arbitrary path>のようなURLの署名を送ることが出来れば良いらしい。
しかし何で署名されているのかすら全くわからない。こういう時はだいたいページのソースコードを見れば何かあるとHacking with Guessing PlatformことTryHackMeで学んだので見てみるとRSAのPEMファイルがベタ書きしてあった。問題の説明文から多分署名鍵だと思われる。
(ちなみに署名において署名者が使う鍵を「公開鍵」って言ったり検証プロセスを「公開鍵で復号」とか言うとTwitterでFF外から怒られが発生したりするらしい、個人的にはそんなﾈﾁﾈﾁ目くじらを立てなくても良いとは思いますが...)
これをpycryptodomeのPublicKey.RSAで読み込むと至って普通の数値であり、secuchat同様に単体の鍵としては何も問題無いようである。
とりあえず(検証結果が)正常なURLと正常な署名が与えられているので、$s$を署名とおいて、先程の署名鍵$n,e$を使って$s^e \bmod n$を計算してみると多分PKCS#1 V1.5に則ったようなバイト列が入手出来る。
このバイト列の正確な説明はRFC3447等を参照していただくとして、この問題では末尾にURLのハッシュ値が格納されているということが効いてくる。また、使われているハッシュアルゴリズムはSHA3-512である。
このままでは現実世界でも使われている堅牢なスキームに立ち向かう事になるのだが、署名を送信するとページのコメント欄に次のようなものが現れる。
成功時: update.c:69:main(): strcmp(hash, &decrypted_signature[512 - 64]) = 0
失敗時: update.c:69:main(): strcmp(hash, &decrypted_signature[512 - 64]) = 255
この出力から推測するにstrcmpを用いてURLのハッシュ値と署名にくっつけたハッシュ値を比較していると思われる。
加えて、署名をちょっと変える、つまり復号結果がパディングの規準に準拠していないようなものになったものを送ってもこの比較は行われているらしい。
以上の2点からまずハッシュ値がXX 00 ...となるようなURLを用意した上で、適当な署名$s'$に対して$s^e \bmod n$を計算し、そのハッシュ格納部が同様にXX 00から始まるようなものを探して提出すれば受理されるはずである。
(多分00 ...のようなものでもいけるはず、「ヌル文字同士ってどう比較されるんだろう?」って思ったので安全のために1文字確保した。)
以下のコードでそのような署名とURLを探して提出したら無事にフラグが開示された。
from pwn import remote
from Crypto.Util.number import long_to_bytes, bytes_to_long
from Crypto.PublicKey import RSA
from Crypto.Signature import pkcs1_15
from Crypto.Hash import SHA3_512
import string
import base64
import json
import requests
from xutil.misc import conn_info
# !!GLOBAL!!
# DON'T TOUCH, CHANGE AND ABUSE THEM
CONN_INFO = ""
normal_sig = "ipTX+GMCdI1da1Bwq6BLzMHBgbMVuWoydFa9s+5xsN/0KLsybT8fHuev4vZ1frd4d569mZlRw+PDsC1zy96OeR8uks4aaz9fR8nSbRsDOJICWw1rj1srpyl7xhxYd591/7EZBPH4MMJi66IFZUThLE1RJppbOHv02kkzzE2y79Hi/UoxGdkImZDVfgL+2Ic1ZUqkkff8g4dNKxlgwKfQHgwUfq7W8PaGhk7cfUfPxyo78jGtwXN4XuES23h2pf8aFXnWTZNglJrbXW6xNr28FpKEtyY+Njm0u4mn+LJywYDfQbxhxpxW0vEppxR2zmkW24M2IHRDBfWOkygttL3suwveLARJTIKElDu7diKBErdTYZr5cNDubSbcQMNjMZ18lD+4UNSSwmMMgwNXrI1QAzh4Ndi+QR0HYeUh0oYrtcAe2Mlvx8GYfVWjxW2sLk98jNl5kZcD3HT/oX8LYdaKKVhkLcGzq1AgLhhCNs6ugLv+/SVzFx0Vw5mKi1N1K7OlvEkryG3Fx31tD89A0KKiHHZ0ZHGjJKe/d6N5DIGx0yvTIFX56mwJd+GGv+tGzVN2UZsxJvWrc1yWltCeYGNnl6hBZixBk/DodWpOF8XFM/4y0GGXRjIp9hO1E7ySf33L7sxrUNfCKTN5bfTEQ6OdkxgKMTqqo8is5P95wcz6kt4="
good_url = b"https://GOODCODE/"
evil_url = b"https://EVILCODE/"
def create_conn():
host, port = conn_info(CONN_INFO)
return remote(host, port)
def search_zero_path():
l = 1
found = False
while True:
print(l)
for c in string.ascii_lowercase:
s = c * l
m = evil_url + s.encode()
h = SHA3_512.new(m).digest()
if h[1] == 0:
print("[+] Found!!")
print(f"[+] [{h[:2]}] in sha3-512({m})")
return (m, h[:2])
l += 1
def create_fake_sig(n, e, target_bytes):
sig = n // 2
while True:
m = long_to_bytes(pow(sig, e, n))
if len(m) != 512:
sig += 1
continue
h = m[448:]
if h[:2] == target_bytes:
return sig
sig += 1
def exploit():
pem = open("pubkey.pem").read().strip()
key = RSA.importKey(pem)
print(key.n.bit_length())
print(key.e)
sig = base64.b64decode(normal_sig)
res = pow(bytes_to_long(sig), key.e, key.n)
res = long_to_bytes(res)
i = res.index(b"\x00")
t = res[i+1:]
sha512_bytes = long_to_bytes(0x3051300d060960864801650304020a05000440)
assert sha512_bytes in t
h = t[len(sha512_bytes):]
print(h)
print(h.hex())
hash_512 = SHA3_512.new(good_url)
_h = hash_512.digest()
print(_h)
target_url, target_bytes = search_zero_path()
fake_sig = create_fake_sig(key.n, key.e, target_bytes)
fake_sig = base64.b64encode(long_to_bytes(fake_sig))
print(f"[+] url: {target_url}")
print(f"[+] sig: {fake_sig}")
if __name__ == "__main__":
exploit()
Flag: DUCTF{https://wiibrew.org/wiki/Signing_bug#L0L_memcmp=strcmp}
フラグ記載のURLだと似たような脆弱性がiOSにあったらしい。
ちなみにFirst Bloodでした。今年で3件目です。
OTWhat 2 §
OTWhat 1同様にWebページのリンクだけ渡される。説明文を見ると今度は署名がECDSAになり、使われているのはP-256曲線ということがわかる。
今回もコメントでデバッグ出力が出るのだが、URLのハッシュ値しか与えられない。ちなみに使われているアルゴリズムは1同様SHA3-512である。
まず最初に署名から$r,s$を抽出するところである。これは何故か1年前に購入していたプログラミングビットコインやこの記事を参考にして抽出した。
この結果を観察すると1組の署名において$r$が一致することがわかった。$k$を署名時に使われるnonceとおくと、$kG$($G$はP-256曲線の生成元)のx座標が$r$になるため、同じ$k$が使われている事になる。
という事はsame nonce attackが使えそうである。この攻撃に関しては何故か日本語Wikipediaが詳しいのでそちらを参照していただきたい。
これを利用すれば秘密鍵$d$が特定出来るので任意のメッセージを署名し放題になる。これで無事に解ける...と思いきやそうもいかなかった。
署名する際にメッセージのハッシュ値を用いるのだが、今回使っているのはSHA3-512であり、P-256曲線のパラメータは256bitである事からハッシュ値をこのサイズにまで切り詰める必要がある。
これは単純にP-256曲線の位数で割るだけでは解決しない。Wikipediaに書いてあるように上位256bitを用いる必要がある。
これを最初無視していたせいで無事に計算出来た$k$が$kG$のx座標が重複した署名の$r$にならないという事態が発生した。
またそれに気づいてもハッシュ値の加工にも苦戦した。前述の通り、ハッシュ値の上位256bitを用いるのだがこれは数値では無く「digestされたバイト列で上位64bit」の事を意味する。つまり、数値で上位256bitだけを取っていると例えば00 ...のようなハッシュ値では00を無視してしまうので異なる結果が得られてしまう。
結局この辺はPythonのfastecdsaの実装を見たりして解決した。
下記コードのeがハッシュ値であり、mpz_fdiv_q_2exp関数を用いて下位256bitを切り捨てていることが分かる。
if(digestBits > orderBits) {
mpz_fdiv_q_2exp(e, e, digestBits - orderBits);
}
これで無事にハッシュ値を切り詰めた結果が得られたので$k,d$を求めることが出来た。後は先程名前を出したfastecdsaを用いてhttps://EVILCODE/を署名し、その結果を形式に沿うようにバイト列にしてbaes64エンコードしたものを提出するとフラグが得られた。
from pwn import remote
from Crypto.Util.number import long_to_bytes, bytes_to_long
from fastecdsa.curve import P256 as _curve
from fastecdsa.ecdsa import sign, verify
from Crypto.Hash import SHA3_512
from hashlib import sha3_512
import string
import base64
import json
import requests
from xcrypto.ec import EllipticCurve, ECDSA, ECPoint
from xcrypto.mod import is_quadratic_residue
# !!GLOBAL!!
# DON'T TOUCH, CHANGE AND ABUSE THEM
p = _curve.p
a = _curve.a
b = _curve.b
order = _curve.q
gx = _curve.gx
gy = _curve.gy
G = _curve.G
# mycurve = EllipticCurve(a, b, p)
# mycurve.set_order(order)
# G = ECPoint(gx, gy, mycurve)
evil_url = b"https://EVILCODE/"
def get_data_from_log():
all_sig = ""
ret = []
raw_log = open("log.txt").read().strip()
lines = raw_log.split("\n")
for line in lines:
url, sig = line.split(" ")
ret.append((url.strip(), base64.b64decode(sig.strip())))
all_sig += sig.strip()
return ret
def exploit():
sigs = []
url_and_sig = get_data_from_log()
for url, sig in url_and_sig:
header = sig[:4]
assert header[0] == 0x30
r_header = sig[2:4]
assert r_header[0] == 0x02
r_length = r_header[1]
r = sig[4:4+r_length]
assert len(r) == r_length
s_idx = 4+r_length
s_header = sig[s_idx:s_idx+2]
assert s_header[0] == 0x2
s_length = s_header[1]
s = sig[s_idx+2:]
assert len(s) == s_length
r = bytes_to_long(r)
s = bytes_to_long(s)
z = SHA3_512.new(url.encode()).digest()
z = bytes_to_long(z)
z //= 2**256
# z = z % (2**256)
assert r < order
assert s < order
# print(sig.hex())
# print(f"{r=}")
# print(f"{s=}")
sig = (r,s,z, url)
sigs.append(sig)
rs = []
dupl_r = None
for r, s, z, _ in sigs:
if r in rs:
print("[+} Duplicated Nonce!!")
dupl_r = r
rs.append(r)
dupl_sigs = list(filter(lambda sig: sig[0] == dupl_r, sigs))
print(dupl_sigs)
(r1, s1, z1, u1), (r2, s2, z2, u2) = dupl_sigs
assert r1 == r2
s_diff = (s1 - s2) % order
z_diff = (z1 - z2) % order
k = z_diff * pow(s_diff, -1, order) % order
assert (k*G).x == r1
d = (s1 * k - z1) * pow(r1,-1, order) % order
_d = (s2 * k - z2) * pow(r2,-1, order) % order
assert d == _d
# check d
# myecdsa = ECDSA(mycurve, G, d*G, d)
# for r, s, z, _ in sigs:
# print(myecdsa.verify(r, s, z))
Q = d*G
for r, s, z, url in sigs:
print(verify((r,s), url, Q, hashfunc=sha3_512))
# evil_url = b"https://GOODCODE/update/abcd0b64039c6eff5a1cbf50f24eb6c62f25f8f39da28fdc112433b93ada6018"
_r, _s = sign(evil_url, d, hashfunc=sha3_512)
b_r = long_to_bytes(_r)
if b_r[0] >= 0x80:
b_r = b"\00" + b_r
b_s = long_to_bytes(_s)
if b_s[0] >= 0x80:
b_s = b"\00" + b_s
fake_r = b"\x02" + len(b_r).to_bytes(1, "little") + b_r
fake_s = b"\x02" + len(b_s).to_bytes(1, "little") + b_s
fake_rs = fake_r + fake_s
sig_len = len(fake_rs)
sig = b"\x30" + sig_len.to_bytes(1, "little") + fake_rs
print(sig)
print("[+] URL:", evil_url)
print("[+] signature:", base64.b64encode(sig))
if __name__ == "__main__":
exploit()
Flag: DUCTF{27C3 Console Hacking 2010 (PS3 3p1c F41l)}
PS3でも同様の攻撃が出来たという話は割と有名
ちなみにSecond Bloodでした。OTWhat 1同様に純粋な数学力でなく、ググり力と仕様を読み込む力とGuessing力が問われた問題だったのでもしかするとCryptoよりもバグハントとかの方が向いているのかもしれないです。