YISF 2016 본선 리버싱 문제 풀이

올해 8월 즈음에 열렸던 순천향대 정보보호 페스티벌 본선에 출제되었던 리버싱 문제를 대회 도중에 풀지 못하여 나중에 풀어야지 생각했다가 풀어서 풀이 올립니다.

분야는 윈도우 드라이버 리버싱이며 정적분석과 windbg로 커널디버깅을 통해 직접 동적분석해서 풀었습니다.

주어진 바이너리는 exe이며 내부 리소스에서 sys파일을 바이너리가 직접 추출해줍니다.

507284b27c265f829adcdc56409200bd.sys라는 파일을 생성하고 서비스를 생성, 시작한 뒤 패스코드를 입력받고 DeviceIoControl로 전달하는 것처럼 보이나

드라이버를 직접 보면 실제로는

드라이버 자체에서 직접 입력을 받고 있습니다. 이 때는 아스키 코드가 아닌 스캔 코드가 반환되므로 문제를 풀 때 유의해야 합니다.

exe를 보면 패스코드를 두 개 입력 받는 것을 볼 수 있고 실제로 드라이버 내에서도 

두 개의 연산 구간이 존재합니다.

두 연산을 간략하게 설명하면 Stage1함수에서는 입력 값을 가지고 12차 연립방정식을 이용하여 비교를 하고 Stage2함수에서는 crc32 알고리즘을 이용해서 비교를 합니다.

먼저 Stage1입니다.

스캔코드는 키보드가 눌렸을 때와 떨어졌을 때 모두 반환하는 값이 있으므로 실질적으로 6개의 글자를 입력했을 때 if문을 통과하여 연산을 진행합니다. 먼저 연립방정식에 사용될 값을 미리 초기화 해 주고

이와 같이 연립방정식을 이용하여 비교합니다. 저는 수학을 잘 하는 편이 아니므로 z3를 이용하여 해결해 주면 됩니다. 키가 맞다면 엔터를 눌러달라고 하네요. 여기서 한 가지 불편했던 점은 여기서 방정식이 틀릴 시 

0으로 초기화 되어있는 clear_stage1변수로 나눗셈 연산을 하기 때문에 DivideByZeroException이 발생하여 블루스크린을 띄웁니다. 생각보다 짜증났습니다ㅠㅠ

쨌든 Stage1을 통과했다면 다음은 crc32입니다. Stage2는

먼저 crc32 table을 연산해서 만들고 들어온 인풋 값이 올바른 스캔코드 범위인지 체크하고 역시 6개의 인풋을 입력했는지 체크 후 다음 연산으로 진행합니다.

다음으로는 앞 12바이트는 스테이지2에서 입력한 값, 뒤 12바이트는 스테이지1에서 입력한 값을 가지고 crc32값을 구할 24바이트의 plaintext를 구성합니다. 여기서 뒤 12바이트는 스테이지1에서 이미 구한 값이므로 crc32 역연산이 가능합니다.

그리고 앞 12바이트에서는 키보드 하나를 누를 때 두 개의 스캔코드가 반환되므로 실질적으로는 6바이트를 브루트포싱 해야 합니다. 스캔코드 범위는 0~85이고 이의 6승인 377149515625가지 경우의 수를 모두 계산하기에는 시간이 너무나도 많이 걸리므로 Meet In The Middle 공격기법을 이용하여 브루트포싱을 하면 됩니다.

이렇게 해서 0xA6C80569의 crc32값을 가지는 평문을 구하면 됩니다. 구했다면 이를 이용해서 플래그를 출력해주는 부분을 볼 수 있습니다.

여기서 해시 충돌이 일어나서 여러개의 평문이 나올 수가 있는데 해당되는 평문 중 위에서 잠깐 언급했던 엔터(\n)로 시작했고 키가 모두 읽을 수 있는 값으로 구성된 평문을 찾으면 됩니다.

분석한 내용을 기반으로 파이썬 소스를 짜서 풀면 됩니다.

from z3 import *
import itertools
 
