[Medium] Partial Tenacity

Partial Tenacity

5^th February 2024 / Document No. D24.102.30

Prepared By: aris

Challenge Author(s): aris

Difficulty: Medium

Classification: Official

Synopsis

• In this challenge, the player is called to factor an RSA modulus $n= p \cdot q$, given alternate base-10 digits of the primes $p,q$. The task is to implement a custom algorithm to retrieve the $i$-th redacted digit by checking if $n$ is equal to $p \cdot q$ modulo $10^i$.

Description

• You find yourself in a labyrinthine expanse where movement is restricted to forward paths only. Each step presents both opportunity and uncertainty, as the correct route remains shrouded in mystery. Your mission is clear: navigate the labyrinth and reach the elusive endpoint. However, there's a twist—you have just one chance to discern the correct path. Should you falter and choose incorrectly, you're cast back to the beginning, forced to restart your journey anew. As you embark on this daunting quest, the labyrinth unfolds before you, its twisting passages and concealed pathways presenting a formidable challenge. With each stride, you must weigh your options carefully, considering every angle and possibility. Yet, despite the daunting odds, there's a glimmer of hope amidst the uncertainty. Hidden throughout the labyrinth are cryptic clues and hints, waiting to be uncovered by the keen-eyed. These hints offer glimpses of the correct path, providing invaluable guidance to those who dare to seek them out. But beware, for time is of the essence, and every moment spent deliberating brings you closer to the brink of failure. With determination and wit as your allies, you must press onward, braving the twists and turns of the labyrinth, in pursuit of victory and escape from the labyrinth's confounding embrace. Are you tenacious enough for that?

Skills Required

• Basic Python source code analysis.
• Basic understanding of the RSA cryptosystem.
• Familiar with modular arithmetic.

Skills Learned

• Gain more experience with modular arithmetic. More specifically, if two numbers are equal, then they are equal modulo any number $m$.

Enumeration

In this challenge, we are provided with two files:

• source.py : This is the main script that encrypts the flag.
• output.txt : This is a text file which contains some values from the source script.

Analyzing the source code

Let us first take a look at the source script which is short and easy-to-follow.

from secret import FLAG
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP

class RSACipher:
    def __init__(self, bits):
        self.key = RSA.generate(bits)
        self.cipher = PKCS1_OAEP.new(self.key)
    
    def encrypt(self, m):
        return self.cipher.encrypt(m)

    def decrypt(self, c):
        return self.cipher.decrypt(c)

cipher = RSACipher(1024)

enc_flag = cipher.encrypt(FLAG)

with open('output.txt', 'w') as f:
    f.write(f'n = {cipher.key.n}\n')
    f.write(f'ct = {enc_flag.hex()}\n')
    f.write(f'p = {str(cipher.key.p)[::2]}\n')
    f.write(f'q = {str(cipher.key.q)[1::2]}')

There is a standard RSA implementation that pads the message with the PKCS#1 OAEP padding scheme. As in any RSA challenge, we are given the modulus $n$ and the encrypted flag $ct$​. Since the RSA key is generated by the PyCryptodome module, its value is 65537.

So far, assuming that RSA is secure, there is no vulnerability to exploit. However we are also provided with two values $p, q$ which look like they are related to the RSA primes $p,q$​. It might be interesting to examine them further.

Before moving on, let us write a function that loads the data from output.txt.

def load_data():
    with open('output.txt') as f:
        n = int(f.readline().split(' = ')[1])
        ct = bytes.fromhex(f.readline().split(' = ')[1])
        hint_p = int(f.readline().split(' = ')[1])
        hint_q = int(f.readline().split(' = ')[1])
		return n, ct, hint_p, hint_q

Solution

Finding the vulnerability

Generally, in most CTF challenges, if any portion of the private key is leaked then the solution will most likely be related to recovering the private key. This challenge verifies this observation.

The Base-10 version of the RSA primes $p,q$ is converted to a string. Then, the even-indexed characters of $p$ and the odd-indexed characters of $q$ are outputted. Let us see how this looks like through an example. Assume $p = 3068913241$ and $q = 2593854881$. Then, the output file would contain the numbers: $$ p = 36934\ q = 53581 $$ The task is be to recover all the base-10 digits of $p$ and $q$. It turns out that the leak is more than enough to make this task computationally feasible.

For simplicity, we will use two binary masks for each of $p, q$. This is useful to keep track of which digits are discarded for each prime. When there is an $1$-bit it means that the digit is leaked, if it is a $0$-bit then the digit is discarded.

For our example above, the corresponding masks would be: $$ p_{mask} = 1010101010\ q_{mask} = 0101010101 $$ Let us write a function that creates $p_{mask}$ and $q_{mask}$.

def create_masks(primelen):
    pmask = ''.join(['1' if i % 2 == 0 else '0' for i in range(primelen)])
    qmask = ''.join(['1' if i % 2 == 1 else '0' for i in range(primelen)])
		return pmask, qmask

Recall that the whole product $n = p \cdot q = 3068913241 \cdot 2593854881 = 7960315589533379321$ is known which is what makes this challenge solveable.

Working modulo powers of 10

Let $n = 7960315589533379321$. The task is to determine the two factors $p, q$ knowing the masks $p_{mask}, q_{mask}$. We know the last digit of $n$ is a $1$. Let us list all the numbers whose product ends with $1$​. $$ 1 \cdot 1 = 1\ 3 \cdot 7 = 21\ 7 \cdot 3 = 21\ 9 \cdot 9 = 81\ $$ Notice how we do not really mind about the $2$-digit products as we keep only the last digit which is a $1$. Therefore, as we mind only about the last digit, we can isolate the rest by reducing the number modulo $10$. This is the key observation to solve the challenge.

