📝

SECCON 2020 CTF writeup

2020/10/12に公開

SECCON CTF Online CTF

結果は This is RSA, koharu, urara, Beginner's Capsule, SCSBX:Reversing の5問を解いて884 pts. 39位でした。

どの問題も3時間以上は頭を抱える箇所があり、warm upからすべての問題やりごたえたっぷりでした。
お腹いっぱいです。

どの問題も解いていて楽しい問題で、きっと裏にはたくさんの問題がボツになっていて、たくさんに人が頑張ってレビューしたんだなという感じが伝わってきました。

本当に運営陣の方、楽しい問題をありがとうございました!

このブログでは動画では見にくいソースコードと、動画で言い損ねた解説を少し付け加えます。

基本的にはこちらの動画を見ていただけたら良いかなと思います( Sorry Japanese only. :sob: :sob: )

This is RSA

youtube: https://youtu.be/VUea1wDQe_A?t=272

Category: crypto
Value: 124
Solved: 62

この問題は筆算の下の桁から確定させていく形で素因数分解を行います。
動画内で筆算で説明していますが、一般の16進数では不可能です。
この問題は一つの枠あたりに、16進数4桁65537に対して、10*10の100通りしか計算結果がなく、計算結果を見るだけで、その掛け算の結果が何と何をかけ合わせた結果なのか、一意に定まることがポイントです。

例えば、1桁目が2になる掛け算は 6*2, 1*2, 3*4, ... とたくさんの組み合わせが考えられますが、使える数字が制約されていればこの限りではありません。
この問題は使える数字を制約することで一意に定めています。
当然、一般のバイト列ではこの方法では素因数分解では不可能です。

target = 13234306273608973531555502334446720401597326792644624514228362685813698571322410829494757436628326246629203126562441757712029708148508660279739210512110734001019285095467352938553972438629039005820507697493315650840705745518918873979766056584458077636454673830866061550714002346318865318536544606580475852690351622415519854730947773248376978689711597597169469401661488756669849772658771813742926651925442468141895198767553183304485662688033274567173210826233405235701905642383704395846192587563843422713499468379304400363773291993404144432403315463931374682824546730098380872658106314368520370995385913965019067624762624652495458399359096083188938802975032297056646831904294336374652136926975731836556951432035301855715375295216481079863945383657

lhs = 0
rhs = 0
cnt = 0

while True:
    mask = (1 << (cnt+1)*8)-1

    okcnt = 0

    for i in list(range(10)) + [0x30]:
        num1 = (i ^ 0x30) << (cnt * 8)
        num1 += lhs
        for j in list(range(10)) + [0x30]:
            num2 = (j ^ 0x30) << (cnt * 8)
            num2 += rhs

            if (num1 * num2) & mask == target & mask:
                okcnt += 1
                lhs = num1
                rhs = num2

        if okcnt == 1:
            break            

    if target&mask == target:
        break

    cnt += 1

assert(lhs * rhs == target)

print(hex(lhs))
print(hex(rhs))

koharu

youtube: https://youtu.be/VUea1wDQe_A?t=936

Category: crypto
Value: 144
Solved: 44

放送中も記憶を喪失していましたが、現在も解き方の記憶を喪失しています。

interkosenCTFの bit cipherに近い問題ですね

この問題のポイントは ランダムな数(多項式) S を 二乗したもの S^2(NP-1)//2 乗することで、 S^{(NP-1)} \mod n となり、なんかいい感じになって1になります。

適当にやったらできてしまったので証明等はしてません。

S^2は1になるので、それに1にならない数 R をかければ R になります。 1にならない数を保証するコードが問題文の

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 を使用して行うのですが、 PQ は渡されているものの PQ はもらっていないのでこの式は通すことができません。

PQ は 多項式だしなんか素因数分解しやすそうだなと思ってsage mathになげたら素因数分解できたので、この問題はもうこれでおしまいです。

ちなみにprintするときにflushしないと動画みたいにリアルタイムで出力されなくて、思ったより時間がかかるので不安になります。


# p = 
# PQ =
# R =
# c =

PR.<x> = PolynomialRing(GF(p))

l = list(PQ.factor())
print(l)
print(len(l))
S = PR.random_element(degree=64)
P = l[0][0]
Q = l[1][0]

