2014 화이트햇 콘테스트 crypto100(Cold war) Writeup

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

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