SECCON 2016 オンライン予選
12月10日(土) 15：00から 12月11日(日) 15：00(日本時間)にかけて、SECCONオンライン予選2016が開催されました。
私も参加して結果は2問200点でした。そこ、去年と同点ｗｗｗとか言わないで～
挑んでみたら、先日の練習問題その１とそっくりな問題が出てビックリしたのは内緒。
（練習問題その２は本編には全く出なかったけれど、興味がある人はどうぞ。）
それでは早速writeupを書いていこう。
※練習問題その1とよく似た問題？のVigenere 100のWriteupはこちら
※WireSharkの意外な使い方が身につくVoIP 100のWriteupはこちら
※エンコード方式に敗北したAnti-Debugging 100の考察はこちら
※Vigenere 100とそっくり？な練習問題その１を解いてみたい方はこちらからどうぞ。
※本編には全く出なかったけれど、練習問題その２もあるので興味がある人はこちらからどうぞ。
Vigenere 100
最初の問題。問題文は以下の通り。便宜上、矢印（←）と数字を3つ追加している。
Vigenere
k: ????????????
p: SECCON{???????????????????????????????????}
c: LMIG}RPEDOEEWKJIQIWKJWMNDTSR}TFVUFWYOCBAJBQ
k=key, p=plain, c=cipher, md5(p)=f528a6ab914c1ecf856a1d93103948fe
|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{ ←３
Vigenere cipher
https://en.wikipedia.org/wiki/Vigen%C3%A8re_cipher
何やら怪しげな対応表がついているが。。。どうやら先日の記事で書いた暗号問題と同じ雰囲気がする。
「Vigenere cipher」で検索調べてみると平文pに対して鍵kを使って暗号文cを作成する暗号の用だ。
上の表の１の行が平文の文字、２～３までの行の一番左の文字が鍵になっているとのこと。
つまり、平文がB、鍵がCなら平文がBとなっている2列目、鍵がCとなっている行の交差するところに暗号化された文字が書いてある。
//一部抜粋 ↓ |ABCDEF //平文の行 ここからBは左から2文字目なので、鍵の行の2列目が暗号化した文字。 -+------ A|ABCDEF B|BCDEFG C|CDEFGH //←Cの行。この行の中から該当の文字を探す。今回は左から2列目なので「D」となる。 D|DEFGHI
実際には鍵は1文字ではなく複数文字あり、平文のn文字目は鍵のn文字目で暗号化されている。
ただし、平文の長さ ＞＝ 鍵の長さなので、平文の文字数が鍵の文字数を超えたら鍵は先頭から再利用する。
例えば平文が ABCDEFG、暗号がXYZであれば、
平文Aは鍵X、平文Bは鍵Y、平文Cは鍵Zで暗号化され、平文Dは鍵Xで暗号化される。（以下、EがY、FがZ、GがX）
このルールに基づいて考えると鍵の先頭7文字は平文と暗号文から復号出来て「VIGENER」となる。
鍵の推測
文字数の推測
鍵の先頭7文字はわかったが、その後の平文がわからず、鍵の文字数もわからない。そこで、まずは鍵の文字数の推測を試みる。
最後の文字を複合すると鍵は「R」となる。偶然にもこのRはすでに復号した鍵の中に入っている。
最後の文字は43文字目、すでに復号された鍵は7文字なので、仮に鍵にRが1文字しか入っていないと仮定すると鍵の周期は43-7＝36の約数ということになる。
もう少し詳しく書くと↓の通り。
//鍵が7文字の場合
VIGENER VIGENER VIGENER VIGENER VIGENER VIGENER V //鍵
SECCON{ ??????? ??????? ??????? ??????? ??????? } //平文
LMIG}RP ??????? ??????? ??????? ??????? ??????? J //鍵と平文から作った暗号文
LMIG}RP EDOEEWK JIQIWKJ WMNDTSR }TFVUFW YOCBAJB Q //実際の暗号文、一番最後の文字が一致しないため鍵は7文字ではない
最後の文字をQにするためには、鍵のRが43文字目に来る必要がある。鍵の中にRが1度しか使われていないと仮定すると、以下のようになる。
//鍵が?文字の場合
VIGENER ??????? ??????? ??????? ??????? ?VIGENE R //鍵
SECCON{ ??????? ??????? ??????? ??????? ??????? } //平文
LMIG}RP ??????? ??????? ??????? ??????? ??????? Q //鍵と平文から作った暗号文
LMIG}RP EDOEEWK JIQIWKJ WMNDTSR }TFVUFW YOCBAJB Q //実際の暗号文、最後の文字が一致
最後のVIGENEの手前までで36文字となる。鍵の中にRが1文字と仮定すると、鍵の文字数をX倍するとぴったり36にならなければならない。
そうでなければ最後がRにならない。
すると、鍵の文字数は36の約数の「1 2 3 4 6 9 12 18 36」に限られる。
ここで、すでに鍵の文字数は７文字以上なので可能性があるのは「9 12 18 36」の４つとなる。
VIGENER?????
さすがに36文字の鍵は考えづらい。ここでもう一度鍵を見てみると、「VIGENER」となっている。
最後にeを足すと「VIGENERE」となるのでおそらく8文字目はEだと推測。
すると、残り1文字とは考えにくいので鍵は「12」文字か「18」文字と推測。
ひとまず12文字だと仮定して続けることにする。
ここまでをまとめて以下のように復号。なお、解答はすべて大文字だが、以下追加で推測した部分は小文字で書く。
//鍵が12文字の場合
VIGENERe???? VIGENERe???? VIGENERe???? VIGENER //鍵
SECCON{????? ???????????? ???????????? ??????} //平文
LMIG}RPEDOEE WKJIQIWKJWMN DTSR}TFVUFWY OCBAJBQ//鍵と平文から作った暗号文
一部復号
//鍵が12文字の場合
VIGENERe???? VIGENERe???? VIGENERe???? VIGENER //鍵
SECCON{a???? bcdedefg???? klmnopqr???? vwxyyz}//平文
LMIG}RPEDOEE WKJIQIWKJWMN DTSR}TFVUFWY OCBAJBQ//鍵と平文から作った暗号文
残りの文字の推測 前半
ここまで解けたが、まだ鍵の残り4文字の値がわからない。が、よくよく見ると平文がアルファベット順（ABC・・・XYZ）に並んでいるように見える。
最初のaの5文字後にbが来ていたり、最後がxyyzとなってyがかぶっていたりと、一部崩してありそうだが、これで推測はできる。
平文のrとvの間には4文字あるが、ここに入るアルファベットはs,t,uの3文字。cdedefのように反復が起こると、4文字では入りきらない。xyyzのようにアルファベットがかぶっている可能性を考えても、rとvの両方を加えると5文字になってしまう。そのため可能性があるのは以下の5パターンと推測。
rstu stuv sstu sttu stuu
5パターン中4パターンは初めの文字がs、同じく5パターン中4パターンは最後の文字がuになっている。そこで、平文はs??uとなっていると推測し鍵を復号してみると該当箇所はc??eとなった。ここまでをまとめて以下のようになった。
//鍵が12文字の場合
VIGENEREc??e VIGENEREc??e VIGENEREc??e VIGENER //鍵
SECCON{A???? BCDEDEFG???? KLMNOPQRs??u VWXYYZ}//平文
LMIG}RPEDOEE WKJIQIWKJWMN DTSR}TFVUFWY OCBAJBQ//鍵と平文から作った暗号文
ここから追加で得られた鍵をもとに平文を復号し以下を得た。
//鍵が12文字の場合
VIGENEREc??e VIGENEREc??e VIGENEREc??e VIGENER //鍵
SECCON{Ab??a BCDEDEFGh??j KLMNOPQRs??u VWXYYZ}//平文
LMIG}RPEDOEE WKJIQIWKJWMN DTSR}TFVUFWY OCBAJBQ//鍵と平文から作った暗号文
残りの文字の推測 後半
アルファベット順だとすると、ここから先は絞り込みの数もそう多くない。総当たりで復号を試みる。
そこで前半部分のab??aの部分に注目する。この間に入るのはaとbの2種類しか考えられない。可能性があるのは以下の4パターンとなる。
aa ab ba bb
それぞれのパターンで鍵を復号してみると以下のようになった。
aa -> oe -> VIGENEREcoee ab -> od -> VIGENEREcode ba -> ne -> VIGENEREcnee bb -> nd -> VIGENEREcnde
この時点で2番目の以外は意味不明だったので、鍵は「VIGENERECODE」であると断定、平文の復号を試みる。
//鍵が12文字の場合
VIGENERECodE VIGENERECodE VIGENERECodE VIGENER //鍵
SECCON{AbabA BCDEDEFGHijJ KLMNOPQRSttU VWXYYZ}//平文
LMIG}RPEDOEE WKJIQIWKJWMN DTSR}TFVUFWY OCBAJBQ//鍵と平文から作った暗号文
これで鍵「SECCON{ABABABCDEDEFGHIJJKLMNOPQRSTTUVWXYYZ}」を得た。
解答
以上から
SECCON{ABABABCDEDEFGHIJJKLMNOPQRSTTUVWXYYZ}
となった。これをさっそく入力・・・すると、不正解、だと・・・？？
と思って5分後によく見てみると解読ミスで・・・PQRSSTU・・・としていたことが発覚。該当箇所を直して解答し無事100 pointsを獲得。
よく見たら、鍵のところが????????????となっていて12文字になっていたのは内緒。だ、だって文字数 = 鍵の文字数だなんて書いてなかったんだもんね！うっかり見落としてたんじゃないんだからね！！
以下、次回に続く。
SECCON2016関連記事
