ニュース

zlib圧縮部分を抽出・展開してファイルに保存するツール作りました

kanata が約9年前に追加

CTFでzlib圧縮部分に気づかずに、解けなかった問題が過去２問あって、
これはいかんと思いました(小並感)。

zlib圧縮部分って、マジックナンバーが定まっているわけじゃなくて、目grepでもすごく判別しにくい。
しかも、fileコマンドでも、tridでも、判らないんだよね。

バイナリからzlib圧縮データを探す
http://teraapi.blogspot.jp/2012/05/zlib.html

よくある： 
78 01, 78 5e, 78 9c, 78 da 

稀 ：
08 1d, 08 5b, 08 99, 08 d7, 18 19, 18 57, 18 95, 18 d3, 
28 15, 28 53, 28 91, 28 cf, 38 11, 38 4f, 38 8d, 38 cb, 
48 0d, 48 4b, 48 89, 48 c7, 58 09, 58 47, 58 85, 58 c3, 
68 05, 68 43, 68 81, 68 de 

極稀：
08 3c, 08 7a, 08 b8, 08 f6, 18 38, 18 76, 18 b4, 18 f2, 
28 34, 28 72, 28 b0, 28 ee, 38 30, 38 6e, 38 ac, 38 ea, 
48 2c, 48 6a, 48 a8, 48 e6, 58 28, 58 66, 58 a4, 58 e2, 
68 24, 68 62, 68 bf, 68 fd, 78 3f, 78 7d, 78 bb, 78 f9

そこで、引数のファイルに含まれるzlib圧縮部分を抽出・展開してファイルに保存するツール作った。

CentOSで動作確認済み。Kali Linuxだとopensslでzlibのdecodeが出来なかったので、たぶん、Debian でも動かないかも。
まぁ、zpipeで代替すれば、どの環境でも行けるはず。
ちなみに、動作はめっちゃ遅い。

#!/bin/bash

# zlib_extraction.sh ver 1.3
# 引数のファイルに含まれるzlib圧縮部分を抽出・展開してファイルに保存する
# 2015.10.06 kanata 

while [ "$#" -gt 0 ]
do

if [ ! -f "${1}" ]
then
  echo "file open error ($1)"
  exit 1
fi

FILESIZE=`ls -l ${1}|awk '{print $5}'`
ZLIBPART="${1##*/}"
ZLIBPART="${ZLIBPART%.*}"
I="0"
FORK_COUNT="0"

  while [ "${I}" -lt "${FILESIZE}" ]
  do
    ZLIBPART_FILE="${ZLIBPART}_${I}.bin"
    ( cat ${1} | dd bs=1 skip=${I} | openssl zlib -d > ${ZLIBPART_FILE} 2>/dev/null ; if [ -s ${ZLIBPART_FILE} ] ; then file ${ZLIBPART_FILE} ; else rm -f ${ZLIBPART_FILE} ; fi )&

    # 並列実行時のサブシェルが増大していくのを抑止
    # 同時35多重までに抑止 25回に1度チェック ( 数値を弄ってチューニングできます )
    if [ $(( I % 25 )) -eq "0" ] ; then FORK_COUNT=`ps -u |fgrep -c ${0}` ; fi
    while  [ "${FORK_COUNT}" -gt "35" ] 
    do
      printf "[WARNING] SubProcess Exceed Limit. fork:%s offset:%s\n" ${FORK_COUNT} ${I}
      FORK_COUNT=`ps -u |fgrep -c ${0}`
    done

    I=$(( I + 1 ))
  done

shift
done

exit 0

遅かったので、処理を並列化したんだけど、その並列化を制御する処理自体がボトルネックになって、そんなに速くならなかった。微妙。

これでpdfとかswfとかから、データの抽出ができるハズ。

詳細：CTF Forensic

2016.8.3 追記
バージョンアップした。シリアル処理と並列処理を選択できるようにした。

CTF Forensic - 引数のファイルに含まれるzlib圧縮部分を抽出・展開してファイルに保存する

Trend Micro CTF 2015 Writeup (3コメント)

kanata が約9年前に追加

CTF Writeup TMCTF2015

結果＆感想

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だと思われ。

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

ココらへんに、ChaCha暗号のライブラリが纏められているのを発見。
その中から、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

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

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