NP = p**64
NQ = p**64

out = 0

for cc in reversed(c):
    if power_mod(cc, (NP-1)//2, P)== 1 or power_mod(cc, (NQ-1)//2, Q) == 1:
        print(1, end = "", flush=True)
    else:
        print(0, end = "", flush=True)
print()

Beginner's Capsule

youtube: https://youtu.be/VUea1wDQe_A?t=1888

Category: web (+ misc)
Value: 130
Solved: 55

webはかなり初心者なのですがplaygroundをガチャガチャやっていたらjsタブなるものを見つけてさらにガチャガチャしていたらWeakMapを則れば良いことに気づいたのでここまでくればおしまいです。

プロトタイプ汚染みたいなこととかいろいろ試してました。

以下のようなソースコードを投げればフラグを教えてくれます。

他の方のwriteupによると本当に最新のtypescript? だと動かないみたいですね

// @ts-ignore
__classPrivateFieldSet = (flag && flag.__classPrivateFieldSet) || function (receiver, privateMap, value) {
    if (!privateMap.has(receiver)) {
        throw new TypeError("attempted to set private field on non-instance");
    }
    console.log(privateMap.get(flag));
    return value;
};


const flag2 = new Flag("Hello");

SCSBX:Reversing

動画リンク: https://youtu.be/VUea1wDQe_A?t=2672

Category: web (+ misc)
Value: 129
Solved: 56

まず与えられたバイナリファイルを動画のようにアセンブリコードライクなコードに落とし、その後は等価な読みやすいものに置き換えていきました。
数値から文字列に変換するのはしんどかったのでvim芸でなんとかしました(https://youtu.be/VUea1wDQe_A?t=2977)

0xa 	: MAP 0xdead0000 0x1000

0x10 	: CALL 0x256
0x16 	: CALL 0x20a
0x21 	: STORE32[0xdead0004] = 0x47414c46
0x2c 	: STORE16[0xdead0008] =  0x203a
0x37 	: WRITE(0xdead0004, 0x6)
0x42 	: READ(0xdead000a, 0x40)
0x43 	: PUSH  0x8
0x4d 	: JMP 0x10e

--------------------------------------------------

0x4e

arg_0 = stack[top]


0x5a 	: PUSH  0xdead000e + 0x8 * (0x8 - arg_0)
0x66 	: PUSH  0xdead000a + 0x8 * (0x8 - arg_0)
0x5a 	: PUSH  LOAD32(0xdead000e + 0x8 * (0x8 - arg_0))
0x66 	: PUSH  LOAD32(0xdead000a + 0x8 * (0x8 - arg_0))
0x98 	: PUSH  0x3
0xa2 	: JMP 0xdd


0xa2

--------------------------------------------------

0xa3


arg_0 = stack[top] - 0x1
arg_1 = stack[top - 1] = arg_2 ^ CALL_0x216(arg_1)
arg_2 = stack[top - 2] = arg_1

0xdc


--------------------------------------------------

0xdd


0xf2 	: arg_0 == 0x0 ? 0xf3 : 0xa3
0xf3 	: STORE32[arg_4] = arg_1
0x100 	: STORE32[arg_3] = arg_2

arg_5 = stack[top - 5] - 0x1

0x10d

--------------------------------------------------

arg_0 = stack[top]

0x10e 	: arg_0 == 0x0 ? 0x124 : 0x4e
0x124 	: POP
0x125 	: PUSH  0x0
0x12a 	: PUSH  0x8
0x134 	: JMP 0x195 

--------------------------------------------------

0x135

arg_0 - 1
arg_1 = stack[top-1] = arg_1 | LOAD32(0x40 + 0xdead000e + (0x8 * (arg_0 - 0x1))) - LOAD32(0xdead000e + (0x8 * (arg_0 - 0x1))) | LOAD32(0xdead000a + (0x8 * (arg_0 - 0x1))) - LOAD32(0x40 + 0xdead000a + (0x8 * (arg_0 - 0x1)))

0x194

--------------------------------------------------

0x195

arg_0 = stack[top]
arg_1 = stack[top-1]

0x1aa 	: arg_0 == 0x0 ? 0x1ab : 0x135
0x1ab 	: arg_0 == arg_1 ? 0x1dd : 0x1b6
0x1b6 	: WRITE("Wrong!!\n") 
0x1dc 	: JMP 0x204

--------------------------------------------------

0x1dd 	: WRITE("Correct\n")
0x1fe 	: PUSH  0x204
0x203 	: JMP

--------------------------------------------------

0x204 	: PUSH  0x0
0x209 	: EXIT

--------------------------------------------------

0x20a 	: STORE32[0xdead0000] = 0x6d35bcd
0x215 	: RET

--------------------------------------------------

0x216
arg_1 = ~arg_1 ^ (0x77f * LOAD32(0xdead0000) - 0x32a % 0x305eb3ea)

0x245 	: STORE32(0xdead0000, (0x77f * LOAD32(0xdead0000) - 0x32a % 0x305eb3ea))
0x255 	: RET

arg_1 = stack[top-1] = ~arg_1 ^ (0x77f * LOAD32(0xdead0000) - 0x32a  % (0x305eb3ea))

0x245 	: STORE32(0xdead0000, 0x77f * LOAD32(0xdead0000) - 0x32a  % (0x305eb3ea))
0x255 	: RET

--------------------------------------------------

0x256 	: STORE32 0xdead004a 0x46761223
0x26b 	: STORE32 0xdead004e 0x54bea5c5
0x276 	: STORE32 0xdead0052 0x7a22e8f6
0x281 	: STORE32 0xdead0056 0x5db493c9
0x28c 	: STORE32 0xdead005a 0x55d175e
0x297 	: STORE32 0xdead005e 0x22fcd33
0x2a2 	: STORE32 0xdead0062 0x42c46be6
0x2ad 	: STORE32 0xdead0066 0x6d10a0e8
0x2b8 	: STORE32 0xdead006a 0x53f4c278
0x2c3 	: STORE32 0xdead006e 0x7279ec2a
0x2ce 	: STORE32 0xdead0072 0x5491fb39
0x2d9 	: STORE32 0xdead0076 0x49ac421f
0x2e4 	: STORE32 0xdead007a 0x49ab3a37
0x2ef 	: STORE32 0xdead007e 0x47855812
0x2fa 	: STORE32 0xdead0082 0x5718bb05
0x305 	: STORE32 0xdead0086 0x540fb5b
0x306 	: RET

それをpythonに変換します。

memory = {}

def store32(addr:int , value: int):
    memory[addr] = value

def load32(addr:int):
    return memory[addr]


def call216(arg_0):
    temp = (((0x77f * load32(0xdead0000) & 0xFFFFFFFF) - 0x32a) %  0x305eb3ea)
    res = 0xFFFFFFFF ^ (arg_0 ^ temp)
    store32(0xdead0000, temp)
    return res


# READ(0xdead000a, 0x40)

store32(0xdead0000, 0x6d35bcd)
store32(0xdead0004, 0x47414c46)
store32(0xdead0008, 0x203a)

store32(0xdead004a,0x46761223)
store32(0xdead004e,0x54bea5c5)
store32(0xdead0052,0x7a22e8f6)
store32(0xdead0056,0x5db493c9)
store32(0xdead005a,0x55d175e)
store32(0xdead005e,0x22fcd33)
store32(0xdead0062,0x42c46be6)
store32(0xdead0066,0x6d10a0e8)
store32(0xdead006a,0x53f4c278)
store32(0xdead006e,0x7279ec2a)
store32(0xdead0072,0x5491fb39)
store32(0xdead0076,0x49ac421f)
store32(0xdead007a,0x49ab3a37)
store32(0xdead007e,0x47855812)
store32(0xdead0082,0x5718bb05)
store32(0xdead0086,0x540fb5b)

cnt = 0x8

while cnt != 0:

        arg_4 = 0xdead000a + 0x8 * (0x8 - cnt)
        arg_3 = 0xdead000e + 0x8 * (0x8 - cnt)
        arg_2 = 0x41414141
        arg_1 = 0x41414141
        arg_0 = 0x3

        while arg_0 != 0:
            arg_0 -= 1
            temp_1 = arg_1
            temp_2 = arg_2
            arg_1 = temp_2 ^ call216(temp_1)
            arg_2 = temp_1

        print("arg_1: ", hex(arg_1))
        print("arg_2: ", hex(arg_2))
        
        store32(arg_4, arg_1)
        store32(arg_3, arg_2)
        cnt -= 1

arg_0 = 8
arg_1 = 0

while arg_0 != 0:
    temp = (0x8 * (arg_0 - 0x1))
    arg_1 ^= (load32(0xdead000e + temp) - load32(0xdead004e + temp)) ^ (load32(0xdead000a + temp) - load32(0xdead004a + temp))
    arg_1 = arg_1 | load32(0xdead004e + temp) - load32(0xdead004e + temp) | load32(0xdead000a + temp) - load32(0xdead004a + temp)
    arg_0 - 1
    arg_0 -= 1

if arg_0 == arg_1:
    print("correct!")

逆の処理をすると解けるようになります。

from Crypto.Util.number import long_to_bytes

memory = {}

def store32(addr:int , value: int):
    memory[addr] = value

def load32(addr:int):
    return memory[addr]

def call216(arg_0, val):
    temp = (((0x77f * val & 0xFFFFFFFF) - 0x32a) %  0x305eb3ea)
    res = 0xFFFFFFFF ^ (arg_0 ^ temp)
    return res

memo = [114514893,710746761,795375097,799907443,96032015,650758303,18615567,552021085,331968059,580031793,684480293,306604937,201756987,624600603,312680763,599390813,228650065,692809733,733956733,762612785,730514535,75027739,621283943,103406385,56843579,85619271,283110181,499531613,11944719,635565661,117193831,745148677,765116841,429317893,276231081,183440601,72597483,252589975,437772823,132885377,792454379,301529707,675350829,778545515,429139523,745451861,298010881,652229461,169826093,527673217,41536813,776706389,145907969,13004651,235036739,63935251,809635951,773656873,449282927,745938473,420306499,163235179,764611139,270388565,233528665,653395731,784872603,497432317,278362991,791121405,415494277,330028563,341593455,248271913,741346437,198124007,619820955,779386899,183326553,665252181,202134807,538124373,245494317,517619819,363473665,98234753,582845229,165471061,760301401,589935935,76121177,47649789,434118255,86678357,692470595,83150911,652807447,467468417,472642605,763058729,774768261,721607633,162551985,265074663,249110939,491008465,24380081,589650429,339747973,190246441,10699309,106052737,28712961,314512557,631149013,231580911,399110291,576956121,126149077,750396567,385454293,140899735,41054253,662186559,474602351,228844007,253471621,269222631,]

store32(0xdead0000, 0x6d35bcd)
store32(0xdead0004, 0x47414c46)
store32(0xdead0008, 0x203a)

store32(0xdead004a,0x46761223)
store32(0xdead004e,0x54bea5c5)
store32(0xdead0052,0x7a22e8f6)
store32(0xdead0056,0x5db493c9)
store32(0xdead005a,0x55d175e)
store32(0xdead005e,0x22fcd33)
store32(0xdead0062,0x42c46be6)
store32(0xdead0066,0x6d10a0e8)
store32(0xdead006a,0x53f4c278)
store32(0xdead006e,0x7279ec2a)
store32(0xdead0072,0x5491fb39)
store32(0xdead0076,0x49ac421f)
store32(0xdead007a,0x49ab3a37)
store32(0xdead007e,0x47855812)
store32(0xdead0082,0x5718bb05)
store32(0xdead0086,0x540fb5b)

res = b""

for j in range(8):
    arg_1 = load32(0xdead004a + j*8)
    arg_2 = load32(0xdead004e + j*8)

    for i in range(3):
        temp_1 = arg_1
        temp_2 = arg_2
        arg_1 = temp_2 ^ call216(temp_1, memo[2-i + 3*j])
        arg_2 = temp_1

    print(long_to_bytes(arg_1))
    print(long_to_bytes(arg_2))
    res = long_to_bytes(arg_1) + res
    res = long_to_bytes(arg_2) + res

print(bytes(list(reversed(list(res)))))

特に何も工夫せずに解いてしまいましたが、よくよく考えれば適当な出力結果を見ながらz3かければもしかしたら解けたかも知れません。

urara

動画リンク: https://youtu.be/VUea1wDQe_A?t=3459

Category: web (+ misc)
Value: 240
Solved: 14

これ240点ってまじ…?

暗号の問題の基本は未知数を減らすことです。

この問題、pとqが 2^{1024} に設定されているので、 n = 2^{2048} になります。 (この設定が後に非想定解放を連想を招くとは誰も想像できなかったのだ…)

この問題は楕円曲線暗号の特性を利用します。
頑張って式変形をすると、楕円曲線暗号の二倍の公式と与えられた b より

P_x^4 - 4 Q_x P_x^3 - 2 a P_x^2 + (-8b - 4 a Q_x) P_x + (a^2 - 4 Q_x b ) \equiv 0 \mod n

このような式を求めることができます。 ここで P_x はフラグです。 それ以外は既知です。

x \in \mathbb{R}であれば求めることはできますが、残念ながら x \in \in \mathbb{Z} なのでまだ解けません。

そこで使うのがRSA暗号の式で、

(x+t)^{65537} - c \equiv 0 \mod n

を使います。

1つ目の式から

x^4 = ...

のような形に変形できるので、x^4以上の次数はx^3に以下に落とすことができます。
つまり、RSA暗号の式はx^3以下に落とせるのですが、x^4を置き換えていくのはめんどくさいので、多項式の剰余を求めることで動画では計算しています。

n2^{2048}であることと、x^3の次数のcoppersmith's attackはそこそこの平文解析できそうだったのでやったら解けました。

ちなみに2つ式がある場合は、さらにx^3の式を使ってx^2を求めて...と繰り返すとxまで行けるのでこの手法で解けなくても問題なかったです。

最近格子をときすぎてcoppersmith's attackに考察がよってしまいましたが、2つ=0となる式がある場合、ベズーの等式からの拡張ユークリッドの互助法で求めることができることをこの文章をかきながら思いつきました。その手法はこちらで紹介しています (15:24からです)

ここまで来ると後は簡単。 x^3 で今回は足りているので、こんな数行のコードで完結してしまいます。(式変形はしんどいので見た目以上に裏では作業してますけどね!)
ちなみにsageでsmall_roots()を使用する場合はモニックな多項式(つまり最高次数の係数が1である多項式)でなければならないことに注意してください。

A = Q[0]

K = Zmod(n)
PR.<x> = PolynomialRing(K)
f = x^4 - 4*A* x^3 - 2*a * x^2 - (8*b+4*a*A)*x + (a * a - 4 * A * b)
g = ((x + t)^65537 - c) % f
h = x^3 + g[2] / g[3] * x^2 + g[1] / g[3] * x + g[0] / g[3]
print(h.small_roots())

反省と所感(ポエムの章)

正直実力以上のパフォーマンスを出せたと思います。競技中に成長できました。
非想定解法とはいえ、coppersmith's attackをRSAのmやpの下位bitが漏洩しているものとは別の解法を思いつけなかったと思います。というわけで、全問題好きなんですが一番成長を実感できた urara が一番好きな問題でした。

sharsable は 多分あと1週間コンテストがあっても解けない問題だと思います。Wiener's attackに見える問題の中、解けた方はlatticeを使用してしっかり解けていたのですごいです。僕も格子力を上げて応用力をつけたいですね。要復習問題です。

近年典型暗号問が増えている中、どれも素晴らしい問題でした。(とはいえ典型で解ける問題も減ってきており初心者バイバイ感も否めなくはない… でもThis is RSA解かれすぎじゃない!? ちょっと非自明です!)

来年のSECCON CTFも出れたら良いな、、、 正直一人で出るにはカロリーが高すぎたので来年は知り合いの援軍を呼んで僕はCryptoに専念したいですね。

動画もたくさんの方に見ていただいてありがとうございました!
解を追うごとに徐々にグローバルになりつつあり、英語の解説もしないといけない日がくるのかなとビクビクしてます Googleさん自動翻訳技術をもっといい感じによろしくおねがいします。

それではここまでみてくださってありがとうございます!
また会える日を楽しみにしているぞ。ばいば〜い

Discussion