Rhome - HackTheBox

Description

I received this lovely letter but the sender put a seal on it. She said that can be opened only at our place, Rhome.

The challenge provides a server implementing Diffie-Hellman key exchange with a menu system to get parameters, reset parameters, and retrieve an encrypted flag.

Analysis

Server Code Review

The server implements a custom Diffie-Hellman class with a critical vulnerability:

class DH:
    def gen_params(self):
        self.r = getPrime(512)
        while True:
            self.q = getPrime(42)  # VULNERABILITY: q is only 42 bits!
            self.p = (2 * self.q * self.r) + 1
            if isPrime(self.p):
                break

        while True:
            self.h = getPrime(42)
            self.g = pow(self.h, 2 * self.r, self.p)  # g has order q
            if self.g != 1:
                break

        self.a = randint(2, self.p - 2)
        self.b = randint(2, self.p - 2)
        self.A, self.B = pow(self.g, self.a, self.p), pow(self.g, self.b, self.p)
        self.ss = pow(self.A, self.b, self.p)

    def encrypt(self, flag_part):
        key = sha256(long_to_bytes(self.ss)).digest()[:16]
        cipher = AES.new(key, AES.MODE_ECB)
        ct = cipher.encrypt(pad(flag_part, 16)).hex()
        return f"encrypted = {ct}"

Vulnerability Breakdown

1. Prime Structure: p = 2 * q * r + 1 where:

   • r is a 512-bit prime
   • q is only a 42-bit prime (extremely small!)

