[Dreamhack] TOP secret!

문제 설명

아모와 보코는 난도 몰래 비밀 메시지을 주고받고 있어요.

내용이 플래그라는 것은 난도에겐 절대, 절대 비밀이에요!

 

키워드

비제네르 암호, RSA, Cube Attack

💡 비제네르 암호
- 비제네르 표(Vigenère Square)를 보고 암호화를 진행한다.
- 암호화 원리는 다음과 같다.
      1. 평문과 키워드(비밀번호)를 준비한다.
      2. 평문 길이에 맞춰 키워드를 반복해서 적는다.
      3. 표에서 두 글자가 만나는 곳을 찾는다.

- 비즈네르 암호법 수식 : $C_i = E_K(M_i) = (M_i+K_i) \pmod{26}$
- 카시스키 테스트를 사용해서 해독할 수 있다.

 

💡 Cube Attack
- Stream Cipher를 깨기 위해 고안된 강력한 해킹 방법
- 복잡한 수학 공식을 아주 단순한 1차 방정식으로 바꿔서 비밀키는 알아내는 것이 핵심이다.

- Cube의 의미: 공격자가 마음대로 바꿀 수 있는 공개 변수(예: 초기화 벡터, IV) 중 일부를 선택해서, 그 값들이 가질 수 있는 모든 경우의 수(0 또는 1)를 다 넣어보는 것을 말한다. 이 모양이 마치 다차원 큐브(입방체) 같다고 해서 붙은 이름이다.

 

소스코드

#prob.py

import random
from Crypto.Util.number import getPrime, bytes_to_long, inverse

class RSA_Cipher:
    def __init__(self):
        self.p = getPrime(1024)
        self.q = getPrime(1024)
        self.N = self.p * self.q
        self.e = 5
        self.d = inverse(self.e, self.N - self.p - self.q + 1)

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

class Vigenere_Cipher:
    def __init__(self, key):
        self._key = key

    def encrypt(self, msg):
        enc = b""
        for i in range(len(msg)):
            enc += bytes([(msg[i] + self._key[i % len(self._key)]) % 256])
        return enc

def main():
    FLAG = open("flag", "rb").read()
    key = random.randbytes(4)

    while(1):
        try:
            vgn = Vigenere_Cipher(key)
            rsa = RSA_Cipher()
            break
        except Exception as e:
            continue

    print("Hi, this is Amo, I'll send you my public key.")
    print("e:", rsa.e)
    print("N:", rsa.N)
    print()

    enc1 = bytes_to_long(vgn.encrypt(FLAG))
    enc2 = rsa.encrypt(bytes_to_long(key))

    print("Hello, this is Boko! I'll send you ciphertexts!")
    print("enc1:", enc1)
    print("enc2:", enc2)


if __name__ == "__main__":
    main()

 

소스코드 분석

1. RSA_Cipher 클래스

class RSA_Cipher:
    def __init__(self):
        self.p = getPrime(1024)
        self.q = getPrime(1024)
        self.N = self.p * self.q
        self.e = 5
        self.d = inverse(self.e, self.N - self.p - self.q + 1)

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

• 공개지수가 5로 매우 작다.
• 개인키 d 계산: $d = e^{-1} \pmod{(p-1)(q-1)}$

 

2. Vigenere_Cipher 클래스

class Vigenere_Cipher:
    def __init__(self, key):
        self._key = key

    def encrypt(self, msg):
        enc = b""
        for i in range(len(msg)):
            enc += bytes([(msg[i] + self._key[i % len(self._key)]) % 256])
        return enc

• Byte 단위의 덧셈 암호
• 암호화 방법 : (평문 + 키) % 256
• 복호화 방법 : (암호문 - 키) % 256

 

3. main 함수

def main():
    FLAG = open("flag", "rb").read()
    key = random.randbytes(4)

    while(1):
        try:
            vgn = Vigenere_Cipher(key)
            rsa = RSA_Cipher()
            break
        except Exception as e:
            continue

• 4바이트 크기의 랜덤한 키를 생성한다.
• vgn, rsa: 각각 비제네르 암호기와 RSA 암호기 객체를 생성한다.
• vgn의 경우 랜덤한 키 값을 가지고 객체를 생성한다.
• RSA_Cipher() 안에서는 inverse(e, phi) 함수를 써서 개인키($d$)를 계산한다. 수학적으로 $e(=5)$와 $\phi(N)$이 서로소가 아니면, 역수($d$)를 구할 수 없어 에러가 발생할 수 있다.
• 또한 랜덤으로 소수($p, q$)를 뽑다 보면 가끔 에러가 날 수 있으므로, 성공적으로 키가 만들어질 때까지 계속 시도하기 위해서 무한 루프를 사용한다.

print("Hi, this is Amo, I'll send you my public key.")
print("e:", rsa.e)
print("N:", rsa.N)

