Crypto 100

CTFって何？という話もあるので、一つ例題と解説掲載してみまうす。今年のカテゴリーは「Pursuits Trivial：トリビア問題」、「Crypto Badness：暗号解読」、「Packet Madness：パケット解析」、「Binary L33tness：バイナリ解析」、「Pwtent Pwnables：リモートexploit」、「Forensics：フォレンジックス」という感じなんだけど、その中で最初に出てきた簡単レベルな問題Cryptoの100について、ルヒーさんが経過書いている（http://d.hatena.ne.jp/Luffy/20090619#p1）ので、あっしも自分の思考経過をまとめておこうと思って書いてたの晒しておこうｗ。てか実質この問題くらいだもんなーちゃんと関与でけたのって。

Crypto100の問題は以下のとおり。

ASI JL DUJZTED SA J EJZD JVV NBTODI, VDD FOD AHB VBFD:

OFFT://YYY.AHB.MSK/TJMD2/CDN08/NSCD_122908.OFZE, PSQD GSW
MWDVV? LS, JNFWJE AHB RWBX.

これを見たら簡単に思いつくのは、
・OFFTのところは、これはURLだろ
ということですね。
で、そういうのをとにかくサクサク当てはめていく作戦に出てみます。

OFFT＝http
YYY＝www

まずはこのあたりが堅そうですね。
実際のアルファベットの方（小文字）を基軸として考えてみます。
h=O（置き換えは逆で、O→hと置換します）
p=T
t=F
w=Y
これを実際に置き換えてみると、

ASI JL DUJZpED SA J EJZD JVV NBphDI, VDD thD AHB VBtD:

http://www.AHB.MSK/pJMD2/CDN08/NSCD_122908.htZE, PSQD GSW
MWDVV? LS, JNtWJE AHB RWBX.

となります。ここで見えてきたのが「thD」で、D→eと推測されますね。あとはちょっと冒険ですが、「J」と1文字で出ているのは英語的には「a」ではないかと思われます。これも置き換えてみましょう。
a=J
e=D

ASI aL eUaZpEe SA a EaZe aVV NBpheI, Vee the AHB VBte:

http://www.AHB.MSK/paMe2/CeN08/NSCe_122908.htZE, PSQe GSW
MWeVV? LS, aNtWaE AHB RWBX.

またいろいろ見えてきましたね。まず、1行目の「Vee」ですが、そのあとの「VBte」と合わせると「V」はおそらく「s」で、ついでに「B」は「i」じゃないかと推測されますね。あと、URL内にある「paMe2」から、「M」は「g」じゃないかと思われますし、URL最後の「htZE」も「html」じゃないでしょうか。ちょっと飛躍気味ですが（笑）、これも置き換えてみます。
g=M
i=B
l=E
m=Z
s=V

ASI aL eUample SA a lame ass NipheI, see the AHi site:

http://www.AHi.gSK/page2/CeN08/NSCe_122908.html, PSQe GSW
gWess? LS, aNtWal AHi RWiX.

ここまででアルファベット26文字のうち11文字まで当てはめることができました。
また見えてきたことをもとに推測してみます。
「eUample」を見ると、「U」が「x」
その前の「aL」を見ると、「L」が「n」
ちょっと怪しい気がしますが「NipheI」は「cipher」？
あと「gWess」を見れば「W」は「u」
URLの中の「gSK」はたぶん「gov」でしょう。
c=N
n=L
r=I
u=W
o=S
v=K
x=U

Aor an example oA a lame ass cipher, see the AHi site:

http://www.AHi.gov/page2/Cec08/coCe_122908.html, PoQe Gou
guess? no, actual AHi RuiX.

だいぶ見えてきましたね。18文字クリアです。
さらに、「Aor」と「oA」を見ると、「A」は「f」
URLの中の「Cec08」と「coCe」を見ると、「C」は「d」
「Gou」から「G」は「y」
ここまでまた置き換えてみます。
d=C
f=A
y=G

for an example of a lame ass cipher, see the fHi site:

http://www.fHi.gov/page2/dec08/code_122908.html, PoQe you
guess? no, actual fHi RuiX.

さて、あと一つわかればURLは判明しますが、gov＝連邦政府ドメインでfHiという三文字で特定するなら、fbiっぽいですね。b=H
これで22文字でしょうか。

for an example of a lame ass cipher, see the fbi site:

http://www.fbi.gov/page2/dec08/code_122908.html, PoQe you
guess? no, actual fbi RuiX.