scancodeTable = ["KEY_NONE", "KEY_ESC", "1", "2", "3", "4", "5", "6", "7", "8", "9", "0", "-", "=", "KEY_BACKSPACE", "KEY_TAB", "q", "w", "e", "r", "t", "y", "u", "i", "o", "p", "[", "]", "\n", "KEY_CTRL", "a", "s", "d", "f", "g", "h", "j", "k", "l", ";", "\"", "`", "KEY_LSHIFT", "\\", "z", "x", "c", "v", "b", "n", "m", ",", ".", "/", "KEY_RSHIFT", "*", "KEY_LALT", "'", "KEY_CAPSLOCK", "KEY_F1", "KEY_F2", "KEY_F3", "KEY_F4", "KEY_F5", "KEY_F6", "KEY_F7", "KEY_F8", "KEY_F9", "KEY_F10", "KEY_NUMLOCK", "KEY_SCROLLLOCK", "KEY_HOME", "KEY_UP", "KEY_PAGEUP", "-", "KEY_LEFT", "KEY_CENTER", "KEY_RIGHT", "+", "KEY_END", "KEY_DOWN", "KEY_PAGEDOWN", "KEY_INS", "KEY_DEL", "KEY_NONE", "KEY_NONE", "KEY_NONE", "KEY_F11", "KEY_F12"]
################### Stage1 ###################
s = Solver()
input = [BitVec("input[%d]" % i, 8) for i in range(12)]
Stage1 = ''
 
dword_13940 = 43123;
dword_13940 >>= 2 + 2 * 2;
dword_13944 = 23446;
dword_13944 ^= 2 * 3;
dword_13948 = 46562;
#dword_13948 >>= 32;
dword_1394C = 23123;
dword_1394C ^= 1 + 2 * 3;
dword_13950 = 55005;
dword_13950 >>= 11;
dword_13954 = 84672 >> 1;
dword_13958 = 2 ^ 0xCF7D;
dword_1395C = 58126;
dword_13960 = 67232;
dword_13964 = 7313;
dword_13968 = 0;
dword_1396C = 2212;
dword_13970 = 54761;
dword_13974 = 54671 >> 3;
dword_13978 = 4 ^ 0x1857;
dword_1397C = 45672;
dword_13980 = 2 ^ 0x3039;
dword_13984 = 56221;
dword_13988 = 65123;
dword_1398C = 2 ^ 0x14709;
dword_13990 = 12353 >> 3;
dword_13994 = 84123;
dword_13998 = 34593;
dword_1399C = 12333;
dword_139A0 = 95783;
dword_139A4 = 26614;
dword_139A8 = 4 ^ 0x854B;
dword_139AC = 1 ^ 0x19D9E;
dword_139B0 = 34123;
dword_139B4 = 2 ^ 0x691B;
dword_139B8 = 23123;
dword_139BC = 56223 >> 4;
dword_139C0 = 74821;
dword_139C4 = 23154;
dword_139C8 = 17702;
dword_139CC = 23812;
dword_139D0 = 56745;
dword_139D4 = 0;
dword_139D8 = 12354;
dword_139DC = 76622 >> 3;
dword_139E0 = 12353;
dword_139E4 = 1 ^ 0x15592;
dword_139E8 = 2 ^ 0x17270;
dword_139EC = (3 + 1 * 2) ^ 0xB484;
dword_139F0 = 1 + 32337 * 2;
dword_139F4 = (2 + 2 * 2) ^ 0xA664;
dword_139F8 = 12367;
dword_139FC = 98382 >> 2;
dword_13A00 = 0;
dword_13A04 = 76445 >> 1 * 1;
dword_13A08 = 2 * 1 ^ 0x5B9D;
dword_13A0C = 59322;
dword_13A10 = 21357;
dword_13A14 = 94872;
dword_13A18 = 23347;
dword_13A1C = 23921;
dword_13A20 = 55652;
dword_13A24 = 6140 >> 2;
dword_13A28 = 23523;
dword_13A2C = 671663;
dword_13A30 = 82828 >> 6;
dword_13A34 = 23512;
dword_13A38 = 2 ^ 0xD973;
dword_13A3C = 55321;
dword_13A40 = 23521 >> 1;
dword_13A44 = 2 * 2 ^ 0x9BDD;
dword_13A48 = 32312;
dword_13A4C = 64042 << 2;
dword_13A50 = 23412;
dword_13A54 = 3 ^ 0x1E106;
dword_13A58 = 23225;
dword_13A5C = 39583 * 2 >> 2;
dword_13A60 = 55212;
dword_13A64 = 12827;
dword_13A68 = 38912 >> 2;
dword_13A6C = 36632;
dword_13A70 = 10450;
dword_13A74 = 23821;
dword_13A78 = 94382 >> 3;
dword_13A7C = 2 ^ 0x79FF;
dword_13A80 = 23112;
dword_13A84 = 55312;
dword_13A88 = 49320;
dword_13A8C = 78244;
dword_13A90 = 34123;
dword_13A94 = 38923;
dword_13A98 = 2 ^ 0x5EC4;
dword_13A9C = 23153;
dword_13AA0 = 3 ^ 0xAEE4;
dword_13AA4 = 11312 << 2;
dword_13AA8 = 12352;
dword_13AAC = 77331;
dword_13AB0 = 23121;
dword_13AB4 = 18820;
dword_13AB8 = 11257 >> 2;
dword_13ABC = 33221;
dword_13AC0 = 1 ^ 18470 * 2;
dword_13AC4 = 22115;
dword_13AC8 = 66442;
dword_13ACC = 22332;
dword_13AD0 = 67753;
dword_13AD4 = 1 * 2 ^ 0xB93D;
dword_13AD8 = 41178 >> 3;
dword_13ADC = 23664;
dword_13AE0 = 88553;
dword_13AE4 = 43502;
dword_13AE8 = 2 ^ 0x132C5;
dword_13AEC = 86731;
dword_13AF0 = 2 ^ 0x1E240;
dword_13AF4 = 58551;
dword_13AF8 = 34364;
dword_13AFC = 88665 >> 2;
dword_13B00 = 11946;
dword_13B04 = 23156 >> 3;
dword_13B08 = 23553;
dword_13B0C = 774423;
dword_13B10 = 18231;
dword_13B14 = 22233;
dword_13B18 = 55443;
dword_13B1C = 11234;
dword_13B20 = 667745;
dword_13B24 = 5 ^ 0x21A4;
dword_13B28 = 26574;
dword_13B2C = 47043;
dword_13B30 = 3 ^ 0xA57B;
dword_13B34 = 23532;
dword_13B38 = 23553;
dword_13B3C = 65634;
dword_13B40 = 55332;
dword_13B44 = 3 ^ 0x5C00;
dword_13B48 = 2 ^ 0xD82F;
dword_13B4C = 51549;
dword_13B50 = 88992;
dword_13B54 = 1 ^ 0x2776;
dword_13B58 = 22316;
dword_13B5C = 63732;
dword_13B60 = 23212;
dword_13B64 = 55332 << 1;
dword_13B68 = 23321;
dword_13B6C = 2 * 1 ^ 0xB0AA;
dword_13B70 = 55332;
dword_13B74 = 44232;
dword_13B78 = 33221;
dword_13B7C = 44221;
 
