saas - Smiley-CTF 2025 Write-up | My CTF Write-up Collection

saas - Smiley-CTF 2025 Write-up

Banner

Challenge: saas Category: crypto Points: 50

Introduction

Hey everyone! Just got done with the ‘saas’ challenge from Smiley-CTF and wanted to write down my thought process. We were given three files to start: a (docker-compose.yaml), a (Dockerfile), and the python script, (chall.py). The name “saas” stands for “squares as a service,” which was a pretty big hint. It’s a crypto challenge involving what looked like a standard RSA setup, but with a special oracle that would calculate square roots for us. The goal was to somehow use this oracle to break the RSA and sign a message.

First Look: Analyzing the Code

First things first, I wanted to see how the service behaved. I connected to it using netcat. I tried sending some random strings just to see what would happen.

root@myusername:~/project-holoswap/another/rorecovery12# nc smiley.cat 34987
>>> lsd
m = 33606824905552062707599129171169352809274710821353519093918195802419317324249488644479801849120945801334418605684180383333628026493303750389863565976567470898917328786801283448523963829292024555920526886197719469894673339542264521566319861722717229758104839637658843151201186136720063241677243736545312886957
>>> add
Traceback (most recent call last):
  File "/app/run", line 25, in <module>
    s = int(input(">>> ")) % n
        ~~~^^^^^^^^^^^^^^^
ValueError: invalid literal for int() with base 10: 'add'
da

Okay, so sending a non-integer breaks the first loop and moves on to the signing part of the challenge. This is our way to advance once we have what we need. The server expects integer inputs for the oracle part.

With that understood, I looked at the chall.py file. Here’s the important stuff I noticed:

RSA Key Gen: It generates two 512-bit primes, p and q. A specific condition is that p % 4 == 3 and q % 4 == 3. This is a known property that makes calculating modular square roots easier.
The Oracle f(x): The server provides a function that takes our integer input l, and calculates f(l). Looking at the math, it’s calculating one of the four possible square roots of l modulo n. It does this by finding the roots modulo p and q and then combining them with the Chinese Remainder Theorem (CRT). The choice([-1, 1]) part is what makes the output random.
The Goal: After we break the loop, it gives us a random message m and asks us to sign it. To sign it, we need the private key d, which means we need to factor n.

The main idea for the attack seemed clear: if we can get two different square roots y1 and y2 for the same number x, then we know:

$y_1^2 \equiv x \pmod{n}$
$y_2^2 \equiv x \pmod{n}$

This means $y_1^2 - y_2^2 \equiv 0 \pmod{n}$, which simplifies to $(y_1 - y_2)(y_1 + y_2) \equiv 0 \pmod{n}$. This is huge! 🤩 It means n divides (y1 - y2)(y1 + y2). If we’re not super unlucky, we can find one of the prime factors by calculating gcd(y1 - y2, n).

Trial and Error:

This challenge took a few tries to get right. My journey was a bit of a rollercoaster. 😅

Attempt #1: The Naive Script

My first script was super simple. It just sent the number 4 twice, got two roots y1 and y2, calculated p = gcd(y1 - y2, n), and tried to sign the message. It failed immediately with “Wrong signature!”.

What went wrong? I realized the server could have given me the same root twice (y1 == y2) or two roots that were just negatives of each other (y1 == -y2 mod n). In both of those cases, the gcd trick fails. My script wasn’t robust enough to handle this randomness.

Attempt #2: The Over-Thinking Phase

I made the script more robust to handle the failure cases from the first attempt. But then I saw something really weird in my logs. My script would find factors p and q, but p % 4 and q % 4 were both 1. This directly contradicted the source code that said they should be 3!

What went wrong? This contradiction made me go down a deep rabbit hole. I came up with this complex theory that the factors I found were actually composite and that n was a product of four primes, not two. This led me to add sympy.factorint() to my code to try and factor them again. Of course, the script just hung forever, because it was trying to factor a giant 1024-bit number, which is impossible.

# This was the bad idea that caused the script to hang forever
p_factors = factorint(p_composite)
q_factors = factorint(q_composite)

Attempt #3: The `n=0` Crash

After realizing the “composite factor” idea was a dead end, I simplified the script. But then it crashed with a ZeroDivisionError. The logs showed Calculated n = 0.

What went wrong? This happened because the server, for some reason, sent back the simple integer roots 2 and -2. When my script tried to calculate n = gcd(2*2 - 4, (-2)*(-2) - 4), it was doing gcd(0, 0), which is 0. My script couldn’t handle getting these trivial responses from the server.

The Final Approach & The Working Exploit

After all those failures, I finally understood what was needed: a script that was robust against all the server’s weird behaviors.

The final strategy was:

