A candidate for a symmetric cryptographic implementation within a netlist. More...

#include </home/runner/work/hal/hal/plugins/hawkeye/include/hawkeye/cipher_candidate.h>

Collaboration diagram for hal::hawkeye::CipherCandidate:

Public Member Functions
	CipherCandidate ()=default

	~CipherCandidate ()=default

	CipherCandidate (const std::set< Gate * > &round_reg)
	Construct a round-based candidate, i.e., one whose input and output register are the same. More...

	CipherCandidate (const std::set< Gate * > &in_reg, const std::set< Gate * > &out_reg)
	Construct a candidate from an input and an output register. The candidate is round-based if both registers are equal. More...

	CipherCandidate (CipherCandidate &&)=default

CipherCandidate &	operator= (CipherCandidate &&)=default

	CipherCandidate (const CipherCandidate &)=delete

CipherCandidate &	operator= (const CipherCandidate &)=delete

Result< std::monostate >	build_round_function ()
	Determine the round function of the candidate, i.e., the combinational logic computing the next state. More...

Result< std::vector< SBox * > >	locate_sboxes ()
	Try to locate S-boxes within the round function of the candidate. More...

void	clear_sboxes ()
	Discard the S-boxes located so far. More...

Result< u32 >	identify_sboxes (const SBoxDatabase &db)
	Try to identify all S-boxes of the candidate by matching them against a database of known S-boxes. More...

Result< std::string >	identify_sbox (const SBox *sbox, const SBoxDatabase &db) const
	Try to identify a single S-box of this candidate by matching it against a database of known S-boxes under affine equivalence. More...

Result< Module * >	create_modules ()
	Write the candidate back into the netlist as a module hierarchy. More...

Netlist *	get_netlist () const
	Get the netlist that the candidate belongs to. More...

u32	get_size () const
	Get the size of the candidate, i.e., the width of its state register. More...

bool	is_round_based () const
	Check whether the candidate is round-based, i.e., whether its input and output register are the same. More...

bool	has_round_function () const
	Check whether the round function of the candidate has been computed, see `build_round_function`. More...

const std::vector< Gate * > &	get_input_reg () const
	Get the input register of the candidate, ordered by gate ID. More...

const std::vector< Gate * > &	get_output_reg () const
	Get the output register of the candidate, ordered by gate ID. Equal to the input register for a round-based candidate. More...

const std::vector< Gate * > &	get_round_logic () const
	Get the combinational logic computing the next state, ordered by gate ID. More...

std::vector< Gate * >	get_gates () const
	Get all gates of the candidate, i.e., its registers together with its round function, ordered by gate ID. More...

std::vector< SBox * >	get_sboxes () const
	Get the S-boxes located within the round function of the candidate. More...

graph_algorithm::NetlistGraph *	get_graph () const
	Get the graph of the round function, in which the gates of the state register are represented by a primary and a shadow vertex so that the feedback of a round-based candidate does not close a cycle. More...

const std::set< Net * > &	get_state_inputs () const
	Get the state inputs of the round function. More...

const std::set< Net * > &	get_control_inputs () const
	Get the control inputs of the round function. More...

const std::set< Net * > &	get_other_inputs () const
	Get the remaining inputs of the round function. More...

const std::set< Net * > &	get_state_outputs () const
	Get the state outputs of the round function. More...

const std::map< Gate , std::set< Gate > > &	get_input_ffs_of_gate () const
	Get a map from each gate of the round function to the input flip-flops it depends on. More...

const std::map< u32, std::set< Gate * > > &	get_longest_distance_to_gate () const
	Get a map from a distance to all gates reachable within at most that distance from any input flip-flop. More...

bool	operator< (const CipherCandidate &rhs) const
	Compare two candidates. More...

bool	operator== (const CipherCandidate &rhs) const
	Check whether two candidates have the same size and the same registers. More...

Static Public Member Functions
static Result< std::vector< CipherCandidate > >	detect (Netlist nl, const std::vector< DetectionConfiguration > &configs, u32 min_state_size=40, const std::vector< Gate > &start_ffs={})
	Attempt to locate candidates for symmetric cryptographic SPN, Feistel, and ARX implementations within a gate-level netlist. More...

static Result< std::string >	identify_sbox (const std::vector< BooleanFunction > &output_functions, const SBoxDatabase &db)
	Try to identify an S-box given as one Boolean function per output bit by matching it against a database of known S-boxes under affine equivalence. More...

Detailed Description

A candidate for a symmetric cryptographic implementation within a netlist.

