Skip to content

HAWKEYE

Jump to bottom
SJulianS edited this page Jun 4, 2024 · 15 revisions

HAWKEYE is a tool to automatically locate implementations of symmetric cryptographic primitives within gate-level netlists. It was developed as part of a publication titled "HAWKEYE - Recovering Symmetric Cryptography From Hardware Circuits" that will be presented at CRYPTO'24. Currently, HAWKEYE is designed to find round-based and pipelined implementations of SPN, ARX and Feistel ciphers. It is not particularly well suited for shift-register-based ciphers and implementations protected against side-channel attacks, although it might get lucky at times.

Prerequisites and Preprocessing

For HAWKEYE to be effective, all gate types used by the netlist under analysis must be properly annotated within the gate library. In particular, each gate must feature

  • Boolean functions describing its outputs (combinational gates only)
  • one or more annotated GateTypeProperty tags for each gate type
  • a correctly assigned PinType for each pin, particularly those of flip-flops

As HAWKEYE cannot currently handle combinational gates with multiple outputs, such gates must be split into two or more separate logic gates before analysis takes place. For example, Xilinx 7-series FPGAs feature LUT6_2 gates that can implement a LUT5 alongside a LUT6. Before running HAWKEYE, we need to split these LUTs up using the split_luts function from the xilinx_toolbox plugin. Furthermore, we remove fan-in endpoints from LUTs if they do not contribute to their implemented Boolean function to aid structural analysis using remove_unused_lut_inputs from the netlist_preprocessing plugin.

from hal_plugins import xilinx_toolbox
from hal_plugins import netlist_preprocessing

xilinx_toolbox.split_luts(netlist)
netlist_preprocessing.NetlistPreprocessingPlugin.remove_unused_lut_inputs(netlist)

Independent of whether an ASIC or FPGA netlist is analyzed, we recommend removing buffer gates by calling remove_buffers to again support structural analysis. Furthermore, some gate libraries feature flip-flops that come with two outputs, one carrying the inverted signal of the other. Here, we recommend using unify_ff_outputs, which will reconnect the inverted flip-flop output to the non-inverted one after inserting an additional inverter gate. This way, the inversion of the output is moved into combinational logic, which allows HAWKEYE to properly deal with it.

netlist_preprocessing.NetlistPreprocessingPlugin.remove_buffers(netlist)
netlist_preprocessing.NetlistPreprocessingPlugin.unify_ff_outputs(netlist)

Additional preprocessing steps may be necessary depending on the netlist-under-analysis. Sometimes, it may also make sense to break LUTs up into primitives combinational gates by decomposing or resynthesizing the respective LUTs. This could aid the localization of S-boxes in particular.

Detecting Candidates for State Registers

To identify candidates for state registers of pipelined or round-based implementations of symmetric ciphers, HAWKEYE converts the input netlist into a flip-flop graph, that is, a graph containing a vertex for every flip-flop in the netlist and an edge between two vertices only if the respective flip-flops are connected through combinational logic. This graph can be further refined by only adding edges if two connected flip-flops are of the same type or are controlled by the same input pins or nets.

HAWKEYE then computes the k-th neighborhood of every flip-flop for k=1, ..., timeout (with timeout defaulting to 10) and outputs a candidate if two successive neighborhoods of the same flip-flop are of equal size (and are larger than min_register_size), that is the i-th neighborhood has the same size as the (i+1)-th neighborhood. Together with the check whether two connected flip-flops feature the same control nets, this makes up Method 1 from the paper.

from hal_plugins import hawkeye

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

candidates = hawkeye.detect_candidates(netlist, [c_nets], min_state_size=40)

Sometimes it helps to relax the control configuration to Control.CHECK_PINS instead of Control.CHECK_NETS, which will just check whether the same pins of flip-flops are used, but they no longer have to be connected to the same control nets. This can also be done in combination with Control.CHECK_NETS.

from hal_plugins import hawkeye

c_nets = hawkeye.DetectionConfiguration()
c_nets.control = hawkeye.DetectionConfiguration.Control.CHECK_NETS
...

c_pins = hawkeye.DetectionConfiguration()
c_pins.control = hawkeye.DetectionConfiguration.Control.CHECK_PINS
...

candidates = hawkeye.detect_candidates(netlist, [c_nets, c_pins], min_state_size=40)

If flip-flops are controlled synchronously, their control inputs are often moved into combinational logic, which makes it harder to differentiate between flip-flops that do not belong to the same register. In the paper, we observed this being the case for some of our ASIC benchmarks. To address this issue, HAWKEYE supports the detection of strongly connected components (SCCs) within the neighborhoods while they are computed to refine results. As the flip-flops of a round-based implementation usually form an SCC, this approach ensures that only the state flip-flops end up in the state register candidate. In the paper, this refinement is referred to as Method 2.

Additionally, some gate libraries feature functionally equivalent gate types that only differ in their electrical properties. As this hampers functional analysis, HAWKEYE allows to specify such gates such that type checks on these gates allow for them to be used interchangeably.

from hal_plugins import hawkeye

config = hawkeye.DetectionConfiguration()
config.control = hawkeye.DetectionConfiguration.Control.CHECK_TYPE
config.components = hawkeye.DetectionConfiguration.Components.CHECK_SCC
config.equivalent_types = [["FD1", "FD1P"]]
config.timeout = 10
config.min_register_size = 10

candidates = hawkeye.detect_candidates(netlist, [config], min_state_size=40)

TODO: how to operate on candidates (get size, input/output registers)

Isolate Round Function

TODO: round candidate holds partial copy of netlist, so not the same gates in registers and state logic as in original one

round_candidates = list()

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

Locate and Identify S-Boxes

sbox_db = hawkeye.SBoxDatabase.from_file(PATH_TO_SBOX_DB)

for rc in round_candidates:
    sbox_candidates = hawkeye.locate_sboxes(rc)
    sbox_name = ""

    for sc in sbox_candidates:
        sbox_name = hawkeye.identify_sbox(sc, sbox_db)
        if sbox_name != "":
            break

    print(sbox_name)

Clone this wiki locally