A painter and a black cat

# CTF Writeup TMCTF2015

{{toc}}

# 結果＆感想

Trend Micro CTF Asia Pacific & Japan 2015 に、チーム sky3 で参加しました。

メンバーは c@t, リリりん♪, kanata の3名で、結果は **2705pt 26位** 。 **国内9位** でした。

自分は、Analysis-defensive 100 と Programing 200 しか解けませんでしたが、c@tさんとリリりん♪さん がやってくれました。

Trend Micro CTF Asia Pacific & Japan 2015 オンライン予選 ランキングページ

https://ctf.trendmicro.co.jp/ranking.html

いちおう、自分が解いたやつは、writeupしようと思います。

c@tさんから、Analysis-offensive 200,Miscellaneous 400,Cryptography 100,Cryptography 500,Programing 100 

リリりん♪さんから、Programming 300 Programming 500 Miscellaneous 200 writeup頂いたので、合わせて公開します!

# 演習 Crypto1-AnswerMe

■演習問題

```

Hi this is chacha. I'm 20 years old.

I have a question. Could you answer a question below?...haha. Just kidding.

6bd00ba222523f58de196fb471eea08d9fff95b5bbe6123dd3a8b9026ac0fa84

Key: 23AD52B15FA7EBDC4672D72289253D95DC9A4324FC369F593FDCC7733AD77617

nonce:5A5F6C13C1F12653

```

ChaChaっていうストリーム暗号らしい。

https://ja.wikipedia.org/wiki/Salsa20#ChaCha

    Hi this is chacha. I'm 20 years old.

って言っているから、ChaCha20だと思われ。

デコーダが無いか探してみるが、見つけられなかった。

