[UIUCTF 2018] xoracle (250)

이번 UIUCTF에서 못다푼 xoracle을 이번에 다시 한번 풀어보기로 했다.

이미 서버가 닫혀버렸으므로 가상서버에서 구축하여서 다시 풀어보기로 하였다.

(서버구축에 관한 내용은 이쪽 참고)

참고로 파이썬은 이렇게 추가해줘야한다.

service xoracle
{
          disable         = no
          flags           = REUSE
          socket_type     = stream
          protocol        = tcp
          wait            = no
          user            = sherlock
          server          = /usr/bin/python3
          server_args     = /home/sherlock/workstation/2018_CTF/UIUCTF/xoracle/xoracle.py
}
 

xoracle ● Crypto ● 250 Points

#!/usr/bin/env python3
from random import randint
from base64 import b64encode
 
def xor(data, key):
    out = b''
    for n in range(len(data)):
        out += bytes([data[n] ^ key[n % len(key)]])
    return out
 
def randkey():
    key = b''
    for n in range(randint(128, 255)):
        key += bytes([randint(0, 255)])
    return key
 
if __name__ == "__main__":
    with open('flag', 'rb') as f:
        data = f.read()
    print(b64encode(xor(data, randkey())).decode("utf-8"))

zip파일 나온 것 복구과정 - WriteUp1, WriteUp2

두사람 writeup에 차이가 나는 이유를 알았다.

writeup1에서는 주어진 암호문의 해독한 길이를 1536으로 보았다. (실제로 서버에서 1536의 길이만 받은것같다.)^[각주:1]

writeup2에서는 주어진 암호문을 해독하여 나온 길이를 2039로 본다.(나도 복호화한 결과 길이가 2039였다.)

그래서 결과적으로 w1과 w2에서 서로 조금씩 다른 파일들을 해독하였고... w2에 있는 분이 더 정확한 파일을 얻게된것이다.

나는 w1의 것을 w2의 2039를 받는것으로 해서 writeup을 재구성해보겠다.

먼저 이론을 다시 한번 정리하면 아래와 같다.

Solution

1.  먼저 키를 모르고 암호문인 C만 알고 있을 때, 여기서 키만 남기고 이 키의 길이를 어떻게 정의하느냐를 알아야한다.

nc를 통해서 받게 되는 암호문 C를 base64로 복호화해보면 길이가 2039인것을 알 수 있다. 그리고 중요한 키 K의 길이는 128~255의 범위에 있고 만약 우리가 같은 길이를 가진 키 k1과 k2가 반복되어 얻어진 OTP인 K1와 K2로 암호화된 C1, C2를 가지고 있다면 키 길이를 유추할 수 가 있다.(키값은 서로 다르다, 같은것은 길이 뿐)

K1 XOR K2 은 2039길이를 가지고 있고, 이 안에는 128-255 의 길이를 가지는 k1 XOR k2가 반복되어지고 있을 것이다.

그러므로 우리는 다음 파이썬 코드를 가지고 키길이가 각각 128-255인 암호문을 128개 얻을 수 있다.

from base64 import b64decode
from socket import socket
 
ADDR = 'localhost', 7777
KEY_LEN = 128
 
def get_msg():
    while True:
        with socket() as s:
            s.connect(ADDR)
            msg = b64decode(s.recv(3000))
        if len(msg) == 2039:
            return msg
 
def xor_bytetrings(a, b):
    return bytes((x^y for x,y in zip(a,b)))
 
def find_msgs():
    msgs ={get_msg()}
    needed = set(range(128))
 
    while needed:
        print(len(msgs), needed)
        new_msg = get_msg()
        for msg in list(msgs):
            xor_key = xor_bytetrings(new_msg, msg)
            good_part, last_part = xor_key[:KEY_LEN], xor_key[KEY_LEN:]
 
            if good_part in last_part:
                i = last_part.index(good_part)
                print('\t', i)
                if i in needed:
                    yield (i+KEY_LEN, new_msg)
                    needed -= {i}
                    msgs -= {msg}
                    continue
        msgs.add(new_msg)
 
if __name__ == "__main__":
### STEP 1. find key_length and Save
    for i, text in find_msgs():
        with open('key_{0:0>3}_c'.format(i), 'wb') as f:
            f.write(text)
 
# yeild : http://kkamikoon.tistory.com/90  , https://dojang.io/mod/page/view.php?id=1119
 
 

---

2. 자 이제 우리는 암호문 C와 그 암호화에 쓰인 키 K의 길이를 알고 있다. 키 길이를 len이라고 할 때 암호문 C를 len길이씩 짤라서 n개의 블록과 M을 len으로 나눈 n개의 블록 다음과 같이 표시 할 수 있다.

그리고 이 연산 c1 xor c2를 통해 키 K를 암호문에서 제거하여 평문 m블록의 연산으로만 바꿀수 있다. 이것이 키 길이를 알 때, 바로 암호문의 자신들끼리 곱하여 암호문에서 키를 소거하는 방법이다.

---

