[Reversing] Keygen

참.. 이 문제 풀고 풀이를 봤는데.. ida가 잘 만든 툴인거 같다..ㅋㅋㅋㅋ

---

문제설명

이 binary는 입력한 문자열과 저장된 문자열과 값 비교를 했을때 같으면 flag를 출력하는 문제이다.

함수의 흐름은 main -> check_key -> encoding 이다.

단, 입력한 문자열의 길이는 0x9 이상, 0x40 이하이다.

여기서 +103은 <check_key> 함수의 종료시점이다.

위 조건에 맞다면, <encoding> 함수가 호출되고, 입력한 문자열을 encoding 한다.

그 후, encoding된 문자열과 저장된 문자열과 비교한다.

접근방법

문제 풀이에 가장 중요한 <encoding> 함수를 분석해보자.

<encoding> 함수의 전문이다. 위에서 부터 천천히 훑어보자.

malloc 받은 주소를 [rbp-0x8]에 저장하고, 입력한 문자열([rbp-0x28])의 길이를 [rbp-0xc]에,

0x48을 [rbp-0x11]에, 0x0을 [rbp-0x10]에 저장한다.

이후, +161로 jmp하게 되는데, 이 부분은 많이 보던 반복문 형식이다.

그러므로, for(i = 0; i < strlen(입력한 문자열); i++) 를 나타낸다.

rbp-0x28 : 입력한 문자열(이하 s)
rbp-0xc  : len(s)
rbp-0x10 : for iterator(이하 i)
rbp-0x8  : malloc에서 받은 주소
rbp-0x11 : 0x48

---

이제, 반복문 안에서 반복되는 내용을 살펴보자. 여기서, 입력값은 "AAAAAAAAAAAAAAAA"로 하자.

1.

위의 assembly code를 수식으로 표현하면 다음과 같다.

g1 = ('A'(0x41) + 0xc) * 0x48

---

2.

위 1번의 결과값을 0xea0ea0eb와 곱셈연산하여 eax에 저장한다. (imul에서 인자가 1개일 경우 eax *= edx 이다.)

+109는 eax * edx 값의 상위 4바이트 값을 가져오기 위함이다.

ex) eax * edx 값의 결과값이 0x13dc57c590d3 라면, 32bits register에서 나타낼 수 있는 최대 값(0xffffffff) 을 넘어선다. 여기서 상위 4바이트 값을 취하려면 "결과값 + eax" 해주면 된다.

그리고, 곱셈 결과값의 상위 4바이트 값을 6만큼 rshift연산한다.

위의 assembly code를 수식으로 표현하면 다음과 같다.

g1 = ('A'(0x41) + 0xc) * 0x48
g2 = g1 * 0xea0ea0eb
g2 = op.rshift(op.rshift(g2, 32), 6)

---

3.

위 2번의 결과값을 0x46 곱한 후, 1번의 결과값에서 sub 연산을 수행한다. 그 후, 0x30만큼 더해준다.

이 값이 최종적인 <encoding> 함수에서 for문의 첫번째 결과값이다.

위의 assembly code를 수식으로 표현하면 다음과 같다.

g1 = ('A'(0x41) + 0xc) * 0x48
g2 = g1 * 0xea0ea0eb
g2 = op.rshift(op.rshift(g2, 32), 6)
result = (g1 - (g2 * 0x46)) + 0x30

---

4.

해당 결과값을 +136~+151 을 통해 malloc에서 할당받은 주소(결과값)에 넣고, rbp-0x11에 도 마찬가지로 넣어준다.

 

이 말은, for문이 len(입력문자열) 만큼 돌면서, rbp-0x11값이 단계마다 계속해서 변화한다는 의미이다.

 

풀이

그렇기에, 우리는 평문을 모르고, encoding방법과 encoding문자열을 알기에, 다음과 같은 프로그램을 통해서 평문을 유추할 수 있다.

import operator as op

result = ""
target = "ABCDEFGHKJKLMNOPQRSTUVWXYZabcdefghkjklmnopqrstuvwxyz0123456789!@#$%^&*()-_+=,.<>\/?;:[{]}"
answer = "OO]oUU2U<sU2UsUsK"
changer = 0x48

def fnc(s):
    g1 = ((s + 0xc) * changer) + 0x11
    g2 = g1 * 0xea0ea0eb
    g2 = op.rshift(op.rshift(g2, 32), 6)
    g2 = g2 - op.rshift(g1, 31)
    return (g1 - (g2 * 0x46)) + 0x30


for i, a in enumerate(answer):
    for t in target:
        r = fnc(ord(t))		# brute force
        if chr(r) == a and i < len(answer) - 1:		# encoding된 문자열과
            result += t					# brute force한 문자열과 같을 경우
            changer = r					# 결과값을 다음 encoding때 사용
            break

print(result)

※ 여기서 i < len(answer) - 1 해준 이유는 평문을 입력할때 줄바꿈문자('\n'->0x0a)가 들어가기 때문이다.

 

Get Flag!