33C3CTF WriteUp try [150] web

ctf-web

ページを開くとHaskellのコードが書かれたテキストボックスとRunボタンが出てきます。
とりあえずRunボタンを押してみることにします。
f:id:megumish:20170103211050p:plain
Log in firstと言われたので適当な名前でログインしてみることにします。
ログインした後に再度試してみると今度はコードを実行することができました。
ソースコードを見ると

<form action="/run" method="post" accept-charset="utf-8">

    <input id="run_file" name="run_file" value="fib.hs" type="hidden"/>
    <input type="submit" value="Run!"/>
</form>

となっておりfib.hsの部分を変えれば任意のプログラムを実行できそうです。
ただし、fib.hsは/static/fib.hsにあるようなので何らかの方法で/static下にファイルを置く必要がありそうです。
ログイン後はさらに上部のメニューにUplodeとProfileが増えています。
UplodeからHaskellのコードがアップロードできるのであればとてつもなく簡単ですが、残念ながら使えないようです。

次にProfileを確認してみると、プロフィール画像としてGIF画像がアップロードできるようです。
試しにGIF画像をアップロードすると、/static/33c3_(UUID)/pic.gifにGIF画像が配置されるようです。
ここで/static下のファイルはURLを書きかえることで実行できることを思い出します。
試しに先ほどのソースのvalueの値をfib.hsから/33c3_(UUID)/pic.gifに変えてみると
GIF画像がコードとして認識されて実行されることがわかります。もちろん、実際はコードではなくGIF画像のバイナリであるためエラーが出ます。
ここまでのことから、偽装したHaskellのコードをGIF画像としてアップロードし、それを実行させることでフラッグを得ることができるのだろうと推測しました。

そこで問題になるのは、どういう形式のファイルをサーバー側がGIF画像として認識するかということです。
GIF画像の構造*1を調べると、GIF画像バイナリの特定のアドレスには固定値があることが分かるのでそこをしらみつぶしに消してはアップロードを繰り返し試してみました。
その結果、バイナリの最初の"GIF89a"と番地0x15の0x2Cの二つの固定値*2以外を変えてアップロードしてもGIF画像として判定されることがわかりました。

次に問題となるのは、この偽装GIFバイナリにHaskellのコードを埋めることです。
最初に考えたのはGIF89aという文字を関数として認識させることで、Haskellのコードの一部として使うというものでしたが、Haskellでは関数や変数の最初を大文字でおくことはできないのですぐに断念することになりました。
少しHaskellについて調べてみるとどうやら型や型クラスは最初の文字を大文字でおくことができるようでした。
しかし自分はHaskellのことをよく知らないので、slackに投げて聞いてみるとGIF89aを型（もしくは型クラス？）として後置宣言したコード*3をくれたのでそれをバイナリに埋め込みアップロードしたところ見事フラッグを手に入れることができました。

GIF89a i = GIF89a "aaaaaa"
newtype GIF89a = GIF89a String
main = putStrLn "Hello, World!"

slackでもらったHaskellのコード
f:id:megumish:20170103210811p:plain
GIF画像にHaskellのコードを埋め込んだバイナリ

以下フラッグ

33C3_n3xt_T1me_idri5_m4ybe

*1:GIFフォーマットの詳細

*2:これ以外に最後の番地に0x3Bを配置することも条件の一つかと考えていたが、間違えて最後の0x3Bを消してアップロードした際に必要な条件ではないことが分かった。

*3:ちなみにリテレートコメント形式はアップロードした後の拡張子が強制的にgifになってしまうため使うことはできませんでした。

JAG夏合宿2016参加記

JAG夏合宿に参加してきました。

 

0日目

0日目はコンテストが無かったのでのんびり過ごしました。

自己紹介は緊張しすぎて、他の人の顔とか覚えてませんでした。

そのあと懇親会まで時間があったので、@AlbicillaTさんと@dohatsutsuさんと部屋が同じだった人と人狼をやろうとしたのですが、人が足りなくて出来なかったので怒髪さんのトランプで大富豪やゴキブリポーカーをやりました。