s.add( dword_1394C * input[3] + dword_13948 * input[2] + dword_13944 * input[1] + dword_13940 * input[0] - dword_13950 * input[4] - dword_13954 * input[5] - dword_13958 * input[6] - dword_1395C * input[7] - dword_13960 * input[8] - dword_13964 * input[9] - dword_1396C * input[11] == 0x33DE90 )
s.add( dword_1397C * input[3] + dword_13978 * input[2] + dword_13974 * input[1] + dword_13970 * input[0] - dword_13980 * input[4] - dword_13984 * input[5] - dword_13988 * input[6] - dword_1398C * input[7] - dword_13990 * input[8] - dword_13994 * input[9] - dword_13998 * input[10] - dword_1399C * input[11] == 0xE845D0 )
s.add( dword_139AC * input[3] + dword_139A8 * input[2] + dword_139A4 * input[1] + dword_139A0 * input[0] - dword_139B0 * input[4] - dword_139B4 * input[5] - dword_139B8 * input[6] - dword_139BC * input[7] - dword_139C0 * input[8] - dword_139C4 * input[9] - dword_139C8 * input[10] - dword_139CC * input[11] == 0xFF4F826B )
s.add( dword_139DC * input[3] + dword_139D8 * input[2] + dword_139D4 * input[1] + dword_139D0 * input[0] - dword_139E0 * input[4] - dword_139E4 * input[5] - dword_139E8 * input[6] - dword_139EC * input[7] - dword_139F0 * input[8] - dword_139F4 * input[9] - dword_139F8 * input[10] - dword_139FC * input[11] == 0xE3FF26 )
s.add( dword_13A0C * input[3] + dword_13A08 * input[2] + dword_13A04 * input[1] + dword_13A00 * input[0] - dword_13A10 * input[4] - dword_13A14 * input[5] - dword_13A18 * input[6] - dword_13A1C * input[7] - dword_13A20 * input[8] - dword_13A24 * input[9] - dword_13A28 * input[10] - dword_13A2C * input[11] == 0x38BE903 )
s.add( dword_13A3C * input[3] + dword_13A38 * input[2] + dword_13A34 * input[1] + dword_13A30 * input[0] - dword_13A40 * input[4] - dword_13A44 * input[5] - dword_13A48 * input[6] - dword_13A4C * input[7] - dword_13A50 * input[8] - dword_13A54 * input[9] - dword_13A58 * input[10] - dword_13A5C * input[11] == 0x219FCF5 )
s.add( dword_13A6C * input[3] + dword_13A68 * input[2] + dword_13A64 * input[1] + dword_13A60 * input[0] - dword_13A70 * input[4] - dword_13A74 * input[5] - dword_13A78 * input[6] - dword_13A7C * input[7] - dword_13A80 * input[8] - dword_13A84 * input[9] - dword_13A88 * input[10] - dword_13A8C * input[11] == 0xA69FCA )
s.add( dword_13A9C * input[3] + dword_13A98 * input[2] + dword_13A94 * input[1] + dword_13A90 * input[0] - dword_13AA0 * input[4] - dword_13AA4 * input[5] - dword_13AA8 * input[6] - dword_13AAC * input[7] - dword_13AB0 * input[8] - dword_13AB4 * input[9] - dword_13AB8 * input[10] - dword_13ABC * input[11] == 0x6C079F )
s.add( dword_13ACC * input[3] + dword_13AC8 * input[2] + dword_13AC4 * input[1] + dword_13AC0 * input[0] - dword_13AD0 * input[4] - dword_13AD4 * input[5] - dword_13AD8 * input[6] - dword_13ADC * input[7] - dword_13AE0 * input[8] - dword_13AE4 * input[9] - dword_13AE8 * input[10] - dword_13AEC * input[11] == 0x7E7EB7 )
s.add( dword_13AFC * input[3] + dword_13AF8 * input[2] + dword_13AF4 * input[1] + dword_13AF0 * input[0] - dword_13B00 * input[4] - dword_13B04 * input[5] - dword_13B08 * input[6] - dword_13B0C * input[7] - dword_13B10 * input[8] - dword_13B14 * input[9] - dword_13B18 * input[10] - dword_13B1C * input[11] == 0x455B88E )
s.add( dword_13B2C * input[3] + dword_13B28 * input[2] + dword_13B24 * input[1] + dword_13B20 * input[0] - dword_13B30 * input[4] - dword_13B34 * input[5] - dword_13B38 * input[6] - dword_13B3C * input[7] - dword_13B40 * input[8] - dword_13B44 * input[9] - dword_13B48 * input[10] - dword_13B4C * input[11] == 0x6BFF55 )
s.add( dword_13B5C * input[3] + dword_13B58 * input[2] + dword_13B54 * input[1] + dword_13B50 * input[0] - dword_13B60 * input[4] - dword_13B64 * input[5] - dword_13B68 * input[6] - dword_13B6C * input[7] - dword_13B70 * input[8] - dword_13B74 * input[9] - dword_13B78 * input[10] - dword_13B7C * input[11] == 0xAEA158 )
 