A candidate is discovered by detect in stages and is filled in as the analysis proceeds: detection only establishes the state register, build_round_function adds the combinational logic computing the next state, and locate_sboxes adds the S-boxes within that logic. Use has_round_function and get_sboxes to find out how far a candidate has been analyzed.

All gates and nets of a candidate belong to the netlist it was detected in, so they can be inspected and grouped into modules directly.

Definition at line 135 of file cipher_candidate.h.

Constructor & Destructor Documentation

◆ CipherCandidate() [1/5]

hal::hawkeye::CipherCandidate::CipherCandidate ( )

default

Referenced by detect().

◆ ~CipherCandidate()

hal::hawkeye::CipherCandidate::~CipherCandidate ( )

default

◆ CipherCandidate() [2/5]

hal::hawkeye::CipherCandidate::CipherCandidate ( const std::set< Gate * > & round_reg )

explicit

Construct a round-based candidate, i.e., one whose input and output register are the same.

Parameters

[in] round_reg - The state register of the candidate.

Definition at line 215 of file cipher_candidate.cpp.

◆ CipherCandidate() [3/5]

hal::hawkeye::CipherCandidate::CipherCandidate	(	const std::set< Gate * > &	in_reg,
		const std::set< Gate * > &	out_reg
	)

Construct a candidate from an input and an output register. The candidate is round-based if both registers are equal.

Parameters

[in]	in_reg	- The input register of the candidate.
[in]	out_reg	- The output register of the candidate.

Definition at line 226 of file cipher_candidate.cpp.

References in_reg, and out_reg.

◆ CipherCandidate() [4/5]

hal::hawkeye::CipherCandidate::CipherCandidate ( CipherCandidate && )

default

◆ CipherCandidate() [5/5]

hal::hawkeye::CipherCandidate::CipherCandidate ( const CipherCandidate & )

delete

The S-boxes are owned through pointers that are handed out to the caller, so copying a candidate would silently produce a second set of S-boxes at different addresses. Candidates are moved, never copied.

Member Function Documentation

◆ build_round_function()

Result< std::monostate > hal::hawkeye::CipherCandidate::build_round_function ( )

Determine the round function of the candidate, i.e., the combinational logic computing the next state.

Determines the state logic between the input and the output register together with the state, control, and other inputs of the candidate, and builds the graph that locate_sboxes operates on. Discards any S-boxes located so far, as they are derived from the round function, which invalidates all pointers previously returned by locate_sboxes and get_sboxes.

Recomputes the round function on every call, which only makes a difference if the netlist changed in the meantime.

Returns: Ok on success, an error otherwise.

Definition at line 661 of file cipher_candidate.cpp.

References clear_sboxes(), hal::combinational, hal::data, ERR, hal::ff, hal::graph_algorithm::NetlistGraph::from_gates(), hal::Endpoint::get_gate(), get_gates(), hal::BasePin< T >::get_type(), and OK.

◆ clear_sboxes()

void hal::hawkeye::CipherCandidate::clear_sboxes ( )

Discard the S-boxes located so far.

Invalidates all pointers previously returned by locate_sboxes and get_sboxes.

Definition at line 349 of file cipher_candidate.cpp.

Referenced by build_round_function(), and hal::PYBIND11_PLUGIN().

◆ create_modules()

Result< Module * > hal::hawkeye::CipherCandidate::create_modules ( )

Write the candidate back into the netlist as a module hierarchy.

Creates one module holding the entire candidate, a submodule holding its state register, and one submodule per identified S-box holding its combinational gates. S-boxes that were not identified are skipped, as are identified S-boxes that overlap an S-box module already created, since a gate belongs to exactly one module. Every skipped S-box is reported to the log.

Returns: The module holding the candidate on success, an error otherwise.

Definition at line 1208 of file cipher_candidate.cpp.

References hal::Netlist::create_module(), ERR, get_gates(), hal::Netlist::get_top_module(), hal::hawkeye::identified, log_info, and OK.

◆ detect()

Result< std::vector< CipherCandidate > > hal::hawkeye::CipherCandidate::detect	(	Netlist *	nl,
		const std::vector< DetectionConfiguration > &	configs,
		u32	min_state_size = `40`,
		const std::vector< Gate * > &	start_ffs = `{}`
	)

static

Attempt to locate candidates for symmetric cryptographic SPN, Feistel, and ARX implementations within a gate-level netlist.

Operates on an abstraction of the netlist that holds only the flip-flops as vertices and their connections through combinational logic as edges. Computes the k-neighborhood of every flip-flop for k = 1, ..., config.timeout and stops once the size of the neighborhood saturates, at which point a candidate is created if the neighborhood is larger than config.min_register_size. Depending on the config, further criteria narrow down the search, see DetectionConfiguration::Control and DetectionConfiguration::Components. The candidates found are then reduced by discarding those smaller than min_state_size as well as those that fully contain a smaller candidate.

