Cryptography | Double DES _ Exploit : Meet-in-the-middle Attack

 

 

Level 1 | Double DES

https://dreamhack.io/wargame/challenges/1118

Double DES

 

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!")

 

 

🔎 코드 분석

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

if __name__ == "__main__":
    signal.alarm(15) #제한 시간 15초

    with open("flag", "rb") as f:
        flag = f.read()
    
    key = b'Dream_' + os.urandom(4) + b'Hacker' #Dream_ + 임의의 4바이트 + Hacker 총 16바이트 
    key1 = key[:8] #key의 앞 8바이트, 미지의 2바이트
    key2 = key[8:] #key의 뒤 8바이트, 미지의 2바이트
    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)) #암호화 > cipher1 사용 암호화
    decrypt = lambda x: cipher1.decrypt(cipher2.decrypt(x)) #복호화 > cipher2 사용 복호화 (=cipher2 암호화 후 cipher1 복호화)

    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!")

 

• siganl 함수 관련

https://growd.tistory.com/57

[Python] Python 일정 시간 후 timeout 에러 내는 방법

 

• 난수 생성 관련 

https://docs.python.org/ko/3.10/library/random.html

random — 의사 난수 생성 — Python 3.10.13 문서

 

➕ os.urandom
CSPRNG(Cryptographically Secure PseudoRandom Number Generator)  
/dev/urandom 이 만드는 난수 ▶ 값 예측 어려움  

 

 

✔️ DES.new 함수

 

https://howudong.tistory.com/90

[네트워크 보안] DES 개념 및 암/복호화 구현(Python)

 

DES 대칭키 암호 

▶ 키를 알면 암복호화 모두 가능 / 키 모르면 둘 다 불가능

 

 

 

 

전체 암호화 과정

 

1) cipher1 암호화

2) cipher2 복호화 ▶ 암호화 기능의 역연산 (= cipher2 로 암호화 > cipher1 로 복호화)

 

 

 

🔎 익스플로잇 설계

📖 전수 조사 (Exhaustive search)  📖

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

 

키 미지 바이트 ▶ 4바이트 (=32비트) 

총 $2^{32}$ 가지 키 존재 

 

 

전수 조사 코드

from pwn import *
from Crypto.Cipher import DES
from tqdm import trange #시간 확인

io = process(["python3", "prob.py"])

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

for i in trange(2**32):
    key = b'Dream_' + i.to_bytes(4, "big") + b'Hacker'
    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

 

 

https://skillmemory.tistory.com/entry/tqdm-%EC%82%AC%EC%9A%A9%EB%B2%95-python-%EC%A7%84%ED%96%89%EB%A5%A0-%ED%94%84%EB%A1%9C%EC%84%B8%EC%8A%A4%EB%B0%94

tqdm 사용법 - python 진행률 프로세스바

 

꽤 오래 걸림

 

 

📌 Meet-in-the-Middle Attack

A : b'DreamHack_blocks'

B : A가 암호화된 결과

 

cipher2.encrypt(cipher1.encrypt(A)) = B 

 

key1, key2 가능 후보는 미지의 2바이트에 따라 각각 $2^{16}=65536$ 가지 가능성

▶ cipher1.encrypt(A), cipher2.decrpyt(B) 가능한 가짓수 모두 65536가지 

 

올바른 키일 경우, cipher2.encrypt(cipher1.encrypt(A)) = B 성립

양변에 cipher2.decrypt ▶ cipher1.encrypt(A) = cipher2.decrypt(B)

 

ciperh1.encrypt(A) 후보 65536개와 cipher2.decrypy(B) 후보 65536 공통 값이 있으면,

해당 경우에 사용된 key1, key2가 올바른 키 

▶가운데에서 만난다는 의미의 Meet-in-the-middle attack

 

 

Python dict 자료형 사용 익스플로잇

 

 

key1 후보 dict에 저장

for i in range(2**16): 
    b = i.to_bytes(2, "big") #미지의 2바이트 
    cipher = DES.new(b"Dream_" + b, DES.MODE_ECB) #Dream_ + 임의 2바이트로 cipher1 암호키 생성
    enc = cipher.encrypt(b"DreamHack_blocks") #생성된 암호키로 암호화
    conflict[enc] = b"Dream_" + b #confilct 자료형에 {암호문:암호키} 형태로 저장

 

key2 후보 값 생성 후 탐색

for i in range(2**16):
    b = i.to_bytes(2, "big") #미지 2바이트 생성
    cipher = DES.new(b + b"Hacker", DES.MODE_ECB) #임의 2바이트 + Hacker로 cipher2 암호키 생성
    dec = cipher.decrypt(hint) #생성된 암호키로 hint 복호화
    
    # cipher2로 복호화한 값이 cipher1으로 암호화한 hint 값과 동일해야 함 

    if dec in conflict: #딕셔너리 자료형을 통해 동일 값 탐색
        key1 = conflict[dec] #key1은 conflict value 값
        key2 = b + b"Hacker" #key2는 미지 2바이트 + Hacker 값
        break

 

힌트 cipher1 암호화 값과 힌트 cipher2 복호화 값 비교를 통해 key 찾기

 

 

• to_bytes 함수 

https://thebook.io/006950/0223/

컴퓨터 사이언스 부트캠프 with 파이썬: 1 메모리 저장 방식

int형을 byte로 전환할 때, 파라미터를 통해 빅 엔디언 방식과 리틀 엔디언 방식을 설정해줄 수 있음

 

flag