skid

Dynamic programming의 정석! 피보나치 수열을 dynamic programming로 구현 해 보았다.

사실 dp를 사용하지 않고 재귀로만 구현했더니 시간초과가 떠버렸다.

점화식은 f[n]=f[n-1]+f[n-2] 이다. 

알고리즘 스터디를 계기로 Dynamic programming 문제를여러가지 접해보았는데 어렵게 느껴져서 백준 알고리즘에서 쉬운 dp문제부터 차근차근 올라가려 한다.

다음에 올릴 땐 자바 연습할 겸 자바로 올려야지!

윈xp용 지뢰찾기를 리버싱 하여 맵핵을 만들어 보자!

이번 문서에서는 약간 편법을 사용하여 폭탄이 생성된 곳을 확인하고 맵핵을 제작할 것이다.

먼저 지뢰찾기 게임을 ida에 넣고 분석해 보았다.

함수명을 bomb로 검색해 보자.

폭탄을 그리기도 하고, 수를 세기도 하고 폭탄을 보여주기도 하는 여러가지 함수들을 볼 수 있다.

이중 ShowBombs함수를 들어가 보자.

이 함수를 유심히 살펴보면 선언되지 않은 xBoxMac, YBoxMac 변수가 있다.

전역변수에 저장되어 있는 폭탄의 위치가 이곳에 저장되어 있다고 유추할 수 있다.

이 부분을 ollydbg를 통해 확인해 보자.

다음과 같이 지뢰찾기 게임의 맵으로 생각되는 부분이 배열로 저장되어 있다.

드물게 등장하는 8F를 지뢰로 생각하고 대조해 보면 위치가 일치한다.

분석해 보면, 10은 개행, 8F는 폭탄, 0F는 아직 누르지 않은 블록이라는 것을 알 수 있다.

이부분을 불러와 맵핵을 만드는 코드를 짜 보았다.

from ctypes import *

from ctypes.wintypes import *

import struct

def getpid(process_name):

import os

return [item.split()[1] for item in os.popen('tasklist').read().splitlines()[4:] if process_name in item.split()]

OpenProcess = windll.kernel32.OpenProcess

ReadProcessMemory = windll.kernel32.ReadProcessMemory

CloseHandle = windll.kernel32.CloseHandle

lenth=1200

PROCESS_ALL_ACCESS = 0x1F0FFF

pid = int(getpid("winmine.exe")[0])

address = 0x1005360

buffer = c_char_p(b" "*lenth)

val = c_int()

bufferSize = len(buffer.value)

bytesRead = c_ulong(0)

processHandle = OpenProcess(PROCESS_ALL_ACCESS, False, pid)

if ReadProcessMemory(processHandle, address, buffer, bufferSize, byref(bytesRead)):

print("Success:" + str(val.value))

else:

print("Failed.")

CloseHandle(processHandle)

buffer = str(buffer).split('\'')[1]

flag=0

for i in range(0,lenth*4):

if i%4==2:

if buffer[i] == '1':

if flag%2==1:

print "\n",

flag+=1

if buffer[i] == '0' and flag%2==1:

print "O",

if buffer[i] == '8':

print "*",

다음과 같이 코드를 완성하여 맵핵을 제작하였다.

완성!

upx로 패킹한 파일을 분석해보자.

패킹된 파일의 EP 포인트 지점에서는 ESI 레지수터에 두번째 섹션 시작 주소를, 그리고 EDI레지스터에는 첫번째 섹션 시작 주소를 세팅한다.

Source(ESI)로부터 데이터를 읽어 압축 해제 후 Destination(EDI)에 저장시킬 것이다. 그러므로 UPX EP 코드를 전부 트레이싱하면 OEP를 찾을 수 있다.

중요한 루프 #1

EDX에서 한 바이트를 읽어 EDI에 쓰는 것이다. EDI레지스터가 가리키는 주소는 첫 번째 섹션의 시작 주소이며, 메모리에서만 존재하는 섹션이다(내용은 전부 NULL).

중요한 루프 #2

본격적인 디코딩 루프로, ESI가 가리키는 두 번째 섹션의 주소에서 차례대로 값을 읽어서 적절한 연산을 거쳐 압축을 해제하여 EDI가 가리키는 첫 번째 섹션의 주소에 값을 써준다.

중요한 루프 #3

원본 코드의 CALL/JMP명령어의 destination 주소를 복원시켜주는 코드이다.

중요한 루프 #4

IAT를 세팅하는 루프이다. EDI가 두번째 섹션 영역으로 세팅된다. 이곳에는 원본 notepad.exe에서 사용되는 API 이름 문자열이 저장되어 있다. 이 과정을 이름 문자열이 끝날 때까지 반복하면 원본 notepad.exe의 IAT 복원 과정이 마무리된다.

upx패커의 특징 중 하나는 EP코드가 PUSHAD/POPAD명령어로 둘러싸여 있다는 것이다. OEP코드로 가는 JMP명령어가 POPAD명령어 바로 이후에 나타나므로 이 JMP명령어에 BP를 설치하고 실행하면 바로 OEP로 갈 수 있다.