s.check()
m = s.model()
Stage1 += scancodeTable[int(str(m[input[0]]))] + scancodeTable[int(str(m[input[2]]))] + scancodeTable[int(str(m[input[4]]))] + scancodeTable[int(str(m[input[6]]))] + scancodeTable[int(str(m[input[8]]))] + scancodeTable[int(str(m[input[10]]))]
print "[*] Stage1 passcode :", Stage1, "\n"
 
################### Stage2 ###################
Stage2 = ''
CRC32 = 0xA6C80569
table = [0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x03, 0x83, 0x04, 0x84, 0x2f, 0xaf, 0x17, 0x97, 0x06, 0x86, 0x21, 0xa1]
 
CRC32Table_Index = []
CRC32Table = []
CRC32Brute_f = []
CRC32Brute_b = []
 
for i in range(256):
    k = i << 24
    for j in range(8):
        bit = k >> 31
        k <<= 1
        if bit:
            k ^= 0x4C11DB7
        k &= 0xffffffff
    CRC32Table.append(k)
    CRC32Table_Index.append(k >> 24)
 
for i in table[-1:-(len(table) / 2 + 1):-1]:
    idx = CRC32Table_Index.index(CRC32 >> 24)
    CRC32 = ((CRC32Table[idx] ^ CRC32) << 8) + (idx ^ i)
print "[*] Finding Middle CRC Finish"
 