#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反転させながら調べるプログラムも貼っておきます。

#!/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

#!/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

#!/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まで）の一覧を参照しました。

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という英語を数値に変換してくれるライブラリを見つけて対応した。

以下、適当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

#!/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）
を計算して最適なルートを通るようにしました。

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

#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)];
                    break;
                case 'C':
                    ckpt[ckpt_num++] = &maze[POS(x, y)];
                    break;
                case 'E':
                    ekan_num++;
                case '.':
                    break;
                default:
                    continue;
                }
                maze[POS(x, y)].x = x;
                maze[POS(x, y)].y = y;

                if (maze[POS(x - 1, y)].c != '#') {
                    maze[POS(x, y)].next[0] = &maze[POS(x - 1, y)];
                }
                if (maze[POS(x, y - 1)].c != '#') {
                    maze[POS(x, y)].next[1] = &maze[POS(x, y - 1)];
                }
                if (maze[POS(x + 1, y)].c != '#') {
                    maze[POS(x, y)].next[2] = &maze[POS(x + 1, y)];
                }
                if (maze[POS(x, y + 1)].c != '#') {
                    maze[POS(x, y)].next[3] = &maze[POS(x, y + 1)];
                }
            }
        }

        //解法生成
        solved = solve_maze();

        free(maze);

        //getchar();

    } while (solved == 0 && qid != 1001); //解けなかったか、１０００問解いたら終了
    //getchar();

    return 0;
}

Programming 500

リリりん♪さん writeup

ブラックジャックで、特定の手のときにStandしたときと、Hitしたときの勝率を求める問題です。
ブラックジャックは知っていたのですが、昨今ラスベガスで行われているルールとは若干違っています。

ブラックジャックは、正しくプレイした場合、掛け金の99%が戻ってくる程度の期待値と言われています。
１００％ではないのは、次のような理由からです。

  • プレイヤーがBUSTした場合、ディーラーがBUSTしたとしてもプレイヤーの負け 　　このルールにより、プレイヤーは圧倒的に不利になります。これを緩和するために、以下のようなルールが設けられます。
  • ダブルダウン：プレイヤーは、最初のHitをするとき、その次以降Hitできる権利を放棄するかわりに掛け金を倍にすることができる。 　　ディーラーのカードが見えた状態（ディーラーがBUSTしやすいことが判明した状態）で掛け金を増やせるので、プレイヤー有利になります。

対して、このカジノは以下のような変更点が加えられています。

  • プレイヤーとディーラーの手が同じ場合、BUSTでなくてもプレイヤーの負け
  • ダブルダウンなし

このように、プレイヤーに不利なルールを押し付けてくる超ブラックカジノですから、
いますぐに退出し別のカジノでプレイするのが正しい　ということは自明です。
（そもそも期待値99%なので、そもそもブラックジャックをプレイしないのが正しいのですが…。）

さて、そうは言ってもCTFの問題ですから、確率を計算しなければなりません。
このカジノでのブラックジャックは以下の手順で進められます。
1. プレイヤー2枚、ディーラー2枚の手札が配られる。ディーラーは2枚のうち、1枚だけを表にする。
2. プレイヤーが好きなだけ枚数を増やす。
3. ディーラーがルールに従って枚数を増やす。
4. プレイヤーの手とディーラーの手を比較し、強いほうが勝利。

さて、上記の順序でプログラミングしてみましょう。
まず、カード2組104枚を使う、とのことでしたので、点数別にカード枚数を定義します。

    { 0,8,8,8,8,8,8,8,8,8,32 },

0点は0枚、1点（A）は8枚・・・10点（10JQK）は32枚です。
初期状態が与えられているので、見えているカードを減らします。

    //自分の手札2まい
    node.card[1]--;
    node.card[2]--;
    node.myhand = 13;
    node.myace = 1;
    //ディーラの手札1まい
    node.card[3]--;
    node.dlhand = 3;
    node.dlace = 0;

ちなみに、aceを別管理するのは、「22以上になっても10を引いて復活」という仕組みにしています。

まずは、プレイヤーがStandをした場合の確率を、calc_win_dealerという関数で実装。
プレイヤーがHitした場合の確率を求めることを考慮し、あらゆる状態に対応した勝率を求める関数を作ります。

