CTF Writeup: 45exiles Shuffle Challenge

Problem Overview

Challenge Name: 45exiles Shuffle

Core Mechanism:

  • Program reads user input
  • Shuffles the input using rand() with a known seed
  • Compares the shuffled input against a target string stored in memory
  • If they match, you get the flag

Key Insight: You can read the target (shuffled) string from memory, but that’s NOT the answer you need to input. You must reverse the shuffle to find the original input.

Disassembly of key functions

[0x00001160]> pdg @ main

ulong main(void)

{
    uint uVar1;
    int iVar2;
    int64_t iVar3;
    ulong uVar4;
    uint64_t uVar5;
    int64_t in_FS_OFFSET;
    int iStack_244;
    int iStack_240;
    uchar auStack_228 [256];
    uchar auStack_128 [255];
    uchar uStack_29;
    int64_t iStack_20;

    iStack_20 = *(in_FS_OFFSET + 0x28);
    iStack_244 = 0;
    sym.imp.puts("Enter the password please :");
    iVar3 = sym.imp.fgets(auStack_228,0x100,_reloc.stdin);
    if (iVar3 == 0) {
        uVar4 = 1;
    }
    else {
        iVar3 = sym.imp.strcspn(auStack_228,0x2028);
        auStack_228[iVar3] = 0;
        sym.imp.strncpy(auStack_128,auStack_228,0xff);
        uStack_29 = 0;
        iStack_240 = 0;
        while( true ) {
            uVar5 = sym.imp.strlen("Gommage");
            if (uVar5 <= iStack_240) break;
            iStack_244 = "Gommage"[iStack_240] + iStack_244 * 0x1f;
            iStack_240 = iStack_240 + 1;
        }
        uVar1 = sym.imp.strlen(auStack_128);
        fcn.00001249(auStack_128,uVar1,iStack_244);
        iVar2 = sym.imp.strcmp("Ygta_u3G_t0h_0aG_r3",auStack_128);
        if (iVar2 == 0) {
            sym.imp.puts("Good Job !");
        }
        else {
            sym.imp.puts("No... Maybe another time !");
        }
        uVar4 = 0;
    }
    if (iStack_20 != *(in_FS_OFFSET + 0x28)) {
    //WARNING: Subroutine does not return
        sym.imp.__stack_chk_fail();
    }
    return uVar4;
}

[0x00001160]> pdg @ fcn.00001249

void shuffle(int64_t param_1,int param_2,uint param_3)

{
    uchar uVar1;
    int iVar2;
    uint uStack_10;

    if ((param_1 != 0) && (0 < param_2)) {
        sym.imp.srand(param_3);
        for (uStack_10 = param_2 + -1; 0 < uStack_10; uStack_10 = uStack_10 + -1) {
            iVar2 = sym.imp.rand();
            iVar2 = iVar2 % (uStack_10 + 1);
            uVar1 = *(param_1 + uStack_10);
            *(param_1 + uStack_10) = *(param_1 + iVar2);
            *(iVar2 + param_1) = uVar1;
        }
    }
    return;
}

The Main Strategy

Why You Can’t Just Read Memory

Unlike the previous “good kitty” challenge where we could directly read the answer from the stack, this challenge applies transformations to the input before comparison.

User Input → [TRANSFORMATION] → Transformed Input → Compare with Target

Since the transformation happens AFTER you enter input:

  • Target in memory = What your input should become AFTER shuffling
  • Answer you need = What produces the target AFTER shuffling

You cannot shortcut this - you MUST reverse the transformation.

Understanding Input Transformations

Scenario 1: Direct Comparison (Can Read Answer)

// Example from "good kitty" challenge
long flag = calculate_target();
char user_input[8];
read(0, user_input, 8);

// Direct byte-by-byte comparison - NO transformation
for (int i = 0; i < 8; i++) {
    if (user_input[i] != ((char*)&flag)[i]) {
        return FAIL;
    }
}

GDB Solution: Read the answer directly!

(gdb) x/8c $rbp-0xb8   # This IS the answer

Scenario 2: Transformed Input (Must Reverse)

// Example from 45exiles Shuffle
char target[20] = "scrambled_target_string";
char user_input[20];
read(0, user_input, 20);

// Transform input THEN compare
char transformed[20];
shuffle(user_input, transformed, seed);

if (strcmp(transformed, target) == 0) {
    return SUCCESS;
}

The Problem:

What you can read:  target = "scrambled_target_string"
What you need:      original_input = ???
Relationship:       shuffle(original_input, seed) = target

Solution Path:

1. Read 'target' from memory (GDB/Ghidra)
2. Understand the shuffle algorithm
3. Implement reverse_shuffle()
4. Calculate: original_input = reverse_shuffle(target, seed)

The Shuffle Algorithm

Forward Transformation (What Program Does)

from ctypes import CDLL

libc = CDLL("libc.so.6")

def shuffle_string(s, seed):
    """Apply Fisher-Yates shuffle to string"""
    libc.srand(seed)
    arr = list(s)
    
    # Iterate backwards
    for i in range(len(arr) - 1, 0, -1):
        j = libc.rand() % (i + 1)  # Random index from 0 to i
        arr[i], arr[j] = arr[j], arr[i]  # Swap
    
    return ''.join(arr)

# Example
original = "hello_world"
shuffled = shuffle_string(original, 42)
print(f"Original: {original}")
print(f"Shuffled: {shuffled}")

Reverse Transformation (What We Need)

Key Insight: Record all swap operations, then apply them in reverse order.

def unshuffle_string(shuffled, seed):
    """Reverse the shuffle to recover original"""
    # Step 1: Record all swaps that were performed
    libc.srand(seed)  # Same seed = same sequence
    swaps = []
    
    for i in range(len(shuffled) - 1, 0, -1):
        j = libc.rand() % (i + 1)
        swaps.append((i, j))  # Record each swap
    
    # Step 2: Apply swaps in REVERSE order
    arr = list(shuffled)
    for i, j in reversed(swaps):
        arr[i], arr[j] = arr[j], arr[i]  # Undo the swap
    
    return ''.join(arr)

# Example: Recover original from shuffled
shuffled = "some_scrambled_text"
original = unshuffle_string(shuffled, 42)
print(f"Recovered: {original}")

Why This Works: rand() Determinism

Critical Property: rand() with the same seed always produces the same sequence.

# Test determinism
libc.srand(42)
r1 = libc.rand()
r2 = libc.rand()
r3 = libc.rand()

# Reset and generate again
libc.srand(42)
r4 = libc.rand()
r5 = libc.rand()
r6 = libc.rand()

print(r1 == r4)  # True
print(r2 == r5)  # True
print(r3 == r6)  # True

Implications:

  • Shuffle pattern is 100% reproducible
  • We can replay the exact same swaps
  • We can reverse them perfectly

Security Note: ⚠️ This is why rand() should NEVER be used for cryptography or security!

Tools & Techniques

Python for Reversing

from ctypes import CDLL

# Load libc to match C's rand()
libc = CDLL("libc.so.6")

# Always use same seed as binary
libc.srand(seed_from_binary)

# Implement reverse logic

Summary

45exiles Shuffle demonstrates a critical CTF concept: transformation-based validation.

The Strategy:

  1. Input transformation prevents direct memory reading
  2. Must implement reverse transformation
  3. rand() determinism enables perfect reversal
  4. Work backwards: target → reverse() → answer

Remember: When input is transformed before comparison, there’s no shortcut - you must reverse the transformation to find the original input.