SECCON 2020 CTF writeup
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に近い問題ですね
この問題のポイントは ランダムな数(多項式)
適当にやったらできてしまったので証明等はしてません。
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
ここになります。復号時も同様に
ちなみに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が
この問題は楕円曲線暗号の特性を利用します。
頑張って式変形をすると、楕円曲線暗号の二倍の公式と与えられた
このような式を求めることができます。 ここで
そこで使うのがRSA暗号の式で、
を使います。
１つ目の式から
のような形に変形できるので、
つまり、RSA暗号の式は
ちなみに２つ式がある場合は、さらに
最近格子をときすぎてcoppersmith's attackに考察がよってしまいましたが、２つ
ここまで来ると後は簡単。
ちなみに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