3. 이제 키 길이가 서로 1차이가 나는 암호문 C1 과 C2 를 가져오자. 이 들의 키를 각각 K1,K2  [|K1-K2|=1이다.  여기서 기억할 것은 우리가 XOR할 것은 M의 블록이란 것이다.

키 길이가 3인 C1과 키 길이가 4인 C2가 있다. 

c11 xor c12 = m11 xor m12 

c21 xor c22 = m21 xor m22 인것을 잊지말자.

위와 같이 계산되는 것이다! 키 길이가 1다른 것을 이용하여

M[1]^M[4]인 부분을 키길이가 3인 H1에서 가져오고, M[0]^M[4]인 부분을 키길이가 4인 H2에서 가져와

그 둘의 XOR결과로 M[0]^M[1]을 구할 수 있는 것이다. 

이 계산을 키 길이 128인 C1을 base로 두고 키길이가 각각 1,2,3,4,5씩 차이나는 C들을 가져와 위와 같은 계산을 하면 우리는 결국   M[0] XOR M[i] for all i in [1,128] 을 계산할 수 있다. (M[1]~M[127])

---

4. 이제 첫 평문 바이트 M[0]를 BruteForce를 통해 나머지 M[1]~M[127]을 구할 수 있고, 이 값을 이용해 키 길이가 128인 암호문과 XOR을 통해 128길이 키 K를 복구하여 평문메세지를 복호화할 수 있다.

import os
 
KEY_LEN = 128
FILE_LEN = 2039
 
def xor_bytetrings(a, b):
    return bytes((x^y for x,y in zip(a,b)))
 
def key2039_gen(key):
    key = key*(FILE_LEN // KEY_LEN)
    key += key[:FILE_LEN % KEY_LEN]
    return key
    
if __name__ == "__main__":
### STEP 2. Xor M1, M2 AND Genearte M[0]^M[i] (i=range(1,128)
    res = [0]
    with open('key_128_c', 'rb') as f: 
        original = f.read()
    
    for i in range(1,128):
        idx=i+KEY_LEN
        with open('key_{0:0>3}_c'.format(idx), 'rb') as f: 
            shifted = f.read()
        
        or_blocks = [original[KEY_LEN*x:KEY_LEN*(x+1)] for x in range(0,2)]
        sh_blocks = [shifted[(KEY_LEN+i)*x:(KEY_LEN+i)*(x+1)] for x in range(0,2)]
 
        H1 = xor_bytetrings(*or_blocks)
        H2 = xor_bytetrings(*sh_blocks)
 
        res.append(H1[i] ^ H2[0])
 
### STEP 3. Bruteforce M[0]
    for m0 in range(256):
        msg_first = [m0^x for x in res]
        key = xor_bytetrings(msg_first, original)
        key = key2039_gen(key);
        
        flag = xor_bytetrings(key, original)
        with open('flag_{0:0>3}'.format(m0), 'wb') as f:
            f.write(flag)
 
### STEP 4. file operation AND Find Real FLAG!
    for m0 in range(256):
        os.system('file flag_{0:0>3} | grep -v ": data"'.format(m0))
 
 
 
 

위 코드를 실행하면 아래와 같이 나온다.

flag_number에서 number은 M[0], 즉 첫바이트를 저값으로 하였을 때 나온 키값으로 복호화했을 때

파일 시그니처로 이렇다는 것이다.

만일 flag가 텍스트 파일이라면 아래와 같이 나온다.

sherlock@ubuntu:~/workstation/2018_CTF/UIUCTF/xoracle/my_writeup$ echo "hello world" > test
sherlock@ubuntu:~/workstation/2018_CTF/UIUCTF/xoracle/my_writeup$ file test
test: ASCII text

여기서 file 명령어를 통해 분석해본 결과로서 flag는 텍스트 파일이 아닌것같다.

가장 가능성있어보이는 것으로는 Zip archive data이나, 일단 한번 헥스값으로 비교해보겠다.

다른 파일들은 다 쓰레기값인것 같지만 flag_080은 뭔가 제대로된 파일헤더가 보인다. PK가 보이니 압축파일이겠고 또 f.bmp라는 문구도 보인다.

한번 unzip해보겠다.

CRC값이 다르다고 오류가 뜨긴하지만 성공적으로 f.bmp가 추출된것을 볼 수 있다.

성공~~ 굿... 굉장히 좋은 문제였다고 생각한다. 물론 CTF 당일에 풀었다면 정말 좋았겠지만..ㅠ

flag.zip

1. writeup1에서 풀이해주신분이 실수하신게 있다. 소스를 확인해보니 서버로 부터 recv(2<<10)를 하는데, 서버가 주는 문자열은 2800자 정도된다. 물론 그 문자열이 base64인코딩되어있어 이를 디코딩하게 되면 2039자가 나온다. 아마 여기서 헷갈리셔서 2<<10=2048자만 받으신거같다. 그래서 서버가 주는 문자열 2800자중에 2048만 받아가게 되어 파일크기가 1536이 된것같다. [본문으로]