CodeGate 2022 NDEncryptor

 대회 기간 동안 단 한 문제 푼 나를 생각하며

 

분석

 

 이 문제는 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분 만에 생성되었다.

 

 원래는 아래에 더 있어야 하지만 대충 플레그 나온 곳 까지만 보았다.