TJCTF | Crypto - Pseudoleon

This was a rather fun CTF event which I played with the team CyberHero. While I didn’t get a chance to try my hands at all the categories, the cryptography challenges were all rather enjoyable. As the challenges were beginner-friendly, I’ve made the write-up be as beginner-friendly as I could. I’ve taken the time to outline my solution and thought process for two of the challenges, those being:

e
keysmith

crypto/e

Author: stosp

64 solves / 60 points

smol e

Note: Below you’ll find a guided solution. If interested just in the solve script, click here

When we first open up our challenge, we are greeted with two files: gen.sage and output.txt. It’s the former that interests us a lot more, so let’s take a look:

from Crypto.Util.number import bytes_to_long

p = random_prime(2 ^ 650)
q = random_prime(2 ^ 650)
N = p*q
e = 5
flag = open("flag.txt", "rb").read().strip()
m = bytes_to_long(b'the challenges flag is ' + flag)
c = m ^ e % N
print("N: ", N)
print("C: ", c)
print("e: ", e)

Obviously, we’re dealing with RSA here. The primes seem safely generated and the encryption’s standard - we can find our public key and the ciphertext in output.txt. So our eyes turn to the central section:

e = 5
flag = open("flag.txt", "rb").read().strip()
m = bytes_to_long(b'the challenges flag is ' + flag)

Immediately we notice that $e = 5$. This should tell us that whatever attack we plan on mounting likely relies on a small exponent.

Next, we notice that our message (i.e. plaintext) is a combination of a known string and the (unknown) flag. More precisely, it means we have a partially known plaintext.

Enter Coppersmith

Let’s take a short detour.

In the mid-to-late 90s, a very clever man named Don Coppersmith, building on the ideas of other clever people, came up with a method for solving univariate modular equations. That is, equations with one variable modulo some $N$. He’d present a very efficient method for finding small roots (i.e. solutions) of such polynomials. In time, this would be generalized for multivariate polynomials as well. The details of the how are beyond the scope of this write-up (but can be found here).

Though that begs the question: what’s small? For a polynomial of degree $k$, we call small roots of the polynomial those less than $N^{1/k}$.

Now, what does this have to do with us? Well, let’s look at our message:

b'the challenges flag is ' + flag

Obviously, we know the higher bits of the plaintext ($kBits$) but don’t know the flag ($x$). If we assume that the flag is $h$ bits large, we can rewrite our message as:

\[kBits * 2^{h} + x = m\]

Which tells us that the ciphertext is:

\[c \equiv m^e \equiv (kBits * 2^{h} + x)^e \ \ \ \ (mod\ N)\]

And since we know that $e=5$ we can write it as:

\[(kBits * 2^{h} + x)^5 - c \equiv 0 \ \ \ \ (mod\ N)\]

And what we get, after expanding it, is a:

univariate polynomial (it has only one unknown, $x$),
that is modulo $N$,
with a small degree $k = e = 5$,
and a relatively small root.

So we can apply Coppersmith! Luckily for us, SageMath already has Coppersmith’s method implemented for us in the form of the small_roots function.

Solve script (crypto/e)

To make our lives easier, we recall that the flag format for the CTF is tjctf{ so we append that to our known string. Additionally, as standard calls to small_roots() don’t result in any outputs, we increase the epsilon value (which defaults to 1/8). We can roughly understand it as increasing the bounds of the algorithm. The lower the epsilon, the larger the bounds.

from sage.all import *

N = 8530080367614029604 ...
C = 2987003325076547237 ... 
e = 5
Z = Zmod(N)
P.<x> = PolynomialRing(Z)

msg = b'the challenges flag is tjctf{'
known = Z(int(msg.hex(), 16)) # Bytes to decimal

for unknown_bytes in range(2,33): # x < N^(1/5) ~= 32 bytes
    m = known * 2^(8*unknown_bytes)
    f = (m + x)^e - C
    
    roots = f.small_roots(epsilon=1/12)
    if roots != []:
        print(roots) #
        break

When converting the number to bytes, we get coppersword2}, resulting in the full message being the challenges flag is tjctf{coppersword2}.

crypto/keysmith

Author: stosp

30 solves / 128 points

I lost my key… can you find it?

nc tjc.tf 31103

Note: Below you’ll find a guided solution. If interested in just the solve script, click here

Downloading the challenge, we stumble upon server.py - let’s see what we’ve got:

#!/usr/local/bin/python3.10 -u
from Crypto.Util.number import getPrime
flag = open("flag.txt", "r").read()

po = getPrime(512)
qo = getPrime(512)
no = po * qo
eo = 65537

msg = 762408622718930247757588326597223097891551978575999925580833
s = pow(msg,eo,no)

print(msg,"\n",s)

try:
    p = int(input("P:"))
    q = int(input("Q:"))
    e = int(input("E:"))
except:
    print("Sorry! That's incorrect!")
    exit(0)

