Crypto Trojan

Imagine the following scenario: a security critical system (e.g. a key card) was designed with an AES encryption circuit. The personalized 128 bit key should under no circumstances be accessible by the user. However, somewhere in the production process workflow a hardware Trojan was inserted into the chip.

The Crypto Trojan example project provides an AES128 encryption netlist that has been tampered with. The purpose is to demonstrate how HAL's analysis tools find the Trojan and reveal how it gets activated.

Requirements

Requirement	Type	Needed for	Availability
dataflow	plugin	recovering the AES register structure	opt-in
hawkeye	plugin	locating the symmetric crypto implementation	opt-in
netlist_preprocessing	plugin	preparing the netlist for HAWKEYE	built by default

dataflow and hawkeye are not built by default. Rebuild HAL with -DBUILD_ALL_PLUGINS=ON if they are missing, see Building HAL, and activate them in the Plugin Manager.

The circuit

The netlist comprises 10,526 gates and 11,441 nets using the LSI 10K gate library. It is completely flat — everything sits in the top_module, with PLAINTEXT, KEY, and CIPHERTEXT as 128 bit ports.

When opening the project be warned that rendering the entire netlist (e.g. by double clicking on the top module) will take a long time. It might be interesting though to have a look at the overwhelming number of gates, but it doesn't reveal the functionality of the circuit nor whether something is wrong with it. This is the point of the exercise: at this size, looking at the graph is not an analysis technique.

Recovering the register structure

The first tool that is needed is the dataflow plugin. Please go to the Plugin Manager (main menu > Utilities) and verify that the dataflow plugin has been activated. If not, enable it and restart HAL.

There are two ways to invoke the dataflow analysis:

GUI: Open the dataflow settings form in main menu > Plugins > dataflow. Set the expected register width to 128, select an existing output directory for the results, and tick the checkbox to create a dot graph.

Script: The project comprises a Python script named find_aes128_register.py in its py/ folder, available from the Python Editor. Running this script produces the same results, writing them into a dataflow subfolder of HAL's working directory. Any modification of parameters (e.g. a different output directory) requires editing the script:

config = dataflow.Configuration(netlist)
config = config.with_flip_flops()
config.expected_sizes = [128]
res = dataflow.analyze(config)

res.write_dot(dataflow_outdir + "/graph.dot")
res.create_modules()

Telling the analysis that we expect 128 bit registers (expected_sizes) biases the grouping towards register candidates of that width — a reasonable assumption given that we are looking at AES128. The call to create_modules() writes the recovered registers back into the netlist as modules, so they show up in the Modules Widget and can be folded in the graph view.

Analysis of the dot file

The graph.dot file is a textual representation of the generated graph and must be converted to your favorite graphic format for viewing. You can open it directly with the dot viewer plugin, or convert it on the command line. The following example line generates a graph.png file, but the dot tool is also capable of generating .pdf, .ps, or .svg files.

dot -Tpng -ograph.png graph.dot

Studying how the 128 bit registers are connected reveals immediately their function in the AES encryption circuit. Remember that there exists a round key in the AES encryption scheme which is only dependent on the key input register. The actual encoding is done round by round (register pointing to itself) based on data from the plaintext register and the round key register. Then there is finally the ciphertext output register which does not have any successors.

Since the key is the secret which must not be leaked, we are alerted spotting a direct connection from the key input register to the ciphertext output register within the graph. Further analysis steps are necessary to isolate that connection and to understand how the leaking of the key gets triggered.

Byte-wise pin groups

The py/pin_grouping.py script splits the 128 bit PLAINTEXT, KEY, and CIPHERTEXT ports of the top module into byte-wise pin groups. Byte granularity is the natural view for AES, since its S-box, ShiftRows, and MixColumns all operate on bytes — so grouping the ports this way makes everything you do afterwards line up with the algorithm rather than with the netlist's flat bit ordering.

Locating the crypto core with HAWKEYE

The dataflow route above finds the AES registers by looking at how flip-flops are grouped and how the resulting registers connect. HAWKEYE comes at the same netlist from a completely different angle: it searches for the structural signature of a symmetric cipher — a state register whose bits feed back into themselves through a round function — without being told that this design is AES, or even that it contains a cipher at all.

That makes it a genuine cross-check. Dataflow analysis tells you that a 128 bit register loops back on itself; HAWKEYE tells you that the logic in that loop looks like a round function, and can go on to identify the S-box inside it. Two independent methods agreeing on the same gates is much stronger evidence than either alone — which matters here, because everything that follows about the Trojan rests on having correctly identified the AES core.

The project ships a ready-to-run py/hawkeye.py that performs the whole sequence.

It starts with a preprocessing step. The flip-flops of this gate library (FD1) have both a Q and an inverted QN output, and a gate driving two nets cannot be handled by the S-box identification. unify_ff_outputs reroutes the inverted outputs through explicit inverter gates, which resolves this — on this netlist it rewires 647 outputs. Skipping it does not prevent HAWKEYE from finding AES, but it produces a stream of errors along the way.

from hal_plugins import netlist_preprocessing

netlist_preprocessing.unify_ff_outputs(netlist)

Detection comes next:

from hal_plugins import hawkeye

config = hawkeye.DetectionConfiguration()
config.control = hawkeye.DetectionConfiguration.Control.CHECK_NETS
config.components = hawkeye.DetectionConfiguration.Components.NONE
config.timeout = 10
config.min_register_size = 10

candidates = hawkeye.detect_candidates(netlist, [config], min_state_size=40)
print(len(candidates), "register candidates")

Each candidate is a suspected cipher state register. Compare the gates it contains against the registers create_modules() produced earlier — for the AES round state, the two should largely agree.

To get at the round function itself, turn the register candidates into round candidates. This copies the state registers and the combinational logic between them into a separate netlist, so you can analyze the round function in isolation:

round_candidates = []

for c in candidates:
    round_candidates.append(hawkeye.RoundCandidate.from_register_candidate(c))

From there HAWKEYE searches the round function for known S-boxes, matching against a database. HAL ships one containing the AES S-box, so no setup is needed — the script locates it automatically in your build directory:

sbox_candidates = hawkeye.locate_sboxes(round_candidate)

identified = ""
for sbox_candidate in sbox_candidates:
    identified = hawkeye.identify_sbox(sbox_candidate, sbox_db)
    if identified:
        break

The structural search deliberately over-approximates — on this netlist it produces around 2500 S-box candidates — so almost all of them fail to identify and the loop stops at the first that succeeds. Running the script prints:

rerouted 647 inverted flip-flop output(s)
detected 2 state register candidate(s)

candidate 0: 128 bit state register
   2508 S-box candidate(s) to check
   >>> identified S-box: AES

candidate 1: 128 bit state register
   no S-box candidates found

Two 128 bit registers, one of which contains the AES S-box — the other is the key register, which has no round function and therefore no S-box. An identified S-box is about as conclusive as netlist reverse engineering gets: it names the algorithm outright rather than merely suggesting a shape. Getting AES out of this netlist, from nothing but gates and without having told HAWKEYE what to look for, is the point of running it here.

See HAWKEYE for what each detection option does, how to assemble an S-box database, and how to map results in the copied netlist back to the original.