pycryptojail-writeup.md

jailCTF 2025 writeup: pycryptojail

I enjoyed this crypto-based Python jail challenge at jailCTF 2025. I even found a partially unintended solution! Here's my writeup.

0. The challenge

#!/usr/local/bin/python3
from Crypto.Util.number import bytes_to_long, long_to_bytes, getPrime
import os
import subprocess

def rsagen():
    p, q = getPrime(768), getPrime(768)
    n = p * q
    e = 0x10001
    d = pow(e, -1, (p - 1) * (q - 1))
    return (n, e)

def rsaenc(pk, msg):
    n, e = pk
    m = bytes_to_long(msg[:192])
    c = pow(m, e, n)
    return long_to_bytes(c)

if __name__ == '__main__':
    secret = os.urandom(8).hex()
    flag = open('flag.txt', 'r').read().strip()

    pk = rsagen()
    while True:
        code = input('>>> ')
        if any(c not in '0123456789abcdefghijklmnopqrstuvwxyz_+-*/ ' for c in code):
            print("You can't do that!")
            continue

        template = f'flag_you_will_never_guess_this_{secret} = {flag!r}\n\nprint({code})'
        output = subprocess.run(
            ['python3', '-c', template],
            stdout=subprocess.PIPE, stderr=subprocess.STDOUT,
        ).stdout

        print(rsaenc(pk, output).hex())

The server is a "signing oracle", where we can submit a Python expression using a limited alphabet and see a signed RSA response.

Our solution will consist of three steps:

1. Finding the RSA modulus n with crypto
2. Revealing secret with a lovely Python trick
3. Reading the flag

The intended solution for step 3 involved an RSA attack known as the Franklin–Reiter related-message attack. But I found an alternative method where I intentionally cause SyntaxWarnings to extract the flag. I'll explain both methods in this writeup.

0.1 What does the server do?

When we connect to the server and send something like

>>> 1+1

it evaluates the following Python program:

flag_you_will_never_guess_this_1234abcd1234abcd = "jail{blah_blah_blah}"

print(1+1)

It gathers the output (here output = b"2\n") and sends back a huge number $\text{rsaenc}(n, e, \text{output})$.

Two things to note that we'll use to our advantage:

• The output is trimmed to the first 192 bytes.
• STDERR is piped to STDOUT when capturing output, so it's included.

1. Finding n

Let's call $M_i$ the first 192 bytes of the output of our $i$-th submission, turned into a big number (by bytes_to_long, which interprets the bytes as base-256). We choose each $M_i$, and we get back

$$C_i = \text{rsaenc}(n, e, M_i) = M_i^e \bmod n$$

where $e = 65537$, but we don't know $n$. How do we find $n$?

We can apply a common trick in crypto CTF challenges. By the definition of modulo, we know that each difference $M_i ^ e - C_i$ is some multiple of $n$, let's say $k_i n$. Now we can send a bunch of $M_i$ and take the gcd of all these differences:

$$\gcd(M_1 ^ e - C_1, M_2 ^ e - C_2, \dots) = \gcd(k_1 n, k_2 n, \dots) = \gcd(k_1, k_2, \dots) \cdot n$$

If we pick our $M_i$ randomly, then the $k_i$ will also be basically random; eventually we expect their gcd to be 1. And then what's left in the right-hand side of this equation is $n$.

2. Revealing secret

Now that we have n, we can leak message equality.

Suppose that we could get the server to tell us $\text{rsaenc}(n, e, f)$ where $f$ is the first byte of the flag. We can't quite decrypt the response, but there are only 95 printable ASCII characters $f$ could be. Thus, we can encrypt 95 "guesses" at the first byte of the flag, and see which encrypted result matches the response from the server.

In the real challenge, we can do no such thing. We don't know the variable name the flag is stored in, and even if we did, we don't have square brackets to extract that first byte with.

Here we come to the essential idea in this challenge: we can make a guess at secret and let Python's NameError tell us if we are close enough.

When we ask for a variable that doesn't exist, Python uses Levenshtein distance to decide if it should suggest a close alternative:

❯ uv run --python 3.10 python
Python 3.10.12 (main, Jul 26 2023, 13:20:36) [Clang 16.0.3 ] on linux
Type "help", "copyright", "credits" or "license" for more information.

>>> flag_you_will_never_guess_this_1234abcd1234abcd = 'flag{}'

>>> #
>>> # If more than 1/3 of the chars differ, there's no hint:
>>> #
>>> flag_you_will_never_guess_thisxxxxxxxxxxxxxxxxx  
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
NameError: name 'flag_you_will_never_guess_thisxxxxxxxxxxxxxxxxx' is not defined

>>> #
>>> # If less than 1/3 of the chars differ, we get a hint!
>>> #
>>> flag_you_will_never_guess_this_xxxxxxxxxxxxxxxx
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
NameError: name 'flag_you_will_never_guess_this_xxxxxxxxxxxxxxxx' is not defined.
  Did you mean: 'flag_you_will_never_guess_this_1234abcd1234abcd'?

Thus, we can submit the following guesses to the oracle:

flag_you_will_never_guess_thisx0xxxxxxxxxxxxxxx
flag_you_will_never_guess_thisx1xxxxxxxxxxxxxxx
...
flag_you_will_never_guess_thisxfxxxxxxxxxxxxxxx

