[Cryptography] Textbook-DH

문제 : https://dreamhack.io/wargame/challenges/120

Textbook-DH

Code Analysis

라이브러리

from Crypto.Util.number import getPrime #소수 반환
from Crypto.Util.Padding import pad, unpad #패딩
from Crypto.Cipher import AES # AES
import hashlib #해시 함수 제공
import random

 

Person - 송신자 수신자

class Person(object):
    def __init__(self, p):
        self.p = p
        self.g = 2
        self.x = random.randint(2, self.p - 1)
    
    def calc_key(self):
        self.k = pow(self.g, self.x, self.p)
        return self.k

    def set_shared_key(self, k):
        self.sk = pow(k, self.x, self.p)
        aes_key = hashlib.md5(str(self.sk).encode()).digest()
        self.cipher = AES.new(aes_key, AES.MODE_ECB)

    def encrypt(self, pt):
        return self.cipher.encrypt(pad(pt, 16)).hex()

    def decrypt(self, ct):
        return unpad(self.cipher.decrypt(bytes.fromhex(ct)), 16)

 

*python3 에서는 Object를 상속하지 않아도 괜찮음

 

init 

def __init__(self, p):
        self.p = p
        self.g = 2
        self.x = random.randint(2, self.p - 1)

• p = 받은 p 초기화
• g = 2
• x = 2 ~ p-1 랜덤 정수 > 송/수신자의 개인 키

 

calc_key

def calc_key(self):
        self.k = pow(self.g, self.x, self.p)
        return self.k

• \(k = g^x (mod\ p)\)로 초기화 > \(g^x\)를 소수 \(p\)로 나눈 값
• k 반환

set_shared_key

def set_shared_key(self, k):
        self.sk = pow(k, self.x, self.p)
        aes_key = hashlib.md5(str(self.sk).encode()).digest()
        self.cipher = AES.new(aes_key, AES.MODE_ECB)

• \(sk = k^x(mod\ p)\) > k 다른 사용자로부터 받은 키 / x는 개인키 
• sk 최종 통신에 사용되는 키 
• aes_key : AES 대칭 암호화 키 생성 > sk 문자열 변환 → 바이트로 인코딩 → MD5 해시 함수를 이용해 해시 처리
• cipher : AES 암호화 객체를 생성 - ECB 모드

encrypt

def encrypt(self, pt):
        return self.cipher.encrypt(pad(pt, 16)).hex()

• cipher 객체를 사용하여 평문을 AES 알고리즘으로 암호화함
• 암호화에 사용되는 키 : sk
• pad(pt,16) : 평문을 패딩 > 평문 pt를 16바이트로
• .hex() : 암호문을 16진수 문자열로 변환

decrypt

def decrypt(self, ct):
        return unpad(self.cipher.decrypt(bytes.fromhex(ct)), 16)

• 암호문 ct를 바이트 형태로 변환한 후 AES 알고리즘으로 복호화함
• unpad(~,16) : 복호화된 결과를 언패딩

코드 동작 과정

flag = open("flag", "r").read().encode() #암호화된 flag를 flag 변수에 저장
prime = getPrime(1024) #1024비트의 소수를 생성하고 prime 변수에 저장
print(f"Prime: {hex(prime)}")
#alice,bob 두 Person 객체를 만들기
alice = Person(prime)
bob = Person(prime)

alice_k = alice.calc_key() #alice의 키 계산 (A)
print(f"Alice sends her key to Bob. Key: {hex(alice_k)}") 
print("Let's inturrupt !")
alice_k = int(input(">> ")) #alice가 bob에게 보내는 키(A) >> 코드로 키 부여 가능
if alice_k == alice.g:
    exit("Malicious key !!")
bob.set_shared_key(alice_k) #alice가 보낸 키를 사용하여 공유하는 비밀키를 설정

bob_k = bob.calc_key() #bob : 개인키를 사용하여 공개키를 계산 > alice에게 공개키를 보냄 (B)
print(f"Bob sends his key to Alice. Key: {hex(bob_k)}")
print("Let's inturrupt !")
bob_k = int(input(">> ")) #bob이 alice에게 보내는 키 (B) >> 코드로 키 부여 가능
if bob_k == bob.g:
    exit("Malicious key !!")
alice.set_shared_key(bob_k) #Alice는 Bob이 보낸 키를 사용하여 공유하는 비밀키를 설정

print("They are sharing the part of flag")
#플래그를 두 부분을 나눔
print(f"Alice: {alice.encrypt(flag[:len(flag) // 2])}")
print(f"Bob: {bob.encrypt(flag[len(flag) // 2:])}")
#alice_pt + bob_pt > flag

키 교환 예시 (Dreamhack:Cryptography > 키 교환 : Diffie-Hellman 알고리즘)

코드와 그림 변수 비교

• K = A, B
• x = a, b
• g = 2
• sk = k

Solution

k(A,B) : 1을 입력 →  A,B,prime을 구할 수 있음 > 암호화된 flag

*공유된 비밀키 sk = 1

challenge.py로 복호화

 

1 실행 결과

Alice: e48e9174a9103e249f4bb809e13d58d49283e2438954799030be4854328adacbeb310c79bce3e91719f218158359af0d
Bob: 2a69648d494907e551b69b74676f2e528644a526e5f7bc8b6300f1bd8ad5f091a9e40939960ea5bd0ad2ceff23a14f96

 

key 1로 암호화된 flag : e48e9174a9103e249f4bb809e13d58d49283e2438954799030be4854328adacbeb310c79bce3e91719f218158359af0d2a69648d494907e551b69b74676f2e528644a526e5f7bc8b6300f1bd8ad5f091a9e40939960ea5bd0ad2ceff23a14f96

 

python ModuleNotFoundError: No module named 'Crypto' 해결

python3 -m pip install pycryptodome

 

Solution Code

• 서로 키를 공유하는 과정에서, 공유된 비밀키를 1로 설정함
• 공유된 비밀키가 1이라는 것을 알고, 이를 이용해서 AES키를 생성
• AES키를 사용하여 암호문을 복호화하여 기존의 플래그 복원

from pwn import *
from Cryptodome.Cipher import AES
from Cryptodome.Util.Padding import unpad
import hashlib

p = remote("host", port number)

# get prime
p.recvuntil(b"Prime: ")
prime = int(p.recvline()[:-1], 16) #주어진 소수를 16진수로 저장

# set key Attacker <=> Alice
p.recvuntil(b"Alice sends her key to Bob. Key: ")
alice_public = int(p.recvline()[:-1], 16)
p.sendline(b'1') # 1전송

# set key Attacker <=> Bob
p.recvuntil(b"Bob sends his key to Alice. Key: ")
bob_public = int(p.recvline()[:-1], 16)
p.sendline(b'1') # 1전송

# decrypt flag
p.recvuntil(b"Alice: ")
alice_enc = p.recvline()[:-1].decode()

p.recvuntil(b"Bob: ")
bob_enc = p.recvline()[:-1].decode()

# 공격자의 공유된 비밀 키
shared_key = 1
aes_key = hashlib.md5(str(shared_key).encode()).digest()

# AES 암호화 객체 생성
cipher = AES.new(aes_key, AES.MODE_ECB)

# 암호문 복호화
alice_dec = unpad(cipher.decrypt(bytes.fromhex(alice_enc)), 16)
bob_dec = unpad(cipher.decrypt(bytes.fromhex(bob_enc)), 16)

# 플래그 복원
flag = alice_dec + bob_dec
print("FLAG:", flag)