Help us understand the problem. What is going on with this article?

CTF初心者が雑に紹介するCTF ~Crypt編~

More than 3 years have passed since last update.

1. はじめに

 今回は私の好きな"CTF"というプログラミングを用いた競技に関して、少しでも知っていただければいいなと思ってこの記事を書きました。私自身ド素人のため、拙い箇所も多々あるかもしれませんが「へーこんなのあるんだ」程度に知って頂ければ幸いです。

2. 目的

 ・CTFがどんな感じのものか全く知らない方に知って頂く
 ・友達探し

3. CTFとは

CTF(Capture The Flag)とは…
コンピュータセキュリティの分野におけるキャプチャー・ザ・フラッグ(CTF)は、コンピュータセキュリティ技術の競技である。CTFは通常、参加者に対しコンピュータを守る経験に加え、現実の世界で発見されたサイバー攻撃への対処を学ぶ教育手法として企画されている。「ハッカーコンテスト」「ハッキング大会」「ハッキング技術コンテスト」「ハッカー大会」などとも訳される。

キャプチャー・ザ・フラッグ - Wikipedia

はい。
つまり情報セキュリティ技術(雑に言うとハッキング技術)を用いたプログラミング技術競技の一種です。
その中でも一般的な「問題出題型CTF」の大まかな流れとしては

  1. 情報セキュリティやその他PCに関する問題が複数出題される。

  2. 問題に添付されているファイル・サーバー・URLまたは問題文から「Flag」(旗)と呼ばれる値を見つけ出す。成功すると問題に応じてポイントが加算される。

  3. 制限時間内により多くのポイントを獲得したチームが勝ち。

といった具合です。

プログラミングを仕事または趣味とされている方の中でも、ゲーム等の開発をしている方はよくいらっしゃるのですが、情報セキュリティに関して詳しい方というのはあまり多くはないため(私の周りだけでしょうか?)、中々同士を見つけづらいのがこの分野の辛いところではあります…

4. 問題のジャンル

 実際に問題出題型のCTFで出題される問題の主なジャンルを雑にご紹介します。

[bin]問題・・・バイナリ(実行)ファイルの解析。アセンブリの知識等が要求される問題

[pwn]問題・・・プログラムの脆弱性攻撃等、世間一般で言う「ハッキングらしい」ことをする問題

[Web]問題・・・ウェブアプリケーションの脆弱性を突く等、ネット経由で[pwn]っぽいことをする問題

[Network]問題・・・ネットワークパケットの解析等、ネット通信関連の問題

[Crypt]問題・・・暗号技術に関連する問題

[Forensics]問題・・・物理的なメモリ(HDD等)のイメージファイルの解析をする問題



ジャンルを挙げれば数え切れないくらいあるのですが、まあ大体この辺が主流です。
他にも[bin]の親戚でリバースエンジニアリング技術をつかう[Reversing(rev)]問題や、画像を用いた[steg(steganography)]問題なんかもあります。

このように問題のジャンルが多種多様なため、何か一つの分野に詳しい方でも十分活躍の可能性があります。
大体のCTFの大会は制限時間付きのチーム戦のため、ジャンルで問題の担当を分け、より効率的に問題を解いていくのも一つの戦略です。問題の出題傾向や開催される大会の性質と自分の適性が上手くマッチングすると、チーム内で救いの神になれるかもしれませんね。

CTFが大体どんな感じのものか、ご理解いただけたでしょうか?

5. 実際にやってみよう

(環境はLinux kali 4.8.0-kali1-amd64 を利用しています。)

それでは、簡単なCrypt(暗号)の例を見てみましょう。
以下の暗号文をご覧ください。

SYNT{PGS_Ortvaare}

こちらの暗号文から、元の文を解読してみましょう。

