//Stronk Rabin

>Overview

Category: Crypto
Challenge: break a "stronk" Rabin variant. Server exposes ENC (square mod N) and DEC (returns shuffled, de-duplicated square roots summed modulo N). N = p·q·r·s with all primes ≡ 3 (mod 4).
Goal: recover flag inside ciphertext C.

>Key Insights

Modulus recovery: For any m, ENC(m) = m² mod N ⇒ m² − ENC(m) = k·N. GCD over a few random m reveals N.
Factoring via DEC(1): DEC(1) returns sum of 7–8 CRT-combined roots. Different calls pick different shuffles → outputs vary. For composite M, gcd(DEC(1)_i − DEC(1)_j, M) leaks a non-trivial factor with good probability; recurse to split fully.
Decryption: Once primes known, enumerate 2⁴ CRT roots of C; pick candidate containing prefix nite{ (or its negative modulo N).

>Local Recon

Read chal.py and stronk_rabin_api.py. Observed:
ENC: m² mod N.
DEC: builds all 16 roots, shuffles, drops ± duplicates, asserts 7–8 remain, returns their sum mod N.
Simulated DEC to confirm gcd(DEC(1)_i − DEC(1)_j, N) frequently factors a modulus.
Derived modulus-leak via m² − ENC(m).

>Exploit Plan

Connect, parse banner JSON to get ciphertext C.
Recover N: send several ENC queries on large random m; gcd of m²−ENC(m) gives N.
Factor N: repeat DEC(1) twice, gcd of differences with current composite; recursively split until primes.
Decrypt: compute all 16 CRT roots of C; check for nite{ in roots or their negatives; output flag.

>Solver

Full solver used (path: solve.py):

python


import json

import random

from math import gcd

from typing import List

from Crypto.Util.number import long_to_bytes

from pwn import remote

from sympy import isprime

from sympy.ntheory.modular import crt

HOST = "stronk.chals.nitectf25.live"

PORT = 1337

def recv_json(io):

    while True:

        line = io.recvline(timeout=5)

        if not line:

            raise EOFError("connection closed")

        line = line.decode().strip()

        try:

            return json.loads(line)

        except json.JSONDecodeError:

            continue

def enc(io, m: int) -> int:

    io.sendline(json.dumps({"func": "ENC", "args": [int(m)]}).encode())

    return int(recv_json(io)["retn"])

def dec(io, c: int) -> int:

    io.sendline(json.dumps({"func": "DEC", "args": [int(c)]}).encode())

    return int(recv_json(io)["retn"])

def recover_modulus(io, rounds: int = 8) -> int:

    g = 0

    for _ in range(rounds):

        m = random.getrandbits(1200)

        c = enc(io, m)

        d = abs(m * m - c)

        g = d if g == 0 else gcd(g, d)

    for _ in range(3):

        m = random.getrandbits(400)

        if enc(io, m) != pow(m, 2, g):

            raise ValueError("modulus recovery failed")

    return g

def get_factor(io, n: int) -> int:

    while True:

        a = dec(io, 1)

        b = dec(io, 1)

        g = gcd(abs(a - b), n)

        if 1 < g < n:

            return g

def factorize(io, n: int) -> List[int]:

    factors = [n]

    res = []

    while factors:

        f = factors.pop()

        if isprime(f):

            res.append(f)

            continue

        g = get_factor(io, f)

        factors.extend([g, f // g])

    return res

def recover_flag(C: int, primes: List[int]) -> bytes:

    roots = [[pow(C, (p + 1) // 4, p), (-pow(C, (p + 1) // 4, p)) % p] for p in primes]

    N = 1

    for p in primes:

        N *= p

    candidates = []

    for mask in range(16):

        residues = [roots[i][(mask >> i) & 1] for i in range(4)]

        val = int(crt(primes, residues)[0])

        candidates.append(val % N)

    for x in candidates:

        b = long_to_bytes(x)

        if b.startswith(b"nite{") or b.find(b"nite{") != -1:

            return b

        b_neg = long_to_bytes((N - x) % N)

        if b_neg.startswith(b"nite{") or b_neg.find(b"nite{") != -1:

            return b_neg

    chosen = max(candidates)

    if chosen <= N // 2:

        chosen = N - chosen

    return long_to_bytes(chosen)

def main():

    io = remote(HOST, PORT, ssl=True)

    banner = recv_json(io)

    C = int(banner["C"]) if "C" in banner else int(recv_json(io)["C"])

    print(f"[*] C = {C}")

    N = recover_modulus(io)

    print(f"[*] N bits = {N.bit_length()}")

    primes = factorize(io, N)

    primes.sort()

    print(f"[*] factors: {[hex(p) for p in primes]}")

    flag = recover_flag(C, primes)

    print(f"[*] flag: {flag.decode(errors='ignore')}")

    io.close()

if __name__ == "__main__":

    main()

>Exploitation Steps

Local: verified modulus-leak and factoring strategies via small-bit simulations; ensured solver logic matched DEC behavior.
Remote: ran python3 solve.py; solver auto-fetched C, recovered N (1024 bits), factored into four Blum primes, enumerated roots, found flag.

>Result

Flag: nite{rabin_stronk?_no_r4bin_brok3n}