Poison Prime

Thanks to Robin Jadoul for helping me make this challenge!

It's Diffie-Hellman, but the parameters are weird.

nc 35.224.135.84 4000

Attachments: server.py

Overview

Alice and Bob use Diffie-Hellman key exchange to encrypt some plaintext, but we get to pick the prime p. The goal is to decrypt the plaintext within 30 seconds to get the flag.

class DiffieHellman:
    def __init__(self, p: int):
        self.p = p
        self.g = 8
        self.private_key = crr.getrandbits(128)

    def public_key(self) -> int:
        return pow(self.g, self.private_key, self.p)

    def shared_key(self, other_public_key: int) -> int:
        return pow(other_public_key, self.private_key, self.p)


def get_prime() -> int:
    p = int(input("Please help them choose p: "))
    q = int(
        input(
            "To prove your p isn't backdoored, "
            + "give me a large prime factor of (p - 1): "
        )
    )

    if (
        cun.size(q) > 128
        and p > q
        and (p - 1) % q == 0
        and cun.isPrime(q)
        and cun.isPrime(p)
    ):
        return p
    else:
        raise ValueError("Invalid prime")


def main():
    print("Note: Your session ends in 30 seconds")

    message = "My favorite food is " + os.urandom(32).hex()
    print("Alice wants to send Bob a secret message")

    p = get_prime()
    alice = DiffieHellman(p)
    bob = DiffieHellman(p)

    shared_key = bob.shared_key(alice.public_key())
    assert shared_key == alice.shared_key(bob.public_key())

    aes_key = hashlib.sha1(cun.long_to_bytes(shared_key)).digest()[:16]
    cipher = AES.new(aes_key, AES.MODE_ECB)
    ciphertext = cipher.encrypt(cup.pad(message.encode(), 16))

    print("Here's their encrypted message: " + ciphertext.hex())

    guess = input("Decrypt it and I'll give you the flag: ")
    if guess == message:
        print("Congrats! Here's the flag: " + os.environ["FLAG"])
    else:
        print("That's wrong dingus")

Solution

Vulnerabilities:

• We pick p
• g is 8

We are also required to provide a large prime factor (128 bits) q for p - 1 so:

• Using Pohlig-Hellman to compute the discrete log isn't possible to do in 30 seconds (and actually the public key isn't even given)
• However, a small subgroup confinement attack might work

Luckily g = 8 is a power of 2, so the trick is to use a Mersenne prime p == 2^k - 1. Here's the reasoning as explained by Robin Jadoul:

The order of 2 (mod 2^k - 1) would be k, since 2^k mod (2^k - 1) is obviously 1. So the order of 8 is at most k since 8 = 2^3, which is in the subgroup of 2.

We can find a list of Mersenne primes here: https://www.mersenne.org/primes/

Next we have to pick one where p - 1 has a prime factor of at least 128 bits. Luckily, we can find that 2^2203 - 1 has one on factordb.

Now we have a p (and a q to show it's not backdoored) where g is confined to a small subgroup. Solve script in solve.py:

$ python3 solve.py
[+] Opening connection to 35.224.135.84 on port 4000: Done
[*] Switching to interactive mode
Congrats! Here's the flag: CCC{sm0l_subgr0up_w1th_a_m3rs3nn3_pr1m3}
[*] Got EOF while reading in interactive

Original writeup (https://github.com/qxxxb/ctf_challenges/blob/master/2021/ccc/crypto/poison_prime/solve).