[CryptoHack] Diffie-Hellman: Parameter Injection 풀이

 

CryptoHack – Home

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()