유메의 티스토리

다음과 같은 사진이 주어지고, 이 근처 STARBUCKS의 주소를 찾는 문제이다.

처음에 "의주찹쌀순대" 간판을 구글링해보니 신의주찹쌀순대가 나와서 이를 네이버에 검색해보니 검색 결과가 너무 많았다.

그렇게 살펴보다가 사진관의 전화번호가 보일락말락해서 542-4858으로 검색해보니 강남구의 사진관이 바로 나왔다.

길찾기로 이 근처 스타벅스를 검색해보니 주소가 삼성동 91-31로 바로 나왔다.

FLAG: 91-31

다음과 같은 암호와 소스가 주어진다.

crypto.txt

fee304acd551a17fbd3b7f23c1e51fba9c55a93de43d797187fc1eaa9055ba74fc3e2c62d4ac10fe864fbb79f83c7822
f0e414aa9d5ebc3df2202c6dc8f85197d54caf6ebd267971c9e51fb9d54fa678bd226d64c2ff51aa9a5faf64bd332c60c6e014b0915abc3df4212c64c8e51fb9d554b878ef732d22
eeac15b1d555a169bd316d71c2ac10fe965aa27ee83e7970
f7e903ad9a55ee6ff8226962d3ff51b39c48ba7cf6372c62c9e851999a5fee7bf2206b6ad1e902fe9852bd69fc396922
eeac05b69c55a53de93a6923c9ed05b79a55af71bd337f70c2e113b28c1bb974f13e2c61c2ac15bb8652a973fc26696787ed02fe941ba67ce7337e67c8f902fe9954ad7ce93b636d
f3e414ad901ba972f2362c70c6f518b0921ba86ff23f2c50cfe51ffebd5aab3dde3a796f
f3e414fe9e5eb73df4212c6287ff19bfc41bb87cf1276923c8ea51aa9d5eee73fc3f6922
fee304fe8252a271bd20696ec6e51ffe9c55ee70e4726466c6fe05fe9354bc78eb377e22

crypto.py

# crypto.py
import random

def g(l):
    r = "".join(chr(random.randint(0, 0xff)) for idx in xrange(l))
    return r

def e(r, p):
    ret = ""
    if len(p) % len(r) == 0:
        c = len(p) / len(r)
        for idx in xrange(c):
            for (c1, c2) in zip(r, p[idx * len(r):(idx + 1) * len(r)]):
                ret += ''.join(chr(ord(c1) ^ ord(c2))) 
    else:
        print "[+] Error"
    return ret

if __name__ == "__main__":
    c = g(n)
    ps = [l.rstrip('\n') for l in open("input_messages")]
    ret = []

    for p in ps:
        ret.append(e(c, p).encode('hex'))

    print c.encode('hex')
    print ret

nByte 랜덤 키 c를 생성한 뒤 plaintext와 XOR을 한다.

이 때 plaintext의 길이가 키 길이의 배수가 아니면 reject하고, 배수이면 랜덤 키를 plaintext 길이와 맞도록 키를 반복한다.

예를 들어 plaintext가 Hello, I am yum3(16Byte)이고 key가 xy(2Byte)라면 다음과 같다.

plaintext  : H  e  l  l  o  ,     I     a  m     y  u  m  3

       key : x  y  x  y  x  y  x  y  x  y  x  y  x  y  x  y

ciphertext : 30 1c 14 15 17 55 58 30 58 18 15 59 01 0c 15 4a (hex encoded)

이는 repeated xor문제이다. 같은 키가 반복해서(repeated) xor되는 것이다.

키의 길이를 구한 뒤, single-byte xor(한 byte씩 xor)해가면서 문장을 보는 것이다.

암호문을 살펴보면 각각 48Byte, 72Byte, 24Byte, 48Byte, 72Byte, 36Byte, 36Byte, 36Byte이므로 키의 길이는 이들의 공약수여야 한다. 후보로는 1, 2, 3, 4, 6, 12가 있다.

key의 길이를 구하기 위해 Hamming Distance를 구해보자. Hamming Distance란 길이가 같은 두 이진수(binary)에 대하여 각 자리수의 비트가 서로 다른 것의 개수다. 예를들어 11011과 11000의 Hamming Distance는 2다. 이 를 구하는 방법은 두 binary를 XOR한 뒤 1의 개수를 세는 것과 같다. (두 비트가 1과 0, 0과 1로 다를 때 XOR값이 1이 나온다는 것에 착안한 것이다. 11011과 11000의 XOR은 00011이고, 1이 2개 있으므로 2이다.)

