PADOCON 2010 hand-ray 리버싱 풀이 2nd
이번에는 두 번째 문제입니다. 이전 문제와 달리 약간의 프로그래밍 경험과 리버싱 경험이 필요했었구요. 핸드레이 리버싱인 만큼 컴퓨터를 비롯한 전자식 도구를 사용하지 않고 손(필기)으로 풀이하는 게 이 문제를 즐기는 포인트입니다. 한 마디로 요약하면, “삽질”을 해야 한다는 얘기죠?
다음 프로그램에서 입력값이 j3m4I7w:_oYu?yjue 일때 출력값은 무엇인가?
일부로 주석을 지웠는지 모르겠지만, 같이 풀던 후배가 살짝 당황했던 문제입니다. 이 문제를 풀기 위해서는 다음의 요소들을 고려해야합니다.
그렇다면 그 이전의 길고 긴 저 명령어들은? 저것들은 단순히 Encoding Routine 이전의 스택과 레지스터를 형성하고 문자열 처리에 활용되는 ES(Extra Segment)를 조작하는 과정입니다. Encoding Routine 이후의 과정은 printf() 함수를 호출하고 스택을 정리하는 과정이구요.
Encoding Routine이 어디인지를 알았으니 그 직전의 스택과 레지스터를 파악해야 합니다. “%s”의 주소가 0x00406030 이므로 0x00406034 부터는 입력값이 저장되어 있을 거라고 가정할 수 있습니다. 실제로도 그렇구요. Intel 아키텍쳐가 Little Endian(리틀 엔디아)이란 점만 주의하면서 흐름을 따라가 보면 스택과 레지스터를 쉽게 그릴 수 있을 겁니다. 아래 참고 문헌들을 참고하면서 그려보세요. 그리고 ES와 관련된 명령은 무시하여도 무방합니다. 문제를 푸는 데는 큰 지장이 없거든요. 어쨋든 Extra 이니까요. :]
[그림1]과 [그림2]는 제가 대충 그려봤던 스택과 레지스터의 모습입니다. Encoding Routine 직전의 모습이지요.
이제 Encoding Routine을 분석합니다. 저는 이런 for/while 문을 분석할 때 서너번 흐름을 따라가 보고 대충 어떤 코드인지를 그려봅니다. 이 문제에서도 그렇게 해보았는데, 핵심 포인트 하나가 존재하는 것을 알 수 있었죠. 0x00401063 에 있는 명령입니다.
이 명령 이전에는 입력된 문자열의 문자가 하나씩 CL에 대입되고, AL에는 1부터 1씩 증가한 값이 들어가게 되어 있습니다. 그리고 이후에 인덱스를 증가시키구요. 즉, 이것을 C 코드로 변환해 보면 아래와 같습니다.
사실, 이 문제에서 제가 약간 당황했던 코드가 있는데, 그것은 for 문의 종료 조건이었습니다. 너무 비효율적인 코드였기 때문이죠. 그래서 문제 출제자인 k1n0 님께 파도콘이 끝나고나서 문의해보았는데, Visual Studio 6.0에서 컴파일했더니 그렇게 나왔다고 하셨습니다. 역시 6.0 버전은… :[
아무튼 위 소스대로 하나씩 XOR 연산을 하면, “k1n0L1p2VeRy2weeT” 라는 답을 얻을 수 있습니다. 답이 참…
Intel Instruction Set pages :: http://www3.itu.edu.tr/~kesgin/mul06/intel/index.html
ASCII printable characters :: http://en.wikipedia.org/wiki/ASCII#ASCII_printable_characters
문제
다음 프로그램에서 입력값이 j3m4I7w:_oYu?yjue 일때 출력값은 무엇인가?
00401000 /$ 83EC 50 SUB ESP,50
00401003 |. A1 34604000 MOV EAX,DWORD PTR DS:[406034]
00401008 |. 8B0D 38604000 MOV ECX,DWORD PTR DS:[406038]
0040100E |. 8B15 3C604000 MOV EDX,DWORD PTR DS:[40603C]
00401014 |. 894424 00 MOV DWORD PTR SS:[ESP],EAX
00401018 |. A1 40604000 MOV EAX,DWORD PTR DS:[406040]
0040101D |. 894C24 04 MOV DWORD PTR SS:[ESP+4],ECX
00401021 |. 66:8B0D 446040>MOV CX,WORD PTR DS:[406044]
00401028 |. 57 PUSH EDI
00401029 |. 894424 10 MOV DWORD PTR SS:[ESP+10],EAX
0040102D |. 66:894C24 14 MOV WORD PTR SS:[ESP+14],CX
00401032 |. B9 0F000000 MOV ECX,0F
00401037 |. 33C0 XOR EAX,EAX
00401039 |. 8D7C24 16 LEA EDI,DWORD PTR SS:[ESP+16]
0040103D |. 895424 0C MOV DWORD PTR SS:[ESP+C],EDX
00401041 |. F3:AB REP STOS DWORD PTR ES:[EDI]
00401043 |. 66:AB STOS WORD PTR ES:[EDI]
00401045 |. 8D7C24 04 LEA EDI,DWORD PTR SS:[ESP+4]
00401049 |. 83C9 FF OR ECX,FFFFFFFF
0040104C |. 33C0 XOR EAX,EAX
0040104E |. 33D2 XOR EDX,EDX
00401050 |. F2:AE REPNE SCAS BYTE PTR ES:[EDI]
00401052 |. F7D1 NOT ECX
00401054 |. 49 DEC ECX
00401055 |. 74 21 JE SHORT q1.00401078
00401057 |> 8A4C14 04 /MOV CL,BYTE PTR SS:[ESP+EDX+4]
0040105B |. 8AC2 |MOV AL,DL
0040105D |. FEC0 |INC AL
0040105F |. 8D7C24 04 |LEA EDI,DWORD PTR SS:[ESP+4]
00401063 |. 32C8 |XOR CL,AL
00401065 |. 33C0 |XOR EAX,EAX
00401067 |. 884C14 04 |MOV BYTE PTR SS:[ESP+EDX+4],CL
0040106B |. 83C9 FF |OR ECX,FFFFFFFF
0040106E |. 42 |INC EDX
0040106F |. F2:AE |REPNE SCAS BYTE PTR ES:[EDI]
00401071 |. F7D1 |NOT ECX
00401073 |. 49 |DEC ECX
00401074 |. 3BD1 |CMP EDX,ECX
00401076 |.^ 72 DF \JB SHORT q1.00401057
00401078 |> 8D4C24 04 LEA ECX,DWORD PTR SS:[ESP+4]
0040107C |. 51 PUSH ECX
0040107D |. 68 30604000 PUSH q1.00406030
00401082 |. E8 19000000 CALL q1.004010A0
00401087 |. 83C4 08 ADD ESP,8
0040108A |. 33C0 XOR EAX,EAX
0040108C |. 5F POP EDI
0040108D |. 83C4 50 ADD ESP,50
00401090 \. C3 RETN일부로 주석을 지웠는지 모르겠지만, 같이 풀던 후배가 살짝 당황했던 문제입니다. 이 문제를 풀기 위해서는 다음의 요소들을 고려해야합니다.
- Encoding Routine이 어디인가?
- Encoding Routine 직전의 스택은 어떤 모습인가?
- Encoding Routine 직전의 레지스터의 값은 무엇인가?
- ASCII 테이블
풀이
여기서부터 풀이입니다. [열기]
아마 일부로 주석을 지운 듯 합니다. 실제로는 0x0040107D 에 주석이 달려 있어야 하는데요. 그건 “%s” 일 겁니다. 그 바로 아래에 있는 CALL q1.004010A0 가 printf() 함수이고, “%s”와 문자열의 주소를 스택에 넣고 있지요. 그렇다면 그 바로 위에 있는 JB 문이 for/while 문의 일부라고 생각해 볼 수 있습니다. 즉, 0x00401057~0x00401076 이 for/while 문으로 이루어진 Encoding Routine 입니다.그렇다면 그 이전의 길고 긴 저 명령어들은? 저것들은 단순히 Encoding Routine 이전의 스택과 레지스터를 형성하고 문자열 처리에 활용되는 ES(Extra Segment)를 조작하는 과정입니다. Encoding Routine 이후의 과정은 printf() 함수를 호출하고 스택을 정리하는 과정이구요.
Encoding Routine이 어디인지를 알았으니 그 직전의 스택과 레지스터를 파악해야 합니다. “%s”의 주소가 0x00406030 이므로 0x00406034 부터는 입력값이 저장되어 있을 거라고 가정할 수 있습니다. 실제로도 그렇구요. Intel 아키텍쳐가 Little Endian(리틀 엔디아)이란 점만 주의하면서 흐름을 따라가 보면 스택과 레지스터를 쉽게 그릴 수 있을 겁니다. 아래 참고 문헌들을 참고하면서 그려보세요. 그리고 ES와 관련된 명령은 무시하여도 무방합니다. 문제를 푸는 데는 큰 지장이 없거든요. 어쨋든 Extra 이니까요. :]
[그림1]과 [그림2]는 제가 대충 그려봤던 스택과 레지스터의 모습입니다. Encoding Routine 직전의 모습이지요.
이제 Encoding Routine을 분석합니다. 저는 이런 for/while 문을 분석할 때 서너번 흐름을 따라가 보고 대충 어떤 코드인지를 그려봅니다. 이 문제에서도 그렇게 해보았는데, 핵심 포인트 하나가 존재하는 것을 알 수 있었죠. 0x00401063 에 있는 명령입니다.
00401063 |. 32C8 |XOR CL,AL이 명령 이전에는 입력된 문자열의 문자가 하나씩 CL에 대입되고, AL에는 1부터 1씩 증가한 값이 들어가게 되어 있습니다. 그리고 이후에 인덱스를 증가시키구요. 즉, 이것을 C 코드로 변환해 보면 아래와 같습니다.
for (EDX = 0; input[EDX] != '0'; EDX++)
{
int AL = EDX;
input[EDX] = input[EDX] ^ (++AL);
}사실, 이 문제에서 제가 약간 당황했던 코드가 있는데, 그것은 for 문의 종료 조건이었습니다. 너무 비효율적인 코드였기 때문이죠. 그래서 문제 출제자인 k1n0 님께 파도콘이 끝나고나서 문의해보았는데, Visual Studio 6.0에서 컴파일했더니 그렇게 나왔다고 하셨습니다. 역시 6.0 버전은… :[
아무튼 위 소스대로 하나씩 XOR 연산을 하면, “k1n0L1p2VeRy2weeT” 라는 답을 얻을 수 있습니다. 답이 참…
참고 문헌
Intel Instruction Set pages :: http://www3.itu.edu.tr/~kesgin/mul06/intel/index.html
ASCII printable characters :: http://en.wikipedia.org/wiki/ASCII#ASCII_printable_characters