1. はじめに
2020/8/22 9:00(JST)～2020/8/24 8:59(JST) Google Capture The Flag 2020にソロ参加しました。
結果は$2$問を解いて$148$点$268$位（CTF Time上だと$259$位？）でした。
あと$1$問解きたかったのですが、まったく違う方向に進んでしまった問題もあって結局叶いませんでした。
2. Write up
2-1 BEGINNER (Reverse, easy)
問題文
Dust off the cobwebs, let's reverse!
ファイル
a.out（ELF バイナリ）
解法
とりあえず、objdumpでダンプ取ってみて、
10be: 66 0f 38 00 05 a9 2f pshufb xmm0,XMMWORD PTR [rip+0x2fa9] # 4070 <SHUFFLE>
10c5: 00 00
10c7: 66 0f fe 05 91 2f 00 paddd xmm0,XMMWORD PTR [rip+0x2f91] # 4060 <ADD32>
10ce: 00
10cf: 66 0f ef 05 79 2f 00 pxor xmm0,XMMWORD PTR [rip+0x2f79] # 4050 <XOR>
10d6: 00
10d7: 0f 29 44 24 10 movaps XMMWORD PTR [rsp+0x10],xmm0
10dc: e8 4f ff ff ff call 1030 <strncmp@plt>
みたいなのがあったので、これを逆演算すればいいのかなと思ったのですが、IDA freeで覗いて分岐構成を見ているとどこからともなく「angrで行けるんじゃね？」という悪魔の囁きが・・・。
で、以下の通りPython3からangrにぶん投げたらフラグ吐いてくれました。
>>> import angr
>>> p = angr.Project("./a.out")
WARNING | 2020-08-21 22:02:59,259 | cle.loader | The main binary is a position-independent executable. It is being loaded with a base address of 0x400000.
>>> state = p.factory.entry_state()
>>> sim = p.factory.simulation_manager(state)
>>> sim.explore(find=(0x400000+0x111D,),avoid=(0x400000+0x1110,))
WARNING | 2020-08-21 22:05:24,104 | angr.state_plugins.symbolic_memory | The program is accessing memory or registers with an unspecified value. This could indicate unwanted behavior.
WARNING | 2020-08-21 22:05:24,105 | angr.state_plugins.symbolic_memory | angr will cope with this by generating an unconstrained symbolic variable and continuing. You can resolve this by:
WARNING | 2020-08-21 22:05:24,105 | angr.state_plugins.symbolic_memory | 1) setting a value to the initial state
WARNING | 2020-08-21 22:05:24,105 | angr.state_plugins.symbolic_memory | 2) adding the state option ZERO_FILL_UNCONSTRAINED_{MEMORY,REGISTERS}, to make unknown regions hold null
WARNING | 2020-08-21 22:05:24,105 | angr.state_plugins.symbolic_memory | 3) adding the state option SYMBOL_FILL_UNCONSTRAINED_{MEMORY_REGISTERS}, to suppress these messages.
WARNING | 2020-08-21 22:05:24,105 | angr.state_plugins.symbolic_memory | Filling memory at 0x7fffffffffefff8 with 56 unconstrained bytes referenced from 0x108a7f0 (strncmp+0x0 in libc.so.6 (0x8a7f0))
WARNING | 2020-08-21 22:05:24,106 | angr.state_plugins.symbolic_memory | Filling memory at 0x7fffffffffeff70 with 8 unconstrained bytes referenced from 0x108a7f0 (strncmp+0x0 in libc.so.6 (0x8a7f0))
WARNING | 2020-08-21 22:05:24,118 | angr.state_plugins.symbolic_memory | Filling memory at 0x7ffffffffff0030 with 16 unconstrained bytes referenced from 0x108a7f0 (strncmp+0x0 in libc.so.6 (0x8a7f0))
<SimulationManager with 2 active, 1 found>
>>> print(sim.found[0].posix.dumps(0))
b'CTF{S1MDf0rM3!}'
日付がずれているのはご愛敬ということで。
フラグ
CTF{S1MDf0rM3!}
2-2 CHUNK NORRIS (Crypto, easy)
問題文
Chunk Norris is black belt in fast random number generation.
ファイル
challenge.py
#!/usr/bin/python3 -u
import random
from Crypto.Util.number import *
import gmpy2
a = 0xe64a5f84e2762be5
chunk_size = 64
def gen_prime(bits):
s = random.getrandbits(chunk_size)
while True:
s |= 0xc000000000000001
p = 0
for _ in range(bits // chunk_size):
p = (p << chunk_size) + s
s = a * s % 2**chunk_size
if gmpy2.is_prime(p):
return p
n = gen_prime(1024) * gen_prime(1024)
e = 65537
flag = open("flag.txt", "rb").read()
print('n =', hex(n))
print('e =', hex(e))
print('c =', hex(pow(bytes_to_long(flag), e, n)))
output.txt
n = 0xab802dca026b18251449baece42ba2162bf1f8f5dda60da5f8baef3e5dd49d155c1701a21c2bd5dfee142fd3a240f429878c8d4402f5c4c7f4bc630c74a4d263db3674669a18c9a7f5018c2f32cb4732acf448c95de86fcd6f312287cebff378125f12458932722ca2f1a891f319ec672da65ea03d0e74e7b601a04435598e2994423362ec605ef5968456970cb367f6b6e55f9d713d82f89aca0b633e7643ddb0ec263dc29f0946cfc28ccbf8e65c2da1b67b18a3fbc8cee3305a25841dfa31990f9aab219c85a2149e51dff2ab7e0989a50d988ca9ccdce34892eb27686fa985f96061620e6902e42bdd00d2768b14a9eb39b3feee51e80273d3d4255f6b19
e = 0x10001
c = 0x6a12d56e26e460f456102c83c68b5cf355b2e57d5b176b32658d07619ce8e542d927bbea12fb8f90d7a1922fe68077af0f3794bfd26e7d560031c7c9238198685ad9ef1ac1966da39936b33c7bb00bdb13bec27b23f87028e99fdea0fbee4df721fd487d491e9d3087e986a79106f9d6f5431522270200c5d545d19df446dee6baa3051be6332ad7e4e6f44260b1594ec8a588c0450bcc8f23abb0121bcabf7551fd0ec11cd61c55ea89ae5d9bcc91f46b39d84f808562a42bb87a8854373b234e71fe6688021672c271c22aad0887304f7dd2b5f77136271a571591c48f438e6f1c08ed65d0088da562e0d8ae2dadd1234e72a40141429f5746d2d41452d916
解法
RSA問題で、秘密鍵のつくり方（素数の取り方）に問題があって・・・という系統の問題です。「解ける...私にも、問題が解ける！」（※池田秀一ボイスで再生してください）という感触が得られたので、取り組むことにしました。
実際、素数は $\overline{a^0s}X^{15}+\overline{a^1s}X^{14}+\overline{a^2s}X^{13}+...+\overline{a^{14}s}X+\overline{a^{15}s}$、ただし$X=2^{64}$、$\overline{a^{i}s}$ は $a^{i}s \mod 2^{64}$ の代表元（$0\le a^is\lt2^{64}$）の形をしているので、
p=\overline{a^0s_p}X^{15}+\overline{a^1s_p}X^{14}+\overline{a^2s_p}X^{13}+...+\overline{a^{14}s_p}X+\overline{a^{15}s_p}\\
q=\overline{a^0s_q}X^{15}+\overline{a^1s_q}X^{14}+\overline{a^2s_q}X^{13}+...+\overline{a^{14}s_q}X+\overline{a^{15}s_q}
とおくと、$n$ % $2^{64}$ = ($s_p$ * $s_q$) % $2^{64}$ であり、
(1) $n$ % $2^{64}$ = ($s_p$ * $s_q$) % $2^{64}$
(2) $s_p$ * $s_q$ ≒ $n$ // $(2^{64})^{30}$
であることから、$s_p$ * $s_q$ の候補を見つけ出すことが可能です（もうちょっとスマートなやり方があるかと思いますが、競技中は上の考え方でやりました）。
あとは、この候補を素因数分解し、積の組み合わせで$s_p$ の候補を列挙、そしてそこから生成される $p$ および $q:=n/p$ が素数でありかつ $s_p$ がもつ条件「$s$ & mask = mask（ただし、mask=0xc000000000000001）」を満たすような$s_p$を探せばOK、ということになります。
やや天下り的な記述もありますが、ソルバーは以下のものとなります。
solve.py
from Crypto.Util.number import *
from factordb.factordb import FactorDB
import gmpy2
import itertools
a = 0xe64a5f84e2762be5
chunk_size = 64
mask = 0xc000000000000001
bits = 1024
mod = 2**chunk_size
n = 0xab802dca026b18251449baece42ba2162bf1f8f5dda60da5f8baef3e5dd49d155c1701a21c2bd5dfee142fd3a240f429878c8d4402f5c4c7f4bc630c74a4d263db3674669a18c9a7f5018c2f32cb4732acf448c95de86fcd6f312287cebff378125f12458932722ca2f1a891f319ec672da65ea03d0e74e7b601a04435598e2994423362ec605ef5968456970cb367f6b6e55f9d713d82f89aca0b633e7643ddb0ec263dc29f0946cfc28ccbf8e65c2da1b67b18a3fbc8cee3305a25841dfa31990f9aab219c85a2149e51dff2ab7e0989a50d988ca9ccdce34892eb27686fa985f96061620e6902e42bdd00d2768b14a9eb39b3feee51e80273d3d4255f6b19
e = 0x10001
c = 0x6a12d56e26e460f456102c83c68b5cf355b2e57d5b176b32658d07619ce8e542d927bbea12fb8f90d7a1922fe68077af0f3794bfd26e7d560031c7c9238198685ad9ef1ac1966da39936b33c7bb00bdb13bec27b23f87028e99fdea0fbee4df721fd487d491e9d3087e986a79106f9d6f5431522270200c5d545d19df446dee6baa3051be6332ad7e4e6f44260b1594ec8a588c0450bcc8f23abb0121bcabf7551fd0ec11cd61c55ea89ae5d9bcc91f46b39d84f808562a42bb87a8854373b234e71fe6688021672c271c22aad0887304f7dd2b5f77136271a571591c48f438e6f1c08ed65d0088da562e0d8ae2dadd1234e72a40141429f5746d2d41452d916
inv_a = inverse(a,mod)
y = n // 2 ** (chunk_size * (bits//chunk_size - 1) * 2)
n0 = ((n % mod) * pow(inv_a, (bits//chunk_size - 1) * 2 ,mod)) % mod
y_mod = y % mod
cand_sp_sq = y - (y_mod - n0 + mod)
f = FactorDB(cand_sp_sq)
f.connect()
factors =f.get_factor_list()
#factors = [3, 5, 41, 43, 509, 787, 31601, 258737, 28110221, 93627982031]
cand_s = []
for i in range(2, len(factors)-2):
for lst in list(itertools.combinations(factors,i)):
s = 1
for f in lst:
s = s * f
if(s & mask == mask and (cand_sp_sq // s) & mask == mask):
cand_s.append(s)
for s0 in cand_s:
s = s0
p = 0
for _ in range(bits // chunk_size):
p = (p << chunk_size) + s
s = a * s % 2 ** chunk_size
if gmpy2.is_prime(p) and n % p == 0 and gmpy2.is_prime(n // p):
break
else:
continue
break
q = n // p
phi = (p-1) * (q-1)
d = gmpy2.invert(e,phi)
print(long_to_bytes(pow(c,d,n)).decode())
フラグ
CTF{donald_knuths_lcg_would_be_better_well_i_dont_think_s0}
3.おわりに
心身とも心地よく疲れました。
来年はCryptoを半分以上解いて二桁順位に食い込めるよう精進したいです。