[noxCTF] PlotTwist (Mersenne Twister)

내가 이 Plot Twist 문제의 롸업을 안올렸다니...

오랜만에 MT19937 Mersenne Twister RNG 에 관해서 다시 접하게되어서 저번에 noxCTF에 나왔던 관련 문제 롸업이나 보자! 하고 왔는데

내가 안올려놨었다 ㅡㅡ;;

나름 문제풀려고 고민고민하다가 검색을 통해서 관련 개념을 알게되서 푼 문제라서 롸업 올려놧을줄 알았는데;;

어찌됫든 기억난 김에 이렇게 써본다.

메르센 트위스터란 유사 난수 생성기이다. 메르센 트위스터의 이름은 난수의 반복 주기가 메르센 소수인 데에서 유래했다. 메르센 트위스터는 그 속도와 난수의 품질 때문에 점점 많은 곳에서 채택되고 있으며, 흔히 주기가 2^{19937}-1인 MT19937을 사용한다.  MT19937과 같으나 생성해 내는 난수가 32비트가 아닌 64비트인 MT19937-64도 쓰이며, 2006년에 동일한 저자들이 발표한 SIMD 기반 메르센 트위스터는 MT19937에 비해 대략 두 배 정도 빠른 것으로 알려져 있다. 난수의 품질에도 불구하고, 메르센 트위스터는 암호학적으로 안전한 유사난수 생성기가 아니다. 즉 난수의 특성(주기, 난수 범위)을 알고 있을 때 유한한 수의 난수(이 경우 624개)만으로 현재 생성기의 상태를 알아 낼 수 있으며, 그 뒤에 나올 난수를 예측해 낼 수 있다. 암호학적으로 안전한 유사난수 생성기를 얻기 위해서는 해시 함수를 사용해야 하지만 난수의 생성 속도가 낮아진다. 또는 블룸 블룸 슙(BBS)과 같이 암호학적으로 안전하게 설계된 생성기를 쓸 수도 있다.  출처 :: 위키피디아(메르센 트위스터)

문제는 아래와 같은 파일이 하나 주어진다.

import socket
import threading
import random
from Crypto.Cipher import AES
 
class ThreadedServer(object):
    def __init__(self, host, port):
        self.host = host
        self.port = port
        self.sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
        self.sock.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)
        self.sock.bind((self.host, self.port))
        self.flag = open('flag.txt', 'r').read()
 
    def listen(self):
        self.sock.listen(20)
        while True:
            client, address = self.sock.accept()
            client.settimeout(60)
            threading.Thread(target = self.listenToClient,args = (client,address)).start()
    
    def getKey(self, r):
        return str(r.getrandbits(32)).rjust(16, '0')
 
    def pad(self, s):
        return s + chr(0)*((-len(s)) % 16)
 
    def encrypt(self, key, plaintext):
        aes = AES.new(key, AES.MODE_CBC, self.pad('SuperSecretIV'))
        return aes.encrypt(self.pad(plaintext))        
 
    def decrypt(self, key, ciphertext):
        aes = AES.new(key, AES.MODE_CBC, self.pad('SuperSecretIV'))
        return aes.decrypt(ciphertext)
 
    def listenToClient(self, client, address):
        client_flag = self.flag
        r = random.Random()
        key = self.getKey(r)
        client_flag = self.encrypt(key, client_flag)
        while True:
            try:
                client.send('Please insert the decryption key:\n')
                key_guess = client.recv(16)
                if key_guess == key:
                    client.send('Correct! Your flag is: ' + self.decrypt(key, client_flag) + '\n')
                    client.close()
                    break
                else:
                    client.send('Wrong! The key was: ' + key + '\n')
                    client_flag = self.decrypt(key, client_flag)
                    key = self.getKey(r)
                    client_flag = self.encrypt(key, client_flag)
            except Exception as e:
                print e
                client.close()
                return False
 
if __name__ == "__main__":
    ThreadedServer('0.0.0.0', 5115).listen()
 

서버에 접속하면 키를 입력해달라고 하고, 올바른 키를 입력하면 플래그를 뿌려준다.

잘못된 키를 입력하면 틀렸다면서 방금 쓰인 암호화 key를 출력해주고, key는 새로 설정된다. 

여기서 r = random.Random()가 쓰이고 아래 함수를 통해 key를 획득하게 된다.

    def getKey(self, r):

        return str(r.getrandbits(32)).rjust(16, '0')

Python의 random은 메르센 트위스터로 되어있어, 624개의 난수만 뽑아낸다면 다음 난수를 예측할 수 있다.

그러므로 624번 틀려서 key값을 알아내어 다음 값을 알아내는 것이 가능하다.

여기서 Mersenne Twister Crack 소스를 짜면 아주 멋지겠지만... 이미 구현되어있는것들이 많으니.. 그것들을 가져와 사용하겠다.

https://github.com/tna0y/Python-random-module-cracker

설명도 아주 잘되어있다.

그냥 적혀있는대로 쓰면된다.

아래는 필자가 작성한 공격코드이다.

#!/usr/bin/env python
from pwn import *
import string
from randcrack import RandCrack
#https://github.com/tna0y/Python-random-module-cracker
 
 
conn = remote("chal.noxale.com", 5115)
 
def get_key(rc):
    conn.recvuntil("Please insert the decryption key:\n")
    conn.send("0"*16*624)
        
    for i in range(624):
        conn.recvuntil("Wrong! The key was: ")
        key = conn.recv(16)
        rc.submit(int(key))
        conn.recvuntil("Please insert the decryption key:\n")
 
    key = str(rc.predict_getrandbits(32)).rjust(16, '0')
    return key
 
rc = RandCrack()
key = get_key(rc)
conn.send(key)
 
conn.interactive()