Human Server – Union CTF 2021

Points: 100 (N+ solves)

Given: human_server.py

TLDR

  1. We are given an implementation of a Diffie-Hellman key-exchange over Elliptic Curves with a weird XOR when computing the key.

  2. Exploit this extra information to try to “get rid of the discrete log”.

  3. You might have heard of this recently Cryptography Dispatches: The Most Backdoor-Looking Bug I’ve Ever Seen

Program

The relevant part of the code is the one below.

CURVE = secp256k1
ORDER = CURVE.q
G = CURVE.G

class EllipticCurveKeyExchange():
    def __init__(self):
        self.private = random.randint(0,ORDER)
        self.public = self.get_public_key()
        self.recieved = None
        self.nonce = None
        self.key = None

    def get_public_key(self):
        A = G * self.private
        return A

    def send_public(self):
        return print(json.dumps({"Px" : self.public.x, "Py" : self.public.y}))

    def receive_public(self, data):
        """
        Remember to include the nonce for ultra-secure key exchange!
        """
        Px = int(data["Px"])
        Py = int(data["Py"])
        self.recieved = Point(Px, Py, curve=secp256k1)
        self.nonce = int(data['nonce'])

    def get_shared_secret(self):
        """
        Generates the ultra secure secret with added nonce randomness
        """
        assert self.nonce.bit_length() > 64
        self.key = (self.recieved * self.private).x ^ self.nonce

    def check_fingerprint(self, h2: str):
        """
        If this is failing, remember that you must send the SAME
        nonce to both Alice and Bob for the shared secret to match
        """
        h1 = hashlib.sha256(long_to_bytes(self.key)).hexdigest()
        return h1 == h2

    def send_fingerprint(self):
        return hashlib.sha256(long_to_bytes(self.key)).hexdigest()

Attack

Looking at the weird XOR in the computation of get_shared_secret reminded us of the recent post stated above Cryptography Dispatches: The Most Backdoor-Looking Bug I’ve Ever Seen. Looking there the attack is quite simple

  1. Alice generates \( a \), computes \( g^a \), and sends \( g^a \) to Bob;
  2. Eve intercepts this message, generates \( t \) and a nonce \( n \), and sends \( (g^t, n) \) to Bob;
  3. Bob receives this message, generates \( b \), computes \( g^b \), and sends \( g^b \) to Alice;
  4. Bob’s shared key is now \( (g^t)^b \oplus n \);
  5. Eve intercepts the message by Bob and sends to Alice \( (g^t, (g^a)^t \oplus (g^b)^t \oplus n) \)instead;
  6. Alice receives this message and computes the shared key as
\[\begin{align} (g^t)^a \oplus \texttt{received\_nonce} &= (g^t)^a \oplus (g^a)^t \oplus (g^b)^t \oplus n =(g^b)^t \oplus n \\ &= \textrm{Bob's shared key} \end{align}\]

In our case, we have this same problem but over EC and the computation of the shared key only uses the x component

self.key = (self.recieved * self.private).x ^ self.nonce

The attack is thus as follows

  1. Alice generates \( a \), computes \( pkey_A = G\ast a \), and sends \( G\ast a \) to Bob;
  2. Eve intercepts this message, generates \( t \) and a nonce \( n \), and sends \( (G\ast t, n) \) to Bob;
  3. Bob receives this message, generates \( b \), computes \( pkey_B = G\ast b \), and sends \( G\ast b \) to Alice;
  4. Bob’s shared key is now \( ((G\ast t)\ast b).x \oplus n \);
  5. Eve intercepts the message by Bob and sends to Alice \( (G\ast t, (pkey_A\ast t).x \oplus (pkey_B\ast t).x \oplus n) \) instead;
  6. Alice receives this message and computes the shared key as
\[\begin{align} (G\ast t)\ast a \oplus \texttt{received\_nonce} &= (G\ast t)\ast a \oplus (pkey_A\ast t).x \oplus (pkey_B\ast t).x \oplus n \\ &= (G\ast t)\ast a \oplus ((G\ast a)\ast t).x \oplus ((G\ast b)\ast t).x \oplus n \\ &= ((G\ast b)\ast t).x \oplus n \\ &= \textrm{Bob's shared key} \end{align}\]

In our exploit we used the nonce \( n = t \). And the flag is :man_facepalming:

b'union{https://buttondown.email/cryptography-dispatches/archive/cryptography-dispatches-the-most-backdoor-looking/}\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e'

Resources

The code for the solution can be downloaded here.