2. Generator Order: The generator g = h^(2*r) mod p has order q, not p-1:

   • Since g^q = h^(2*r*q) = h^(p-1) = 1 mod p (by Fermat's Little Theorem)
   • The discrete log problem is confined to a subgroup of order q

3. Small Subgroup Attack: With q being only 42 bits:

   • Baby-step Giant-step algorithm requires O(sqrt(q)) ~ 2^21 ~ 2 million operations
   • This is computationally trivial on modern hardware

Attack Strategy

1. Obtain DH parameters (p, g, A, B) and encrypted flag from server
2. Factor p-1 to extract the small prime q
3. Verify g^q = 1 mod p to confirm generator order
4. Compute discrete log a where g^a = A mod p using Baby-step Giant-step
5. Calculate shared secret ss = B^a mod p
6. Derive AES key and decrypt the flag

Solution

#!/usr/bin/env python3
"""
Rhome - HackTheBox Crypto Challenge
Small Subgroup Attack on Diffie-Hellman

The vulnerability: generator g operates in a subgroup of order q,
where q is only 42 bits. This makes discrete log feasible via BSGS.
"""
from pwn import *
from Crypto.Util.number import long_to_bytes
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from hashlib import sha256
from sympy import factorint
from math import isqrt
import re

def baby_giant(g, h, p, n):
    """
    Baby-step Giant-step algorithm for discrete logarithm.
    Finds x such that g^x = h mod p, where x < n.
    
    Time complexity: O(sqrt(n))
    Space complexity: O(sqrt(n))
    """
    m = isqrt(n) + 1
    
    # Baby step: compute g^j for j in [0, m)
    # Store in hash table for O(1) lookup
    table = {}
    val = 1
    for j in range(m):
        table[val] = j
        val = (val * g) % p
    
    # Giant step: compute h * (g^(-m))^i for i in [0, m)
    # Looking for collision with baby step table
    factor = pow(g, -m, p)  # g^(-m) mod p
    gamma = h
    for i in range(m):
        if gamma in table:
            x = i * m + table[gamma]
            return x
        gamma = (gamma * factor) % p
    
    return None

def solve():
    # Connect to server
    r = remote('94.237.121.111', 56547)
    
    # Get DH parameters
    r.sendlineafter(b'> ', b'1')
    data = r.recvuntil(b'Choose').decode()
    
    p = int(re.search(r'p = (\d+)', data).group(1))
    g = int(re.search(r'g = (\d+)', data).group(1))
    A = int(re.search(r'A = (\d+)', data).group(1))
    B = int(re.search(r'B = (\d+)', data).group(1))
    
    log.info(f"p = {p}")
    log.info(f"g = {g}")
    log.info(f"A = {A}")
    log.info(f"B = {B}")
    
    # Get encrypted flag
    r.sendlineafter(b'> ', b'3')
    data = r.recvuntil(b'Choose').decode()
    ct = bytes.fromhex(re.search(r'encrypted = ([0-9a-f]+)', data).group(1))
    log.info(f"Ciphertext: {ct.hex()}")
    
    r.close()
    
    # Factor p-1 to find the small prime q
    # p = 2*q*r + 1, so p-1 = 2*q*r
    log.info("Factoring p-1 to find small prime q...")
    factors = factorint((p - 1) // 2, limit=2**50)
    log.info(f"Factors of (p-1)/2: {factors}")
    
    # Find the small 42-bit prime
    q = None
    for factor in factors:
        if 40 <= factor.bit_length() <= 50:
            q = factor
            break
    
    if q is None:
        log.error("Could not find small prime factor!")
        return
    
    log.success(f"Found q = {q} ({q.bit_length()} bits)")
    
    # Verify g has order q
    assert pow(g, q, p) == 1, "g^q != 1 mod p - unexpected!"
    log.success("Verified: g^q = 1 mod p (generator has order q)")
    
    # Compute discrete log using Baby-step Giant-step
    log.info(f"Computing discrete log (BSGS with ~{isqrt(q)} operations)...")
    a = baby_giant(g, A, p, q)
    
    if a is None:
        log.error("BSGS failed to find discrete log!")
        return
    
    log.success(f"Found private key a = {a}")
    
    # Verify: g^a should equal A
    assert pow(g, a, p) == A, "Verification failed: g^a != A"
    log.success("Verified: g^a = A mod p")
    
    # Compute shared secret
    ss = pow(B, a, p)
    log.info(f"Shared secret: {ss}")
    
    # Derive AES key and decrypt
    key = sha256(long_to_bytes(ss)).digest()[:16]
    cipher = AES.new(key, AES.MODE_ECB)
    plaintext = unpad(cipher.decrypt(ct), 16)
    
    log.success(f"FLAG: {plaintext.decode()}")

if __name__ == "__main__":
    solve()

Alternative: Using SageMath

For those who prefer SageMath, the discrete log can be computed directly:

# In SageMath
F = GF(p)
g_sage = F(g)
A_sage = F(A)

# discrete_log automatically uses Pohlig-Hellman + BSGS
a = discrete_log(A_sage, g_sage)

Theory: Why This Works

Pohlig-Hellman Algorithm

When the group order n factors as n = p1^e1 * p2^e2 * ... * pk^ek, the discrete log problem can be solved by:

1. Solving DLP in each subgroup of order pi^ei
2. Combining results using Chinese Remainder Theorem

Small Subgroup Attack

In this challenge:

• p - 1 = 2 * q * r
• Generator g has order q (not p-1)
• All computations happen in the subgroup of order q
• Since q is 42 bits, BSGS needs only ~2^21 operations

Baby-step Giant-step Complexity

For a group of order n:

• Time: O(sqrt(n))
• Space: O(sqrt(n))

For n = 2^42: sqrt(n) = 2^21 ~ 2 million operations (seconds on modern CPU)

References

• Pohlig-Hellman Algorithm
• Baby-step Giant-step
• Small Subgroup Attacks on DH

Lessons Learned

1. Always verify group order: In DH, the security depends on the full group order, not just the prime size
2. Safe prime construction: Use p = 2q + 1 where q is also prime (Sophie Germain prime)
3. Generator validation: Ensure generator has order p-1 (or q for safe primes)
4. Parameter transparency: Be suspicious of custom DH parameter generation