Challenge - Easy Keygen

Reversing.kr의 두 번째 문제인 Easy Keygen이다.

첫 번째 문제가 6천 명이 풀었던 것에 비하면 좀 줄어들긴 했지만 그래도 Easy라는 이름답게 4천명이나 풀은 문제다. 이번 문제는 설명 파일도 따로 포함되어 있는데 다음과 같다.

즉 시리얼이 5B134977135E7D13인 이름을 찾는 것이 이 문제의 목적이 될 것이다. 우선 키젠 프로그램을 실행시켜서 어떻게 동작하는지 확인해보자.

이번 프로그램은 콘솔 프로그램이기 때문에 명령 프롬프트에서 실행해서 프로그램 종료 후 곧바로 창이 꺼지는 것을 방지했다. 어쨌든 실행시키면 먼저 사용자 입력으로 이름(Name)을 받는다. 일단 아무 문자열이나 입력해보자.

이번에는 시리얼을 입력받고 있다. 아직 이 이름에 어떤 시리얼이 해당되는지 알 수 없기 때문에 아무 문자열이나 입력해보았다.

그러자 "Wrong"이란 메시지와 함께 프로그램이 종료되는 것을 볼 수 있었다. 그렇다면 이 키젠은 사용자가 입력한 이름을 기반으로 시리얼이 생성되며 해당 시리얼을 맞게 입력해야 성공 메시지를 출력하고 종료되리라고 추측할 수 있겠다. 이름과 시리얼 모두 공백 문자열은 받지 않으며 그 외 특별한 결과는 얻을 수 없었다. 문제에서 요구하는 대로 특정 시리얼 키에 맞는 이름을 추측하려면 키 생성 로직을 알아야 할 것 같은데 일단 디버거로 열어서 "Wrong"이라는 문자열이 사용되는 곳을 탐색해보았다.

어렵지 않게 관련 문자열을 찾을 수 있었으며 해당 위치의 코드를 살펴보니 아래처럼 분기에 따라 성공, 실패 문자열을 출력하는 부분을 볼 수 있었다.

0x00401115의 test eax, eax에 의해서 성공, 실패 분기가 결정되는 것 같지만 실제로는 키젠에서 생성한 시리얼과 사용자가 입력한 시리얼을 비교해야 하므로 좀 더 위를 살펴볼 필요가 있다. 성공 문자열을 보는 것이 목적이라면 분기를 뒤집으면 되겠지만 문제에서는 프로그램의 로직을 파악하여 특정 시리얼에 맞는 이름을 찾아내는 것을 원하기 때문에 의미가 없는 방법이다. 그렇다면 프로그램 실행에서 나왔던 "Input Name: ", "Input Serial: " 같은 문자열이 사용되는 곳을 위주로 탐색해보았다.

Detect It Easy로 확인해보면 마이크로소프트 컴파일러로 컴파일된 C/C++ 콘솔 프로그램이기 때문에 문자열을 출력하려면 printf 같은 함수를 호출하리라 생각해볼 수 있다. 위의 사진에서 볼 수 있듯이 "Input Name: "이란 문자열이 스택에 삽입되고 있는데 0x00401047의 함수 호출에 중단점을 걸고 확인해보자.

이름을 입력받는 문자열이 출력되는 것을 확인할 수 있었다. 그렇다면 값을 입력받기 위해 printf 후 scanf를 호출할 것 같은데, 0x00401054에서 스택에 삽입되는 "%s"가 scanf 함수 호출에 사용되는 매개 변수는 아닐까?

추측대로 0x00401059에서 함수가 호출된 후 사용자로부터 값을 입력받는 것을 볼 수 있었다. 함수 호출규약에 따라 오른쪽에서 왼쪽으로 매개변수가 스택에 삽입되므로 scanf("%d", &num) 처럼 호출했다면 eax 레지스터로 삽입된 0x0019FE08에 사용자가 입력한 이름이 저장될 것이다.

이후 몇 라인의 연산을 수행한 후 갑자기 esi 레지스터의 값을 3과 비교하는데 아래 0x004010B4에서 보면 cmp ebp, ecx 명령어에 따라 다시 현재 위치로 돌아오고 있다. 즉 0x00401077 ~ 0x004010B4 구간을 몇 번 반복하고 있다는 것인데 이는 어떤 목적으로 수행되는 걸까? 일단 0x0040109A에서 호출되는 함수의 매개변수로 전달되는 곳을 감시하면서 함수 실행을 감시해보기로 했다.

