[Dreamhack] Exploit Tech: Meet-in-the-middle Attack

 

prob.py

#!/usr/bin/env python3
from Crypto.Cipher import DES
import signal
import os

if __name__ == "__main__":
    signal.alarm(15)

    with open("flag", "rb") as f:
        flag = f.read()
    
    key = b'Dream_' + os.urandom(4) + b'Hacker'
    key1 = key[:8]
    key2 = key[8:]
    print("4-byte Brute-forcing is easy. But can you do it in 15 seconds?")
    cipher1 = DES.new(key1, DES.MODE_ECB)
    cipher2 = DES.new(key2, DES.MODE_ECB)
    encrypt = lambda x: cipher2.encrypt(cipher1.encrypt(x))
    decrypt = lambda x: cipher1.decrypt(cipher2.decrypt(x))

    print(f"Hint for you :> {encrypt(b'DreamHack_blocks').hex()}")

    msg = bytes.fromhex(input("Send your encrypted message(hex) > "))
    if decrypt(msg) == b'give_me_the_flag':
        print(flag)
    else:
        print("Nope!")

 

코드 분석

• signal.alarm(15) : 15초의 제한 시간
• key = b'Dream_' + os.urandom(4) + b'Hacker' : 미지의 4byte가 껴있는 16byte의 키를 생성

 

os.urandom 함수

• /dev/urandom이 만들어내는 난수
• CSPRNG(Cryptographically Secure Pesudorandom Number Generator) → 값 예측 어려운 난수
• 아무런 정보 없이 이 값을 예측하는 것은 불가능

• key1 = key[:8], key2 = key[8:]
• 각각 8바이트짜리 DES 키예요.

• cipher1 = DES 객체 (key1과 ECB 모드로 동작)
• cipher2 = DES 객체 (key2와 ECB 모드로 동작)

 

DES

• 대칭키 암호
• 키를 알면 암복호화 모두 가능
• 키를 모르면 둘 중 어느 것도 불가능

DES.MODE_ECB

• DES의 동작 모드 지정
• ECB(Electronic Codebook) 모드 = 가장 단순한 블록 암호 모드

 

encrypt = lambda x: cipher2.encrypt(cipher1.encrypt(x))
decrypt = lambda x: cipher1.decrypt(cipher2.decrypt(x))

• 암호화 → cipher1으로 암호화하고 cipher2로 암호화
• 복호화 → cipher2로 복호화하고 cipher1으로 복호화

 

print(f"Hint for you :> {encrypt(b'DreamHack_blocks').hex()}")

• b'DreamHack_blocks'가 암호화된 결과를 힌트로 줌

⇒ 이걸 이용해서 key1, key2의 미지의 2byte를 복구하는 것이 목표

 

Exploit 설계

Exhaustive search 전수 조사

• 모든 가능한 값을 대입해서 올바른 입력값을 찾는 것

 

키의 미지 바이트는 총 4byte = 32bit ⇒ 232232가지의 키가 존재함

from pwn import *
from Crypto.Cipher import DES
from tqdm import trange

io = process(["python3", "prob.py"]) #로컬에서 prob.py 실행

io.recvuntil(b":> ") #:>라는 문자열이 나올 때까지 읽어들임
hint = bytes.fromhex(io.recvline().decode())
#그 다음에 나오는 힌트(hex문자열)을 받아서 바이트열로 변환

for i in trange(2**32): #2^{32}번 반복
    key = b'Dream_' + i.to_bytes(4, "big") + b'Hacker'
    #미지의 4byte 부분에 정수 i를 4byte big-endian 바이트로 변환
    #즉 0부터 2^32-1까지의 숫자를 4byte big-endian 바이트로 변환해서 집어 넣음
    
    key1 = key[:8]
    key2 = key[8:]
    cipher1 = DES.new(key1, DES.MODE_ECB)
    cipher2 = DES.new(key2, DES.MODE_ECB)
    if cipher2.encrypt(cipher1.encrypt(b'DreamHack_blocks')) == hint:
        print("Success")
        break

 

⇒ 많은 시간이 필요함

 

[ 컴퓨터의 연산 능력 ]

• 개인 컴퓨터의 경우 232232회의 사칙연산은 1분 내외로 가능
• 하지만, DES와 같은 여러 회의 연산으로 이루어진 암복호화 연산의 경우 훨씬 오래걸림
• 슈퍼 컴퓨터의 경우 264264회 연산도 가능함 → 64bit = 8btye 전수 조사 가능
• 따라서, DES 대칭키 암호가 더이상 사용되지 않음
• 21282128회 연산은 불가능 → 16byte 이상의 키를 가지는 AES 대칭키 암호는 전수 조사 x

Meet-in-the-Middle Attack

지금 알고있는 건 평문 A = b'DreamHack_blocks'와 암호문 B (힌트 값)

key1, key2 각각 8바이트인데, 그 안에 2바이트만 모름

따라서, 각 키의 후보 키 개수 = 216216 = 6553665536

 

모든 키 조합 (key1,key2)(key1,key2)를 다 해보면 65536∗65536=23265536∗65536=232 ⇒ 너무 오래걸림

그래서 가운데에서 만나자!

 

1. 모든 가능한 key1에 대해서 cipher1.encrypt(A)를 계산
2. 모든 가능한 key2에 대해서 cipher2.decrypt(B)를 계산
3. cipher1.encrypt(A) = cipher2.decrypt(B)인 key1, key2를 찾기

 

Exploit

 

python의 dict

dict ⇒ key와 value를 가지는 python 자료형

from pwn import *
from Crypto.Cipher import DES

io = process(["python3", "prob.py"])
# io = remote("host3.dreamhack.games", 18664)

io.recvuntil(b":> ")
hint = bytes.fromhex(io.recvline().decode())

conflict = dict()

#key1 -> 모든 key1 후보에 대한 encrypt 값을 dict에 저장
for i in range(65536):
    b = i.to_bytes(2, "big")
    cipher = DES.new(b"Dream_" + b, DES.MODE_ECB) #key1 = b"Dream_"+ b
    enc = cipher.encrypt(b"DreamHack_blocks") 
    conflict[enc] = b"Dream_" + b #enc를 key로, key1을 value로 dict에 저장

#key2 -> 모든 key2 후보에 대한 decrypt 값 계산 -> dict에 저장된 결과랑 비교
for i in range(65536):
    b = i.to_bytes(2, "big")
    cipher = DES.new(b + b"Hacker", DES.MODE_ECB)
    dec = cipher.decrypt(hint)

    if dec in conflict:
        key1 = conflict[dec] #dict의 key 값 중 decrypt(dec)값와 일치하는 것이 있으면 value값을 가져옴
        key2 = b + b"Hacker" #그 때의 key2값도 저장
        break

cipher1 = DES.new(key1, DES.MODE_ECB)
cipher2 = DES.new(key2, DES.MODE_ECB)
encrypt = lambda x: cipher2.encrypt(cipher1.encrypt(x))
assert encrypt(b"DreamHack_blocks") == hint

io.sendlineafter(b'> ', encrypt(b"give_me_the_flag").hex().encode())

flag = eval(io.recvline())
io.close()

print(flag.decode())