> For the complete documentation index, see [llms.txt](https://docs.cooku222.kr/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://docs.cooku222.kr/security/crypto/dreamhack/dreamhack-textbook-dh.md). # \[DreamHack] Textbook-DH #### 문제 링크 [ Textbook-DHDescription Alice와 Bob의 통신을 중간자 드림이가 엿보고 있습니다. 둘의 키교환 과정을 공격해 플래그를 획득해주세요 ! 플래그 형식은 DH{...} 입니다. References https://dreamhack.io/lecture/courses/75dreamhack.io](https://dreamhack.io/wargame/challenges/120) #### 문제
#### WriteUp ``` #!/usr/bin/python3 from Crypto.Util.number import getPrime from Crypto.Util.Padding import pad, unpad from Crypto.Cipher import AES import hashlib import random 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) flag = open("flag", "r").read().encode() prime = getPrime(1024) print(f"Prime: {hex(prime)}") alice = Person(prime) bob = Person(prime) alice_k = alice.calc_key() print(f"Alice sends her key to Bob. Key: {hex(alice_k)}") print("Let's inturrupt !") alice_k = int(input(">> ")) if alice_k == alice.g: exit("Malicious key !!") bob.set_shared_key(alice_k) bob_k = bob.calc_key() print(f"Bob sends his key to Alice. Key: {hex(bob_k)}") print("Let's inturrupt !") bob_k = int(input(">> ")) if bob_k == bob.g: exit("Malicious key !!") alice.set_shared_key(bob_k) 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:])}") ``` -> chall.py -> Diffie-Hellman 키 교환을 진행하는 Alice와 Bob의 통신 사이에서 중간자 공격을 진행함 -> Alice와 Bob에게 전송하려는 정보를 얻은 이후 Bob에게 원하는 정보를 전송할 수도 있고, 그 반대의 과정 또한 진행됨 공격자에 대한 검증이 전혀 없다는 점을 이용해 Bob(또한 Alice)의 의도된 동작과 동일하게 행동하여 키를 공유할 수도 있고, 악의적인 값을 송신할 수도 있다. #### Exploit 올바른 Alice와 Bob처럼 행동 Diffie-Hellman 키 교환을 수행하고 나면 두 송/수신자는 서로 같은 키를 공유함. \=> Alice와의 통신에서 올바른 Bob처럼 행동하면 결과적으로 Alice와 동일한 키를 공유하게 됨 -> 같은 방식으로 Bob과의 통신에서 올바른 Alice처럼 행동하면 Bob과 동일한 키를 공유하게 됨 \*Alice와 통신하는 가짜 Bob인 not\_bob과, Bob과 통신하는 가짜 Alice인 not\_alice를 생성하여 다음의 솔브 코드를 작성함 ``` from pwn import * from Crypto.Util.Padding import pad, unpad from Crypto.Cipher import AES import hashlib class Person(object): ... io = remote("host3.dreamhack.games", 9957) io.recvuntil(b"Prime: ") p = int(io.recvline(), 16) not_alice, not_bob = Person(p), Person(p) # Communication 1 io.recvuntil(b"Key: ") not_bob.set_shared_key(int(io.recvline(), 16)) io.sendlineafter(">> ", str(not_alice.calc_key()).encode()) # Communication 2 io.recvuntil(b"Key: ") not_alice.set_shared_key(int(io.recvline(), 16)) io.sendlineafter(">> ", str(not_bob.calc_key()).encode()) # Alice's shared key is same with not_bob's shared key io.recvuntil(b"Alice: ") flag1 = not_bob.decrypt(io.recvline().decode()) # Bob's shared key is same with not_alice's shared key io.recvuntil(b"Bob: ") flag2 = not_alice.decrypt(io.recvline().decode()) io.close() print((flag1 + flag2).decode()) ``` 악의적인 값 송신 -> Alice의 키를 의도되지 않은 값으로 설정하기 위해 실제로 생성되지 않은 악의적인 값을 전달할 수 있다. 간편한 설명을 위해 Alice의 비밀키 x를 xa, Bob의 비밀키 x를 xb라고 부른다. g와 연관된 값 송신 Alice가 Bob에게 보내는 정보와 Bob이 Alice에게 보내는 정보를 통해 g^xa, g^xb의 값을 알 수 있음 k라는 값을 Bob에서 수신하게 된다면 Bob의 키는 k^xb로 설정하게 됨 If) k의 값을 알려진 값인 g=2로 설정하게 된다면 Bob의 키는 g^xb 설정되어, 공격자가 아는 값으로 설정됨 Alice의 키도 동일함 \=> 이를 방지하기 위해 Alice, Bob은 수신된 값이 g와 동일할 경우 "Malicious Key!!"를 출력하며 통신을 종료하지만, 모든 연산은 p를 modulus로 삼아 이루어지기 때문에 p+q와 같은 값을 송신하는 것으로도 동일한 결과를 가져올 수 있음 ``` from pwn import * from Crypto.Util.Padding import pad, unpad from Crypto.Cipher import AES import hashlib def decrypt(shared, ciphertext): aes_key = hashlib.md5(str(shared).encode()).digest() cipher = AES.new(aes_key, AES.MODE_ECB) return unpad(cipher.decrypt(ciphertext), 16) io = remote("host3.dreamhack.games", 9957) io.recvuntil(b"Prime: ") p = int(io.recvline(), 16) g = 2 # Communication 1 io.recvuntil(b"Key: ") alice_data = int(io.recvline(), 16) io.sendlineafter(">> ", str(p + g).encode()) # Communication 2 io.recvuntil(b"Key: ") bob_data = int(io.recvline(), 16) io.sendlineafter(">> ", str(p + g).encode()) io.recvuntil(b"Alice: ") flag1 = decrypt(alice_data, bytes.fromhex(io.recvline().decode())) io.recvuntil(b"Bob: ") flag2 = decrypt(bob_data, bytes.fromhex(io.recvline().decode())) io.close() print((flag1 + flag2).decode()) ``` 또한 g^2를 송신하게 되면 Bob의 키는 (g^2)^xb = (g^xb)^2로 설정되게 되어 이 또한 공격자가 연산하여 알아낼 수 있는 값에 속함 ``` # Communication 1 io.recvuntil(b"Key: ") alice_data = int(io.recvline(), 16) io.sendlineafter(">> ", str(g**2).encode()) # Communication 2 io.recvuntil(b"Key: ") bob_data = int(io.recvline(), 16) io.sendlineafter(">> ", str(g**2).encode()) io.recvuntil(b"Alice: ") flag1 = decrypt(alice_data**2 % p, bytes.fromhex(io.recvline().decode())) io.recvuntil(b"Bob: ") flag2 = decrypt(bob_data**2 % p, bytes.fromhex(io.recvline().decode())) ``` 특수한 값 송신 0은 얼마를 거듭제곱하여도 0의 결과를 가지고, 1도 동일한 성질을 가지고 있다. => 따라서 0 or 1을 송신하게 되면 Alice, Bob의 키가 0 또는 1로 설정됨 ``` from pwn import * from Crypto.Util.Padding import pad, unpad from Crypto.Cipher import AES import hashlib def decrypt(shared, ciphertext): aes_key = hashlib.md5(str(shared).encode()).digest() cipher = AES.new(aes_key, AES.MODE_ECB) return unpad(cipher.decrypt(ciphertext), 16) io = remote("host3.dreamhack.games", 9957) io.sendlineafter(">> ", b"0") io.sendlineafter(">> ", b"0") io.recvuntil(b"Alice: ") flag1 = decrypt(0, bytes.fromhex(io.recvline().decode())) io.recvuntil(b"Bob: ") flag2 = decrypt(0, bytes.fromhex(io.recvline().decode())) io.close() print((flag1 + flag2).decode()) ``` 이산 로그 문제(Discrete Log Problem) -> g^xa의 값으로부터 비밀키 xa의 값을 알아낼 가능성 또한 완전히 배제할 수는 없다. -> 이산 로그 문제(Discrete Log Problem)에 해당하는 문제, 임의의 1024비트 소수로 설정된 p가 p-1이 smooth해서 취약할 경우 해결할 수 있는 문제 일반적으로는 랜덤한 소수가 Smooth prime일 확률은 굉장히 낮아서 이 문제를 해당하는 방법으로 해결하기는 어려우나, 이 가능성조차 완전히 배제하기 위해서는 Pycryptodome의 getStrongPrime과 같이 강제적으로 Smooth prime이 되지 않게 하는 함수를 사용하여 소수 p를 생성하는 방법이 존재함 --- # Agent Instructions This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com. ## Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://docs.cooku222.kr/security/crypto/dreamhack/dreamhack-textbook-dh.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.