double calc_win_dealer(struct node node) {
    int i;
    double ret = 0.0;
    struct node node2;

    //ディーラーのバースト判定
    while (node.dlhand > 21 && node.dlace > 0) {
        node.dlace--; node.dlhand -= 10;
    }
    if (node.dlhand > 21) {
        return 1.0;
    }

    //ディーラーがStandする場合
    if (node.dlhand > 16) {
        if (node.myhand > node.dlhand) {
            return 1.0;
        }
        else if (node.myhand == node.dlhand) {
            return 0.0;
        }
        else{
            return 0.0;
        }
    }

    //ディーラーがHitする場合
    for (i = 1; i < 11; i++) {
        if (node.card[i] == 0) {
            continue;
        }

        //カードをドローする前の状態にする
        node2 = node;
        //カードをドロー
        node2.card[i]--; node2.cardnum--;
        switch (i) {
        case 1:
            node2.dlhand += 11; node2.dlace += 1;
            break;
        default:
            node2.dlhand += i;
            break;
        }
        ret += calc_win_dealer(node2) * (double)(node.card[i]) / (double)node.cardnum ;
    }
    return ret;
}

ディーラーがHitする場合は、(Hitした数字で勝つ確率) × (その数字を引く確率)の合計です。
Hitした数字で勝つ確率は、再帰的に呼び出すことにしています。

では、次にHitした場合の勝率を求めてみましょう。

  • BUSTした場合はディーラーの確率を求めるまでもなく負け
  • 現在の時点でStandした場合は、calc_win_dealerを参照して勝率を求める（ただし、初回だけは仕様上強制Hitする）
  • Hitする場合、勝てる確率は再帰的に呼び出して計算する ** 効率化のため、さすがに19以上でHitするケースの方が勝率が上がるワケがないので19以下の場合だけHitを考慮する

という方針で実装しました。

double calc_win_player(struct node node, int nohit) {
    int i,j;
    double ret = 0.0;
    struct node node2;
    double stand = 0.0;

    //プレイヤーのバースト判定
    while (node.myhand > 21 && node.myace > 0) {
        node.myace--; node.myhand -= 10;
    }
    if (node.myhand > 21) {
        for (j = 0; j < LIFE - node.life; j++)fputc(' ', fp_out2);
        fprintf(fp_out2,"Burst\n");
        return 0.0;
    }

    //Standする場合の確率
    if (nohit == 0) {
        stand = calc_win_dealer(node);
        for (j = 0; j < LIFE - node.life; j++)fputc(' ', fp_out2);
        fprintf(fp_out2, "Now %d, ace %d\n", node.myhand, node.myace);
    }

    //あまりにも低い確率でしか出ない場合はStandの確率を返す
    if (node.life > 0 && node.myhand < 19) {
        node.life--;
        //Hitする場合
        for (i = 1; i < 11; i++) {
            if (node.card[i] == 0) {
                continue;
            }
            //カードをドローする前の状態にする
            node2 = node;
            //カードをドロー
            node2.card[i]--; node2.cardnum--;
            switch (i) {
            case 1:
                node2.myhand += 11; node2.myace += 1;
                break;
            default:
                node2.myhand += i;
                break;
            }
            for (j = 0; j < LIFE - node.life; j++)fputc(' ', fp_out2);
            fprintf(fp_out2, "Hit %d (%d/%d) now %d, ace %d\n", i, node.card[i], node.cardnum, node.myhand, node.myace);
            ret += calc_win_player(node2, 0) * (double)(node.card[i]) / (double)node.cardnum;
        }
    }
    for (j = 0; j < LIFE - node.life; j++)fputc(' ', fp_out2);
    fprintf(fp_out2,"stand %10.7f, Hit %10.7f\n", stand, ret);
    if (ret < stand) return stand;
    return ret;
}

これが中心部分です。全ソースは添付していますので、興味があればダウンロードして解析してみてください。

ConsoleApplication2.cpp

※上記ソースは、エラー処理等の考慮が不十分な点があります。これは、CTFという環境のもと、エラーが発生しないケースで1度正常に動作すれば良いというプログラムであったために無視しています。あらかじめご承知おきください。

Miscellaneous 200

リリりん♪さん writeup

