Flag-In-The-Middle

Description

Alice and Bob want to communicate. Since they cannot communicate directly, they need you to act as an intermediary (Alice <-> you <-> Bob). For their security, they first derive a key and then encrypt their messages. Can you crack the encryption?

You can reach Alice at host "sfl.cs.tu-dortmund.de" via TCP-port 10002 and Bob via TCP-port 10003.

public_g = 85

public_p = 1721521895839319678905052879206116244297628155585535737450178608344748052531840924013694224743693

Below is a Message exchange you captured earlier:

1. Alice->Bob: 1620692786992126367441054120788201446232
2. Bob->Alice: 387595310845143558731231784820556640625
3. Bob->Alice: Flag?
4. Alice->Bob: [encrypted first part of the flag]
5. Alice->Bob: Flag?
6. Bob->Alice: [encrypted second part of the flag]

After receiving an encrypted flag part you can decrypt it using the code snippet:

def response_decrypt(response_encrypted, key):
    if (key < pow(2, 130)):
        print("Key maybe too small...")
    response_int = int.from_bytes(response_encrypted, byteorder='big')
    print("Decrypted:", str((int(response_int) ^ key).to_bytes(128, byteorder='big'), 'utf-8'))

Hint 1: SGVyZSBpcyBhbiBweXRob24gZXhhbXBsZSBob3cgdG8gY29ubmVjdCB0byBBbGljZToKCmlwID0gInNmbC5jcy50dS1kb3J0bXVuZC5kZSIKcG9ydCA9IDEwMDAyCmJ1ZmZlclNpemUgPSAxMDI0CgojIENvbm5lY3QgdG8gQWxpY2UKc29jayA9IHNvY2tldC5zb2NrZXQoKQpzb2NrLmNvbm5lY3QoKGlwLCBwb3J0KSkKCiMgV2FpdCBmb3IgQWxpY2UKcmVzcG9uc2UgPSBpbnQoc29jay5yZWN2KGJ1ZmZlclNpemUpLmRlY29kZSgpKQ==

Solution

If you take a look at the captured message protocol, you can see Alice and Bob are, in step one and two, performing a key-exchange. Because we have access to all the message between Alice and Bob we can perform a MitM attack.

To do so a connection to Alice and Bob is needed. A look at "Hint 1" reveals a snippet to connect to Alice. Extended with the public information and the given decryption function the snippet reads like this:

import socket
import time

ip = "sfl.cs.tu-dortmund.de"
port = 10002
bufferSize = 1024

def res_decrypt(res_encrypted, key):
    if (key < pow(2, 130)):
        print("Key maybe too small...")
    response = int.from_bytes(res_encrypted, byteorder='big')
    print("Flag part:", str((int(response) ^ key).to_bytes(128, byteorder='big'), 'utf-8'))

# Connect to Alice
sock = socket.socket()
sock.connect((ip, port))

# Define own private y and public values
private_z = 20
private_y = 20
public_g = 85
public_p = 1721521895839319678905052879206116244297628155585535737450178608344748052531840924013694224743693

# Wait for Alice
response = int(sock.recv(bufferSize).decode())

Based on the the information that there is a public_p, public_g and only two messages needed to exchange the key you can assume Alice and Bob are using RSA. The task is now to catch the key-exchange information, replace parts of it with our own values and so build two key. One for communication with Alice and one for Bob. Then use the keys to encrypt the encrypted_flag messages. Bellow is a sample code that does this:

import socket
import time

ip = "sfl.cs.tu-dortmund.de"
port = 10002
bufferSize = 1024

def res_decrypt(res_encrypted, key):
    if (key < pow(2, 130)):
        print("Key maybe too small...")
    response = int.from_bytes(res_encrypted, byteorder='big')
    print("Flag part:", str((int(response) ^ key).to_bytes(128, byteorder='big'), 'utf-8'))

# Connect to Alice
sock = socket.socket()
sock.connect((ip, port))

# Define own private y and public values
private_z = 20
private_y = 20
public_g = 85
public_p = 1721521895839319678905052879206116244297628155585535737450178608344748052531840924013694224743693

# Wait for Alice to initiate DHKE
response = int(sock.recv(bufferSize).decode())
X = response

# Calculate own public Y and send it to Alice
Y = pow(public_g, private_y) % public_p
sock.send(str(Y).encode())
time.sleep(1)

# Calculate key
key = pow(X, private_y) % public_p

# Ask Alice for her part of the flag
sock.send("Flag?".encode())
response = sock.recv(bufferSize)
print(response)

# Decrypt the flag with calculated key
res_decrypt(response, key)

sock.close()

# Connect to Bob
sock = socket.socket()
sock.connect((ip, 10003))

# Calculate own public Z and send it to Bob
Z = pow(public_g, private_z) % public_p
sock.send(str(Z).encode())

# Wait for Bobs response
response = int(sock.recv(bufferSize).decode())
Y = response

# Calculate key from Bobs response
key = pow(Y, private_z) % public_p

# Ask Bob for his part of the flag
sock.send("Flag?".encode())
response = sock.recv(bufferSize)

# Decrypt the flag with calculated key
res_decrypt(response, key)