#output.txt
Hi, this is Amo, I'll send you my public key.
e: 5
N: 24778450034785355796150191255487074823099958164427517612668815658468206009158475774203229828058652831641389747402272728790787685762568229069520469756247804941312947307153713830371750706901868389560472732254665749033734649996443767231968425511092244591774647092925931126950380935008196052393893271837275626174525444417778170526468251066473481105512939105882134615031671691748551289394109269703632798650982887859648332846094423809290782207835604174269463315884480062803289020119565250762542625596177768616201281918850432872639983965071018579891448754659608103400036049016809640134053891855019010729470727777892901808607

• 사용자에게 RSA의 공개키를 준다.

enc1 = bytes_to_long(vgn.encrypt(FLAG))
enc2 = rsa.encrypt(bytes_to_long(key))

print("Hello, this is Boko! I'll send you ciphertexts!")
print("enc1:", enc1)
print("enc2:", enc2)

#output.txt
Hello, this is Boko! I'll send you ciphertexts!
enc1: 25889043021335548821260878832004378483521260681242675042883194031946048423533693101234288009087668042920762024679407711250775447692855635834947612028253548739678779
enc2: 332075826660041992234163956636404156206918624

• 비제네르 암호화를 사용해서 FLAG를 암호화 한다.
• key를 RSA로 암호화 한다.
• 최종적으로 암호화된 값을 사용자에게 출력한다.

 

취약점 분석

• enc2를 해독해서 key 값을 얻어낸 뒤, 그 key를 사용해 enc1을 푸는 문제이다.

핵심 취약점

1. key가 너무 작음 : 4바이트는 숫자로 치면 0~42억정도의 숫자로 컴퓨터 연산으로는 빠르게 계산할 수 있다.
2. 공개 지수 $e$가 너무 작음 : 공개지수 $e=5$로 너무 작아서 공격에 취약하다.
3. 모듈러($N$)은 너무 큼

RSA 암호화 식은 $C = M^e \pmod{N}$이다. 여기서 $M$이 4바이트 정수이므로 $M < 2^{32}$이다. 이를 5제곱 해도 $M^5 < (2^{32})^5 = 2^{160}$dlek.

반면 $N$은 $2^{2048}$정도의 엄청나게 큰 수이다. 즉, $M^5$가 $N$보다 훨씬 작아서 모듈러 연산 $\pmod{N}$이 사실상 일어나지 않는다.

따라서 enc2 값은 그냥 모듈러 연산이 일어나지 않은 $M^5$ 그 자체이다. enc2의 정수 5제곱근을 구하면 바로 key 찾을 수 있다는 것이다.

 

공격

import gmpy2
from Crypto.Util.number import long_to_bytes

# --- 문제에서 주어진 값 ---
e = 5
N = 24778450034785355796150191255487074823099958164427517612668815658468206009158475774203229828058652831641389747402272728790787685762568229069520469756247804941312947307153713830371750706901868389560472732254665749033734649996443767231968425511092244591774647092925931126950380935008196052393893271837275626174525444417778170526468251066473481105512939105882134615031671691748551289394109269703632798650982887859648332846094423809290782207835604174269463315884480062803289020119565250762542625596177768616201281918850432872639983965071018579891448754659608103400036049016809640134053891855019010729470727777892901808607
enc1_int = 25889043021335548821260878832004378483521260681242675042883194031946048423533693101234288009087668042920762024679407711250775447692855635834947612028253548739678779
enc2_int = 332075826660041992234163956636404156206918624

def solve():
    # [Step 1] Key 복구 
    # 모듈러 연산 없이 단순히 5제곱근을 구합니다.
    key_int, is_exact = gmpy2.iroot(enc2_int, e)

    if not is_exact:
        print("[-] Error: Key recovery failed (Not an exact root).")
        return

    key = long_to_bytes(key_int)
    print(f"Recovered Key: {key}")

    # [Step 2] Flag 복구 (Vigenère Decryption)
    # (평문 + 키) % 256 = 암호문  ==>  (암호문 - 키) % 256 = 평문
    enc1 = long_to_bytes(enc1_int)
    flag = b""
    
    for i, char_byte in enumerate(enc1):
        # 복호화: (C - K) % 256
        k = key[i % len(key)]
        decoded_byte = (char_byte - k) % 256
        flag += bytes([decoded_byte])

    print(f"FLAG: {flag.decode()}")

if __name__ == "__main__":
    solve()

 

코드 설명

 

• gmpy2.iroot(enc2_int, 5):
  • 이 함수는 매우 큰 숫자의 n제곱근을 빠르게 계산해준다.
  • is_exact 값을 통해 딱 떨어지는 정수인지 확인할 수 있어, 성공했는지 바로 검증 가능하다.
• long_to_bytes:
  • 숫자로 되어 있는 암호문과 키를 바이트 문자열(b'...')로 변환해준다.
• 복호화 로직:
  • 문제의 암호화 방식 (m + k) % 256의 역연산인 (c - k) % 256을 수행하여 플래그를 복원한다.