The returned candidates only know their state register, call build_round_function on a candidate to analyze it further.

Parameters

[in]	nl	- The netlist to operate on.
[in]	configs	- The configurations of the detection approaches to be executed one after another on each start flip-flop.
[in]	min_state_size	- The minimum size of a candidate to be considered a cryptographic state register. Defaults to `40`.
[in]	start_ffs	- The flip-flops to analyze. Defaults to an empty vector, i.e., all flip-flops of the netlist are analyzed.

Returns: The candidates on success, an error otherwise.

Definition at line 317 of file candidate_search.cpp.

References hal::hawkeye::DetectionConfiguration::CHECK_FF, hal::hawkeye::DetectionConfiguration::CHECK_NETS, hal::hawkeye::DetectionConfiguration::CHECK_PINS, hal::hawkeye::DetectionConfiguration::CHECK_SCC, hal::hawkeye::DetectionConfiguration::CHECK_TYPE, CipherCandidate(), ERR, hal::ff, hal::graph_algorithm::NetlistGraph::from_netlist_no_edges(), hal::Netlist::get_gate_library(), hal::Netlist::get_gates(), hal::Gate::get_id(), hal::Gate::get_type(), in_reg, log_info, hal::hawkeye::DetectionConfiguration::NONE, OK, out_reg, and size.

Referenced by hal::PYBIND11_PLUGIN().

◆ get_control_inputs()

const std::set< Net * > & hal::hawkeye::CipherCandidate::get_control_inputs ( ) const

Get the control inputs of the round function.

Returns: The control inputs of the candidate.

Definition at line 322 of file cipher_candidate.cpp.

Referenced by hal::PYBIND11_PLUGIN().

◆ get_gates()

std::vector< Gate * > hal::hawkeye::CipherCandidate::get_gates ( ) const

Get all gates of the candidate, i.e., its registers together with its round function, ordered by gate ID.

Returns: The gates of the candidate.

Definition at line 293 of file cipher_candidate.cpp.

Referenced by build_round_function(), create_modules(), locate_sboxes(), and hal::PYBIND11_PLUGIN().

◆ get_graph()

graph_algorithm::NetlistGraph * hal::hawkeye::CipherCandidate::get_graph ( ) const

Get the graph of the round function, in which the gates of the state register are represented by a primary and a shadow vertex so that the feedback of a round-based candidate does not close a cycle.

Returns: The graph of the round function, nullptr if the round function has not been computed yet.

Definition at line 312 of file cipher_candidate.cpp.

◆ get_input_ffs_of_gate()

const std::map< Gate *, std::set< Gate * > > & hal::hawkeye::CipherCandidate::get_input_ffs_of_gate ( ) const

Get a map from each gate of the round function to the input flip-flops it depends on.

Returns: A map from gates to sets of input flip-flops.

Definition at line 337 of file cipher_candidate.cpp.

Referenced by hal::PYBIND11_PLUGIN().

◆ get_input_reg()

const std::vector< Gate * > & hal::hawkeye::CipherCandidate::get_input_reg ( ) const

Get the input register of the candidate, ordered by gate ID.

Returns: The input register of the candidate.

Definition at line 278 of file cipher_candidate.cpp.

Referenced by hal::PYBIND11_PLUGIN().

◆ get_longest_distance_to_gate()

const std::map< u32, std::set< Gate * > > & hal::hawkeye::CipherCandidate::get_longest_distance_to_gate ( ) const

Get a map from a distance to all gates reachable within at most that distance from any input flip-flop.

Returns: A map from longest distance to a set of gates.

Definition at line 343 of file cipher_candidate.cpp.

Referenced by hal::PYBIND11_PLUGIN().

◆ get_netlist()

Netlist * hal::hawkeye::CipherCandidate::get_netlist ( ) const

Get the netlist that the candidate belongs to.

Returns: The netlist of the candidate.

Definition at line 258 of file cipher_candidate.cpp.

Referenced by hal::PYBIND11_PLUGIN().

◆ get_other_inputs()

const std::set< Net * > & hal::hawkeye::CipherCandidate::get_other_inputs ( ) const

Get the remaining inputs of the round function.

Returns: The other inputs of the candidate.

Definition at line 327 of file cipher_candidate.cpp.

Referenced by hal::PYBIND11_PLUGIN().

◆ get_output_reg()

