Writeup: ASIS CTF 2021
先週末に開催されていたASIS CTF 2021に出たので自分が解いた問題のWriteupを書きます。
Crypto Warm up §
次のようなスクリプトとその実行結果が与えられる
#!/usr/bin/env python3
from Crypto.Util.number import *
import string
from secret import is_valid, flag
def random_str(l):
rstr = ''
for _ in range(l):
rstr += string.printable[:94][getRandomRange(0, 93)]
return rstr
def encrypt(msg, nbit):
l, p = len(msg), getPrime(nbit)
rstr = random_str(p - l)
msg += rstr
while True:
s = getRandomNBitInteger(1024)
if is_valid(s, p):
break
enc = msg[0]
for i in range(p-1):
enc += msg[pow(s, i, p)]
return enc
nbit = 15
enc = encrypt(flag, nbit)
print(f'enc = {enc}')
15bitの整数pを法として1024bitの整数sからidx = pow(s,i,p)を計算し、enc[i+1] = msg[idx]となるように暗号文を並べ替えている。pはmsgやencの長さと一致している。また、明らかにs >> pなのでsは1024bitではあるが、実質pと同程度のエントロピーしかない。
この構成から例えばフラグ2文字目の文字I(フラグフォーマットはASIS{...})は$2\equiv s^x \mod p$を解いて$x+1$に対応するインデックスに飛ぶのでsをp未満の数で回してこの離散対数問題を解き(pが小さいので簡単に解ける)、対応するインデックスにIが存在するかを調べる。これを後続のS,{についても同様に行う事でsの候補を絞る事が出来る。
これらのsの候補を用いて復号すると1つだけまともに復号出来たのがあったのでそれがフラグ
from xcrypto.prime import is_prime
from xcrypto.dlp import baby_step_giant_step
def exploit():
enc = open("output.txt").read()
p = len(enc)
print(is_prime(p), p)
s_cand = []
for s in range(2, p):
if pow(s, (p-1)//2, p) == 1:
continue
if pow(s, (p-1)//3, p) == 1:
continue
if pow(s, (p-1)//7, p) == 1:
continue
if pow(s, (p-1)//29, p) == 1:
continue
e = baby_step_giant_step(s, 2, p)
if e is None:
continue
if enc[e+1] != "I":
continue
e = baby_step_giant_step(s, 3, p)
if e is None:
continue
if enc[e+1] != "S":
continue
e = baby_step_giant_step(s, 4, p)
if e is None:
continue
if enc[e+1] != "{":
continue
s_cand.append(s)
for s in s_cand:
flag = "AS"
for i in range(2, 100):
e = baby_step_giant_step(s, i, p)
m = enc[e+1]
flag += m
print(flag)
if __name__ == "__main__":
exploit()
- Flag:
ASIS{_how_d3CrYpt_Th1S_h0m3_m4dE_anD_wEird_CrYp70_5yST3M?!!!!!!}
Spiritual §
配布スクリプトは無いが、サーバーに繋ぐと次のようなクイズが出題される。
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+ hello, you know valuable information about given elliptic curve, +
+ your mission is to answer the question in each stage quickly! +
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
| E is an elliptic curve with k elements in the following form:
| E: y**2 = x**3 + a*x + b (mod p)
| p = 6615696742597842521
| a = ?
| b = ?
| k = 6615696744334514383
| What's the number of elements of E over finite field GF(p**n) where n = 5?
楕円曲線$y^2 \equiv x-3 + ax + b \mod p$の位数と法が与えられている状況で$\mathbb F_{p^n}$上の同じ楕円曲線の位数を答えよという問題。
この問題見る前は楕円曲線の位数について何も知らなかったのでたまたま今取っている講義の教科書に指定されていた「代数学から学ぶ暗号理論｜日本評論社」を読んだらフロベニウス写像のトレース$\mathrm{tr}(\varphi)$と位数$k$、有限体の法となっている素数$p$に次の関係があるらしい。
$$ \mathrm{tr}(\varphi) = 1 + p - k $$
また、このトレースを用いると$\mathbb F_{p^n}$の位数$k_n$も次の式で求める事が出来るらしい
$$ k_n = p^n + 1 - \alpha^n + \beta^n $$
ここで$\alpha, \beta$は特性多項式:$T^2 - \mathrm{tr}(\varphi)T + p$の2つの根である。
というわけでこれに沿って計算するだけのコードを書いて17問正解したらフラグをくれた。
ところで、こういう問題は最初に何問正解したらフラグをくれるのかを明記してほしいです。
from pwn import remote
def create_conn():
host, port = "168.119.108.148", 13010
return remote(host, port)
def solve(sc):
sc.recvuntil(b"p = ")
p = int(sc.recvline())
sc.recvuntil(b"k = ")
k = int(sc.recvline())
sc.recvuntil(b"n = ")
n = int(sc.recvline().strip()[:-1])
print("[+] instance:")
print(f" {p=}")
print(f" {k=}")
print(f" {n=}")
tr_phi = 1 + p - k
D = sqrt(tr_phi^2 - 4*p)
alpha = (tr_phi + D) / 2
beta = (tr_phi - D) / 2
alpha_n = expand(alpha^n)
beta_n = expand(beta^n)
answer = p^n + 1 - alpha_n - beta_n
print(f"[+] answer: {answer}")
sc.sendline(str(answer).encode("utf-8"))
def exploit():
sc = create_conn()
cnt = 17
for i in range(cnt):
solve(sc)
sc.interactive()
if __name__ == "__main__":
exploit()
- flag:
ASIS{wH47_iZ_mY_5P1R!TuAL_4NiMal!???}
Madras §
次のようなスクリプトとその実行結果をくれる
#!/usr/bin/env python3
from Crypto.Util.number import *
from flag import FLAG
def gentuple(nbit):
a, b, c = [getPrime(nbit // 3) for _ in '012']
return a, b, c
def encrypt(msg, params):
a, b, c = params
e, n = 65537, a * b * c
m = bytes_to_long(msg)
assert m < n
enc = pow(m, e, n)
return enc
nbit = 513
a, b, c = gentuple(nbit)
enc = encrypt(FLAG, (a, b, c))
print(f'a*b + c = {a*b + c}')
print(f'b*c + a = {b*c + a}')
print(f'c*a + b = {c*a + b}')
print(f'enc % a = {enc % a}')
print(f'enc % b = {enc % b}')
print(f'enc % c = {enc % c}')
print(f'enc = {enc}')
Multi-prime RSAで暗号化されていて、a,b,cの関係式が3つ与えられるので、終結式に放り込むと解けて素因数分解出来る。
from Crypto.Util.number import long_to_bytes
def get_params():
ha = 4414187148384348278031172865715942397786003125047353436418952679980677617016484927045195450392723110402
hb = 2621331497797998680087841425011881226283342008022511638116013676175393387095787512291008541271355772802
hc = 4553352994596121904719118095314305574744898996748617662645730434291671964711800262656927311612741715902
ca = 1235691098253903868470929520042453631250042769029968
cb = 2235727505835415157472856687960365216626058343546572
cc = 1197976933648163722609601772402895844093866589777721
cn = 6238548897897912462708514382106387305984378113132192980353695746912882399991285268937548949835500837749446265632471076030233510866260067177632747513323223
return (ha, hb, hc, ca, cb, cc, cn)
def exploit():
ha, hb, hc, ca, cb, cc, cn = get_params()
PR.<a,b,c> = PolynomialRing(ZZ)
fa = a + b*c - ha
fb = b + a*c - hb
fc = c + a*b - hc
r1 = fc.resultant(fb, c)
print(r1)
r2 = fc.resultant(fa, c)
print(r2)
r = r1.resultant(r2, b)
print(r)
ra = r.univariate_polynomial().roots()[0][0]
rb = r2(a=ra).univariate_polynomial().roots()[0][0]
rc = fc(a=ra, b=rb).univariate_polynomial().roots()[0][0]
assert ra + rb*rc == ha
assert rb + ra*rc == hb
assert rc + rb*ra == hc
N = ra*rb*rc
phi = (ra-1)*(rb-1)*(rc-1)
e = 65537
d = inverse_mod(e, phi)
m = pow(cn, d, N)
print(long_to_bytes(m))
if __name__ == "__main__":
exploit()
- Flag:
ASIS{m4dRa5_iZ_RSA_l1k3_cH41L3n9E?!!}
Pinhole §
次のようなスクリプトとその実行結果をくれる
#!/usr/bin/env sage
from sage.all import *
from Crypto.Util.number import *
from secret import a, flag
def random_poly(degree):
R.<x> = ZZ[]
f = x**degree
for i in range(1, degree):
f += randint(-3, 3) * x ** (degree - i)
return f
def genkey(a):
M, N = [SL2Z.random_element() for _ in '01'] # Special Linear Group
A = N * matrix(ZZ, [[0, -1], [1, 1]]) * N**(-1)
B = N * matrix(ZZ, [[0, -1], [1, 0]]) * N**(-1)
r, s = [randint(5, 14) for _ in '01']
U, V = (B * A) ** r, (B * A**2) ** s # V is not used?
F = []
for _ in range(2):
Ux = [random_poly(randint(1, 4)) for _ in range(4)]
Ux = [Ux[i] - Ux[i](a) + U[i // 2][i % 2] for i in range(4)]
Ux = matrix([[Ux[0], Ux[1]], [Ux[2], Ux[3]]])
F.append(Ux)
X, Y = M * F[0] * M ** (-1), M * F[1] * M ** (-1)
pubkey, privkey = (X, Y), (M, a)
return pubkey, privkey
def encrypt(msg, pubkey):
X, Y = pubkey
C = Y
for b in msg:
C *= X ** (int(b) + 1) * Y
return C
pubkey, privkey = genkey(a)
msg = bin(bytes_to_long(flag.lstrip(b'ASIS{').rstrip(b'}')))[2:]
enc = encrypt(msg, pubkey)
print(f'pubkey = {pubkey}')
print(f'enc = {enc}')
秘密となっているMは特殊線形群$SL_2(\mathbb Z)$とかいうやつの要素らしく、SageのSL2Z.random_element()だと各成分の絶対値が高々100のものが返される。そこでまず特殊線形群の要素で成分が小さいものを全部調べると100000弱だったのでこれを候補として更に絞り込む。
行列X,YはそれぞれX = M * F[0] * M**(-1), Y= M * F[1] * M**(-1)であり、F[0], F[1]はその作り方から定数項以外の係数の絶対値が高々3である(random_poly()より)。というわけでMの候補とX,YからF[0], F[1]を計算し、その任意の成分がこのような小さい係数の多項式であるようなMを探す。すると4つに絞れた上にこれらは符号を除いて差が無かったので殆ど一意に定まった。
問題は暗号化手順でC *= X ** (int(b) + 1) * Yをフラグの各bitに対して行っている。X,Yの定義から計算すると次が成り立つ。
$$ M^{-1} C M = F_1 \left( \prod_i F_0^{b_i + 1} F_1 \right) $$
ここでSageではF[0], F[1]の逆行列を計算出来るが、要素が整数係数多項式ではなく多項式の分数になる。しかし、前述の式を見れば分かるように左辺はF[1]と何らかの整数係数多項式を成分に持つ行列の積であり、F[1]**(-1)を計算して両辺左からかけてあげるとどちらも整数係数多項式を成分に持つ行列が現れる。
これを利用して右辺の項の数を減らすように左からF[0]**(-1)とF[1]**(-1)を掛けていき、整数係数多項式を成分に持つ行列が現れるかどうかをオラクルにして各ビットを特定する事が出来る。
無理にassertionを挟んだせいでエラーを吐くが、適宜フラグのビットを出力していたので残りは気合で解いたスクリプトは以下の通り。
load("result.sage")
def search():
cand = []
for a in range(-100, 100):
if a == 0:
continue
for b in range(-100, 100):
for c in range(-100, 100):
nume = b*c + 1
denom = a
if nume % denom != 0:
continue
d = nume // denom
if abs(d) >= 100:
continue
assert a*d - b*c == 1
cand.append((a,b,c,d))
return cand
def get_pubkey():
R.<x> = ZZ[]
X = [[ 1235*x^2 - 4196*x + 2802185, 4225*x^2 - 14356*x + 9559410],[ -361*x^2 + 1227*x - 821422, -1235*x^2 + 4198*x - 2802211]]
X = matrix(R, X)
Y = [
[ -779*x^4 - 2829*x^3 + 205*x^2 + 252*x + 40630633, -2665*x^4 - 9676*x^3 + 697*x^2 + 863*x + 138967416],[ 228*x^4 + 828*x^3 - 60*x^2 - 73*x - 11893098, 780*x^4 + 2832*x^3 - 204*x^2 - 250*x - 40677503]
]
Y = matrix(R, Y)
return X,Y
def check_matrix(F):
F = [F[0][0], F[0][1], F[1][0], F[1][1]]
for f in F:
coefs = f.coefficients()[1:]
for c in coefs:
if abs(c) > 3:
return False
return True
def recover_M():
cand = search()
X,Y = get_pubkey()
M_cand = []
for i, (a,b,c,d) in enumerate(cand):
M = matrix(ZZ, [[a,b],[c,d]])
M_inv = matrix(ZZ, [[d,-b],[-c,a]])
F_1 = M_inv * X * M
F_2 = M_inv * Y * M
res = check_matrix(F_1)
if res and check_matrix(F_2):
print("[+] Found!!", (a,b,c,d))
print(M)
print(F_1)
print(F_2)
M_cand.append(M)
print("=====" * 10)
return M_cand
# from `recover_a` and `recover_M`
def get_privkey():
raw_M = [
(-65, 41, 19, -12), (-41, -65, 12, 19), (41, 65, -12, -19), (65, -41, -19, 12)
]
Ms = []
for a,b,c,d in raw_M:
M = matrix(ZZ, [[a,b], [c,d]])
assert M in SL2Z
Ms.append(M)
a = 14
return Ms, a
def recover_a():
X,Y = get_pubkey()
a_cand = []
M_cand = recover_M()
for M in M_cand:
print(M)
F_X = M^(-1) * X * M
F_Y = M^(-1) * Y * M
for a in range(50000):
if F_X(a) == F_Y(a):
print("[+] Found!!", a)
U = F_X(a)
def exploit():
RZ.<x> = ZZ[]
C = matrix(RZ, enc)
X, Y = get_pubkey()
Ms, a = get_privkey()
for M in Ms:
MCM = M^(-1) * C * M
F_X = M^(-1) * X * M
F_Y = M^(-1) * Y * M
F_X_inv = F_X^(-1)
F_Y_inv = F_Y^(-1)
lhs = F_Y_inv * MCM
assert lhs.denominator() == 1
flag = ""
while True:
print(flag)
lhs = F_X_inv * lhs
assert lhs.denominator() == 1
_lhs = F_X_inv * lhs
if _lhs.denominator() == 1:
flag = flag + "1"
__lhs = F_Y_inv * _lhs
assert __lhs.denominator() == 1
lhs = __lhs
else:
_lhs = F_Y_inv * lhs
assert _lhs.denominator() == 1
flag = flag + "0"
lhs = _lhs
if __name__ == "__main__":
# L0OpHo13S_iN_cRyp705YST3mS!
exploit()
ちなみにaも算出出来たが使わなかった、謎
- Flag:
ASIS{L0OpHo13S_iN_cRyp705YST3mS!}
Lagleg §
次のようなスクリプトとその実行結果が与えられる。
#!/usr/bin/env python3
from Crypto.Util.number import *
from gmpy import *
from math import gcd
from flag import flag
def lag(k, a, n):
s, t = 2, a
if k == 0:
return 2
r = 0
while k % 2 == 0:
r += 1
k //= 2
B = bin(k)[2:]
for b in B:
if b == '0':
t = (s * t - a) % n
s = (s **2 - 2) % n
else:
s = (s * t - a) % n
t = (t** 2 - 2) % n
for _ in range(r):
s = (s ** 2 - 2) % n
return s
def legkey(nbit):
while True:
r = getRandomNBitInteger(nbit >> 1)
s = getRandomNBitInteger(nbit >> 3)
p, q = r**5 + s, s + r
if isPrime(p) and isPrime(q):
while True:
a = getRandomRange(2, q)
if q*legendre(a, p) - p*legendre(a, q) == p - q:
return p, q, a
def keygen(p, q, a):
e = 65537
if gcd(e, p**2 - 1) * gcd(e, q**2 - 1) < e:
d = inverse(e, (p**2 - 1) * (q**2 - 1))
x = pow(d, e, n)
y = lag(x, a, p * q)
return e, y, d
def encrypt(m, n, a, y, e):
assert m < n
r = getRandomRange(2, n)
enc = (lag(r, a, n), (lag(r, y, n) + lag(e, m, n)) % n)
return enc
p, q, a = legkey(256)
n = p * q
e, y, d = keygen(p, q, a)
m = bytes_to_long(flag)
c = encrypt(m, n, a, y, e)
print(f'a = {a}')
print(f'n = {n}')
print(f'y = {y}')
print(f'C = {c}')
「ここで扱われたCryptosystemについては理解する必要が無い」と私の中のゴーストが囁くので無視してnの素因数分解をまず試みる。ちなみに最近、攻殻機動隊S.A.C.を一気に見ました、面白かったです。
2つの素数$p,q$はそれぞれ128bit, 32bitというCryptoにしては比較的小さい値$r,s$を用いて次のように計算されている。
$$ \begin{aligned} p = r^5 + s \cr q = r+s \end{aligned} $$
ここで$r \ll s$なので$N = pq \approx r^6$である。そこで、ある程度素数生成の実験を繰り返すと$|N^{1/6} - r|$は高々$2^{30} \approx 10^9$程度である事が判明した。というわけで$r$を$N^{1/6}$から1ずつ減らしていくことで正しい$r$を探した。
この判定には$pq = N = (r^5+s)(r+s)$より、$f(s) = s^2 + (r^5+r)s + r^6 - N$が正の整数解を持つという条件を利用した。
これは30分ぐらい回すと無事に求められ、つまり素因数分解が成功した。
あとは復号するだけだが、正直よくわかっていない。2年半CTFをやってきた勘によればenc = (lag(r, a, n), (lag(r, y, n) + lag(e, m, n)) % n)がElGamal暗号っぽい形をしていると感じたのでべき乗をlag、乗算/除算を加算/減算に対応させてElGamal暗号と同様の復号手順を経ることでlag(e,m,n)をまず求める。問題スクリプトによれば鍵生成時に秘密鍵dをd = inverse(e, (p**2 - 1) * (q**2 - 1))で求めていたのでこれをlagの第1引数に入れてlag(e,m,n)を第2引数に入れたら復号されるんじゃないかとGuessしたら何故か解けた。
r導出用のコード §
from Crypto.Util.number import long_to_bytes
from math import gcd, isqrt
from xcrypto.num_util import int_nth_root
def get_params():
a = 192948041792305023195893277034532781336
n = 772559547290160010920412621051392165317498598296084946084386444091060134053985973087541256301003639549317798291916637210182966424107689011211268907278162096553174971554689109947325734336069313105789282878112740205249104820920364881
y = 754843853942922590978288450377461057162899072980081889481597335367906588582097339709346991452615504422434823707721197330881973700388055679080814559570248350531810374624494389646277873934234170885190847719684200687267925979436889772
C = (9083709539234699681499154559006541145975405183323215645582033885264296926186620280958201308661746194284022873377667665062501349047202357817146222033735539058147945671541486202387767382626733526030628929826676457655813734637020574, 625771268848498566477216756364333384750869252753726246816617776940622341574266652518894117167008714362418009723919180248010211052475114496172513936468417590330695688907796560242492250071433491517329459840410014214097477377322316145)
return (a, n, y, C)
def exploit():
a,n,y,C = get_params()
start_r = int_nth_root(n, 6)
r = start_r
diff = 0
while True:
if diff % 10000000 == 0:
print(diff)
D = (r**5 + r)**2 - 4*(r**6 - n)
sqrt_D = isqrt(D)
if sqrt_D**2 == D:
print("[+] Found!!", r)
break
diff -= 1
r -= 1
if __name__ == "__main__":
exploit()
復号コード §
from Crypto.Util.number import long_to_bytes, inverse
from math import gcd, isqrt
from xcrypto.num_util import solve_quadratic_eq
def lag(k, a, n):
s, t = 2, a
if k == 0:
return 2
r = 0
while k % 2 == 0:
r += 1
k //= 2
B = bin(k)[2:]
for b in B:
if b == '0':
t = (s * t - a) % n
s = (s **2 - 2) % n
else:
s = (s * t - a) % n
t = (t** 2 - 2) % n
for _ in range(r):
s = (s ** 2 - 2) % n
return s
def factorize(n, r):
ss = solve_quadratic_eq(1, r**5+r, r**6 - n, int_sol=True)
s = ss[0] if ss[0] > 0 else ss[1]
p = r**5 + s
q = s+r
assert p*q == n
return (p,q)
def get_params():
a = 192948041792305023195893277034532781336
n = 772559547290160010920412621051392165317498598296084946084386444091060134053985973087541256301003639549317798291916637210182966424107689011211268907278162096553174971554689109947325734336069313105789282878112740205249104820920364881
y = 754843853942922590978288450377461057162899072980081889481597335367906588582097339709346991452615504422434823707721197330881973700388055679080814559570248350531810374624494389646277873934234170885190847719684200687267925979436889772
C = (9083709539234699681499154559006541145975405183323215645582033885264296926186620280958201308661746194284022873377667665062501349047202357817146222033735539058147945671541486202387767382626733526030628929826676457655813734637020574, 625771268848498566477216756364333384750869252753726246816617776940622341574266652518894117167008714362418009723919180248010211052475114496172513936468417590330695688907796560242492250071433491517329459840410014214097477377322316145)
r = 302915847001663746574137782281707162419
p,q = factorize(n, r)
return (a, n, y, C, p, q)
def decrypt():
a, n, y, C, p, q = get_params()
e = 65537
# decryption (if factorization succeed)
c1, c2 = C
order = (p**2 - 1) * (q**2 - 1)
_d = inverse(e, order)
x = pow(_d, e, n)
dec = (c2 - lag(x, c1, n)) % n
_m = lag(_d, dec, n)
print(long_to_bytes(_m))
if __name__ == "__main__":
decrypt()
- Flag:
ASIS{N0w_LUc4s_vers10n_Of_the_El_Gamal_3nCryp7iOn_5cH3mE_:P}
Thanks for reading! Read other posts?