spbctf_2_x86

Platform: spbctf | Category: Reversing | Type: Challenge | Difficulty: Easy | OS: NA | Author: XESXOR | Date: 2026-03-25 | Status: Solved Techniques: gcd_based_decryption, prime_factor_encoding_reversal, rodata_table_extraction, static_disassembly

Summary

Task: Reverse engineer the encoding algorithm and decode the given sequence of 16 integers to recover the original 8-character string.

spbctf_2_x86 — SPbCTF (rev-kids20)

Description

You have a binary (ELF 32-bit x86, C language) that encodes a string given as command line argument. Find the original string from this encoded data: 497 1207 1273 871 476 884 1615 475 2233 231 505 1919 190 2755 231 561

Task: Reverse engineer the encoding algorithm and decode the given sequence of 16 integers to recover the original 8-character string.

Analysis

Binary Reconnaissance

$ file spbctf_2_x86
ELF 32-bit LSB executable, Intel 80386, dynamically linked, not stripped

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

Key observations:

• Binary imports: srandom, random, time, strlen, calloc, printf, puts
• Key function name visible: Tr4NsF0rm
• Source file name in strings: spbctf_2.c
• Not stripped — function names are available

Algorithm Reverse Engineering

main function:

1. Seeds PRNG with srandom(time(0))
2. Calls Tr4NsF0rm(argv[1], &output_len) which returns an array of integers
3. Prints each integer with printf("%d ")

Tr4NsF0rm(char *input, int *out_len) function:

1. Computes len = strlen(input)
2. Allocates calloc(2*len, 4) — an int array of size 2*len
3. Uses a lookup table at 0x8048840 containing 10 primes: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
4. For each character at index i:
   • Calls random() % 10 to select prime p1 from the table
   • Calls random() % 10 to select prime p2 from the table
   • If p1 == p2, re-rolls both until they differ
   • Stores char_value * p1 at output position 2*i
   • Stores char_value * p2 at output position 2*i+1
5. Sets *out_len = 2 * len ‍​‌‌​​​​‌​‌‌​​‌‌​​‌‌​​‌‌​​‌‌​​‌​​​​‌‌​​​​​‌‌​​‌‌​​‌‌​​‌​‌​‌‌​​‌​‌‍

Key Insight

Each original character c is encoded as a pair (c * p1, c * p2) where p1 and p2 are two different primes from the table. Since both values share c as a common factor and the primes are coprime, computing GCD(v1, v2) for each pair directly recovers the original character.

The random seed (time(0)) determines which primes are chosen, but it's irrelevant for decoding — GCD works regardless of which primes were used.

Solution

 python read-only • copy allowed Copy
#!/usr/bin/env python3
import math
‍​‌‌​​​​‌​‌‌​​‌‌​​‌‌​​‌‌​​‌‌​​‌​​​​‌‌​​​​​‌‌​​‌‌​​‌‌​​‌​‌​‌‌​​‌​‌‍

# Encoded data (16 values = 8 pairs)
encoded = [497, 1207, 1273, 871, 476, 884, 1615, 475, 2233, 231, 505, 1919, 190, 2755, 231, 561]

# Decode using GCD
result = []
for i in range(0, len(encoded), 2):
    c = math.gcd(encoded[i], encoded[i+1])
    result.append(chr(c))

print(''.join(result))

Step-by-step GCD Computation