Note the _ that has turned into an x.

For all but one of these, we can predict the no-hint NameError we expect to get if our guess is wrong. But for one of them, the Levenshtein distance will be smaller, and we'll get the "Did you mean:" hint, causing the encrypted response to differ.

That means our guess was correct, and we can lock in that character of the variable name and continue. To keep the Levenshtein distance "balanced", right on the edge of getting a hint, we need to replace one more character with x — this time, the s in this:

flag_you_will_never_guess_thixx10xxxxxxxxxxxxxx
flag_you_will_never_guess_thixx11xxxxxxxxxxxxxx
flag_you_will_never_guess_thixx12xxxxxxxxxxxxxx
...

We continue this process to exfiltrate all of secret.

3. Reading the flag

Okay, now we know the flag is contained in, say, flag_you_will_never_guess_this_1234abcd1234abcd, and we can ask the server for it:

>>> flag_you_will_never_guess_this_1234abcd1234abcd

...but of course, we get an encrypted response. How do we decrypt it?

3.1. Intended solution: Franklin–Reiter

In proper usage of RSA, messages should always be padded with random bytes so that an attacker cannot use a related message attack to break the cryptosystem. In this challenge, that's exactly how we'll leak the flag.

Remember that the messages are turned into numbers by bytes_to_long, which interprets a string as a base-256 number. So, b"flag{}" is represented by a number like

  ord('f') * 256**5
+ ord('l') * 256**4
+ ord('a') * 256**3
+ ord('g') * 256**2
+ ord('{') * 256
+ ord('}')

Let's call this number $F$.

What happens to this number when we add bytes to the end of this string? Well, think about what happens in base 10: when we write a 6 at the end of 345 to make 3456, it's like we're applying $x \mapsto 10x + 6$ to the number. It works just the same for our strings: adding a newline (ASCII 10) to the flag takes us from $F$ to $256F + 10$.

When we submit just flag_you_will_never_guess_this_1234abcd1234abcd to the server, the Python code prints the flag, followed by a newline. So our first plaintext-ciphertext pair is

$$M_1 = 256F + 10$$ $$C_1 = (256F + 10)^e \bmod n$$

Now, we can obtain a "related" message: we submit flag_you_will_never_guess_this_1234abcd1234abcd+__name__. The Python code prints the flag, followed by b"__main__", followed by a newline. So we get

$$M_2 = 256^9F + b$$ $$C_2 = (256^9F + b)^e \bmod n$$

where $b$ is the number bytes_to_long(b"__main__\n").

The trick is now that we can consider the following polynomials in $\mathbb{Z}_n$:

$$g_1(x) = (256x+10)^e - C_1 \qquad g_2(x) = (256^9x+b)^e - C_2$$

where $x$ is a symbolic variable.

From our equations for $C_1$ and $C_2$, we know that these polynomials have a common root, namely $F$:

$$g_1(F) = (256F+10)^e - C_1 = C_1 - C_1 = 0$$ $$g_2(F) = (256^9F+b)^e - C_2 = C_2 - C_2 = 0$$

So we can use SageMath to compute the polynomial $\gcd(g_1,g_2)$ and factor the result. Taking the GCD is easier than factoring, and the resulting polynomial will be far smaller than either input — small enough to factor. But because $F$ is a root of both $g_1$ and $g_2$, they both contain a factor $(x - F)$. So we can expect the same of their GCD! Extracting this coefficient $F$ and calling long_to_bytes on it gets us the flag.

3.2. Unintended solution: SyntaxWarning

Just like in step 2, we can use the 192-byte limit and piping of STDERR to our advantage.

Let's cause the Python code to produce 191 bytes of known junk data, followed by the flag. To produce this known junk data, we can use SyntaxWarnings!

If we ask the server for

>>> 1and 1and 0o1and __name__*5+flag_you_will_never_etc

it will respond by encrypting:

b'<string>:3: SyntaxWarning: invalid decimal literal\n<string>:3: SyntaxWarning: invalid decimal literal\n<string>:3: SyntaxWarning: invalid octal literal\n__main____main____main____main____main__j'

(Our literals are "invalid" because Python would prefer we write 1 and over 1and.)

The very last byte of this output is the first byte of the flag. So we can make 95 "guesses" for this single byte and compare them to the encrypted response from the server. Only our guess for j will match it.

Then we continue, this time with one fewer byte of junk data, so there's room for two characters of the flag. We send:

>>> 1and 1and __name__*11+flag_you_will_never_etc

And the server responds by encrypting:

b'<string>:3: SyntaxWarning: invalid decimal literal\n<string>:3: SyntaxWarning: invalid decimal literal\n__main____main____main____main____main____main____main____main____main____main____main__ja'

and we can guess the next byte of the flag. Repeat until we have the whole thing.

If we only had __name__ at our disposal, we'd be forced to guess 8 bytes of the flag at a time, but by combining it with SyntaxWarnings of various known lengths, we can make junk of any length we desire. Nifty!

4. Takeaway

I couldn't summarize this writeup better than the flag itself:

jail{pyth0n_tr4c3b4ck_is_a_l3v3n5ht31n_d15t4nc3_0r4cle}

Thanks to Lyndon for this creative challenge, and to my teammate ovs for realizing we could use NameError to leak secret.