You can read up on Diffie-Hellman Key Exchange in various articles, books or get started on Wikipedia. We’ll begin the discourse with a short intro anyway.

Background⌗

In DH key exchange scheme, two interested parties Alice and Bob participate in an exchange, at the end of which both have a shared secret. This secret is jointly computed over their inputs, one of which is kept private.

Let the two parties be Alice and Bob. Two global parameters $g$ and $p$ are decided upon at the start of the exchange. $g$ is the generator of the group $(\mathbb{Z}/p\mathbb{Z})^\times$. $p$ is a prime integer. $g$ is then said to be the primitive root modulo $p$.

Once the exchange begins,

1. Alice chooses an integer $a$, which is her private key. Alice then calculates $A \equiv g^a \pmod{p}$, which is declared as her public key, and is sent to Bob.

2. Bob does the same and chooses b , his private key and calculates $B \equiv g^b \pmod{p}$, his public key. This is sent to Alice.

3. The shared secret $S$ is computed by Alice as $S \equiv B^a \pmod{p}$ and by Bob as $S \equiv A^b \pmod{p}$. Both values are found to be equal.

The challenge⌗ ⌗

The challenge is served to us through a Python script. I’ve snipped away some part of it to maintain focus and left some comments. Take a read.

# The flag is a dummy one. The real flag is set on the server.
FLAG = "CTF{--REDACTED--}"
DEBUG_MSG = "DEBUG MSG - "


# The prime and base
p = 0x509efab16c5e2772fa00fc180766b6e62c09bdbd65637793c70b6094f6a7bb8189172685d2bddf87564fe2a6bc596ce28867fd7bbc300fd241b8e3348df6a0b076a0b438824517e0a87c38946fa69511f4201505fca11bc08f257e7a4bb009b4f16b34b3c15ec63c55a9dac306f4daa6f4e8b31ae700eba47766d0d907e2b9633a957f19398151111a879563cbe719ddb4a4078dd4ba42ebbf15203d75a4ed3dcd126cb86937222d2ee8bddc973df44435f3f9335f062b7b68c3da300e88bf1013847af1203402a3147b6f7ddab422d29d56fc7dcb8ad7297b04ccc52f7bc5fdd90bf9e36d01902e0e16aa4c387294c1605c6859b40dad12ae28fdfd3250a2e9
g = 2

# Decrypt with AES. 
def decrypt(encrypted, shared_secret):
    key = hashlib.md5(long_to_bytes(shared_secret)).digest()
    cipher = AES.new(key, AES.MODE_ECB)
    message = cipher.decrypt(encrypted)
    return message


def main(s):
	# Server calculates its keys
    c = random.randrange(2, p - 1)
    C = pow(g, c, p)

	# Enter our public key here
    M = receiveMessage(s, "Enter The Public Key of The Memory: ")
    shared_secret = pow(M, c, p)

    encrypted_sequence = receiveMessage(s, "Enter The Encrypted Initialization Sequence: ")

	# The cipher text should be a hex digest
    try:
        encrypted_sequence = bytes.fromhex(encrypted_sequence)
        assert len(encrypted_sequence) % 16 == 0

    sequence = decrypt(encrypted_sequence, shared_secret)

    if sequence == b"Initialization Sequence - Code 0":
        sendMessage(s, "\n" + DEBUG_MSG + "Reseting The Protocol With The New Shared Key\n")
        sendMessage(s, DEBUG_MSG + f"{FLAG}")
    else:
        exit()

So we know the plaintext! We need to encrypt the string Initialization Sequence - Code 0 such that it decrypts correctly. But, to our dismay, we find that we don’t know the shared secret and there’s no way to derive it since we never received server’s public key $C$. How can we hope to find the shared secret then?

The solution⌗ ⌗

We don’t need to derive the shared secret if we can just make it predictable! The way to do this would be to send a ‘bad’ public key.

If you see how the shared secret is being derived,

shared_secret = pow(M,c,p)

you’ll notice that our public key is used as the base here, which means we have complete control over group that is being formed. So, if [ M \equiv 0 \pmod{p} ] then

[ S \equiv M^{b} \equiv 0 \pmod{p} ]

And we made $S$ predictable! This is because powers of $M$ are also congruent to 0 mod p.

This means we can send in a ciphertext encrypted with the key ‘0’ and it should decrypt correctly!

from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes
import hashlib

# Send in 0 as our key (shared secret)
key = hashlib.md5(long_to_bytes(0)).digest()
cipher = AES.new(key, AES.MODE_ECB)
message = cipher.encrypt(b"Initialization Sequence - Code 0")
print(message.hex())


# Returns the following digest. This is our encrypted text.
# 1af761314a07bf79f31aeb53bc9e1335e1749e1142b326d82a3c29ac37a042bf

Once we submit the ciphertext to the server, we get our flag! Notice that we entered our public key $M$ as 0.

Key takeaway⌗ ⌗

(Pun intended)

While the order of operations does not matter mathematically, i.e.

$S = A^b = (g^a)^b = (g^b)^a = B^a \pmod{p}$

It clearly did matter to us. This vulnerability was only possible because we had control over the base (And subsequently, the group that was formed).

Note: Instead of 0, we could have also chosen a value of $M$ that is divisible by $p$, and it would have meant the same thing. (Why?)

Exercise to the reader⌗ ⌗

• The full challenge is here: Code. Try solving the challenge yourself by retracing my steps! :)

• The reader is invited to solve a similar Cryptopals challenge based on parameter injection: Challenge.

• What’s the group that we formed?

[\blacksquare\blacksquare\blacksquare]