Rhome
generator g operates within a very small subgroup of the prime field
This challenge implements a Diffie-Hellman (DH) key exchange but introduces a critical mathematical vulnerability: the generator $g$ operates within a very small subgroup of the prime field.
Analysis of the Source (server.py)
The security of Diffie-Hellman relies on the Discrete Logarithm Problem (DLP) being hard. However, the server constructs its parameters $p$ and $g$ in a specific way:
-
Prime Construction: $p = 2qr + 1$, where $q$ is a 42-bit prime and $r$ is a 512-bit prime.
-
Generator Construction: $g = h^{2r} \pmod{p}$.
-
Subgroup Order: By Fermat’s Little Theorem, $h^{p-1} \equiv 1 \pmod{p}$. Since $p-1 = 2qr$, raising $h$ to the power of $2r$ ensures that the order of $g$ is exactly $q$ (or a small factor of $q$).
-
Vulnerability: While $p$ is large (~555 bits), the private exponents $a$ and $b$ effectively only matter modulo the order of $g$. Since the order $q$ is only 42 bits, the search space for the private key is small enough to brute-force or use efficient algorithms.
Exploitation Strategy
To recover the shared secret $ss = g^{ab} \pmod{p}$, we need to find the private exponent $a$.
-
Algorithm: We use the Baby-step Giant-step (BSGS) algorithm, which solves $g^a \equiv A \pmod{p}$ in $O(\sqrt{q})$ time.
-
Complexity: For a 42-bit $q$, the complexity is approximately $2^{21}$ operations, which is trivial for a modern computer (taking only a few seconds).
Execution (solve.py)
The solver follows these steps:
-
Connect to the server and retrieve $p, g, A, B$.
-
Run BSGS to find $a$ such that $g^a \equiv A \pmod{p}$.
-
Compute Shared Secret: $ss = B^a \pmod{p}$.
-
Decrypt: Derive the AES key using
sha256(ss)and decrypt the flag.
Mathematical Summary
The vulnerability lies in the group order:
-
Standard DH: $g$ should generate a large prime-order subgroup (usually 256 bits or more).
-
This Challenge:
$$Order(g) = q \approx 2^{42}$$
$$Time\ Complexity = \sqrt{2^{42}} = 2^{21} \approx 2,097,152 \text{ iterations.}$$
from pwn import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from Crypto.Util.number import long_to_bytes, inverse
from hashlib import sha256
import math
# --- Crypto Helper: Baby-step Giant-step ---
def bsgs(g, A, p, limit_bound):
"""
Solves g^a = A mod p.
limit_bound should be >= the order of g.
"""
# We use limit_bound to set the square root search space
m = math.isqrt(limit_bound) + 1
# Baby steps: {g^i % p: i}
lookup = {}
curr = 1
for i in range(m):
lookup[curr] = i
curr = (curr * g) % p
# Giant steps: A * (g^-m)^j % p
giant_step = pow(inverse(g, p), m, p)
target = A
# We search up to m steps
for j in range(m):
if target in lookup:
return j * m + lookup[target]
target = (target * giant_step) % p
return None
def solve():
# Connect to the server
io = remote("94.237.120.137", 49822)
# 1. Get Parameters
io.sendlineafter(b"> ", b"1")
lines = [io.recvline() for _ in range(4)]
p = int(lines[0].split(b" = ")[1])
g = int(lines[1].split(b" = ")[1])
A = int(lines[2].split(b" = ")[1])
B = int(lines[3].split(b" = ")[1])
# 2. Skip FactorDB. We know q is 42 bits from server.py source code.
# The order of g is q.
# Max value of a 42-bit number is 2^42 - 1.
# We use 2^42 as the upper bound for BSGS.
search_limit = 1 << 42
print("[*] Solving DLP using BSGS with limit 2^42...")
# 3. Solve Discrete Log
# finding 'a' such that g^a = A (mod p)
# Note: This recovers 'a' modulo q, which is sufficient for the shared secret
a = bsgs(g, A, p, search_limit)
if a is None:
print("[-] BSGS failed to find the exponent.")
return
print(f"[+] Recovered private exponent (modulo q): {a}")
# 4. Shared Secret & Flag
# ss = B^a mod p
# Since B is in the same subgroup as g, knowing 'a' mod q is sufficient.
ss = pow(B, a, p)
key = sha256(long_to_bytes(ss)).digest()[:16]
io.sendlineafter(b"> ", b"3")
ct_hex = io.recvline().split(b" = ")[1].strip().decode()
ct_bytes = bytes.fromhex(ct_hex)
cipher = AES.new(key, AES.MODE_ECB)
try:
flag = unpad(cipher.decrypt(ct_bytes), 16)
print(f"\n[!] FLAG: {flag.decode()}")
except Exception as e:
print(f"[-] Decryption failed: {e}")
if __name__ == "__main__":
solve()