今週担当の杉山です。今回はつい最近まで行われていた、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を見たら、やはり効率的かつ数学的理論に基づいた解き方があるようで、数学も勉強しないとなって気持ちになりました!

ではノシ