Skip to content

HAWKEYE

Jump to bottom
SJulianS edited this page Jul 9, 2024 · 14 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)

Once state register candidates have been discovered, they can be passed on to HAWKEYE's round function analysis to, e.g., search for S-boxes. However, using get_in_reg() and get_out_reg(), the input and output registers associated with the register candidate can be retrieved, e.g., to create respective modules in the netlist.

Isolate Round Function

To isolate the round function for further analysis, the register candidates can be passed to RoundCandidate.from_register_candidate() to construct a round function candidate. This will first create a partial deep copy of the original netlist under analysis, with the copy comprising only the gates of the state input and output registers as well as the combinational logic in between. In case of a round-based implementation, the input register is often identical to the output register, which would require handling of some edge cases further down the line. Hence, while copying the partial netlist, HAWKEYE also duplicates this register and reconnects the round function logic to ensure that input and output register are distinct.

round_candidates = list()

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

While creating a round function candidate, HAWKEYE will also annotate its state input and output nets, any control nets, and other nets (e.g., plaintext and (round)key) feeding into the combinational round function logic. Please note that, while these nets can be retrieved using get_state_inputs(), get_state_outputs(), get_control_inputs(), and get_other_inputs(), they will be from the copied netlist and additional steps need to be taken to map them to the original netlist. To this end, the gate and net IDs can be used, as they should be identical to the ones used in the original netlist (with the exception of the output register in case of a round-based implementation, since it is a duplicate of the input register).

Locate and Identify S-Boxes

Once the combinational logic of the round function has been isolated and its inputs have been annotated, HAWKEYE can be tasked to search for known S-boxes within the round function candidate. To this end, it first needs to load or create a database of known S-boxes. This database comprises linear representatives of many S-boxes of up to 8 bits, against which HAWKEYE will later match S-box candidates extracted from logic (under affine equivalence).

After the database has been set up, HAWKEYE can search for S-boxes using structural analysis using locate_sboxes(). This will ideally produce one or more S-box candidates that comprise of input flip-flops and some combinational logic and come with annotated input and output gates. Next, identify_sbox() can be called on each of these candidates to attempt to identify them using functional analysis.

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)

Creating and Editing an S-Box Database

You can also create your own S-box database, e.g., by first creating an empty database and then filling it up with known S-boxes (up to 8 bits). For PRESENT, this could look like shown in the Python code below. Note that you can also save your database to a JSON file and load it just as shown before.

sbox_db = hawkeye.SBoxDatabase()

present_sbox = [0xC,0x5,0x6,0xB,0x9,0x0,0xA,0xD,0x3,0xE,0xF,0x8,0x4,0x7,0x1,0x2]

sbox_db.add("PRESENT", present_sbox)
sbox_db.store(PATH_TO_SBOX_DB)
Clone this wiki locally