CryptoHack – Home
A free, fun platform to learn about cryptography through solving challenges and cracking insecure code. Can you reach the top of the leaderboard?
cryptohack.org
Diffie-Hellman Key exchange
이 프로토콜은 DLP:Discrete Logarithm Problem을 바탕으로 만들어진 키 교환 프토로콜이다.
$A = g^a mod\ p$
를 알고 있을 때, $(g, p, A)$를 모두 알고 있어도, $a$ 값은 알기 어렵다는 것을 기반으로 하고 있다.
좀 더 자세히 보면,
Alice와 Bob이 통신키(세션키)를 교환하고자 할 때 안전하게 교환하는 프로토콜이다.
1. Alice가 $a < p$인 secret 값 $a$ 를 정한다.
2. Alice -> Bob: $\{g, p, A=g^{a} mod\ p\}$ 를 전송한다.
3. Bob: $b < p$인 secret 값 $b$를 정한다.
4. Bob: $\{A^{b} mod\ p\}$ 를 계산한다. 이게 둘 사이의 shared secret이다. $A^b mod\ p = g^{ab} mod\ p$
5. Bob -> Alice: $\{B=g^{b} mod\ p\}$ 를 전송한다.
6. Alice: $B^a mod\ p$ 를 계산한다. ($B^{a} mod\ p = g^{ba} mod\ p$)
이렇게 되면, Alice와 Bob은 안전하게 세션키를 교환할 수 있다.
Exploit - theori
그런데 여기서, 중간에 통신을 가로챌 수 있는 중간자가 있다면, 이 프로토콜을 깰 수 있다. :MITM: Man In The Middle attack
공격자 Carol을 가정하고, 위 프로토콜을 깨보자.
이 때, Carol은 본인만의 Malicious한 secret 값 $c$를 생성한다.
1. Alice가 $a < p$인 secret 값 $a$ 를 정한다.
2. Alice -> Bob: $\{g, p, A=g^a mod\ p\}$ 를 전송한다.
Carol이 위 데이터를 가로채서, $\{g, p, A=g^c mod\ p\}$ 를 Bob에게 전송한다.
3. Bob: $b < p$인 secret 값 $b$를 정한다.
4. Bob: $A^b mod\ p$ 를 계산한다. 이게 둘 사이의 shared secret이다. $A^b mod\ p = g^{cb} mod\ p$
5. Bob -> Alice: $\{B=g^b mod\ p\}$ 를 전송한다.
Carol이 위 데이터를 가로채서, $\{B=g^c mod\ p\}$를 Alice에게 전송한다.
6. Alice: $B^a mod\ p$ 를 계산한다. $(B^a mod\ p = g^{ca} mod\ p)$
이러한 과정을 거치면, Carol은 Alice와 Bob의 세션키를 모두 가지고있게 된다.
Alice의 통신키: $g^{ac} mod\ p$
Bob의 통신키: $g^{bc} mod\ p$
이를 통해, Carol은 Man In The Middle에서 둘 사이의 통신을 마음대로 쥐락펴락 할 수 있다.
Exploit - do it
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import hashlib
def is_pkcs7_padded(message):
padding = message[-message[-1]:]
return all(padding[i] == len(padding) for i in range(0, len(padding)))
def decrypt_flag(shared_secret: int, iv: str, ciphertext: str):
# Derive AES key from shared secret
sha1 = hashlib.sha1()
sha1.update(str(shared_secret).encode('ascii'))
key = sha1.digest()[:16]
# Decrypt flag
ciphertext = bytes.fromhex(ciphertext)
iv = bytes.fromhex(iv)
cipher = AES.new(key, AES.MODE_CBC, iv)
plaintext = cipher.decrypt(ciphertext)
if is_pkcs7_padded(plaintext):
return unpad(plaintext, 16).decode('ascii')
else:
return plaintext.decode('ascii')
# protocol
from pwn import *
import json
import os
from Crypto.Util.number import *
r = remote('socket.cryptohack.org', 13371)
r.recvuntil('Intercepted from Alice: ')
Alice = json.loads(r.recvline().decode())
p = int(Alice['p'], 16)
g = int(Alice['g'], 16)
A = int(Alice['A'], 16)
c = bytes_to_long(os.urandom(100))
payload = json.dumps({'p':hex(p),'g':hex(g),'A':hex(p)})
r.recvuntil('Send to Bob: ')
r.sendline(payload)
r.recvuntil('Intercepted from Bob: ')
Bob = json.loads(r.recvline().decode())
B = int(Bob['B'], 16)
r.recvuntil('Send to Alice: ')
C = pow(g, c, p)
payload = json.dumps({'B': hex(C)})
r.sendline(payload)
r.recvuntil('Intercepted from Alice: ')
data = json.loads(r.recvline().decode())
iv = data['iv']
encrypted_flag = data['encrypted_flag']
shared_secret = pow(A, c, p)
print(decrypt_flag(shared_secret, iv, encrypted_flag))
# crypto{n1c3_0n3_m4ll0ry!!!!!!!!}
r.close()