const std::vector< Gate * > & hal::hawkeye::CipherCandidate::get_output_reg ( ) const

Get the output register of the candidate, ordered by gate ID. Equal to the input register for a round-based candidate.

Returns: The output register of the candidate.

Definition at line 283 of file cipher_candidate.cpp.

Referenced by hal::PYBIND11_PLUGIN().

◆ get_round_logic()

const std::vector< Gate * > & hal::hawkeye::CipherCandidate::get_round_logic ( ) const

Get the combinational logic computing the next state, ordered by gate ID.

Returns: The round function of the candidate, empty if it has not been computed yet.

Definition at line 288 of file cipher_candidate.cpp.

Referenced by hal::PYBIND11_PLUGIN().

◆ get_sboxes()

std::vector< SBox * > hal::hawkeye::CipherCandidate::get_sboxes ( ) const

Get the S-boxes located within the round function of the candidate.

Returns: The S-boxes of the candidate, empty if they have not been located yet.

Definition at line 301 of file cipher_candidate.cpp.

Referenced by locate_sboxes(), and hal::PYBIND11_PLUGIN().

◆ get_size()

u32 hal::hawkeye::CipherCandidate::get_size ( ) const

Get the size of the candidate, i.e., the width of its state register.

Returns: The size of the candidate.

Definition at line 263 of file cipher_candidate.cpp.

Referenced by hal::PYBIND11_PLUGIN().

◆ get_state_inputs()

const std::set< Net * > & hal::hawkeye::CipherCandidate::get_state_inputs ( ) const

Get the state inputs of the round function.

Returns: The state inputs of the candidate.

Definition at line 317 of file cipher_candidate.cpp.

Referenced by hal::PYBIND11_PLUGIN().

◆ get_state_outputs()

const std::set< Net * > & hal::hawkeye::CipherCandidate::get_state_outputs ( ) const

Get the state outputs of the round function.

Returns: The state outputs of the candidate.

Definition at line 332 of file cipher_candidate.cpp.

Referenced by hal::PYBIND11_PLUGIN().

◆ has_round_function()

bool hal::hawkeye::CipherCandidate::has_round_function ( ) const

Check whether the round function of the candidate has been computed, see build_round_function.

Returns: true if the round function has been computed, false otherwise.

Definition at line 273 of file cipher_candidate.cpp.

Referenced by hal::PYBIND11_PLUGIN().

◆ identify_sbox() [1/2]

Result< std::string > hal::hawkeye::CipherCandidate::identify_sbox	(	const SBox *	sbox,
		const SBoxDatabase &	db
	)		const

Try to identify a single S-box of this candidate by matching it against a database of known S-boxes under affine equivalence.

Tries every assignment of the control inputs that the S-box reads, as the round function computes the S-box for one of them and something else for the others, and the right one is not known in advance. The remaining inputs are held at 0.

Does not annotate the S-box, use identify_sboxes for that.

Parameters

[in]	sbox	- The S-box to identify. Must be one of the S-boxes of this candidate.
[in]	db	- The database of known S-boxes.

Returns: The name of the S-box on success and an empty string if it is not contained in the database, an error otherwise.

Definition at line 1018 of file cipher_candidate.cpp.

References hal::BooleanFunction::Const(), ERR, hal::BooleanFunctionNetDecorator::get_boolean_variable_name(), hal::hawkeye::SBox::get_combinational_gates(), hal::BooleanFunctionNetDecorator::get_net_from(), hal::hawkeye::SBox::input_gates, log_info, OK, and hal::hawkeye::SBox::output_gates.

Referenced by identify_sboxes(), and hal::PYBIND11_PLUGIN().

◆ identify_sbox() [2/2]

Result< std::string > hal::hawkeye::CipherCandidate::identify_sbox	(	const std::vector< BooleanFunction > &	output_functions,
		const SBoxDatabase &	db
	)

static

Try to identify an S-box given as one Boolean function per output bit by matching it against a database of known S-boxes under affine equivalence.

Evaluates the Boolean functions into a truth table and looks that up in the database, so it works on functions that do not come from a netlist at all. Every variable occurring in them is taken as an input bit of the S-box, so substitute anything that is not one beforehand.

Parameters

[in]	output_functions	- The Boolean functions of the S-box, one per output bit. Their order does not matter, as affine equivalence absorbs a permutation of the output bits.
[in]	db	- The database of known S-boxes.

Returns: The name of the S-box on success and an empty string if it is not contained in the database, an error otherwise.

Definition at line 1163 of file cipher_candidate.cpp.

References ERR.

◆ identify_sboxes()

