rsay

Platform: rev_kids20 | Category: Reversing | Type: Challenge | Difficulty: Easy | OS: Linux | Author: XESXOR | Date: 2026-06-24 | Status: Solved Techniques: deobfuscate_ollvm_flattening, extract_plaintext_before_rsa_encryption, pyghidra_headless_decompilation, rsa_verification, xtea_decryption

Summary

Task: stripped x86-64 ELF (OLLVM control-flow flattening + Heaven's Gate anti-debug) performs textbook RSA (e=65537, hardcoded balanced 2048-bit n) and prints c=m^e mod n with an unfactorable modulus. Solution: instead of factoring, recover the plaintext m before encryption — a 192-byte .rodata blob is XTEA-decrypted (key cafebabe/deadbeef/faceface/c0deefef, delta 0x9E3779B9, 42 rounds) into 96 decimal digits which, read in reverse order, form m; pow(m,65537,n)==c and m.to_bytes() is the flag.

rsay — rev_kids20 (SPbCTF)

• File: rsay.elf — ELF 64-bit x86-64, stripped, dynamically linked
• Source: https://rev-kids20.forkbomb.ru/files/rev/new7/rsay.elf
• Flag: spbctf{REDACTED}

Description

The name is a pun: rsa + say (cowsay-style). Running the binary prints:

Hey! I am going to encrypt the flag with rsa...
Please wait for results...
> 158460114827767882201995264272628704077440291475...

It outputs a single 2047-bit decimal number c — an RSA ciphertext. The output is deterministic regardless of stdin: the flag is hardcoded and encrypted. ‍​‌‌​​​​‌​‌‌​​‌‌​​‌‌​​‌‌​​‌‌​​‌​​​​‌‌​​​​​‌‌​​‌‌​​‌‌​​‌​‌​‌‌​​‌​‌‍

Recon

Strings reveal the parameters and the crypto library:

• e = 65537
• n = a 617-digit (2048-bit) decimal modulus, stored as a string in .rodata
• bi_mod: zero or negative modulus, bi_power: negative exponent, ... → the axTLS bigint library.

So this is textbook RSA: c = m^e mod n, no padding (the imported random() is never actually called at runtime — confirmed with an LD_PRELOAD hook).

On Apple Silicon the ELF runs only under Docker amd64:

 bash read-only • copy allowed Copy
docker run --rm --platform linux/amd64 -v "$PWD":/work -w /work ubuntu:22.04 \
    bash -c "echo '' | ./rsay.elf"

‍​‌‌​​​​‌​‌‌​​‌‌​​‌‌​​‌‌​​‌‌​​‌​​​​‌‌​​​​​‌‌​​‌‌​​‌‌​​‌​‌​‌‌​​‌​‌‍

Factoring is a dead end

n is a strong, balanced RSA-2048 modulus:

• Fermat (close primes): fails.
• Trial division to 1e6: no small factor.
• Pollard p-1, ECM up to B1=250000 (hundreds of curves): nothing.
• gcd(c, n) = 1; iroot(c, e) is not exact for any small e.

Do not try to factor. The intended path is to recover the plaintext m before it is encrypted.

Anti-analysis

The worker function is obfuscated with:

• OLLVM control-flow flattening — a dispatcher driven by a 32-bit state variable compared against magic constants.
• Heaven's Gate / x32-mode transitions and getpid/kill/syscall anti-debug.
• gdb does not work under macOS Rosetta/QEMU emulation (ptrace register I/O errors). ‍​‌‌​​​​‌​‌‌​​‌‌​​‌‌​​‌‌​​‌‌​​‌​​​​‌‌​​​​​‌‌​​‌‌​​‌‌​​‌​‌​‌‌​​‌​‌‍

Dynamic heap scanning (dump /proc/self/mem at the Please wait and > printf points, then test pow(val, e, n) == c for every 32-bit little-endian limb arrangement) finds no plaintext bigint — m is built and consumed without ever sitting in the heap as the flag's ASCII bytes.

Static deobfuscation with PyGhidra

 bash read-only • copy allowed Copy
pip install pyghidra
GHIDRA_INSTALL_DIR=/opt/homebrew/opt/ghidra/libexec python3 - <<'PY'
import pyghidra; pyghidra.start()
from pyghidra import open_program
from ghidra.app.decompiler import DecompInterface
from ghidra.util.task import ConsoleTaskMonitor
with open_program("rsay.elf", analyze=True) as flat:
    p = flat.getCurrentProgram()
    dec = DecompInterface(); dec.openProgram(p)
    f = p.getFunctionManager().getFunctionContaining(
        p.getAddressFactory().getAddress("0x400b00"))
    print(dec.decompileFunction(f, 180, ConsoleTaskMonitor()).getDecompiledFunction().getC())
PY

‍​‌‌​​​​‌​‌‌​​‌‌​​‌‌​​‌‌​​‌‌​​‌​​​​‌‌​​​​​‌‌​​‌‌​​‌‌​​‌​‌​‌‌​​‌​‌‍

The decompiled worker shows the real logic:

1. e and n are loaded with bi_str_import from the decimal strings.
2. A 192-byte (0xC0) blob at .rodata vaddr 0x4403e2 is XTEA-decrypted in place. The rounds use delta = 0x9E3779B9 (shown as -0x61c88647), sum initialized to delta * 0x2a, 42 rounds, and key [0xcafebabe, 0xdeadbeef, 0xfaceface, 0xc0deefef] (visible as immediates inside the obfuscated bit-twiddling).
3. The decrypted bytes are 96 little-endian uint16 shorts, each a single decimal digit 0..9.
4. The message bigint is built with a loop m = m*10 + digit, consuming the digits in reverse order.
5. Finally c = m^65537 mod n is printed. ‍​‌‌​​​​‌​‌‌​​‌‌​​‌‌​​‌‌​​‌‌​​‌​​​​‌‌​​​​​‌‌​​‌‌​​‌‌​​‌​‌​‌‌​​‌​‌‍

So m is the plaintext flag as a big integer, and the flag's decimal digits were XTEA-encrypted in .rodata.

Solve

 python read-only • copy allowed Copy
import struct
n = 27088416445065152412401988600629205919589510736339807113242995665543692567685705808370958648378950013373974868575959945892512480566891454663901291437147085211019068666216566352483136070854190989512834073531801498062999362987638521823006205504444905875595450394288117910424075353372441948652401125634066334890644449270327758011793653577263913929009931405501719514733697425686452609121251146185503481273389486689183113570459449742563038459830287438560687668276184055735432573504289676974530292435369629893924906568600967382226536779446799917330437928553295812800490242877051981306661598095223076349426902448920576650551
e = 65537
c = 15846011482776788220199526427262870407744029147515172582208543207385148127395566700933587311004925149387337370627551792540128823230093147238840196235260453904606270764727846637584370074500427380339863008506338747593586404094051553201263225601020361874720113575630730683102790850863569081727858851594335718737858110618727064463099624160921500198050945993332230960305707753670790012199933959098334082201303841288606011135035773589900447322932648421049562129177761032016721822063065918947165359019991096621165509324910897203369049625710518435667612243027061592741669665372935833159257410693810892355595638034471382607372
‍​‌‌​​​​‌​‌‌​​‌‌​​‌‌​​‌‌​​‌‌​​‌​​​​‌‌​​​​​‌‌​​‌‌​​‌‌​​‌​‌​‌‌​​‌​‌‍

blob = bytes.fromhex(
    "68a2af449096394bdcfe51b174c4af2929ee33e91ed311ed56d52ddce5ad5dfa"
    "50f4eae550b2fcbb99a2c746ca4a11b22809f8306be35d8751de413d4631ab5d"
    "5654746e7262d5c5dc17079fba449da037e32eb93e16306fbe2e791342e1e292"
    "a78470a6954eef7e4886ae2f97762066d49bb55a51ab05337c99ad5ae3567fd2"
    "69014214b5704f7d3a03984683e694d0c9fb345292d78dec8c920d7b52a9cfaeb"
    "72f866c2cdc2e7f32da928b41e6afbb3e1d29df2580b5a3530714323501193b")

key = [0xcafebabe, 0xdeadbeef, 0xfaceface, 0xc0deefef]
delta = 0x9E3779B9
M = 0xffffffff
NR = 0x2a  # 42 rounds
‍​‌‌​​​​‌​‌‌​​‌‌​​‌‌​​‌‌​​‌‌​​‌​​​​‌‌​​​​​‌‌​​‌‌​​‌‌​​‌​‌​‌‌​​‌​‌‍

def xtea_dec(v0, v1):
    s = (delta * NR) & M
    for _ in range(NR):
        v1 = (v1 - (((v0 << 4 ^ v0 >> 5) + v0) ^ (s + key[(s >> 11) & 3]))) & M
        s = (s - delta) & M
        v0 = (v0 - (((v1 << 4 ^ v1 >> 5) + v1) ^ (s + key[s & 3]))) & M
    return v0, v1

out = b""
for i in range(0, len(blob), 8):
    v0, v1 = struct.unpack("<II", blob[i:i+8])
    a, b = xtea_dec(v0, v1)
    out += struct.pack("<II", a, b)

shorts = struct.unpack("<%dH" % (len(out) // 2), out)   # 96 decimal digits
m = int("".join(str(d) for d in reversed(shorts)))      # digits read in reverse
assert pow(m, e, n) == c
print(m.to_bytes((m.bit_length() + 7) // 8, "big").decode())
# spbctf{REDACTED}

‍​‌‌​​​​‌​‌‌​​‌‌​​‌‌​​‌‌​​‌‌​​‌​​​​‌‌​​​​​‌‌​​‌‌​​‌‌​​‌​‌​‌‌​​‌​‌‍

pow(m, 65537, n) == c confirms correctness, and m decodes to the flag.

Lessons

• When RSA n is a strong, balanced modulus, don't factor — recover the plaintext m from the program before encryption.
• OLLVM control-flow flattening is readable: PyGhidra headless decompilation exposes the state machine; the real constants (0x9E3779B9, the four key words) appear as immediates.
• The four magic key words 0xcafebabe / 0xdeadbeef / 0xfaceface / 0xc0deefef plus the <<4 ^ >>5 pattern and delta = 0x9E3779B9 are a clear XTEA fingerprint. ‍​‌‌​​​​‌​‌‌​​‌‌​​‌‌​​‌‌​​‌‌​​‌​​​​‌‌​​​​​‌‌​​‌‌​​‌‌​​‌​‌​‌‌​​‌​‌‍