InterKosenCTF2020 Writeup
2020/9/5(土)10:00~9/6(日)22:00 JSTに開催された InterKosenCTF2020に参加しました。
traP内でメンバーを公募したチームChitandaEruで参加し、2059点で正の点数を取った133チーム中23位でした。
userの順位は、1938点で正の点数を取った188人中21位でした。
web,rev,pwnに全く手が出ず、なのは今まで通りでしたが(何とかしたい)、今回はCryptoの問題を結構解くことができ、最近のCrypto精進の成果を発揮できたかなあという感じです。間違いなく成長できてる感じがあり嬉しい。
discordのctf-logチャンネルで各問題の早解き上位3人にスタンプがつけられており、なんと3つスタンプをもらうことができました。No pressureはFirst Bloodでした。結構うれしい。
運営の皆様、お疲れさまでした。
良問揃いでとても勉強になりました。ありがとうございました。
welcome [welcome] (100pts,126solves)
言われたとおりにDiscord鯖に参加します。
announcementチャンネルにflagがありました。
KosenCTF{w31c0m3_and_13ts_3nj0y_the_party!!} です。
survey [survey] (110pts, 48solves)
googleformのアンケートに回答すると手に入ります。
KosenCTF{w4s_th1s_ch4ll3ng3_h4rd_4_u?}
limited [web,forensics] (157pts,40solves)
pcapファイルが渡されます。中身を覗いてみると、
http://moxxie.tk:8080/search.php?keyword=&search_max=%28SELECT+unicode%28substr%28secret%2C+26%2C+1%29%29+FROM+account+WHERE+name%3D%22admin%22%29+%25+11
のようなリクエストが投げられたサーバーがhtmlを返しています。Blind SQL Injectionですね。
ただし今回の場合はクエリのsearch_maxの部分に[flagのi文字目の文字コード]%11のように剰余を指定することを各文字に対し2~4回ほど繰り返しています。攻撃者は帰ってくるhtmlにおいて検索結果が何件含まれているかを確認することで、flagのi番目の文字コードをある素数で割った余りを知ることができるわけです。
つまり今回のpcapファイルからはflagの各文字について、割る数をRequest URIから、割った余りをサーバーが返すhtmlから知ることができます。この情報をすべてかき集めて中国剰余定理によりflagの各文字を復元すれば勝ちです。
私はwiresharkでhttpのパケットを選択してから[エキスパートパケット解析]->[プレインテキストとして]でやりとりをplaintextにして、以下のコードでflagを復元しました。
with open("aaa.txt", "r") as inp2:
a = inp2.read()
rows = []
a = a.split("No.")
for i in a:
if "tbody" in i:
ii = i.split("<tbody>")[1].split("</tbody>")[0]
row_num = len(ii.split('<th scope="row">'))-1
ii = i.split("[Request URI: ")[1].split("]")[0]
if "substr" in ii:
ii = str(ii.split("SELECT"))
ii = ii.split("secret%2C+")[1]
num = int(ii.split("%")[0])
i = i.split("admin%22%29+%25+")[1].split(" ")[0][:-2]
mod = int(i)
rows.append((num, mod, row_num))
def ex_euclid(a,b):
# ax + by = gcd(a,b) なる (x,y)を求める
#
x1, y1 = 1, 0 # (init) a1 + b0 = a
x2, y2 = 0, 1 # (init) a0 + b1 = b
while b != 0:
q = a // b
a, b = b, a%b
x1, y1, x2, y2 = x2, y2, x1-q*x2, y1-q*y2
return (x1, y1, a) # a*x1 + b*y1 = gcd(a,b)
def CRT(alist, mlist):
# mで割った余りがa
m = mlist[0]
x = alist[0]
for mm,aa in zip(mlist[1:], alist[1:]):
u,v,_ = ex_euclid(m, mm)
x = aa*m*u + x*mm*v
m *= mm
x %= m
return x,m
flag = ""
bnum=0
mods = [1]
rems = [1]
for num,mod,remind in rows:
if num != bnum:
flag += chr(CRT(rems, mods)[0])
mods = []
rems = []
bnum = num
mods.append(mod)
rems.append(remind)
print(flag)
KosenCTF{u_c4n_us3_CRT_f0r_LIMIT_1nj3ct10n_p01nt} です。
No pressure [misc,warmup] (335pts,16solves)
問題のプログラムは以下の通りです。
from Crypto.Cipher import ARC4
from hashlib import sha256
from base64 import b64encode
import zlib
import os
flag = open("./flag.txt", "rb").read()
nonce = os.urandom(32)
while True:
m = input("message: ")
arc4 = ARC4.new(sha256(nonce + m.encode()).digest())
c = arc4.encrypt(zlib.compress(flag + m.encode()))
print("encrypted! :", b64encode(c).decode())
人生初のFirst Bloodを勝ち取ることができました。めっちゃうれしいです。
実は4日ほど前にCRYPTOHACKで精進をしていた際にほぼ同じ問題を解いておりました。
(用いている暗号化アルゴリズムがarc4かAES-CTRかの違いだけでした...)
用いる脆弱性はCRIMEです。zlib.compress(flag + m.encode())の特徴的な振る舞いとして、mがflagの部分文字列のときはそうでないときに比べて出力長が短くなるというものがあります。これを利用して、"KosenCTF{"の後ろに一文字ずつつけてサーバーに投げたときに、正しくflagの部分列になるようなリクエストときだけ出力結果が他よりも短くなっていることから一文字ずつflagの各文字を確定させることができます。
from pwn import * # pip install pwntools
from Crypto.Util.number import *
r = remote('misc.kosenctf.com', 10002, level = 'debug')
def json_recv():
line = r.recvline()
return json.loads(line.decode())
def json_send(hsh):
request = json.dumps(hsh).encode()
r.sendline(request)
a = "KosenCTF{"
for _ in range(100):
#lens = []
request = a + chr(0x11)
r.sendline(request)
x = r.recvline()
baselen = len(x)
for i in range(0x11, 0x80):
request = a + chr(i)
r.sendline(request)
x = r.recvline()
if baselen > len(x):
a += chr(i)
break
print(a)
KosenCTF{DEFLATE_is_an_algorithm_that_combines_LZ77_and_Huffman_coding} です。
ciphertexts [crypto,warmup] (201pts,33solves)
$ n1=pq, n2=pqr $ ($p,q,r$は512bitの素数)
$c1\equiv m^{e1} (\mod n1), c2\equiv m^{e2} (\mod n2)$
となっており、$n1, n2, e1, e2, c1, c2$が与えられていて、$m$を求める問題です。
$c2 = m^{e2} + kpqr (k\in\mathbb{Z})$なので、c2 % n1 == m^{e2} % n1 となります。
これがわかれば、c22 = c2 % n1 として、
$c1\equiv m^{e1} (\mod n1), c22\equiv m^{e2} (\mod n1)$
となりますから、拡張ユークリッド互除法で$m$を求めることができます。
n1 = 112027309284322736696115076630869358886830492611271994068413296220031576824816689091198353617581184917157891542298780983841631012944437383240190256425846911754031739579394796766027697768621362079507428010157604918397365947923851153697186775709920404789709337797321337456802732146832010787682176518192133746223
n2 = 1473529742325407185540416487537612465189869383161838138383863033575293817135218553055973325857269118219041602971813973919025686562460789946104526983373925508272707933534592189732683735440805478222783605568274241084963090744480360993656587771778757461612919160894779254758334452854066521288673310419198851991819627662981573667076225459404009857983025927477176966111790347594575351184875653395185719233949213450894170078845932168528522589013379762955294754168074749
e1 = 745699
e2 = 745709
c1 = 23144512980313393199971544624329972186721085732480740903664101556117858633662296801717263237129746648060819811930636439097159566583505473503864453388951643914137969553861677535238877960113785606971825385842502989341317320369632728661117044930921328060672528860828028757389655254527181940980759142590884230818
c2 = 546013011162734662559915184213713993843903501723233626580722400821009012692777901667117697074744918447814864397339744069644165515483680946835825703647523401795417620543127115324648561766122111899196061720746026651004752859257192521244112089034703744265008136670806656381726132870556901919053331051306216646512080226785745719900361548565919274291246327457874683359783654084480603820243148644175296922326518199664119806889995281514238365234514624096689374009704546
from Crypto.Util.number import inverse, bytes_to_long, long_to_bytes
import fractions
from math import gcd
def ex_euclid(a,b):
# ax + by = gcd(a,b) なる (x,y)を求める
#
x1, y1 = 1, 0 # (init) a1 + b0 = a
x2, y2 = 0, 1 # (init) a0 + b1 = b
while b != 0:
q = a // b
a, b = b, a%b
x1, y1, x2, y2 = x2, y2, x1-q*x2, y1-q*y2
return (x1, y1, a) # a*x1 + b*y1 = gcd(a,b)
def CRT(alist, mlist):
# mで割った余りがa
m = mlist[0]
x = alist[0]
for mm,aa in zip(mlist[1:], alist[1:]):
u,v,a = ex_euclid(m, mm)
assert(a==1)
x = aa*m*u + x*mm*v
m *= mm
x %= m
return x,m
r = n2//n1
assert(r*n1==n2)
c22 = c2 % n1
x,y,g = ex_euclid(e1, e2)
a = ((pow(inverse(c1, n1), -x, n1) * pow(c22, y, n1))%n1)
print(long_to_bytes(a))
KosenCTF{HALDYN_D0M3} です。
bitcrypto [crypto] (326pts,17solves)
- 秘密鍵：デカい素数$p,q$
- 公開鍵：$n=pq$と、$p,q$のどちらにおいてもlegendre symbolが-1であるような数$z$
となっており、暗号化では文字列の各bitに対して、bitが0なら$x^2 \mod n$、bitが1なら$zx^2 \mod n$ ($x$はランダムな数字)を対応させたlist[int]にしています。
また、復号では、list[int]を受け取り、list内の各intについて、その値が$p,q$のどちらを法としてもlegendre symbolが1であれば0、そうでなければ1を対応させたバイナリにします。
操作は、以下の操作A,Bをこの順に一回ずつ行います。
操作Aでは、まず8bytes以内の文字列を入力して暗号化したlist[int]を得るというものがあります。この操作で、平文のビット"0"に対応する$x^2 \mod n$の値と平文のビット"1"に対応する$zx^2 \mod n$の値を合計64個入手することができます。
操作Bでは、list[int]を入力し、復号結果が"yoshiking, give me ur flag"に一致すればflagを入手することができます。ただし、入力するlist[int]は重複が許されず、"yoshiking, give me ur flag"に対応する合計26×8個の値を用意する必要があり、操作Aで得た合計64個の値だけでは足りません。
ここで、Legendre Sybmolの$\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$という性質を利用します。つまり、
平文のビット"0"に対応する$x^2 \mod n$の値の集合を$X_0$、平文のビット"1"に対応する$zx^2 \mod n$の値の集合を$X_1$としたとき、
$g,h\in X_0\implies gh\in X_0$
$g\in X_0, h\in X_1\implies gh\in X_1$
$g,h\in X_1\implies gh\in X_0$
となります。これを使い、操作Aで得た値を適切に掛け合わせることで、平文のビット"0"および"1"に対応する数字を十分な数用意することができます。
from pwn import * # pip install pwntools
import json
import codecs
from Crypto.Util.number import getPrime, bytes_to_long, inverse, long_to_bytes
r = remote('crypto.kosenctf.com', 13003, level = 'debug')
def json_recv():
line = r.recvline()
return json.loads(line.decode())
def json_send(hsh):
request = json.dumps(hsh).encode()
r.sendline(request)
keyword = "yoshiking, give me ur flag"
print(bin(bytes_to_long(keyword.encode())))
keyworde = "UUUUUUU"
print(bin(bytes_to_long(keyworde.encode())))
r.sendline("UUUUUUU")
a = r.recvline()
a = str(a).split("[")[1].split("]")[0]
a = a.split(", ")
a = [int(aa) for aa in a]
ones = [a[i] for i in range(0, len(a), 2)]
zeros = [a[i] for i in range(1, len(a) ,2)]
ones_ex = [one*zero for one in ones for zero in zeros]
zeros_ex0 = [zeros[i]*zeros[j] for i in range(len(zeros)) for j in range(i+1, len(zeros))]
zeros_ex1 = [ones[i]*ones[j] for i in range(len(ones)) for j in range(i+1, len(ones))]
ones.extend(ones_ex)
zeros.extend(zeros_ex0)
zeros.extend(zeros_ex1)
ansbin = bin(bytes_to_long(keyword.encode()))[2:]
#print(len(ansbin))
print(sum([int(i) for i in ansbin]), len(ansbin)-sum([int(i) for i in ansbin]))
print(len(ones), len(zeros))
print(len(ones_ex), len(zeros_ex0))
resp = ""
for i in ansbin:
if i=="1":
resp += str(ones[0])
ones = ones[1:]
else:
resp += str(zeros[0])
zeros = zeros[1:]
resp += ","
r.sendline(resp[:-1])
print(r.recvline())
print(r.recvline())
print(r.recvline())
print(r.recvline())
KosenCTF{yoshiking_is_clever_and_wild_god_of_crypt} です。
padding oracle [crypto] (326pts,17solves)
AES-CBCのpadding oracle attackをします。
AES-CBCのブロック$i$について、そのブロックに対応する暗号文を$c_i$、そのひとつ前のブロックに対応する暗号文を$c_{i-1}$ ($c_{-1}$はivとします)、暗号文をブロックに通したものを$dec=\text{AESdecode}(c_i)$とします。このとき、ブロックごとの復号は$plain_i = XOR(dec, c_{i-1})$と計算されます。
ここで、padding oracle attackを用いると、$XOR(dec,iv')="0x0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f??"$となるような$iv'$(の16bytesのうち上位15bytes)を求めることができます。
この$iv'$を用いて$XOR(iv', "0x0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f??", c_{i-1})$を計算することで各ブロックの平文(の16bytesのうち上位15bytes)を求めることができます。
from pwn import * # pip install pwntools
import json
import codecs
from Crypto.Util.number import getPrime, bytes_to_long, inverse, long_to_bytes
r = remote('padding-oracle.kosenctf.com', 13004, level = 'debug')
def json_recv():
line = r.recvline()
return json.loads(line.decode())
def json_send(hsh):
request = json.dumps(hsh).encode()
r.sendline(request)
def search(iv_meta, enc, init_iv=""):
iv = init_iv
for i in range(15-len(init_iv)//2):
iv = [int(iv[i:i+2], 16)^(len(iv)//2)^(len(iv)//2+1) for i in range(0,len(iv),2)]
iv = "".join([format(j, "02x") for j in iv])
print(iv)
for j in range(256):
iv2 = iv + format(j, "02x")
iv2 = iv2 + "00"*(16-len(iv2)//2)
print(iv2)
r.sendline(iv2 + enc)
res = r.recvline()
if res[:4]==b"True":
iv += format(j, "02x")
break
#sleep(1)
print(iv)
ivs = [int(iv[i:i+2], 16)^0x0f^int(iv_meta[i:i+2], 16) for i in range(0,len(iv),2)]
#print(ivs)
return ivs
#iv = "".join([format(j, "02x") for j in iv])
# base padding = 030303
base = str(r.recvline())[2:-3]
#print(base)
base_iv = base[:32]
base_enc = base[32:]
print(base_iv)
print(base_enc)
print(len(base_iv), len(base_enc))
iv = int(base_iv, 16)
l0 = search(base_iv, base_enc[:32], base_iv[:6])
with open("out", "a") as out:
print("".join([chr(l0[i]) for i in range(3,len(l0))]), file=out)
ls = []
for i in range(1,10):
l = search(base_enc[32*(i-1):32*i], base_enc[32*i:32*(i+1)])
ls.append(l)
with open("out", "a") as out:
print(str(i)+":", file=out)
print("".join([chr(i) for i in l]), file=out)
今回の手法では各ブロックについて下位1byteを求められないので、穴埋めはguessで行いました。KosenCTF{0r4c13_5urviv3?_57i11_n0w} を穴埋めして
KosenCTF{0r4c13_5urviv35_57i11_n0w} です。
ochazuke [crypto] (383pts,11solves)
ECDSAかなんかです。
楕円曲線はそこまで理解していないので困ったなあ...と思っていたらbytes_to_long(b"ochazuke")にnを足してhexにしたもので通りました。おしまい。(非想定感がありますが、どうなんでしょう)
from pwn import * # pip install pwntools
import json
from Crypto.Util.number import getPrime, bytes_to_long, inverse, long_to_bytes
r = remote('crypto.kosenctf.com', 13005, level = 'debug')
def json_recv():
line = r.recvline()
return json.loads(line.decode())
def json_send(hsh):
request = json.dumps(hsh).encode()
r.sendline(request)
n = 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551
hoge = bytes_to_long(b"ochazuke")+n
hoge = hex(hoge)[2:]
r.sendline(hoge)
r.recvline()
rec = r.recvline()
sign = str(rec).split("signature: ")[1].split(r"\n")[0]
r.sendline(sign)
r.recvline()
KosenCTF{ahhhh_ochazuke_oisi_geho!geho!!gehun!..oisii...} です。