ecx, eax, 0x00408054, ecx를 차례대로 스택에 삽입하고 있는데 스택을 살펴보면 0x00408054는 "%s%02X" 서식 문자열이었고 ecx 레지스터는 0x71 값을 가지고 있어 별다른 의미를 찾을 수 없었다. eax 레지스터에는 0x0019FE6C라는 값이 들어갔는데 해당 위치를 덤프로 살펴보니 0x00401077 ~ 0x004010B4 구간을 반복할때마다 위의 사진처럼 특정 값이 기록되는 것을 볼 수 있었다. 총 4번 수행된 후 종료되었는데 결과적으로 71535476이라는 문자열이 되었다. 그렇다면 이것이 시리얼 키일까? 이를 알아보기 위해 프로그램을 계속 진행시킨 후 시리얼을 입력받을 때 해당 값을 입력해보았다.

"Correct!"라는 문자열과 함께 시리얼이 올바르다는 것을 확인할 수 있었다. 하지만 단지 이것만으로는 문제가 해결되지 않는데 위에서 말했듯이 이 프로그램의 목적은 시리얼이 "5B134977135E7D13"인 이름을 찾는, 즉 시리얼을 생성하는 과정을 역행하여 어떤 이름이 이 시리얼을 생성하는지 찾아내는 것이기 때문이다. 그렇다면 사용자 입력값(Name)을 가지고 키젠이 어떤 작업을 수행하는지 면밀히 살펴볼 필요가 있다.

먼저 이름을 입력받은 후에는 or, xor, add 등 0x0040105E부터 0x00401072까지 여러 연산을 수행하고 있는데 이는 0x0040106E의 명령어인 'repne scasb'을 위한 사전, 사후 작업이다. 이 명령어는 문자열의 길이를 측정하는 명령어 조합으로 0x00401072에서 마지막 널 문자를 제외한 문자열의 길이를 구하는데 ECX 레지스터에 이름("abcd")의 길이인 4가 저장되어 있는 것을 볼 수 있다. test 명령어를 통해 ZF가 세워지지 않으므로 0x00401075의 jle는 동작하지 않으며 esi는 0이기 때문에 0x00401077에 의해 0x0040107E로 점프하게 된다. 그 이후 어떻게 동작하는지 살펴보자.

movsx 명령어를 통해 ecx, edx 레지스터에 각각 esp+esi+C, esp+ebp+10 위치의 바이트 값을 복사한다. 전자의 경우 10, 20, 30 값이 저장되어 있으며 후자는 0x61, 0x62, 0x63, 0x64로 아스키 문자 'a', 'b', 'c', 'd'가 저장되어 있다. 즉 후자는 사용자가 입력한 이름 문자열이 저장되어 있는데 0x00401088을 보면 ecx, edx 레지스터를 xor 연산하는 것을 볼 수 있다. 0x10과 0x61을 xor 연산하면 0x71이 계산되며 이는 ecx 레지스터에 반영된다. 이후 스택에 ecx, eax 레지스터 등을 삽입한 후 함수를 호출하는데 해당 함수가 호출된 후 메모리에 해당 문자로부터 생성된 시리얼 문자가 기록된다.

레지스터를 통해 스택에 삽입된 위치를 주시해보면 아스키 문자로 '7', '1'이 저장되어 있으며 이는 위에서 xor 연산된 0x71 값과 동일하다. 이후에는 위에서 'repne scasb' 명령어로 문자열 길이를 구하던 것처럼 동일하게 사전, 사후 작업을 수행하고 비교를 통해 코드 블록을 반복 수행한다.

현재 ebp 레지스터에는 1, ecx 레지스터에는 4가 저장되어 있는데 이는 전체 4글자의 문자열에 대해 1개의 문자를 시리얼로 생성했다는 것을 의미한다. ebp 레지스터 값이 ecx 레지스터 값보다 작으므로 0x004010B4의 jl 명령어를 실행하여 0x00401077로 돌아가는데 이는 문자를 xor 하기 바로 전에 있는 'cmp esi, 3' 명령어다.

