Advent Calendar CTF 2014 Write Up [Rotate]

今週担当の杉山です。今回はつい最近まで行われていた、Advent Calendar CTF 2014のRotateというCrypt問題についてのwrite upを書いていきたいと思います。

まず始めにこの問題はどういう問題なのか

rotate.zipファイルが渡され、それを解凍すると、暗号化されたjpegらしきファイルflag.jpg.encと暗号化に用いられたであろうrotate.pyというファイルが渡され、どうにかして、flag.jpg.encを復号化するという問題です。

rotate.pyはどういうファイルなのか。

このファイルはpython rotate.py 暗号化したいFILENAME 任意の数字という感じで実行すると、暗号化したいFILENAME.encという暗号化されたファイルを生成します。またKeyの値はKey = math.radians(int(任意の数字））という式で生成されており、暗号化には(x * math.cos(key) - y * math.sin(key)) + p(x * math.sin(key) + y * math.cos(key))) という式が使われています。これの中央の部分の+は数値の足し算ではなく、文字列の連結を意味していることがわかりました。また暗号化前のバイナリ１byteに対して4byteのバイナリを生成するということがコードを読むとわかり、一度に2byteのバイナリを読み込み、それぞれ1byteずつ暗号化し、それぞれの暗号化後の4byteのバイナリと4byteのバイナリを文字列連結して8byteのバイナリをファイルに書き出していることがわかりました。

どうやって復号するか。

問題の題名的にRot暗号かなと思ったのですが、解く方法が思いつかなかったのでゴリ押し（頭の悪い解き方）で解くことにしました。 流れとしては、Keyの値を求める->Keyの値と暗号化されたバイナリを用いてx*cos(key)-y*sin(key)とx*sin(key)+y*cos(key)の連立方程式(この部分がたぶんダメ）を求め復号していくような形になります。

実際に解いてみる。

まず暗号化されたファイルがjpgファイルということで、暗号化前のjpgファイルの先頭の2byteは\xff\d8ということが確定しています。暗号化されたflag.jpg.encをバイナリエディタに突っ込んでみると、先頭の8byteがA8 5D 08 42 3C 93 A7 41 となっており、暗号化前の\ffは\a8\x5d\x08\x42に対応、\d8は\x3c\x93\xa7\x41に対応しており、これによりxとyの値が固定されKeyの値を求めることができる。

次にkeyが求められたので、Keyの値と暗号化されたファイルのバイナリを8byteずつ使って連立方程式を解く。そうすると暗号化される前のxとyの値が求められ、さらにxとyの数値をpackしてバイナリにしてあげ、ファイルに書き込むと復号化ができる。

import sys
import math
import struct
from numpy import *
from numpy.linalg import *

p = lambda x :struct.pack('f',x)
p_2 = lambda x:struct.pack('b',x)
u = lambda x :struct.unpack('b',x)[0]
u_2 = lambda x:struct.unpack('f',x)
a = '\xa8\x5d\x08\x42'
b = '\x3c\x93\xa7\x41'

def get_key():
    x,y = u('\xff'),u('\xd8')
    for i in range(0,256):
        key=math.radians(i)
        c = p(x * math.cos(key) - y * math.sin(key))
        d = p(x * math.sin(key) + y * math.cos(key))
        if a == c and b == d:
            print "key is %f\n" % key 
            return key


def decrypt(key):
    filename = sys.argv[1]
    all_list =[]
    cos_key = math.cos(key)
    sin_key = math.sin(key)
    enc = open(filename,'rb').read()
    dec = open(filename.replace('.enc',''),'wb')

    for i in range(0,len(enc),4):
        binary_4bytes = enc[i]+enc[i+1]+enc[i+2]+enc[i+3]
        z = u_2(binary_4bytes)
        all_list+=list(z) 


    for j in range(0,len(enc),2):
        equation_1 = array([[cos_key,-sin_key],[sin_key,cos_key]])
        equation_2 = array([all_list[j],all_list[j+1]])

        sol = solve(equation_1,equation_2)
        s_1 = int(round(sol[0],3))
        s_2 = int(round(sol[1],3) )
        dec.write(p_2(s_1))
        dec.write(p_2(s_2))




def main():
    if len(sys.argv) != 2:
        sys.exit(1)
    key=get_key()
    try:
        decrypt(key)
    except IndexError:
        print "Success Make flag.jpg file" 
    else:
        print "Failed Make flag.jpg file"
        sys.exit(1)

if __name__ == '__main__':
    main()

今回は普段あまり挑戦しない、Crypt問題に挑戦してみました。解き慣れていないこともあって、問題の解き方がごり押しな感じになってしまいました（笑）。他の方のWrite Upを見たら、やはり効率的かつ数学的理論に基づいた解き方があるようで、数学も勉強しないとなって気持ちになりました! ではノシ