NextLine's blog

Wctf 2018 Truth
1. Intro
대회때는 함수들이 행렬곱을 나타내는 것이고, 행렬도 역연산이 가능하다는 사실을 알지 못해서 못풀었다.
2. Binary
파일은 윈도우 바이너리이며 dotnet이라 dnspy를 이용하였다. 이 문제를 처음에 잡았던 이유는 그나마 좀 만만해보이기도 하였고 디컴파일을 해보면 정말 쉽게 풀릴것처럼 생겼기 때문이였다.
private static void Main()
{
	Console.Write(Enter your flag );
	if (Lib.Verify(Console.ReadLine().Trim()))
	{
		Console.WriteLine(Great ));
		return;
	}
	Console.WriteLine(Wrong ();
}
위가 프로그램 main이며 딱 보기에도 Verify함수로 Flag인지 아닌지 검증한다.
public static bool Verify(string s)
{
	byte[] bytes = Encoding.ASCII.GetBytes(s);
	if (bytes.Length != 32)
	{
		return false;
	}
	byte[] array = Lib.Func2();
	Lib.Func3(array, bytes);
	Lib.Func4(array, bytes);
	Lib.Func5(array, bytes);
	for (int i = 0; i < 32; i++)
	{
		if (bytes[i] != array[3104 + i])
		{
			return false;
		}
	}
	return true;
}
Verify 함수 구조도 단순하다. Func2에서 특정 배열을 가져온다.
public static void Func3(byte[] b, byte[] x)
{
	byte[] array = new byte[32];
	for (int i = 0; i < 32; i++)
	{
		array[i] = (byte)b.Skip(i * 32).Take(32).Zip(x, (byte x1, byte x2) => (int)(x1 * x2)).Sum();
	}
	Array.Copy(array, x, 32);
}
// Token: 0x06000007 RID: 7 RVA: 0x00002228 File Offset: 0x00000428
public static void Func4(byte[] b, byte[] x)
{
	byte[] array = new byte[32];
	for (int i = 0; i < 32; i++)
	{
		array[i] = (byte)b.Skip(1024 + i * 32).Take(32).Zip(x, (byte x1, byte x2) => (int)(x1 * x2)).Sum();
	}
	Array.Copy(array, x, 32);
}
// Token: 0x06000008 RID: 8 RVA: 0x00002298 File Offset: 0x00000498
public static void Func5(byte[] b, byte[] x)
{
	byte[] array = new byte[32];
	for (int i = 0; i < 32; i++)
	{
		array[i] = (byte)(b.Skip(2048 + i * 32).Take(32).Zip(x, (byte x1, byte x2) => (int)(x1 * x2)).Sum() + (int)b[3072 + i]);
	}
	Array.Copy(array, x, 32);
}
Func들도 전부 간단하게되어있다. (하지만 실제로 이코드도 solver를 이용해 풀기에는 시간이 오래걸린다.)
// WCTF2018Rev.Properties.Resources
// Token: 0x0600000A RID: 10 RVA: 0x00002314 File Offset: 0x00000514
unsafe static Resources()
{
	IntPtr intPtr = ldftn(Func) - 16;
	long num = *intPtr;
	IntPtr intPtr2 = ldftn(Func) - 8;
	long num2 = *intPtr2;
	ref long ptr = ldftn(Func) - 16;
	IntPtr intPtr3 = ldftn(Func) + 5;
	long num3 = (long)(*(intPtr3 + 1));
	ptr = *(intPtr3 + (IntPtr)(((int)(*(intPtr3 + 2)) << 3) + 3)) + (num3 << 3);
	ref long ptr2 = ldftn(Func) - 8;
	object obj = *(ldftn(Func) - 16);
	object obj2;
	for (;;)
	{
		obj2 = obj;
		if (*obj2 == 5)
		{
			break;
		}
		obj = obj2 + 16;
	}
	ptr2 = *(obj2 + 8);
	long num4 = *(ldftn(Func) - 8);
	*num4 = 6293447916875450697L;
	long num5 = num4 + 8L;
	*num5 = 996842507592L;
	long num6 = num5 + 8L;
	*num6 = -5023708761407594752L;
	long num7 = num6 + 8L;
	*num7 = 2247216228701921188L;
	long num8 = num7 + 8L;
	*num8 = 5195160555404404409L;
	long num9 = num8 + 8L;
	*num9 = 543045289092056715L;
	long num10 = num9 + 8L;
	*num10 = 612363414786457928L;
	long num11 = num10 + 8L;
	*num11 = 5245003925894368584L;
	long num12 = num11 + 8L;
	*num12 = 3816147333L;
	long num13 = num12 + 8L;
	object obj3 = *(ldftn(Func) - 16);
	object obj4;
	for (;;)
	{
		obj4 = obj3;
		if (*obj4 == 6)
		{
			break;
		}
		obj3 = obj4 + 16;
	}
	*(obj4 + 8) = *(ldftn(Func) - 8);
	object obj5 = *(ldftn(Func) - 16);
	object obj6;
	for (;;)
	{
		obj6 = obj5;
		if (*obj6 == 7)
		{
			break;
		}
		obj5 = obj6 + 16;
	}
	*(obj6 + 8) = *(ldftn(Func) - 8) + 89L;
	object obj7 = *(ldftn(Func) - 16);
	object obj8;
	for (;;)
	{
		obj8 = obj7;
		if (*obj8 == 8)
		{
			break;
		}
		obj7 = obj8 + 16;
	}
	*(obj8 + 8) = *(ldftn(Func) - 8) + 170L;
	*intPtr2 = num2;
	*intPtr = num;
}
하지만 이 바이너리가 좀 이상한게 디버깅을 해보면 Func3은 제대로 리턴하는데 Func4와 Func5는 이상한 값들을 리턴한다. 그 이유는 위처럼 생성자에서 jitpage에 직접 어셈을 삽입하는 부분이 있다. 이부분을 이 코드만 가지고 예측하기는 힘들어서 windbg를 이용해 cli를 직접 디버깅했다. 그랬더니 Func4와 Func5의 제대로된 부분을 얻을 수 있었다.
Func4
WCTF2018Rev.Lib.Func2()
Begin 00007ff9997505d0, size 26e
00007ff9`997505d0 4989c8          mov     r8,rcx
00007ff9`997505d3 4989d1          mov     r9,rdx
00007ff9`997505d6 56              push    rsi
00007ff9`997505d7 57              push    rdi
00007ff9`997505d8 488d7118        lea     rsi,[rcx+18h]
00007ff9`997505dc e800000000      call    00007ff9`997505e1 (WCTF2018Rev.Lib.Func2(), mdToken: 0000000006000005)
00007ff9`997505e1 5f              pop     rdi
00007ff9`997505e2 488d7f33        lea     rdi,[rdi+33h]
00007ff9`997505e6 48baa45f45f540b72f1f mov rdx,1F2FB740F5455FA4h
00007ff9`997505f0 b926000000      mov     ecx,26h
00007ff9`997505f5 eb18            jmp     00007ff9`9975060f
00007ff9`997505f7 488b06          mov     rax,qword ptr [rsi]
00007ff9`997505fa 4831d0          xor     rax,rdx
00007ff9`997505fd 488907          mov     qword ptr [rdi],rax
00007ff9`99750600 48c1ca03        ror     rdx,3
00007ff9`99750604 488d7f08        lea     rdi,[rdi+8]
00007ff9`99750608 488d7608        lea     rsi,[rsi+8]
00007ff9`9975060c 48ffc9          dec     rcx
00007ff9`9975060f 4885c9          test    rcx,rcx
00007ff9`99750612 75e3            jne     00007ff9`997505f7
00007ff9`99750614 5f              pop     rdi
00007ff9`99750615 5e              pop     rsi
00007ff9`99750616 4c89c1          mov     rcx,r8
00007ff9`99750619 4c89ca          mov     rdx,r9
00007ff9`9975061c 488d4910        lea     rcx,[rcx+10h]
00007ff9`99750620 488d5210        lea     rdx,[rdx+10h]
00007ff9`99750624 e986000000      jmp     00007ff9`997506af
00007ff9`99750629 488d8910040000  lea     rcx,[rcx+410h]
00007ff9`99750630 488d5210        lea     rdx,[rdx+10h]
00007ff9`99750634 57              push    rdi
00007ff9`99750635 56              push    rsi
00007ff9`99750636 4881ec00040000  sub     rsp,400h
00007ff9`9975063d 4889e7          mov     rdi,rsp
00007ff9`99750640 4889ce          mov     rsi,rcx
00007ff9`99750643 b980000000      mov     ecx,80h
00007ff9`99750648 f348a5          rep movs qword ptr [rdi],qword ptr [rsi]
00007ff9`9975064b 4889e1          mov     rcx,rsp
; rdx = input / rcx = tb[1024:2048] / rsi = tb[2048:]
; function : make new table 
00007ff9`9975064e e8ac000000      call    00007ff9`997506ff (WCTF2018Rev.Lib.Func2(), mdToken: 0000000006000005)
00007ff9`99750653 4831ff          xor     rdi,rdi
; function : func4
00007ff9`99750656 e854000000      call    00007ff9`997506af (WCTF2018Rev.Lib.Func2(), mdToken: 0000000006000005)
00007ff9`9975065b ffc7            inc     edi
00007ff9`9975065d 83ff05          cmp     edi,5
00007ff9`99750660 75f4            jne     00007ff9`99750656
00007ff9`99750662 4831ff          xor     rdi,rdi
00007ff9`99750665 80343a5a        xor     byte ptr [rdx+rdi],5Ah
00007ff9`99750669 ffc7            inc     edi
00007ff9`9975066b 83ff20          cmp     edi,20h
00007ff9`9975066e 75f5            jne     00007ff9`99750665
00007ff9`99750670 4881c400040000  add     rsp,400h
00007ff9`99750677 5e              pop     rsi
00007ff9`99750678 5f              pop     rdi
00007ff9`99750679 c3              ret
00007ff9`9975067a 488d8910080000  lea     rcx,[rcx+810h]
00007ff9`99750681 488d5210        lea     rdx,[rdx+10h]
00007ff9`99750685 57              push    rdi
00007ff9`99750686 56              push    rsi
00007ff9`99750687 4831ff          xor     rdi,rdi
00007ff9`9975068a 4831f6          xor     rsi,rsi
00007ff9`9975068d 488b84f100fcffff mov     rax,qword ptr [rcx+rsi*8-400h]
00007ff9`99750695 483104f2        xor     qword ptr [rdx+rsi*8],rax
00007ff9`99750699 ffc6            inc     esi
00007ff9`9975069b 83fe04          cmp     esi,4
00007ff9`9975069e 75ed            jne     00007ff9`9975068d
00007ff9`997506a0 e80a000000      call    00007ff9`997506af (WCTF2018Rev.Lib.Func2(), mdToken: 0000000006000005)
00007ff9`997506a5 ffc7            inc     edi
00007ff9`997506a7 83ff0a          cmp     edi,0Ah
00007ff9`997506aa 75de            jne     00007ff9`9975068a
00007ff9`997506ac 5e              pop     rsi
00007ff9`997506ad 5f              pop     rdi
00007ff9`997506ae c3              ret
00007ff9`997506af 57              push    rdi
00007ff9`997506b0 56              push    rsi
00007ff9`997506b1 51              push    rcx
00007ff9`997506b2 4883ec20        sub     rsp,20h
00007ff9`997506b6 4831ff          xor     rdi,rdi
00007ff9`997506b9 e824000000      call    00007ff9`997506e2 (WCTF2018Rev.Lib.Func2(), mdToken: 0000000006000005)
00007ff9`997506be 88043c          mov     byte ptr [rsp+rdi],al
00007ff9`997506c1 488d4920        lea     rcx,[rcx+20h]
00007ff9`997506c5 ffc7            inc     edi
00007ff9`997506c7 83ff20          cmp     edi,20h
00007ff9`997506ca 75ed            jne     00007ff9`997506b9
00007ff9`997506cc b904000000      mov     ecx,4
00007ff9`997506d1 4889d7          mov     rdi,rdx
00007ff9`997506d4 4889e6          mov     rsi,rsp
00007ff9`997506d7 f348a5          rep movs qword ptr [rdi],qword ptr [rsi]
00007ff9`997506da 4883c420        add     rsp,20h
00007ff9`997506de 59              pop     rcx
00007ff9`997506df 5e              pop     rsi
00007ff9`997506e0 5f              pop     rdi
00007ff9`997506e1 c3              ret
00007ff9`997506e2 53              push    rbx
00007ff9`997506e3 57              push    rdi
00007ff9`997506e4 4831ff          xor     rdi,rdi
00007ff9`997506e7 4831db          xor     rbx,rbx
00007ff9`997506ea 8a0439          mov     al,byte ptr [rcx+rdi]
00007ff9`997506ed f6243a          mul     al,byte ptr [rdx+rdi]
00007ff9`997506f0 00c3            add     bl,al
00007ff9`997506f2 ffc7            inc     edi
00007ff9`997506f4 83ff20          cmp     edi,20h
00007ff9`997506f7 75f1            jne     00007ff9`997506ea
00007ff9`997506f9 4889d8          mov     rax,rbx
00007ff9`997506fc 5f              pop     rdi
00007ff9`997506fd 5b              pop     rbx
00007ff9`997506fe c3              ret
Func5
; rcx = table
; rdx = input
00007ff9`9975067a 488d8910080000  lea     rcx,[rcx+810h]
00007ff9`99750681 488d5210        lea     rdx,[rdx+10h]
00007ff9`99750685 57              push    rdi
00007ff9`99750686 56              push    rsi
00007ff9`99750687 4831ff          xor     rdi,rdi
00007ff9`9975068a 4831f6          xor     rsi,rsi
00007ff9`9975068d 488b84f100fcffff mov     rax,qword ptr [rcx+rsi*8-400h]
00007ff9`99750695 483104f2        xor     qword ptr [rdx+rsi*8],rax
00007ff9`99750699 ffc6            inc     esi
00007ff9`9975069b 83fe04          cmp     esi,4
00007ff9`9975069e 75ed            jne     00007ff9`9975068d
00007ff9`997506a0 e80a000000      call    00007ff9`997506af (WCTF2018Rev.Lib.Func2(), mdToken: 0000000006000005)
00007ff9`997506a5 ffc7            inc     edi
00007ff9`997506a7 83ff0a          cmp     edi,0Ah
00007ff9`997506aa 75de            jne     00007ff9`9975068a
00007ff9`997506ac 5e              pop     rsi
00007ff9`997506ad 5f              pop     rdi
00007ff9`997506ae c3              ret
위 두개의 함수를 제대로 복구해서 사용자 입력에 따른 출력값을 정확히 예측할 수 있었다. 하지만 여기서 중요한건 저 연산 자체가 행렬곱을 뜻한다는건데, input을 1 * 32 행렬이라고 생각하니 역행렬을 이용해 역연산을 할 수 있었다.
위처럼 행렬곱이 발생하므로 input을 X 곱하는 행렬을 A라고하면 아래와 같다.
이런식의 역연산을 그대로 코드로 짜주면 된다.
from sage.all import *
def xor(a, b):
	return eval("%s^%s" % (a, b))
f = open('table','r')
table = f.read().split(' ')
table = [int(i) for i in table]
f.close()
enc = list(table[3104:])
func5 = [0 for i in range(0x20)]
for i in range(0x20):
	func5[i] = table[2048 + (i*32) : 2048 + ((i+1)*32)]
func5_xortb = list(table[1024 : 1024 + 32])
table2 = list(table)
for j in range(0x20):
    for i in range(j,0x20):
        tmp = table2[1024 + (j * 0x20) + i]
        tmp2 = table2[1024 + (i * 0x20) + j]
        table2[1024 + (j * 0x20) + i] = tmp2
        table2[1024 + (i * 0x20) + j] = tmp
func4 = [0 for i in range(0x20)]
for i in range(0x20):
	func4[i] = table2[1024 + i * 32 : 1024 + (i+1) * 32]
func3 = [0 for i in range(0x20)]
for i in range(0x20):
	func3[i] = table[i*32 : (i+1) * 32]
R = Integers(256)
# enc_Vector
encv = vector(enc)
# Func 5
func5m = Matrix(R,func5)
for j in range(10):
	encv = list(func5m.inverse() * encv)
	for i in range(0x20):
		encv[i] = xor(encv[i],func5_xortb[i])
	encv = vector(encv)
# Func 4
encv = list(encv)
for i in range(0x20):
	encv[i] = xor(encv[i],0x5a)
    
func4m = Matrix(R,func4)
encv = vector(encv)
for j in range(5):
	encv = func4m.inverse() * encv
# Func 3
func3m = Matrix(R,func3)
encv = func3m.inverse() * encv
flag = ''
for i in encv:
	flag += chr(i)
print flag

WCTF 2018 truth write-up

댓글