key의 길이를 추측할 때, ciphertext를 1Byte, 2Byte, 3Byte, ... 등 shift한 shifted ciphertext와 원래의 ciphertext의 Hamming Distance를 각각 구한것 중 Hamming Distance가 낮게 나오는 것을 key의 길이로 잡을 수 있다.

위의 ciphertext를 예로 들어보자. 1Byte와 2Byte를 shift한 뒤 각각의 원본 ciphertext와 Hamming Distance를 구하면 다음과 같다. (구분을 위해 원본 ciphertext의 첫번째 Byte에 빨간색으로 칠했다.)

     ciphertext : 30 1c 14 15 17 55 58 30 58 18 15 59 01 0c 15 4a

  1Byte shifted : 4a 30 1c 14 15 17 55 58 30 58 18 15 59 01 0c 15

Hamming Distance: 5  3  1  1  1  2  3  3  3  1  3  3  3  3  3  6   Sum: 44

  2Byte shifted : 15 4a 30 1c 14 15 17 55 58 30 58 18 15 59 01 0c

Hamming Distance: 3  4  2  2  2  1  5  4  0  2  4  2  2  4  2  3   Sum: 42

이 중 Hamming Distance가 작은 것이 2Byte shifted이므로 키는 2Byte일 확률이 높다.

지금은 메시지의 길이가 짧아서 Hamming Distance가 큰 차이가 나지 않는데, 문제의 암호로 계산을 해보면 큰 차이가 나는 것을 확인할 수 있다.

key는 모든 문장에 대해 동일하므로, 모든 문장을 이어붙인 뒤 계산했다.

# -*- coding: cp949 -*-
def hamming_distance(c, keylen):
    HD=0
    for i,j in zip(c, c[-keylen:] + c): # c와 c를 keylength만큼 shift한 것
        HD += bin(ord(i)^ord(j))[2:].count('1')
    return HD

f = open('crypto.txt', 'rt')
c = ''
for line in f.xreadlines():
    c += line.rstrip() # 문장 이어붙이기

c = c.decode('hex')

for i in [1, 2, 3, 4, 6, 12]:
    print i, hamming_distance(c, i)

결과는 다음과 같다.

1 1538

2 1418

3 1430

4 1564

6 1610

12 964

12일 때 확연히 Hamming Distance가 작은 것을 볼 수 있고, key의 길이는 12Byte일 확률이 높다.

12Byte씩 자른 뒤 한 글자씩 0부터 255까지 XOR한 뒤 영어와 일반적인 특수문자로 구상된 결과를 key로 뽑아내자.

12Byte씩 자르면 아래와 같이 나온다. 

fee304acd551a17fbd3b7f23
c1e51fba9c55a93de43d7971
87fc1eaa9055ba74fc3e2c62
d4ac10fe864fbb79f83c7822
f0e414aa9d5ebc3df2202c6d
c8f85197d54caf6ebd267971
c9e51fb9d54fa678bd226d64
...

여기서 첫 Byte인 fe, c1, 87, ...를 따온 뒤 0부터 255까지 XOR하고 살펴보면 167과 XOR했을 때 결과가 다음과 같다.

Yf sWoneaoIePtnvInee oTahT oYaa

(나머지는 영어가 아닌 괴상한 문자가 많이 섞여있다.)

이와 같은 방식으로 12번을 반복한다.

f = open('crypto.txt', 'rt')
c = ''
for line in f.xreadlines():
    c += line.rstrip()
f.close()
c = c.decode('hex')

def divide_into_stream(c, keylen):
    stream = []
    for i in xrange(keylen):
        stream.append(c[i::keylen])
    return stream

s = divide_into_stream(c, 12) # s[0]: 첫번째 Byte만 모아둠. s[1]: 두번째 Byte만 모아둠. ...

for n,each_stream in enumerate(s):
    f = open('decrypted%d.txt' % n, 'wt')
    for j in xrange(256):
        f.write('='*50 + str(j) + '\n')
        decrypted_text = ''
        for k in each_stream:
            decrypted_text += chr(j^ord(k))
        f.write(decrypted_text+'\n')
    f.close()

decrypted0.txt부터 11.txt까지 영어와 스페이스바로 많이 이루어진 key값을 찾는다.

key = [167, 140, 113, 222, 245, 59, 206, 29, 157, 82, 12, 3]

이를 이용해 ciphertext 복호화하면 원래의 message가 나온다.

f = open('crypto.txt', 'rt')
c = ''
for line in f.xreadlines():
    c += line.rstrip()
f.close()
c = c.decode('hex')

key = [167, 140, 113, 222, 245, 59, 206, 29, 157, 82, 12, 3]

