2024 Hack The Boo: TerrorFryer

#htb #ctf #reversing #binary #shuffling #random

Challenge Information

AttributeDetails
Event2024 Hack The Boo
CategoryReversing
ChallengeTerrorFryer

Summary

The TerrorFryer challenge involves analyzing a binary that implements a shuffling algorithm based on the Fisher-Yates shuffle. The challenge provides an expected shuffled output and requires finding the original input string that, when processed through the fryer_simulation function, produces the given output.

Analysis

Understanding the Algorithm

The binary implements a deterministic shuffling algorithm with a fixed seed (0x13377331). The shuffle algorithm works as follows:

  1. Takes an input string
  2. Converts it to a list of characters
  3. Uses random number generation with a fixed seed to perform shuffling
  4. Returns the shuffled string

The expected shuffled output is:

1_n3}f3br9Ty{_6_rHnf01fg_14rlbtB60tuarun0c_tr1y3

Key Observations

  • The seed is hardcoded: 0x13377331
  • The algorithm uses rand_r() equivalent with proper seeding
  • The shuffling follows the Fisher-Yates algorithm pattern
  • Character swaps are performed based on random indices

Solution

Approach 1: Brute Force Permutations

The first solver attempts to find the original input by testing permutations of the known output:

import random


def fryer_simulation(input_str):
    seed = 0x13377331
    random.seed(seed)


    input_list = list(input_str)
    length = len(input_list)


    if length > 1:
        lVar4 = 0
        while lVar4 != length - 1:
            iVar2 = random.randint(0, 2**32 - 1)
            swap_index = (iVar2 % (length - lVar4)) + lVar4


            # Swap characters
            input_list[lVar4], input_list[swap_index] = input_list[swap_index], input_list[lVar4]


            lVar4 += 1


    return ''.join(input_list)


# Given expected string
expected_str = "1_n3}f3br9Ty{_6_rHnf01fg_14rlbtB60tuarun0c_tr1y3"


# Try different permutations
from itertools import permutations


for perm in permutations(expected_str):
    perm_str = ''.join(perm)
    shuffled = fryer_simulation(perm_str)
    if shuffled == expected_str:
        print(f"Original input found: {perm_str}")
        break

Approach 2: Integrated Solution with pwntools

The second solver uses pwntools to interact with the binary directly:

from pwn import *
import random


context.binary = './fryer'


def fryer_simulation(input_str):
    seed = 0x13377331
    random.seed(seed)


    input_list = list(input_str)
    length = len(input_list)


    if length > 1:
        lVar4 = 0
        while lVar4 != length - 1:
            iVar2 = random.randint(0, 2**32 - 1)
            swap_index = (iVar2 % (length - lVar4)) + lVar4


            input_list[lVar4], input_list[swap_index] = input_list[swap_index], input_list[lVar4]


            lVar4 += 1


    return ''.join(input_list)


binary = process('./fryer')
expected_output = "1_n3}f3br9Ty{_6_rHnf01fg_14rlbtB60tuarun0c_tr1y3"


from itertools import permutations


for perm in permutations(expected_output):
    perm_str = ''.join(perm)
    simulated = fryer_simulation(perm_str)


    if simulated == expected_output:
        print(f"[+] Found the correct input: {perm_str}")


        binary.sendline(perm_str)
        response = binary.recvall()
        print(response.decode())


        break


binary.close()

Key Takeaways

  • Fisher-Yates Algorithm: Understanding classic shuffling algorithms is important in reverse engineering
  • Fixed Seeds: Seeded random number generators produce deterministic outputs, which can be exploited
  • Reverse Engineering Approach: When the transformation is understood, working backward by testing permutations can reveal the original input
  • Binary Analysis: Understanding algorithm logic from decompiled/disassembled code requires careful attention to loop structures and operations
  • Tool Integration: Using tools like pwntools allows automated interaction with binaries for testing hypotheses
  • Computational Complexity: Note that brute-forcing all permutations of a long string is computationally expensive; optimization strategies may be needed

Tools Used

  • Python: For implementing the algorithm simulation
  • pwntools: For binary interaction and automation
  • itertools: For permutation generation

References