0x004010AC에서 보면 'inc esi' 명령어를 통해 esi 레지스터의 값을 1 증가시키고 있다. 즉 여기서는 무언가를 3번을 주기로 반복하는 것을 추측해볼 수 있는데 바로 아래의 명령어(0x0040107E)에서 이 esi 레지스터의 값을 사용하고 있다. esi 레지스터는 0 -> 1, 1 -> 2, 2 -> 3으로 증가하며 3에 도달했을 경우 0x00401077의 비교문에 걸려서 'xor esi, esi'를 통해 다시 0으로 초기화된다. 그렇기 때문에 0x0040107E는 esi 레지스터가 0일 때, 1일 때, 2일 때 경우의 총 3개의 값을 참조하며 이는 추적해보면 0x0019FE04에 위치한 0x10, 0x20, 0x30 값을 참조하는 것이 된다. 이 참조된 값은 위에서 볼 수 있듯이 사용자가 입력한 문자열과 한글자씩 xor 연산되며 연산 결과를 함수를 이용해 아스키 문자열로 생성하는 것이다. 즉 사용자 이름의 각 글자를 순서대로 0x10, 0x20, 0x30과 

위에서 시리얼을 생성하기 위해 호출하던 함수를 다시 살펴보자. 함수 호출 이전에 스택에 삽입하는 값들을 살펴보면 xor 연산 결과값 뿐 아니라 어떤 생성된 문자열, "%s%02X" 라는 포맷 스트링(현재는 안보이지만 easy keygen.408054에 위치한 문자열이다)이 존재하는 것을 볼 수 있다. 해당 문자열은 문자열로 변환된 xor 연산 결과들이 이어붙여진 형태로 포맷 스트링과 함수 형태로 볼 때 다음과 같은 sprintf 함수라고 추측할 수 있다.

int sprintf(char *buffer, const char *format-string, argument-list);

오른쪽부터 삽입되는 특성상 전달되는 매개변수를 거꾸로 파악해보면 buffer에는 0x0019FE6C, 포맷 스트링에는 0x00408054("%s%02X"), 포맷 스트링의 매개변수 리스트에 각각 0x0019FE6C, 0x74가 해당된다. 0x0019FE6C는 포맷된 문자열이 저장될 공간(buffer) 뿐 아니라 포맷 스트링 자체에서도 "%s"의 매개변수로 사용되고 있는데 그렇다면 이 0x0019FE6C에 새로운 문자열, 즉 이름 한 글자당 생성된 시리얼을 "%02X"를 이용해 이어붙이고 이 이어붙여진 문자열을 원본 문자열에 덮어씌우면서 문자열을 늘려나가 시리얼 키를 생성하는 과정이라 추측할 수 있다.

 

그렇다면 이렇게 얻은 정보를 바탕으로 어떻게 시리얼을 이름으로 계산할 수 있을까? 0x10, 0x20, 0x30과 한 글자씩 xor 연산한다는 단서를 얻었기 때문에 수동으로 계산기를 돌리거나 프로그램을 작성하여 얻어낼 수 있을 것이다. xor 연산의 중요한 특징은 xor 연산의 연산자 값을 다시 xor 연산하면 원래 피연산자 값을 찾아낼 수 있다는 것이다. 예를 들어 0x15 XOR 0x71 XOR 0x71 = 0x15가 된다. 문제에서 이름을 찾길 원하는 시리얼은 5B134977135E7D13로 위의 포맷 스트링에서 볼 수 있듯이 두 글자씩 16진수값이 쓰여져 있는 형태기 때문에 이를 분해해서 위에서 언급한 xor 연산의 특징을 활용, 순서대로 0x10, 0x20, 0x30을 다시 xor 연산한다면 원본 문자를 찾을 수 있을 것이다. 윈도우10 계산기와 hex 값이 적힌 아스키 테이블을 활용하면 쉽게 계산할 수 있다.

 

 

이번 문제는 사실 처음 풀때는 반쯤 추측으로 풀고 이 포스팅을 작성하면서 좀 더 확실하게 로직을 파악했기 때문에 시행착오가 좀 있었다. 키젠에서 이름으로 생성하는 문자열이 규칙(3개씩 비슷한 패턴)이 있는 것을 발견하고 처음에는 단순히 16진수로 일정한 값을 각 문자의 16진수마다 빼는 줄 알았는데 알고보니 xor 연산이었기 때문에 추측한 문자열과 실제 결과값이 달라서 호출되는 함수의 내부도 살펴봐야하나 고민했는데 다시 살펴보니 xor 연산 명령어를 찾을 수 있어서 어렵지 않게 이해할 수 있었던 것 같다. 이로써 두 번째 문제를 풀 수 있었고, 다음 마지막 Easy 문제는 언패킹 문제기 때문에 관련 공부를 얼른 해봐야 할 것 같다.