これは「シーザー(カエサル)暗号」と呼ばれる換字式暗号の一種で、おそらくCTFを経験したことがなくても、ご存じの方は多いのではないでしょうか?
この暗号は、文字をアルファベット順にn文字(nは1~25の自然数 通常のシーザー暗号では13)ずらすことで成り立っています。
例えば、nを13とすると、'A'という文字はアルファベット順に13文字後にある'N'に、'b'は13文字後の'o'に変換されている、といった感じです。もし、文字をアルファベット順に後ろにずらす過程で、zまたはZを越してしまった場合は、aまたはAから再開します(例えば変換前がYなら、Y,Z,A,B,C,D,E,F,G,...,Lで暗号化前/後の値はLと言った具合)。こういった操作を回転、ローテーション(rotation,rot)と言ったりもします。

まずはC言語を使って、この暗号文を解読してみましょう。
 

rot13.c
#include <stdio.h>

int main(){

    int i,key = 13;
    char target[18] = "SYNT{PGS_Ortvaare}";
    char answer[18];

    for(i = 0; i < 18; i++){
        if(target[i] >= 'A' && target[i] <= 'Z')
            answer[i] = (target[i] - 'A' + key) % 26 + 'A';

        else if(target[i] >= 'a' && target[i] <= 'z')
            answer[i] = (target[i] - 'a' + key) % 26 + 'a';

        else
            answer[i] = target[i];
    };

    printf("Answer is %s \n" , answer);

    return 0;
}

(雑コードなのはお許し下さい(> <)。シーザー暗号の汎用性のあるエンコーダ/デコーダは読者様の使いやすいものを是非作成してみてください(丸投げ))
このプログラムをコンパイルして実行すると、以下の文が表示されます。

Answer is FLAG{CTF_Beginner}

というわけで答えが出ましたね。暗号化前の文は「FLAG{CTF_Beginner}」でした。大抵のCTFでFLAGとして用いられる値は「FLAG{...}」や「...(開催されている大会の名前等){....}」という形式を取ることが多いです。

それでは同じ問題をPythonで解いてみましょう。今回は手っ取り早く端末に'python'と入力して対話型シェルで実行してみましょう。

root@kali:~/ctf# python
Python 2.7.12+ (default, Sep  1 2016, 20:27:38) 
[GCC 6.2.0 20160927] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import codecs
>>> codecs.decode('SYNT{PGS_Ortvaare}','rot13')
'FLAG{CTF_Beginner}'

はい、私、ズルをしました。実際私が入力したのは上記のうち、'python'と'>>>'後の二行だけです。
種明かし(というほどのものではありませんが)をすると、Pythonには標準でシーザー暗号(n=13の場合)を解く機能(rot13)が備わっている、ということです。
このように、PythonはCTFをする上で非常に楽な言語の一つであるということです。(勿論他に自分にとってやりやすい言語があるなら、それでも全然OKですが)Pythonには面倒な処理を請け負ってくれる多種多様なライブラリが存在し、最近では機械学習や科学技術計算等にも用いられています。私個人としては非常におすすめしたい言語の1つです。

それでは、有名なCTFの一つ、「SECCON CTF 2016」で実際に出題された問題を解いてみましょう。

SECCON 2016 オンライン予選より
[Crypt]Vigenere

k: ????????????
p: SECCON{???????????????????????????????????}
c: LMIG}RPEDOEEWKJIQIWKJWMNDTSR}TFVUFWYOCBAJBQ

k=key, p=plain, c=cipher, md5(p)=f528a6ab914c1ecf856a1d93103948fe

問題文のkはkey(鍵の意 さっきの例で言うnですね)、pはplain(プレーンテキスト 暗号化前の文のことです)、cはcipher(暗号文)を意味します。md5は確認用のハッシュ値ですね。(これに関して書くと長くなるので省略しますが、簡単に言うと正解として導き出されるpの値が正しいかをどうかをこいつを使うことで確認できます)

というわけでこちら、問題名にも書いてありますが「Vigenere(ヴィジュネル)暗号」という換字式暗号の一種です。(先程のシーザー暗号の仲間ですね)

ヴィジュネル暗号-Wikipedia

15~16世紀にフランスの外交官だったヴィジュネルさんが考えた暗号というわけです。

