hackingboy

안녕하십니까. 오랜만에 포스팅을 다시 할려고 합니다. 포스팅 주제는 백준 온라인 저지에 올라와있는 알고리즘 문제 풀이입니다. 문제 풀이 순서는 정답자가 많은 문제부터 차례대로 풀어갈 예정입니다.

문제 : https://www.acmicpc.net/problem/2557 (백준 온라인 저지)

이 문제는 크게 설명할 필요가 없으므로 넘기겠습니다.

안녕하십니까 이번에는 level10을 한 번 풀어보겠습니다. 홈페이지로 들어가 문제를 한 번 봅시다.

시리얼이 WWWCCCJJJRRR일 때 이름값을 구하라고 되어있습니다. 이름은 4자리자로 하는군요. 프로그램을 다운받아 실행셔키봅시다.

이름과 시리얼이 매치가 안될 경우 실패문자열을 출력합니다. 올리디버거에서 문자열을 찾아봅시다.

CMP EAX,0C를 하여 EAX값이 0C가 아닐 경우 실패문자열이 출력되는것을 확인 할 수 있습니다. C가 10진수로 12이므로 아마 이부분은 시리얼의 자리수를 검사하는 부분인 것 같습니다. 계속 진행합시다.

00402092부분을 보시면 0022FEA3스택의 값과 0을 비교하는 것을 볼 수 있습니다. 만약 0022FEA3스택의 값이 0이라면 실패문자열이 출력되는 곳으로 점프하는군요. 0022FEA3스택에 하드웨어 브레이크를 건 후 다시 실행시켜봅시다. 

그러면 00401F8F에서 AL의 값을 0022FEA3에 대입하는 것을 확인할 수 있습니다. EAX레지스터는 보통 함수의 반환값을 저장하므로 위의 0040144C함수에서 값을 받을 확률이 큽니다. 0040144C함수를 살펴봅시다.

함수 내부로 가서 살펴보면 00401C80에서 22FD84스택의 값을 EAX에 옮기는 것을 확인할 수 있습니다. 22FD84스택에 하드웨어 브레이크를 걸고 재실행해봅시다.

그러면 00401BC2에서 22FD3C스택의 값을 EDX에 옮기고 그 EDX를 22FD84에 옮기는 것을 확인할 수 있습니다. 이번엔 22FD3C스택에 브레이크를 걸고 재실행해봅시다.

이번엔 00401B79에서 22FDDF스택의 값을 EAX에 옮기고 그 EAX를 22FD3C에 옮기는 것을 확인할 수 있습니다. 지겹지만 22FDDF에 브레이크를 걸고 또 재실행해봅시다.

그러면 00401B5C에서 CMP구문을 수행하고 그 결과에 따라 JLE명령어 수행. JLE가 수행되지 않으면 22FDDF에 0을 집어넣는 것을 확인할 수 있습니다. 즉 EAX가 5보다 클 경우 22FDDF에 0을 집어넣는 것을 볼 수 있으며 우리가 원하는 성공문자열을 출력하기 위해서는 22FDDF에 0이 들어가지 않아야 하는 것을 알 수 있습니다.

간단하게 00401B5C에서 EAX값이 5이하 여야 한다는 것이지요. EAX값이 5이하라면 JLE코드에서 점프를 하게 되므로 22FDDF에 0을 대입하는 코드를 생략할 수 있게 딥니다.

그렇다면 이 EAX는 어디서 오는 것일까요? 코드를 다시 한 번 분석해보니 다음과 같은 알고리즘을 찾을 수 있었습니다.

여기서 하나라도 CMP EAX,5에 의해 0022FDDF에 0이 넣어지면 실패하게 됩니다.

자 그러면 이제 이름으로 만든 22FDCC스택의 값과 시리얼로 만든 22FDD0스택의 값이 어떻게 만들어지는지 살펴볼 차레입니다. 분석을 한 결과 다음과 같은 알고리즘을알아내었습니다.

즉 CMP연산에 필요한 EAX와 EDX에서 EDX는 시리얼값을 토대로 만들어진 값이며 EAX는 이름값을 토대로 만들어진 값이라고 결론지을 수 있습니다. 이것을 코딩으로 한 번 구현해봅시다.

a배열에는 알파벳이 저장된 배열입니다.

i는 이름값을 차례대로 대입하기 위한 카운트이며 j는 EAX와 EDX값을 구하기 위한 카운트입니다.

for문이 총 5번 쓰였는데 첫번째 for문은 이름값을 차례대로 대입하기 위한 for문이고 그다음 실행하는 2개의 for문은 이름값을 토대로 만든 EDX값을 구하기 위해, 그리고 나머지 2개의 for문은 시리얼값을 토대로 만든 EAX값을 구하기 위해 사용하였습니다.

abs함수는 절대값을 구해주는 함수이고 이렇게 반환된 값이 5이하 일경우 해당하는 이름값을 출력하도록 하였습니다.

자 그러면 한 번 실행해봅시다. 제일 먼저 시리얼값인 W에 해당하는 첫자리 이름값을 구해보겠습니다.

여기서 출력된 숫자와 영문자 값이 시리얼 W에 해당하는 값. 즉 이름의 첫자리에 올 수 있는 값입니다.

이번에는 시리얼 C에 해당하는 값. 즉 이름의 두자리에 올 수 있는 값입니다.

이번에는 시리얼 J에 해당하는 값. 즉 이름의 세자리에 올 수 있는 값입니다.

마지막으로 시리얼 R에 해당하는 값. 즉 이름의 네자리에 올 수 있는 값입니다.

정리하면 다음과 같습니다.

보시다시피 올 수 있는 단어가 많으므로 이로 만들 수 있는 이름값도 굉장히 많습니다.

