34C3 Junior CTF: dotr

問題

問題文

I implemented some crypto and encrypted my secret: 03_duCbr5e_i_rY_or cou14:L4G f313_Th_etrph00 Wh03UBl_oo?n07!_e

Can you get it back?

問題概要

暗号化処理をする Python3 スクリプトと暗号文が与えられる。

平文を復号せよ。

解答例

指針

• 復号処理するプログラムを作成し Bruteforce する。

解説

与えられた Python3 コード内に登場する zip および soretd という関数について説明する。

zip 関数

zip は複数のシーケンスに同時にアクセスする for ループを作るのに役立つ関数である。

引数に複数のシーケンスを指定すると、もとのシーケンスの同じ位置にある要素を組みとしたタプルを要素とするリストを返す。

>>> A = [2, 5, 1, 4, 3]
>>> B = [9, 8, 7, 6]
>>> zip(A, B)
[(2, 9), (5, 8), (1, 7), (4, 6)]
>>> for (x, y) in zip(A, B):
        print x, '+', y, '=', x+y


2 + 9 = 11
5 + 8 = 13
1 + 7 = 8
4 + 6 = 10

引数の要素数が異なる場合は短いものに揃えられることも確認できる。

zip 関数は辞書オブジェクトを作成するのにも役立つ。

>>> C = list("abcde")
>>> C
['a', 'b', 'c', 'd', 'e']
>>> dict(zip(A, C))
{1: 'c', 2: 'a', 3: 'e', 4: 'd', 5: 'b'}

ちなみに Python3 では zip の戻り値はリストではなくイテレータに変わっている。

>>> A = [1,2,3,4,5]
>>> B = list("ABCDE")
>>> zip(A, B)
<zip object at 0x6ffffe36f88>
>>> list(zip(A, B))
[(1, 'A'), (2, 'B'), (3, 'C'), (4, 'D'), (5, 'E')]

sorted 関数

sorted 関数はオブジェクトをソートしたものを返す関数である。オブジェクトの各要素が複数の要素からなる場合、各要素の1番目を基準にソートをする。

>>> sorted(zip(A, B))
[(1, 7), (2, 9), (4, 6), (5, 8)]

各要素の2番目を基準にソートをしたければ次のようにする。

>>> sorted(zip(A, B), key=lambda x: x[1])
[(4, 6), (1, 7), (5, 8), (2, 9)]

key に指定されている lamda x: x[1] はオブジェクトの2番目の要素を返す無名関数である。

>>> a = lambda x: x[1]
>>> a((3,3,4))
3

以上の知識を前提に Python3 のコードを読んでいく。

プログラムを読む

与えられた Python3 コードは以下の様なものである。

import random


def encrypt(msg, key):
    keylen = len(key)
    k = [x[1] for x in sorted(zip(key[:keylen], range(keylen)))]

    m = ''
    for i in k:
        for j in range(i, len(msg), keylen):
            m += msg[j]

    return m



m = input()
while True:
    k = [random.randrange(256) for _ in range(16)]  # generate 2 keys
    if len(k) == len(set(k)):
        break

m = encrypt(m, k[:8])
m = encrypt(m, k[:8])

print(m)

while 文の中で 16文字の相異なる 0~255 のランダムな整数 16 個で構成されるリストが生成されている。

生成されてたリストのうち前半の8つが関数 encrypt() に key として渡されている。

def encrypt(msg, key): の処理では、まず k というリストが生成されている。 k は range(len(key)) で生成されるリスト [0, 1, 2, 3, ... len(key)-1] と key を zip で 1 つのリストにして key でソートした順序で range(len(key)) の要素を並び替えたものであると分かる。

得られた k をもとに msg を一定の規則で並び替えたものを返している。 鍵となる k は [0, 1, 2, 3, 4, 5, 6, 7] を並び替えたものしかないので全通り (8! 通り) 試すことができる。

以上のことから復号をする Python プログラムは次のように書ける。

#!/usr/bin/env python2
# coding: utf-8

import itertools

def decrypt(msg, k):
    m = "*" * len(msg)
    c = 0
    for i in k:
        for j in range(i, len(msg), 8):
            m = m[:j] + msg[c] + m[j+1:]
            c += 1

    return m

encrypt_txt = "03_duCbr5e_i_rY_or cou14:L4G f313_Th_etrph00 Wh03UBl_oo?n07!_e"

for k in itertools.permutations(range(8)):
    s = decrypt(decrypt(encrypt_txt, k), k)
    if "34C3" in s:
        print s

• 実行結果

$ python solve.py
 coorhu_4G: Lof1_d0u34C3Th3__1eb_i5_errtn0o7?r!Y00p h_W_UB0l3e
_Th3_he_o corout 4G:Lrf1u_d034C3__i5e1rb7n0o?r!Y 00ph_W_lUB03e
Wh00p here_i5_Y0ur coo1_fL4G: 34C3_d0ub1e_Th3_troUBl3_or_n07?!
Wh 00phere__i5Y0e__Th3t_uro co1rfL 4G:34C3u_d0b1oU_Bl3or_n!07?

参考文献

• 初めてのPython