懇親会では寿司とパスタなどを食べました。パスタをもっと食べたかったのですが、気づいたらなくなっていたのであきらめました。

@mayoko_さんや@yurahunaさん、@tubo28さん、@osrehunさんなどプロ各位と話せたのでよかったです。ちなみに今名前を挙げた人たちの大半は合宿終了後に築地市場に行き刺身と化します。

 

1日目

1日目から@AlbicillaTさんと@startcppさんとチームを組んでコンテストに臨みました。僕がやるだけ問題を一問解いて、他の二人が考察して協力して二問、問題を解いていました。

（もちろん自分も問題の概要を伝えるなどはしました。）

 

2日目

2日目も自分がやるだけ問題を一問解いて、あとの二人が考察など協力して二問、問題を解いていました。とくにD問題は@AlbicillaTさんの考察がさえていてグッジョブでした。

C問題が単純に実装が面倒くさそうなだけに見えたので、マラソンマッチで鍛えた実装力で何とかしようと思ったのですが、REとTLEとWAの3コンボであえなく撃沈しました。

 

3日目

3日目はC問題がやるだけ問題に見えたのでやろうとしたのですが、うまくいかなかったので@startcppさんに投げてしまいました。すみません。

そのあとは他の問題の概要を@startcppさんに伝えて解いてもらいました。というか前二日もほとんど@startcppさんが解いてくれました。申し訳ない。

あと@startcppさんが解いてくれている間、H問題のコードをずっと書いていたのですが、最後完成したと思ったら、せぐふぉに見舞われて見事に死にました。

 

以上です。

運営さん、チーム組んでくれた方、話してくれた方、ルームが一緒だった方、オリセンから六本木に向かう途中に僕が突然クソなぞなぞに答えたのに快く受け入れてくれた方などありがとうございました。

 

おまけ

刺身と化したプロたち。

 

C言語でBMP画像を作ろう！

大学C言語の授業の定期試験で作成したレポート

ソースコード

Generate bmp image with C. · GitHub

１．目的

C言語を使ってファイルをバイナリストリームで開いてbmpファイルを作成しよう。

f:id:megumish:20160530002517p:plain

図１．この画像を生成する。

２．原理

２．１C言語でバイナリファイルを生成

C言語のstdio.hライブラリにはファイルを開く関数があるがそれを使うことで直接機械が読み取れるバイナリデータを書き込むことができる。

これを使うことで一からファイルを生成しよう。

２．２bmpとは？

bmpとは「bitmapimage」の略であり、imageという名前がついている通り画像ファイルだ。一般に使われているpngやjpegといった形式はバイナリデータが圧縮されているためC言語で扱うにはほかにライブラリが必要である。bmpファイルは圧縮しなくても画像ファイルとして作成することができ、バイナリデータを直接いじるのに複雑な操作が（pngなどと比べて）必要でなく容易である。そのため今回はbmpを使う。

 

３．ソースコード

1

//中京と書いてあるbmp画像を生成するプログラムです。

2

  

3

#include<stdio.h>

4

#include"bmpsetting.h"

5

  

 

#include”bmpsetting.h” は今のディレクトリからヘッダーファイル「bmpsetting.h」

を探してインクルードするマクロ。

Bmpsetting.hはbmpファイルのヘッダー情報を設定するための構造体と構造体を初期化するための関数が入っている。

 

7

