 # KITCTFCTF 2022 - Prime Guesser 1 and 2

12.12.2022 by goreil

Prime Guesser 1 and Prime Guesser 2 are two cryptography challenges where a user guess the prime factors of an encrypted number. To help the user had acess to an oracle that tells whether a ciphertext is 0 or not. Prime Guesser 1 had access to an extra Oracle but the exploit was basically the same. The encryption scheme seemed to be based on Polynomials.

While the challenges look intimidating at the beginning, pulling out polynomial multiplication and addition, there has been a major oversight with the encryption scheme, allowing us to easily solve both challenges without really needing to understand what the encryption scheme actually does.

## Challenge overview

The Challenge server employed a custom polynomial based encryption protocol. The server will send you an encrypted number between 11 and 200 and the goal is to send back a set of prime-factors of the encrypted number.

Between each encrypted number you can query an oracle any times you want that returns True or False whether a ciphertext corresponds to the plaintext 0. In PrimeGuesser 1 you also have access to an oracle that will encrypt the number 1 - 20.

You need to send back the correct factors 100 times to get the flag. ### Example Encryption output

• Plaintext: 117 (not send to you)
• Ciphertext: (2 arrays of 64 numbers)

The interesting part of the challenge is the encrypt function. It just adds a scaled plaintext on top of an array of some random numbers. Using the oracle, we can easily recover the plaintext from any ciphertext. While the 165 lines can look very intimidating, only a few were actually relevant to solve the challenge.

Key differences in PrimeGuesser 2 were:

• $n$, $q$ and $t$ were the same on the server as in the source
• The oracle didn’t have choice 0

## Vulnerability

The encrypt function just added the plaintext on top of some random junk. If you add a decrement the ciphertext with a certain $\text{delta}$ you the plaintext also decrements by one. Using the oracle this is enough to calculate the original plaintext.

While the challenge uses polynomial multiplication and polynomial addition, for us only polynomial addition is relevant, which just adds each element of one array to each element of the other array:

### Example:

Knowing that $\text{size}, q, t, poly_mod$ are known global variables this is essentially:

function encrypt(pk, pt):

• $ct_0 = (pk_0 \cdot u) + e + (scaled_plaintext)$ (using polynomial addition and multiplication)
• return ($ct_0$, $ct_1$)

where

• $pk$ is the private key
• $pt$ is the plaintext
• $ct$ is the ciphertext, consiting of two arrays $ct_0$ and $ct_1$

Since $\text{scaled_plaintext}$ only gets added at the end and mostly consists of zeros, we can easily modify a ciphertext to return a different value:

### Example

We get the following ciphertext:

which corresponds to $pt = 117$ If we modify only the first number of $c_0$ like this: We reduced the $pt$ by one. This is also something we can repeat infinitely. To solve the challenge we then only need to substract 1 for the plaintext each time, until the oracle returns true. The code might look like this:

### Getting q and t

Interestingly with our approach Prime Guesser 2 is already solved, since $q$ and $t$ known.

To get $q$ and $t$ in Prime Guesser 1 we follwed the Guesser part and just eyeballed the values:

1. We just assume that $q$ and $t$ are powers of 2 since they are in the local challenge script.
2. We can guess $q$ with the first ciphertext, since it is probably the next power of 2 that is bigger than all values in the ciphertext.
3. We use the encrypt oracle to encrypt the number 1. We then iterate through possible stepsizes until we get a correct one with which the plaintext is 0.

Result: $\frac{q}{t} = 0\text{x}100000$

## Exploit

Our exploits follows the vulnerability description. Since we need to find 100 numbers and each number is randomly split between 11 and 200, we should need approx. $100 \cdot \frac{201 - 11}{2} = 9500$ requests to the oracle. In practice this meant that the exploit takes around 10 minutes to run.

## Summary

This writeup showcases how you don’t have to understand a whole encryption scheme to exploit it. We are able to modify corresponding plaintext to a ciphertext to decrement it in steps of one. With the Oracle that told us whether a ciphertext corresponst to zero, the exploitation was quite easy.