ヴィジュネル暗号とは、一体どのようなものなのでしょうか?
下の表を御覧下さい。横軸が平文(暗号化前の文)で、縦軸が鍵(key)です。
例として、平文を"CTFCTF" 鍵を"ABCD"としてみましょう。

 |ABCDEFGHIJKLMNOPQRSTUVWXYZ{} 
-+----------------------------
A|ABCDEFGHIJKLMNOPQRSTUVWXYZ{}
B|BCDEFGHIJKLMNOPQRSTUVWXYZ{}A
C|CDEFGHIJKLMNOPQRSTUVWXYZ{}AB
D|DEFGHIJKLMNOPQRSTUVWXYZ{}ABC
E|EFGHIJKLMNOPQRSTUVWXYZ{}ABCD
F|FGHIJKLMNOPQRSTUVWXYZ{}ABCDE
G|GHIJKLMNOPQRSTUVWXYZ{}ABCDEF
H|HIJKLMNOPQRSTUVWXYZ{}ABCDEFG
I|IJKLMNOPQRSTUVWXYZ{}ABCDEFGH
J|JKLMNOPQRSTUVWXYZ{}ABCDEFGHI
K|KLMNOPQRSTUVWXYZ{}ABCDEFGHIJ
L|LMNOPQRSTUVWXYZ{}ABCDEFGHIJK
M|MNOPQRSTUVWXYZ{}ABCDEFGHIJKL
N|NOPQRSTUVWXYZ{}ABCDEFGHIJKLM
O|OPQRSTUVWXYZ{}ABCDEFGHIJKLMN
P|PQRSTUVWXYZ{}ABCDEFGHIJKLMNO
Q|QRSTUVWXYZ{}ABCDEFGHIJKLMNOP
R|RSTUVWXYZ{}ABCDEFGHIJKLMNOPQ
S|STUVWXYZ{}ABCDEFGHIJKLMNOPQR
T|TUVWXYZ{}ABCDEFGHIJKLMNOPQRS
U|UVWXYZ{}ABCDEFGHIJKLMNOPQRST
V|VWXYZ{}ABCDEFGHIJKLMNOPQRSTU
W|WXYZ{}ABCDEFGHIJKLMNOPQRSTUV
X|XYZ{}ABCDEFGHIJKLMNOPQRSTUVW
Y|YZ{}ABCDEFGHIJKLMNOPQRSTUVWX
Z|Z{}ABCDEFGHIJKLMNOPQRSTUVWXY
{|{}ABCDEFGHIJKLMNOPQRSTUVWXYZ
}|}ABCDEFGHIJKLMNOPQRSTUVWXYZ{

・平文の一文字目はC、鍵の一文字目はAなので、上の表で横軸の値をC、縦軸の値をAとすると表の指す値(交差する点)はCであり、暗号文の一文字目はCとなります。

・同様に、平文の2文字目はT、鍵の2文字目はBなので、横軸はT、縦軸はBに設定すると表の指す点(交差する点)はUのため、暗号文の2文字目はUとなります。

・操作の過程で鍵が最後の文字に到達してしまったら、その次はまた鍵の一文字目に戻る「回転」をして下さい。

・このようにして暗号文を作ると、暗号文は"CUHDTG"になります。

・暗号文と鍵から平文を求めたい場合は、鍵の1文字目がある行から暗号文の1文字目を探し、その文字がある列の横軸の値が平文の1文字目・・・といった具合にすれば良いわけです。

はい。というわけで非常に雑な解説ではありましたが、だいたいどんな感じかはご理解頂けたでしょうか?

それでは問題に戻ります。
平文を求めろ!という問題なのだろうと推測されますが肝心の鍵が12文字であるといったヒントしか与えられていません。しかし、平文の最初の方の文字が示されていますね。ここからある程度鍵を求めることができそうです。上と似たような方法で行きましょう。

平文の1文字目はSですから、横軸のSと同じ列から暗号文の1文字目であるLを探すと、その時の横軸の文字はV、となるので鍵の一文字目はVですね。同様の操作を平文が明らかになっているところと推測を使って求めると、鍵は
"VIGENERE????"
となりそうです。鍵が全てわからない限りは、平文の全容は明らかになりませんから残りの4文字は推測してみましょうか。(高々4文字、しかも28^4=614656通り程度なら総当りか辞書で求めてみても良い気はしますが・・・)実際に私がこれを解いたときは推測がたまたま当たり、なんとか正解できました。それでは、なんかそれっぽい値として"CODE"の4文字を鍵に入れて、実際に解読用のプログラムを書いてみましょうか。

vigenere.py
#! /usr/bin/env python
# -*- coding: utf-8 -*- #

key='VIGENERECODE'

cycle='ABCDEFGHIJKLMNOPQRSTUVWXYZ{}'

target='LMIG}RPEDOEEWKJIQIWKJWMNDTSR}TFVUFWYOCBAJBQ'

result = ''


for n in range(0, len(target)):


    index1 = 28 - cycle.find(key[n%12])
    index2 = cycle.find(target[n])
    index = index1 + index2

    if index >= 28:
        index = index % 28

    result = result + cycle[index]

    n = n + 1

print result

これを実行すると

SECCON{ABABABCDEDEFGHIJJKLMNOPQRSTTUVWXYYZ}

と表示されますね。それでは、この値のmd5値を求めてみましょう。この処理にもPythonを使ってみます。

root@kali:~/ctf# python
Python 2.7.12+ (default, Sep  1 2016, 20:27:38) 
[GCC 6.2.0 20160927] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import hashlib
>>> print hashlib.md5('SECCON{ABABABCDEDEFGHIJJKLMNOPQRSTTUVWXYYZ}').hexdigest()
f528a6ab914c1ecf856a1d93103948fe
>>>

というわけで、出力されたmd5値が問題文のmd5値と一致したため、FLAGは

SECCON{ABABABCDEDEFGHIJJKLMNOPQRSTTUVWXYYZ}

で間違いないようです。普通、FLAGの{}の中身はもっとわかりやすい文や単語などになるのですが、ちょっと正解感のない(?)FLAGですね。だからわざわざmd5値を用意してくれたのかもしれませんが・・・また、通常のVigenere暗号の表は縦軸横軸両方ともA~Zで構成されており、{ }は存在しません。通常のVigenere暗号のエンコーダ/デコーダはちょっとググれば出てくるのですが、この問題の場合は、表において{ }がアルファベットの後に追加されているため、恐らく役に立ちません。既存のものに依存しないでしっかり自分でコードを書けよ、というSECCON運営さんからのメッセージかもしれませんね。
最後は本当のズルをしましたが、CTFの問題を解く流れはだいたいこんな具合です。

6. 終わりに

 非常にダラダラと冗長で雑な記事を書いてしまいました。最初にも述べたとおり、私自身ド素人なので技術的な面や記事の書き方の面で拙い箇所も多々あったかと思いますので、よりスマートな解法、より読みやすい記事のためのアドバイス等はDMやリプ、コメント等で随時受け付けております。他にも、「この記事を読んでCTFに興味を持った!」「私がCTFマスターだ。力が欲しいか・・・?」という方のコメントを頂けると昇天して喜びます。

 また、これから先のCTF関連の記事に関してですが、今回の記事の反省等を元に私自身勉強して、記事がかけるレベルになったらまた投稿してみようかなあ・・・程度に考えています。私の好きな[pwn]問題に関しても記事を書いてみたいと考えてはいるのですが、如何せん内容が完全に悪用可能な知識(ハッキングというか不正アクセスのやり方、またはそれに近い知識)になってしまうので、その辺の法律やら免責やらに関してもう少し調べてから検討したいです・・・。そんなん解説してるサイトいくらでもあるじゃんというツッコミは無しで・・・

というわけで、ここまで長々とお付き合い頂き、有難う御座いました。

 

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away