int main(void){

8

  

9

        FILE *BMPfp;

10

        errno_t error;

11

        if (error = fopen_s(&BMPfp, "test.bmp", "wb") != 0)

12

                return error;

 

今回のプログラムはVisualStudio2013を使って作成した。VisualStudi2013ではセキュリティの意識が高く、fopenなどの関数が使えない。その代わりにfopen_sなどの関数を使われるように促される。

fopen_sはfopen関数と違い、FILE構造体を戻り値として返す形で開くファイルを設定せずにFILE構造体のインスタンスのアドレスを書きかえてファイルを開く。

fopen_sは戻り値としてerrno_t型の変数を返す。この変数の数値によってerrorが起こったかだけでなくerrorの種類がわかる。

bmpファイルに情報を書き込むためにはファイルにテキストではなくバイナリを書き込まなくてはならない。そのためfopen_s関数の第三引数において”w”ではなく”wb”のように”b”を加えることでファイルをテキストストリームではなくバイナリストリームで開いている。

 

13

        int sfsdaf[10][18] =

14

        { { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1 },

15

          { 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1 },

16

          { 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },

17

          { 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1 },

18

          { 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1 },

19

          { 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1 },

20

          { 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1 },

21

          { 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1 },

22

          { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1 },

23

          { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1 } };

 

配列を宣言する際に(変数名)のように記述すると配列の配列が作成できる。これらの数値をつかってbmp画像に入力するデータを決める。

 

24

        BMPFileHeader bmpFH = InitializeFileHeader();

25

        BMPInfoHeader bmpIH = InitializeInfoHeader();

26

        ColorPalette  colP[2] = {

27

                { 0x00, 0x00, 0x00, 0x00 }, //Black

28

                { 0xFF, 0xFF, 0xFF, 0x00 }  //White

29

        };

30

  

31

        bmpIH.ImgHeight =  0x0A;

32

        bmpIH.ImgWidth  =  0x12;

33

        unsigned int ByteperImgLine = ((0x12 / 8) + 1) + 1;

34

        bmpIH.ImgDateSize = 0x0A * ByteperImgLine;

35

        bmpFH.FileSize = bmpFH.DateOffSet + bmpIH.ImgDateSize;

36

  

37

  

38

        fwrite((char*)&bmpFH + 2, sizeof(BMPFileHeader)-2, 1, BMPfp);

39

        fwrite(&bmpIH, sizeof(BMPInfoHeader), 1, BMPfp);

40

        fwrite(colP, sizeof(ColorPalette), 2, BMPfp);

41

  

 

bmpファイルには画像そのもののデータだけでなく、ヘッダデータが存在している。ここではそのヘッダデータを記述している。

ヘッダデータには二種類のヘッダがある。ひとつはファイルヘッダというものでどのような形式のbmp画像にもこれが存在する。もうひとつは情報ヘッダで、このヘッダはCORE型やINFO型などの型があり、INFO型が一般的であるらしい。今回はINFO型を使用した。これらの詳しい構成は付属のExcelファイルに記述した。

 

 

 

 

42

        unsigned int num;

43

        char zero = 0;

44

        for (int row = 0; row < 10; row++){

45

                num = 0;

46

                for (int column = 0; column < 18; column++){

47

                        num = num * 2 + sfsdaf[9 - row][column];

48

                }

49

                fwrite(&num, sizeof(int), 1, BMPfp);

50

        }

51

       

52

        fclose(BMPfp);

53

        return 0;

54

  

55

}

 

BMPfpに用意したデータを書き込む。

fwrite関数はこのソースの記述で言うと、アドレス&numを初期位置としてsizeof(int)バイト分のデータを1個取り出してBMPfpに書き込むという処理をしている。

このソースコードではsfsdafを一番目の配列からではなく最後の配列から入力している。なぜこうするかというとbmpファイルは最初のイメージデータが左下から始まり右方向に進み、改行すると今度は上方向に進むので下から順番に積み上げるようにデータを入力しないといけないためだ

 

 

 

 

 

 

 

 

 

 

 

４．結果

図１のような画像を生成するつもりだったが、実際にプログラムを組んだところ画像が反転しさらに謎の黒棒がついた画像が出来上がった。

f:id:megumish:20160530002537p:plain

図２．反転してしまった画像

 

 

５．考察

図３．出来上がった画像のバイナリデータ

バイナリデータに数値を書き込む前のint型の数値は「0x3FF6D」だった。しかしこのバイナリファイルで対応する数値（図3で赤丸で囲った部分）では「0x6DFF03」になっている。

この問題をGoogle検索で調べたところ、どうやらCPUの処理による問題らしい。

バイナリデータに書き込まれたデータはリトルエンディアンという配置方法でデータが配置されたらしい。リトルエンディアンは数倍とあるデータを転送する際に一バイトずつ上位バイトを下位バイトに埋めていく方式であるらしい。