じゃんけんに30連勝しろよ、という指令。
ふつうに考えると1/(3の30乗)＝0.0000000000004%くらいで発生するのですが、Trendmicroが出してくる手は「チートしない」「学習する」との記載がありましたので、どう学習データを作るか悩んでました。

そんなところに kanata さんから「1回のアクセスで5000勝負までできる」という情報をもらって、ちょっとひらめきました。
「これって、4970回ランダムに入れて学習成果を一定にすれば、その後出してくる手はだいたい同じなんじゃない…？」

というわけで、Excelでランダム手を5000個生成。最近はRANDBETWEENが使えるからじゃんけんの手の生成も楽勝です。

それで4971手目から、Trendmicroが出してくる手に勝つ手に変更していきます。
完全に固定というわけではなく、ランダムになる箇所もありましたが、おそらく学習を忘れてしまったところなので、その場合はリロードして勝つまでやっています。
ちょっと地味な作業でしたが、何とか30連勝できました。

Miscellaneous 400

c@t さん writeup

Chinese chess の対戦プログラム。
こちらは相手の駒を取れない、対戦相手のAIは連続2手動かせる、とやりたい放題。

上手くアンパックできなかったので、とりあえず手番管理してるメモリでも探そうか。
・・・と思ったが、見つからず。
代わりに、よく分からないアドレスを発見。

  • ウィンドウがフォーカスを失ったとき？に変化するアドレス (起動のたびに変わる)
  • 0x1458B350 のアドレスの値を書き換えると、微妙に操作するプレイヤーが変わる

な…　何を言っているのか　わからねーと思うが
おれも　何をされたのか　わからなかった…

とりあえず、フォーカス変数？の値が 0x28 の時にアドレス 0x1458B350 の値を1に、
それ以外で 0x1458B350 を 0 に書き換えてみると、以下のように状況が改善される。

  • 自分の手番で駒を取れる
  • 相手の手番のうち1回は、こちらの駒を動かしてくれる

相手の手番でも駒が取れてしまうが、上手いこと頑張って
一つも駒を取られずに最後の1枚をとることができれば、フラグが表示される。

TMCTF{W1NN1N9_TH3_1MP0551BL3_G4M3}

期待の良書ラッシュ！ (1コメント)

kanata が約9年前に追加

なんかとても気なる本が続々と！

[9/12]ハロー "Hello, World" OSと標準ライブラリのシゴトとしくみ
http://www.amazon.co.jp/dp/4798044784/

[9/30]セキュリティコンテストチャレンジブック -CTFで学ぼう! 情報を守るための戦い方-
http://www.amazon.co.jp/dp/4839956480/ref=cm_sw_r_tw_dp_Jpw-vb0XRB1Q4

[10/24]サイバーセキュリティプログラミング　――　Ｐｙｔｈｏｎで学ぶハッカーの思考
http://www.e-hon.ne.jp/bec/SA/Detail?refBook=978-4-87311-731-7&Rec_id=1010

シルバーウィークはこれを読むぞ～

20150919_hellowrold.jpg

Latest Hacking News には、便利そうなCheet Sheetが沢山ある

kanata が約9年前に追加

Latest Hacking Newsというサイト(全部英語だけど)があって、たまに
いろんなカンニングペーパーを公開してくれる。
たまに見ると新しいのが増えていて面白い。

自分が見つけた便利そうなのを一応紹介してみる。

Security Cheat Sheets for Ethical Hacking and Penetration Testing
https://www.latesthackingnews.com/security-cheat-sheets-for-ethical-hacking-and-penetration-testing/

Kali Linux Commands Cheat Sheet
https://www.latesthackingnews.com/kali-linux-commands-cheat-sheet/

Metasploit Cheat Sheet Free Download
https://www.latesthackingnews.com/metasploit-cheat-sheet-free-download/

ちなみに、便利そうとか言いながら、お世話になったことは、まだないのだけれど。

Microsoft Office 2013 で公式のパスワード解除ツールがあると聞いて

kanata が約9年前に追加

Microsoft Office 2013 で公式のパスワード解除ツールがあると聞いて
「何それ、公式で解除ツールを出してたら鍵かける意味無いじゃんwwww」
とか思ったけど、そんなことはなかった。そりゃそうだよね。。

