18 min to read

고등해커 본선 리버싱 Write UP

Featured image

제1회 고등해커 출제자 풀이

안녕하세요. 치열했던 예선의 열기에 이어 본선도 성황리에 끝난 거 같아서 모쪼록 다행입니다. 운영도 무사히 끝났고 모두 즐겨주셨을 것이라 생각하지만, 만약 그렇지 않은 분들이 있다면 죄송합니다. 올해로 새로 생긴 다소 운영 미스가 많았다고 생각합니다. 저는 본선에서는 역공학과 암호학 그리고 MISC 분야에서 출제를 했는데요. 대회가 끝나고 보니 리버싱은 배점이 좀 적었다는 생각도 들었습니다. 본디 3시 반부터 9시까지 진행되어서 6시간 내지는 5시간 진행이 예정돼있던 본선대회였지만 학과의 농간으로 5~6교시 수업이 7교시 수업이 되어서 4시간 대회가 되어버렸기 때문에 분석 위주였던 리버싱문제가 더 풀기 힘들어진 것 같습니다. 제 문제 중에서 0솔브가 4문제나 되어서 아무래도 풀이를 해야 하겠다 생각이 들어서 적어봅니다.

Re_plynn

Re_plynn문제의 파일은 전부 dll로 되어있습니다. 다만 Re_plynn.dll이 엔트리 포인트입니다.

정보 수집

die 화면

.Net 바이너리네요. 같은 폴더에 FSharp.Core.dll이 있는 거로 보아 F#언어로 작성된 거 같습니다. 별다른 문자열은 찾기 힘듭니다.

분석

[EntryPoint]
public static int main(string[] argv)
{
	$Program.init@ = 0;
	int init@ = $Program.init@;
	bool[][][] arg = Program.s2ms(Console.ReadLine());
	string[] values = Program.ms2s(SeqModule.ToArray<bool[][]>(new Program.main@56(arg, null, null, 0, null)));
	string a = string.Join(string.Empty, values);
	if (string.Equals(a, "­éò\u0002Ö}¿b±,VvÚ­þd©å\u0096\u001cvô\u0097ö½åÀNºÀ\u0093¦-)ÛO¼l\u0097Â,bê^\"ìûæ=+ò/\u00a0´_$\u009dëP?º\u009dº$\u001cgÔ'òA¯¤½\n_vÒ=§Æ¼\u0082ÉR²­ÿ\u0004=$ÈN2à\u0097¦0 Â\u0003\u0018 \0$"))
	{
		PrintfFormat<Unit, TextWriter, Unit, Unit> format = new PrintfFormat<Unit, TextWriter, Unit, Unit, Unit>("YES");
		PrintfModule.PrintFormatLineToTextWriter<Unit>(Console.Out, format);
	}
	else
	{
		PrintfFormat<Unit, TextWriter, Unit, Unit> format = new PrintfFormat<Unit, TextWriter, Unit, Unit, Unit>("NO");
		PrintfModule.PrintFormatLineToTextWriter<Unit>(Console.Out, format);
	}
	return 0;
}

main 함수의 디컴파일된 코드입니다. 입력을 받고 s2ms함수를 통해 3차원 bool 배열로 바꾼 후 해당 배열로 main@56클래스를 생성하고 이를ms2s에 넣습니다. 그리고 이 결괏값과 저 의문의 문자열을 비교하여 같으면 YES를, 다르면 NO를 출력하는군요.

main@56클래스는 2차원 bool 배열의 시퀸스 입니다. 3차원 배열과 유사하죠. 대신 불러 와질 때 변수를 정해진 동작을 통해서 바꿔서 출력한다는 점이 다릅니다. 이 클래스의 핵심은 GenerateNext함수입니다. 일종의 getter 같은 역할을 하는데, 이 부분에서 s2ms함수의 결괏값이 this.current = Program.r(this.i);를 통해서 만들어집니다. 즉 r함수를 모두 통과하는 것이죠.

//s2ms@28
string arg = this.s.Substring(this.i * 8).PadRight(9).Remove(8);
this.current = SeqModule.ToArray<bool[]>(new Program.s2ms@28-1(arg, 0, null, 0, null));
//s2ms@28-1
char byt = this.arg[this.i];
byte[] array = SeqModule.ToArray<byte>(new Program.s2ms@28-2(byt, 0, null, 0, 0));
if (array != null)
{
    bool[] array2 = new bool[array.Length];
    for (int i = 0; i < array2.Length; i++)
    {
        array2[i] = (array[i] > 0);
    }
    this.current = ArrayModule.Reverse<bool>(array2);
    return 1;
}
//s2ms@28-2
this.current = ((byte)this.byt & (byte)(1 << (this.i & 7)));