d = ''
for n,i in enumerate(c):
    d += chr(ord(i) ^ key[n%len(key)])

print d

Your job is finding your potential as a student!Whether or not I was turning the pages today a calendar is going over!!!I do not care a calculusPerson repeats mistake and God forgives mistake!I think the national assembly will be designated as a hazardous locationThese good saying from Shin Hae ChulThe key is a sha1 value of the name!You will remain in my heart forever!

Shin Hae Chul을 sha1 hash하면 FLAG이다.

FLAG: 43722cf51b6539c298fdb0f78ed987f05a826d2c

이 문제는 직접 flag.txt를 읽거나 shell을 따는 게 아니라 형식만 잘 맞춰준 뒤 flag.txt를 읽어주는 함수를 부르면 된다.

개인적으로 Exploitation 300점보다 수월하게 풀 수 있었다.

다음과 같은 바이너리가 주어진다.

saturn

메뉴에서 1byte를 읽고(이하 input이라 칭함), 0xF0과 AND를 해서(1byte중 상위 4bit만 남는다) 0xA0, 0xE0, 0x80 중 어디에 속하는지 정한 뒤 각 메뉴에 알맞는 함수를 부른다.

0xA0일 때 실행되는 0x804885c 함수는 input & 0x0F(1byte중 하위 4bit만 남는다)를 0x804a050가 가리키는 곳에 더한 뒤 이 메모리에 있는 4byte를 출력한다. 0x804a050이 가리키는 곳은 0x804a0c0이다.

즉 0x804a0c0 + 4*(input & 0x0F)를 출력해준다. 4를 곱하는 이유는 DWORD(4byte) 단위로 되어있기 때문이다.

0xE0일 때 실행되는 0x80488e8 함수는 input & 0x0F를 0x804a054가 가리키는 곳에 더한 뒤 그 메모리 값과, 새로 stdin에서 4byte를 읽은 뒤 비교한다. 값이 다르면 exit을 하고, 값이 같으면 0x804a0a0 + (input & 0x0F)를 1로 만들어준다.

0x804a054가 가리키는 곳은 0x804A0E0이다.

마지막으로 0x80일 때 실행되는 0x8048a01 함수는 0x80487ed 함수의 반환값이 0이면 프로그램을 종료하고, 그렇지 않으면 flag.txt를 읽어서 출력해준다.

즉 flag를 출력하게 하기 위해선 0x80487ed의 반환값을 0이 아닌 값으로 만들어줘야 한다.

이 함수를 살펴보자.

매우 간단하다. 0x804a0a0+4*0부터 0x804a0a0+4*7까지 값을 모두 곱한 뒤 반환한다.

이 값들은 초기값이 모두 0이라 아무 작업을 해주지 않으면 0을 반환할 것이고, flag.txt를 읽을 수 없게 된다.

아까 2번째 메뉴에서 실행됐던 0x80488e8 함수에서 0x804a0a0 + 4*(input & 0x0F)를 1로 만들어주니, 이를 이용해 0x804a0a0+4*0부터 0x804a0a0+4*7를 모두 1로 만들어줄 수 있을 것이다.

하지만 이를 위해서는 0x804a0e0 + 4*(input & 0x0F)값을 알아야할 필요가 있다(이 값과 비교해서 다르면 exit하므로). 이 때 0x80488e8 함수를 이용한다.

이 함수에서는 0x804a0c0 + 4*(input & 0x0F)를 출력해준다. 즉, "\xa8"을 넣게 되면 0x804a0e0값을 출력해준다. 이렇게 "\xaf"까지 보내서 값을 알아낸 뒤 "\xe0", ..., "\xe7"을 보내서 알아낸 값을 넣어주고 "\x80"을 호출하면 된다.

정리해보면 다음과 같다.

"\xa8\xa9\xaa\xab\xac\xad\xae\axf" = >반환값

"\xe0" + 반환값[0:4] + "\xe1" + 반환값[4:8] + ... + "\xe7" + 반환값[28:32]

"\x80"

다음은 최종 exploit code이다.

from socket import *
from time import sleep

s = socket(2,1)
s.connect(('54.85.89.65',8888))

s.recv(256)
t=''
for ai in xrange(8,16):
	t += chr(0xa0+ai)

s.send(t)
sleep(1)
data = s.recv(256)
print data.encode('hex')

t2 = ''
for ei in xrange(8):
	t2 += chr(0xe0+ei)+data[ei*4:ei*4+4]

s.send(t2)
print t2.encode('hex')
s.send('\x80')
sleep(.7)
print s.recv(128)

s.close()