n = p * q
d = pow(e, -1, (p-1)*(q-1))
enc = pow(msg, e, n)
dec = pow(s, d, n)
if enc == s and dec == msg:
    print(flag)
else:
    print("Not my keys :(")

Interesting. So we’re given $m$ and $s$ (and technically $e_o$), and nothing else. Let’s put this into some equations:

\[n_o = p_o * q_o\] \[s \equiv m^{e_o} \quad (mod\ n_o)\]

So our $s$ is essentially an encrypted message. And for our chosen input of $e$, $p$ and $q$ we have:

\[n = p * q\] \[d \equiv e^{-1} \quad (mod\ n)\] \[enc \equiv m^e \quad (mod\ n),\ \text{where $enc$ should be the same as $s$}\] \[dec \equiv s^d \quad (mod\ n),\ \text{where $dec$ should be the same as $m$}\]

Right, that’s a few expressions. Let’s put some words behind them.

Effectively, we’re looking to input parameters $n$ and $e$ such that $m^e$ equals to a specific number $s$. If our numbers $p$ and $q$ are both prime, then the second test regarding $dec$ will always pass.

Obviously, one way to get the flag would be to send the private parameters back. However, seeing as the target $n_o$ is rather large, factoring it isn’t really an option. So what now? Well, let’s think back to what we just said: we’re looking to find an $e$ such that $m^e$ equals to $s$. This problem, when stated over a numbers modulo $n$, is called the discrete logarithm problem (or DLP for short).

The DLP is the ‘hard’ problem behind cryptosystems such as Diffie-Hellman. It’s proven to be rather difficult in the general case, however there are some special cases when it’s far easier. Notably, for a prime $p$, if $p-1$ is smooth (meaning it has many prime factors), it’s possible to solve the DLP in polynomial time. But is us being forced to send two primes, resulting in a composite DLP, going to be an issue? Of course not! Thanks to the Chinese Remainder Theorem, we can solve the DLP modulo each prime factor using the efficient algorithm.

The algorithm in question, called Pohlig–Hellman, is luckily implemented in SageMath through the discrete_logarithm function. All that’s left now is to code-up the rest.

Generating $p-1$ smooth numbers

While for solving our special case of the DLP we have an efficient algorithm, how would we go about generating these ‘smooth’ numbers? The method we’ll employ is surprisingly simple: multiply a lot of small numbers, check if the incremented version of the number is prime and, if so, return that number. Here’s one way to achieve just that in SageMath:

from sage.all import *

def smooth_prime(r=80): 
    not_found = True 
    while not_found: 
        k = 2 
        for _ in range(r): 
            k *= random_prime(1000, 10000) * random_prime(10000, 1000000) 
        k += 1 
        if is_prime(k) and len(factor(k-1)) > 20: 
            not_found = False 
            return k 

Here our function’s parameter r corresponds to a rough estimate of how many prime multiplications we’d like. While not ideal, it gets the job done - a better method would be to go about multiplying random numbers until a certain bit-length is reached. But we don’t have to worry about a key-size here, as long as our public key $n$ is larger than $s$, we’re set.

Solve script (crypto/keysmith)

To simplify things, we only bother with ensuring $p-1$ is smooth. For $q$ we can send any small prime factor. It should be noted that we might need multiple attempts with this script; sometimes, we’ll get such an $s$ that finding a modular inverse is unlikely (or impossible).

from sage.all import *

def smooth_prime(r=80): 
    not_found = True 
    while not_found: 
        k = 2 
        for _ in range(r): 
            k *= random_prime(1000, 10000) * random_prime(10000, 1000000) 
        k += 1 
        if is_prime(k) and len(factor(k-1)) > 20: 
            not_found = False 
            return k 
                         
# === SETUP
from pwn import *
server = "tjc.tf"
port = 31103
io = remote(server, port)

# === INIT
msg = int(io.recvline())
s = int(io.recvline())

eo = 65537

# === PAYLOAD
successful = False
while not successful:
    p = int(smooth_prime(55))
    q = 3
    n = p*q
    print("Attempting...")
    Z = Zmod(n)
    try:
        e = discrete_log(Z(s), Z(msg))
        e = int(e)
        e = e % ((p-1)*(q-1))
        d = pow(e, -1, (p-1)*(q-1))
    except ValueError:
        continue
    except ZeroDivisionError:
        continue
    
    successful = True

# === CHECKS
enc = pow(msg, e, n)
dec = pow(s, d, n)
assert enc == s
assert dec == msg

# === ATTACK
p_ = str(p).encode()
print(p_)
io.sendline(p_)

q_ = str(q).encode()
print(q_)
io.sendline(q_)

e_ = str(e).encode()
print(e_)
io.sendline(e_)

io.interactive() # tjctf{lock-smith_289378972359}

crypto/e

Enter Coppersmith

Solve script (crypto/e)

crypto/keysmith

Generating \(p-1\) smooth numbers

Solve script (crypto/keysmith)