Tags: diffie-hellman crypto
Rating:
# 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.
```python
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](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 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
```
