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)

Step	Action	What happens	Result
1	Encrypt m=1 (optim=0→1)	local = g^1, c = g · rⁿ mod n²	Triggers optim flip
2	Encrypt m=1 (optim=1)	local = 1 (raw!), c = 1 · rⁿ mod n²	Leaks b = rⁿ mod n²
3	Encrypt m=0	m > 0 is False → local = self.gm, c = gm · rⁿ mod n²	Encrypted flag with known blinding

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.

#!/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()