Wrap the connection and n calculation in a loop. Keep trying until the server gives back proper large modular roots so we can calculate a valid, large n.
Once n is found, get two square roots y1 and y2.
Loop until y1 and y2 are different and not just negatives of each other.
Use gcd(abs(y1 - y2), n) to find a prime factor p. Crucially, trust this factor. Don’t try to factor it again.
Calculate q = n // p, then phi, then d.
Sign m and get the flag.

Here’s the final script that put all the pieces together and worked!

#!/usr/bin/env python3
from pwn import *
from math import gcd

PORT = 39807
HOST = "smiley.cat"
x = 4 # A small perfect square is efficient.
MIN_N_BIT_LENGTH = 1000 

r = None
n = 0

while n.bit_length() < MIN_N_BIT_LENGTH:
    if r:
        r.close()
    
    log.info(f"connecting to {HOST}:{PORT}...")
    try:
        r = remote(HOST, PORT)
    except PwnlibException:
        log.failure(f"uh oh, can't connect to port {PORT}. maybe it changed?")
        exit(1)

    log.info("trying to get n from the server...")
    try:
        r.sendlineafter(b">>> ", str(x).encode())
        y1_str = r.recvline().strip()
        y1 = int(y1_str)

        r.sendlineafter(b">>> ", str(x).encode())
        y2_str = r.recvline().strip()
        y2 = int(y2_str)
    except (ValueError, EOFError) as e:
        log.warning(f"server gave weird roots ({e}), trying again.")
        n = 0 # Reset n to ensure loop continues
        continue


    val1 = y1*y1 - x
    val2 = y2*y2 - x

    if val1 == 0 or val2 == 0:
        log.warning("got trivial roots, can't find n. retrying...")
        n = 0
        continue
    
    n = gcd(val1, val2)

    if n.bit_length() < MIN_N_BIT_LENGTH:
        log.warning(f"n is too small ({n.bit_length()} bits). trying again.")
        n = 0 # Reset n to ensure the loop continues

log.success(f"cool, got n = {n}")


while y1 == y2 or (y1 + y2) % n == 0:
    log.warning("same roots again, asking for new ones...")
    r.sendlineafter(b">>> ", str(x).encode())
    y1 = int(r.recvline().strip())
    
    r.sendlineafter(b">>> ", str(x).encode())
    y2 = int(r.recvline().strip())
log.success("nice, got two different roots.")

p = gcd(abs(y1 - y2), n)

if p == 1 or p == n:
    log.info("gcd was trivial, trying the other pair...")
    p = gcd(y1 + y2, n)
    if p == 1 or p == n:
        log.critical("oof, can't factor n. something's wrong.")
        r.close()
        exit(1)

q = n // p
log.success("nice, factored n.")
log.info(f"p is {p}")
log.info(f"q is {q}")

phi = (p - 1) * (q - 1)
e = 0x10001
d = pow(e, -1, phi)
log.info("got d.")

log.info("okay, breaking the loop for m.")
r.sendlineafter(b">>> ", b"break")
m_line = r.recvline().decode().strip()
m = int(m_line.split(" = ")[1])
log.info(f"got m = {m}")

s = pow(m, d, n)
log.info("signing m and sending it.")
r.sendlineafter(b">>> ", str(s).encode())

flag = r.recvall(timeout=2).decode()
log.success(f"flag maybe? {flag}")

r.close()

Running this script finally gave the correct output and the flag!

[*] connecting to smiley.cat:39807...
[+] Opening connection to smiley.cat on port 39807: Done
[*] trying to get n from the server...
[+] cool, got n = 110116769454860084964964147432363060206020865054866362195033207272972778017050819554703928090719593110468946716946060076413371569988943910838557026874357084814924508409542058123581418561375173142103763419011870903204212752206184413782726508229333296118212092362018291999372875853383052049820129316991822579573
[+] nice, got two different roots.
[+] nice, factored n.
[*] p is 9252982657489086787230540697344791453722952924129706467069426224627343249518064775025943988499061596688575070440589731488465240297129880741803949224292639
[*] q is 11900678249486923303336113996663926362059364607293849537370813849613456250184530640703244682312855723093569507304197567152811628854538432006329231717404907
[*] got d.
[*] okay, breaking the loop for m.
[*] got m = 64668793919614993349415340262375679223849242716115189172277086483740141094101622788529221300654799845036204924025606034340563544265672445015561098670699050165712650377111020875636451633693151428363117186205801819251204478460127516948854671884967526752172853134432518989023251183704409004975850458243891808885
[*] signing m and sending it.
[+] Receiving all data: Done (54B)
[*] Closed connection to smiley.cat port 39807
[+] flag maybe? .;,;.{squares_as_a_service_est_like_the_dawn_of_time}

Flag: .;,;.{squares_as_a_service_est_like_the_dawn_of_time}