# 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 weget to pick the prime `p`. The goal is to decrypt the plaintext within 30seconds to get the flag.
```pythonclass 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](http://factordb.com/index.php?query=2%5E2203+-+2).
Now we have a `p` (and a `q` to show it's not backdoored) where `g` is confinedto 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 modeCongrats! Here's the flag: CCC{sm0l_subgr0up_w1th_a_m3rs3nn3_pr1m3}[*] Got EOF while reading in interactive```