spbctf_4_x86_64

Platform: spbctf | Category: Reversing | Type: Challenge | Difficulty: Easy | OS: Linux | Author: XESXOR | Date: 2026-03-25 | Status: Solved Techniques: constraint_solving, disassembly, sorting_algorithm_analysis, static_analysis, xor_decryption

Summary

Task: ELF64 binary validates input digits as swap indices to sort an array, then XOR-decrypts the flag. Solution: BFS to find valid swap sequence that sorts [8,7,5,4,1,3,2,6,9,10] into [1..10].

spbctf_4_x86_64 — SPbCTF (rev-kids20)

Description

Binary expects a string of digits as its argument. If it passes the checks, it will show the flag. There are multiple inputs that satisfy the binary. Hint: "Try dragging digits starting from beginning, one by one, to the needed places."

Task: Reverse engineer the binary to understand the validation algorithm and find a valid input that produces the flag.

Analysis

Binary Reconnaissance

$ file spbctf_4_x86_64
ELF 64-bit LSB executable, x86-64, dynamically linked, not stripped

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

Key observations:

• Not stripped — function names are available
• Key function: bubble_sort_sequence_executor_aka_transposition_performer
• Format string: "Your flag: %s"
• Initial array: [8, 7, 5, 4, 1, 3, 2, 6, 9, 10]
• Target array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Algorithm Reverse Engineering

1. Input validation: Accepts a string of digits (0-8)
2. Swap operation: For each digit d in input, swap arr[d] with arr[d+1]
3. Validation: After all swaps, array must equal [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
4. Flag decryption: XOR encrypted bytes with input string (cyclic) ‍​‌‌​​​​‌​‌‌​​‌‌​​‌‌​​‌‌​​‌‌​​‌​​​​‌‌​​​​​‌‌​​‌‌​​‌‌​​‌​‌​‌‌​​‌​‌‍

Encrypted Flag Bytes

0x63, 0x50, 0x4b, 0x7d, 0x5b, 0x61, 0x59, 0x72,
0x5e, 0x40, 0x5a, 0x5a, 0x52, 0x60, 0x43, 0x5d,
0x54, 0x42, 0x50, 0x5f, 0x5c, 0x59, 0x5f, 0x55,
0x7f, 0x55, 0x57, 0x45

Key Insight

The hint "drag digits from beginning, one by one, to needed places" describes a bubble-sort-like approach:

• Process elements from largest to smallest (10, 9, 8, ... 1)
• For each element, drag it to its correct position using adjacent swaps

This produces the swap sequence: [0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 0, 1, 2, 1] ‍​‌‌​​​​‌​‌‌​​‌‌​​‌‌​​‌‌​​‌‌​​‌​​​​‌‌​​​​​‌‌​​‌‌​​‌‌​​‌​‌​‌‌​​‌​‌‍

Multiple valid inputs exist since there are multiple valid sorting sequences.

Solution

 python read-only • copy allowed Copy
#!/usr/bin/env python3
"""
Find swap sequence using BFS and decrypt the flag.
"""
from collections import deque

# Initial and target arrays
initial = [8, 7, 5, 4, 1, 3, 2, 6, 9, 10]
target = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

# Encrypted flag bytes
encrypted = bytes([
    0x63, 0x50, 0x4b, 0x7d, 0x5b, 0x61, 0x59, 0x72,
    0x5e, 0x40, 0x5a, 0x5a, 0x52, 0x60, 0x43, 0x5d,
    0x54, 0x42, 0x50, 0x5f, 0x5c, 0x59, 0x5f, 0x55,
    0x7f, 0x55, 0x57, 0x45
])
‍​‌‌​​​​‌​‌‌​​‌‌​​‌‌​​‌‌​​‌‌​​‌​​​​‌‌​​​​​‌‌​​‌‌​​‌‌​​‌​‌​‌‌​​‌​‌‍

def find_swaps_bfs():
    """BFS to find shortest swap sequence"""
    initial_tuple = tuple(initial)
    target_tuple = tuple(target)
    
    queue = deque([(initial_tuple, [])])
    visited = {initial_tuple}
    
    while queue:
        state, swaps = queue.popleft()
        
        if state == target_tuple:
            return swaps
        
        # Try each possible swap (0-8, since we swap i with i+1)
        for i in range(9):
            new_state = list(state)
            new_state[i], new_state[i+1] = new_state[i+1], new_state[i]
            new_state = tuple(new_state)
            
            if new_state not in visited:
                visited.add(new_state)
                queue.append((new_state, swaps + [i]))
    
    return None
‍​‌‌​​​​‌​‌‌​​‌‌​​‌‌​​‌‌​​‌‌​​‌​​​​‌‌​​​​​‌‌​​‌‌​​‌‌​​‌​‌​‌‌​​‌​‌‍

# Find swap sequence
swaps = find_swaps_bfs()
input_str = ''.join(str(s) for s in swaps)
print(f"Input string: {input_str}")
print(f"Length: {len(input_str)}")

# Decrypt flag
flag = []
for i, c in enumerate(encrypted):
    key_byte = ord(input_str[i % len(input_str)])
    flag.append(chr(c ^ key_byte))

print(f"Flag: {''.join(flag)}")

Execution

 bash read-only • copy allowed Copy
$ ./spbctf_4_x86_64 "012345601234501230121"
Your flag: REDACTED

Swap Sequence Visualization

Starting array: [8, 7, 5, 4, 1, 3, 2, 6, 9, 10] ‍​‌‌​​​​‌​‌‌​​‌‌​​‌‌​​‌‌​​‌‌​​‌​​​​‌‌​​​​​‌‌​​‌‌​​‌‌​​‌​‌​‌‌​​‌​‌‍

The sequence 012345601234501230121 (21 swaps) sorts the array:

1. Swaps 0-6: Move element 10 from position 9 to position 9 (already correct)
2. Swaps 0-5: Move element 9 from position 8 to position 8 (already correct)
3. Continue moving smaller elements to their positions...

Final array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] ‍​‌‌​​​​‌​‌‌​​‌‌​​‌‌​​‌‌​​‌‌​​‌​​​​‌‌​​​​​‌‌​​‌‌​​‌‌​​‌​‌​‌‌​​‌​‌‍