POPO (Paillier Operation Performance Optimizer)

Platform: HackTheBox | Category: Cryptography | Type: Challenge | Difficulty: Medium | OS: NA | Author: D3v0o0Nu11 | Date: 2026-02-27 | Status: Solved Techniques: blinding_factor_cancellation, oracle_abuse, paillier_decryption, private_key_leak, state_manipulation

Summary

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

Recon

Port scan

 bash read-only • copy allowed Copy
nmap -p- -sV -sC <TARGET> --min-rate 1000 -Pn

Enumeration highlights

• Event: HackTheBox | ID: 20260227_hackthebox_popo
• Tags: modular_arithmetic, nonce_reuse, paillier, homomorphic_encryption, state_machine_bug, blinding_factor, optimization_flaw
• Indicators: Paillier cryptosystem (g = n+1, n²), optim state variable toggling encryption behavior, same r reused across encryptions, validate_role leaks λ = lcm(p-1
• Source: 20260227_hackthebox_popo.md

Foothold

Vulnerability / Misconfiguration

1. blinding_factor_cancellation
2. oracle_abuse
3. paillier_decryption
4. private_key_leak
5. state_manipulation

 bash read-only • copy allowed Copy
<command>

Exploitation

• See original writeup content for detailed exploitation.

Privilege Escalation

Enumeration

 bash read-only • copy allowed Copy
sudo -l
find / -perm -4000 2>/dev/null
getcap -r / 2>/dev/null
cat /etc/crontab
ps aux

Exploitation

1. N/A for challenge-type writeup; see exploitation above.
2. Flag obtained via challenge solve.

 bash read-only • copy allowed Copy
<command>

Flags

Key Takeaways / Lessons

• blinding_factor_cancellation
• oracle_abuse
• paillier_decryption
• private_key_leak
• state_manipulation
• Tags: modular_arithmetic, nonce_reuse, paillier, homomorphic_encryption, state_machine_bug, blinding_factor, optimization_flaw

Original Writeup

<details><summary>Click to expand original content</summary>

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)

Since the same self.r is used each time, we can divide out the blinding factor: gm = c₃ · b⁻¹ mod n²

With the recovered gm, call validate_role(gm) to get λ, then standard Paillier decryption recovers the flag.

 python read-only • copy allowed Copy
#!/usr/bin/env python3
from pwn import *
from Crypto.Util.number import long_to_bytes
import re

HOST = "154.57.164.81"
PORT = 30852

def send_choice(r, choice):
    r.recvuntil(b"> ")
    r.sendline(str(choice).encode())

def encrypt(r, m):
    send_choice(r, 1)
    r.recvuntil(b"Provide a message: ")
    r.sendline(str(m).encode())
    resp = r.recvline().decode().strip()
    c_match = re.search(r"'c'\s*:\s*(\d+)", resp)
    n_match = re.search(r"'n'\s*:\s*(\d+)", resp)
    c = int(c_match.group(1))
    n = int(n_match.group(1))
    return c, n

def reset_optim(r):
    send_choice(r, 4)

def validate_role(r, gm):
    send_choice(r, 2)
    r.recvuntil(b"Provide gm: ")
    r.sendline(str(gm).encode())
    resp = r.recvline().decode().strip()
    l_match = re.search(r"'λ'\s*:\s*(\d+)", resp)
    if l_match:
        return int(l_match.group(1))
    return None

r = remote(HOST, PORT)

# Step 1: Encrypt m=1 with optim=0 -> sets optim=1
c1, n = encrypt(r, 1)
n2 = n * n

# Step 2: Encrypt m=1 with optim=1 -> local = m = 1 (raw!)
c2, _ = encrypt(r, 1)
b = c2  # This is r^n mod n²

# Step 3: Encrypt m=0 -> local = self.gm
c3, _ = encrypt(r, 0)

# Step 4: Recover gm = c3 * inverse(b) mod n²
gm = (c3 * pow(b, -1, n2)) % n2

# Step 5: Validate role with gm to get lambda
lam = validate_role(r, gm)

# Step 6: Standard Paillier decryption
g = n + 1
gl = pow(g, lam, n2)
L_gl = (gl - 1) // n
mu = pow(L_gl, -1, n)

gml = pow(gm, lam, n2)
L_gml = (gml - 1) // n

m = (L_gml * mu) % n
flag = long_to_bytes(m)
print(f"FLAG: {flag.decode()}")

r.close()

</details>

---

signed by XESXOR