POPO - HackTheBox CTF

In this HTB challenge, we are given the code that the server is executing. It is implementing the Paillier Cryptosystem, with some differences, which will allow us to recover some useful information so as to get the flag.

Source code

from secret import FLAG
from Crypto.Util.number import bytes_to_long, long_to_bytes, getPrime, GCD
from random import randint
from math import lcm

class POPO:
    def __init__(self, m):
        self.m = m
        self.p = getPrime(1024)
        self.q = getPrime(1024)
        self.n = self.p * self.q
        self.phi = (self.p-1) * (self.q-1)
        self.l = lcm(self.p-1, self.q-1)
        self.n2 = self.n * self.n
        self.g = self.n + 1
        self.gm = pow(self.g, self.m, self.n2)
        self.optim = 0

        while GCD(self.g, self.n) != 1 or \
              GCD(self.g-1, self.n) != 1 or \
              GCD(self.n, (pow(self.g, self.l, self.n2) - 1) // self.n) != 1:
            self.g = randint(self.n, self.n2)

        self.r = randint(self.n, self.n2)

    def anonymize(self, m, r=0):
        if m < 0:
            return {'c': 'No, some mind got you', 'n': self.n}

        if m != self.m and m > 0:
            if self.optim == 0:
                local = pow(self.g, m, self.n2)
            else:
                local = m
        else:
            local = self.gm

        if self.optim == 0:
            self.optim = 1

        if r == 0:
            r = self.r
        
        b = pow(r, self.n, self.n2)
        c = local * b % (self.n2)
        return {'c' : c, 'n' : self.n}

    def encrypt(self, m, r):
        return self.anonymize(m, r)

    def reset_optim(self):
        self.optim = 0

    def test_standard_encryption(self, m1, m2):
        r1 = randint(0, self.n)
        r2 = randint(0, self.n)
        c1 = self.encrypt(m1, r=r1)["c"]
        self.reset_optim()
        c2 = self.encrypt(m2, r=r2)["c"]
        self.reset_optim()
        return {'additive_he' : (c1*c2) % (self.n2), 'res' : (c1*c2) % (self.n2) == self.encrypt(m1 + m2, r1*r2)['c']}

    def validate_role(self, gm):
        if gm == self.gm:
            return {'λ' : self.l}
        else:
            return {"Error": "not enough knowledge provided"}


def menu():
    print("\nPOPO - v.1.0.0. Choose your action:\n")
    print("1. Encrypt")
    print("2. Knowledge proof")
    print("3. Test homomorphic encryption")
    print("4. Reset optimization")

    option = input("\n> ")
    return option

def main():
    popo = POPO(bytes_to_long(FLAG))

    while True:
        choice = int(menu())
        try:
            if choice == 1:
                menu_m = input("\nProvide a message: ").strip()
                print(popo.anonymize(int(menu_m)))
            elif choice == 2:
                menu_gm = input("\nProvide gm: ").strip().encode()
                print(popo.validate_role(int(menu_gm)))
            elif choice == 3:
                menu_multiple_m = input("\nProvide two messages formatted as m1,m2 : ").strip().encode().split(b',')
                print(popo.test_standard_encryption(bytes_to_long(menu_multiple_m[0]), bytes_to_long(menu_multiple_m[1])))
            elif choice == 4:
                popo.reset_optim()
            else:
                print('Nothing to see here.')
                exit(1)
        except Exception as e:
            print("Error during execution")



if __name__ == "__main__":
    main()

Solution

Now on, let $F$ be the integer value of the flag. When the server creates the class, among other values, it generates:

• A random number $n \leq r < n^2$, which is then used for encryption
• A number $g_m = (n+1)^F ~ (\text{mod} ~ n^2)$

Note that, using the Binomial theorem, we get:

\[g_m \equiv (n+1)^F \equiv \sum_{k=0}^n \binom{F}{k} n^k \equiv 1 + nF ~ (\text{mod} ~ n^2)\]

The server allows us to encrypt some messages. There are three modes of encryption with this code, depending on whether $m = 0$ or not, and whether $optim = 0$ or $optim = 1$. If we first encrypt the message $m = 0$, it is easy to see that the final ciphertext will be:

\[c_1 = g_m r^n \equiv (1+nF)r^n ~ (\text{mod} ~ n^2)\]

At this point, $optim = 1$, and we can use the corresponding way of encrypting. If we now encrypt $c_1$, we get:

\[c_2 = c_1 r^n ~ (\text{mod} ~ n^2)\]

So that we can compute $r^n$ as $r^n = c_2 c_1^{-1} ~ (\text{mod} ~ n^2)$. This allows as to compute $g_m$ as well: $1+nF \equiv g_m \equiv c_1 (r^n)^{-1} ~ (\text{mod} ~ n^2)$.

\[nF \equiv c_1(r^n)^{-1} - 1 ~ (\text{mod} ~ n^2)\]

For this to have solution (we want to find $F$), $gcd(n, n^2) = n$ must divide $c_1(r^n)^{-1} - 1$. And as surely $F < n$, we can just set $F = \dfrac{c_1(r^n)^{-1} - 1}{n}$

The solve script is:

import json
from pwn import *
from Crypto.Util.number import long_to_bytes

r = remote("94.237.49.113", 51305)

r.sendlineafter(b"> ", b"1")
r.sendlineafter(b"message: ", b"0")
data = json.loads(r.recvuntil(b'\n').strip().decode().replace("'", "\""))

c1 = int(data["c"])
n = int(data["n"])

r.sendlineafter(b"> ", b"1")
r.sendlineafter(b"message: ", str(c1).encode())
c2 = int(json.loads(r.recvuntil(b"\n").strip().decode().replace("'", "\""))["c"])

rn = (c2 * pow(c1, -1, n**2)) % n**2
gm = (c1*pow(rn, -1, n**2)) % n**2

# These next 3 lines are used to make sure that gm is actually that value
r.sendlineafter(b"> ", b"2")
r.sendlineafter(b"gm: ", str(gm).encode())
assert json.loads(r.recvuntil(b"\n").strip().decode().replace("'", "\""))['λ']


print(long_to_bytes((gm-1)//n).decode())