[ココ](http://ianix.com/pub/chacha-deployment.html)らへんに、ChaCha暗号のライブラリが纏められているのを発見。

その中から、[chacha20-simple-1.0.tar.bz2](http://chacha20.insanecoding.org/chacha20-simple-1.0.tar.bz2)をダウンロード

http://chacha20.insanecoding.org/

中に入っているtest.cを、ちょっと修正。

```

$ diff test.c test.c.org

95d94

<     printf("%d %s %s\n",len,output,cipher);

156d154

<   /*

162,163d159

<   */

<   /*

168,178d163

<   */

< 

<   char key[]   = "23AD52B15FA7EBDC4672D72289253D95DC9A4324FC369F593FDCC7733AD77617";

<   char nonce[] = "5A5F6C13C1F12653";

<   char plain[] = "0000000000000000000000000000000000000000000000000000000000000000";

<   char chiper[]= "6bd00ba222523f58de196fb471eea08d9fff95b5bbe6123dd3a8b9026ac0fa84";

<   test_encipherment(key, nonce, chiper, plain, 0, 5);

```

makeして実行

```

$ make;./test 

gcc -W -Wall -O3 -I. -o test.o -c test.c

gcc -o test chacha20_simple.o test.o -s

Test Vector: Encipherment #5: Failed exact length

32 TMCTF{Whose_garden_is_internet?}&z

$

```

細かい事はわからんがフラグが出てきた。

答え

```

TMCTF{Whose_garden_is_internet?}

```

# 演習 Crypto2-air_on_g_string

■演習問題

G線上のアリアのMIDIファイルなのだが、不協和音っぽいのが混じっている。

----

いろいろ調べたけど、このソフトでとりあえず楽譜化してみる。

楽譜作成ソフト、印刷・再生も – MuseScore Portable

http://triton.casey.jp/portable/musescore-portable/

ピアノが全部で４台(？)あって、内３台に C,T,F と名前がついている。ちょっと怪しい。

![Crypto2-air_on_g_string.png](Crypto2-air_on_g_string.png)

リリりん♪さんが、以下に気づいて、教えてくれた。

>CH#1～3で本物のG線上のアリアを演奏しています。

>（CH#4でも若干本物の音が混じっていそうですが・・・）

>CH#4が不協和音、C,T,FはそれぞれCH#4の3音目、4音目、5音目を抜き出したものですね。

あぁ、そうか、フラグの形式が

```

TMCTF{??????????}

```

だろうから、つまり、

CH#4の1音目…T

CH#4の2音目…M

CH#4の3音目…C

CH#4の4音目…T

CH#4の5音目…F

CH#4の6音目…{

を表しているんじゃないかと。

```

ドレミファソラシ

ＣＤＥＦ  ＧＡＢ

```

として、CH#4を整理すると

```

EA AD FD DE DC DB EE AB AF AA FA FB BC BB AE EA BD CE CC FE AA A

CE E  BE EA EA A  AC CA CC CC DA BA CE DE CB CA DC BC AA DE ED DD

A        C  A               E           C           A          

D        A                                          D          

-----------------------------------------------------------------

T? M? C  T  F  {?

```

こんな感じ。おぉ Tは、確定っぽい。並び順とか違うけど、同じ音程の和音になってるね。

```

EA AD FD DE DC DB EE AB AF AA FA FB BC BB AE EA BD CE CC FE AA A

CE E  BE EA EA A  AC CA CC CC DA BA CE DE CB CA DC BC AA DE ED DD

A        C  A               E           C           A          

D        A                                          D          

-----------------------------------------------------------------

54 4D 43 54 46 7B 42 61 63 68 20 41 72 69 65 20 61 75 66 20 47 7D

T  M  C  T  F  {  B  a  c  h     A  r  i  e     a  u  f     G  }

```

縦の列の音階を全部XORしたものをASCIIコードとして見るんですね。

A xor D = 7

A xor C = 6 みたいな。

答え

```

TMCTF{Bach Arie auf G}

```

# 演習 Programming1-what_is_input

■演習問題

what_is_input.c

```c

#include <string.h>

#include <stdio.h>

void repeat_remainder( int rem ){

    if( rem == 0 ){

        printf("%p\n", &rem);

        return;

    }

    repeat_remainder(rem-1);

    return;

}

int main(int argc, const char** argv){

    if( argc != 2 ){

        printf("Invalid input\n");

        return -1;

    }

    if( memcmp(argv[1], "TMCTF{", 6) != 0 ){

        printf("Invalid input format\n");

        return -1;

    }

    if( '}' != *(argv[1] + strlen(argv[1]) - 1) ){

        printf("Invalid input format\n");

        return -1;

    }

    const char* p = argv[1]+6;

    while( *p != '}' ){

        repeat_remainder( (*p)%5 );

        repeat_remainder( (*p)%11);

        p++;

    }

    return 0;

}

```

output.txt

```

0xbff3c3f4

0xbff3c394

0xbff3c434

0xbff3c394

0xbff3c414

0xbff3c334

0xbff3c3d4

0xbff3c454

0xbff3c414

0xbff3c354

0xbff3c414

0xbff3c314

0xbff3c3d4

0xbff3c3d4

0xbff3c434

0xbff3c414

0xbff3c3f4

0xbff3c354

0xbff3c434

0xbff3c414

0xbff3c3d4

0xbff3c3d4

0xbff3c454

0xbff3c3b4

0xbff3c454

0xbff3c394

0xbff3c454

0xbff3c454

0xbff3c3f4

0xbff3c3d4

0xbff3c414

0xbff3c314

0xbff3c3d4

0xbff3c3b4

0xbff3c414

0xbff3c334

0xbff3c454

0xbff3c3b4

0xbff3c414

0xbff3c314

0xbff3c454

0xbff3c434

0xbff3c434

0xbff3c434

0xbff3c454

0xbff3c454

0xbff3c434

0xbff3c414

```

----

なんかアドレス出力してますね。入力文字のアドレスを5文字単位と11文字単位で丸めてアドレス出力しているような感じ。

自分のLinux環境だと、ASLRが動いちゃって、毎回実行する度に勝手にアドレス変わっちゃって困る。

とりあえず、こういう実行の仕方すると、ASLR無効で実行できる。

```

$ setarch `uname -m` -R  ./a.out TMCTF{hoge}

```

### 1.ます、output.txtを一文字毎に差を取ってみる

```

BFF3C3F4 - BFF3C394     =       60

BFF3C434 - BFF3C394     =       A0

BFF3C414 - BFF3C334     =       E0

BFF3C3D4 - BFF3C454     =       -80

BFF3C414 - BFF3C354     =       C0

BFF3C414 - BFF3C314     =       100

BFF3C3D4 - BFF3C3D4     =       0

BFF3C434 - BFF3C414     =       20

BFF3C3F4 - BFF3C354     =       A0

BFF3C434 - BFF3C414     =       20

BFF3C3D4 - BFF3C3D4     =       0

BFF3C454 - BFF3C3B4     =       A0

BFF3C454 - BFF3C394     =       C0

BFF3C454 - BFF3C454     =       0

BFF3C3F4 - BFF3C3D4     =       20

BFF3C414 - BFF3C314     =       100

BFF3C3D4 - BFF3C3B4     =       20

BFF3C414 - BFF3C334     =       E0

BFF3C454 - BFF3C3B4     =       A0

BFF3C414 - BFF3C314     =       100

BFF3C454 - BFF3C434     =       20

BFF3C434 - BFF3C434     =       0

BFF3C454 - BFF3C454     =       0

BFF3C434 - BFF3C414     =       20

```

### 2.アルファベット順に差を取ってみる(自分の環境)

```

7FFFFFFFE4AC - 7FFFFFFFE36C     =       140 A

7FFFFFFFE48C - 7FFFFFFFE4AC     =       -20 B

7FFFFFFFE46C - 7FFFFFFFE48C     =       -20 C

7FFFFFFFE44C - 7FFFFFFFE46C     =       -20 D

7FFFFFFFE42C - 7FFFFFFFE44C     =       -20 E

7FFFFFFFE4AC - 7FFFFFFFE42C     =       80 F

7FFFFFFFE48C - 7FFFFFFFE40C     =       80 G

7FFFFFFFE46C - 7FFFFFFFE3EC     =       80 H

7FFFFFFFE44C - 7FFFFFFFE3CC     =       80 I

7FFFFFFFE42C - 7FFFFFFFE3AC     =       80 J

7FFFFFFFE4AC - 7FFFFFFFE38C     =       120 K

7FFFFFFFE48C - 7FFFFFFFE36C     =       120 L

7FFFFFFFE46C - 7FFFFFFFE4AC     =       -40 M

7FFFFFFFE44C - 7FFFFFFFE48C     =       -40 N

7FFFFFFFE42C - 7FFFFFFFE46C     =       -40 O

7FFFFFFFE4AC - 7FFFFFFFE44C     =       60 P

7FFFFFFFE48C - 7FFFFFFFE42C     =       60 Q

7FFFFFFFE46C - 7FFFFFFFE40C     =       60 R

7FFFFFFFE44C - 7FFFFFFFE3EC     =       60 S

7FFFFFFFE42C - 7FFFFFFFE3CC     =       60 T

7FFFFFFFE4AC - 7FFFFFFFE3AC     =       100 U

7FFFFFFFE48C - 7FFFFFFFE38C     =       100 V

7FFFFFFFE46C - 7FFFFFFFE36C     =       100 W

7FFFFFFFE44C - 7FFFFFFFE4AC     =       -60 X

7FFFFFFFE42C - 7FFFFFFFE48C     =       -60 Y

7FFFFFFFE4AC - 7FFFFFFFE46C     =       40 Z

7FFFFFFFE46C - 7FFFFFFFE38C     =       E0 a

7FFFFFFFE44C - 7FFFFFFFE36C     =       E0 b

7FFFFFFFE42C - 7FFFFFFFE4AC     =       -80 c

7FFFFFFFE4AC - 7FFFFFFFE48C     =       20 d

7FFFFFFFE48C - 7FFFFFFFE46C     =       20 e

7FFFFFFFE46C - 7FFFFFFFE44C     =       20 f

7FFFFFFFE44C - 7FFFFFFFE42C     =       20 g

7FFFFFFFE42C - 7FFFFFFFE40C     =       20 h

7FFFFFFFE4AC - 7FFFFFFFE3EC     =       C0 i

7FFFFFFFE48C - 7FFFFFFFE3CC     =       C0 j

7FFFFFFFE46C - 7FFFFFFFE3AC     =       C0 k

7FFFFFFFE44C - 7FFFFFFFE38C     =       C0 l

7FFFFFFFE42C - 7FFFFFFFE36C     =       C0 m

7FFFFFFFE4AC - 7FFFFFFFE4AC     =       0 n

7FFFFFFFE48C - 7FFFFFFFE48C     =       0 o

7FFFFFFFE46C - 7FFFFFFFE46C     =       0 p

7FFFFFFFE44C - 7FFFFFFFE44C     =       0 q

7FFFFFFFE42C - 7FFFFFFFE42C     =       0 r

7FFFFFFFE4AC - 7FFFFFFFE40C     =       A0 s

7FFFFFFFE48C - 7FFFFFFFE3EC     =       A0 t

7FFFFFFFE46C - 7FFFFFFFE3CC     =       A0 u

7FFFFFFFE44C - 7FFFFFFFE3AC     =       A0 v 

7FFFFFFFE42C - 7FFFFFFFE38C     =       A0 w

7FFFFFFFE4AC - 7FFFFFFFE36C     =       140 x

7FFFFFFFE48C - 7FFFFFFFE4AC     =       -20 y

7FFFFFFFE46C - 7FFFFFFFE48C     =       -20 z

```

### 3.自分の環境の結果と照らし合わせる。

4文字目が"c"というのは、すぐ解る。

同じ差が出ている文字でも、%5している開始アドレスが変わってくるので判別できる。

例えば、差が 20 だと、候補の文字が defgh のどれかなんだけど

```

d BFF3C454

e BFF3C434

f BFF3C414

g BFF3C3F4 

h BFF3C3D4 

```

で、判別できる

```

BFF3C3F4 - BFF3C394     =       60      PQRST S

BFF3C434 - BFF3C394     =       A0      stuvw t

BFF3C414 - BFF3C334     =       E0      ab    a

BFF3C3D4 - BFF3C454     =       -80     c     c

BFF3C414 - BFF3C354     =       C0      ijklm k

BFF3C414 - BFF3C314     =       100     UVW   

BFF3C3D4 - BFF3C3D4     =       0       nopqr r

BFF3C434 - BFF3C414     =       20      defgh e

BFF3C3F4 - BFF3C354     =       A0      stuvw v

BFF3C434 - BFF3C414     =       20      defgh e

BFF3C3D4 - BFF3C3D4     =       0       nopqr r

BFF3C454 - BFF3C3B4     =       A0      stuvw s

BFF3C454 - BFF3C394     =       C0      ijklm i

BFF3C454 - BFF3C454     =       0       nopqr n

BFF3C3F4 - BFF3C3D4     =       20      defgh g

BFF3C414 - BFF3C314     =       100     UVW

BFF3C3D4 - BFF3C3B4     =       20      defgh h

BFF3C414 - BFF3C334     =       E0      ab    a

BFF3C454 - BFF3C3B4     =       A0      stuvw s

BFF3C414 - BFF3C314     =       100     UVW

BFF3C454 - BFF3C434     =       20      defgh d

BFF3C434 - BFF3C434     =       0       nopqr o

BFF3C454 - BFF3C454     =       0       nopqr r

BFF3C434 - BFF3C414     =       20      defgh e

```

UVWって書いてあるところは、実は" "(スペース)だった。

```

TMCTF{Stack reversing has dore}

```

# Analysis-offensive 200

問題

Click button to get the flag!

ということで、apkのファイルが渡される

----

**c@t** さん writeup

APK-Multi-Toolでデコンパイル・コンパイル、BlueStacksで動作確認しました。

答えらしき文字列が分からなかったので、命令を書き換えてごり押し・・・。

以下はデコンパイル後にコードを修正した部分の差分パッチです。

前半の短い部分は、クリック回数をカウントしてる変数が1000万で無い場合に弾く処理を消しました。

後半の大量のif,iput,igetは、特定のクリック回数のときに何か処理をしているようなので、

クリック回数の変数にその特定の値を設定する処理を追加しました。

コンパイルしてアプリを起動し、何回かクリックするとクリアできます。

```

Only in VirusClicker.apk2: build

Only in VirusClicker.apk2: dist

diff -u -r VirusClicker.apk/smali/com/tm/ctf/clicker/activity/CongraturationsActivity.smali VirusClicker.apk2/smali/com/tm/ctf/clicker/activity/CongraturationsActivity.smali

--- VirusClicker.apk/smali/com/tm/ctf/clicker/activity/CongraturationsActivity.smali	2015-10-13 20:36:04.731482800 +0900

+++ VirusClicker.apk2/smali/com/tm/ctf/clicker/activity/CongraturationsActivity.smali	2015-09-26 16:32:45.496808200 +0900

@@ -147,11 +147,6 @@

     move-result v1

-    if-eq v0, v1, :cond_0

-

-    invoke-virtual {p0}, Lcom/tm/ctf/clicker/activity/CongraturationsActivity;->finish()V

-

-    :cond_0

     invoke-virtual {p0}, Lcom/tm/ctf/clicker/activity/CongraturationsActivity;->getIntent()Landroid/content/Intent;

     move-result-object v0

diff -u -r VirusClicker.apk/smali/com/tm/ctf/clicker/activity/c.smali VirusClicker.apk2/smali/com/tm/ctf/clicker/activity/c.smali

--- VirusClicker.apk/smali/com/tm/ctf/clicker/activity/c.smali	2015-10-13 20:36:04.762484500 +0900

+++ VirusClicker.apk2/smali/com/tm/ctf/clicker/activity/c.smali	2015-09-26 16:32:06.931541900 +0900

@@ -782,42 +782,91 @@

     iget v1, p0, Lcom/tm/ctf/clicker/activity/c;->g:I

+    if-lt v0, v1, :mycond_1

+

+    iput v0, p0, Lcom/tm/ctf/clicker/activity/c;->g:I

+

+    iget v1, p0, Lcom/tm/ctf/clicker/activity/c;->g:I

+

+    :mycond_1

     if-eq v0, v1, :cond_1

     const/16 v0, 0x2717

     iget v1, p0, Lcom/tm/ctf/clicker/activity/c;->g:I

+    if-lt v0, v1, :mycond_2

+

+    iput v0, p0, Lcom/tm/ctf/clicker/activity/c;->g:I

+

+    iget v1, p0, Lcom/tm/ctf/clicker/activity/c;->g:I

+

+    :mycond_2

     if-eq v0, v1, :cond_1

     const v0, 0xe767

     iget v1, p0, Lcom/tm/ctf/clicker/activity/c;->g:I

+    if-lt v0, v1, :mycond_3

+

+    iput v0, p0, Lcom/tm/ctf/clicker/activity/c;->g:I

+

+    iget v1, p0, Lcom/tm/ctf/clicker/activity/c;->g:I

+

+    :mycond_3

     if-eq v0, v1, :cond_1

     const v0, 0x186a3

     iget v1, p0, Lcom/tm/ctf/clicker/activity/c;->g:I

+    if-lt v0, v1, :mycond_4

+

+    iput v0, p0, Lcom/tm/ctf/clicker/activity/c;->g:I

+

+    iget v1, p0, Lcom/tm/ctf/clicker/activity/c;->g:I

+

+    :mycond_4

     if-eq v0, v1, :cond_1

     const v0, 0x78e75

     iget v1, p0, Lcom/tm/ctf/clicker/activity/c;->g:I

+    if-lt v0, v1, :mycond_5

+

+    iput v0, p0, Lcom/tm/ctf/clicker/activity/c;->g:I

+

+    iget v1, p0, Lcom/tm/ctf/clicker/activity/c;->g:I

+

+    :mycond_5

     if-eq v0, v1, :cond_1

     const v0, 0xf4243

     iget v1, p0, Lcom/tm/ctf/clicker/activity/c;->g:I

+    if-lt v0, v1, :mycond_6

+

+    iput v0, p0, Lcom/tm/ctf/clicker/activity/c;->g:I

+

+    iget v1, p0, Lcom/tm/ctf/clicker/activity/c;->g:I

+

+    :mycond_6

     if-eq v0, v1, :cond_1

     const v0, 0x98967f

     iget v1, p0, Lcom/tm/ctf/clicker/activity/c;->g:I

+    if-lt v0, v1, :mycond_7

+

+    iput v0, p0, Lcom/tm/ctf/clicker/activity/c;->g:I

+

+    iget v1, p0, Lcom/tm/ctf/clicker/activity/c;->g:I

+

+    :mycond_7

     if-ne v0, v1, :cond_2

     :cond_1

```

# Analysis-defensive 100

vonnというELFファイルが渡される。

```

$ file vonn

vonn: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, for GNU/Linux 2.6.24, BuildID[sha1]=7f89c2bb36cc9d0882a4980a99d44a7674fb09e2, not stripped

```

実行すると

```

$./vonn

You are not on VMM

```

と表示して、自身のファイルを削除して終了する。

gdbでステップ実行すると

```

gdb-peda$ 

process 9182 is executing new program: /tmp/...,,,...,,

```

なんか、ファイルを作ってる。ここで、実行を止めて別コンソールで

```

$ cd /tmp

$ chmod ugo+x ./...,,,...,,

$ ./...,,,...,,

TMCTF{ce5d8bb4d5efe86d25098bec300d6954}

```

答え

```

TMCTF{ce5d8bb4d5efe86d25098bec300d6954}

```

# Cryptography 100

問題

```

Decrypt it by your missing private key!

kPmDFLk5b/torG53sThWwEeNm0AIpEQek0rVG3vCttc=

You have a strange public key.

Where is the lost 1bit?

Let's enjoy your prime factorization:)

```

ということで、共通鍵と思わしきファイルが渡される

----

**c@t**さん writeup

まず素数の積を表示。

```

$ openssl rsa -pubin -text < PublicKey.pem 

Public-Key: (256 bit)

Modulus:

    00:b6:2d:ce:9f:25:81:63:57:23:db:6b:18:8f:12:

    f0:46:9c:be:e0:cb:c5:da:cb:36:c3:6e:0c:96:b6:

    ea:7b:fc

Exponent: 65537 (0x10001)

writing RSA key

-----BEGIN PUBLIC KEY-----

MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhALYtzp8lgWNXI9trGI8S8EacvuDLxdrL

NsNuDJa26nv8AgMBAAE=

-----END PUBLIC KEY-----

$ openssl rsa -pubin -text < PublicKey.pem | egrep "^ " | sed -e 's/://g'

writing RSA key

    00b62dce9f2581635723db6b188f12

    f0469cbee0cbc5dacb36c36e0c96b6

    ea7bfc

0x00b62dce9f2581635723db6b188f12f0469cbee0cbc5dacb36c36e0c96b6ea7bfc

```

答えは最終bitが反転してたんだけど、そもそもこれ偶数じゃないか・・・。

先人のツールを拝借しつつ、素因数分解して復号化を実施。

```

$ cat msieve.00b62dce9f2581635723db6b188f12f0469cbee0cbc5dacb36c36e0c96b6ea7bfd.log 

(snip)

Sun Sep 27 00:34:35 2015  prp39 factor: 279125332373073513017147096164124452877

Sun Sep 27 00:34:35 2015  prp39 factor: 295214597363242917440342570226980714417

Sun Sep 27 00:34:35 2015  elapsed time 00:03:29

$ python genrsa.py 

-----BEGIN RSA PRIVATE KEY-----

MIGmAgEAAiC2Lc6fJYFjVyPbaxiPEvBGnL7gy8XayzbDbgyWtup7/QIDAQABAiBmFb0WyPl8JTRe

m+CjK8Wfmc4OQE8hvrvpfOO9bceNAQIQ0f2VZdriZPX9V5U9v7noDQIQ3hhDaCqytILM/1BvAs93

sQIQCdB3Rg5n3F4e3BQOkcJnlQIQP59HwBFrPBa0TvdltbJlIQIQcFyJhxTaQVkB9pJqKC2NOQ==

-----END RSA PRIVATE KEY-----

$ python genrsa.py > private.key

$ openssl enc -in crypted_message.txt -out binarytext -d -a

$ openssl rsautl -decrypt -in binarytext -out plain.txt -inkey private.key 

$ cat plain.txt 

TMCTF{$@!zbo4+qt9=5}

```

PCを無駄に頑張らせてしまいましたが、せっかく書いたので全bit反転させながら調べるプログラムも貼っておきます。

```ruby

#!/usr/bin/ruby

require 'yaml'

org_pubkey = "00b62dce9f2581635723db6b188f12f0469cbee0cbc5dacb36c36e0c96b6ea7bfc".scan(/.{1,2}/).map{|m| m.hex}

bitmask = [0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80]

org_pubkey.each_with_index do |c, i|

  bitmask.each do |mask|

    new_pubkey = org_pubkey.clone

    new_pubkey[i] = (new_pubkey[i] ^ mask)

    pubkey_str = new_pubkey.map{|m| sprintf("%02x", m)}.join

    puts "next pubkey: #{pubkey_str}"

    result = ""

    result_file = "msieve.#{pubkey_str}.log"

    if File.exists?(result_file)

      File.open(result_file) do |f|

        result = f.read

      end

    else

      result = `./msieve -e -v 0x#{pubkey_str}`

      `mv msieve.log #{result_file}`

    end

    result = result.encode("UTF-16BE", "UTF-8",

           invalid: :replace,

           undef: :replace,

           replace: '.').encode("UTF-8")

    if result.encode("UTF-8").split(/\n/).select{|line| line =~ /factor:/}.length == 2

      puts pubkey_str

      exit

    end

  end

end

```

# Cryptography 500

問題

アルファベットのみで構成された同じ長さの異なる2つの文字列を考えます。

その文字列をそれぞれBase64でエンコードした結果、同じ位置に同じ文字があれば抜きだすことにします。

抜きだした文字を順に左から並べたとき、できあがる文字列が「2015」「Japan」になるような入力列として、以下のようなものがあります。

例）

CaEkMbVnD→(Base64)→Q2FFa01iVm5E

GePoMjXNW→(Base64)→R2VQb01qWE5X

aBckjTiRgbpS→(Base64)→YUJja2pUaVJnYnBT

URehZQjLyvwk→(Base64)→VVJlaFpRakx5dndr

このとき、抜き出してできる文字列に上記のように「a」が現れることはありますが、「f」*が現れることはありません。

入力にどんなアルファベットを指定しても、抜きだしてできる文字列に現れることがないような文字の一覧を求め、

「ASCIIコード順」に並べたものを「SHA1」でハッシュ化した小文字の値で出力し、"TMCTF{<出力した値>}"として回答してください。

*訂正前の問題文は「A」となっていました。誤りなので訂正します。

----

**c@t**さん writeup

平文3文字 → 4文字にエンコードされるので、1～3文字の全ての組み合わせのエンコードを実施。

エンコード後の文字の位置毎に出現回数を数えて、一度も現れない文字を探します。

答えは、67569763552b4e9b8ac950be0d25f446f8470c60

```

$ ruby listup.rb

(snip)

+/7f

67569763552b4e9b8ac950be0d25f446f8470c60

```

listup.rb

```ruby

#!/usr/bin/ruby

require 'base64'

require 'digest/sha1'

require 'yaml'

#puts Base64.encode64("CaEkMbVnD")

#exit

chars = [*("A".."Z"),*("a".."z")]

words = []

result = []

chars.each do |a|

  encoded_str = Base64.encode64("#{a}")

  encoded_str.split(//).each_with_index do |c, i|

    result[i] = {} unless result[i]

    result[i][c] = 0 unless result[i][c]

    result[i][c] += 1

  end

end

chars.repeated_permutation(2) do |a, b|

  encoded_str = Base64.encode64("#{a}#{b}")

  encoded_str.split(//).each_with_index do |c, i|

    result[i] = {} unless result[i]

    result[i][c] = 0 unless result[i][c]

    result[i][c] += 1

  end

end

chars.repeated_permutation(3) do |a, b, c|

  encoded_str = Base64.encode64("#{a}#{b}#{c}")

  encoded_str.split(//).each_with_index do |c, i|

    result[i] = {} unless result[i]

    result[i][c] = 0 unless result[i][c]

    result[i][c] += 1

  end

end

puts result.to_yaml

strings = ["+","/",*("0".."9"),"=",*("A".."Z"),*("a".."z")]

#strings = [*("0".."9"),*("A".."Z"),*("a".."z")]

counter = {}

result.each do |v|

  v.each do |c, n|

    counter[c] = 0 unless counter[c]

    counter[c] += 1

  end

end

answer = ""

strings.each do |c|

  next if counter[c]

  answer += c

end

puts answer

puts Digest::SHA1.hexdigest(answer)

```

# Programming 100

**c@t** さん writeup

URLを開くと色つきの正方形が沢山並んでいて、1つだけ違う色のマスをクリックするという問題。

マスがどんどん小さくなっていくので、自力では流石に無理ですね。

1ピクセルずつ色を数えて、(白を除く)一番少なかった色の座標をクリックするプログラムを書きました。

最後まで行くと答えが表示されます。エラーはご愛嬌ということで・・・。

```

$ruby prog100.rb

(snip)

Congraturations!!

The flag is TMCTF{U must have R0807 3Y3s!}

prog100.rb:54:in `rescue in <main>': undefined method `body' for #<Mechanize:0x000000024bfe90> (NoMethodError)

	from prog100.rb:40:in `<main>'

```

prog100.rb

````ruby

#!/usr/bin/ruby

require 'mechanize'

require 'rmagick'

url = "http://ctfquest.trendmicro.co.jp:43210/click_on_the_different_color"

def get_most_shine_point(filename)

  image = Magick::Image.read(filename).first

  color_counter = {}

  image.each_pixel do |p|

    color = (p.red & 0xFF) + (p.green & 0xFF) * 0x100 + (p.blue & 0xFF) * 0x10000

    color_counter[color] = 0 unless color_counter[color]

    color_counter[color] += 1

  end

  puts image.columns

  puts color_counter

  mincolor = color_counter.sort{|(k1,v1),(k2,v2)| k2 <=> k1}[1][0]

  puts mincolor

  n = 0

  image.each_pixel do |p|

    color = (p.red & 0xFF) + (p.green & 0xFF) * 0x100 + (p.blue & 0xFF) * 0x10000

    if color == mincolor

      return [n % image.columns, n / image.columns]

    end

    n += 1

  end

  puts "Error..."

  return [0, 0]

end

#filename = "d5f4a52aad72c56ab771213407319384c5bdd38b43eb.png"

#puts get_most_shine_point(filename)

agent = Mechanize.new

begin

  loop do

    puts url

    page = agent.get(url)

    puts page.body

    image_url = page.at("img")[:src]

    puts image_url

    filename = File.basename(image_url)

    agent.download(image_url, filename) unless File.exists?(filename)

    (x, y) = get_most_shine_point(filename)

    url = "/#{File.basename(filename, '.png')}?x=#{x}&y=#{y}"

  end

rescue => e

  puts agent.body

end

```

# Programming 200

```

Calculate it.

nc ctfquest.trendmicro.co.jp 51740

```

----

みんな大好き計算問題。

見せてやるぜ！オレのシェル芸を！と、思ってやり始めたら撃沈した。

### ３種類の数値表現

３種類の数値表現が出てくる。

**数字**

```

62 * 9,324 + 1,859 * ( 300 - 7 ) + 2,921 - 37 * ( 58,555,427 + 4,982,941,063 ) - 59 + 5,528,776,321 =

```

**ローマ数字**

```

( CDXXVIII + 344131 ) * ( DCCXCVII + 8620480 ) * 154274 + 4757 - DXXXII + 790147 * ( IX + CMI ) * II = 

```

**英語**

```

206,441 * six million, one hundred thirty two thousand, eight hundred thirty nine + ninety - three hundred seventy + five million, eight hundred eighty nine thousand, seven hundred seven * ( 658 + eighty nine ) - 976 =

```

英語で死んだ。パーサー書くのめんどくさくなって、英語を逐次google翻訳して数値を得ようとして失敗した。「はい今死んだ！今君のシェル芸死んだよ！」 みたいな気分になった。

### ローマ数字と英語の対応

ローマ数字は、辞書を作って対応。[ローマ数字（1から3999まで）の一覧](http://kw-note.com/notation/roman-numerals/)を参照しました。

dic.txt

```

0	ZERO	zero

1       I       One

2       II      Two

3       III     Three

4       IV      Four

5       V       Five

       ・

       ・

       ・

3999    MMMCMXCIX       Three Thousand Nine Hundred Ninety Nine

```

英語は結局、perlの[Lingua::EN::Words2Nums](http://search.cpan.org/~joey/Lingua-EN-Words2Nums-0.18/Words2Nums.pm)という英語を数値に変換してくれるライブラリを見つけて対応した。

### 以下、適当solver

test.sh

```

#!/bin/sh

transrate(){

  W=`echo $1`

  W2=`perl solv.pl "$W"`

  echo $W2

}

exec 5<>/dev/tcp/ctfquest.trendmicro.co.jp/51740

for I in {1..1001}

do

  cat 0<&5>test.txt &

  cat test.txt >> log.txt

  sleep 2

  pkill cat

  LIST=`cat test.txt|tail -1|tr '*' 'Z'`

  WORD=""

  FULL_NUM=""

  PARTS_NUM=""

  for WORK in ${LIST}

  do

  if echo ${WORK} |grep [A-Y] >/dev/null

  then

    #-------------------------------------------------------------

    # ローマ数字変換

    #-------------------------------------------------------------

    ROMAN_WORK=`grep $'\t'"${WORK}"$'\t' dic.txt|awk '{print $1}'`

    WORD="${WORD}${ROMAN_WORK}"

  elif echo ${WORK} |grep [a-z] >/dev/null

  then

    #-------------------------------------------------------------

    # 英数字変換

    #-------------------------------------------------------------

    FULL_NUM="${FULL_NUM}${WORK}"

  else

    #-------------------------------------------------------------

    # それ意外

    #-------------------------------------------------------------

    A_NUM=`transrate "${FULL_NUM}"`

    WORD="${WORD}${A_NUM}${WORK}"

    A_NUM=""

    FULL_NUM=""

  fi

  done

  WORD=`echo ${WORD}|sed 's/Z/*/g'|tr -d '=,'`

  echo ==============================================================

  cat test.txt

  echo

  echo "${WORD}"

  ANSWER=`echo ${WORD}|bc`

  echo ${ANSWER} >&5

  echo Debug [${I}] ${WORD} '=' ${ANSWER}

done

exit 0

```

solv.pl

```perl

#!/bin/perl

use Lingua::EN::Words2Nums;

$num=words2nums($ARGV[0]);

print $num

```

最後、こんな感じでフラグが出る。

答え

```

Congratulations!

The flag is TMCTF{U D1D 17!}

```

# Programming 300

**リリりん♪**さん writeup

まず、PCにプログラミング環境入れずに開始時刻を迎えてしまったので

手っ取り早くプログラミングできる環境をそろえるために

Microsoft Visual Studioをダウンロード＆インストール。意外と重かった。

コンパイラはC++のものですが、C言語でプログラミングしました。

迷路の単純な解法は、右手か左手を壁につけたまま移動する、という方法もあるのですが、

この方法だけでは解けない迷路も存在するので、「上下左右に移動する経路を全探索する」というアプローチをとりました。

通常の迷路では、一度通った経路を通らないので、後戻りすると即死する方法がいいのですが、

今回は「チェックポイントを通過する」「エナジードリンク（以下E缶と表記）」ということから後戻り禁止にもできません。

かといって、まともに探索するといくら時間があっても足りなさそうです。

そこで、「最後にチェックポイントかE缶を取ったあとに」通った経路を通ってはいけない、という制約を付けました。

あとは仕様通りプログラミングして、コスト（同じ経路を２回目以降に通った場合に+1、ゴール時残したE缶１つにつき+20）

を計算して最適なルートを通るようにしました。

ちなみに、[いしのなかにいる](http://rocketnews24.com/2012/08/13/240452/)とはWizardlyの言葉です。

プログラムで迷路を解こうとするときは、石があっても突っ込むので数多くの勇者が石に吸い込まれていったことでしょう・・・。

```c

#include "stdafx.h"

#include <stdio.h>

#include <stdlib.h>

#define POS(x,y) ((y)*(w)+(x))

#define SIZE(w,h) ((w)*(h))

#define MAX_DEPTH 150

struct node {

	struct node * next[4]; //左上右下の順

	char c;

	int x, y;

};

struct route {

	char path[MAX_DEPTH+1];

	int path_pos;

	unsigned int cost;

};

struct node *maze;

int w; //迷路の幅

struct node *start = NULL;

struct node *goal = NULL;

struct node *ckpt[30] = {};

int ckpt_num;

FILE *fp_out, *fp_out2;

int ekan_num;

struct path {

	int life;

	//現在の場所

	int x, y;

	//残りのチェックポイント数を調べます。

	char ckpt_left;

	//残りのE缶の数を調べます。

	char ekan_left;

	//対象の位置をすでに通ったかどうかを判定します。

	char footprint[30][30];

	//エネルギーを使ったら増える

	char cost;

};

const char *delection = "LURD";

// -1:答なし 0,1,2,3,...:解ありの場合の最小コスト

// route 

// path ※値渡し

struct route solve_maze_core(struct path path) {

	struct route route; //Return用

	struct route route_get[4]; //比較用

	unsigned int min_cost = 0;

	//指定歩数以下でたどり着けない場合はNG

	if (path.life == 0) {

//		fprintf(fp_out2, "life is 0\n");

		route.cost = -1;

		return route;

	}

	path.life--;

	// *いしのなかにいる* 場合は即死

	if (maze[POS(path.x, path.y)].c == '#') {

//		fprintf(fp_out2, "in the wall\n");

		route.cost = -1;

		return route;

	}

	if (maze[POS(path.x, path.y)].c != '.') {

		fprintf(fp_out2, "pos %d, %d road=%c cost=%d life=%d fp=%d ", path.x, path.y, maze[POS(path.x, path.y)].c, path.cost, path.life, path.footprint[path.x][path.y]);

	}

	//2回目以降にくる場合はコスト増加

	if (path.footprint[path.x][path.y]) {

		//CheckpointもEも通らずに再度来た場合はNG(枝刈り) 

		if (path.footprint[path.x][path.y] == path.ckpt_left + path.ekan_left + 1) {

			if (maze[POS(path.x, path.y)].c != '.') {

				fprintf(fp_out2, "footprint error c=%d e=%d\n", path.ckpt_left, path.ekan_left);

			}

			route.cost = -1;

			return route;

		}

		path.cost++;

	}

	else {

		//最初にC,Eにくる場合はチェックポイント通過

		if (maze[POS(path.x, path.y)].c == 'C') {

			path.ckpt_left--;

		}

		//最初にEにくる場合はE回数増加

		if (maze[POS(path.x, path.y)].c == 'E') {

			path.ekan_left--;

		}

	}

	path.footprint[path.x][path.y] = path.ckpt_left + path.ekan_left + 1;

	//チェックポイント全通過かつここがゴールならコストを報告. Eを残した場合はペナルティ加算。

	if (path.ckpt_left == 0 && maze[POS(path.x, path.y)].c == 'G') {

		fprintf(fp_out2, "Reached goal c=%d e=%d\n", path.ckpt_left , path.ekan_left);

		route.path_pos = MAX_DEPTH;

		route.path[MAX_DEPTH] = '\0';

		route.cost = path.cost + path.ekan_left * 20;

		return route;

	}

	if (maze[POS(path.x, path.y)].c != '.') {

		fprintf(fp_out2, "normal phaze c=%d e=%d\n", path.ckpt_left, path.ekan_left);

	}

	//上下左右に移動して迷路を解く

	path.x--;

	route_get[0] = solve_maze_core(path);

	min_cost = 0;

	path.x++;

	path.y--;

	route_get[1] = solve_maze_core(path);

	if (route_get[min_cost].cost > route_get[1].cost) {

		min_cost = 1;

	}

	path.y++;

	path.x++;

	route_get[2] = solve_maze_core(path);

	if (route_get[min_cost].cost > route_get[2].cost) {

		min_cost = 2;

	}

	path.x--;

	path.y++;

	route_get[3] = solve_maze_core(path);

	if (route_get[min_cost].cost > route_get[3].cost) {

		min_cost = 3;

	}

	path.y--;

	route = route_get[min_cost];

	if (route_get[min_cost].cost < 10000) {

		route.path[--route.path_pos] = delection[min_cost];

		fprintf(fp_out2, "pos %d, %d road=%c cost=%d life=%d route:%s\n", path.x, path.y, maze[POS(path.x, path.y)].c, path.cost, path.life, &route.path[route.path_pos]);

	}

	return route;

}

//迷路を解く

int solve_maze(void) {

	struct path path = {};//0初期化

	struct route route; //Return受け取り用

	path.x = start->x;

	path.y = start->y;

	path.ckpt_left = ckpt_num;

	path.ekan_left = ekan_num;

	path.life = MAX_DEPTH;

	route = solve_maze_core(path);

	if (route.cost > 100000) {

		return -1;

	}

	fprintf(fp_out, "%s\n", &route.path[route.path_pos]);

	fprintf(fp_out2, "ANSWER:%s\n", &route.path[route.path_pos]);

	return 0;

}

int main()

{

	FILE *fp;

	int h, x, y;

	int chk, pos;

	char c;

	struct node *node;

	int solved;

	int qid = 0;

        //問題ファイル、答え、デバッグ出力のファイルを開く

	fopen_s(&fp, "d:\\maze.txt", "r");

	fopen_s(&fp_out, "d:\\maze.solved.txt", "w");

	fopen_s(&fp_out2, "d:\\maze.debug.txt", "w");

        //問題ファイルが開けないときだけエラー処理（他はエラーの場合は不正終了します）

	if (fp == NULL) {

		exit(0);

	}

	do {

		// 迷路の読み込み開始

		pos = 0;

		ckpt_num = 0;

		ekan_num = 0;

		fscanf_s(fp, "%d %d %d", &w, &h, &chk);

		fprintf(fp_out2, "%d %d %d\n", w, h, chk);

		printf("#%d %d %d %d\n", ++qid, w, h, chk);

		maze = (struct node *)malloc(SIZE(w, h) * sizeof(struct node));

		memset(maze, 0, SIZE(w, h) * sizeof(struct node));

		while (EOF != (c = fgetc(fp))) {

			switch (c) {

			case '#':

			case 'S':

			case 'G':

			case 'C':

			case 'E':

			case '.':

				maze[pos++].c = c;

				break;

			}

			if (pos == SIZE(w, h)) {

				break;

			}

		}

		// 表示（デバッグ用）

		for (y = 0; y < h; y++) {

			for (x = 0; x < w; x++) {

				fprintf(fp_out2, "%c", maze[POS(x, y)].c);

			}

			fprintf(fp_out2, "\n");

		}

		// ノードを追加（ホントは要らなかった。文字のままでよかった…）

		for (y = 0; y < h; y++) {

			for (x = 0; x < w; x++) {

				switch (maze[POS(x, y)].c) {

				case '#':

					continue;

				case 'S':

					start = &maze[POS(x, y)];

					break;

				case 'G':

					goal = &maze[POS(x, y)];