SECCON 2020 にソロで参加しました。3問しか解けなかった上、web と pwn が一切解けなかったので精神的にきつかったですが、やりきりました…結果は55位でした。
解けた問題の writeup を書いていきます。
crypto
This is RSA
require 'openssl'
def get_prime
i = OpenSSL::BN.rand(512).to_s.unpack1('H*').hex
OpenSSL::BN.new(i).prime? ? i : get_prime
end
p = get_prime
q = get_prime
n = p * q
e = 65537
m = File.read('flag.txt').unpack1('H*').hex
c = m.pow(e, n)
puts "N = #{n}"
puts "c = #{c}"
ぱっとみ普通に RSA を実装していて、「解けるか！」となった。
ruby は使ったことがないので、動作確認がてらいろいろと値を出力してみると、
hoge = OpenSSL::BN.rand(512)
puts "#{hoge}" # 8789075289580136989141860017780760182122828630114854964056373892990807181340201051588788637045557195329003635494406702355355094779917754508547687697607355
puts "#{hoge.to_s}" # 8789075289580136989141860017780760182122828630114854964056373892990807181340201051588788637045557195329003635494406702355355094779917754508547687697607355
puts "#{hoge.to_s.unpack1('H*')}" # [想定と違う] 38373839303735323839353830313336393839313431383630303137373830373630313832313232383238363330313134383534393634303536333733383932393930383037313831333430323031303531353838373838363337303435353537313935333239303033363335343934343036373032333535333535303934373739393137373534353038353437363837363937363037333535
puts "#{hoge.to_s.unpack1('H*').hex}" # 16239487839404132663621670751823682525339498548767928239304284082221282575643559773528741246442148285618215057908528122117099662069084670450114644439679340919790283345853240141449065294082614666607877812926351170250504266278822204402580595487315393009793455898975346318724367853016604792996677635557919249443011068275281439874265455062137191606898248119982002155960874293
となっており、16進数に直すところが想定挙動になっていなかった。つまり p や q は0x(3[0-9])+ という形をしている。
$p$, $q$ の下 $2(n-1)$ 桁 (16進数で。以下同様) がわかっているとき、 $n = pq$ の下 $2n$, $2n-1$ 桁目を見ることで、 $p$, $q$ の 下 $2n$, $2n-1$ 桁目をかなり限定することができる (多分一意にはならないけど、ほぼ一意)。
したがって、下の桁から順番に決めていけば、$O(10^2 \log n)$ で求まるはずである。 dfs で書いた。
from Crypto.Util.number import inverse, long_to_bytes
c = 9094564357254217771457579638296343398667095069849711922513911147179424647045593821415928967849073271368133854458732106409023539482401316282328817488781771665657515880026432487444729168909088425021111879152492812216384426360971681055941907554538267523250780508925995498013624610554177330113234686073838491261974164065812534037687990653834520243512128393881497418722817552604416319729143988970277812550536939775865310487081108925130229024749287074763499871216498398695877450736179371920963283041212502898938555288461797406895266037211533065670904218278235604002573401193114111627382958428536968266964975362791704067660270952933411608299947663325963289383426020609754934510085150774508301734516652467839087341415815719569669955613063226205647580528
e = 65537
n = 13234306273608973531555502334446720401597326792644624514228362685813698571322410829494757436628326246629203126562441757712029708148508660279739210512110734001019285095467352938553972438629039005820507697493315650840705745518918873979766056584458077636454673830866061550714002346318865318536544606580475852690351622415519854730947773248376978689711597597169469401661488756669849772658771813742926651925442468141895198767553183304485662688033274567173210826233405235701905642383704395846192587563843422713499468379304400363773291993404144432403315463931374682824546730098380872658106314368520370995385913965019067624762624652495458399359096083188938802975032297056646831904294336374652136926975731836556951432035301855715375295216481079863945383657
p_str = ""
q_str = ""
ans_p_str = ""
ans_q_str = ""
max_idx = 0
def dfs(p_str, q_str, idx):
global ans_p_str, ans_q_str, max_idx
if idx > max_idx:
ans_p_str = p_str
ans_q_str = q_str
max_idx = idx
for i in range(10):
tmp_p = int(f"3{i}" + p_str, 16)
for j in range(10):
tmp_q = int(f"3{j}" + q_str, 16)
if hex(tmp_p * tmp_q)[-2 * (idx + 1):] == hex(n)[-2 * (idx + 1):]:
# p, q に比べ n のほうが当然桁が大きいので、↑の分岐だけでは破綻する
# 考えるのが面倒だったので↓の分岐の条件は適当に決めました…
if idx > 156:
if (
hex(tmp_p * tmp_q)[-2 * (idx + 50):]
!= hex(n)[-2 * (idx + 50):]
):
continue
dfs(f"3{i}" + p_str, f"3{j}" + q_str, idx + 1)
dfs(p_str, q_str, 0)
p = int(ans_p_str, 16)
q = int(ans_q_str, 16)
phi = (p-1) * (q-1)
d = inverse(e, phi)
print(long_to_bytes(pow(c, d, n)))
SECCON{I_would_always_love_the_cryptography_and_I_know_RSA_never_gets_old_So_Im_always_a_fan_of_this_mathematical_magic_and...Wait_This_flag_can_be_longer_than_I_expected_What_happened?}
`
koharu
while True:
p = random_prime(1<<64)
if is_prime((p+1) // 2):
break
with open("flag.txt", "rb") as f:
flag = f.read()
flag = int.from_bytes(flag, "big")
PR.<x> = PolynomialRing(GF(p))
while True:
P = PR.random_element(degree=64)
if P.is_irreducible():
break
while True:
Q = PR.random_element(degree=64)
if Q.is_irreducible():
break
NP = p**P.degree()
NQ = p**Q.degree()
while True:
R = PR.random_element(degree=64)
if power_mod(R, (NP-1)//2, P) != 1 and power_mod(R, (NQ-1)//2, Q) != 1:
break
PQ = P*Q
c = []
while flag:
S = PR.random_element(degree=64)
if flag & 1:
c.append((S * S) % PQ)
else:
c.append((S * S * R) % PQ)
flag = flag >> 1
print("p =", p)
print("PQ =", PQ)
print("R =", R)
print("c =", c)
コードを見て、 interKosenCTF 2020 の bitcrypto という問題を思い出した (問題サーバーはもう稼働していないっぽいので自分の過去の writeup のリンクを貼りました)。
有限体の理論はよくわかっていないため、↑の過去問のアナロジーで考えると、暗号化された数値の各桁 (2進数表記で) に対して
power_mod(c[1], (NP-1)//2, P) == 1 and power_mod(c[1], (NQ-1)//2, Q) == 1 が成り立っていれば i 桁目は1, 違えば0とすることでデコードできそう (という期待)。実際に適当な数を生成して実験してみたところ、成り立っていそうだった (あくまで期待)。しかし P, Q がわからない。
問題文のコードを眺めていると、 if P.is_irreducible(): というのが目に止まった。有限体では因数分解が高速にできるのだろうか。
sage のページを見に行くと、 factor() という method があったため、 PQ.factor() を呼んでみると、因数分解ができた。これらを P, Q として
ans = 0
for i, cc in enumerate(c):
if power_mod(cc, (NP-1)//2, P) == 1 and power_mod(cc, (NQ-1)//2, Q) == 1:
ans += 2**i
print(ans) # この値をバイト列に変換する
を計算した
SECCON{p01y-p01y-p3r0-p3r0-hy0ukun-p3r0p3r0}
reversing
SCSBX:Reversing
独自の VM が実装されていて、その VM 上で動くプログラムを reversing する問題。 オライリー本 を思い出した。
まずは binary ファイルを読めるようにした。
from pprint import pprint
from Crypto.Util.number import bytes_to_long
name_to_num = {
"INS_PUSH": 0x20,
"INS_POP": 0x21,
"INS_DUP": 0x22,
"INS_XCHG": 0x23,
"INS_LOAD32": 0x24,
"INS_LOAD64": 0x25,
"INS_STORE8": 0x26,
"INS_STORE16": 0x27,
"INS_STORE32": 0x28,
"INS_SHOW": 0x70,
"INS_JMP": 0x30,
"INS_JEQ": 0x31,
"INS_JGT": 0x32,
"INS_JGE": 0x33,
"INS_CALL": 0x34,
"INS_ADD": 0x40,
"INS_SUB": 0x41,
"INS_MUL": 0x42,
"INS_DIV": 0x43,
"INS_MOD": 0x44,
"INS_NOT": 0x50,
"INS_AND": 0x51,
"INS_OR": 0x52,
"INS_XOR": 0x53,
"INS_SHL": 0x54,
"INS_SHR": 0x55,
"INS_ROL": 0x56,
"INS_ROR": 0x57,
"INS_READ": 0x60,
"INS_WRITE": 0x61,
"INS_MAP": 0x62,
"INS_UNMAP": 0x63,
"INS_EXIT": 0x64,
}
num_to_name = {v: k for k, v in name_to_num.items()}
code = []
idx = 0
with open("seccon.bin", "rb") as f:
try:
while True:
b = bytes_to_long(f.read(1))
if b == 0x20:
tmp = f"{idx:x} INS_PUSH"
arg = f.read(4)
tmp += f" {bytes_to_long(arg):x}"
code.append(tmp)
idx += 5
else:
code.append(f"{idx:x} {num_to_name[b]}")
idx += 1
except:
pass
pprint(code)
output.txt
['0 INS_PUSH 100000',
'5 INS_PUSH adde',
'a INS_MAP',
'b INS_PUSH 56020000',
'10 INS_CALL',
'11 INS_PUSH a020000',
'16 INS_CALL',
'17 INS_PUSH 464c4147',
'1c INS_PUSH 400adde',
'21 INS_STORE32',
'22 INS_PUSH 3a200000',
'27 INS_PUSH 800adde',
'2c INS_STORE16',
'2d INS_PUSH 6000000',
'32 INS_PUSH 400adde',
'37 INS_WRITE',
(以下略)
全部追うのは大変だったので、適当に stack を出力するコードを書き、あまり呼ばれていない命令 (例えば INS_XOR 等) 中で stack の中身を見られるようにソースコードを改変してコンパイルしなおし、実行させるなどした。
void SCSBX::__show_stack()
{
std::cout << "--------" << std::endl;
std::cout << "called: " << count << std::endl;
count += 1;
std::cout << std::endl;
for (int i = top; i >= 0; i--) {
std::cout << stack[i] << " (" << std::hex << stack[i] << ") " << std::dec << std::endl;
}
std::cout << std::endl;
}
読めてしまえば (読めてしまえば…) やっていることは単純で、 xor など逆変換可能な演算を使って、入力した FLAG の値を更新していき、プログラムの最初のほうでメモリに格納した値と一致しているかをチェックしている。 reversing のお決まりの型 (それはそう)。
from Crypto.Util.number import long_to_bytes
def int_reverse(num):
num_len = 32
f = 2 ** num_len - 1
return num ^ f
def modify(s):
ret = ""
for i in range(4):
ret += s[7 - (i * 2 + 1)] + s[7 - i * 2]
return int(ret, 16)
dead004a_hex = [
"23127646",
"c5a5be54",
"f6e8227a",
"c993b45d",
"5e175d05",
"33cd2f02",
"e66bc442",
"e8a0106d",
"78c2f453",
"2aec7972",
"39fb9154",
"1f42ac49",
"373aab49",
"12588547",
"05bb1857",
"5bfb4005",
]
dead004a = list(map(modify, dead004a_hex))
dead0000 = [0x06D35BCD]
for i in range(3 * 8):
dead0000.append(((0x77F * dead0000[-1] - 0x32A) % 2 ** 32) % 0x305EB3EA)
flag = []
for i in range(8):
tmp_flag_0 = dead004a[2 * i]
tmp_flag_1 = dead004a[2 * i + 1]
for j in range(3):
xor = dead0000[1 + 3 * i + 2 - j] ^ tmp_flag_0
xor_inv = int_reverse(xor)
tmp = tmp_flag_0
tmp_flag_0 = tmp_flag_1 ^ xor_inv
tmp_flag_1 = tmp
flag.append(long_to_bytes(tmp_flag_0)[::-1])
flag.append(long_to_bytes(tmp_flag_1)[::-1])
print(b"".join(flag))
SECCON{TfuRYYVaz8Us696t3JWNxZZPsXEmdL7cCmgzpgxXKarUOnIwhSj9tQ}