HackIM 2016 Reversing - PrisonBreak

HackIM 2016 리버싱 중 500점 짜리 마지막 문제입니다. 이 문제는 대회 당시에는 풀지 못하고 대회가 끝나고 풀어서 아쉬움이 좀 있지만 그래도 풀었기에 풀이를 올립니다. 일단 이 문제 역시 64비트에 

이러한 비주얼을 가진 문제입니다. HackIM은 이런 것을 참 좋아하는군요.. 비주얼 마저도 꼭 prison처럼 생겼네요. 헥스레이로 봐 보면 역시 donfos처럼 v50변수에 따라 프로그램 흐름이 달라지는 형식입니다. 일단 

처음에 cell을 입력받습니다. cell은 1~3까지 있고 어떤 cell을 입력했냐에 따라 할당된 메모리에 쓰여지는 값이 다릅니다. cell을 입력 받은 후에 

이렇게 동적할당을 합니다. 이 과정을 세 번 거쳐서 세 군데에 동적할당을 하고 

이렇게 할당된 공간에 값을 씁니다. 여기서 cell을 1을 했다면 12가 써지고, 2를 했다면 10, 3을 했다면 11이 쓰입니다. 디버깅을 해서 보면 

0xf52010~0xf52048까지가 첫 번째 할당된 부분, 0xf52050~f52088까지가 두 번째 할당된 부분, 0xf52090~0xf520c8까지가 세 번째 할당된 부분이며 저는 cell에서 1을 했기 때문에 각각에 12가 쓰였습니다. 그리고 

이 부분에서 첫 번째 할당된 부분에 0번째 값만큼 2번째 위치부터 값을 써 나갑니다. 즉, 첫 번째 할당 공간의 0번째 값에는 12가 있었을 테고 그 값만큼 2번 째 값부터 1부터 차례대로 써 나갑니다. 이를 위 메모리 사진에서 볼 수 있습니다. 두 번째 값부터 1, 2, 3 차례대로 써있는 것을 볼 수 있습니다. 그리고 0번째 값은 0이 됩니다. 이 작업이 끝난 후에 

path를 입력받습니다. path는 

여기서 이렇게 한 글자씩 입력을 받으며 'q', 'w', 'e', 'a', 's', 'd', 'z' 이 7글자에 대해서 각각 연산이 일어납니다. 각 글자를 입력하면 

이렇게 함수를 호출해 줍니다. 여기서 리턴값이 1이라면 프로그램은 실패 부분으로 분기하게 됩니다. 여기서 각 글자마다 모두 함수를 호출하는데 함수를 호출할 때에 인자가 바로 아까 할당한 메모리의 시작 주소들입니다. 위 사진은 'a'를 입력했을 때의 함수호출 부분인데 인자로 첫 번째 할당 주소, 세 번째 할당 주소를 넣어주고 있습니다. 각 글자들에 따른 인자 넣는 값들을 보면 

d : func(alloc_1, alloc_2);
a : func(alloc_1, alloc_3);
z : func(alloc_2, alloc_1);
q : func(alloc_2, alloc_3);
s : func(alloc_3, alloc_1);
w : func(alloc_3, alloc_2);

이러한 순서로 넣어주게 됩니다. 'e'를 입력하면 할당된 메모리의 값들을 비교합니다. 성공 부분으로 가려면 alloc_1[0] == alloc_1[1] && alloc_2[0] == 0 && alloc_3[0] == alloc_3[1] 이어야 합니다. 

이런 식으로 비교를 합니다. 다 맞다면 지금까지 입력한 값의 md5를 구하고 다시 비교합니다. 모두 true가 될 시에 flag를 출력하게 됩니다. 그러면 이제 sub_400960함수를 보겠습니다. 

역시나 굉장히 복잡해 보입니다. 이를 짧게 다시 최적화 해서 표현하면 첫 번째 인자를 a1, 두 번째 인자를 a2라 하고 

a1 != NULL
a2 != NULL
a1[0] < a1[1]
a2[0] != NULL

위 조건들을 만족하지 않으면 1를 반환합니다. 그 이후에 a2[0] == a2[1]라면 

a2[a2[0] + 1] = a1[a1[0] + 2]
a1[0]++
a2[0]--

이와 같은 연산들을 합니다. a2[0] == a2[1]가 아니라면 a1[a1[0] + 2] < a2[a2[0] + 2]인지를 비교하고 이도 아니라면 1을 반환, 맞다면 위와 같은 연산을 합니다. 이렇게 바이너리 분석은 끝이 났습니다. 그러나 위 알고리즘에 맞는 값을 찾지 못해 대회 도중에는 풀지 못하였습니다. 끝나고 다시 풀어본 결과 위 알고리즘은 hanoi 알고리즘임을 알게 됬습니다. 위 알고리즘을 알지 못한다면 https://ko.wikipedia.org/wiki/%ED%95%98%EB%85%B8%EC%9D%B4%EC%9D%98_%ED%83%91 위 링크를 참조하고 이 문제를 풀 때는 hanoi알고리즘을 적용하여 최단으로 할 수 있는 경로를 찾아내면 됩니다. 

다시 정리를 해 보자면 할당된 세 부분의 메모리는 세 개의 기둥을 의미하고, cell은 원판의 개수를 의미합니다. 1이면 11개, 2면 10개, 3이면 12개의 원판이 있는 것입니다. 그리고 보통 hanoi라면 첫 번째 기둥에서 세 번째 기둥으로 옮기는데 이 문제는 두 번째 기둥이 0인지를 확인 했고 이는 첫 번째 기둥에서 두 번째 기둥으로 원판들을 옮김을 의미하게 됩니다. 

따라서 hanoi알고리즘을 가져와서 각 경로를 출력하는 소스를 짜 주면 됩니다. 

소스는 이렇게 되고 컴파일 해서 실행 후 cell을 입력하면 그에 맞는 path를 출력해 줍니다. 

Key : nullcon{t00_34sy_t0_br34k_th15_pr1510n_by_d0nf05}