반응형
대회 기간 동안 단 한 문제 푼 나를 생각하며
분석
이 문제는 32bit win binary와 암호화된 png 파일을 제공합니다.
exe 파일은 UPX Packing 되어 있어 IDA로 바로 분석하기 어려웠지만 UPX Unpacking이 가능했기에 unpacking후 ida로 분석하였고, 동적 분석은 x64dbg를 사용하였다.
프로그램의 첫 번째 실행 루틴입니다.
File 이름을 입력받고 89번째 라인에서 File 내용을 읽어드립니다. 그리고 rand함수를 사용해 121크기의 sbox를 생성합니다.
첫 번째 핵심 루틴입니다.
파일 각 byte를 bit로 바꾼 뒤 121 bit 크기만큼 채워진다면 위에서 생성한 Sbox를 통해 위치를 바꿉니다.
그리고 83번째 라인에서 121bit에 대한 HASH 연산을 하고 121~128사이를 채워 넣습니다.
그리고 임의의 자리 바꾸기를 하고, 해당 내용을 저장합니다.
그리고 연산 후 남은 bit 부분은 0을 체워서 저장해 둡니다.
두 번째 핵심 연산은 16byte 랜덤 값을 생성하는 것으로 시작합니다.
그 후 첫 번째 연산에서 만든 값을 랜덤 값과 XOR 하고, sub 401660에서 변환을 한 뒤 랜덤 값을 변환된 값으로 바꿔 줍니다.
sub 404EE0 함수에서는 암호화될 파일 앞 16byte를 가져와서 sub 401660에서 사용될 a2의 값을 생성합니다.
여기서 byte_4232A0은 AES Sbox이고, 파일은 PNG 파일이므로 앞 16byte에 무엇이 들어갈지 알 수 있습니다.
변환 함수에서 다른 코드는 역연산에 큰 문제가 없지만 위 코드에서는 문제가 있어 보입니다.
4 byte 브포는 할 수 없으므로, 연산을 조금 수정해 보면
1byte 브포 공식으로 바꿀 수 있습니다.
마지막은 8byte 랜덤으로 MT19937_64 랜덤을 생성하고 16byte마다 1bit를 xor 하는 연산이 있습니다.
해당 연산 때문에 역연산에서 브포를 해야 하는 부분이 생깁니다.
이 연산이 끝나면 .enc파일을 생성하고 암호화된 내용과 연산 2에서 나온 랜덤 값을 저장하고 끝납니다.
역연산
일단 우리는 연산 1과 2는 쉽게 해결할 수 있음을 알고 있습니다.
다만 문제는 연산 3에서 브포를 해야 한다는 것인데 이는 DFS 구조를 사용하면 쉽게 할 수 있습니다.
0x10씩 끊어서 연산하면서 연산 1에서 나온 HASH 값을 토대로 찾아가면 될 줄 알았으나... 연산 2의 존재로 인해 잘못된 값이 생성되기 시작했습니다.
하지만 여기서 우리는 PNG파일에서도 CRC32가 존재함을 알고 있기 때문에 역연산 하면서 연산 내용인 PNG 파일을 분석하면서 복호화된 내용이 올바른 값인지 확인하면 됩니다.
그래서 풀이 코드는 아래와 같습니다.
import copy
from struct import unpack
import string
import zlib
import pickle
OUTPUT_str = ['' for i in range(0xF000)]
STR_OK = [b'IHDR',b'IDAT',b'IEND',b'gAMA',b'pHYs',b'sRGB',b'sPLT']
OUTPUT = open("test.png","wb")
class THE_PNG_STATER():
def __init__(self):
self.STACK = [(0,0,0,0) for i in range(0xF000)]
self.IDX = 0
self.LEN = 0
self.next_in = 0
self.data = b""
self.bit_str=""
self.crh_stat = 0
self.crh_start = 0
self.crh_len = 0
def crc32(self,data):
crc = zlib.crc32(data[:-4])
if crc != unpack(">I",data[-4:])[0]:
return False
return True
def check_data(self,I,data_bit):
if self.next_in == I:
tmp = self.bit_str + data_bit
self.STACK[I] = (self.IDX,self.crh_stat,self.crh_start,self.crh_len)
else:
alive = (121 * I) // 8
lb = (121 * I) % 8
if alive >= len(self.data):
print("!!!!!!!!!!!!!!!!!!!")
ta = []
OUT = ""
for a in range(I):
OUT += OUTPUT_str[a]
while len(OUT) >= 8:
ta.append(int(OUT[0:8],2))
OUT = OUT[8:]
self.data = bytes(ta)
self.bit_str = OUT
else:
t = self.data[alive]
if lb == 0:
self.bit_str = ""
else:
self.bit_str = f"{t:08b}"[:lb]
tmp = self.bit_str + data_bit
self.data = self.data[:alive]
(self.IDX,self.crh_stat,self.crh_start,self.crh_len) = self.STACK[I]
datas = []
while len(tmp) >= 8:
datas.append(int(tmp[0:8],2))
tmp = tmp[8:]
bit_str = tmp
data = self.data + bytes(datas)
datalen = (121 * (I+1)) // 8
idx = self.IDX
crh_stat = self.crh_stat
crh_len = self.crh_len
crh_start = self.crh_start
while idx < datalen:
if idx == 0:
if data[0:8] != b"\x89PNG\x0d\x0a\x1a\x0a":
return False
idx += 8
if crh_stat == 0:
if idx + 4 >= datalen:
break
crh_len = unpack(">I",data[idx:idx+4])[0]
if crh_len > 0x7000:
print(hex(crh_len))
return False
crh_stat = 1
idx += 4
elif crh_stat == 1:
if idx + 4 >= datalen:
break
t = data[idx:idx+4]
print(t)
if t not in STR_OK:
return False
crh_stat = 2
crh_start = idx
idx += 4
elif crh_stat == 2:
if idx - crh_start == crh_len + 8:
if self.crc32(data[crh_start:idx]) == False:
return False
OUTPUT.seek(0);
OUTPUT.write(data)
crh_stat = 0
else:
idx += 1
# it successed
self.next_in = I+1
self.crh_start= crh_start
self.crh_stat = crh_stat
self.crh_len = crh_len
self.IDX = idx
self.data = data
self.bit_str = bit_str
return True
class microsoft_rand_prng:
def __init__(self):
self._seed = 0
def srand(self, seed):
self._seed = seed
def rand(self):
n = self._seed * 0x343fd + 0x269ec3
self._seed = n & 0xffffffff
return (n>>16) & 0x7fff
libc = microsoft_rand_prng()
libc.srand(1);
BIT_SBOX = [i for i in range(121)]
C = 0
while True:
T1 = libc.rand()
T2 = libc.rand()
if (T1* T2)&0xffffffff <= C:
break
T1 = libc.rand() % 121
T2 = libc.rand() % 121
tmp = BIT_SBOX[T1]
BIT_SBOX[T1] = BIT_SBOX[T2]
BIT_SBOX[T2] = tmp
C+=1
def HASH_BIT(STR):
HASH = 0xff
for i in range(121):
HASH = ~((int(STR[i]) & 1) - 1) & 0x89 ^ (HASH >> 1)
HASH &= 0xff
return ~HASH & 0x7F
s_box = (
0x63, 0x7C, 0x77, 0x7B, 0xF2, 0x6B, 0x6F, 0xC5, 0x30, 0x01, 0x67, 0x2B, 0xFE, 0xD7, 0xAB, 0x76,
0xCA, 0x82, 0xC9, 0x7D, 0xFA, 0x59, 0x47, 0xF0, 0xAD, 0xD4, 0xA2, 0xAF, 0x9C, 0xA4, 0x72, 0xC0,
0xB7, 0xFD, 0x93, 0x26, 0x36, 0x3F, 0xF7, 0xCC, 0x34, 0xA5, 0xE5, 0xF1, 0x71, 0xD8, 0x31, 0x15,
0x04, 0xC7, 0x23, 0xC3, 0x18, 0x96, 0x05, 0x9A, 0x07, 0x12, 0x80, 0xE2, 0xEB, 0x27, 0xB2, 0x75,
0x09, 0x83, 0x2C, 0x1A, 0x1B, 0x6E, 0x5A, 0xA0, 0x52, 0x3B, 0xD6, 0xB3, 0x29, 0xE3, 0x2F, 0x84,
0x53, 0xD1, 0x00, 0xED, 0x20, 0xFC, 0xB1, 0x5B, 0x6A, 0xCB, 0xBE, 0x39, 0x4A, 0x4C, 0x58, 0xCF,
0xD0, 0xEF, 0xAA, 0xFB, 0x43, 0x4D, 0x33, 0x85, 0x45, 0xF9, 0x02, 0x7F, 0x50, 0x3C, 0x9F, 0xA8,
0x51, 0xA3, 0x40, 0x8F, 0x92, 0x9D, 0x38, 0xF5, 0xBC, 0xB6, 0xDA, 0x21, 0x10, 0xFF, 0xF3, 0xD2,
0xCD, 0x0C, 0x13, 0xEC, 0x5F, 0x97, 0x44, 0x17, 0xC4, 0xA7, 0x7E, 0x3D, 0x64, 0x5D, 0x19, 0x73,
0x60, 0x81, 0x4F, 0xDC, 0x22, 0x2A, 0x90, 0x88, 0x46, 0xEE, 0xB8, 0x14, 0xDE, 0x5E, 0x0B, 0xDB,
0xE0, 0x32, 0x3A, 0x0A, 0x49, 0x06, 0x24, 0x5C, 0xC2, 0xD3, 0xAC, 0x62, 0x91, 0x95, 0xE4, 0x79,
0xE7, 0xC8, 0x37, 0x6D, 0x8D, 0xD5, 0x4E, 0xA9, 0x6C, 0x56, 0xF4, 0xEA, 0x65, 0x7A, 0xAE, 0x08,
0xBA, 0x78, 0x25, 0x2E, 0x1C, 0xA6, 0xB4, 0xC6, 0xE8, 0xDD, 0x74, 0x1F, 0x4B, 0xBD, 0x8B, 0x8A,
0x70, 0x3E, 0xB5, 0x66, 0x48, 0x03, 0xF6, 0x0E, 0x61, 0x35, 0x57, 0xB9, 0x86, 0xC1, 0x1D, 0x9E,
0xE1, 0xF8, 0x98, 0x11, 0x69, 0xD9, 0x8E, 0x94, 0x9B, 0x1E, 0x87, 0xE9, 0xCE, 0x55, 0x28, 0xDF,
0x8C, 0xA1, 0x89, 0x0D, 0xBF, 0xE6, 0x42, 0x68, 0x41, 0x99, 0x2D, 0x0F, 0xB0, 0x54, 0xBB, 0x16,
)
Sbox_inv = (
0x52, 0x09, 0x6A, 0xD5, 0x30, 0x36, 0xA5, 0x38, 0xBF, 0x40, 0xA3, 0x9E, 0x81, 0xF3, 0xD7, 0xFB,
0x7C, 0xE3, 0x39, 0x82, 0x9B, 0x2F, 0xFF, 0x87, 0x34, 0x8E, 0x43, 0x44, 0xC4, 0xDE, 0xE9, 0xCB,
0x54, 0x7B, 0x94, 0x32, 0xA6, 0xC2, 0x23, 0x3D, 0xEE, 0x4C, 0x95, 0x0B, 0x42, 0xFA, 0xC3, 0x4E,
0x08, 0x2E, 0xA1, 0x66, 0x28, 0xD9, 0x24, 0xB2, 0x76, 0x5B, 0xA2, 0x49, 0x6D, 0x8B, 0xD1, 0x25,
0x72, 0xF8, 0xF6, 0x64, 0x86, 0x68, 0x98, 0x16, 0xD4, 0xA4, 0x5C, 0xCC, 0x5D, 0x65, 0xB6, 0x92,
0x6C, 0x70, 0x48, 0x50, 0xFD, 0xED, 0xB9, 0xDA, 0x5E, 0x15, 0x46, 0x57, 0xA7, 0x8D, 0x9D, 0x84,
0x90, 0xD8, 0xAB, 0x00, 0x8C, 0xBC, 0xD3, 0x0A, 0xF7, 0xE4, 0x58, 0x05, 0xB8, 0xB3, 0x45, 0x06,
0xD0, 0x2C, 0x1E, 0x8F, 0xCA, 0x3F, 0x0F, 0x02, 0xC1, 0xAF, 0xBD, 0x03, 0x01, 0x13, 0x8A, 0x6B,
0x3A, 0x91, 0x11, 0x41, 0x4F, 0x67, 0xDC, 0xEA, 0x97, 0xF2, 0xCF, 0xCE, 0xF0, 0xB4, 0xE6, 0x73,
0x96, 0xAC, 0x74, 0x22, 0xE7, 0xAD, 0x35, 0x85, 0xE2, 0xF9, 0x37, 0xE8, 0x1C, 0x75, 0xDF, 0x6E,
0x47, 0xF1, 0x1A, 0x71, 0x1D, 0x29, 0xC5, 0x89, 0x6F, 0xB7, 0x62, 0x0E, 0xAA, 0x18, 0xBE, 0x1B,
0xFC, 0x56, 0x3E, 0x4B, 0xC6, 0xD2, 0x79, 0x20, 0x9A, 0xDB, 0xC0, 0xFE, 0x78, 0xCD, 0x5A, 0xF4,
0x1F, 0xDD, 0xA8, 0x33, 0x88, 0x07, 0xC7, 0x31, 0xB1, 0x12, 0x10, 0x59, 0x27, 0x80, 0xEC, 0x5F,
0x60, 0x51, 0x7F, 0xA9, 0x19, 0xB5, 0x4A, 0x0D, 0x2D, 0xE5, 0x7A, 0x9F, 0x93, 0xC9, 0x9C, 0xEF,
0xA0, 0xE0, 0x3B, 0x4D, 0xAE, 0x2A, 0xF5, 0xB0, 0xC8, 0xEB, 0xBB, 0x3C, 0x83, 0x53, 0x99, 0x61,
0x17, 0x2B, 0x04, 0x7E, 0xBA, 0x77, 0xD6, 0x26, 0xE1, 0x69, 0x14, 0x63, 0x55, 0x21, 0x0C, 0x7D
)
# WE KNOW THAT
FIRST_IN = [0x89,0x50,0x4E,0x47,0x0D,0x0A,0x1A,0x0A,0x00,0x00,0x00,0x0D,0x49,0x48,0x44,0x52]
ENC_TABLE = [0 for i in range(16 * 11)]
AB = [0,1,2,4,8,16,32,64,128,0x1b,0x36]
for i in range(16):
ENC_TABLE[i] = FIRST_IN[i]
for i in range(0x28):
v5 = ENC_TABLE[i*4 + 12]
v6 = ENC_TABLE[i*4 + 13]
v7 = ENC_TABLE[i*4 + 14]
v8 = ENC_TABLE[i*4 + 15]
if i % 4 == 0:
v9 = s_box[v6]
v6 = s_box[v7]
v7 = s_box[v8]
v8 = s_box[v5]
v5 = v9 ^ AB[(i >> 2) + 1]
ENC_TABLE[4*i+16] = v5 ^ ENC_TABLE[4*i + 0]
ENC_TABLE[4*i+17] = v6 ^ ENC_TABLE[4*i + 1]
ENC_TABLE[4*i+18] = v7 ^ ENC_TABLE[4*i + 2]
ENC_TABLE[4*i+19] = v8 ^ ENC_TABLE[4*i + 3]
def FIND_INV_XORS(K):
eT = K[0]^K[1]^K[2]^K[3]
eCxD = K[0] ^ K[2] ^ ((27 * ((eT >> 7))) ^ (2 * (eT)))&0xff
eAxB = K[1] ^ K[3] ^ ((27 * ((eT >> 7))) ^ (2 * (eT)))&0xff
#eBxC = K[0] ^ K[1] ^ ((27 * (eCxD >> 7) ^ (2 * eCxD)))&0xff
eAxD = K[2] ^ K[3] ^ ((27 * (eCxD >> 7) ^ (2 * eCxD)))&0xff
#eBxD = K[1] ^ K[2] ^ ((27 * (eAxB >> 7) ^ (2 * eAxB)))&0xff
eAxC = K[0] ^ K[3] ^ ((27 * (eAxB >> 7) ^ (2 * eAxB)))&0xff
for i in range(256):
A = i
B = eAxB ^ A
C = eAxC ^ A
D = eAxD ^ A
T = A ^ B ^ C ^ D;
if K[0] == (T ^ (27 * ((B ^ C) >> 7)) ^ (2 * (B ^ C)) ^ C)&0xff and K[1] == (T ^ (27 * ((D ^ B) >> 7)) ^ (2 * (D ^ B)) ^ B)&0xff:
if K[2] == (T ^ (27 * ((A ^ D) >> 7)) ^ (2 * (A ^ D)) ^ D)&0xff and K[3] == (T ^ (27 * ((A ^ C) >> 7)) ^ (2 * (A ^ C)) ^ A)&0xff:
return (A,B,C,D)
raise BaseException
MAP = {}
def REVERSE_XORS(ENC):
if bytes(ENC) in MAP:
return copy.deepcopy(MAP[bytes(ENC)])
S = [0 for i in range(16)]
T = [0 for i in range(16)]
S[0] = ENC[0] ^ ENC_TABLE[160]
S[5] = ENC[1] ^ ENC_TABLE[161]
S[10] = ENC[2] ^ ENC_TABLE[162]
S[15] = ENC[3] ^ ENC_TABLE[163]
S[4] = ENC[4] ^ ENC_TABLE[164]
S[9] = ENC[5] ^ ENC_TABLE[165]
S[14] = ENC[6] ^ ENC_TABLE[166]
S[3] = ENC[7] ^ ENC_TABLE[167]
S[8] = ENC[8] ^ ENC_TABLE[168]
S[13] = ENC[9] ^ ENC_TABLE[169]
S[2] = ENC[10] ^ ENC_TABLE[170]
S[7] = ENC[11] ^ ENC_TABLE[171]
S[12] = ENC[12] ^ ENC_TABLE[172]
S[1] = ENC[13] ^ ENC_TABLE[173]
S[6] = ENC[14] ^ ENC_TABLE[174]
S[11] = ENC[15] ^ ENC_TABLE[175]
C = 10
while True:
for i in range(16):
S[i] = Sbox_inv[S[i]]
C -= 1
for i in range(16):
S[i] ^= ENC_TABLE[16*C+i]
if C == 0:
break
(T[11],T[1],T[12],T[6]) = FIND_INV_XORS((S[12],S[13],S[14],S[15]))
(T[7],T[13],T[8],T[2]) = FIND_INV_XORS((S[8],S[9],S[10],S[11]))
(T[3],T[9],T[4],T[14]) = FIND_INV_XORS((S[4],S[5],S[6],S[7]))
(T[15],T[5],T[0],T[10]) = FIND_INV_XORS((S[0],S[1],S[2],S[3]))
for i in range(16):
S[i] = T[i]
MAP[bytes(ENC)] = copy.deepcopy(S)
return S
f = open("rewrite.png.enc","rb")
ENC = f.read()
f.close()
SEED = ENC[-16:]
ENC = ENC[:-16]
DEC_1 = []
S = [0 for _ in range(16)]
print(len(ENC)//16)
PNG = THE_PNG_STATER()
ORI_SEED = ['' for _ in range(len(ENC)//16)]
ORI_SEED[0] = SEED
CONT = [[0,0] for _ in range(len(ENC)//16)]
COUT = 0
I = 0
import sys
def my_except_hook(exctype, value, traceback):
with open("ORI_SEED.pickle","wb") as fw:
pickle.dump(ORI_SEED, fw)
with open("CONT.pickle","wb") as fw:
pickle.dump(CONT, fw)
with open("I.pickle","wb") as fw:
pickle.dump(I, fw)
with open("OUTPUT_str.pickle","wb") as fw:
pickle.dump(OUTPUT_str, fw)
with open("PNG.pickle","wb") as fw:
pickle.dump(PNG, fw)
sys.__excepthook__(exctype, value, traceback)
sys.excepthook = my_except_hook
if False:
with open("ORI_SEED.pickle","rb") as fw:
ORI_SEED = pickle.load(fw)
with open("CONT.pickle","rb") as fw:
CONT = pickle.load(fw)
with open("I.pickle","rb") as fw:
I = pickle.load(fw)
with open("OUTPUT_str.pickle","rb") as fw:
OUTPUT_str = pickle.load(fw)
with open("PNG.pickle","rb") as fw:
PNG = pickle.load(fw)
while I < (len(ENC)//16):
print(I)
CN_s = CONT[I][0]
CB_s = CONT[I][1]
tmp = ENC[I*16:I*16+16]
enc = []
for i in tmp:
enc.append(i)
if I == (len(ENC)//16)-1:
T = REVERSE_XORS(enc)
for i in range(16):
T[i] ^= ORI_SEED[I][i]
if T[15] != 0:
CONT[I][0] = 0
CONT[I][1] = 0
I -= 1
continue
print(T)
OUT = ""
for i in range(16):
OUT += f"{T[i]:08b}"[::-1]
if PNG.check_data(I,copy.deepcopy(OUT)) == False:
continue
CONT[I][0] = 0
CONT[I][1] = 0
I -= 1
continue
F = 0
for CN in range(CN_s,16):
for CB in range(CB_s,8):
enc[15-CN] ^= 1 << (7-CB)
T = REVERSE_XORS(enc)
enc[15-CN] ^= 1 << (7-CB)
for i in range(16):
T[i] ^= ORI_SEED[I][i]
TMP3 = ""
for i in range(16):
TMP3 += f"{T[i]:08b}"[::-1]
TMP2 = ['' for _ in range(128)]
for i in range(121):
TMP2[i] = TMP3[i+3]
TMP2[127] = TMP3[0]
TMP2[122] = TMP3[1]
TMP2[126] = TMP3[2]
TMP2[124] = TMP3[124]
TMP2[125] = TMP3[125]
TMP2[123] = TMP3[126]
TMP2[121] = TMP3[127]
hash = ""
for i in range(127,120,-1):
hash += TMP2[i]
HASH = int(hash,2)
if HASH_BIT(TMP2) != HASH:
continue
TMP = ['' for i in range(121)]
for t in range(121):
TMP[BIT_SBOX[t]] = TMP2[t]
OUT = ""
for t in range(121):
OUT += TMP[t]
if PNG.check_data(I,copy.deepcopy(OUT)) == False:
continue
F = 1
OUTPUT_str[I] = copy.deepcopy(OUT)
tmp = copy.deepcopy(enc)
tmp[15-CN] ^= 1 << (7-CB)
CONT[I][0] = CN
CONT[I][1] = CB + 1
ORI_SEED[I+1] = tmp
I += 1
break
CB_s = 0
if F == 1:
break
if F == 0:
CONT[I][0] = 0
CONT[I][1] = 0
I -= 1
Python으로 코딩하다가 잘못됨을 느꼈지만 C로 포팅하기에는 늦음을 알고 쭉 진행했습니다.
재귀 호출로 DFS를 구현하려다가 스택이 터지는 문제를 보고 while로 억지로 구현하였고, pypy로 실행한 결과 한 1시간 30분 만에 생성되었다.
원래는 아래에 더 있어야 하지만 대충 플레그 나온 곳 까지만 보았다.
'CTF' 카테고리의 다른 글
| 2017 DIMICTF problems & 후기 (0) | 2017.07.22 |
|---|---|
| Google CTF 2017 Moon (0) | 2017.06.23 |
| Plaid CTF 2017 BB8 (0) | 2017.06.02 |
| SSG 2017 Write Up (0) | 2017.06.02 |
| Plaid CTF 2017 Down the Reversing Hole (0) | 2017.04.24 |
SSGWriteUp.pdf