s2ms에서 쓰이는 시퀸스들의 GenerateNext함수의 주요구문입니다. 28에서는 8바이트씩 문자열을 나누고 28-1에서는 나눠진 문자열의 각 문자를 28-2에 넣어 배열로 바꿉니다. 28-2에서는 문자 하나를 이진 배열화 시킵니다. 즉 s2ms는 문자열을 8바이트로 나누어서 각 문자열을 8x8 이차 이진 배열로 바꿉니다. 예를 들자면 이런 식이죠, \(\left[ ``Sunrin\{\}'' => \begin{bmatrix} S\\u\\n\\r\\i\\n\\\{\\\} \end{bmatrix}=> \begin{bmatrix} 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 & 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 & 0 & 1 \end{bmatrix} \right]\) s2ms 는 위같은 8x8 배열을 문자열 끝까지 만듭니다. 이제 r함수를 분석해 봅시다.

public static bool[][] r(bool[][] blk)
{
    bool[][] array = SeqModule.ToArray<bool[]>(new Program.tmp@31(0, null, 0, null));
    for (int i = 0; i < 8; i++)
    {
        for (int j = 0; j < 8; j++)
        {
            Tuple<int, int> tuple = Program.subtable[i][j];
            int item = tuple.Item2;
            int item2 = tuple.Item1;
            array[item2][item] = blk[i][j];
        }
    }
    return array;
}

r함수의 디컴파일된 코드입니다. 8x8 정도크기의 blk 배열을 i,j 좌표에 있는 값을 subtable[i][j]에 있는 x,y 좌표로 이동시킨 배열을 만들어서 반환합니다. 가령 blk[i][j]을 옮길 때 subtable[i][j] 이 (0,1) 이면 arr[0][1]=blk[i][j] 가 되는 거죠.

ms2s의 분석은 생략 하겠습니다. 그저 s2ms의 역연산 일 뿐 입니다.

키복구

키복구를 하려면 subtable을 얻어야 합니다. subtable을 이용해서 반대로 된 subtable을 만들면 이상한 문자열을 키로 복구해 낼 수 있습니다.

subtable은 다음과 같습니다

[
    [(0, 6), (1, 2), (7, 5), (5, 2), (3, 7), (4, 4), (7, 6), (2, 6)],
    [(3, 0), (0, 0), (3, 6), (6, 7), (7, 3), (1, 0), (2, 5), (4, 6)], 
    [(0, 1), (6, 6), (0, 2), (1, 6), (1, 1), (1, 7), (6, 0), (3, 2)], 
    [(7, 4), (0, 5), (7, 2), (6, 5), (2, 7), (2, 4), (4, 0), (3, 1)], 
    [(4, 7), (6, 3), (4, 3), (3, 5), (2, 2), (3, 4), (6, 1), (6, 4)], 
    [(5, 6), (2, 3), (2, 1), (5, 0), (4, 5), (5, 3), (4, 1), (1, 5)], 
    [(1, 3), (6, 2), (2, 0), (0, 7), (5, 7), (3, 3), (5, 4), (1, 4)], 
    [(7, 7), (0, 4), (0, 3), (5, 5), (7, 0), (4, 2), (5, 1), (7, 1)]
]

사실 반대로 된 subtable은 필요가 없습니다. [0][0] 에 있던 비트를 복구하려면 subtable[0][0] 의값인 0,6 의 좌표로 가 읽으면 되기 때문입니다. 따라서 역연산 코드는 다음과 같습니다.

subtable=[
    [(0, 6), (1, 2), (7, 5), (5, 2), (3, 7), (4, 4), (7, 6), (2, 6)],
    [(3, 0), (0, 0), (3, 6), (6, 7), (7, 3), (1, 0), (2, 5), (4, 6)],
    [(0, 1), (6, 6), (0, 2), (1, 6), (1, 1), (1, 7), (6, 0), (3, 2)],
    [(7, 4), (0, 5), (7, 2), (6, 5), (2, 7), (2, 4), (4, 0), (3, 1)],
    [(4, 7), (6, 3), (4, 3), (3, 5), (2, 2), (3, 4), (6, 1), (6, 4)],
    [(5, 6), (2, 3), (2, 1), (5, 0), (4, 5), (5, 3), (4, 1), (1, 5)],
    [(1, 3), (6, 2), (2, 0), (0, 7), (5, 7), (3, 3), (5, 4), (1, 4)],
    [(7, 7), (0, 4), (0, 3), (5, 5), (7, 0), (4, 2), (5, 1), (7, 1)]
]

