Bogosort

Platform: CUSTOM | Category: Reversing | Type: Challenge | Difficulty: Medium | OS: N/A | **Author: XESXOR Techniques: character_permutation_recovery, floating_point_rodata_extraction, sin_value_mapping, static_disassembly

Summary

Walkthrough of the CUSTOM Reversing Bogosort. Task: ELF binary bogosorts a scrambled flag string until check_correct_order passes; check computes sin(ord(char)*π/180) and compares against 36 expected doubles. Solution: compute sin values for each

Description

Этот ELF сам может собрать флаг, но сделает это через пару сотен лет. Можно подождать или вспомнить геометрию.

English summary: An ELF binary can assemble the flag by itself, but it would take hundreds of years. You can either wait or "remember geometry" to solve it analytically.

File provided: bogosort — ELF 64-bit LSB PIE executable, x86-64, dynamically linked, not stripped.

Analysis

Reconnaissance

The binary is not stripped, revealing key symbols: main, shuffle_string, check_correct_order, plus imports for sin, srand, rand, time, strlen, strcpy, printf, puts. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Main function

1. Seeds PRNG with srand(time(0))
2. Stores a scrambled flag string on the stack via immediate movabs instructions:
   • 0x5F52754331425234 → 4RB1CuR_
   • 0x7B7D735F63316146 → Fa1c_s}{
   • 0x5F677430674E6F54 → ToNg0tg_
   • 0x6C74756F42633173 → s1cBoutl
   • 0x674e6530 → 0eNg
   • Full scrambled string: 4RB1CuR_Fa1c_s}{ToNg0tg_s1cBoutl0eNg (36 characters)
3. Enters a bogosort loop: calls shuffle_string, then check_correct_order. If the check returns 1, prints the flag. Otherwise prints progress every 100,000 iterations and continues shuffling indefinitely. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

shuffle_string function

Standard Fisher-Yates shuffle using rand() — produces a random permutation of the input string each iteration.

check_correct_order function (the key!)

This is where the "geometry" hint pays off:

1. Copies 36 pre-stored double values (288 bytes) from .rodata at offset 0x2020 onto the stack.
2. Checks that strlen(input) == 36; returns 0 if not.
3. For each character at position i:
   • Computes sin(ord(char[i]) * π / 180.0) — treats the ASCII value as degrees and takes the sine.
   • Constants from .rodata: π = 3.141592653589793 at offset 0x21b0, divisor = 180.0 at 0x21b8.
   • Compares fabs(computed_sin - expected[i]) against epsilon 0.0001 (at 0x21d0).
   • If any character's sin value doesn't match, returns 0.
4. Returns 1 only if all 36 positions match their expected sin values. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Expected sin values (36 doubles from .rodata)

[0]  0.9135  [1]  0.8910  [2]  0.9744  [3]  0.9205  [4]  0.9945
[5]  0.9397  [6]  0.8387  [7]  0.9135  [8]  0.7431  [9]  0.9744
[10] 0.9336  [11] 0.9063  [12] 0.9336  [13] 0.9903  [14] 0.8988
[15] 0.7547  [16] 0.9781  [17] 0.9744  [18] 0.9962  [19] 0.7431
[20] 0.9903  [21] 0.9962  [22] 0.9877  [23] 0.7880  [24] 0.7547
[25] 0.9877  [26] 0.8910  [27] 0.9511  [28] 0.9925  [29] 0.8988
[30] 0.9816  [31] 0.9962  [32] 0.9063  [33] 0.7547  [34] 0.9781
[35] 0.8192

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

Why bogosort is infeasible

A 36-character string has 36! ≈ 3.7 × 10⁴¹ possible permutations. Even at millions of shuffles per second, brute force would take far longer than the age of the universe — hence the hint about "a couple hundred years."

Solution

The key insight is that each unique character in the scrambled string produces a unique sin(ord(c) * π / 180) value. Instead of shuffling, we can directly compute which character belongs at each position.

Step 1: Build character-to-sin mapping

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

Compute sin(ord(c) * π / 180) for each unique character in the scrambled string:

Step 2: Match expected values to characters

For each expected sin value at position i, find the character whose computed sin value is within epsilon 0.0001.

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

# Scrambled flag string from the binary
scrambled = "4RB1CuR_Fa1c_s}{ToNg0tg_s1cBoutl0eNg"

# Expected sin values extracted from .rodata (36 doubles)
expected = [
    0.9135, 0.8910, 0.9744, 0.9205, 0.9945,
    0.9397, 0.8387, 0.9135, 0.7431, 0.9744,
    0.9336, 0.9063, 0.9336, 0.9903, 0.8988,
    0.7547, 0.9781, 0.9744, 0.9962, 0.7431,
    0.9903, 0.9962, 0.9877, 0.7880, 0.7547,
    0.9877, 0.8910, 0.9511, 0.9925, 0.8988,
    0.9816, 0.9962, 0.9063, 0.7547, 0.9781,
    0.8192
]
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# Build mapping: sin value -> character (for unique chars)
sin_to_char = {}
for c in set(scrambled):
    val = math.sin(ord(c) * math.pi / 180.0)
    sin_to_char[round(val, 4)] = c

# Recover flag by matching expected values
flag = ""
for exp_val in expected:
    for sin_val, char in sin_to_char.items():
        if abs(sin_val - exp_val) < 0.0001:
            flag += char
            break

print(flag)
# Output: BugCTF{REDACTED}

Step 3: Verify

The recovered flag BugCTF{REDACTED} decodes to the message: "B0gosoRt1Ng 0R c41culate s1N" — "Bogosorting OR calculate sin!" — a perfect punchline matching both the challenge name and the geometry hint. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Key Takeaways / Lessons

• Mastering character_permutation_recovery, floating_point_rodata_extraction, sin_value_mapping, static_disassembly was key to this challenge.
• Always check for common misconfigurations and verify assumptions.

---

Crafted by XESXOR Research • 2026-05-27 • CUSTOM • Bogosort • Difficulty: Medium