[117] IT 비전공자 [dreamhack]Double DES문제 풀기

 

 

소스코드당

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

 

 

 

Double DES는 두 개의 Data Encryption Standard (DES) 암호화를 연속적으로 적용하여 보안성을 향상하려는 암호화 방식입니다. DES 자체의 보안이 약화되면서 이를 강화하기 위해 제안된 기법 중 하나입니다. 하지만 Double DES에는 취약점이 있어 실질적으로 많이 사용되지는 않습니다.

---

동작 방식

1. 암호화:
   • 평문 PP에 대해 두 개의 서로 다른 키 K1K_1와 K2K_2를 사용하여 두 번 암호화를 수행합니다.
   C=EK2(EK1(P))C = E_{K_2}(E_{K_1}(P))여기서:
   • EK1(P)E_{K_1}(P): 첫 번째 DES 암호화.
   • EK2E_{K_2}: 두 번째 DES 암호화.
   • CC: 최종 암호문.
2. 복호화:
   • 암호문 CC에 대해 같은 두 키를 역순으로 사용하여 복호화합니다.
   P=DK1(DK2(C))P = D_{K_1}(D_{K_2}(C))여기서:
   • DK2(C)D_{K_2}(C): 두 번째 DES 복호화.
   • DK1D_{K_1}: 첫 번째 DES 복호화.

---

보안 목표

• 단일 DES의 56비트 키 길이를 두 번 적용함으로써 키 길이를 112비트로 늘려 보안성을 강화하려는 것이 목표였습니다.

---

취약점: Meet-in-the-Middle 공격

Double DES는 Meet-in-the-Middle (MITM) 공격으로 인해 예상보다 약한 보안성을 가집니다.

1. MITM 공격:
   • 공격자가 암호문 CC와 평문 PP 한 쌍을 알고 있다고 가정.
   • EK1(P)E_{K_1}(P)와 DK2(C)D_{K_2}(C)의 중간 값을 계산하여 키를 복구.
2. 단계:
   1. 첫 번째 키 K1K_1 후보를 모두 시도하여 EK1(P)E_{K_1}(P) 값을 저장.
   2. 두 번째 키 K2K_2 후보를 모두 시도하여 DK2(C)D_{K_2}(C) 값을 계산.
   3. EK1(P)E_{K_1}(P)와 DK2(C)D_{K_2}(C)의 일치 여부를 확인하여 올바른 K1K_1과 K2K_2를 찾음.
3. 결과:
   • Double DES의 보안 수준은 이론적으로 21122^{112}번의 연산을 요구하지만, MITM 공격으로 인해 2572^{57}번의 연산으로 키를 복구 가능.
   • 이는 단일 DES의 2562^{56}에 비해 큰 보안 향상이 아님.

---

Triple DES와의 비교

Double DES의 취약점을 극복하기 위해 Triple DES가 제안되었습니다. 이는 DES를 세 번 연속 적용하는 방식으로, 보안성이 크게 향상되었습니다:

C=EK1(DK2(EK1(P)))C = E_{K_1}(D_{K_2}(E_{K_1}(P)))

• Triple DES는 효과적인 키 길이가 112비트에서 168비트에 이르며, 여전히 많은 금융 시스템에서 사용됩니다.

---

요약

• Double DES는 두 번의 DES 암호화를 사용하여 보안을 강화하려 했으나, MITM 공격으로 인해 예상보다 약한 보안을 제공합니다.
• Triple DES가 더 강력한 대안으로 사용됩니다.
• 현재는 AES(Advanced Encryption Standard)와 같은 더 안전하고 효율적인 암호화 방식이 널리 사용됩니다.

 

 

 

---

 

 

이 프로그램은 두 개의 DES 키를 사용하여 데이터를 암호화하고 복호화합니다. 주요 목표는 4바이트의 랜덤 값을 brute-force하여 프로그램이 15초 내에 암호화된 메시지를 올바르게 복호화하도록 만드는 것입니다. 프로그램의 흐름을 분석하고 공격 방법을 설명하겠습니다.

---

코드 분석

1. 키 생성:
   • key는 16바이트로 구성되며, b'Dream_' + 4바이트 랜덤 값 + b'Hacker 형태입니다.
   • key1와 key2는 각각 8바이트로 나뉘어 DES 키로 사용됩니다.
2. key = b'Dream_' + os.urandom(4) + b'Hacker' key1 = key[:8] key2 = key[8:]
3. 암호화와 복호화:
   • encrypt: 두 번의 DES 암호화를 적용 (Cipher1 → Cipher2).
   • decrypt: 두 번의 DES 복호화를 적용 (Cipher2 → Cipher1).
4. 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))
5. 힌트:
   • 프로그램은 b'DreamHack_blocks'를 암호화한 값을 힌트로 제공합니다.
6. print(f"Hint for you :> {encrypt(b'DreamHack_blocks').hex()}")
7. 입력 확인:
   • 프로그램은 사용자가 입력한 메시지를 복호화한 결과가 b'give_me_the_flag'인지 확인합니다.
8. msg = bytes.fromhex(input("Send your encrypted message(hex) > ")) if decrypt(msg) == b'give_me_the_flag': print(flag) else: print("Nope!")

---

공격 전략

1. 키 공간:
   • os.urandom(4)는 4바이트의 랜덤 값을 생성합니다.
   • 4바이트는 2322^{32} (약 42억)개의 가능한 값이 있습니다.
2. Brute-Force:
   • 힌트 메시지와 입력한 메시지의 암호화 및 복호화 과정을 역추적하여 가능한 키를 brute-force 합니다.
   • 먼저 key1와 key2를 추정하여 메시지를 복호화합니다.
