# 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}))

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