Result< u32 > hal::hawkeye::CipherCandidate::identify_sboxes ( const SBoxDatabase & db )

Try to identify all S-boxes of the candidate by matching them against a database of known S-boxes.

Annotates every S-box with the outcome, see SBox::status and SBox::identified_as. An S-box that is not contained in the database is not an error.

Since the exact outputs of an S-box are not known in advance, locate_sboxes produces many variants of the same S-box that differ only in which of the surplus gates are taken as its outputs but all read the same input flip-flops. Variants are therefore identified as a group, and the group is left as soon as one of them matches, marking the remaining ones superseded. This is where most of the runtime would otherwise go, as identifying an S-box costs far more than locating it.

Parameters

[in] db - The database of known S-boxes.

Returns: The number of identified S-boxes on success, an error otherwise.

Definition at line 956 of file cipher_candidate.cpp.

References ERR, hal::hawkeye::identified, identify_sbox(), log_info, OK, hal::hawkeye::superseded, and hal::hawkeye::unidentified.

◆ is_round_based()

bool hal::hawkeye::CipherCandidate::is_round_based ( ) const

Check whether the candidate is round-based, i.e., whether its input and output register are the same.

Returns: true if the candidate is round-based, false if it is pipelined.

Definition at line 268 of file cipher_candidate.cpp.

Referenced by hal::PYBIND11_PLUGIN().

◆ locate_sboxes()

Result< std::vector< SBox * > > hal::hawkeye::CipherCandidate::locate_sboxes ( )

Try to locate S-boxes within the round function of the candidate.

Computes an initial set of connected components within the round function. If these components are reasonably small and their input and output sizes match, they are turned into S-boxes right away. Otherwise, iteratively considers more combinational gates starting from the components' input gates and searches for sub-components.

Returns the S-boxes located by an earlier call unchanged instead of locating them again, so the returned pointers stay valid. Call clear_sboxes to locate them anew.

Returns: The S-boxes of the candidate on success, an error otherwise.

Definition at line 354 of file cipher_candidate.cpp.

References hal::c_inverter, ERR, hal::ff, hal::graph_algorithm::get_connected_components(), get_gates(), get_sboxes(), hal::graph_algorithm::get_subgraph(), log_info, and OK.

◆ operator<()

bool hal::hawkeye::CipherCandidate::operator< ( const CipherCandidate & rhs ) const

Compare two candidates.

Larger candidates come first, as reducing a set of candidates relies on a candidate being visited before the smaller candidates that it may contain. Ties are broken by the gate IDs of the registers so that the order does not depend on where the gates of the netlist happen to be allocated.

Parameters

[in] rhs - The candidate to compare against.

Returns: true if this candidate is ordered before rhs, false otherwise.

Definition at line 237 of file cipher_candidate.cpp.

◆ operator=() [1/2]

CipherCandidate& hal::hawkeye::CipherCandidate::operator= ( CipherCandidate && )

default

◆ operator=() [2/2]

CipherCandidate& hal::hawkeye::CipherCandidate::operator= ( const CipherCandidate & )

delete

◆ operator==()

bool hal::hawkeye::CipherCandidate::operator== ( const CipherCandidate & rhs ) const

Check whether two candidates have the same size and the same registers.

Parameters

[in] rhs - The candidate to compare against.

Returns: true if both candidates are equal, false otherwise.

Definition at line 253 of file cipher_candidate.cpp.

The documentation for this class was generated from the following files:

plugins/hawkeye/include/hawkeye/cipher_candidate.h
plugins/hawkeye/src/candidate_search.cpp
plugins/hawkeye/src/cipher_candidate.cpp

Public Member Functions

Static Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ CipherCandidate() [1/5]

◆ ~CipherCandidate()

◆ CipherCandidate() [2/5]

◆ CipherCandidate() [3/5]

◆ CipherCandidate() [4/5]

◆ CipherCandidate() [5/5]

Member Function Documentation

◆ build_round_function()

◆ clear_sboxes()

◆ create_modules()

◆ detect()

◆ get_control_inputs()

◆ get_gates()

◆ get_graph()

◆ get_input_ffs_of_gate()

◆ get_input_reg()

◆ get_longest_distance_to_gate()

◆ get_netlist()

◆ get_other_inputs()

◆ get_output_reg()

◆ get_round_logic()

◆ get_sboxes()

◆ get_size()

◆ get_state_inputs()

◆ get_state_outputs()

◆ has_round_function()

◆ identify_sbox() [1/2]

◆ identify_sbox() [2/2]

◆ identify_sboxes()

◆ is_round_based()

◆ locate_sboxes()

◆ operator<()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator==()