[Dreamhack] Textbook-RSA

문제 설명

드림이가 비밀 플래그를 가지고 있는 RSA 서버를 운영하고 있습니다. 서버를 공격해 플래그를 탈취해주세요!

플래그 형식은 DH{...} 입니다.

 

소스코드

#challenge.py

#!/usr/bin/python3
from Crypto.Util.number import getStrongPrime, bytes_to_long, inverse


class RSA(object):
    def __init__(self):
        self.p = getStrongPrime(512)
        self.q = getStrongPrime(512)
        self.N = self.p * self.q
        self.e = 0x10001
        self.d = inverse(self.e, self.N - self.p - self.q + 1)

    def encrypt(self, pt):
        return pow(pt, self.e, self.N)

    def decrypt(self, ct):
        return pow(ct, self.d, self.N)


rsa = RSA()
FLAG = bytes_to_long(open("flag", "rb").read())
FLAG_enc = rsa.encrypt(FLAG)

print("Welcome to dream's RSA server")

while True:
    print("[1] Encrypt")
    print("[2] Decrypt")
    print("[3] Get info")

    choice = input()

    if choice == "1":
        print("Input plaintext (hex): ", end="")
        pt = bytes_to_long(bytes.fromhex(input()))
        print(rsa.encrypt(pt))

    elif choice == "2":
        print("Input ciphertext (hex): ", end="")
        ct = bytes_to_long(bytes.fromhex(input()))
        if ct == FLAG_enc or ct > rsa.N:
            print("Do not cheat !")
        else:
            print(rsa.decrypt(ct))

    elif choice == "3":
        print(f"N: {rsa.N}")
        print(f"e: {rsa.e}")
        print(f"FLAG: {FLAG_enc}")

    else:
        print("Nope")

 

소스코드 분석

1. 라이브러리 임포트 및 RSA 클래스 정의

from Crypto.Util.number import getStrongPrime, bytes_to_long, inverse

class RSA(object):
    def __init__(self):
        self.p = getStrongPrime(512)   # 512비트의 강한 소수 p 생성
        self.q = getStrongPrime(512)   # 512비트의 강한 소수 q 생성
        self.N = self.p * self.q       # 모듈러스 N 계산 (1024비트)
        self.e = 0x10001               # 공개 지수 e = 65537
        self.d = inverse(self.e, self.N - self.p - self.q + 1)

    def encrypt(self, pt):
        return pow(pt, self.e, self.N) # 암호화: pt^e mod N

    def decrypt(self, ct):
        return pow(ct, self.d, self.N) # 복호화: ct^d mod N

• 키 생성
  • 두 개의 큰 소수 $p,q$를 생성해서 RSA 키를 만든다.
  • self.d를 구하는 공식에서 self.N - self.p - self.q + 1을 사용했는데, 이는 수학적으로 $(p-1)(q-1)$인 $\phi(N)$과 동일하다.
• 암호화/복호화
  • 파이썬의 pow(base, exp, mod) 함수를 사용하여 RSA의 기본 공식인 $C \equiv M^e \pmod N$과 $M \equiv C^d \pmod N$을 수행한다.

 

2. 초기 설정 및 플래그 암호화

rsa = RSA()
FLAG = bytes_to_long(open("flag", "rb").read())
FLAG_enc = rsa.encrypt(FLAG)

• 서버가 시작되자마자 flag라는 파일의 내용을 읽어 숫자로 변환(FLAG)한 뒤, 위에서 만든 RSA 키로 암호화(FLAG_enc) 한다.

 

3. 메인 루프 (사용자 인터페이스)

• 서버는 무한 루프(while True)를 돌며 사용자에게 3가지 메뉴를 제공한다.

[1] Encrypt (암호화)

if choice == "1":
    print("Input plaintext (hex): ", end="")
    pt = bytes_to_long(bytes.fromhex(input()))
    print(rsa.encrypt(pt))

• 사용자가 평문(Hex)을 입력하면, 서버의 공개키($N, e$)를 이용해 암호화한다.
• 공격자가 원하는 임의의 데이터에 대한 암호문을 얻을 수 있다.

[2] Decrypt (복호화)

elif choice == "2":
    print("Input ciphertext (hex): ", end="")
    ct = bytes_to_long(bytes.fromhex(input()))
    
    # [중요] 치팅 방지 로직
    if ct == FLAG_enc or ct > rsa.N:
        print("Do not cheat !")
    else:
        print(rsa.decrypt(ct))

• 사용자가 암호문(Hex)을 입력하면, 서버의 비밀키($d$)를 이용해 복호화한다.
• Challenge
  • 사용자가 입력한 암호문 ct가 서버가 가지고 있는 플래그 암호문(FLAG_enc)과 똑같으면 복호화를 거부한다.

[3] 정보 확인

elif choice == "3":
    print(f"N: {rsa.N}")       # 공개키 모듈러스
    print(f"e: {rsa.e}")       # 공개 지수
    print(f"FLAG: {FLAG_enc}") # 암호화된 플래그

• 공개키 정보($N, e$)와 암호화된 플래그($FLAG_{enc}$)를 알려준다.

 

취약점 분석

서버의 방어 로직을 다시 보면 다음과 같다.

if ct == FLAG_enc or ct > rsa.N:
    print("Do not cheat !")
else:
    print(rsa.decrypt(ct))

 

