[Crypto] 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!")

 

 

코드 분석

• signal.alarm(15) → 15초의 제한 시간 부여
• key = b'Dream_' + os.urandom(4) + b'Hacker'
  • 알려진 6byte, 미지의 4byte, 다시 알려진 6byte가 이어진 16byte의 키가 생성됨
• os.urandom 함수는 /dev/urandom 이 만들어내는 난수로, CSPRNG(Cryptographically Secure Pseudorandom Number Generator) 로서 값을 예측하기 굉장히 어려움
  • 앞으로도 문제에 os.urandom 함수가 등장한다면 아무런 관련 정보 없이 그 값을 예측하는 것은 불가능하다는 것을 전제로 두면 됨!
• key1 = key[:8], key2 = key[8:]
  • 키의 앞 8바이트를 key1으로, 뒤 8바이트를 key2로 설정
  • key1, key2 모두 8byte의 키이고, 각각 미지의 2byte를 갖고 있는 셈
• DES.new(key1, DES.MODE_ECB) 와 같은 함수를 이용하여 cipher1 암호를 생성
  • DES 는 대칭키 암호이기 때문에 키를 알면 암호화와 복호화가 모두 가능하고, 키를 모르면 둘 중 어느 것도 불가
  • 따라서 key1, key2의 미지 2바이트를 각각 알아낸다면 cipher1, cipher2의 암호화와 복호화 기능을 마음껏 사용할 수 있음
  • 여기서 ECB는 DES 암호화 모드 중 하나이며, 이는 각 블록을 독립적으로 암호화!

 

 

• 전체 암호화 기능은 cipher1로 암호화한 후 cipher2로 복호화하는 방식으로 진행
• 복호화 기능은 암호화 기능의 역연산으로, cipher2로 암호화한 후 cipher1로 복호화하는 방식으로 진행
  • 역연산이 진행되려면 순서까지 역으로 바뀌어야 함에 유의!
• b'DreamHack_blocks' 를 암호화한 후의 결과가 주어져 있는 상태에서 두 키의 미지 2바이트를 복구하는 것이 목표
  • 즉 cipher2.encrypt(cipher1.encrypt(b'DreamHack_blocks'))의 결과를 이용해 두 키를 완전히 복구하면 문제를 해결할 수 있음
  • 어떠한 암호문을 복호화해야 give_me_the_flag 라는 평문이 나오는지를 구해야함 (암/복호화에 사용된 key 찾기)

 

---

 

익스플로잇 설계

• 키의 미지 바이트는 총 4바이트, 즉 32비트 (1byte = 8bit)
• 따라서 2^{32}가지의 키가 존재하고 그 키들을 모두 대입해보았을 때, b'DreamHack_blocks'를 암호화한 결과가 일치하면 높은 확률로 올바른 키라고 추측할 수 있음
• 이와 같이 모든 가능한 값을 대입하여 올바른 입력값을 찾는 방식을 전수 조사(Exhaustive search)라고 함

 

키를 찾아내는 4바이트 전수 조사 코드는 다음과 같이 구현 가능하다.

어느 정도의 시간이 걸릴지 확인하기 위해 range 대신 tqdm 패키지의 trange를 사용

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) # 암호화 객체 cipher1 생성
    cipher2 = DES.new(key2, DES.MODE_ECB) # 암호화 객체 cipher2 생성
    if cipher2.encrypt(cipher1.encrypt(b'DreamHack_blocks')) == hint:
        print("Success")
        break

  0%|                        | 883465/4294967296 [00:08<11:13:23, 106280.79it/s] # 많은 시간 소요

 

• io.recvuntil(b":> ")
  • 프로세스 출력을 읽어서 :> 문자열이 나올 때까지 대기
• hint = bytes.fromhex(io.recvline().decode())
  • recvline은 한 줄을 수신하고, decode는 바이트 문자열을 문자열로 변환, bytes.fromhex는 16진수 문자열을 바이트로 변환 ⇒ 즉 힌트를 수신하는 코드
• for문은 브루트 포스 알고리즘으로 trange에 의해 진행 상태를 시각적으로 표시하게 됨
• key = b'Dream_' + i.to_bytes(4, "big") + b'Hacker'
  • 현재 반복하는 인덱스를 4byte(big endian)로 변환하여 Dream_i_Hacker 형식의 12byte 키를 생성
• if cipher2.encrypt(cipher1.encrypt(b'DreamHack_blocks')) == hint:
  • 평문인 b'DreamHack_blocks' 를 cipher1으로 암호화하고, 이 결과를 다시 cipher2로 암호화
  • 이렇게 이중 암호화한 결과가 hint와 일치하는지 확인하는 코드

⇒ 즉, 해당 익스플로잇의 목적은 브루트 포스 알고리즘을 통해 모든 키 조합을 시도하여 주어진 힌트 값과 일치하는 암호화 결과를 찾는 것!

 

---

 

컴퓨터의 연산 능력

