cryptofreemedium

POPO (Paillier Operation Performance Optimizer)

HackTheBox

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 c

$ ls tags/ techniques/
modular_arithmeticnonce_reusepaillierhomomorphic_encryptionstate_machine_bugblinding_factoroptimization_flaw
blinding_factor_cancellationstate_manipulationpaillier_decryptionoracle_abuseprivate_key_leak

$ cat /etc/rate-limit

Rate limit reached (20 reads/hour per IP). Showing preview only — full content returns at the next hour roll-over.

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)

...

$ grep --similar

Similar writeups