Milp xor differential model

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

Bases: MilpModel

add_constraints_to_build_in_sage_milp_class(weight=- 1, weight_precision=2, fixed_variables=[])

Take the constraints contained in self._model_constraints and add them to the build-in sage class.

INPUT:

  • model_type – string; the model to solve

  • weight – integer (default: -1); 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.

  • 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.speck_block_cipher import SpeckBlockCipher
sage: from claasp.cipher_modules.models.milp.milp_models.milp_xor_differential_model import MilpXorDifferentialModel
sage: speck = SpeckBlockCipher(block_bit_size=32, key_bit_size=64, number_of_rounds=2)
sage: milp = MilpXorDifferentialModel(speck)
sage: milp.init_model_in_sage_milp_class()
sage: milp.add_constraints_to_build_in_sage_milp_class()
...
sage: mip = milp._model
sage: mip.number_of_variables()
532
property binary_variable
build_xor_differential_trail_model(weight=- 1, fixed_variables=[])

Build the model for the search of XOR differential trails.

INPUT:

  • weight – integer (default: -1); a specific weight. If set to non-negative integer, fixes the XOR trail weight

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

See also

set_fixed_variables().

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=22)
sage: milp = MilpXorDifferentialModel(speck)
sage: milp.init_model_in_sage_milp_class()
sage: milp.build_xor_differential_trail_model()
...
property cipher
property cipher_id
exclude_variables_value_constraints(fixed_variables=[])

Return constraints list that ensures that at least one of the specified variables is not equal to fixed values.

INPUT:

  • fixed_variables – list (default: []); 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_models.milp_xor_differential_model import MilpXorDifferentialModel
sage: simon = SimonBlockCipher(block_bit_size=32, key_bit_size=64, number_of_rounds=2)
sage: milp = MilpXorDifferentialModel(simon)
sage: milp.init_model_in_sage_milp_class()
sage: fixed_variables = [{
....:    'component_id': 'plaintext',
....:    'constraint_type': 'not_equal',
....:    'bit_positions': [0, 1, 2, 3],
....:    'bit_values': [1, 0, 1, 1]
....: }, {
....:    'component_id': 'cipher_output_2_12',
....:    'constraint_type': 'not_equal',
....:    'bit_positions': [0, 1, 2, 3],
....:    'bit_values': [1, 1, 1, 0]
....: }]
sage: constraints = milp.exclude_variables_value_constraints(fixed_variables)
sage: constraints
[x_0 == 1 - x_1,
 x_2 == x_3,
 x_4 == 1 - x_5,
 x_6 == 1 - x_7,
 x_8 == 1 - x_9,
 x_10 == 1 - x_11,
 x_12 == 1 - x_13,
 x_14 == x_15,
 1 <= x_0 + x_2 + x_4 + x_6 + x_8 + x_10 + x_12 + x_14]
find_all_xor_differential_trails_with_fixed_weight(fixed_weight, fixed_values=[], weight_precision=2, solver_name='GLPK', external_solver_name=None)

Return all the XOR differential trails with weight equal to fixed_weight as a list in standard format. By default, the search is set in the single-key setting.

See also

convert_solver_solution_to_dictionary()

Note

This method should be run after you have found the solution with the find_lowest_weight_xor_differential_trail() method.

INPUT:

  • fixed_weight – integer; the weight found using find_lowest_weight_xor_differential_trail()

  • fixed_values – list (default: []); each dictionary contains variables values whose output need to be fixed

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

  • solver_name – string (default: GLPK); the name of the solver (if needed)

EXAMPLES:

# single-key setting
sage: from claasp.cipher_modules.models.milp.milp_models.milp_xor_differential_model import MilpXorDifferentialModel
sage: from claasp.ciphers.block_ciphers.speck_block_cipher import SpeckBlockCipher
sage: speck = SpeckBlockCipher(number_of_rounds=5)
sage: milp = MilpXorDifferentialModel(speck)
sage: trails = milp.find_all_xor_differential_trails_with_fixed_weight(9) # long # doctest: +SKIP
...
sage: len(trails) # doctest: +SKIP
2

# related-key setting
sage: from claasp.cipher_modules.models.utils import set_fixed_variables
sage: from claasp.cipher_modules.models.milp.milp_models.milp_xor_differential_model import MilpXorDifferentialModel
sage: from claasp.ciphers.block_ciphers.speck_block_cipher import SpeckBlockCipher
sage: speck = SpeckBlockCipher(number_of_rounds=5)
sage: milp = MilpXorDifferentialModel(speck)
sage: key = set_fixed_variables('key', 'not_equal', list(range(64)), [0] * 64)
sage: trails = milp.find_all_xor_differential_trails_with_fixed_weight(2, fixed_values=[key])#long# doctest: +SKIP
...
sage: len(trails) # doctest: +SKIP
2
find_all_xor_differential_trails_with_weight_at_most(min_weight, max_weight, fixed_values=[], weight_precision=2, solver_name='GLPK', external_solver_name=None)

Return all XOR differential trails with weight greater than min_weight and lower/equal to max_weight. By default, the search is set in the single-key setting. The value returned is a list of solutions in standard format.

See also

convert_solver_solution_to_dictionary().

Note

Note that the search will start with min_weight and should end when the weight reaches a value greater than the maximum cipher inputs bit-size. Fix a convenient max_weight value.

