POPO (Paillier Operation Performance Optimizer) — HackTheBox

Description

An unknown and shady startup is selling its new product, called "POPO" - Paillier Operation Performance Optimizer. Our colleague Bongio claimed to have identified a confidentiality problem, but has now disappeared under mysterious circumstances. Before she disappeared, she published the suspicious code. It is time to get clarity and rescue her.

The server implements a Paillier homomorphic encryption system with a menu-driven interface offering encryption, knowledge proof (validate_role), homomorphic encryption testing, and optimization reset. The flag is encrypted as the message m during initialization: popo = POPO(bytes_to_long(FLAG)).

Analysis

Paillier Cryptosystem Background

Paillier is an additive homomorphic encryption scheme where:

• Key generation: n = p·q, g = n+1, λ = lcm(p-1, q-1)
• Encryption: c = g^m · r^n mod n² (where r is a random blinding factor)
• Decryption: m = L(c^λ mod n²) · μ mod n, where L(x) = (x-1)/n and μ = L(g^λ mod n²)⁻¹ mod n

The Vulnerability: optim State Bug

The anonymize() method has a critical state-dependent behavior controlled by self.optim:

• When optim=0 (first call): properly computes local = g^m mod n², then flips optim to 1.
• When optim=1 (subsequent calls): uses the raw input m directly as local — completely skipping the exponentiation step.

Additional Weaknesses

1. Nonce reuse: The same self.r is used for all encryptions when no explicit r is provided, meaning b = r^n mod n² is constant across calls.
2. Private key oracle: validate_role(gm) returns λ = lcm(p-1, q-1) if the correct gm is provided — leaking the Paillier private key.
3. Branch control: Sending m=0 forces the else branch (local = self.gm), giving us the encrypted flag component directly.

Solution

Exploit Chain (3 steps to recover gm)

...