神のミソ汁のセカイ

大学生活のことや技術的な備忘録を残してます

ASIS Quals CTF 2015: Simple Algorithm Write-up

問題

ASIS Quals CTF 2015: Simple Algorithm

チャレンジ中のリストはこちCrypto Challenges List(2015)

解答

問題ファイルを解凍すると暗号文enc.txtと暗号化アルゴリズムが書かれたsimple_algorithm.pyが入っている。simple_algorithm.pyを読み解くと次のような変換を行っていることがわかった。

flag(ASCII文字列)を16進数に変換
↓
最初の1byteを除いて10進数に変換
↓
10進数表現で頭から2文字ずつ取り出しFAN関数に通す
↓
変換結果を文字列化して結合

FAN関数は入力した10進数を3進数ぽいものに変換して10進数表現を返している。FANへの入力は0〜99なので試しに全部変換してみると1〜4桁の10進数が返ってきた。これだと暗号文の区切りがわからないので、予め変換テーブルを用意して全ての区切りパターンを再帰を使って探索してみた。

#!/usr/bin/python
# -*- coding: utf-8 -*-

def FAN(n, m):
    i = 0
    z = []
    s = 0
    st = ''
    while n > 0:
        if n % 2 != 0:
            z.append(2 - (n % 4))
        else:
            z.append(0)
        n = (n - z[i])/2
        i = i + 1
    z = z[::-1]
    l = len(z)
    for i in range(0, l):
        p = z[i] * m ** (l - 1 - i)
        s += p
    return s

def encrypt():
    i = 0
    r = ''
    while i < len(str(iflag)):
        d = str(iflag)[i:i+2]
        nf = FAN(int(d), 3)
        print (d+':'+str(nf))
        r += str(nf)
        i += 2
    print r

def search(str, result):
    if len(str) == 0:
        return True

    for i in reversed(range(1,min(4, len(str))+1)):
        if table.has_key(int(str[:i])):
            result.append(table.get(int(str[:i])))
            if search(str[i:], result):
                return True

            result.pop()

    return False

encrypted_text = '2712733801194381163880124319146586498182192151917719248224681364019142438188097307292437016388011943193619457377217328473027324319178428'

table = {}
for i in range(100):
    table[FAN(i, 3)] = str(i).zfill(2)

result = []
search(encrypted_text, result)
result[-1] = str(int(result[-1]))
print 'A'+('%x' % int(''.join(result))).decode('hex')

このプログラムの実行結果は次の通り。

$ ./answer.py
ASIS{a9ab115c488a311896dac4e8bc20a6d7}

よってflagはASIS{a9ab115c488a311896dac4e8bc20a6d7}

補足

  • 38行目でforを逆順で回しているが、0から探しても別の結果が出るものの、復号してもflagにはならなかった。
  • FANへの入力は基本2桁だが、最後尾は1桁になる可能性がある。今回はそれに当たったので56行目で0埋めした数字から0を外して1桁に戻している。
  • ASISの問題なのでflagの頭はAだということで57行目で頭にAを追加している。

感想

はじめ、FANの逆関数を作ろうとして時間を無駄に割いてしまった。暗号文のパターンがわかっているときは変換テーブルを作って全探索するのがいいのかな。

再帰プログラムは久しぶりに書いたけどこういう時は便利だなぁ。