Writeup: Circle City Con 2021
先週土日に開催されていたCircle City Con 2021に出たので自分が解いた問題(OSINTを除く)と、終了後に復習した問題についてのWriteupを書きます。
なお、問題はこちらのリポジトリで公開されています。Writeup付きなので復習や参加していない人もどうぞ。
Table of Contents §
Guardian §
Babyタグが付いているRevだったので簡単な解説に留めます。
フラグを1文字ずつ先頭からチェックし、合っていたらチェックマークを表示、異なっていたところで終了というプログラムが動いている。ということは先頭から文字を決定出来るのでそれをするだけのコードを書いただけ。
問題の性質上「文字種数 x フラグの長さ」の時間がかかるのだが、アホみたいにフラグが長いのがちょっとだけ気に食わなかった。
Flag: CCC{let_m3_thr0ugh!_let_me_p4ss!_d0_y0u_th1nk_y0u_c4n_h3lp_h3r?}
Lonk §
フラグを表示してくれるPythonスクリプトとそれを動かす為のライブラリが与えられる。
じゃあ動かして終わりじゃん...という事はなく、最初の6文字は直ぐ出るものの残りはかなり時間がかかる。
フラグ開示用のスクリプトは長過ぎるので割愛するが、ライブラリの方は次のようになっている
class 我:
def __init__(self, n=None):
self.n = n
def 非(a):
h = 我()
c = h
while a > 0:
c.n = 我()
c = c.n
a -= 1
return h.n
def 常(a):
i = 0
while a:
i += 1
a = a.n
return i
def 需(a):
h = 我()
b = h
while a:
b.n = 我()
b = b.n
a = a.n
return h.n
def 要(a, b):
h = 需(a)
c = h
while c.n:
c = c.n
c.n = 需(b)
return h
def 放(a, b):
h = 需(a)
c = h
d = b
while d:
c = c.n
d = d.n
return c
def 屁(a, b):
h = 我()
c = a
while c:
h = 要(h, b)
c = c.n
return h.n
def 然(a, b):
r = 需(b)
c = r
while c.n:
c = c.n
c.n = r
d = r
c = a
while c.n:
d = d.n
c = c.n
if id(d.n) == id(r):
r = None
else:
d.n = None
return r
def 後(a, b):
h = 我()
c = b
while c:
h = 屁(h, a)
c = c.n
return h
def 睡(a, b, m):
return 然(後(a, b), m)
def 覺(n):
print(chr(常(n)), end="", flush=True)
まず注目すべきは一番上の非である。内部では最初にhという我classを作りその中に別の我を追加している形になる。よって次のような構造になっている
c.n.n.n.n ... .n = 我()
非を更に読んでみると最後の空の我()に辿り着くまでの回数が引数で与えたaになっているようである。
残りの関数を読んでみると常はこの回数を返し、需は与えられた我と同じ長さの我を返す。そして以降の関数も解析しようと思ったところで、フラグ開示用のスクリプトの上部だけを抜粋すると次のようになっている
覺(非(67))
覺(要(非(34), 非(33)))
覺(要(放(非(105), 非(58)), 非(20)))
覺(屁(非(3), 非(41)))
覺(然(非(811), 非(234)))
覺(睡(非(3), 非(5), 非(191)))
これらはCCC{m4に対応する。覺は与えられた我の長さのchrを出力する関数である。ここからそれっぽい演算を(Guessingで)逆算出来ないか試みたところ加算、減算、乗算、余り、法の下でのべき乗である事がなんとなくわかる。
というわけで非を引数aを格納するだけのクラスに改造し、残りの関数もそれに対応させたライブラリを作って差し替えたら無事にフラグが出力された。最終的に出来たライブラリは次の通り。
class Structure2:
def __init__(self, n):
self.n = n
# a階層の構造を作る
def create(a):
return Structure2(a)
# 構造が何階層かを返す
def calc(a):
return a.n
def cp(a):
return create(calc(a))
def add(a, b):
return Structure2(a.n + b.n)
def sub(a, b):
return Structure2(a.n - b.n)
def mul(a, b):
return Structure2(a.n * b.n)
def mod(a, b):
return Structure2(a.n % b.n)
def normalpow(a, b):
return Structure2(pow(a.n, b.n))
def modpow(a, b, m):
return Structure2(pow(a.n, b.n, m.n))
def dump(n):
print(chr(calc(n)), end="", flush=True)
※一応断っておくと、加算は自分で解析して、残りも四則演算だろうと当たりを付けたので完全にGuessingで解いたわけではないです。
Flag: CCC{m4Th_w1tH_L1Nk3d_l1$t5}
Poison Prime §
次のようなスクリプトが動いてる
import Crypto.Util.number as cun
import Crypto.Random.random as crr
import Crypto.Util.Padding as cup
from Crypto.Cipher import AES
import os
import hashlib
class DiffieHellman:
def __init__(self, p: int):
self.p = p
self.g = 8
self.private_key = crr.getrandbits(128)
def public_key(self) -> int:
return pow(self.g, self.private_key, self.p)
def shared_key(self, other_public_key: int) -> int:
return pow(other_public_key, self.private_key, self.p)
def get_prime() -> int:
p = int(input("Please help them choose p: "))
q = int(
input(
"To prove your p isn't backdoored, "
+ "give me a large prime factor of (p - 1): "
)
)
if (
cun.size(q) > 128
and p > q
and (p - 1) % q == 0
and cun.isPrime(q)
and cun.isPrime(p)
):
return p
else:
raise ValueError("Invalid prime")
def main():
print("Note: Your session ends in 30 seconds")
message = "My favorite food is " + os.urandom(32).hex()
print("Alice wants to send Bob a secret message")
p = get_prime()
alice = DiffieHellman(p)
bob = DiffieHellman(p)
shared_key = bob.shared_key(alice.public_key())
assert shared_key == alice.shared_key(bob.public_key())
aes_key = hashlib.sha1(cun.long_to_bytes(shared_key)).digest()[:16]
cipher = AES.new(aes_key, AES.MODE_ECB)
ciphertext = cipher.encrypt(cup.pad(message.encode(), 16))
print("Here's their encrypted message: " + ciphertext.hex())
guess = input("Decrypt it and I'll give you the flag: ")
if guess == message:
print("Congrats! Here's the flag: " + os.environ["FLAG"])
else:
print("That's wrong dingus")
if __name__ == "__main__":
try:
main()
except ValueError as e:
print(e)
どうやらDH鍵共有が行われていて、それで共有された値から鍵を決定し、メッセージを暗号化した結果をくれる。これを復号した結果がメッセージと一致すればフラグが表示される。
普通のDH鍵共有問題と異なるのは法である素数pをこちらから指定出来ることである。但し、次の条件がある。
pは素数p - 1の素因数で128bit以上の素数qも同時に与える
この問題の鍵となるのはDH鍵共有の際に開示される公開鍵$g^x \bmod p$が公開されていないことである($x$は秘密鍵)。ということは離散対数問題を解けるようなpを提出しても特に使い所は無い。
となると考えられるのは$\mathbb{Z}_p^*$におけるg (= 8)の位数が小さくなるようなpを提出することである。gの位数が小さいのであればDH鍵共有で共有される値が取りうる範囲も少なくなり、鍵を総当り出来る。
というわけで$g^e \equiv 1 \bmod p$となる$e$が小さくなるような$p$の導出を目指す。
右辺を移項してから左辺を因数分解すると次のようになる。ここで$8^e = (2^e)^3$であることを利用した。
$$ (2^e - 1)((2^e)^2 + 2^e + 1) \equiv 0 \bmod p $$
これより$2^e - 1 \equiv 0 \Leftrightarrow 2^e - 1 = kp$となるので$2^e - 1$を計算し、素因数に大きな$p$が現れるものを探す。FactorDB等を利用しても良かったのだが、面倒なので10000000までの素数で雑に割って出てきた因数の内、一番大きい数が素数であるかを判定して探した。
こうやって求めた$p$の中から$p-1$が大きな素因数を持つものを探した。これは見つかった$p$の数がそこまで多くなかったのでFactorDBに突っ込んで判定した。
これで$e = 881$の時の$p$が条件を満たす事がわかったので素因数であるqと一緒に提出して暗号文を総当りで復号した。
使用したスクリプトは次の通り
import Crypto.Util.number as cun
import Crypto.Random.random as crr
import Crypto.Util.Padding as cup
from Crypto.Cipher import AES
import os
import hashlib
from pwn import remote
from xcrypto.prime import create_sieve, is_prime
sieve = create_sieve(10000000)
primes = []
for i, is_p in enumerate(sieve):
if is_p:
primes.append(i)
print("[+] primes are created")
def easy_factorize(n):
factors = []
for p in primes:
while n % p == 0:
n //= p
factors.append(p)
if n == 1:
return factors
return factors + [n]
def get_largest_factor(n):
return easy_factorize(n)[-1]
def has_large_factor(n):
large_factor = get_largest_factor(n)
if large_factor.bit_length() > 128 and is_prime(large_factor):
return True, large_factor
return False, None
def search_primes():
factors = []
exponent = 128
two_exp = pow(2, exponent)
for i in range(1000):
term = two_exp - 1
res, p = has_large_factor(term)
if res:
print("[+] found:", exponent, p)
factors.append((p, exponent))
two_exp *= 2
exponent += 1
return factors
# from `search_primes` and factordb.com
def get_params():
p = 609975771894476528674847741770477550690431975984816508022169315752408668993737964630175742325288277204552613243684812253451253427056346412559151033770967839107719594288877646641877521578455691636766459660797203894013905167748331753651455643293131241572177344321
e = 881
q = 15138363943702743414985849001110688007893252776119878248055700358370333679110882929900173580454870111418797892031803506068105088295467180152699913928496417418117370927810699181181027547022238296846731688545530752594436880185320372547
return p, e, q
if __name__ == "__main__":
host = "35.224.135.84"
port = 4000
sc = remote(host, port)
p, e, q = get_params()
sc.recvuntil(b"choose p: ")
sc.sendline(str(p))
sc.recvuntil(b"(p - 1): ")
sc.sendline(str(q))
sc.recvuntil(b" message: ")
ct = bytes.fromhex(sc.recvline().strip().decode())
print(ct)
for i in range(e):
shared_key = pow(8, i, p)
aes_key = hashlib.sha1(cun.long_to_bytes(shared_key)).digest()[:16]
cipher = AES.new(aes_key, AES.MODE_ECB)
pt = cipher.decrypt(ct)
if pt[:11] == b"My favorite":
print("[+] Found!!")
pt = cup.unpad(pt, 16)
print(pt)
break
sc.recvuntil(b"the flag: ")
sc.sendline(pt)
sc.interactive()
Flag: CCC{sm0l_subgr0up_w1th_a_m3rs3nn3_pr1m3}
4番目に解いたので惜しくも3rd Bloodを逃した、Web勢とPwn勢が1st~3rd Bloodを取っていたのでCryptoも取りたかった。
No Stone Left Unturned §
この問題は解けませんでしたが、終了後にCTFのDiscordからWriteupを回収して復習しました
次のようなスクリプトとその実行結果が与えられる。
from gmpy2 import next_prime, is_prime
import random, os, sys
if __name__ == "__main__":
random.seed(os.urandom(32))
p = next_prime(random.randrange((1<<1024), (1<<1024) + (1<<600)))
pp = (p * 7) // 11
q = next_prime(random.randrange(pp - (1<<520), pp + (1 << 520)))
with open(sys.argv[1], "rb") as f:
flag = int.from_bytes(f.read(), "big")
assert is_prime(p)
assert is_prime(q)
N = p * q
assert flag < N
e = 0x10001
c = pow(flag, e, N)
with open("out.txt", "w") as f:
f.write(f"N = {hex(N)}\n")
f.write(f"e = {hex(e)}\n")
f.write(f"c = {hex(c)}\n")
RSAだが$p = 2^{1024} + p_0, q = \frac 7{11} p + q_0$となっている(ここで$|p_0| \lt 2^{600}, |q_0| \lt 2^{520}$である)。
今回は$p,q$どちらも如何にもな近似が出来るのだが、使うのは$q$の方で$11q = 7p + 11q_0$となり、$q_0$が520bitとそこまで大きくない事から$11q \approx 7p$とすることが出来る。
ということは$11q \cdot 7p = 77N$は近い2数の積となっている事からフェルマー法が適用出来る。
※一見この2数の差である$11q - 7p = 11q_0$は520bit程度と大きいように見えるが、実はフェルマー法は有効($N = (a+b)(a-b)$と因数分解を試みた時に$a$の増加に対して$b$が$N^{1/4}$ぐらい増加するため)。これに引っかかって当日はチームメイトと共にフェルマー法を棄却してしまった。
使用スクリプトは次の通り
from Crypto.Util.number import long_to_bytes
from xcrypto.rsa import dec_pq
from xcrypto.prime import fermat_method
from math import isqrt
if __name__ == "__main__":
N = 0xa2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba2e8ba93f56d1e890d1827d8ae8d40172a2dfafaa73523dd318c608bd4169d702442e6d153ae0637766f635255f4c1ee6bc694589b2708ae9061fb84f9db9da7199996c519635decfb53b4ccfde2bf9e89f70de9172bd370be887e8e1009b278774ee2449ce3ea3b76428506b4a98beda6e3c9aabbf1164e088f27554282d7909ef2ae61fb5316e705e3ea72cba9df06af06e54c3ee898dab8ed245e26290f59feeec9f58e61c4a2051086234fe48b42399a74452b87829da28f3e88a5a4b01b72d045b296297a3da34b9a5c20cb
e = 0x10001
c = 0x2d1f77201435e00d3355246cc4de54b3c98a801f688500ff1e824d985f225f95415019188af01c39c80393e648e5e51bab80e1abfda82a74490fe58ef82afde4bed2999b10ac71f241f20564f5d2461cd57b50033c0fe64319b246ad241846b2ab37328f83d0a77fe5c3564cec18dbc577fdacad417925d208735d8b916779f567ef863dba594d9d035c99e6210db9397797c10e900a1d4a3bce2f87502c23f2e909808c10ac675affb41b3e0769360c959289338ce2877813c723524718d84a75b2209ba4f3560fcbc82da69d6b2f86c32970b325ec034a060fc62f6b3a97ae01cdfc8aeb35df03d92af88a7b60831254095fb66ce73b2c5941440721899dc1
_n = 7*11*N
p, q = fermat_method(_n)
print(p, q)
if p % 7 == 0:
p //= 7
q //= 11
else:
p //= 11
q //= 7
assert p*q == N
print(long_to_bytes(dec_pq(c, p, q, e)))
Flag: CCC{b4d_j0k3s_4b0ut_ferm4t's_f1rst_n4m3}
ちなみに解いていた時は未知数$p_0, q_1$が小さいので多変数Coppersmithだと思っていた。式変形をしまくっていたが結局上手くいかずに12時間無駄にした。