3. 공격 단계:
   1. 힌트 값과 평문(b'DreamHack_blocks')을 사용하여 모든 가능한 key1와 key2를 brute-force 합니다.
   2. 올바른 키를 찾으면 사용자가 입력한 암호화된 메시지를 복호화하여 플래그를 가져옵니다.

 

 

 

https://whitehacking.tistory.com/38

[Dreamhack] Double DES 문제 풀이

여기 문제 풀이가 너무 완벽해서 줏어왔다..역시 암호학은 복호화 과정 100% 이해해야 풀이가능 ㅋㅋㅋ

직접 손으로 타이핑하거나, 종이에 쓰는게 이해가 빠르다

 

 

 

힌트 값은 e18151dfa842d675d0f0f767b80ac143

 

DreamHack_block를 암호화 해서 16진수로 나타낸 값이 저거

 

DreamHack_block를 A, 전체 암호화 결과를 B라고하면

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

여기에 cipher2.decryp를 양식에 둘다 넣어주면

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

이 식을 만족하는 공통된 key1, key2가 올바른 키

2^16 =2^17

 

 

 

 

 

이 코드는 DreamHack 문제에서 Double DES 암호화를 브루트포싱을 통해 풀기 위한 스크립트입니다. 코드의 주요 목적은 key1과 key2를 찾아 특정 메시지를 복호화하거나 암호화된 데이터를 다시 보낼 수 있도록 하는 것입니다. 아래는 코드의 주요 부분에 대한 설명입니다.

---

1. Key와 Message 정의

key = b'Dream_' + bytearray(4) + b'Hacker'

• key는 DES 키의 형식을 나타냅니다.
  • 앞부분은 b'Dream_' (6바이트).
  • 중간은 4바이트로 브루트포싱할 영역 (bytearray(4)는 빈 값으로 초기화).
  • 뒷부분은 b'Hacker' (6바이트).
• key1과 key2는 각각 이 키에서 중간의 브루트포싱 값에 의해 결정됩니다.

---

2. Key1 브루트포싱 (Precomputation)

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')
    m[cipher_text] = int.to_bytes(i, 2, 'big')

• key1의 중간 값 (int.to_bytes(i, 2, 'big'))을 모든 가능한 값으로 설정하며 브루트포싱합니다.
  • i는 2바이트 값이므로 총 256 * 256 = 65,536개의 경우의 수를 시도합니다.
• 각 key1로 b'DreamHack_blocks' 문자열을 암호화하여 암호문을 생성하고, 결과를 딕셔너리 m에 저장합니다:
  • Key: cipher_text (암호화된 텍스트).
  • Value: key1에서 사용된 중간 값 (2바이트).

---

3. 서버 연결

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

• remote를 사용하여 DreamHack 문제의 서버에 연결합니다.
• 서버로부터 제공되는 힌트를 읽어옵니다. 이 힌트는 Double DES 암호화된 텍스트로, 이를 브루트포싱하여 키를 복구합니다.

---

4. Key2 브루트포싱

cipher_text3 = int.to_bytes(int(data, 16), 16, 'big')
ans = 0
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')

• 힌트를 바탕으로 key2를 브루트포싱합니다.
  • cipher_text3는 서버에서 받은 힌트(암호화된 메시지)를 바이트로 변환한 값.
  • key2는 브루트포싱 값과 b'Hacker'의 조합.
  • 각 key2로 복호화를 시도하며, 복호화된 값이 m 딕셔너리의 키(cipher_text)에 존재하는지 확인합니다.
• 키를 찾으면 ans에 key1과 key2의 중간 값들을 조합해 저장합니다.

---

5. 암호화 메시지 생성

cipher1 = DES.new(key[:6] + ans[:2], DES.MODE_ECB)
cipher2 = DES.new(ans[2:] + key[10:], DES.MODE_ECB)
send_msg = cipher2.encrypt(cipher1.encrypt(b'give_me_the_flag'))

• 찾은 key1과 key2를 사용하여 Double DES 암호화를 수행합니다.
• 메시지 b'give_me_the_flag'를 암호화하여 서버로 보낼 메시지를 생성합니다.

---

6. 서버로 암호화 메시지 전송

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

• 생성한 암호화 메시지를 서버에 전송합니다.
• r.interactive()를 사용하여 서버와의 상호작용을 유지합니다.

---

코드 흐름 요약

1. Precomputation (Key1): key1의 모든 가능한 값을 브루트포싱하여 암호화된 텍스트를 딕셔너리로 저장.
2. 서버로부터 힌트 수신: 서버에서 제공된 Double DES 암호문을 수신.
3. Key2 브루트포싱: 받은 힌트를 이용해 key2를 브루트포싱하며 key1과 일치하는 값을 찾음.
4. Double DES 암호화 메시지 생성: 찾은 key1과 key2로 b'give_me_the_flag'를 암호화.
5. 서버로 메시지 전송: 암호화된 메시지를 서버로 보내 플래그를 획득.

---

중요한 점

• Precomputation: key1을 미리 브루트포싱하고 저장하여 검색 속도를 빠르게 함.
• 효율적인 키 탐색: Double DES의 중간 값을 활용한 Meet-in-the-Middle 공격 기법 사용.
• 2단계 브루트포싱: key1과 key2를 분리하여 효율적으로 브루트포싱.

이 코드는 Double DES의 보안 약점을 효과적으로 이용하여 키를 찾는 방식입니다.

 

 

 

 

https://whitehacking.tistory.com/38

 

[Dreamhack] Double DES 문제 풀이

https://ah-rok.tistory.com/57

[Dream Hack - Crypto] Double DES