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

...