2016 CodeGate Final GMPQZ

6명 푼 미스크 문제입니다.

이렇게 생긴 파일 하나 달랑 줍니다. 여기서 맨 앞에 있는 0x78 0x9c는 zlib이라는 압축 알고리즘의 시그니쳐 입니다. 내부에 시그니쳐가 많이 보이는 것으로 보아 여러개가 모여 있는 것 같습니다. 파이썬 소스를 짜서 몽땅 압축을 풀어 줍니다.

file = open('GMPQZ', 'rb').read().split('\x78\x9c')
 
data = ''
for i in range(1, len(file)):
    data += ('\x78\x9c' + file[i]).decode('zlib')
open('decypted', 'wb').write(data)

처음에는 압축이 풀린 것을 하나하나 다른 파일에 저장했는데 열어서 확인해 보니 중간 중간 0x55 0xaa로 끝나는 파일들이 있어서 MBR을 분할 압축한 것이라 생각하고 파일 내용을 모두 모아서 한 파일로 만들었습니다. 0x55 0xaa는 부트코드가 담겨있는 MBR의 맨 끝에 있는 푸터입니다. 

0x55 0xaa로 끝나는 것을 볼 수 있습니다. 이러한 MBR이 총 다섯 개가 모여 있으며 이를 나눠서 qemu나 VM Ware로 부팅시켜보면 

이런 식으로 띄어쓰기가 없는 파이썬 코드가 한 줄씩 들어있어 총 5줄의 파이썬 코드가 나옵니다. 띄어쓰기를 적절히 넣어서 보면 

x = 0
for i in range(0, 7777777 + 1): x = x + 2 ** i
key=0
for i in range(len(str(x))): key += int(x[i])
print "flag{" + key + "}"

이런 소스가 나옵니다. 분석을 하면

2 ** 0 + 2 ** 1 + 2 ** 2 + 2 ** 3 + ... + 2 ** 7777777 을 구합니다. 이 값을 모두 x에 담고 이를 str형으로 변환하여 각 글자를 int형으로 변환한 값이 플래그입니다. 

우선 첫 번째 작업부터 시간이 엄청 걸릴 뿐만 아니라 값이 오버플로우 납니다. 따라서 이 부분을 살짝 변형해야 합니다. 먼저 2 ** 0 + 2 ** 1 + 2 **2 + ... 2 ** n은
(2 ** (n + 1)) - 1과 같은 값을 가집니다. 따라서 위의 반복문은 x = 2 ** 7777778 - 1이라는 코드로 바꿀 수 있습니다.

하지만 이 마저도 문제가 됩니다. 2 ** 77777778은 매우매우 큰 값으로써 파이썬에서 역시 오버플로우가 나는데 여기서 필요한 것이 gmpy모듈입니다. 문제 이름이 GMPQZ인 것으로 보아 gmpy모듈 사용을 의도한 것 같습니다. 따라서 위 연산을 gmpy모듈로 연산을 하면 약 1초만에 플래그를 구할 수 있습니다. 

import gmpy2
 
x = gmpy2.mpz(2) ** gmpy2.mpz(7777778) - 1
key = 0
for i in range(len(str(x))): key += int(x[i])
print key

이 코드를 실행하면 플래그가 나옵니다.

key : 2341345