Sunday, April 13, 2014

PlaidCTF2014 Write Up: Twenty (Crypto20)

Ini adalah soal kategori kriptografi, seperti biasa kita diberi ciphertext dan diminta untuk men-dekrip menjadi plaintext.

Berikut adalah deskripsi soalnya:

It's so far in the past, computers haven't even been imagined, let alone used. But somehow The Plague has already been here, building an evil army of hackers. Can you find his secret message?

Ciphertext yang diberikan adalah:

fvoxoxfvwdepagxmwxfpukleofxhwevefuygzepfvexwfvufgeyfryedojhwffoyhxcwgmlxeylawfxfurwfvoxecfezfvwbecpfpeejuygoyfefvwxfpwwfxojumwuxfuffvwawuxflecaazubwjwoyfvwyepfvwuxfhwfjlopwckaohvfjlzopwoaahevupgwpfvuywjoywjdwyfufjupouvbuaajwuaoupkecygjwoyfvwuxxdofvyeacmwbvuzoyhlecpwzcbroyhdofvfvwgcgwdveheffvwrwlxfelecpxuzwuygfvexwfvufbuyfgempoyhxcofxbplfelecpcybawxujfexwffawgoxkcfwxfvechvflecgfubrawfvoxdofvuaoffawjepwfubfmcffvwyuhuoyzcghwkubrwpxogeyfryediubroxvwgufwupwswplfojwofvoyrezaorxuyhmcfxvofjuyfvwlpwubepkepufoeyuygojukwpxeyozobufoeyezzpwwgejzepuaaleczoaagebrwfxaorwfvufxubeybwkfzepwohyfeluaadvoawaudlwpxjcggldufwpuygfpexxfuaaecfezmcxoywxxoxiuoazepjwuyglecpwxcoyhjwbosoaalwnvomoffvoxoyfvwbecpfpeejheeygeofogupwlecbeyhpufcaufoeyxfvwzauhoxxoybwywdbplkfejohvfvuswyxumubrgeepxocxweagbplkfe

Kalau dilihat sepintas ada banyak pola dan perulangan huruf, ini adalah ciri dari substitution atau shift cipher.

Saya menggunakan tools substitution cipher solver yang menggunakan algoritma hill climbing untuk mencari kunci. Hill climbing adalah salah satu algoritma optimasi dan dekripsi adalah salah satu problem optimasi. Skor optimasi diukur berdasarkan kemiripan hasil dekripnya dengan teks bahasa inggris yang dilihat dari statistik 4-gram. Bila hasil dekripsinya banyak mengandung 4 huruf (THEY, HAVE,TION dsb) yang banyak ditemukan dalam bahasa inggris, maka skornya akan tinggi, semakin tinggi skor berarti semakin mendekati ke kunci yang benar. Bila skor masih rendah, kita akan mencari kunci lain dengan mengubah sedikit kunci sebelumnya agar skornya semakin tinggi.

Dalam waktu singkat hill climbing berhasil menemukan kunci substitusinya.









No comments:

Post a Comment