[🥉 Bronze 1] 공유키에 1을 넣으면 비밀이 1로 고정된다 — DreamHack Textbook-DH 풀이

• Alice: 개인키 a, 공개키 A = g^a mod p
• Bob: 개인키 b, 공개키 B = g^b mod p
• 공유비밀: Alice는 B^a = g^(ab), Bob은 A^b = g^(ab) — 같은 값에 도달한다.

여기서 핵심은 받은 값을 그대로 믿고 거듭제곱한다는 점이다. 교과서에 나오는 형태(textbook DH)는 상대가 보낸 공개키가 정말 g^x 꼴인지, 안전한 범위의 값인지 검증하지 않는다. 그래서 중간자가 두 사람 사이에 끼어 공개키를 자기 마음대로 바꿔치기하면, 공유비밀을 원하는 값으로 유도할 수 있다.

가장 극단적인 게 작은/열화(degenerate) 값 주입이다. 상대에게 y를 공개키라며 건네면 상대의 공유비밀은 y^x mod p가 된다. 이때

• y = 1 → 1^x mod p = 1 (개인키 x가 뭐든 항상 1)
• y = 0 → 0^x mod p = 0
• y = p → p^x mod p = 0
• y = p-1 → (-1)^x mod p (x의 홀짝에 따라 1 또는 p-1)

즉 공개키 하나만 바꿔치기해도 상대의 공유비밀을 내가 아는 상수로 못박을 수 있다. 이걸 막으려면 받은 공개키가 {0, 1, p-1} 같은 위험한 값이 아닌지 걸러야 하는데, 교과서 DH엔 그 검증이 없다.

🔬 코드 정찰 — 무엇이 노출되고 무엇이 막혀 있나

Person 클래스가 DH 당사자다. set_shared_key(k)가 받은 값 k를 자기 개인키 x로 거듭제곱해 공유비밀 sk를 만들고, 그걸 md5로 해싱해 AES-ECB 키로 쓴다.

set_shared_key의 세 줄이 전부다. sk = pow(k, self.x, self.p)에서 k는 내가 넣는 값이고, aes_key = md5(str(sk))라 공유비밀만 알면 AES 키가 그대로 나온다. 별도의 인증이나 서명은 없다.

메인 흐름을 보면 중간자 역할이 노골적으로 열려 있다.

순서를 따라가면:

1. prime = getPrime(1024)와 Alice의 공개키를 출력한다.
2. "Let's inturrupt !" — alice_k = int(input(">> "))로 Bob이 받을 키를 내가 직접 입력한다.
3. if alice_k == alice.g: exit("Malicious key !!") — 막는 건 오직 g(=2)와 같을 때뿐이다.
4. bob.set_shared_key(alice_k) → bob.sk = alice_k^(x_bob) mod p.
5. 똑같이 Bob의 공개키를 출력하고, bob_k = int(input(">> "))로 Alice가 받을 키를 입력받는다. 역시 g만 거부.
6. alice.set_shared_key(bob_k) → alice.sk = bob_k^(x_alice) mod p.
7. Alice: encrypt(flag[:half]), Bob: encrypt(flag[half:]) — 각자의 공유비밀로 flag를 절반씩 암호화해 출력.

정리하면, 나는 Bob과 Alice가 각각 받을 공개키를 자유롭게 넣을 수 있고, 서버가 검사하는 건 그 값이 2인지뿐이다.

🐛 삽질 — 어떤 "열화키"를 넣어야 통과하면서 예측되나

정리하면, Alice가 받을 키에도·Bob이 받을 키에도 똑같이 1을 넣으면 된다.

💣 핵심 — 1을 넣으면 양쪽 공유비밀이 1

주입한 1이 두 공유비밀을 어떻게 고정시키는지 수식으로 확인해두자.

• Bob의 공유비밀: bob.sk = pow(1, x_bob, p) = 1 (개인키 x_bob가 무엇이든)
• Alice의 공유비밀: alice.sk = pow(1, x_alice, p) = 1

1의 거듭제곱은 언제나 1이라, 상대의 개인키를 전혀 몰라도 두 sk가 1로 못박힌다. 그러면 두 사람의 AES 키가 똑같이 md5("1")이 된다.

임의의 1024비트 개인키를 여러 개 뽑아 pow(1, x, p)를 돌려도 전부 1이고, 그로부터 md5(str(1)) = md5("1") = c4ca4238a0b923820dcc509a6f75849b가 나온다. 이 키만 있으면 Alice가 만든 앞절반 암호문도, Bob이 만든 뒷절반 암호문도 그대로 복호할 수 있다. flag가 앞뒤로 쪼개져 서로 다른 사람이 암호화했지만, 둘 다 같은 키를 쓰게 만든 것이다.

🎯 익스플로잇 — nc 한 세션으로 두 절반 회수

서버에 붙어 >> 프롬프트가 뜰 때마다 1을 보내면 된다. 첫 번째 1은 Bob이 받을 키, 두 번째 1은 Alice가 받을 키다. 그 뒤 서버가 출력하는 두 hex 암호문을 md5("1") 키로 복호한다.

출력이 흐름을 그대로 보여준다. Bob이 받는 키 = 1 -> sk=1, Alice가 받는 키 = 1 -> sk=1을 거쳐 두 암호문(Alice ct, Bob ct)을 받고, 각각을 복호해 flag 앞절반(DH{6625...0d83)과 flag 뒷절반(...7104})을 얻어 이어붙였다.

🚀 Full Exploit

전체 풀이는 짧다. >> 를 만날 때마다 1을 두 번 보내고, 받은 두 암호문을 md5("1") AES-ECB로 복호해 이어붙인다.

Alice가 앞절반, Bob이 뒷절반을 암호화했으니 복호 결과를 그 순서로 이어붙이면 완전한 flag가 된다.

📝 결론

교과서 DH의 진짜 취약점은 "받은 공개키를 검증하지 않는 것"이다.

이 문제는 중간자가 공개키를 바꿔치기할 수 있는 상황을 그대로 재현했다. Diffie-Hellman은 도청은 막아주지만 인증은 해주지 않는다. 상대가 보낸 값이 정말 정당한 공개키인지 확인하지 않으면, 중간자가 1이나 0 같은 열화값을 흘려 넣어 공유비밀을 원하는 상수로 고정할 수 있다. 실제 프로토콜(TLS 등)이 DH 파라미터에 서명을 붙이고, 받은 공개키가 2 ≤ y ≤ p-2 범위이며 위험한 소부분군에 속하지 않는지 검사하는 이유가 이것이다.

블랙리스트 하나로 막으려 하면 항상 빠져나갈 구멍이 있다.

서버는 key == g만 거부했다. 딱 한 값만 막는 필터는 1, 0, p, p-1처럼 똑같이 위험한 값들을 전부 놓친다. 안전한 값의 화이트리스트(허용 범위를 명시하고 그 밖은 거부)로 검증해야지, 위험한 값 몇 개를 골라 막는 블랙리스트로는 부족하다. 여기에 더해, 공유비밀을 그대로 KDF에 넣지 말고 양측 공개키·세션 정보를 함께 섞어 키를 유도하면(즉 인증된 키 교환) 이런 열화키 주입 자체가 무력화된다.