willwam

HackPack CTF 2022

Thanks for the fun challenges @Polymero!

Challenge Name Tags
repeating offence homomorphic rsa pallier
P(ai)^3 pallier faulty

repeating offence

from Crypto.Util.number import getPrime, inverse, GCD
from secrets import randbelow
import os, hashlib

with open('flag.txt','rb') as f:
    FLAG = f.read().decode().strip()
    f.close()

class RSA_then_Paillier:
    """ Layered Cipher of RSA : Zn -> Zn then Paillier : Zn -> Zn2. """

    def __init__(self, domain: tuple):
        # Class parameters
        P, Q = domain
        self.HISTORY = []

        # RSA public key
        self.E = 0x10001
        self.N = P * Q

        # RSA private key
        F = (P - 1) * (Q - 1)
        self.D = inverse(self.E, F)

        # Paillier public key
        self.G = randbelow(self.N * self.N)

        # Paillier private key
        self.L = F // GCD(P - 1, Q - 1)
        self.U = inverse((pow(self.G, self.L, self.N * self.N) - 1) // self.N, self.N)


    def encrypt(self, msg: int) -> int:
        # RSA
        cip_rsa = pow(msg, self.E, self.N)

        # Paillier
        g_m = pow(self.G, cip_rsa, self.N * self.N)
        r_n = pow(randbelow(self.N), self.N, self.N * self.N)
        cip = (g_m * r_n) % (self.N * self.N)

        # Update HISTORY
        self.HISTORY += [hashlib.sha256(cip.to_bytes(256, 'big')).hexdigest()]
        return cip


    def decrypt(self, cip: int) -> int:
        # Check HISTORY
        if hashlib.sha256(cip.to_bytes(256, 'big')).hexdigest() in self.HISTORY:
            return -1

        # Paillier
        cip_rsa = ((pow(cip, self.L, self.N * self.N) - 1) // self.N * self.U) % self.N

        # RSA
        return pow(cip_rsa, self.D, self.N)


class Paillier_then_RSA:
    """ Layered Cipher of Paillier : Zn -> Zn2 then RSA : Zn2 -> Zn2. """

    def __init__(self, domain: tuple):
        # Class parameters
        P, Q = domain
        self.HISTORY = []

        # RSA public key
        self.E = 0x10001
        self.N = P * Q

        # RSA private key
        F = (P - 1) * (Q - 1) * self.N
        self.D = inverse(self.E, F)

        # Paillier public key
        self.G = randbelow(self.N * self.N)

        # Paillier private key
        self.L = F // self.N
        self.U = inverse((pow(self.G, self.L, self.N * self.N) - 1) // self.N, self.N)


    def encrypt(self, msg: int) -> int:
        # Paillier
        g_m = pow(self.G, msg, self.N * self.N)
        r_n = pow(randbelow(self.N), self.N, self.N * self.N)
        cip_pai = (g_m * r_n) % (self.N * self.N)

        # RSA
        cip = pow(cip_pai, self.E, self.N * self.N)

        # Update HISTORY
        self.HISTORY += [hashlib.sha256(cip.to_bytes(256, 'big')).hexdigest()]
        return cip


    def decrypt(self, cip: int) -> int:
        # Check HISTORY
        if hashlib.sha256(cip.to_bytes(256, 'big')).hexdigest() in self.HISTORY:
            return -1

        # RSA
        cip_pai = pow(cip, self.D, self.N * self.N)

        # Paillier
        return ((pow(cip_pai, self.L, self.N * self.N) - 1) // self.N * self.U) % self.N
    
DOMAIN = [getPrime(512) for _ in range(2)]

STAGE_1, STAGE_2 = True, False
RTP = RSA_then_Paillier(DOMAIN)
print("|\n|  STAGE 1 :: RSA-then-Paillier\n|\n|   N: {}\n|   G: {}".format(RTP.N, RTP.G))

RTP_PWD = int.from_bytes(os.urandom(32).hex().encode(), 'big')
print("|\n|  RTP(Password): {}".format(RTP.encrypt(RTP_PWD)))

while STAGE_1:
    print("|\n|\n|  MENU:\n|   [E]ncrypt\n|   [D]ecrypt\n|   [S]ubmit Password")
    choice = input("|\n|  >>> ").lower()
    if choice == 'e':
        user_input = input("|\n|  MSG(int): ")
        print("|\n|  CIP ->", RTP.encrypt(int(user_input)))            
    elif choice == 'd':
        user_input = input("|\n|  CIP(int): ")
        print("|\n|  MSG ->", RTP.decrypt(int(user_input)))    
    elif choice == 's':
        user_input = input("|\n|  PWD(int): ")
        if user_input == str(RTP_PWD):
            print("|\n|\n|  Correct ~ On to Stage 2!\n|")
            STAGE_2 = True
            break

if STAGE_2:
    PTR = Paillier_then_RSA(DOMAIN)
    print("|\n|  STAGE 2 :: Paillier-then-RSA\n|   N: {}\n|   G: {}\n|".format(RTP.N, RTP.G))
    PTR_PWD = int.from_bytes(os.urandom(32).hex().encode(), 'big')
    print("|\n|  PTR(Password): {}".format(PTR.encrypt(PTR_PWD)))

while STAGE_2:
    print("|\n|\n|  MENU:\n|   [E]ncrypt\n|   [D]ecrypt\n|   [S]ubmit Password")
    choice = input("|\n|  >>> ").lower()
    if choice == 'e':
        user_input = input("|\n|  MSG(int): ")
        print("|\n|  CIP ->", PTR.encrypt(int(user_input)))            
    elif choice == 'd':
        user_input = input("|\n|  CIP(int): ")
        print("|\n|  MSG ->", PTR.decrypt(int(user_input)))    
    elif choice == 's':
        user_input = input("|\n|  PWD(int): ")
        if user_input == str(PTR_PWD):
            print("|\n|\n|  Correct ~ Here's your flag: {}\n|".format(FLAG))
            break

We’re given a service where we need to recover two passwords after being given the encryption of them. They are encrypted using a combination of the RSA and Pallier cryptosystems, the first being RSA first, then Pallier, and the second Pallier first, then RSA. We are able to encrypt and decrypt arbitrary messages, however we are not able to decrypt a message that has already been encrypted before, which includes the passwords.

solution

We denote RSA encryption as $R(x)$, and Pallier encryption as $P(x)$

The main idea for this challenge is that both the RSA and Pallier cryptosystems are homomorphic. This gives us a few properties of them that we can abuse, namely:

  • $R(a) * R(b) = R(a * b)$
  • $R(a)^{x} = R(a^x)$
  • $P(a) * P(b) = P(a + b)$
  • $P(a)^{x} = P(a * x)$

These will prove very useful for us later. Also keep in mind that we can encrypt using either one of RSA or Pallier individually, as these are public key cryptosystems, and we are luckily provided with the public key.

Anyway, let’s look at the two stages.

stage 1

We are given $C = P(R(p))$, where we need to find $p$.

The idea for this stage is to raise $C$ to the power of $R(x)$ for some known $x$. Then, using the properties above:

$C^{R(x)} = P(R(p))^{R(x)} = P(R(p) * R(x)) = P(R(p*x))$

and then we can ask the server to decrypt that to get $p * x$. Since we know $x$, we divide to get $p$.

stage 2

We are given $C = R(P(p))$, where we need to find $p$.

For this stage, we observe what happens when we multiply encryptions together:

$R(P(a)) * R(P(b)) = R(P(a) * P(b)) = R(P(a + b))$

So, notice that we can set $a = p$ and then $b$ to be some known value. We encrypt $b$ and then multiply the encryption with the flag encryption to get $R(P(p + b))$. We ask the server to decrypt this to get $p + b$, and then since we know $b$, subtract it to get $p$.

Submitting these passwords gives us the flag. Solve script below:

from pwn import *

s = remote("cha.hackpack.club", 10996)

def encrypt(msg):
    s.sendlineafter(">>>", "E")
    s.sendlineafter("MSG(int):", str(msg))
    s.recvuntil("CIP ->")
    return int(s.recvline())

def decrypt(cip):
    s.sendlineafter(">>>", "D")
    s.sendlineafter("CIP(int):", str(cip))
    s.recvuntil("MSG ->")
    return int(s.recvline())

def submit(password):
    s.sendlineafter(">>>", "S")
    s.sendlineafter("PWD(int):", str(password))

s.recvuntil("N:")
n = int(s.recvline())

# Stage 1
s.recvuntil("(Password):")
c1 = int(s.recvline())
Rb = pow(2, 0x10001, n)
C = pow(c1, Rb, n**2)
passx = decrypt(C)
password = passx * pow(2, -1, n)
submit(password % n)

# Stage 2
s.recvuntil("(Password):")
c2 = int(s.recvline())
Rb = encrypt(2)
password = decrypt((Rb * c2) % n**2) - 2
submit(password)

s.recvuntil("flag:")
print(s.recvline().decode())

Flag: flag{s4dly_f0r_y0u_j41l_t1m3_1s_n0t_h0m0m0rph1c4lly_r3duc1bl3}

unintended solution

There’s actually a pretty trivial unintended solution to this challenge: notice that the server does not take mod $n^2$ when checking history, however it does (effectively) take mod $n^2$ when computing decryptions. Therefore, all we need to do to bypass the history check is ask for the decryptions of $C + n^2$, where $C$ is our encrypted password.

P(ai)^3

from Crypto.Util.number import getPrime, inverse
from secrets import randbelow

with open("flag.txt",'rb') as f:
    FLAG = f.read().decode()
    f.close()

MENU = r"""|
|  MENU:
|   [E]ncrypt
|   [D]ecrypt
|"""

class Paiaiai:
    """ My first Paillier implementation! So proud of it. ^ w ^ """

    def __init__(self):
        # Key generation
        p, q = [getPrime(512) for _ in range(2)]
        n = p * q
        # Public key
        self.pub = {
            'n'  : n,
            'gp' : pow(randbelow(n**2), p, n**2),
            'gq' : pow(randbelow(n**2), q, n**2)
        }
        # Private key
        self.priv = {
            'la' : (p - 1)*(q - 1),
            'mu' : inverse((pow(self.pub['gp'] * self.pub['gq'], (p-1)*(q-1), n**2) - 1) // n, n)
        }
        
    def encrypt(self, m: str):
        m_int = int.from_bytes(m.encode(), 'big')
        g = pow([self.pub['gp'],self.pub['gq']][randbelow(2)], m_int, self.pub['n']**2) 
        r = pow(randbelow(self.pub['n']), self.pub['n'], self.pub['n']**2)
        return (g * r) % self.pub['n']**2
    
    def decrypt(self, c: int):
        cl = (pow(c, self.priv['la'], self.pub['n']**2) - 1) // self.pub['n']
        return (cl * self.priv['mu']) % self.pub['n']

pai = Paiaiai()

while True:
    print(MENU)
    choice = input("|  >>> ").lower().strip()
    if choice == 'e':
        print("|\n|  ENCRYPT:")
        print("|   [F]lag")
        print("|   [M]essage")
        subchoice = input("|\n|  >>> ").lower().strip()
        if subchoice == 'f':
            enc_flag = pai.encrypt(FLAG)
            print("|\n|  FLAG:", enc_flag)
        elif subchoice == 'm':
            msg = input("|\n|  MSG: str\n|   > ")
            cip = pai.encrypt(msg)
            print("|\n|  CIP:", cip)
        elif choice == 'd':
            cip = input("|\n|  CIP: int\n|   > ")
            msg = pai.decrypt(int(cip))
            print("|\n|  MSG:", msg)

We’re given a service that implements what appears to be a Pallier cryptosystem, however the encrypt function is faulty and will use either $g_p$ or $g_q$ instead of the actual $g = g_p * g_q$ from which the private key is derived. We can arbitrarily encrypt and decrypt messages, or the flag, however we are given no information about the public key.

solution

Not having the public key makes this a little tricky, so we’ll start by trying to at least recover some of that.

The main function we need to look at for this challenge is the decrypt function, which is shown below:

    def decrypt(self, c: int):
        cl = (pow(c, self.priv['la'], self.pub['n']**2) - 1) // self.pub['n']
        return (cl * self.priv['mu']) % self.pub['n']

recovering $n$

We’ll start by observing what happens when we decrypt a message $a$, and it’s square, $a^{2}$

The first step is to raise each to the power of $\lambda$ (la), which we know is the Euler totient of $n$, therefore raising anything to the power of it will give a value of $1 \bmod n$. Here we take it mod $n^{2}$, so our result will be of the form $kn + 1$, where $k$ is some unknown value.

\[a^{\lambda} = k_1n + 1\\ (a^{2})^{\lambda} = a^{2\lambda} = k_2n + 1\\\]

Now, we know that $(a^{\lambda})^2 = a^{2\lambda}$, so we’ll square $k_1n+1$ and set it equal to $k_2n + 1$, and hopefully we can write $k_2$ in terms of $k_1$ or vice versa.

\[\begin{eqnarray} (k_1n+1)^2 &=& k_1^2n^2 + 2k_1n + 1 \\ k_1^2n^2 + 2k_1n + 1&=& k_2n + 1\\ k_1^2n + 2k_1 &=& k_2 \end{eqnarray}\]

Now we’ll finish the decryption and see what value is actually returned by subtracting 1, dividing by $n$ and multiplying by $\mu$ (mu):

\[\begin{eqnarray} cl_1 &=& \frac{k_1n + 1 - 1}{n} = k_1\\ r_1 &=& \mu * k_1 \bmod n\\ r_2 &=& \mu * k_2 \bmod n\\ \end{eqnarray}\]

But remember, we have an expression for $k_2$ in terms of $k_1$, so let’s write that out:

\[\begin{eqnarray} r_1 &=& \mu * k_1 \bmod n\\ r_2 &=& \mu * (k_1^2n + 2k_1) \bmod n \\ &=& \mu * 2k_1 \bmod n\\ \end{eqnarray}\]

Now we know that $r_1 * 2 = r_2$ if we decrypt $a$ and $a^2$. Since there is a possibility for $2 * r_1 > n$, we’ll use this to recover $n$. If we find the returned $r_2 < r_1$, we can recover $n$ by working out $2r_1 - r_2$

recovering $\mu$ (mu)

Now that we have recovered $n$, we’ll observe what happens when we decrypt $n$.

$n^{\lambda} \equiv 0 \bmod n^2$, as $\lambda$ will always be even, and so $n^{\lambda}$ will always be a multiple of $n^{2}$. Then $cl = \lfloor{\frac{-1}{n}}\rfloor = -1$, and therefore $r = -1 * \mu \bmod n = n - \mu$. We have now recovered $\mu$.

recovering $\lambda$ (la)

The last thing we would like to recover is $\lambda$, as this will allow us to factorize $n$, and also “decrypt” any message. We’ll do this by asking for the decryption of $n + 1$

To see why this works, we need to look at the binomial expansion of $(1 + n)^k \bmod n^2$

The binomial expansion is written as:

\[\sum^{k}_{x=0} {k\choose x}n^{x}\]

Notice that for $x > 1$, all terms will be cancelled out by the $\bmod n^2$, regardless of what ${k\choose x}$ is. Therefore, for any $k$, we only need to worry about $x = 0, 1$. This results in the sum:

\[\begin{eqnarray} (1 + n)^k &=& {k\choose 0} + {k\choose 1}n\\ &=& 1 + kn \end{eqnarray}\]

Therefore, $cl = \frac{1+ kn - 1}{n} = k$, and so $r = k * \mu$. We know $\mu$, and we know $k = \lambda$, so we have recovered $\lambda$. This also allows us to factorize $n$, although it is not required for flag recovery.

flag recovery

Our final step is to recover the flag with all the information we have. Let’s look at the encryption function:

    def encrypt(self, m: str):
        m_int = int.from_bytes(m.encode(), 'big')
        g = pow([self.pub['gp'],self.pub['gq']][randbelow(2)], m_int, self.pub['n']**2) 
        r = pow(randbelow(self.pub['n']), self.pub['n'], self.pub['n']**2)
        return (g * r) % self.pub['n']**2

and also briefly at the private key generation:

        self.priv = {
            'la' : (p - 1)*(q - 1),
            'mu' : inverse((pow(self.pub['gp'] * self.pub['gq'], (p-1)*(q-1), n**2) - 1) // n, n)
        }

Notice that instead of using $g_p * g_q$ as the generator $g$, which is what the private key is derived from, we are using only one of $g_p$ or $g_q$. To get something that is decryptable, we would ideally want a ciphertext which uses $gp * gq$ as $g$.

Luckily, it turns out we can make one ourselves! Notice that the $r$’s are pretty much arbitrary, as multiplying two $r$’s together will only give another potential $r$, and $g = {g_p^{flag}, g_q^{flag}}$. If we multiply these two together, we get $g = (g_p*g_q)^{flag}$, which is exactly what we need!

Therefore, all we need to do is ask for a couple flag ciphertexts, multiply combinations of two of them together, and attempt to decrypt it using standard Pallier decryption. This should hopefully give us a flag after a couple of tries.

Solve script below:

from pwn import *
import itertools
from Crypto.Util.number import *

s = remote("cha.hackpack.club", 10997)

def decrypt_msg(msg):
    s.sendlineafter(">>>", "D")
    s.sendlineafter(">", str(msg))
    s.recvuntil("MSG: ")
    return int(s.recvline())

def encrypt_flag():
    s.sendlineafter(">>>", "E")
    s.sendlineafter(">>>", "F")
    s.recvuntil("FLAG: ")
    return int(s.recvline())

i = 2
n = 0

# squaring message gives k, 2*k, subtract to get n
while not n:
    c1 = decrypt_msg(i)
    c2 = decrypt_msg(i**2)
    n = c1*2 - c2
    i += 1

print("n:", n)

# asking for decryption of n gives n - mu
mu = n - decrypt_msg(n)

# asking for decryption of n + 1 gives mu*la
la = decrypt_msg(n + 1) * pow(mu, -1, n) % n

flags = [encrypt_flag() for _ in range(5)]
for c1, c2 in itertools.combinations(flags, r=2): # hopefully we find one that uses gp, gq, then mu is correct
    c = c1 * c2
    pt = mu* ((pow(c, la, n**2) - 1)//n)
    flag = long_to_bytes(pt%n)
    if b"flag" in flag:
        print(flag)

Flag: flag{p41_41_41_1_d0nt_th1nk_th1s_1s_wh4t_p41ll13r_1nt3nd3d_3h}

angstromCTF 2022 - RSA-AES SUSCTF 2022