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

코드 분석

주어진 파이썬 코드를 분석해보면, 알려진 6byte, 미지의 4byte, 다시 알려진 6byte가 이어진 16byte의 키를 생성한다.
이때 미지의 4byte를 생성할때 os.urandom함수를 사용하는데, os.urandom 함수는 값을 예측하기 굉장히 어려우므로 값을 예측하는것이 아닌 다른 방식으로 풀이 방향을 잡아야 한다.

 

코드를 8byte씩 잘라 각각 key1, key2로 설정한다. 이때, 미지의 4byte가 2byte씩 쪼개진다. 키별로 DES의 ECB모드를 사용해 각각 cipher1, cipher2 암호를 생성한다.
그리고 'DreamHack_blocks'를 암호화한 암호문을 주어진다. 'give_me_the_flag'를 암호화한값을 입력으로 넣으면 flag를 출력해준다.

 

우리가 모르는 키의 부분은 4byte, 즉 32bit이다. $ 2^{32} $ 의 경우의 수는 브루트포스로 해볼만하지만, DES는 여러번의 연산을 거치기 때문에 시간이 훨씬 많이 소요되고, signal.alarm(15)로 인해 15초안에 풀어야하는 지금은 불가능하다.

 

먼저 'Dreamhack_blocks'를 A, 이를 암호화한 결과를 B라고 하자. 이러면 cipher2.encrypt(cipher1.encrypt(A)) == B 라고 할 수 있다. 양변에 cipher2.decrypt를 취해주면, cipher1.encrypt(A) == cipher2.encrypt(B) 라고 할 수 있다. cipher1.encrypt(A) 와 cipher2.decrypt(B) 가 가질 수 있는 경우의 수는 각각 $ 2^{32} =65536$ 가지이므로, 각각의 후보 중에 공통된 값이 있다면, 그때 사용된 key1과 key2가 올바른 키일 것이라고 생각할 수 있다.

 

이런 공격을 가운데서 만단다는 의미로 Meet-in-the-middle attack이라고 부른다.

 

익스플로잇

은 드림핵 정책에 따라 공개하지 않습니다,,