• 개인 컴퓨터의 경우 2^{32}회의 사칙연산은 1분 내외로 가능
  • 하지만 DES와 같이 여러 회의 연산으로 이루어진 암, 복호화 연산의 경우 훨씬 더 소요되어, 15초에 2^{32}회 진행하는 것은 어려움
• 슈퍼컴퓨터의 경우 2^{64}회의 연산도 가능
  • 따라서 64비트 전수 조사가 가능하고, 이론상 8바이트 키를 가지는 모든 암호 체계를 위협할 수 있다.
    (문제에서 등장한 DES 대칭키 암호가 더 이상 사용되지 않는 이유 중 하나)
• 현대 기술로는 2^{128}회의 연산은 불가능하다고 알려져 있다. 따라서 16바이트 키를 가지는 AES 대칭키 암호는 전수 조사를 통해 공격이 어려움

위와 같이 두 암호를 중첩시켜 암, 복호화를 진행하는 경우, 2^{32}회보다 더 적은 횟수의 암, 복호화 연산으로 키를 알아내는 방법을 알아보자.

 

 

Meet-in-the-Middle Attack 🤝

먼저 b'DreamHack_blocks'를 A, 암호화된 결과를 B라고 칭해보자.

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

 

key1, key2로 가능한 후보는 미지 2바이트(16 bit), 따라서 2^{16}=65536가지 가능성이 존재한다.

따라서 cipher1.encrypt(A) 와 cipher2.decrypt(B) 의 결과로 가능한 가짓수 모두 65536가지

 

올바른 키에 대하여 cipher2.encrypt(cipher1.encrypt(A)) == B 를 만족하기 때문에, 양변에 cipher2.decrypt를 취해주면 cipher1.encrypt(A) == cipher2.decrypt(B) 를 만족하게 된다.

 

따라서 cipher1.encrypt(A) 의 결과로 가능한 후보 65536개와 cipher2.decrypt(B) 의 결과로 가능한 후보 65536개 중에서 공통으로 속하는 값이 있다면, 그 경우에 각각 사용된 key1, key2 가 올바른 키일 것이라고 추측할 수 있다!

 

두 65536 길이 배열의 공통 원소를 찾기 위해서는 65536×65536회 연산하는 방법도 있지만, 이보다 훨씬 빠른 알고리즘들이 존재한다. Python의 set이나 dict 자료구조를 이용하면 간단히 해당 알고리즘을 사용할 수 있다.

가운데서 만난다는 의미를 가진 해당 공격을 Meet-in-the-middle attack이라고 부름

 

 

---

 

익스플로잇

앞서 언급한대로 meet in the middle attack 공격을 하기 위해 python의 dict 자료형을 활용해보자!

for i in range(65536):
    b = i.to_bytes(2, "big")
    cipher = DES.new(b"Dream_" + b, DES.MODE_ECB)
    enc = cipher.encrypt(b"DreamHack_blocks")
    conflict[enc] = b"Dream_" + b

 

• conflict의 key에는 65536개의 후보, value에는 해당하는 key1 를 저장
• to_bytes() 란? → 빅 엔디언 방식일 때의 바이트의 나열과 리틀 엔디언일 때의 바이트 나열을 확인할 수 있는 메소드
  • 예를 들어 a = 0x01020304 (16진수), 10진수로는 16909060 인 정수 a를 4byte 메모리 공간에 저장한다고 가정
  • 16진수 두 자리는 1byte를 나타내고 4byte에 저장되므로 각 byte에 1, 2, 3, 4가 저장됨
  • 복습) 이때 1, 2, 3, 4 순서대로 저장되는 것이 빅 엔디언, 반대로 4, 3, 2, 1 순서로 저장되는 것이 리틀 엔디언 방식
  • a.to_bytes(4, ‘big’) → b’\x01\x02\x03\x04’
  • a.to_bytes(4, ‘little’) → b’\x04\x03\x02\x01’

 

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: # 공통된 key가 존재하는 경우
        key1 = conflict[dec] 
        key2 = b + b"Hacker" # 올바른 키를 복구
        break

 

• conflict에 공통된 key, 즉 가운데에서 만난 값이 존재한다면, 위 코드를 사용해 올바른 key2와 함께 conflict의 value에서 key1를 가져와 올바른 키를 복구할 수 있음

 

solve code

from pwn import *
from Crypto.Cipher import DES

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

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

conflict = dict()

# key1 부분을 브루트포싱하여 모든 가능한 값에 대해 암호화된 텍스트 저장
for i in range(65536):
    b = i.to_bytes(2, "big")
    cipher = DES.new(b"Dream_" + b, DES.MODE_ECB)
    enc = cipher.encrypt(b"DreamHack_blocks") # 암호화
    conflict[enc] = b"Dream_" + b # key1으로 암호화된 암호문 enc

# key2를 브루트포싱하여 복호화한 값이 딕셔너리에 있는지 체크
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]
        key2 = b + b"Hacker"
        break

cipher1 = DES.new(key1, DES.MODE_ECB)
cipher2 = DES.new(key2, DES.MODE_ECB)
encrypt = lambda x: cipher2.encrypt(cipher1.encrypt(x)) # 이중 DES로 암호화
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())