INPUT:

  • min_weight – integer; the weight found using find_lowest_weight_xor_differential_trail().

  • max_weight – integer; the upper bound for the weight.

  • fixed_values – list (default: []); each dictionary contains variables values whose output need to be fixed

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

  • solver_name – string (default: GLPK); the name of the solver (if needed)

  • 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:

# single-key setting
sage: from claasp.cipher_modules.models.milp.milp_models.milp_xor_differential_model import MilpXorDifferentialModel
sage: from claasp.ciphers.block_ciphers.speck_block_cipher import SpeckBlockCipher
sage: speck = SpeckBlockCipher(number_of_rounds=5)
sage: milp = MilpXorDifferentialModel(speck)
sage: trails = milp.find_all_xor_differential_trails_with_weight_at_most(9, 10) # long #doctest: +SKIP
...
sage: len(trails) #doctest: +SKIP
28

# related-key setting
sage: from claasp.cipher_modules.models.utils import set_fixed_variables
sage: from claasp.cipher_modules.models.milp.milp_models.milp_xor_differential_model import MilpXorDifferentialModel
sage: from claasp.ciphers.block_ciphers.speck_block_cipher import SpeckBlockCipher
sage: speck = SpeckBlockCipher(number_of_rounds=5)
sage: milp = MilpXorDifferentialModel(speck)
sage: key = set_fixed_variables('key', 'not_equal', list(range(64)), [0] * 64)
sage: trails = milp.find_all_xor_differential_trails_with_weight_at_most(2, 3, fixed_values=[key]) # long #doctest: +SKIP
...
sage: len(trails) #doctest: +SKIP
9
find_lowest_weight_xor_differential_trail(fixed_values=[], weight_precision=2, solver_name='GLPK', external_solver_name=False)

Return a XOR differential trail with the lowest weight in standard format, i.e. the solver solution. By default, the search is set in the single-key setting.

See also

convert_solver_solution_to_dictionary()

INPUT:

  • fixed_values – list (default: []); each dictionary contains variables values whose output need to be fixed

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

  • solver_name – string (default: GLPK); the name of the solver (if needed)

  • 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:

# single-key setting
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=5)
sage: milp = MilpXorDifferentialModel(speck)
sage: trail = milp.find_lowest_weight_xor_differential_trail() #doctest: +SKIP
...
sage: trail["total_weight"] #doctest: +SKIP
9.0

# related-key setting
sage: from claasp.cipher_modules.models.utils import set_fixed_variables
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=5)
sage: milp = MilpXorDifferentialModel(speck)
sage: key = set_fixed_variables('key', 'not_equal', list(range(64)), [0] * 64)
sage: trail = milp.find_lowest_weight_xor_differential_trail(fixed_values=[key]) #doctest: +SKIP
...
sage: trail["total_weight"] #doctest: +SKIP
1.0
find_one_xor_differential_trail(fixed_values=[], weight_precision=2, solver_name='GLPK', external_solver_name=None)

Return a XOR differential trail, not necessarily the one with the lowest weight. By default, the search is set in the single-key setting.

INPUT:

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

    format

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

  • solver_name – string (default: GLPK); the solver to call

  • 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.

See also

set_fixed_variables()

EXAMPLES:

# single-key setting
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=5)
sage: milp = MilpXorDifferentialModel(speck)
sage: trail = milp.find_one_xor_differential_trail() # random # doctest: +SKIP

# related-key setting
sage: from claasp.cipher_modules.models.utils import set_fixed_variables
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=5)
sage: milp = MilpXorDifferentialModel(speck)
sage: key = set_fixed_variables('key', 'not_equal', list(range(64)), [0] * 64)
sage: trail = milp.find_one_xor_differential_trail(fixed_values=[key]) # random # doctest: +SKIP
find_one_xor_differential_trail_with_fixed_weight(fixed_weight, fixed_values=[], weight_precision=2, solver_name='GLPK', external_solver_name=None)

Return one XOR differential trail with weight equal to fixed_weight as a list in standard format. By default, the search is set in the single-key setting.

INPUT:

  • fixed_weight – integer; the weight found using find_lowest_weight_xor_differential_trail()

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

    format

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

  • solver_name – string (default: GLPK); the solver to call

  • 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.

See also

set_fixed_variables()

EXAMPLES:

# single-key setting
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=3)
sage: milp = MilpXorDifferentialModel(speck)
sage: trail = milp.find_one_xor_differential_trail_with_fixed_weight(3) # random # doctest: +SKIP
sage: trail['total_weight'] # doctest: +SKIP
3.0

# related-key setting
sage: from claasp.cipher_modules.models.utils import set_fixed_variables
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=3)
sage: milp = MilpXorDifferentialModel(speck)
sage: key = set_fixed_variables('key', 'not_equal', list(range(64)), [0] * 64)
sage: trail = milp.find_one_xor_differential_trail_with_fixed_weight(3, fixed_values=[key]) # random # doctest: +SKIP
sage: trail['total_weight'] # doctest: +SKIP
3.0
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
is_single_key(fixed_values=[])

Return True if key is fixed to 0, False otherwise.

INPUT:

  • fixed_values – list; dictionaries containing each dict contains variables values whose output need to be fixed

EXAMPLES::

sage: from claasp.cipher_modules.models.utils import get_single_key_scenario_format_for_fixed_values 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(block_bit_size=8, key_bit_size=16, number_of_rounds=2) sage: milp = MilpXorDifferentialModel(speck) sage: milp.is_single_key(get_single_key_scenario_format_for_fixed_values(speck)) True

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]
property weight_precision