URLがわかりましたね。
ちょっと整理してみましょう。
a=J
b=H
c=N
d=C
e=D
f=A
g=M
h=O
i=B
j=
k=
l=E
m=Z
n=L
o=S
p=T
q=
r=I
s=V
t=F
u=W
v=K
w=Y
x=U
y=G
z=
あと4文字ですねー。で、文章の中で残るのは、「PoQe」と「RuiX」のまさに4文字です。どれも1文字ずつなので英語の意味を推測しながら当てはめるしかなさそうです。
残っている文字が「j」「k」「q」「z」ですが、まず「RuiX」を見るとおそらく「R」は「q」でしょう。とすると「X」は「z」、残りから推測して「PoQe」は「joke」であるように思えますね。

for an example of a lame ass cipher, see the fbi site:

http://www.fbi.gov/page2/dec08/code_122908.html, joke you
guess? no, actual fbi quiz.

簡単に訳してみます。

くそひどい暗号の例を見るなら、FBIのサイトを見てみろ。
http://www.fbi.gov/page2/dec08/code_122908.html
冗談かと思うだろ？違うんだ。これは現実に行われたFBIのクイズなんだ。

酷い言いようですね（苦笑）。

対応表を完成させましょう。
a=J
b=H
c=N
d=C
e=D
f=A
g=M
h=O
i=B
j=P
k=Q
l=E
m=Z
n=L
o=S
p=T
q=R
r=I
s=V
t=F
u=W
v=K
w=Y
x=U
y=G
z=X

さて、ここで気になるくそひどいFBIのクイズを見てみましょう（笑）。

VFWTDLCSWV. YD
NSLMIJFWEJFD GSW SL
NIJNQBLM FOBV EJFDVF
DLNIGTFBSL. KBVBF
YYY.AHB.MSK/NSCDC.OFZ
FS EDF WV QLSY SA
GSWI VWNNDVV.

YYY.AHB.MSK/NSCDC.OFZというあたりが超見覚えありますね（笑）。というわけで、同じ置き換えじゃないかなと思われるので、置換してみます。

stupendous. we
congratulate you on
cracking this latest
encryption. visit
www.fbi.gov/coded.htm
to let us know of
your success.

これも簡単に訳してみます。

すばらしい。
この最新暗号をあなたが解けたことをお祝いします。
www.fbi.gov/coded.htmを訪れて、あなたが解読に成功したことをわれわれにお知らせください。

なるほど。
確かにちょっと酷いなって思うのは、アルファベットが全部出てこないところでしょうかね（笑）。「z」や「x」「j」「q」というところが出てこない。これは解読する側としては少し辛いところですねー。まーでも単語が想像できる＝語彙が豊富な人にとっては大きな問題ではないかも知れません。

ついでにうんちくを書いておきますと、こういう暗号文を解読するときは、TIPSとでも言うべき英語の性質を知っていると便利です。例えば、「母音は頻出してくるので、母音から行くと効率が良い」「母音の他に頻出するのは「s」「t」「n」「r」あたり」「1文字、2文字の単語は限定的なので、推測しやすい」などなど。このあたりは「頻度解析」という古典的な英文暗号の解析手法に詳しいのですが、そういう知識が少しだけでもあると、ただ眺めるのとは異なり、分析的に見ることができるので良いのではないでしょうか。
ちなみにそういう話はこの本の最初の方に出てきますね。

暗号解読（上） (新潮文庫)

暗号解読 下巻 (新潮文庫 シ 37-3)

あと、各言語の頻度解析（分析）について具体的に例が載ってるのは、

暗号事典

ですね。チャーチハウス著の「Code and Ciphers」という本からの引用なんですが、英語、フランス語、ドイツ語、イタリア語、ウェールズ語の頻度表が掲載されてます。
ってかこれらの本はおもろいよー。

で、肝心の回答なんですが、
a=J
b=H
c=N
d=C
e=D
f=A
g=M
h=O
i=B
j=P
k=Q
l=E
m=Z
n=L
o=S
p=T
q=R
r=I
s=V
t=F
u=W
v=K
w=Y
x=U
y=G
z=X
これを大文字側をキーにしてアルファベット順ソートした文字列、fideltybravngchjkqopxsuzwmでした。つまり、もとの英語の文章をあぶりだすのに使った「逆変換」をアルファベット順ソートした文字列、ということですね。
って実は、この正解に至る前にも、例えば「Hack the planet!」的なDEFCONのCTF的常套句を変換してみたりとか、そんな感じのトライを何度もやってみたりしたんだけど、どれもダメで、結局もっともシンプルにアルファベット変換という結論にたどり着くまで少し暇が要ってしまいました。このあたりの発想についても分析できたらなーって思ってます。

今年のCTF関連情報は、てっしーさんとこに詳しいですね＞http://d.hatena.ne.jp/tessy/20090617/1245232700、あとこのへんとかhttp://d.hatena.ne.jp/tessy/20090618/1245316776
全体的な概要と例題について、愛甲先生のプレゼンもあるよ。
http://07c00.com/a.pdf