breadth picoMini by redpwn Solution

Description

1. Step 1Run and inspect the binary
   Run file and execute the binary to understand what it expects as input. Then load it into Ghidra to decompile and understand the graph structure encoded inside.
   bash

   file breadth

   Copied!

   bash

   chmod +x breadth

   Copied!

   bash

   ./breadth

   Copied!
   Learn more

   The challenge title "breadth" is a direct reference to Breadth-First Search (BFS), a graph traversal algorithm that visits all nodes at the current depth before moving to the next level. The binary likely encodes a graph as an adjacency list or adjacency matrix in its data section and expects you to provide a BFS traversal order.

   Understanding what the program prints when run - error messages, prompts, usage strings - is always the first step. Strings like "wrong path" or "try again" hint at what the binary validates.

2. Step 2Reverse engineer the graph structure
   In Ghidra, identify the graph data (adjacency list or matrix) stored in the binary. Trace the main function to find where it reads input and how it validates the traversal order against the expected BFS path.
   bash

   # Extract all strings from the binary to find hints

   Copied!

   bash

   strings breadth

   Copied!

   bash

   # Disassemble to see data layout

   Copied!

   bash

   objdump -d breadth | head -100

   Copied!
   Learn more

   BFS algorithm uses a queue data structure. Starting from a source node, it enqueues the source, then repeatedly dequeues a node, visits it, and enqueues all its unvisited neighbors. The result is a level-order traversal - all nodes at distance 1 are visited before nodes at distance 2.

   In the binary, the graph is typically stored as a flat array of integers where adj[i][j] = 1 means an edge from node i to node j. Ghidra's decompiler will show the edge-checking logic as a double loop or indexed array access.

   The key insight: the binary knows the correct BFS order. Find the array or sequence it expects, and supply that as your input.

3. Step 3Reconstruct the BFS traversal and submit
   Once you have the graph encoded in the binary, manually run BFS (or write a Python script) to compute the correct traversal order. Feed that order to the binary to receive the flag.
   python

   python3 -c "
   from collections import deque
   # Reconstruct adjacency from binary analysis
   adj = { 0:[1,2], 1:[3], 2:[3,4] }  # example
   visited = set()
   queue = deque([0])
   order = []
   while queue:
       n = queue.popleft()
       if n in visited: continue
       visited.add(n)
       order.append(n)
       for nb in adj.get(n,[]):
           queue.append(nb)
   print(' '.join(map(str,order)))
   "

   Copied!

   bash

   echo '<bfs_order>' | ./breadth

   Copied!
   Learn more

   Implementing BFS in Python using collections.deque gives O(V+E) time complexity. The traversal order depends on the order neighbors are stored in the adjacency structure - make sure to preserve the same neighbor ordering as in the binary's data section.

   If there are multiple valid BFS orderings (due to tie-breaking between same-level nodes), the binary likely accepts only one specific ordering. Try different neighbor orderings until you find the one that produces the expected sequence. Ghidra will show you the exact loop order the binary uses to iterate neighbors.

Flag

The binary validates a BFS traversal order of an embedded graph - reconstruct the adjacency structure from Ghidra, run BFS with the correct neighbor ordering, and submit the sequence.