Writeup: zer0pts CTF 2021
先週土日に開催されていたzer0pts CTF 2021に出たので自分が解いた問題と、解けなかったが、終了後に解けた問題についてそのWriteupを書きます。
ちなみに問題はここで全部公開されている上に公式Writeupもあるので是非覗いてみてください。
Table of Contents §
war(sa)mup §
問題のスクリプトは次の通り
from Crypto.Util.number import getStrongPrime, GCD
from random import randint
from flag import flag
import os
def pad(m: int, n: int):
# PKCS#1 v1.5 maybe
ms = m.to_bytes((m.bit_length() + 7) // 8, "big")
ns = n.to_bytes((n.bit_length() + 7) // 8, "big")
assert len(ms) <= len(ns) - 11
ps = b""
while len(ps) < len(ns) - len(ms) - 3:
p = os.urandom(1)
if p != b"\x00":
ps += p
return int.from_bytes(b"\x00\x02" + ps + b"\x00" + ms, "big")
while True:
p = getStrongPrime(512)
q = getStrongPrime(512)
n = p * q
phi = (p-1)*(q-1)
e = 1337
if GCD(phi, e) == 1:
break
m = pad(int.from_bytes(flag, "big"), n)
c1 = pow(m, e, n)
c2 = pow(m // 2, e, n)
print("n =", n)
print("e =", e)
print("c1=", c1)
print("c2=", c2)
コメントからPKCS#1 v1.5らしきパディングをフラグに加えたもの(m)を暗号化している。問題の鍵となるのはmに加えてm // 2も暗号化した結果もくれることである。
ここでフラグの末尾が}で終わる事を考えるとmは奇数になる(}のASCIIコードは0x7d = 125である)。ということはm // 2は(m-1) // 2である。
m // 2を$m_2$とおくと、$m = 2m_2 + 1$の関係がある。線形の関係にある2つの平文を同一公開鍵で暗号化している場合はFranklin-Reiter Related Message Attackが有効なのでこれを使う。
使用コードは次の通り
from Crypto.Util.number import long_to_bytes
def gcd(a, b):
while b:
a, b = b, a % b
return a.monic()
def franklinreiter(c_1, c_2, e_1, e_2, N, a, b):
P.<X> = PolynomialRing(Zmod(N))
g_1 = X^e_1 - c_1
g_2 = (a*X + b)^e_2 - c_2
result = -gcd(g_1, g_2).coefficients()[0]
return result
n = 113135121314210337963205879392132245927891839184264376753001919135175107917692925687745642532400388405294058068119159052072165971868084999879938794441059047830758789602416617241611903275905693635535414333219575299357763227902178212895661490423647330568988131820052060534245914478223222846644042189866538583089
e = 1337
c1= 89077537464844217317838714274752275745737299140754457809311043026310485657525465380612019060271624958745477080123105341040804682893638929826256518881725504468857309066477953222053834586118046524148078925441309323863670353080908506037906892365564379678072687516738199061826782744188465569562164042809701387515
c2= 18316499600532548540200088385321489533551929653850367414045951501351666430044325649693237350325761799191454032916563398349042002392547617043109953849020374952672554986583214658990393359680155263435896743098100256476711085394564818470798155739552647869415576747325109152123993105242982918456613831667423815762
m2 = franklinreiter(c2, c1, 1337, 1337, n, 2, 1)
m = m2 * 2 + 1
print(long_to_bytes(m))
フラグはzer0pts{y0u_g07_47_13457_0v3r_1_p0in7}であった。
なお、Franklin-Reiter Related Message Attackについては半年ぐらい前に書いた自分の記事でそこそこ解説しているので良かったら読んでください。
OT or NOT OT §
問題のスクリプトは次の通り
import os
import signal
import random
from base64 import b64encode
from Crypto.Util.number import getStrongPrime, bytes_to_long
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from flag import flag
p = getStrongPrime(1024)
key = os.urandom(32)
iv = os.urandom(AES.block_size)
aes = AES.new(key=key, mode=AES.MODE_CBC, iv=iv)
c = aes.encrypt(pad(flag, AES.block_size))
key = bytes_to_long(key)
print("Encrypted flag: {}".format(b64encode(iv + c).decode()))
print("p = {}".format(p))
print("key.bit_length() = {}".format(key.bit_length()))
signal.alarm(600)
while key > 0:
r = random.randint(2, p-1)
s = random.randint(2, p-1)
t = random.randint(2, p-1)
print("t = {}".format(t))
a = int(input("a = ")) % p
b = int(input("b = ")) % p
c = int(input("c = ")) % p
d = int(input("d = ")) % p
assert all([a > 1 , b > 1 , c > 1 , d > 1])
assert len(set([a,b,c,d])) == 4
u = pow(a, r, p) * pow(c, s, p) % p
v = pow(b, r, p) * pow(c, s, p) % p
x = u ^ (key & 1)
y = v ^ ((key >> 1) & 1)
z = pow(d, r, p) * pow(t, s, p) % p
key = key >> 2
print("x = {}".format(x))
print("y = {}".format(y))
print("z = {}".format(z))
AESの暗号文とIVと鍵の長さ、そして素数pが与えられ、以下のプロセスを鍵が0以上の間続けている。
- 3つの正整数$r,s,t$が用意され、そのうち$t$のみが開示される。
- 入力として$a,b,c,d$の4つが要求される。どれも$p$を法とした値にされる上に、1より大きく重複してはならないという制約がある。
- 次の5つの数$u,v,x,y,z$が計算され$x,y,z$が与えられる、ここで$k_0, k_1$はそれぞれ鍵の末尾bitとその1つ上のbitを表す
- $u\equiv a^rc^s \bmod p$
- $v\equiv b^rc^s \bmod p$
- $x = u \oplus k_0$
- $y = v \oplus k_1$
- $z\equiv d^rt^s \bmod p$
- 鍵を右に2bitシフトする
結論から言うと$a = 2, \ b = -a, \ c = t^{-1} \ d = a^{-1}$を入力した。この場合の$u,v,z$はそれぞれ次のようになる。
$$ \begin{aligned} u &\equiv \frac{a^r}{t^s} \bmod p \cr v & \equiv \frac{(-a)^r}{t^s} \bmod p \cr z & \equiv \frac{t^s}{a^r} \bmod p \end{aligned} $$
これからわかるように$uz \equiv 1 \bmod p, \ \frac{u}{v} \equiv (-1)^r \bmod p$が成立する。
まず前者の関係から$(x \oplus k_0)z \equiv 1 \bmod p$である。よって$k_0$を2通り試してこの式の左辺に代入し、成り立てば$k_0$が決定出来る。
これで$u$が決定された事になるので、この値を用いて先程同様に$\frac{u}{y \oplus k_1} \equiv (-1)^r$が成り立つような$k_1$を選択する。
これで鍵の下位2bitが決定されたので鍵全体を復元するようなスクリプトを書けば良い。
使用コードは次の通り
from Crypto.Util.number import long_to_bytes
from pwn import remote
from base64 import b64decode
from Crypto.Cipher import AES
from math import ceil
if __name__ == "__main__":
sc = remote("crypto.ctf.zer0pts.com", 10130)
sc.recvuntil(": ")
encrypted_flag = b64decode(sc.recvline().strip())
iv, encrypted_flag = encrypted_flag[:AES.block_size], encrypted_flag[AES.block_size:]
print(iv, encrypted_flag)
sc.recvuntil("p = ")
p = int(sc.recvline())
print("p =", p)
sc.recvuntil("() = ")
key_length = int(sc.recvline())
iteration = ceil(key_length / 2)
key = ""
for i in range(iteration):
print(i)
sc.recvuntil("t = ")
t = int(sc.recvline())
a = 2
b = -2
c = pow(t, -1, p)
d = pow(2, -1, p)
sc.recvuntil("a = ")
sc.sendline(str(a))
sc.recvuntil("b = ")
sc.sendline(str(b))
sc.recvuntil("c = ")
sc.sendline(str(c))
sc.recvuntil("d = ")
sc.sendline(str(d))
sc.recvuntil("x = ")
x = int(sc.recvline())
sc.recvuntil("y = ")
y = int(sc.recvline())
sc.recvuntil("z = ")
z = int(sc.recvline())
for key_u in range(2):
_u = x ^ key_u
lhs = _u * z % p
if lhs == 1:
break
assert lhs == 1
for key_v in range(2):
_v = y ^ key_v
lhs = _u * pow(_v, -1, p) % p
if lhs == 1 or lhs == p - 1:
break
assert lhs == 1 or lhs == p-1
key = (str(key_v) + str(key_u)) + key
key = long_to_bytes(int(key,2))
print(len(key))
cipher = AES.new(key=key, mode=AES.MODE_CBC, iv=iv)
flag = cipher.decrypt(encrypted_flag)
print(flag)
フラグはzer0pts{H41131uj4h_H41131uj4h}になった。
janken vs yoshiking §
問題のスクリプトは次の通り
import random
import signal
from flag import flag
from Crypto.Util.number import getStrongPrime, inverse
HANDNAMES = {
1: "Rock",
2: "Scissors",
3: "Paper"
}
def commit(m, key):
(g, p), (x, _) = key
r = random.randint(2, p-1)
c1 = pow(g, r, p)
c2 = m * pow(g, r*x, p) % p
return (c1, c2)
def decrypt(c, key):
c1, c2 = c
_, (x, p)= key
m = c2 * inverse(pow(c1, x, p), p) % p
return m
def keygen(size):
p = getStrongPrime(size)
g = random.randint(2, p-1)
x = random.randint(2, p-1)
return (g, p), (x, p)
signal.alarm(3600)
key = keygen(1024)
(g, p), _ = key
print("[yoshiking]: Hello! Let's play Janken(RPS)")
print("[yoshiking]: Here is g: {}, and p: {}".format(g, p))
round = 0
wins = 0
while True:
round += 1
print("[system]: ROUND {}".format(round))
yoshiking_hand = random.randint(1, 3)
c = commit(yoshiking_hand, key)
print("[yoshiking]: my commitment is={}".format(c))
hand = input("[system]: your hand(1-3): ")
print("")
try:
hand = int(hand)
if not (1 <= hand <= 3):
raise ValueError()
except ValueError:
print("[yoshiking]: Ohhhhhhhhhhhhhhhh no! :(")
exit()
yoshiking_hand = decrypt(c, key)
print("[yoshiking]: My hand is ... {}".format(HANDNAMES[yoshiking_hand]))
print("[yoshiking]: Your hand is ... {}".format(HANDNAMES[hand]))
result = (yoshiking_hand - hand + 3) % 3
if result == 0:
print("[yoshiking]: Draw, draw, draw!!!")
elif result == 1:
print("[yoshiking]: Yo! You win!!! Ho!")
wins += 1
print("[system]: wins: {}".format(wins))
if wins >= 100:
break
elif result == 2:
print("[yoshiking]: Ahahahaha! I'm the winnnnnnner!!!!")
print("[yoshiking]: You, good loser!")
print("[system]: you can check that yoshiking doesn't cheat")
print("[system]: here's the private key: {}".format(key[1][0]))
exit()
print("[yoshiking]: Wow! You are the king of roshambo!")
print("[yoshiking]: suge- flag ageru")
print(flag)
じゃんけんのスクリプトが動いていて、自分の手を出す前に相手の手をElGamal暗号を用いて暗号化したものが与えられる。これで100回勝てばフラグが開示される。
当たり前だが、じゃんけんの手は3つしか存在しないため今回は平文の空間が非常に狭い事になる。平文の空間が狭くてElGamal暗号と言えばTokyoWesterns CTF 6th 2020 - The Melancholy of Aliceを思い出す。ここで使った手法が今回も有効そうである。
getStrongPrime()は必ずしも安全素数を生成するわけではなく、$p - 1 = p_0 \times p_1 \times \cdots $と素因数分解した際に、素因数の中で非常に大きなものがある、程度の生成をする。ということはある程度小さい素数は素因数として抱えている事になる。今回は10000までの数で雑に素因数分解を試して$p - 1 = p_0 \times p_1 \times \cdots \times C$となったとする($C$は大きな数)。
The Melancoly of Aliceでも使った方法を用いるには秘密鍵$x$を指数とした値が必要である。今回はElGamal暗号の公開鍵$h \equiv g^x \bmod p$が与えられていないが、$c_2 \equiv mc_1^x \bmod p$の関係があり、$m$は3通りしか無いのでこれを全部試す。
これで$x' \equiv x \bmod \prod_{i=0} p_i$となる$x'$を求めることが出来る。これを用いると$\left(\frac{c_2}{c_1^{x'}}\right)^C \equiv m^C \bmod p$となるので(詳細は前述のWriteupを参照してください)、事前にこの値をキー値を出す手とする辞書を作成しておけば、照合する事で出す手の特定が出来る。
使用コードは以下の通り(但し、結構な確率で失敗するので成功するまで連発した)
from pwn import remote
from xcrypto.dlp import pohlig_hellman
from xcrypto.num_util import prod
def small_factorize(n):
ret = []
for i in range(2, 10000):
factor = [i, 0]
while n % i == 0:
print(i)
n //= i
factor[1] += 1
if factor[1] > 0:
ret.append(factor)
return ret
win_hand = {
1: 3,
2: 1,
3: 2
}
if __name__ == "__main__":
sc = remote("crypto.ctf.zer0pts.com", 10463)
sc.recvuntil("g: ")
g = int(sc.recvuntil(",")[:-1])
sc.recvuntil("p: ")
p = int(sc.recvuntil("\n")[:-1])
order = p - 1
factors = small_factorize(order)
C = order
for factor, exponent in factors:
C //= pow(factor, exponent)
print(factors, C)
if len(factors) == 1:
print("[+] p is fxxkin super hyper safe...")
exit()
hands_to_power = {}
for hand in range(1, 4):
hands_to_power[pow(hand, C, p)] = hand
while True:
sc.recvuntil("is=(")
c1 = int(sc.recvuntil(",")[:-1])
c2 = int(sc.recvuntil(")")[:-1])
hand = None
for y_hand in range(1, 4):
lhs = c2 * pow(y_hand, -1, p) % p
try:
_x = pohlig_hellman(c1, lhs, p, factors)
res = pow(c2 * pow(c1, -_x, p) % p, C, p)
if res in hands_to_power:
hand = hands_to_power[res]
break
except:
pass
if hand is not None:
print(hand)
win = win_hand[hand]
sc.recvuntil("(1-3): ")
sc.sendline(str(win))
sc.recvuntil("[system]: ")
res = sc.recvline()
print(res)
if b"100" in res:
sc.interactive()
break
else:
exit()
フラグはzer0pts{jank3n-jank3n-0ne-m0r3-batt13}であった。
easy pseudo random(解き直し) §
当日解けませんでしたが、同じ考え方をしているWriteupがあり、そちらでは解けていたのでもう一度解いてみたら、普通に解けたのでWriteupを書きます。古いコードは別の解法での復習の際に上書きしたので何故解けなかったかはわかりませんが、多分Typoか致命的な凡ミスをしていたんだと思います。
問題のスクリプトは次の通り
from Crypto.Util.number import*
from flag import flag
nbits = 256
p = random_prime(1 << nbits)
Fp = Zmod(p)
P.<v> = PolynomialRing(Fp)
b = randrange(p)
d = 2
F = v^2 + b
v0 = randrange(p)
v1 = F(v0)
k = ceil(nbits * (d / (d + 1)))
w0 = (v0 >> (nbits - k))
w1 = (v1 >> (nbits - k))
# encrypt
m = bytes_to_long(flag)
v = v1
for i in range(5):
v = F(v)
m ^^= int(v)
print(f"p = {p}")
print(f"b = {b}")
print(f"m = {m}")
print(f"w0 = {w0}")
print(f"w1 = {w1}")
2乗を利用した乱数生成機を利用してフラグと5回排他的論理和を取っている。乱数の生成には$v_{i+1} \equiv v_i^2 + b \bmod p$を利用しており、この内開示されるのは$v_0, v_1$の上位171bitのみである。XORに使用する乱数は$v_2$からである。
ビットシフトによって最初2つの乱数が削られているのでこれを復元する事を考える。$v_0, v_1$の未知部分を$\alpha, \beta$とおくと次のような関係がある。
$$ \begin{aligned} v_0 &= w_0 \times 2^{85} + \alpha \cr v_1 &= w_1 \times 2^{85} + \beta \end{aligned} $$
これと乱数生成機の式から$w_1 \times 2^{85} + \beta \equiv (w_0\times 2^{85} + \alpha)^2 + b \bmod p$が成り立つので、適当に移項して整数$k$を用いると次のようになる。
$$ kp - 2\alpha w_0\times 2^{85} + w_1\times 2^{85} - w_0^2 \times 2^{170} - b = \alpha^2 - \beta $$
左辺がおよそ512bitの項からなる式なのに対して、右辺が170bitぐらいなのでSVPに落とし込めばいい感じになりそうである。そこで次のような格子を用意する。
$$ \left( \begin{matrix} p & -2w_0\times 2^{85} & w_1 - w_0^2 \times 2^{170} - b \cr 0 & 2^{n_2} & 0 \cr 0 & 0 & 2^{n_1} \end{matrix} \right) $$
これに右からベクトル$(k, \alpha, 1)^{\mathrm{T}}$を掛ける事でベクトル$(\alpha^2 - \beta, 2^{n_2}\alpha, 2^{n_1})^{\mathrm{T}}$が現れる。LLLで現れる基底の中にこれが含まれるそうなスケーリングを設定する。今回は$n_1 = 170, \ n_2 = 85$を利用した。これで$(\alpha^2 - \beta, 2^{n_2}\alpha, 2^{n_1})^{\mathrm{T}}$のサイズはだいたい170bitぐらいになり、また、この格子にLLLを施した時に現れる基底のサイズはだいたい$(p \times 2^{n_1 + n_2})^{1/3} \approx 2^{512/3}$以下になる事から特に問題無さそうである。
使用コードは次の通り
from Crypto.Util.number import long_to_bytes
nbits = 256
d = 2
k = ceil(nbits * (d / (d + 1)))
print(k)
print(nbits - k)
p = 86160765871200393116432211865381287556448879131923154695356172713106176601077
b = 71198163834256441900788553646474983932569411761091772746766420811695841423780
m = 88219145192729480056743197897921789558305761774733086829638493717397473234815
w0 = 401052873479535541023317092941219339820731562526505
w1 = 994046339364774179650447057905749575131331863844814
w0 <<= (nbits - k)
w1 <<= (nbits - k)
Fp = Zmod(p)
P.<v> = PolynomialRing(Fp)
F = v^2 + b
n1 = 170
print("[+] vector size:", n1)
n2 = n1 - (nbits - k)
l_list = [
[p, 0, 0],
[-2 * w0, 2^n2, 0],
[(-w0^2 + w1 - b), 0, 2^n1]
]
llled = Matrix(ZZ, l_list).LLL()
for basis in llled:
if basis[1] < 0:
basis = -basis
x0 = basis[1] // (2^n2)
x1 = -(basis[0] - x0^2)
v0 = w0 + x0
v1 = w1 + x1
if F(v0) == v1:
print("[+] Found!!")
v = v1
for i in range(5):
v = F(v)
m ^^= int(v)
print(long_to_bytes(m))
フラグはzer0pts{is_blum_blum_shub_safe?}であった。
ちなみに想定解や多くの人が解いている解法はdefund氏の多変数Coppersmith's Attackのスクリプトを利用しており、以前から存在は知っていたものの出てこなかったのが反省点です(これを使っても解き直しましたが割愛します)。