SECCON 2020 Writeup

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}