Reverse Engineering Jane Street's ASIC Challenge

Jane Street's challenges are known for their ability to nerd-snipe developers, and their ASIC reverse engineering puzzle was no exception. This post dives into a developer's journey through a month-long rabbit hole, tackling a complex problem: understanding the functionality of an Application-Specific Integrated Circuit (ASIC) described by a GDS file.

The core task was to take a GDS (Graphic Database System) file – a common format for integrated circuit layout – and work backward to deduce the chip's function, ultimately revealing a hidden message or "password." The challenge comprised two parts: a warmup with more provided information and the main puzzle, where assistance was minimal.

Initial Exploration and File Formats

Starting with little prior research, the developer adopted a hands-on approach. The challenge files included GDS files, which are binary, and VCD (Value Change Dump) files, which are text-based and typically contain simulation waveforms. Initial inspection of the VCD file for the main puzzle revealed suspicious ASCII characters, leading to a small C program that outputted "TRY AGAIN," confirming the circuit's ability to communicate messages.

For parsing the GDS files, the Python library gdstk proved invaluable. It allowed initial introspection, revealing, for example, 27 elements in the warmup puzzle's GDS file:

Bash % python3 -c 'print(len(import("gdstk").read_gds("warmup/04_final.gds").cells))' 27

Before settling on a practical path, the author admittedly veered into a multi-day tangent, attempting to build a custom circuit simulator, a hardware description language parser, and a waveform viewer. This highlights a common developer pitfall: over-engineering custom tools when robust, existing solutions often suffice. Eventually, this custom software was abandoned in favor of established GDS viewers and documentation.

Leveraging Standard Cells and Documentation

A critical turning point was discovering the sky130-unofficial documentation, which describes a standard library for chip design elements. This 'sky130' framework provides common design components (like 'and' gates or more complex 'o21bai' cells) and, crucially, their functional descriptions. This documentation, combined with text labels extracted from GDS elements (e.g., via SVG exports from gdstk), allowed the developer to map geometric layouts to their logical functions and I/O pins.

The gdstk library's ability to detect 2D overlaps between elements proved essential. Even though GDS describes 3D geometry, the assumption that labels or pins overlapping in 2D space indicated connection points worked remarkably well. This allowed for the theoretical mapping of specific geometry to circuit element I/O, forming the basis for extracting a "real circuit."

From Geometry to Logic: Circuit Extraction

Converting the GDS geometry, with its thousands of paths and polygons, into a logical circuit graph was the next major hurdle. The approach involved identifying elements that were "touching" – on adjacent layers and overlapping – and treating them as connected. A simplification step coalesced these connected wire segments into single logical wires. This process, while algorithmically intensive, was manageable thanks to the developer's background in graph algorithms.

The output of this extraction was a network that could be translated into Verilog, a hardware description language. This allowed for basic simulations, confirming fundamental connections like "turning this pin high makes that one go low." For the warmup puzzle, this led to identifying major components: two shift registers, an adder, and a comparator. Knowing the comparator (comparitor496) was looking for a sum of 496, the task became finding the correct bit sequence to achieve this, culminating in a successful warmup simulation.

Scaling Up and Uncovering the Real Puzzle's Structure

The real puzzle presented a significant jump in complexity: over 80 component types and nearly 10,000 instances, compared to the warmup's 20 types and 1,000 instances. While initial scripts adapted quickly, performance became an issue, with circuit extraction taking almost a minute. Optimizing the wire segment gathering step to be 100x faster, from 3.4 seconds to 0.03 seconds, provided a crucial win, though the connected components step remained time-consuming.

A minor but notable success involved manually transcribing descriptions for the 40+ new components from the documentation. After integrating these and making quality-of-life improvements, a simulation of the real puzzle could run, albeit without producing the desired output initially.

During this phase, a critical bug was identified and reported to Jane Street: an undriven wire connected to two input pins, and an unconnected neighboring pin. Jane Street confirmed the bug, noting it wouldn't impact the challenge's results, a small but significant technical achievement for the developer.

By mapping out sub-circuits and their interconnections, a bird's-eye view emerged. The "success" wire was traced back to six inputs, two of which went high after specific clock cycles, simplifying the problem to controlling four wires. Patterns emerged, suggesting left-most sub-circuits acted as a signal generator, potentially holding clues to the "password" in their structure.

The Breakthrough: Reverse Engineering the Input

After days of struggling with a non-functional overall simulation, a fundamental oversight was discovered: the 'reset' pin hadn't been set, effectively disabling the entire circuit. Correcting this immediately yielded the expected "TRY AGAIN" message. Further experimentation with inputs revealed other messages: "EMPTY SKY" for all zeros and "BIG BANG" for all ones, narrowing the correct answer space. The challenge boiled down to finding a 120-bit input.

Exhaustively checking 2^120 inputs was infeasible. The breakthrough idea was to run the simulation in reverse. By knowing the desired output (success) at a specific time (e.g., 120 clock cycles) and knowing the circuit's initial state (all outputs at zero), the problem could be framed as a recurrence relation. This allowed working backward from the target state to determine the necessary inputs. This approach, similar to the shift register component in the warmup, offered a mathematical pathway to solve for the elusive 120-bit password.

This journey highlights the power of combining open-source tools, meticulous documentation review, persistent debugging, and creative algorithmic thinking to solve complex reverse engineering problems.

FAQ

Q: What is a GDS file and why is it used in ASIC design? A: A GDS (Graphic Database System) file is a binary file format used for transferring integrated circuit layout data between different stages of the design process. It describes the geometric shapes, layers, and text labels that define the physical layout of a microchip, essentially providing instructions for manufacturing the silicon.

Q: How did sky130-unofficial documentation help in reverse engineering the ASIC? A: The sky130-unofficial documentation provided a standard library of design elements (standard cells) used in the ASIC. By referencing this documentation, the developer could understand the function and I/O pins of individual geometric components within the GDS file, translating physical layouts into their logical equivalents, which was crucial for building a functional circuit model.

Q: What was the significance of running the simulation in reverse to solve the challenge? A: The significance lay in transforming an intractable forward-simulation problem (finding a 120-bit input out of 2^120 possibilities) into a solvable backward-simulation problem. By knowing the desired 'success' output state at a specific clock cycle and the circuit's initial conditions, the problem could be framed as a recurrence relation, allowing the necessary inputs to be deduced by working backward through the circuit's logic gates over time.