TSG LIVE! 8 CTF
はじめに
毎週恒例のチーム内で問題を持ち寄って適当に解く会で、今週は誰も出ていなかったTSG LIVE! 8 CTFのバーチャルコンテスト(なのに何故か参加者全員Crypto開始縛り)をしたのでそのWriteupを書きます。
なお、当日は住んでる建物のインターネットのメンテナンスで参加出来ませんでした。
Roulette
次のようなスクリプトが動いている
import numpy as np
from flag import flag
class RNG:
def __init__(self):
self.p = np.random.randint(2**32)
self.q = np.random.randint(2**32)
self.r = np.random.randint(2**32)
self.x = np.random.randint(2**32)
def next(self):
self.x = (self.p * self.x + self.q) % self.r
return self.x
money = 5
rng = RNG()
print("GAME OF ROULETTE")
print("Obtain 1 million money to earn a secret flag!")
for round in range(7):
print("--------------------")
print("Round {}".format(round+1))
print("You have {} money.".format(money))
a = int(input("How much will you bet?\n> "))
assert 1 <= a <= money
n = int(input("What number will you bet on?\n> "))
assert 0 <= n <= 36
m = rng.next() % 37
print("Your guess: {} Result: {}".format(n, m))
if n == m:
print("You win {} money!".format(a*36))
money += a*36
else:
print("You lose {} money.".format(a))
money -= a
if money <= 0:
print("You are broke.")
break
if money >= 1000000:
print("Good job! Here is your flag: {}".format(flag))
break
print("GAME OVER")
ルーレットを模したゲームが動いている。ルールは次の通り。
- 7回まで
- 1回ごとに所持金までの額を賭けることが出来て、当たると36倍になって返ってくる
- 当然だが所持金が0になると終了する
- 所持金が1000000を超えるとフラグが開示される
ルーレットの値を決めるのには線形合同法を使っており、そのパラメータは、シードも含めて全て32bit整数からランダムに選ばれる。そうやって出た値を37で割った余りがルーレットの数字となる。また、各回ごとに出た値は知ることが出来る。
線形合同法のパラメータは$p,q,r$と、シード$x$からなっており$x_i \equiv px_{i-1} + q \mod r$で乱数が生成される。
ここで$r$が37の倍数である場合を考えると、$x_i \equiv px_{i-1} + q \mod 37$も成り立つし、その確率は1/37とそこまで低くない。よって、このパターンを引いた際は、ルーレットの値を決定するために37で割った余りを取る必要は実質無くなる。
ゲームごとに出目もわかることから、3回値を入手すると次のようになる。
- $x_1 \equiv px_0+q \mod 37$
- $x_2 \equiv px_1+q \mod 37$
- $x_3 \equiv px_2+q \mod 37$
ここで、$x_2 - x_3 \equiv p(x_1 - x_2) \mod 37$で、$p$以外既知なので$p \equiv \frac{x_2 - x_3}{x_1-x_2} \mod 37$で求めることが出来る。$p$が求まったので乱数の式から$q$も求めることが出来る。
よってこのパターンであれば、4回目以降の値を完全に予測出来るのであとは全額賭け続ければ1000000になる。
コードは次の通り(xcrypto.lcg.solve_a_and_bは↑の計算を勝手にやってくれるやつ)
from pwn import process
from xcrypto.lcg import solve_a_and_b
while True:
sc = process(["python3", "main.py"])
def bet(a, m):
sc.recvuntil(b"you bet?\n")
sc.sendline(str(a).encode())
sc.recvuntil(b"you bet on?\n")
sc.sendline(str(m).encode())
sc.recvuntil(b"Result: ")
res = int(sc.recvline())
return res
r = 37
reses = []
for _ in range(3):
reses.append(bet(1,1))
a,b = solve_a_and_b(reses[0], reses[1], reses[2], r)
preds = []
est_money = 2
x = reses[-1]
for _ in range(4):
x = (a*x + b) % r
bet(est_money, x)
if b"lose" in sc.recvline():
break
est_money += (est_money*36)
if est_money >= 1000000:
sc.interactive()
exit()
フラグはローカルでやっただけなので無し
Forgetful RSA
次のようなスクリプトとその実行結果が与えられる
from Crypto.Util.number import getPrime, bytes_to_long
p = getPrime(512)
q = getPrime(512)
N = p * q
phi = (p - 1) - (q - 1)
e = 0x101
d = pow(e, -1, phi)
with open('flag.txt', 'rb') as f:
flag = bytes_to_long(f.read())
c = []
for i in range(flag.bit_length() + 1):
c.append(pow(flag >> i, e, N))
print(f'c = {c}')
フラグを1bitずつ削ってRSAで暗号化しているが、肝心の$N$が与えられない。$N$さえ求められれば、cの各成分と比較することで、各ビットを上から決めていくことが出来るので$N$を求める事を目指す。
暗号文のビット長はそれなりにあるので暗号文の中に"00"はほぼ必ず含まれるとする。この時、あるビットの削減で"...00"という形になった時の平文を$4m_0$とすると、次のビットの削減では$2m_0$が、その次では$m_0$が暗号化される事になる。
よってそれぞれの暗号文を$c_1, c_2, c_3$とおくと、次が成り立つ。
$$ \begin{aligned} c_1 &\equiv (2\times 2)^em_0^e \equiv 2^e(2m)^e \mod N \cr c_2 &\equiv 2^em_0^e \mod N\cr c_3 &\equiv m_0^e \mod N \end{aligned} $$
これより、$c_2 \equiv 2^ec_3 \mod N$と$c_1 \equiv 2^ec_2 \mod N$が成り立つので、どちらの式も両辺差を取ると$N$の倍数が手に入ることが期待出来る。よって最大公約数をとって$N$を求めることが出来る。このような$c_1, c_2, c_3$は"00"というビット列が存在していれば存在するので、インデックスを総当りする。
後は明らかにフラグの下のビットから決めることが出来るのでそれをして終わり。スクリプトは次のようになった。
from output import c
from math import gcd
from xcrypto.num_util import list_gcd
from Crypto.Util.number import long_to_bytes
e = 0x101
c.reverse()
ns = []
coeff = 2**e
for i in range(10, len(c)-2):
lhs1 = c[i+1] - coeff*c[i]
lhs2 = c[i+2] - coeff*c[i+1]
g = gcd(lhs1, lhs2)
if g > 114514:
ns.append(g)
N = list_gcd(ns)
for x in range(2, 1000):
assert N % x != 0, x
b_flag = ""
for _c in c:
res1 = pow(int(b_flag + "0", 2), e, N)
res2 = pow(int(b_flag + "1", 2), e, N)
if res1 == _c:
b_flag = b_flag + "0"
elif res2 == _c:
b_flag = b_flag + "1"
else:
print("ha?")
exit()
flag = int(b_flag, 2)
print(long_to_bytes(flag))
フラグはTSGLIVE{mY_m3MoRy-m4y_Impr0ve_s0me_D4y..._b1t_by_6it!}であった。
Two Keys
次のようなスクリプトとその実行結果が与えられる
from Crypto.Util.number import *
from flag import flag
def nextPrime(n):
while True:
n += 1
if isPrime(n):
return n
class RSA:
def __init__(self, p, q):
assert isPrime(p) and isPrime(q)
self.p = p
self.q = q
self.e = 65537
self.d = pow(self.e, -1, (self.p-1) * (self.q-1))
def encrypt(self, x):
return pow(x, self.e, self.p * self.q)
def decrypt(self, y):
return pow(y, self.d, self.p * self.q)
def printPublicKey(self):
print(f"N = {self.p * self.q}")
print(f"e = {self.e}")
p = getPrime(512)
q = getPrime(512)
pp = nextPrime(p)
qq = nextPrime(q)
rsa1 = RSA(p, q)
rsa2 = RSA(pp, qq)
x1 = int.from_bytes(str.encode(flag[:len(flag)//2]), "big")
x2 = int.from_bytes(str.encode(flag[len(flag)//2:]), "big")
y1 = rsa1.encrypt(x1)
y2 = rsa2.encrypt(x2)
assert x1 == rsa1.decrypt(y1)
assert x2 == rsa2.decrypt(y2)
print("First half:")
rsa1.printPublicKey()
print(f"y = {y1}")
print()
print("Second half:")
rsa2.printPublicKey()
print(f"y = {y2}")
2つのRSA公開鍵による暗号化が行われている。1つ目の素因数$p,q$は普通に生成されているが、2つ目はnext_prime()を使って素因数を生成しており、それぞれ$p+\alpha, q+\beta$とおくと$\alpha, \beta$は(手元の実験によると)大きくても1000程度と非常に小さい値となる。
1つ目の公開鍵である$N_1$を素因数分解出来れば2つ目もnext_prime()を使うことで素因数を求めることが出来るので、$N_1$の素因数分解を目指す。
先に述べたとおりだが、$N_1, N_2$に関して次のような関係がある。
$$ \begin{aligned} N_1 &= pq \cr N_2 &= (p+\alpha)(q+\beta) = N_1 + p\beta + q\alpha + \alpha\beta \end{aligned} $$
ここで、$q = \frac{N_1}p$を$N_2$の式に代入すると次のようになる。
$$ pN_2 = N_1 + p^2\beta + pq\alpha + p\alpha\beta $$
面倒なので移項して整理はしないが、どう考えても$p$に関する二次方程式になっている。ここで、$\alpha,\beta$は1000程度の小さい数なのでこれらを総当りし、上の二次方程式が整数解を持つ場合にそれを$p$とする。適当に回してみると偽陽性が出てくるので$N$の約数かどうかでも判定する。
スクリプトは次の通り(xcrypto.num_util.solve_quadratic_eqは二次方程式を整数の範囲で解く関数)
from xcrypto.num_util import solve_quadratic_eq
from Crypto.Util.number import *
from xcrypto.rsa import dec_pq
def nextPrime(n):
while True:
n += 1
if isPrime(n):
return n
N1 = 56857358946783738817465975297711204069935415016419932538392922530218921201217352346494361968035470184308357037387164930109496691365401965670237349367799774405061235025947852274083877022468072607753900481316564650009744632767993278947752127202134753913008582254000854930780954253903124752186965795809304941831
e = 65537
y1 = 54129553452548020723616698595285587704861441821682175273940519683163638301529404696982989366696324064594396066797701089154672560828427185057071836681043144874565113154501014407283089885871224438534781940829559886228137883794445606551971734932755694582218804069846658338752506228081788324414191778266867960340
N2 = 56857358946783738817465975297711204069935415016419932538392922530218921201217352346494361968035470184308357037387164930109496691365401965670237349367805332556208545324190423359112543995138089627600000504956531406110700016755090783444147649357626603184673602899015609448577621960908326053341685493162553923683
e = 65537
y2 = 54904189490273836503960200711350004725920576885881641688173306274762202573095421887773308652425204453956153996353028898080968805699877265273638393099277340479488951192104954084070323022216313855632506411275865181376283939786423085736432815359399351894579725901517442688632028924262380544819047494361593650323
for a in range(2, 2000, 2):
for b in range(2, 2000, 2):
res = solve_quadratic_eq(b,N1 + a*b - N2, a*N1, True)
if len(res) > 0:
for _p in res:
if N1 % _p == 0:
_q = N1 // _p
flag1 = dec_pq(y1, _p, _q, e)
_p = nextPrime(_p)
_q = nextPrime(_q)
assert _p*_q == N2
flag2 = dec_pq(y2, _p, _q, e)
print(long_to_bytes(flag1) + long_to_bytes(flag2))
フラグはTSGLIVE{pr1M3_numb3R5_4R3_pR377y_d3N53_1M0}であった。
感想してない完走
短時間で解くという事が重視されるCTFだったため、半年ぐらい前にやったRTACTFを思い出す感じで楽しかったです。見たら直ぐ解ける、という問題は少なくともCryptoには無く、色々と考えさせられました。
反省点としては、Two Keysに時間をかけた結果、100分でCryptoを全部解けなかったという大失態を犯したことが挙げられます。というのも、適当に変形して$p,q$で法を取っていたらCoppersmith's Attackができそうな形になってそれに固執し、パラメータチューニングをしていたら1時間ぐらい経過して我に帰ったという感じです。変数を減らすなら$N_1 = pq$から$q = N_1/p$でも済む事をなぜ思い浮かばなかったのでしょうか? 不思議で仕方がありません。
今度早解き系のイベントがあったら今度は別分野でも挑戦してみたいです。