Milp model

The target of this module is to find different kind of trails associated to a cryptanalysis technique by using MILP, e.g. the search for XOR differential trails.

The user is asked to use one of the following MILP solver, some need to be installed and integrated to sage beforehand. Available MILP solvers are:

The default choice is GLPK.

class MilpModel(cipher, n_window_heuristic=None, verbose=False)

Bases: object

Build MILP models for ciphers using Cipher.

property binary_variable
property cipher
property cipher_id
fix_variables_value_constraints(fixed_variables=[])

Return a list of constraints that fix the input variables to a specific value.

INPUT:

  • fixed_variables – list (default: []); dictionaries containing the variables to be fixed in standard format

See also

set_fixed_variables()

EXAMPLES:

sage: from claasp.ciphers.block_ciphers.simon_block_cipher import SimonBlockCipher
sage: from claasp.cipher_modules.models.milp.milp_model import MilpModel
sage: simon = SimonBlockCipher(block_bit_size=32, key_bit_size=64, number_of_rounds=2)
sage: milp = MilpModel(simon)
sage: milp.init_model_in_sage_milp_class()
sage: fixed_variables = [{
....:    'component_id': 'plaintext',
....:    'constraint_type': 'equal',
....:    'bit_positions': [0, 1, 2, 3],
....:    'bit_values': [1, 0, 1, 1]
....: }, {
....:    'component_id': 'cipher_output_1_8',
....:    'constraint_type': 'not_equal',
....:    'bit_positions': [0, 1, 2, 3],
....:    'bit_values': [1, 1, 1, 0]
....: }]
sage: constraints = milp.fix_variables_value_constraints(fixed_variables)
sage: constraints
[x_0 == 1,
 x_1 == 0,
 x_2 == 1,
 x_3 == 1,
 x_4 == 1 - x_5,
 x_6 == 1 - x_7,
 x_8 == 1 - x_9,
 x_10 == x_11,
 1 <= x_4 + x_6 + x_8 + x_10]
init_model_in_sage_milp_class(solver_name='GLPK')

Initialize a MILP instance from the build-in sage class.

INPUT:

  • solver_name – string; the solver to call

EXAMPLES:

sage: from claasp.ciphers.block_ciphers.speck_block_cipher import SpeckBlockCipher
sage: from claasp.cipher_modules.models.milp.milp_model import MilpModel
sage: speck = SpeckBlockCipher(block_bit_size=32, key_bit_size=64, number_of_rounds=2)
sage: milp = MilpModel(speck)
sage: milp.init_model_in_sage_milp_class()
sage: milp._model
Mixed Integer Program (no objective, 0 variables, 0 constraints)
property integer_variable
property intermediate_output_names
property model
property model_constraints

Return the model specified by model_type.

INPUT:

  • model_type – string; the model to retrieve

EXAMPLES:

sage: from claasp.ciphers.block_ciphers.speck_block_cipher import SpeckBlockCipher
sage: from claasp.cipher_modules.models.milp.milp_model import MilpModel
sage: speck = SpeckBlockCipher(number_of_rounds=4)
sage: milp = MilpModel(speck)
sage: milp.model_constraints
Traceback (most recent call last):
...
ValueError: No model generated
property non_linear_component_id
solve(model_type, solver_name='GLPK', external_solver_name=None)

Return the solution of the model.

INPUT:

  • model_type – string; the model to solve

  • solver_name – string (default: GLPK); the solver to call when building the internal Sagemath MILP model. If no external solver is specified, solver_name will also be used to solve the model.

  • external_solver_name – string (default: None); if specified, the library will write the internal Sagemath MILP model as a .lp file and solve it outside of Sagemath, using the external solver.

EXAMPLES:

sage: from claasp.ciphers.block_ciphers.speck_block_cipher import SpeckBlockCipher
sage: from claasp.cipher_modules.models.milp.milp_models.milp_xor_differential_model import MilpXorDifferentialModel
sage: speck = SpeckBlockCipher(number_of_rounds=4)
sage: milp = MilpXorDifferentialModel(speck)
sage: milp.init_model_in_sage_milp_class()
sage: milp.add_constraints_to_build_in_sage_milp_class()
...
sage: solution = milp.solve("xor_differential") # random
solver_names(verbose=False)
weight_constraints(weight, weight_precision=2)

Return a list of variables and a list of constraints that fix the total weight to a specific value.

INPUT:

  • weight – integer; the total weight. If negative, no constraints on the weight is added

  • weight_precision – integer (default: 2); the number of decimals to use when rounding the weight of the trail.

EXAMPLES:

sage: from claasp.ciphers.block_ciphers.simon_block_cipher import SimonBlockCipher
sage: from claasp.cipher_modules.models.milp.milp_model import MilpModel
sage: simon = SimonBlockCipher(block_bit_size=32, key_bit_size=64, number_of_rounds=2)
sage: milp = MilpModel(simon)
sage: milp.init_model_in_sage_milp_class()
sage: variables, constraints = milp.weight_constraints(10)
sage: variables
[('p[probability]', x_0)]
sage: constraints
[x_0 == 1000]
get_independent_input_output_variables(component)

Return a list of 2 lists containing the name of each input/output bit.

The bit in position 0 of those lists corresponds to the MSB.

INPUT:

  • component – Component object; component in cipher

EXAMPLES:

sage: from claasp.ciphers.block_ciphers.speck_block_cipher import SpeckBlockCipher
sage: from claasp.cipher_modules.models.milp.milp_model import get_independent_input_output_variables
sage: speck = SpeckBlockCipher(block_bit_size=32, key_bit_size=64, number_of_rounds=2)
sage: component = speck.get_component_from_id("xor_1_10")
sage: l = get_independent_input_output_variables(component)
sage: l[0]
 ['xor_1_10_0_i',
 'xor_1_10_1_i',
 ...
 'xor_1_10_30_i',
 'xor_1_10_31_i']
sage: l[1]
['xor_1_10_0_o',
 'xor_1_10_1_o',
 ...
 'xor_1_10_14_o',
 'xor_1_10_15_o']
get_input_output_variables(component)

Return a list of 2 lists containing the name of each input/output bit.

The bit in position 0 of those lists corresponds to the MSB.

INPUT:

  • component – Component object; component in cipher

EXAMPLES:

sage: from claasp.ciphers.block_ciphers.speck_block_cipher import SpeckBlockCipher
sage: from claasp.cipher_modules.models.milp.milp_model import get_input_output_variables
sage: speck = SpeckBlockCipher(block_bit_size=32, key_bit_size=64, number_of_rounds=2)
sage: component = speck.get_component_from_id("rot_0_0")
sage: l = get_input_output_variables(component)
sage: l[0]
['plaintext_0',
'plaintext_1',
'plaintext_2',
...
'plaintext_13',
'plaintext_14',
'plaintext_15']
sage: l[1]
['rot_0_0_0',
'rot_0_0_1',
'rot_0_0_2',
...
'rot_0_0_13',
'rot_0_0_14',
'rot_0_0_15']