scalib.attacks.FactorGraph#

class scalib.attacks.FactorGraph(graph_text, tables=None)[source]#

FactorGraph allows to run Soft Analytical Side-Channel Attacks (SASCA).

A SASCA is based on a set of variables, on knowledge of relationships between those variables and information about the values of the variables.

Variables have values in a binary finite field of size nc, and are viewed as bit vectors. Those values are represented as integers in [0, nc). Variables can be qualified as SINGLE or MULTI, which relates to the multiple-execution feature of FactorGraph: when performing a SASCA, it is useful to acquire multiple execution traces. In these executions, some variables stay the same (e.g. an encryption key), and other change (e.g. plaintext, masked variables, etc.). The SINGLE qualifier should be used for variables that remain the same and MULTI for variables that change. FactorGraph will then build a graph where each MULTI variable is replicated n times (once for each execution), as well as all the relationships that relate at least on MULTI variable.

Relationships between variables are bitwise XOR, bitwise AND, bitwise OR, bitiwise negation, modular addition, modular multiplication and lookup table. A lookup table can describe any function that maps a single variable to another variable. Description of nc, the variables, and the relationships is given in a text format specified below.

Finally, variables are of two kinds: the public values and the variables. The public values have a single known value, while variables have an uncertain value modelled as a probability distribution. The SASCA computes these distributions from the relationships encoded by the graph, and from prior information. The prior distributions are by default uniform, but this can be changed.

An attack attempting to recover the secret key byte k is shown below.

>>> # Describe and generate the SASCAGraph
>>> graph_desc = '''
...     # Small unprotected Sbox example
...     NC 256 # Graph over GF(256)
...     TABLE sbox   # Sbox
...     VAR SINGLE k # key (to recover !)
...     PUB MULTI p  # plaintext (known)
...     VAR MULTI x # Sbox input
...     VAR MULTI y # Sbox output (whose leakage is targeted)
...     PROPERTY x = k ^ p   # Key addition
...     PROPERTY y = sbox[x] # Sbox lookup
...     '''
>>> sbox = np.arange(256, dtype=np.uint32) # don't use this S-box ;)
>>> graph = FactorGraph(graph_desc, {"sbox": sbox})
>>> # n is the number of traces for our attack.
>>> n = 2
>>> plaintexts = np.array([0, 1], dtype=np.uint32)
>>> bp = BPState(graph, n, {"p": plaintexts})
>>> y_leakage = np.random.rand(2, 256) # this might come from an LDA
>>> y_leakage = y_leakage / y_leakage.sum(axis=1, keepdims=True)
>>> bp.set_evidence("y",y_leakage)
>>> # Solve graph
>>> bp.bp_loopy(it=3, initialize_states=True)
>>> # Get key distribution and derive key guess
>>> k_distri = bp.get_distribution("k")
>>> key_guess = np.argmax(k_distri)

By running a belief propagation algorithm (see [1]), the distributions on all the variables are updated based on their initial distributions. The SASCAGraph can be solved by using run_bp().

Notes

The graph description format is a text line-oriented format (each line of text is a statement) that describes a set of variables and relationships between those variables. The ordering of the statements is irrelevant and whitespace is irrelevant except for newlines and around keywords. End-of-line comments start with the # symbol. The statements are:

  • NC <nc>: specifies the field size (must be a power of two). There must be one NC statement in the description.

  • PUB SINGLE|MULTI variable_name: declares a public variable. variable_name is an identifier of the variable (allowed characters are letters, digits and underscore). One of the qualifiers SINGLE or MULTI must be given.

  • VAR SINGLE|MULTI variable_name: declares a variables.

  • PROPERTY w = x ^ y ^ z: declares a bitwise XOR property. There can be any number of operands.

  • PROPERTY z = x & y: declares a bitwise AND property.

  • PROPERTY x = t[y]: declares a LOOKUP property (y is the lookup of the table t at index y). No public variable is allowed in this property.

  • PROPERTY x = !y: declares a bitwise NOT property. No public variable is allowed in this property.

  • PROPERTY x = y + z - w: declares a modular sum (+ and - are supported, with arbitrary number of terms).

  • PROPERTY f(x, y, z): declares a “Generic factor” property, f must be

    declared as a GENERIC.

  • TABLE t = [0, 3, 2, 1]`: Declares a table that can be used in a LOOKUP. The values provided in the table must belong to the interval [0, nc). The initialization expression can be omitted from the graph description (e.g. TABLE t) and be given with tables parameter.

  • GENERIC SINGLE|MULTI f: declares a “Generic factor” f. A generic factor

    can be used to define an arbitrary functional relationships between variables. See the docs for GenFactor for more information and examples.

Note: if the MULTI feature doesn’t match your use-case, using only SINGLE variables works (or set the number of execution to 1).

Parameters:

  • graph (string) – The graph description.

  • graph_text (str) –

  • tables (Mapping[str, numpy.typing.NDArray.numpy.uint32] | None) –

Methods

factors()

Return the names of the factors in the graph.

sanity_check(pub_assignment, var_assignment)

Verify that the graph is compatible with example variable assignments.

vars()

Return the names of the variables in the graph.
sanity_check(pub_assignment, var_assignment, factor_assignment=None)[source]#

Verify that the graph is compatible with example variable assignments.

If the graph is not compatible, raise a ValueError.

Parameters:

  • pub_assignment (Mapping[str, int | Sequence[int]]) – For each public variable its value for all test executions.

  • var_assignment (Mapping[str, int | Sequence[int]]) – For each non-public variable its value for all test executions.

  • factor_assignment (Mapping[str, GenFactor | Sequence[GenFactor]] | None) – The probability tables (i.e., GenFactor assignments) for each generic factor.

Return type:

None

vars()[source]#

Return the names of the variables in the graph.

Return type:

Sequence[str]

factors()[source]#

Return the names of the factors in the graph.

Return type:

Sequence[str]