[Dream Hack - Crypto] Double DES

Double Encryption

암호키 전수조사가 가능하다면? 암호키 크기를 늘이면 된다!

암호 알고리즘 Cipher1 = Enc(Plan, key1)
강화된 알고리즘 : Cipher2 = Enc(Cipher1, key2)
블록 크기는 그대로, 암호키 크기는 2배로 강화하였다.

 

과연 두배의 안정성을 가질까?

Cipher1 = Enc(Plan, key1) → 키 크기 2^n 일 때, Cipher2 = Enc(Cipher1, key2) → 키 크기 2^2n을 기대하지만 MITM attack 을 이용하면 2^(n+1)로 공격이 가능하다.

MITM (Meet In The Middle) 이란?

주어진 (평문(P), 암호문(C)) 쌍에 대하여, 암호키 key1, key2를 찾는 공격

평문 P 를 가능한 모든 key1으로 암호화 하여 사전에 저장한다.

암호문 C를 가능한 모든 key2로 복호화 하여 저장한 사전에서 찾는다.

 

풀이 과정

from Crypto.Cipher import DES 
import signal 
import os 

if __name__ == "__main__":
    # 프로그램을 15초 후에 종료하도록 알람 설정
    signal.alarm(15)

    with open("flag", "rb") as f:
        flag = f.read()
    
    ## key : 'Dream_' + 4바이트의 랜덤  + 'Hacker'
    key = b'Dream_' + os.urandom(4) + b'Hacker'

		## key 를 8byte 씩 나눔
    key1 = key[:8]
    key2 = key[8:]
    
    print("4-byte Brute-forcing is easy. But can you do it in 15 seconds?")
    
    # key1, key2를 사용하는 DES 오라클 생성
    cipher1 = DES.new(key1, DES.MODE_ECB)
    cipher2 = DES.new(key2, DES.MODE_ECB)
    
    # Double Encryption 암복호화 함수 정의
    encrypt = lambda x: cipher2.encrypt(cipher1.encrypt(x))
    decrypt = lambda x: cipher1.decrypt(cipher2.decrypt(x))

    # 'DreamHack_blocks'를 Double Encryption 한 암호문 제공
    print(f"Hint for you :> {encrypt(b'DreamHack_blocks').hex()}")

    # 아래의 'give_me_the_flag'의 암호문을 전달하면 flag를 얻는 형색
    msg = bytes.fromhex(input("Send your encrypted message(hex) > "))
    
    if decrypt(msg) == b'give_me_the_flag':
        print(flag)
    else:
        print("Nope!")

1. Cipher1의 키 2바이트를 모두 대입하여 b‘DreamHack_blocks’를 암호환 값을 사전에 저장한다. 사전에는 { 암호문 : 2바이트 키} 형태로 저장한다.
2. 통신으로 암호문을 받고, cipher2의 키 2바이트를 대입하여 복호화한다. 이 값이 1에서 만든 사전에 있으면 그 때, 사전의 2 바이트 키 값과, cipher2를 복호화한 키 값을 전체키로 확정한다.
3. 앞의 방법으로 찾은 키를 사용하여 b‘give_me_the_flag’를 암호환 값을 서버로 전달한다.

 

풀이 코드

from Crypto.Cipher import DES
from pwn import * 

key = b'Dream_' + bytearray(4) + b'Hacker'  # 키 형식 정의: 'Dream_' + 4바이트의 빈 바이트 배열 + 'Hacker'

# key1의 부분을 브루트포싱하여 모든 가능한 값에 대해 암호화된 텍스트를 저장
m = {}
for i in range(0, 256 * 256):
    key1 = key[:6] + int.to_bytes(i, 2, 'big')
    cipher1 = DES.new(key1, DES.MODE_ECB)
    cipher_text = cipher1.encrypt(b'DreamHack_blocks')  # 'DreamHack_blocks' 문자열 암호화
    m[cipher_text] = int.to_bytes(i, 2, 'big')  # {"key1로 암호화된 암호문", "key1의 "}

r = remote('host3.dreamhack.games', 18638)
data = r.recvline()
data = r.recvline()[16: -1]
print(data)

# 16진수로 된 암호화된 값을 바이트 배열로 변환
cipher_text3 = int.to_bytes(int(data, 16), 16, 'big')
ans = 0
# key2를 브루트포싱하여 복호화한 값이 딕셔너리에 있는지 확인.
for i in range(0, 256 * 256):
    key2 = int.to_bytes(i, 2, 'big') + key[10:]
    cipher2 = DES.new(key2, DES.MODE_ECB)
    cipher_text2 = cipher2.decrypt(cipher_text3)
    if cipher_text2 in m:
        ans = m.get(cipher_text2) + int.to_bytes(i, 2, 'big')

# 두 개의 키 부분으로 DES 암호 객체 생성
cipher1 = DES.new(key[:6] + ans[:2], DES.MODE_ECB)
cipher2 = DES.new(ans[2:] + key[10:], DES.MODE_ECB)
# 'give_me_the_flag' 문자열을 이중 DES로 암호화
send_msg = cipher2.encrypt(cipher1.encrypt(b'give_me_the_flag'))

print(send_msg.hex())
r.sendline(send_msg.hex().encode('ascii')) 
r.interactive()