#chk
t = [173,233,242,2,214,125,191,98,177,44,86,118,218,173,254,100,169,229,150,28,118,244,151,246,189,229,192,78,186,192,147,166,45,41,219,79,188,108,151,194,44,98,234,94,34,236,251,230,61,43,242,47,160,180,95,36,157,235,80,63,186,157,186,36,28,103,212,39,242,65,175,164,189,10,95,118,210,61,167,198,188,130,201,82,178,173,255,4,61,36,200,78,50,224,151,166,48,32,194,3,24,32,0,36]

td8 = [[list(bin(j)[2:].zfill(8)) for j in t[i:i+8]]for i in range(0,len(t),8)]
flag = "".join(["".join([chr(int("".join([td8[i][subtable[j][k][0]][subtable[j][k][1]] for k in range(8)]),2))for j in range(8)])for i in range(len(t)//8)])
print(flag)

급하게 쓴 코드라서 다소 난해하지만 그냥 3중 for문 2번 돌린다고 생각하시면 됩니다.

PlantForBeam

elf 바이너리입니다. 나중에 생각해보니 배점을 더 올리는게 맞았을꺼같네요.

비록 나중에 쉬운바이너리로 바꿨지만, 저는 처음에 올라간 바이너리로 풀겠습니다.

정보수집

실행화면

실행하면 다짜고짜 행복하게 만들어 달라고 합니다. 그래서 행복해지는 말을 했는데 행복하지가 않다네요.

die 화면

AMD64 리눅스 바이너리네요.

분석

이 바이너리 분석에서 hex-rays는 사용하지 않는 게 좋습니다. SSE2명령어가 몇몇 개 있기 때문에 결과가 이쁘게 나오지를 않습니다. 그리고 제가 hexray가 없어서..

ida function

함수는 깔끔하게 main 밖에 없습니다.

main cfg

메인 함수의 그래프를 보면 프롤로그와 값을 입력받는 부분, 루프문 하나 그리고 아주 기이——인 노드가 보입니다.

main 첫부분

main의 첫 부분을 보면 scanf로 0x6011A0 주소에 값을 받고 있습니다. (앞으로 60은 생략하겠습니다) 후에 cl레지스터에 11A0주소를 dl 레지스터에 11A0+1주소를 rax에 -50을 그리고 esi에 0x3E0F0E32값을 넣습니다.

그후 하단 루프에서

(0x11E0+100)[rax*2] = (0x11A0+50)[rax] & (0x11A0+50)[rax+1]
(0x11E0+100)[rax*2+1] = (0x11A0+50)[rax] & (0x11A0+50)[rax+2]
(0x12E5+51)[rax*4] = (DWORD((0x11A0+50)+rax)) & esi

이렇게 3가지 연산을 50번 반복합니다.

cmp부분

그 후 movdqa,pcmpeqb,pand,pshufd 등등 요오상한 어셈이 잔뜩 있습니다. 이건 amd64에서 있는 SIMD인스트럭쳐인데요. xmmword는 128bit 정수인데요. xmm0, xmm1과 비교를 하는데 mov를 통해서 옮겨오고 비교하기 때문에 사실상 0x1040부터 100byte를 0x11E0부터 100byte와 비교하는 것과 같습니다.

밑에도 좀 변태같이 비교하긴 하지만 0x10B0와 0x1250 배열을 비교하는 것 입니다. 이것은 전부 같거나 참이 여야하고 0x11A0 배열의 마지막 바이트는 64이상이여야 합니다.

키복구

and연산으로만 점철 돼 있는 루프문에서 키를 얻어야 합니다.

and연산의 특성상 두 바이트 중 둘 중 하나라도 없는 비트는 결과에 나오지를 않습니다. 역으로 생각하면 둘 다에게 있는 비트만 결과에 나오겠죠. 그리고 한 비트는 8가지 단서를 통해서 복구 할 수 있습니다.

4가지 단서는

(0x11E0+100)[rax*2] = (0x11A0+50)[rax] & (0x11A0+50)[rax+1]
(0x11E0+100)[rax*2+1] = (0x11A0+50)[rax] & (0x11A0+50)[rax+2]

연산에서 나옵니다. 이 연산은 입력된 값의 앞글자와 두개 앞글자를 and 하는것입니다.

P4B을 예로 들자면

P4B
=> 01010000 00110100 01000010 
 PP44BB
&4BB???
=> 01010000 01010000 00110100 00110100 01000010 01000010
 & 00110100 01000010 01000010 NULLBYTE NULLBYTE NULLBYTE
=> 00010000 01000000 00000000 00000000 00000000 00000000

이런식의 배열이 나오게 됩니다.

이때 B를 알아 내고 싶다면 변환된 배열의 2번째 요소와 3번째, 5번째, 6번째 요소에서 and 되었으므로

2,3,5,6번째 요소를 OR 시켜주면 부분적으로 알아낼 수 있습니다.

01000000|00000000|00000000|00000000
=01000000

그 다음 4개 단서는 (0x12E5+51)[rax*4] = (DWORD((0x11A0+50)+rax)) & 0x3E0F0E32에서 얻을 수 있습니다. 이 연산은 Hello, P4B를 예시로 들면 다음과 같이 처리됩니다. (0x3E0F0E32는 that 이라고 표기하겠습니다).

Hello, P4B
=> Hell ello llo, lo,  o, P , P4  P4B P4B? 4B?? B???
&  that that that that that that that that that that

만약 5번째 글자인 o를 알고 싶다면 o가 사용된 2,3,4,5번쨰째 요소의 결과를 or 시키면 됩니다.

우리는 이연산에서 한 글자의 하위 6비트를 알아낼 수 있습니다. 왜냐하면

ooooooooxxxxxxxxxxxxxxxxxxxxxxxx
00111110000011110000111000110010

xxxxxxxxooooooooxxxxxxxxxxxxxxxx
00111110000011110000111000110010

xxxxxxxxxxxxxxxxooooooooxxxxxxxx
00111110000011110000111000110010

xxxxxxxxxxxxxxxxxxxxxxxxoooooooo
00111110000011110000111000110010

이니까 o인 부분만 보면

oooooooo
00111110
00001111
00001110
00110010
=>00111111

이여서 전부 or해주면 하위 6비트를 알아낼 수 있습니다.

이제 코드를 짜면 다음과 같이 짤수있습니다.

orihop = [81,66,100,112,98,104,96,98,104,105,106,98,115,105,97,115,97,105,103,103,111,79,79,105,73,83,97,73,83,112,80,79,96,96,111,110,110,103,102,98,99,101,113,98,100,101,102,78,71,103,71,85,101,97,113,85,89,105,73,78,104,104,106,100,96,106,100,101,102,46,39,97,57,37,97,113,97,69,83,97,73,78,104,104,106,100,96,106,100,101,102,32,33,33,33,33,33,0,0,0]
oritof = [839779346,671223344,772342306,973998130,839585312,671287842,906560050,772212786,772736544,504303154,672075298,839454242,503515154,806289952,771755570,772734994,772738608,638455330,839323170,872613410,772080162,638452786,503778864,638518818,872877602,939853330,503907362,672073776,772345392,705562642,873074208,772082210,638452770,1040649776,940508706,604573218,839190578,503514160,672072224,772345394,705562642,873074208,772082210,638452770,537333296,536938018,1006698530,852000,3104,48]

flg=""
for i in range(50):
    suhk=orihop[i*2]
    suhk|=(oritof[i]&0xFF)
    if i - 3>=0:
        suhk |= (oritof[i - 3] >> 24) & 0xFF
    if i - 2 >= 0:
        suhk |= (oritof[i - 2] >> 16) & 0xFF
    if i - 1 >= 0:
        suhk |= (oritof[i - 1] >> 8) & 0xFF
    if (i*2)-3>=0:
        suhk|=orihop[(i*2)-3]
    if (i*2)-2>=0:
        suhk|=orihop[(i*2)-2]
    if (i*2)+1<len(orihop):
        suhk|=orihop[(i*2)+1]
    flg += chr(suhk)
print flg[:-1]+chr(ord(flg[-1])|(1<<6))

다음과 같은 코드를 짜서 플래그를 얻을수 있습니다.

시간이 4시간 밖에 없었던 대회 치곤 분석에 시간이 더 걸렸을 수 도 있다는 생각이 들었습니다.

시간이 6시간 정도면 충분히 풀이자가 나올 수 있었을 텐데, 좀 아쉽습니다.