Milp xor linear model

class MilpXorLinearModel(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. It is the negative base-2 logarithm of the total correlation of the trail. 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_linear_model import MilpXorLinearModel
sage: speck = SpeckBlockCipher(block_bit_size=32, key_bit_size=64, number_of_rounds=2)
sage: milp = MilpXorLinearModel(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()
743
property binary_variable
branch_xor_linear_constraints()

Return a list of constraints for branch constraints.

for a 3-way branch, it is a 1-xor: X + Y + Z - 2 dummy >= 0 X + Y + Z <= 2 dummy - X >= 0 dummy - Y >= 0 dummy - Z >= 0

and more generally, for a k-way branch, it is a (k-2)-xor

INPUT:

  • None

EXAMPLES:

sage: from claasp.ciphers.block_ciphers.speck_block_cipher import SpeckBlockCipher
sage: from claasp.cipher_modules.models.milp.milp_models.milp_xor_linear_model import MilpXorLinearModel
sage: speck = SpeckBlockCipher(block_bit_size=32, key_bit_size=64, number_of_rounds=1)
sage: milp = MilpXorLinearModel(speck.remove_key_schedule())
sage: milp.init_model_in_sage_milp_class()
sage: constraints = milp.branch_xor_linear_constraints()
sage: constraints
[x_0 == x_1,
x_2 == x_3,
...
x_316 == x_317,
x_318 == x_319]
build_xor_linear_trail_model(weight=- 1, fixed_variables=[])

Build the linear model.

INPUT:

  • weight – integer (default: -1). By default, the weight corresponds to the negative base-2 logarithm of the correlation of the trail.

  • fixed_variables – list (default: [])

EXAMPLES:

sage: from claasp.ciphers.block_ciphers.speck_block_cipher import SpeckBlockCipher
sage: from claasp.cipher_modules.models.milp.milp_models.milp_xor_linear_model import MilpXorLinearModel
sage: speck = SpeckBlockCipher(number_of_rounds=22)
sage: milp = MilpXorLinearModel(speck)
sage: milp.init_model_in_sage_milp_class()
sage: milp.build_xor_linear_trail_model()
...
property cipher
property cipher_id
exclude_variables_value_xor_linear_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_linear_model import MilpXorLinearModel
sage: simon = SimonBlockCipher(block_bit_size=32, key_bit_size=64, number_of_rounds=2)
sage: milp = MilpXorLinearModel(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_xor_linear_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_linear_trails_with_fixed_weight(fixed_weight, fixed_values=[], weight_precision=2, solver_name='GLPK', external_solver_name=None)

Return all the XOR linear trails with weight equal to fixed_weight as a solutions list in standard format. By default, the search removes the key schedule, if any. By default, the weight corresponds to the negative base-2 logarithm of the correlation of the trail.

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_linear_trail() method.

INPUT:

  • fixed_weight – integer; the weight found using find_lowest_weight_xor_linear_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:

sage: from claasp.cipher_modules.models.milp.milp_models.milp_xor_linear_model import MilpXorLinearModel
sage: from claasp.ciphers.block_ciphers.speck_block_cipher import SpeckBlockCipher
sage: speck = SpeckBlockCipher(block_bit_size=8, key_bit_size=16, number_of_rounds=3)
sage: milp = MilpXorLinearModel(speck)
sage: trails = milp.find_all_xor_linear_trails_with_fixed_weight(1)
...
sage: len(trails)
12

# including the key schedule in the model
sage: from claasp.cipher_modules.models.milp.milp_models.milp_xor_linear_model import MilpXorLinearModel
sage: from claasp.ciphers.block_ciphers.speck_block_cipher import SpeckBlockCipher
sage: from claasp.cipher_modules.models.utils import set_fixed_variables
sage: speck = SpeckBlockCipher(block_bit_size=8, key_bit_size=16, number_of_rounds=4)
sage: milp = MilpXorLinearModel(speck)
sage: key = set_fixed_variables('key', 'not_equal', list(range(16)), [0] * 16)
sage: trails = milp.find_all_xor_linear_trails_with_fixed_weight(2, fixed_values=[key]) # long # doctest: +SKIP
...
sage: len(trails) # doctest: +SKIP
8
find_all_xor_linear_trails_with_weight_at_most(min_weight, max_weight, fixed_values=[], weight_precision=2, solver_name='GLPK', external_solver_name=None)

Return all XOR linear trails with weight greater than min_weight and lower than or equal to max_weight. By default, the search removes the key schedule, if any.

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

sage: from claasp.cipher_modules.models.milp.milp_models.milp_xor_linear_model import MilpXorLinearModel
sage: from claasp.ciphers.block_ciphers.speck_block_cipher import SpeckBlockCipher
sage: speck = SpeckBlockCipher(block_bit_size=8, key_bit_size=16, number_of_rounds=3)
sage: milp = MilpXorLinearModel(speck)
sage: trails = milp.find_all_xor_linear_trails_with_weight_at_most(0,1)
...
sage: len(trails)
13

# including the key schedule in the model
sage: from claasp.cipher_modules.models.milp.milp_models.milp_xor_linear_model import MilpXorLinearModel
sage: from claasp.ciphers.block_ciphers.speck_block_cipher import SpeckBlockCipher
sage: from claasp.cipher_modules.models.utils import set_fixed_variables
sage: speck = SpeckBlockCipher(block_bit_size=8, key_bit_size=16, number_of_rounds=4)
sage: milp = MilpXorLinearModel(speck)
sage: key = set_fixed_variables('key', 'not_equal', list(range(16)), [0] * 16)
sage: trails = milp.find_all_xor_linear_trails_with_weight_at_most(0, 3, fixed_values=[key]) # long # doctest: +SKIP
...
sage: len(trails) # doctest: +SKIP
73
find_lowest_weight_xor_linear_trail(fixed_values=[], weight_precision=2, solver_name='GLPK', external_solver_name=None)

Return a XOR linear trail with the lowest weight in standard format, i.e. the solver solution. By default, the search removes the key schedule, if any. By default, the weight corresponds to the negative base-2 logarithm of the correlation of the trail.

See also

convert_solver_solution_to_dictionary()

verified with https://eprint.iacr.org/2019/019.pdf for Present https://eprint.iacr.org/2016/407.pdf for Speck and https://eprint.iacr.org/2014/747.pdf (page 17) https://eprint.iacr.org/2014/973.pdf for SIMON

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:

# To reproduce the trail of Table 6 from https://eprint.iacr.org/2016/407.pdf run:
sage: from claasp.cipher_modules.models.milp.milp_models.milp_xor_linear_model import MilpXorLinearModel
sage: from claasp.ciphers.block_ciphers.speck_block_cipher import SpeckBlockCipher
sage: from claasp.cipher_modules.models.utils import integer_to_bit_list, set_fixed_variables
sage: speck = SpeckBlockCipher(block_bit_size=32, key_bit_size=64, number_of_rounds=9)
sage: milp = MilpXorLinearModel(speck)
sage: plaintext = set_fixed_variables(component_id='plaintext', constraint_type='equal', bit_positions=range(32), bit_values=integer_to_bit_list(0x03805224, 32, 'big'))
sage: trail = milp.find_lowest_weight_xor_linear_trail(fixed_values=[plaintext])  # doctest: +SKIP
...
sage: trail["total_weight"] # doctest: +SKIP
14.0

# To reproduce the trail of Table 8 from https://eprint.iacr.org/2014/973.pdf run:
sage: from claasp.cipher_modules.models.milp.milp_models.milp_xor_linear_model import MilpXorLinearModel
sage: from claasp.ciphers.block_ciphers.simon_block_cipher import SimonBlockCipher
sage: from claasp.cipher_modules.models.utils import integer_to_bit_list, set_fixed_variables
sage: simon = SimonBlockCipher(block_bit_size=32, key_bit_size=64, number_of_rounds=13)
sage: milp = MilpXorLinearModel(simon)
sage: plaintext = set_fixed_variables(component_id='plaintext', constraint_type='equal', bit_positions=range(32), bit_values=integer_to_bit_list(0x00200000, 32, 'big'))
sage: trail = milp.find_lowest_weight_xor_linear_trail(fixed_values=[plaintext])  # doctest: +SKIP
...
sage: trail["total_weight"] # doctest: +SKIP
18.0

# including the key schedule in the model
sage: from claasp.cipher_modules.models.milp.milp_models.milp_xor_linear_model import MilpXorLinearModel
sage: from claasp.ciphers.block_ciphers.speck_block_cipher import SpeckBlockCipher
sage: from claasp.cipher_modules.models.utils import set_fixed_variables
sage: speck = SpeckBlockCipher(block_bit_size=16, key_bit_size=32, number_of_rounds=4)
sage: milp = MilpXorLinearModel(speck)
sage: key = set_fixed_variables('key', 'not_equal', list(range(32)), [0] * 32)
sage: trail = milp.find_lowest_weight_xor_linear_trail(fixed_values=[key]) # doctest: +SKIP
sage: trail["total_weight"] # doctest: +SKIP
3.0
find_one_xor_linear_trail(fixed_values=[], weight_precision=2, solver_name='GLPK', external_solver_name=None)

Return a XOR linear trail, not necessarily the one with the lowest weight. By default, the search removes the key schedule, if any. By default, the weight corresponds to the negative base-2 logarithm of the correlation of the trail.

INPUT:

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

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

See also

set_fixed_variables()

EXAMPLES:

sage: from claasp.cipher_modules.models.milp.milp_models.milp_xor_linear_model import MilpXorLinearModel
sage: from claasp.ciphers.block_ciphers.speck_block_cipher import SpeckBlockCipher
sage: speck = SpeckBlockCipher(block_bit_size=32, key_bit_size=64, number_of_rounds=2)
sage: milp = MilpXorLinearModel(speck)
sage: trail = milp.find_one_xor_linear_trail() # random

# including the key schedule in the model
sage: from claasp.cipher_modules.models.milp.milp_models.milp_xor_linear_model import MilpXorLinearModel
sage: from claasp.ciphers.block_ciphers.speck_block_cipher import SpeckBlockCipher
sage: from claasp.cipher_modules.models.utils import set_fixed_variables
sage: speck = SpeckBlockCipher(block_bit_size=32, key_bit_size=64, number_of_rounds=2)
sage: milp = MilpXorLinearModel(speck)
sage: key = set_fixed_variables('key', 'not_equal', list(range(32)), [0] * 32)
sage: trail = milp.find_one_xor_linear_trail(fixed_values=[key]) # random
find_one_xor_linear_trail_with_fixed_weight(fixed_weight, fixed_values=[], weight_precision=2, solver_name='GLPK', external_solver_name=None)

Return one XOR linear trail with weight equal to fixed_weight as a list in standard format. By default, the search removes the key schedule, if any. By default, the weight corresponds to the negative base-2 logarithm of the correlation of the trail.

INPUT:

  • fixed_weight – integer; the weight found using find_lowest_weight_xor_linear_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 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.

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_linear_model import MilpXorLinearModel
sage: speck = SpeckBlockCipher(block_bit_size=32, key_bit_size=64, number_of_rounds=2)
sage: milp = MilpXorLinearModel(speck)
sage: trail = milp.find_one_xor_linear_trail_with_fixed_weight(6) # random
...
sage: trail['total_weight']
6.0

sage: from claasp.cipher_modules.models.milp.milp_models.milp_xor_linear_model import MilpXorLinearModel
sage: from claasp.ciphers.block_ciphers.speck_block_cipher import SpeckBlockCipher
sage: from claasp.cipher_modules.models.utils import set_fixed_variables
sage: speck = SpeckBlockCipher(block_bit_size=8, key_bit_size=16, number_of_rounds=4)
sage: milp = MilpXorLinearModel(speck)
sage: key = set_fixed_variables('key', 'not_equal', list(range(16)), [0] * 16)
sage: trail = milp.find_one_xor_linear_trail_with_fixed_weight(3, fixed_values=[key]) # random
sage: trail["total_weight"]
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]
fix_variables_value_xor_linear_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_models.milp_xor_linear_model import MilpXorLinearModel
sage: simon = SimonBlockCipher(block_bit_size=32, key_bit_size=64, number_of_rounds=2)
sage: milp = MilpXorLinearModel(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_xor_linear_constraints(fixed_variables)
sage: constraints
[x_0 == 1,
 x_1 == 0,
 ...
 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)
update_xor_linear_constraints_for_more_than_two_bits(constraints, input_vars, number_of_inputs, output_var, x)
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
weight_xor_linear_constraints(weight, weight_precision=2)

Return a list of variables and a list of constraints that fix the total weight to a specific value. By default, the weight corresponds to the negative base-2 logarithm of the correlation of the trail.

INPUT:

  • weight – integer; the total weight. By default, it is the negative base-2 logarithm of the total correlation of the trail.

  • 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_models.milp_xor_linear_model import MilpXorLinearModel
sage: simon = SimonBlockCipher(block_bit_size=32, key_bit_size=64, number_of_rounds=2)
sage: milp = MilpXorLinearModel(simon)
sage: milp.init_model_in_sage_milp_class()
sage: variables, constraints = milp.weight_xor_linear_constraints(10)
sage: variables
[('p[probability]', x_0)]
sage: constraints
[x_0 == 1000]