これを解決するためには上位バイトは上位バイトにそのまま配置するビッグエンディアンという配置方法を使う、もしくは1バイトずつデータを配置していけばいいらしい。

 

６．参考文献・参考サイト

６．１bmpのバイナリ構造について

プログラミング/BMPファイル仕様/バイナリ構造 - ルーチェ's Homepage：

URL http://www.ruche-home.net/program/bmp/struct#image-data

６．２fopen_s関数やfwrite関数について

MSDN: URL http://msdn.microsoft.com/ja-jp/library/z5hh6ee9.aspx

C言語標準ライブラリ関数ポケットリファレンス：葛西 朝雄、技術評論社、2009

６．３エンディアンについて

バイトオーダ - ビッグエンディアン/リトルエディアン：URL http://www.ertl.jp/~takayuki/readings/info/no05.html

 

TCO16 Marathon Match Round1 に参加しました。

今日の2時にTCOMM16Round1が終わったということで、自分の戦略をここにまとめておきます。

最終的な戦略

まず貪欲で初期解を作り、それをもとに遺伝的アルゴリズムでランダムで線を入れ替えて（なぜ削除ではなく入れ替えるなのかというとそれは、NP-1本必ず線を引かなければいけないと勘違いしていたからです。）得点を上げていく手法を使いました。

貪欲にも遺伝的アルゴリズムにもそれを評価するためのスコアが必要ですが、それには(分割できた植物のある領域の数）＋（残った根の長さ）/（全体の根の長さ）という評価式を用いました。

（分割できた植物のある領域の数）は一本ずつ線を引くと考えて、それから線の上にあるか下にあるかで二分割するのを繰り返して分けました。

根の長さについては深さ優先探索を使い求めました。まずvector<int>rootsから木を構成します。（全体の根の長さ）を求めるにはこの次に、深さ優先探索を使って葉のスコアは0として、親は子のスコアと親と子の間の距離をそのスコアとするというのをすべての植物に対して行います。そしてすべての植物のスコアを足すと全体の長さがわかります。

（残った根の長さ）は深さ優先探索を使って各線について子と親の間に線が通っていたときに、元の子の座標を交点の座標に書きかえて子の子はすべて消すというのを繰り返します。そうすると、根の状態は切り取られた後の状態になるのでさっき全体の根の長さを求めた方法と同じことをやると残った根の長さがわかります。

この評価方法をそのまま使うと、深さ優先探索の再帰のコストが大きくなってしまうため、NPが多いときには探索する深さを制限して使うようにしていました。NPが多いときに使う理由は、NPが多いときには深さを制限してもある程度本当の得点に相関性のあるスコアが得られるからです。またNPが多いときはとくに再帰のコストが多くかかるからです。

その他に考えた戦略

評価式はそのままで山登り法を使った方法

正直これでもある程度うまくいったのですが、途中で遺伝的アルゴリズムを使ってみたくなり使うのをやめました。

評価式はそのままで焼きなまし法と遺伝的アルゴリズムを使った方法

遺伝的アルゴリズムの本に焼きなましと遺伝的アルゴリズムを合わせたハイブリッド手法には様々な利点があると書いてあったため使いました。しかし本をまともに読まず我流で書いたためか確かな効果は得られませんでした。この手法はコンテスト終了直前に書いていたのでパラメーターの調整が間に合わず提出できませんでした。

評価式に円の半径を使って貪欲法を使った方法

植物の根を植物の中心点から四象限に分けて、根の長さから四つの円を書いてそれがどれぐらい削られたかで判定する方法を使いました。これは得点との相関性がないことから最終的には使いませんでした。

反省

序盤にも書いた通りルールを勘違いしていたとというのが本当に悲しいです。次からは問題文をちゃんと読んでおきたいですね。

Exampleの結果だけ見ていて他のテストケースでのTLEを気にしていなかったのも終了後に気づいた反省点です。あと次は時間内にビジュアライザ作りたいと思いました。