Right now, there are four candidates for the last digit of $p$ and $q$. If the size of $n$ is small, bruteforcing each of these candidates could be a feasible approach but in the context of the challenge, $n$ is $1024$ bits which rules out bruteforcing as the candidates increase exponentially for each digit.

Back to our example, due to $q_{mask}$, we know that the last digit of $q$ is $1$ so we can quickly determine that the last digit of $p$ would also be $1$. Moving on to the second-to-last digit of $n$ which we know is $2$ which can be produced by the following candidates: $$ 1 \cdot 2 = 2\ 2 \cdot 1 = 2\ 2 \cdot 6 = 12\ 3 \cdot 4 = 12\ 4 \cdot 3 = 12\ 4 \cdot 8 = 32\ 6 \cdot 2 = 12\ 6 \cdot 7 = 42\ 7 \cdot 6 = 42\ 8 \cdot 4 = 32\ 8 \cdot 9 = 72\ 9 \cdot 8 = 72\ $$ Again, we mind only about the last digit. Due to $p_{mask}$, we know the second-to-last digit of $p$ is $4$, therefore the candidates are reduced to: $$ 4 \cdot 3 = 12\ 4 \cdot 8 = 32\ $$ The problem is that we are not left with one choice which would require us testing each of these candidates. Again, for larger $n$ this would eventually be computationally infeasible.

So far, we know:

• The last two digits of $p$ are $41$
• The last digit of $q$ is $1$
• The last two digits of $n$ are $21$.
• The second-to-last digit of $q$ can be either $3$ or $8$.

We know we have found the correct candidate of $q$ if the product of the last two digits of $p$ and $q$ match the last two digits of $n$. This is equivalent to saying that the product of $p$ and $q$ modulo $10^2$ is equal to $n$ modulo $10^2$.

Let us compute the products $41 \cdot 31 = 1271$ and $41 \cdot 81 = 3321$.

For candidate $81$, we see that the product ends with $21$ so this should be the correct candidate. Finally, we have found out that: $$ p = 41\ q = 81 $$ We can apply this logic for each digit until we have recovered the whole numbers $p$ and $q$.

The algorithm can be summarized as follows:

1. For the digit at position $i$, we can extract the $i$-th character of $p_{mask}$ and $q_{mask}$.
2. If $p_{mask}[i] = 1$, then we know the $i$-th digit of $p$ so extract it.
   1. Bruteforce all 10 possible candidates of $q$.
   2. Check whether $n \pmod {10^i} == (p \cdot q) \pmod {10^i}$.
   3. The correct candidate for $q[i]$ will satisfy this relation.
3. Else, we know the $i$-th digit of $q$ so extract it and repeat the same steps until all the bits of $p, q$​ are recovered.

Let us write a function that brute forces the $i$-th digit of $p$ or $q$ and checks whether $n \pmod {10^i} == p \cdot q \pmod {10^i}$ holds.

def bruteforce_digit(i, n, known_prime, prime_to_check, hint_prime):
    msk = 10**(i+1)
    known_prime = 10**i * (hint_prime % 10) + known_prime
    for d in range(10):
        test_prime = 10**i * d + prime_to_check
        if n % msk == known_prime * test_prime % msk:
            updated_prime_to_check = test_prime			    # correct candidate! update the unknown prime
            updated_hint_prime = hint_prime // 10			  # move on to the next digit
            return known_prime, updated_prime_to_check, updated_hint_prime

The variable known_prime corresponds to the prime whose $i$-th character of the mask is $1$, or in other words, is known. Then, prime_to_check will be set to the other one. Similarly with hint_prime.

Exploitation

Let us write a function that iterates over $p_{mask}$ and $q_{mask}$ and checks if the current character is $1$ or $0$. Then it calls bruteforce_digit with the corresponding arguments.

def factor(n, p, q, hp, hq, pmask, qmask):
    for i in range(prime_len):
        if pmask[-(i+1)] == '1':
            p, q, hp = bruteforce_digit(i, n, p, q, hp)
        else:
            q, p, hq = bruteforce_digit(i, n, q, p, hq)
            
    assert n == p * q

    return p, q

Having factored $n$​, we can decrypt the flag using RSA along with the PKCS#1 OAEP padding scheme.

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP

def decrypt(p, q, n, ct):
		e = 0x10001
    d = pow(e, -1, (p-1)*(q-1))
    key = RSA.construct((n, e, d))
    flag = PKCS1_OAEP.new(key).decrypt(ct)
    return flag

Getting the flag

A final summary of all that was said above:

1. Notice that we know alternate digits of the decimal representation of $p$ and $q$​.
2. Create two masks consisting of $0,1$ and show which digits of the two primes are known and which are redacted.
3. Realize that knowing the $i$-th digit of $p$ is enough to recover the $i$-th digit of $q$ by verifying whether $n$ is equal to $p \cdot q$ modulo $10^i$.
4. Write a custom algorithm that recovers the primes' digits one by one.
5. Having factored $n$, decrypt the flag using RSA along with the PKCS#1 OAEP padding scheme.

This recap can be represented by code with the pwn() function:

from math import sqrt

def pwn():
    n, ct, hint_p, hint_q = load_data()
    prime_len = len(str(int(sqrt(n))))
    pmask, qmask = create_masks(prime_len)
    p, q = factor(n, 0, 0, hint_p, hint_q, pmask, qmask)
    flag = decrypt(p, q, n, ct)
    print(flag)

if __name__ == '__main__':
    pwn()