rootybooty

Platform: spbctf | Category: Reversing | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-06-25 | Status: Solved Techniques: magic_number_division_recognition, modified_modulus_cipher, python_reimplementation, rc4_reverse_engineering, static_analysis

Summary

Task: ELF64 'malware' that reboots the host (reboot syscall gated on getuid) unless run as root, hiding an RC4-style decryptor. Solution: statically reverse the cipher, recognize the magic-number division reveals modulus 129 (not 256) over a 129-entry S-box, and reimplement the modified RC4 in Python to decrypt the flag offline.

rootybooty — SPbCTF (rev-kids20)

Description

it's a bad bad malware, run only on a virtual machine.

A 64-bit ELF PIE binary is given. It refuses to do anything useful unless run as root, and contains a reboot() tripwire that punishes running it under a normal user. The goal is to recover the flag without detonating the sample, by statically reversing its embedded decryptor.

Analysis

Recon:

• file: ELF 64-bit LSB PIE, x86-64, dynamically linked, not stripped (Debian GCC 9.3.0). Only main is exported, but ASK, AGRP, CRYPT, swap are visible as local symbols in objdump.
• Imports of interest: reboot, getuid, geteuid, malloc, strlen, putchar, puts.
• Strings: "You must run this as root." and an encoded key blob o$NCF~9}[f+{S9Q6"\Df.JaFcm*p in .rodata at vaddr 0x201f, plus a CRYPT label. ‍​‌‌​​​​‌​‌‌​​‌‌​​‌‌​​‌‌​​‌‌​​‌​​​​‌‌​​​​​‌‌​​‌‌​​‌‌​​‌​‌​‌‌​​‌​‌‍

Control flow

• main checks geteuid(). Non-zero euid → prints "You must run this as root." and exits. euid == 0 → proceed.
• main builds a 34-byte ciphertext on the stack from four movabs constants (little-endian QWORDs), points a key at .rodata 0x201f, mallocs 0x22 (34) output bytes, calls CRYPT(key, ciphertext, output), then prints 0x20 (32) output bytes via putchar and a newline.
• CRYPT(rdi=key, rsi=ct, rdx=out) = ASK(key, Sbox) (RC4 KSA) followed by AGRP(Sbox, ct, out) (RC4 PRGA + XOR). ‍​‌‌​​​​‌​‌‌​​‌‌​​‌‌​​‌‌​​‌‌​​‌​​​​‌‌​​​​​‌‌​​‌‌​​‌‌​​‌​‌​‌‌​​‌​‌‍

Anti-analysis (the "malware")

swap and ASK call reboot() when getuid() falls in particular ranges:

• swap(): after a normal byte swap, getuid(); if eax <= 0xc → reboot(0xa1b2c3d4).
• ASK(): if uid is in a signed range (cmp -0x63 / 0x6) → reboot(0x1234567).

So running it as a normal interactive user reboots the box. The intended path is running as root, where getuid()/geteuid() are 0 and the reboot branches are skipped. Statically we just ignore those branches.

KEY INSIGHT — modified RC4 with modulus 129

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

The modular reduction is done via the compiler's magic-number division. The disassembly shows:

imul rax, rax, 0xfe03f81 ; shr rax, 0x20 ; sar ecx, 0x3   ; q = floor(x / 129)
shl eax, 0x7 ; add eax, ecx ; sub edx, eax                ; eax = q*128 + q = q*129
                                                          ; edx = x - q*129

q*128 + q = q*129 proves the divisor is 129, not 256 (standard RC4) and not 128. The S-box is initialized only over indices 0..0x80 (129 entries: S[i]=i for i in 0..128). Assuming mod 256/128 yields garbage — this is the trap. Note the division uses C trunc semantics (toward zero) because the key byte is read signed (movsx), so negative values are possible. ‍​‌‌​​​​‌​‌‌​​‌‌​​‌‌​​‌‌​​‌‌​​‌​​​​‌‌​​​​​‌‌​​‌‌​​‌‌​​‌​‌​‌‌​​‌​‌‍

ASK (KSA, uid==0 path)

• S[i]=i for i in 0..0x80
• j=0
• for i in 0..0x80: keyb = (signed) key[i % keylen]; j = (S[i] + j + keyb) mod 129 (truncated division); swap S[i], S[j]

AGRP (PRGA, euid==0 path)

• i2=0, j2=0
• for k in 0..0x21 (34 iterations):
  • i2 = (i2 + 1) mod 129
  • j2 = (j2 + S[i2]) mod 129
  • swap S[i2], S[j2]
  • t = (S[i2] + S[j2]) mod 129
  • output[k] = ciphertext[k] XOR S[t]
• main prints the first 32 bytes.

Extracted data

• key (hex): 6f244e43467e397d5b662b7b53395136225c44662e4a6146636d2a70 (o$NCF~9}[f+{S9Q6"\Df.JaFcm*p, 28 bytes, .rodata @ 0x201f)
• ciphertext (hex): 6537720448557c5f1531055a3d1d053053110b5f634436230d287e290b7e697c (32 meaningful bytes from the four LE QWORDs 0x5f7c554804723765, 0x30051d3d5a053115, 0x233644635f0b1153, 0x7c697e0b297e280d) ‍​‌‌​​​​‌​‌‌​​‌‌​​‌‌​​‌‌​​‌‌​​‌​​​​‌‌​​​​​‌‌​​‌‌​​‌‌​​‌​‌​‌‌​​‌​‌‍

Solution

Reimplement the modified RC4 in Python with MOD=129 and truncating division — no need to run the dangerous binary.

 python read-only • copy allowed Copy
import struct, math

key = bytes.fromhex('6f244e43467e397d5b662b7b53395136225c44662e4a6146636d2a70')
vals = [0x5f7c554804723765, 0x30051d3d5a053115, 0x233644635f0b1153, 0x7c697e0b297e280d]
ct = (b''.join(struct.pack('<Q', v) for v in vals) + b'\x00\x00')[:34]
keylen = len(key)
MOD = 129

def mod(val):
    q = math.trunc(val / MOD)   # truncate toward zero, matching the asm
    return val - q * MOD
‍​‌‌​​​​‌​‌‌​​‌‌​​‌‌​​‌‌​​‌‌​​‌​​​​‌‌​​​​​‌‌​​‌‌​​‌‌​​‌​‌​‌‌​​‌​‌‍

# S-box over 0..128 only
S = list(range(256))
for i in range(0, 0x81):
    S[i] = i

# ASK: KSA
j = 0
for i in range(0, 0x81):
    keyb = key[i % keylen]
    if keyb >= 128:             # movsx: signed key byte
        keyb -= 256
    j = mod(S[i] + j + keyb)
    S[i], S[j] = S[j], S[i]

# AGRP: PRGA + XOR
out = bytearray()
i2 = 0
j2 = 0
for k in range(0, 0x22):
    i2 = mod(i2 + 1)
    j2 = mod(j2 + S[i2])
    S[i2], S[j2] = S[j2], S[i2]
    t = mod(S[i2] + S[j2])
    out.append((ct[k] ^ S[t]) & 0xff)
‍​‌‌​​​​‌​‌‌​​‌‌​​‌‌​​‌‌​​‌‌​​‌​​​​‌‌​​​​​‌‌​​‌‌​​‌‌​​‌​‌​‌‌​​‌​‌‍

print(out[:32].decode())

Output: SPbCTF{REDACTED}

The flag is its own lesson: don't run samples as root — and the reboot trick punishes those who run it as a non-root user instead. ‍​‌‌​​​​‌​‌‌​​‌‌​​‌‌​​‌‌​​‌‌​​‌​​​​‌‌​​​​​‌‌​​‌‌​​‌‌​​‌​‌​‌‌​​‌​‌‍