こんな流れ

  • 事前にレジストリに公開鍵を登録しておく
  • Microsoft Office 2013 でパスワード設定
  • パスワードを失念
  • 公式のパスワード解除ツールでパスワードを解除（秘密鍵を使ってパスワード解除できる）

面白い仕組み。ただ事前に管理する全PCに公開鍵登録するのと、秘密鍵は個別に管理(漏れないように)しないと使えない。

参考

Office 2013 のファイルのパスワードを削除あるいはリセットします。
https://technet.microsoft.com/ja-jp/library/jj923033.aspx

[Office 2013]ファイルパスワードのエスクローキー機能
http://www.ka-net.org/blog/?p=2608

Word／Excelのパスワードによる保護では個人情報は守れません
http://www.atmarkit.co.jp/ait/articles/1506/16/news012.html

すみだセキュリティ勉強会2015#2に参加してきました

kanata が約9年前に追加

すみだセキュリティ勉強会2015#1 に参加以降、いくつか他の勉強会にも参加するようになりました。ありがとうございます。とても勉強になります！

  • yasulibさん
    HTTP/2のヘッダインジェクションの話。HTTP/2が実装されているサーバはまだ少ないようですが、過去HTTPで発見された脆弱性はfixしてリリースされるといいですね。初物ってリスクあるから、今後に動向に注目。

  • inaz2さん
    WinDbgキター。使ったこと無いので大変参考になりました。まずはOllyさんからですね。。ちなみに私もCUI派です。

  • ozuma5119さん
    9100番をsshdポートに使うのは初耳でした！そして突然100個のsshd!ww。木を隠すなら森方式ですね。
    良いアイデアを頂きました。

こういう方式を思いついた。実装したい。

1.ポートスキャンを検知する(snortかなぁ、netstatかssで代用できないかな。。)
2.検知をトリガにして100個のDecoy sshd(囮)を立ち上げる。バナーは全部変えるか、全部統一する。
3.攻撃者が諦めて15分くらいしたら、100個のsshは落とす。

20150829_sumida.jpg

オライリー・ジャパンの書籍全部買ったら、おいくらになるか俺の中で話題 (6コメント)

kanata が9年以上前に追加

という訳でシェル芸をしてみる。
オライリー・ジャパンは、全書籍のタイトルと価格を1ページで公開しているのですぐ計算できる。

まず、何冊有るだろう？ワンライナーでいける。

$ curl -s  http://www.oreilly.co.jp/catalog/index.html|grep price|wc -l
420

20015.8.8現在 420点

全部合計した値段はいくらだろう！？
ちょっと無理してワンライナーで書いてみた。

$ curl -s  http://www.oreilly.co.jp/catalog/index.html|grep price|cut -d'>' -f9|cut -d' ' -f1|tr -d ',th<'|tr '\n' '+'|sed -e 's/$/0/g'|cut -c2-|bc
1442988

144万2988円也

意外に、安い。ような気がする。買わんけど。

I/O 2015年8月号 が気になる

kanata が9年以上前に追加

I/Oという雑誌の存在は、なんとなく知ってはいたけど買ったことはなかった。
HackerJapanが休刊になって以来、こういうの書いてある雑誌が無かった。
欲しい。。買いかしら・・・気になる。

20150730_IO.jpg

NERV汐留支部職員に採用されました

kanata が9年以上前に追加

採用されたってことでいいよね？
よし後はもぅ両津勘吉ばりの国際公務員生活を送ってやるんだ。。

NERV汐留支部職員採用試験
http://realdgame.jp/eva2015/shiken.html

20150725_NERV.png

※CTFではなくナゾナゾです

WEB+DB PRESS総集編［Vol.1～84］ が発売される！

kanata が9年以上前に追加

WEB+DB PRESSのVol.1～84までが３千円以下で買える。
即買。
ガンジーが助走つけながら、そのまま書店に突っ込むレベル。
この前はVol1～72の総集編が出てたが、気がついたら売り切れてた。

WEB+DB PRESS総集編［Vol.1～84］ (WEB+DB PRESS plus)
http://sinkan.net/?action_item=true&asin=4774175382&aid=15339&ref=tw

20150719_panada.gif

1 ... 11 12 13 14 15 16 (121-130/153)

他の形式にエクスポート: Atom

クリップボードから画像を追加 (サイズの上限: 100 MB)