31A6, 61A6 38A6, 3DJG.... 이런식으로 말입니다.

그런데 문제에서 보면 순서상 가장 먼저 오는 문자열이 바로 정답문자열이라고 합니다. 그렇다면 가장 먼저 출력된 값인 3,1,A,6으로 만든 문자열이 정답이 되겠군요. 일단 확인해봅시다.

올바른 이름과 키값이라고 출력되는군요. 한번 인증해봅시다.

성공적으로 인증이 된 것을 확인 할 수 있습니다.

네 이것으로 문제풀이를 마치겠습니다.

안녕하십니까 이번에는 level9를 한 번 풀어보겠습니다. 홈페이지로 들어가 문제를 한 번 봅시다.

패스워드를 찾으라고 되어있습니다. 파일을 다운받아 실행시켜봅시다.

이름과 패스워드를 입력하면 이름 혹은 패스워드가 틀렸다는 문구가 나옵니다. 올리디버거로 문자열을 찾아봅시다.

입력받을 때 출력된 문자열인 Username과 password가 보입니다. 따라 들어가봅시다.

00EC1000 함수를 호출하면 실패 문자열이 출력되는 것을 확인할 수 있네요. 따라 들어가봅시다.

계속 코드를 수행하다 보면 위의 TEST문과 CMP구문에 의해 실패 문자열이 출력되는 루프 부분으로 점프하는 것을 볼 수 있습니다. 즉 성공문자열을 출력하기 위한 루프로 가기 위해서는 위의 점프 명령어에 점프하지 않아야 한다는 것을 할 수 있습니다.

조건은 총 2개입니다.

TEST BL,BL -> BL의 값이 0이면 JZ로 인해 점프하게 됩니다. 즉 BL은 0이 아니어야 합니다.

CMP BYTE PTR SS:[ESP+0B], 0 -> ESP+0B주소값인 스택의 값이 0이면 JE에 의해 점프하게 됩니다. 즉 ESP+0B의 스택값은 0이 아니어야 합니다.

다시 한 번 코드를 살펴봅시다.

재시작하여 다시 코드를 수행하면 윗부분의 첫루프 부분에서 우리가 입력한 Name의 값이 첫번째자리랑 0x00(NULL값)을 비교하는 것을 알 수 있습니다. 코드를 계속 수행해봅시다.

코드를 계속 수행하면 JNE로 인해 SBB명령어 부문으로 점프하게 되고 SBB 명령어 부문에서 EAX를 0이 아닌 값으로 만듭니다.

그리고 TEST EAX,EAX 코드를 수행하여 그 ZF의 값에 따라 SETZ 명령어가 수행됩니다.

SETZ 명령어는 ZF의 값이 1일 때 해당 부분의 값을 1로 수정시켜주는 명령어입니다. 여기서는 BL의 값을 변경시키는데 이 때 이 BL의 값은 앞에서 보셧던 성공 문자열 출력 분기점에서 TEST 코드를 수행하는 레지스터입니다. 즉 이 코드에서 BL의 값이 1이 되어야 분기점의 TEST BL,BL 에서 TEST가 ZF를 0으로 반환하고 ZF가 0이므로 JZ명령어가 수행되지 않게 됩니다. 즉 성공부분으로 갈 수 있는 첫 부분입니다.

계속 다음 코드로 넘어가봅시다.

SETZ명령어 바로 아래의 코드를 보시면 CMP EAX,DWORD PTR DS:[ECX]부분이 보입니다. 이 때 비교하는 값은 우리가 입력한 패스워드(EAX)와 0088228F를 비교하는 것을 볼 수 있습니다. 그리고 이로 인한 ZF가 설정되어 밑의 SETE BYTE PTR SS:[ESP+0F]에서 값이 입력되는 것을 알 수 있습니다.

SETE 명령어는 ZF가 0일 때 해당 주소의 값을 1로 수정시켜주는 0이며 이 때 수정시키는 주소값인 BYTE PTR SS:[ESP+0F]는 우리가 성공문자열로 가기 위한 분기점에 존재하는 BYTE PTR SS:[ESP+0B]의 값이랑 동일한 것을 알 수 있습니다.

즉 CMP EAX,DWORD PTR DS:[ECX]부분에서 두 값이 서로 같아야 ZF가 0을 반환하고 이 ZF에 의해 SETE코드에서 BYTE PTR SS:[ESP+0F]의 값을 1로 수정하여 성공분기점에서 JE명령어를 수행하지 않게 할 수 있습니다.

최종적으로 정리를 하면 다음과 같습니다.

1. 우리가 입력한 이름의 첫자리 값이 NULL이어야 한다.

2. 우리가 입력한 패스워드 값이 16진수 0088228F이어야 한다.

다만 패스워드를 입력받을 때에는 10진수로 받으므로 우리는 16진수값인 0088228F를 10진수로 바꿔줄 필요가 있습니다. 10진수로 바꾸면 값은 8921743가 됩니다.

즉 이 8921743값이 패스워드라고 볼 수 있겠습니다. 이름 같은 경우에는 NULL을 입력해주면 될 것 같은데 NULL값을 입력할 방법이 없어 시연은 생략하겠습니다.

이 패스워드를 인증해봅시다.

정답이 맞는 것 같군요.

추가로 재미있는 부분이 하나 있다면 코드에 이름과 DonaldDuck를 비교하는 부분이 나오는데 이름을 DonaldDuck으로 주면 "니가 그것(DonaldDuck)을 이름으로 느꼈다는 걸 못믿겠어" 라는 문자열이 추가로 출력됩니다. 일종의 낚시라고 볼 수도 있겠네요.

네 이것으로 문제풀이를 마치겠습니다.