[CryptoHack] Diffie-Hellman: Export-grade 풀이, SageMath 사용해보기

 

CryptoHack – Home

 

이번 문제도 그냥 MITM이다. 

Overview

Alice와 Bob이 어떠한 값들을 주고받는지 살펴보자.

 

우선, nc로 연결해보면,

Intercepted from Alice: {"supported": ["DH1536", "DH1024", "DH512", "DH256", "DH128", "DH64"]}

이렇게 나오고, Bob은

Intercepted from Bob: {'chosen': 'DH1536'}

이러한 값을 Alice에게 전달하는 것을 볼 수 있다.

즉, Alice는 Bob에게 선택지를 보내고, Bob은 그 중 secret 값으로 사용할 숫자의 길이를 보내는 것 같다.

Exploit - Theory

그렇다면, Alice가 보내는 선택지를 공격자의 임의로 변경해서 보내면 되지않을까?

{'supported': ['DH64']}

로 바꿔서 보내보았다. 그랬더니,

Intercepted from Bob: {'chosen': 'DH64'}

로 답이 왔다.

길이가 64밖에 되지 않는다면, DLP를 풀 수 있을 것만 같다.

64 길이의 DLP 문제를 푸는 것은, 간단하게 SageMath를 이용해서 해결할 수 있다고 한다.

그런데, 내가 SageMath는 초보라서, 지피티와 함께 풀었다.

Exploit - Do it

우선, 이 문제에서도 이전 문제에서 사용했던 AES decrypt 코드를 이용한다고 하였다.

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

from pwn import *

import json

r = remote("socket.cryptohack.org", 13379)

def recv_json():

    ret = json.loads(r.recvuntil('}').decode())

    print(ret)

    return ret

def send_json(msg):

    to_send = json.dumps(msg).encode()

    r.sendline(to_send)

r.recvuntil('Intercepted from Alice: ')

Alice_1 = recv_json()

Alice_1 = {'supported': ['DH64']}

r.recvuntil('Send to Bob: ')

send_json(Alice_1)

r.recvuntil('Intercepted from Bob: ')

Bob_1 = recv_json()

r.recvuntil('Send to Alice: ')

send_json(Bob_1)

r.recvuntil('Intercepted from Alice: ')

Alice_2 = recv_json()

p = int(Alice_2['p'], 16)

g = int(Alice_2['g'], 16)

A = int(Alice_2['A'], 16)

r.recvuntil('Intercepted from Bob: ')

data = recv_json()

B = int(data['B'], 16)

이렇게 해서 Alice와 Bob의 p, g, A, B를 받아볼 수 있다.

하지만, 여기에서 사용된 p의 길이가 64밖에 되지 않기 때문에, 다른 취약점이 아닌, 계산을 통해 문제를 풀 수 있다.

이 아래 이와 같은 코드를 추가해주었다.

# sagemath에서 dlp를 계산하고 돌아옴

a = int(input())

잠시 멈추고, 위의 p, g, A, B를 이용해 a 값을 계산하여 이를 입력하는 과정이다.

$ sage

sage: g = Mod({g}, {p})

sage: A = {A}

sage: a = discrete_log(A, g)

sage: a

이렇게 하면 a값을 얻을 수 있다. (물론 '{}'로 씌워진 곳에는 문자가 아니라 숫자를 입력해야한다.)

이 다음 과정부터는 그냥 Diffie-Hellman 이용해서 계산하고, 보내주면 된다. 간단하다.

shared_secret = pow(B, a, p)

r.recvuntil('Intercepted from Alice: ')

data = recv_json()

iv = data['iv']

encrypted_flag = data['encrypted_flag']

print(decrypt_flag(shared_secret, iv, encrypted_flag))

#crypto{d0wn6r4d35_4r3_d4n63r0u5}

r.close()

 

끝~