for i in itertools.product(''.join(chr(i) for i in range(0x55)), repeat=3):
    CRC32_f = 0
    plain = i[0] + chr(ord(i[0]) + 0x80) + i[1] + chr(ord(i[1]) + 0x80) + i[2] + chr(ord(i[2]) + 0x80)
    for j in plain:
        CRC32_f = ((CRC32_f >> 8) ^ CRC32Table[(CRC32_f ^ ord(j)) & 0xff])
    CRC32Brute_f.append([CRC32_f, i])
print "[*] Forward Calculation Finish"
 
for i in itertools.product(''.join(chr(i) for i in range(0x55)), repeat=3): 
    CRC32_b = CRC32
    plain = chr(ord(i[2]) + 0x80) + i[2] + chr(ord(i[1]) + 0x80) + i[1] + chr(ord(i[0]) + 0x80) + i[0]
    for j in plain:
        idx = CRC32Table_Index.index(CRC32_b >> 24)
        CRC32_b = ((CRC32Table[idx] ^ CRC32_b) << 8) + (idx ^ ord(j))
    CRC32Brute_b.append([CRC32_b, i])
print "[*] Reverse Calculation Finish"
 
CRC32Brute_f.sort()
CRC32Brute_b.sort()
 
count = 85 ** 3
cnt1 = 0
cnt2 = 0
while cnt1 < count and cnt2 < count:
    if CRC32Brute_f[cnt1][0] == CRC32Brute_b[cnt2][0]:
        if CRC32Brute_f[cnt1][1][0] == chr(scancodeTable.index('\n')):    # Stage2 Starts With Enter
            Stage2 = scancodeTable[ord(CRC32Brute_f[cnt1][1][0])] + scancodeTable[ord(CRC32Brute_f[cnt1][1][1])] + scancodeTable[ord(CRC32Brute_f[cnt1][1][2])]
            Stage2 += scancodeTable[ord(CRC32Brute_b[cnt2][1][0])] + scancodeTable[ord(CRC32Brute_b[cnt2][1][1])] + scancodeTable[ord(CRC32Brute_b[cnt2][1][2])]
            print "\n[*] Stage2 passcode :",Stage2[1:]    # Ignore Enter
            break
        cnt1 += 1
    elif CRC32Brute_f[cnt1][0] > CRC32Brute_b[cnt2][0]:
        cnt2 += 1
    elif CRC32Brute_f[cnt1][0] < CRC32Brute_b[cnt2][0]:
        cnt1 += 1
 
scancode_flag = ''.join(chr(scancodeTable.index(i)) + chr(scancodeTable.index(i) + 0x80) for i in Stage2)
scancode_flag += ''.join(chr(scancodeTable.index(i)) + chr(scancodeTable.index(i) + 0x80) for i in Stage1)
flag = ''
 
flag += chr(ord(scancode_flag[0]) + 0x4d)
flag += chr(ord(scancode_flag[1]) - 0x6b)
flag += chr(ord(scancode_flag[2]) + 0x55)
flag += chr(ord(scancode_flag[3]) - 0x63)
flag += chr(ord(scancode_flag[4]) + 0x2e)
flag += chr(ord(scancode_flag[5]) - 0x46)
flag += chr(ord(scancode_flag[6]) + 0x3e)
flag += chr(ord(scancode_flag[7]) - 0x14)
flag += chr(ord(scancode_flag[8]) + 0x5e)
flag += chr(ord(scancode_flag[9]) - 0x31)
flag += chr(ord(scancode_flag[10]) + 0x60)
flag += chr(ord(scancode_flag[11]) - 0x54)
flag += chr(ord(scancode_flag[12]) + 0x2d)
flag += chr(ord(scancode_flag[13]) - 0x14)
flag += chr(ord(scancode_flag[14]) + 0x45)
flag += chr(ord(scancode_flag[15]) - 0x4d)
flag += chr(ord(scancode_flag[16]) + 0x8)
flag += chr(ord(scancode_flag[17]) - 0x6f)
flag += chr(ord(scancode_flag[18]) + 0xa)
flag += chr(ord(scancode_flag[19]) - 0x4e)
flag += chr(ord(scancode_flag[20]) + 0x59)
flag += chr(ord(scancode_flag[21]) - 0x20)
flag += chr(ord(scancode_flag[22]) + 0x10)
flag += chr(ord(scancode_flag[23]) - 0x33)
 
print "\n[*] flag :", flag

flag : i1i1_k@nn_d00oI77@!I_f1n