ЗаБАГованная башня (Bugged Tower)

Platform: bug-makers | Category: Reversing | Type: Challenge | Difficulty: Easy | OS: Linux | Author: XESXOR | Date: 2026-05-27 | Status: Solved Techniques: xor_decryption, base64_decoding, game_logic_reversal, optimal_algorithm_derivation, digit_to_ascii_conversion

Summary

Task: ELF binary implementing Tower of Hanoi game where move history becomes XOR decryption key. Solution: derive optimal 15-move solution for 4 disks, convert move history to ASCII key via 3-digit grouping, XOR-decrypt base64-decoded ciphertext.

ЗаБАГованная башня (Bugged Tower) — Bug-Makers CTF

Description

На сколько оптимальный алгоритм решения вы можете найти?

English summary: Given an ELF binary that implements a Tower of Hanoi game with 4 disks. The player's move history is used to derive a XOR key that decrypts a hidden flag. The challenge asks for the most optimal solving algorithm — hinting that the minimum number of moves (2^4 - 1 = 15) is required.

Analysis

Initial Reconnaissance

The binary is a 64-bit ELF, not stripped, dynamically linked. Key symbols revealed the architecture immediately: ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

• Game logic: main, initTower, displayTowers, isValidMove, isGameComplete, push, pop, peek, isEmpty
• Decryption pipeline: base64_decode, base64_table, decode_text, xor_crypt, digitsToAsciiString, encoded

A base64-encoded ciphertext was found at address 0x2080:

JxMXJiw/HlIcCRcCVFEYCDkYURYWVDkWX0wXGA==

Game Flow Reversal

The binary implements a classic Tower of Hanoi with 4 disks on 3 pegs (towers 0, 1, 2):

1. Move recording: Each move is stored as "1<from><to>" — a 3-character string. For example, moving a disk from tower 0 to tower 2 produces "102". ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

2. History concatenation: All move strings are concatenated into a single move history string.

3. Key derivation via digitsToAsciiString(): The history string is processed 3 digits at a time, converting each triplet to an ASCII character: d1*100 + d2*10 + d3 → chr(value). For example, "101" → chr(101) = 'e', "102" → chr(102) = 'f'.

4. Decryption via decode_text(): The base64-encoded ciphertext is decoded, then XOR'd with the derived key (repeating).

Key Insight

The challenge description explicitly asks "how optimal of a solving algorithm can you find?" — this is the critical hint. The optimal Tower of Hanoi solution for n disks requires exactly 2^n - 1 moves. For 4 disks: 15 moves. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Only the optimal 15-move sequence produces the correct XOR key. Any suboptimal solution generates a different (longer) key that won't decrypt the flag.

Solution

Step 1: Generate Optimal Moves

The classic recursive Tower of Hanoi algorithm for 4 disks (source=0, target=2, auxiliary=1) produces:

Step 2: Derive XOR Key

Move history string (45 characters):

101102112101120121101102112110120112101102112

Converting 3 digits at a time to ASCII:

101 → 'e', 102 → 'f', 112 → 'p', 101 → 'e', 120 → 'x', 121 → 'y',
101 → 'e', 102 → 'f', 112 → 'p', 110 → 'n', 120 → 'x', 112 → 'p',
101 → 'e', 102 → 'f', 112 → 'p'

XOR key: efpexyefpnxpefp (15 characters)

Step 3: Decrypt

 python read-only • copy allowed Copy
#!/usr/bin/env python3
"""
Tower of Hanoi Flag Decryptor
Bug-Makers CTF - "ZaBAGovannaya bashnya" (Bugged Tower)
"""
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

import base64

ENCODED = "JxMXJiw/HlIcCRcCVFEYCDkYURYWVDkWX0wXGA=="

def hanoi_moves(n, source=0, target=2, auxiliary=1):
    """Generate optimal Tower of Hanoi moves for n disks."""
    if n == 0:
        return []
    moves = []
    moves.extend(hanoi_moves(n - 1, source, auxiliary, target))
    moves.append((source, target))
    moves.extend(hanoi_moves(n - 1, auxiliary, target, source))
    return moves

def build_move_history(moves):
    """Build the move history string: "1<from><to>" for each move."""
    return "".join(f"1{src}{dst}" for src, dst in moves)
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

def digits_to_ascii_string(s):
    """Convert 3-digit groups to ASCII characters."""
    result = ""
    for i in range(0, len(s) - 2, 3):
        d1 = ord(s[i]) - ord('0')
        d2 = ord(s[i+1]) - ord('0')
        d3 = ord(s[i+2]) - ord('0')
        result += chr(d1 * 100 + d2 * 10 + d3)
    return result

def xor_crypt(data, key):
    """XOR data with repeating key."""
    return bytes(b ^ ord(key[i % len(key)]) for i, b in enumerate(data))

# Generate optimal moves for 4 disks
moves = hanoi_moves(4)
history = build_move_history(moves)
key = digits_to_ascii_string(history)
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# Decrypt
ciphertext = base64.b64decode(ENCODED)
flag = xor_crypt(ciphertext, key).decode('utf-8')
print(f"Flag: {flag}")
# Flag: BugCTF{REDACTED}

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