読者です 読者をやめる 読者になる 読者になる

三種の勉強会盛り合わせ日記(一日目)

3月の23~25日までに三つの勉強会に参加してきたので、感想をまとめて書いておきます。

Rust プログラマーミートアップ

前日譚

今回東京に行こうと思ったきっかけがこの勉強会です。

今までも何回かRustのイベントがあることは知っていたのですが、どれもRustを(あまり)知らない方向けという感じでした。

しかし、プログラマーミートアップはそれらに比べると本格的なRustLangを使った技術に触れられそうな気配を感じ取りました。

そして何よりも

こんなことをツイートする通り、Rustのことを(自分の中では)得意な言語だとは思ってるものの

本物のRustのプロ各位はどんなことをやっているのか気になってたまらなくなり、前日に急遽行くことを決めたというわけです。

感想

コンパスのサイト

最初の方の話は諸事情で30分遅れぐらいで参加しました。

英語圏の方の発表でしたが、英語があまり分からない僕は「Rustで作ったライブラリは高速だ!」ということぐらいしかわかりませんでした。

二番目の発表はiOSアプリの開発者の方でSwift使いから見たRustの利点などを話していました。

Swift にも if let 式があるのですが、 let を複数かけるらしくその機能はぜひRustにも取り入れてほしいです(今のところはタプルを使うことで同じようなことはできますが…)。

三番目の発表はTwitterGoogle検索でもよく見るRust皿が頭についた河童のアイコンのκeenさんの発表でした。

発表に使われたソースコードはRustの機能を上手くつかっていて、見ていて「なにこれ、ぼくのかいてるRustとちがう」となりました。

開発に便利なライブラリの紹介もあったのでぜひ使っていきたいです。

[κeen](http://keens.github.io/slide/Rust_in_Production/)さんのスライド

懇親会では検索エンジンの会社に勤めている方と話したり、κeenさんとこばさんの(qnighy大丈夫かみたいな)話を聞いたりしました。

もっとくわしく勉強会の内容について知りたい方は、僕に直接リプライを送ったりすれば答えられるものは答えます。

また、Twitterハッシュタグ(#rust_jp)でも参加者各位のライブツイートがあるのでそれも参考にしてください。

本日の記事は以上です。次は二日目の記事(Vuls祭り#2)を明日とかに書きます。

33C3CTF WriteUp pay2win [200] web

cheapとflagが買えるようです。
まずはcheapから買ってみることにしましょう。
f:id:megumish:20170103235550p:plain
クレジットカードナンバーはcredit card number sample などで検索して出てきたものを入力してもいいですが、
実はLuhnアルゴリズムが通る数字ならなんでもいいっぽいので0でも入力しておきます。
f:id:megumish:20170103235637p:plain
0を入力すると無事にcheapを購入することができ、cheap.txtの中身を見ることができます。
f:id:megumish:20170103235659p:plain
次にflagを購入してみましょう。
flagもcheapを買ったときと同じように、0を入力し購入できるか試します。
おっと、クレジットカードの使用限度を超えていて買えないようです。
f:id:megumish:20170103235718p:plain

おおよそflagを手に入れる方法は次の二つです。
正しいクレジットカードナンバーを入力するか、cheapの購入後画面でをcheap.txtをflag.txtを何らかの方法で書きかえることで手に入れるかです。
答えを先に行ってしまうと正しかった方は、cheap.txtをflag.txtに書きかえる方です。

以下flagを発見した手順です。
まず、cheapを購入する場面でのURLのdataの値と、flagを購入する場面でのURLのdataの値を比較します。

cheap:5e4ec20070a567e03c598eac510b4a85475daa246cb031e03b5b0554edda4f8828df361f896eb3c3706cda0474915040
flag :5e4ec20070a567e03c598eac510b4a85d1d71c0ceb6e8d6d4f75c9736d3b8e0641e7995bb92506da1ac7f8da5a628e19ae39825a916d8a2f

ここでまず、二つのdataの長さが違うことに気付きます。自分はflagのdataの末尾にあるae39825a916d8a2fという文字列をcheapのdataの後ろに引っ付けて試してみることにしました。
すると次のような画面が現れました。
f:id:megumish:20170103235750p:plain
なんとcheapがcheapgになっています。これによりae39825a916d8a2fがflagの末尾であるg部分に対応すると推測できます。*1
しかし、flagやcheapの文字ひとつひとつがハッシュ化されて末尾に固められているという確証はまだできません。
もしかしたらハッシュ値全体にちりばめられている可能性もあるからです。
次に、cheapを購入する前と購入後のdataの値について比べてみます。

cheap購入前:5e4ec20070a567e03c598eac510b4a85475daa246cb031e03b5b0554edda4f8828df361f896eb3c3706cda0474915040
cheap購入後:5765679f0870f4309b1a3c83588024d7c146a4104cf9d2c88d527869fa7bdbef28df361f896eb3c3706cda0474915040

後ろの32文字に注目すると、28df361f896eb3c3706cda0474915040という同じ文字列で構成されていることがわかります。
二つのページで共通する文字列はcheapだけであるため後ろ32文字がcheapを表しているということがおおよそ確定できます。

つまりcheap購入後の後ろ32文字と同じ位置にあるflagの後ろ48文字を交換すれば見事flagがとれるのではないでしょうか、早速試してみます。
はい、とれました。おわり。
f:id:megumish:20170103235815p:plain
フラッグ

33C3_3c81d6357a9099a7c091d6c7d71343075e7f8a46d55c593f0ade8f51ac8ae1a8

*1:まだサーバーが動いてるなら試すことができるが、ae39825a916d8a2fをさらに付け加えると、どんどんgを増やすことができる。

33C3CTF WriteUp try [150] 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

1.目的

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

f:id:megumish:20160530002517p:plain

図1.この画像を生成する。

2.原理

2.1C言語でバイナリファイルを生成

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

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

2.2bmpとは?

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

 

3.ソースコード

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ファイルは最初のイメージデータが左下から始まり右方向に進み、改行すると今度は上方向に進むので下から順番に積み上げるようにデータを入力しないといけないためだ

 

 

 

 

 

 

 

 

 

 

 

4.結果

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

f:id:megumish:20160530002537p:plain

図2.反転してしまった画像

 

 

5.考察

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

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

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

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

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

 

6.参考文献・参考サイト

6.1bmpのバイナリ構造について

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

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

6.2fopen_s関数やfwrite関数について

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

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

6.3エンディアンについて

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

 

Collins DictionaryからAnki用の発音記号を収拾しよう。メモ記事

これはOneNoteにメモしたものをそのまま貼り付けたものです。

読みやすくする予定は今のところありません。

またソースコードも公開しません。

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

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

最終的な戦略

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

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

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

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

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

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

その他に考えた戦略

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

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

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

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

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

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

反省

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

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