ABCTF(2016) Writeup - 知ることはたのしい

チームのみんなが強く、ひよっこの僕はほとんど眺めてたABCTFですが

解けた問題もあるので、そのWriteupを（僕と同じくらい入門者な人向けに）書いてみます。

そのまえに、CTF wo SuruのチームメンバーのWriteupがこちらになります。

https://kimiyuki.net/blog/2016/07/23/abctf-2016/ @ki6o4

https://tsunpoko.github.io/abctf2016/ @No___Op

http://yuelab82.hatenablog.com/entry/2016/07/24/042028 @yue_roo

http://junk-coken.hatenablog.com/entry/2016/07/24/030423 @junk_coken

AES Mess - 75

AES-ECB方式で暗号化されたflagと、flagを暗号化した時に使った鍵と同じもので暗号化した、偽物のflagを多数並べたtxtファイルが与えられ、それを用いて元のflagの平文を求める問題です。 AES暗号とは共通鍵暗号の一種で、ブロック暗号でもあります。

AES-ECBでの暗号化は平文を決まった長さ(128bit)のブロックという単位に分け、分けたブロックそれぞれを鍵で暗号化します。

そのため、同じ鍵で暗号化する際、ブロックの内容が同じであれば、暗号文も同じになります。今回はその事実を使う問題でした。

復号するflagがこちら(見やすさのためにブロック単位で改行してあります)
e220eb994c8fc16388dbd60a969d4953
f042fc0bce25dbef573cf522636a1ba3
fafa1a7c21ff824a5824c5dc4a376e75

そして偽物のflagの暗号文と同じ部分をピックアップすると abctf{looks_like_gospel_feebly}:
e220eb994c8fc16388dbd60a969d4953
6d896bd7d6da9c4ce3eac5e4832c2f64

abctf{verism_evg_you_can_break_ajugas}:
528c30c67c57968fa131684d07c1fa9c
f042fc0bce25dbef573cf522636a1ba3
c0bd6ceeec8e817f1be7b09a9a8b0fb8

abctf{eocene_fazes}:
b58b970036b3a521a314d06f1436863e
fafa1a7c21ff824a5824c5dc4a376e75

これをつなげてあげると abctf{looks_like_you_can_break_aes}になります。

~~なぜ、平文16byteに対して、暗号文が32byteになっているのかは、すみませんよくわからないです・・・。~~ ~~16byteに満たないブロックは何かで埋めているみたいなんですが。~~
追記：教えてもらったところ、暗号文は16進数表記になっていて2文字で1組となるため暗号文も16byteのままでした。

The Big Kahuna - 120

"massivegargantuanhugeepicginormous"から "tinysmallmicroscopicinvisible"へのレーベンシュタイン距離(編集距離)を求める問題でした。

レーベンシュタイン距離というのは文字列Aから文字列Bへ変換する際に、追加、削除、(置換)の処理を1文字単位で行った時の最小のステップ数です。

置換を許す場合と許さない場合とがあるのですが、今回は問題で置換も含まれていました。

アルゴリズムはWikipedia レーベンシュタイン距離を参照してください。

このソースコードを実行すると28が得られ、abctf{28}というのがflagになります。

def list_init(s1, s2, l):
    for i in range(len(s1)+1):
        l[i][0] = i
    for i in range(len(s2)+1):
        l[0][i] = i

def edit_distance(s1, s2):
    distance_list = [[0 for i in range(len(s2)+1)] for j in range(len(s1)+1)]
    list_init(s1, s2, distance_list)
    
    for i in range(1, len(s1)+1):
        for j in range(1, len(s2)+1):
            #replace is allowed
            rp = 0 if s1[i-1] == s2[j-1] else 1
            n = distance_list[i-1][j] + 1
            m = distance_list[i][j-1] + 1
            l = distance_list[i-1][j-1] + rp
            distance_list[i][j] = min(n, m, l)
    return distance_list[i][j]


if __name__ == "__main__":
    str1 = "massivegargantuanhugeepicginormous"
    str2 = "tinysmallmicroscopicinvisible"
    print edit_distance(str1, str2)

今回はこれくらいしかできませんでしたが、

今後はもっと解けるように頑張ります。