• 공격자는 FLAG_enc를 알고 있다.
• 하지만 FLAG_enc를 그대로 2번 메뉴(복호화)에 넣으면 서버가 "Do not cheat!"라며 거절한다.
• 따라서, FLAG_enc와 다르게 생겼지만, 수학적으로 플래그와 연결된 새로운 암호문을 만들어야 한다.

 

핵심 취약점 : RSA Homomorphic

RSA 암호화에는 두 암호문을 곱하면, 그 안의 평문끼리도 곱해지는 성질이 있다.

이를 수학적으로 표현하면 다음과 같다. ($E(m)$은 메시지 $m$을 암호화한 것을 의미)

 

$E(A) \times E(B) = E(A \times B)$

 

즉, 암호문 상태에서 곱하기를 하면, 나중에 복호화했을 때 평문도 곱해진 상태로 나온다.

 

 

 

공격 시나리오

RSA의 Homomorphic 성질 이용해서 플래그 암호문을 변장시켜 플래그를 얻을 것이다. 가장 간단한 숫자 2를 사용해서 변장시켜보자.

 

STEP 1 : 숫자 2 암호화

직접 숫자 2를 RSA로 암호화한다.

$C_{two} = 2^e \pmod N$

 

STEP 2 : 변장된 암호문 만들기

원본 플래그 암호문($C_{flag}$)에 방금 만든 $C_{two}$를 곱한다.

 

$C_{fake} = (C_{flag} \times C_{two}) \pmod N$

 

$C_{fake} = E(\text{FLAG}) \times E(2) = E(\text{FLAG} \times 2)$

 

$C_{fake}$는 플래그에 2를 곱한 값의 암호문이 된다.

 

STEP 3 : 서버에게 전송 후 플래그 복구

$C_{fake}$를 서버의 2번 메뉴에 보낸다.

서버가 복호화해서 준 값($P_{fake}$)은 다음과 같다.

 

$P_{fake} = \text{FLAG} \times 2$

 

우리는 평문 상태의 결과를 받았으므로, 여기서 그냥 2로 나누기만 하면 원본 FLAG를 얻을 수 있다.

 

 

공격 코드

from pwn import *
from Crypto.Util.number import long_to_bytes

# 통신 과정을 자세히 보기 위해 디버그 모드 활성화
context.log_level = 'debug'

r = remote('host8.dreamhack.games', 13064) 

def solve():
    print("[*] 서버 접속 및 정보 수집 중...")
    
    # 1. 메뉴 [3]번 선택하여 정보(N, e, FLAG_enc) 가져오기
    # 확실하게 메뉴가 다 출력될 때까지 기다린 후 입력
    r.sendlineafter(b"Get info", b"3")
    
    r.recvuntil(b"N: ")
    N = int(r.recvline().strip())
    
    r.recvuntil(b"e: ")
    e = int(r.recvline().strip())
    
    r.recvuntil(b"FLAG: ")
    FLAG_enc = int(r.recvline().strip())
    
    print(f"[+] N: {N}")
    print(f"[+] e: {e}")
    print(f"[+] FLAG_enc: {FLAG_enc}")

    # 2. Chosen Ciphertext Attack (CCA) 준비
    factor = 2
    C_factor = pow(factor, e, N)
    
    # 변조된 암호문 생성: (FLAG_enc * 2^e) % N
    C_forged = (FLAG_enc * C_factor) % N
    
    print(f"[*] 변조된 암호문 생성 완료")

    # 3. 메뉴 [2]번 선택하여 변조된 암호문 복호화 요청
    r.sendlineafter(b"Get info", b"2")
    
    # Hex 문자열 변환 시 짝수 길이 맞추기
    # bytes.fromhex()는 홀수 길이 문자열을 받으면 서버가 튕긴다.
    payload = hex(C_forged)[2:]
    if len(payload) % 2 != 0:
        payload = '0' + payload
        
    print(f"[*] Sending Payload Length: {len(payload)}")
    
    # 프롬프트 "Input ciphertext (hex): "를 기다림
    r.sendlineafter(b"(hex): ", payload.encode())
    
    # 4. 복호화된 결과 받기
    try:
        # 서버가 숫자만 보내고 줄바꿈 하므로 recvline() 사용
        # 간혹 통신 지연으로 빈 줄이 올 수 있어 예외 처리
        received = r.recvline().strip()
        if not received:
             received = r.recvline().strip() # 한 번 더 시도
             
        P_forged = int(received)
        print(f"[+] 서버로부터 받은 복호화 값 (FLAG * 2): {P_forged}")

        # 5. 원래 플래그 복구
        FLAG_int = P_forged // factor
        FLAG = long_to_bytes(FLAG_int)
        
        print("\n" + "="*40)
        print(f"FLAG: {FLAG.decode(errors='ignore')}") # decode 에러 방지
        print("="*40)
        
    except Exception as e:
        print(f"[-] Error parsing result: {e}")

    r.close()

if __name__ == "__main__":
    solve()

 

주의사항

파이썬의 bytes.fromhex() 함수는 반드시 짝수 길이의 문자열만 입력받는다.

만든 암호문 숫자(C_forged)를 hex()로 변환할 때, 앞의 0이 잘리면서 홀수 길이가 되는 경우가 종종 발생한다.

따라서 payload의 길이가 홀수면 앞에 0을 넣어 짝수로 만드는 코드를 넣어주었다.