cascada.linear.characteristic module

Manipulate non-symbolic linear characteristics.

Characteristic

Represent linear characteristics over bit-vector functions.

EncryptionCharacteristic

Represent linear characteristics over encryption functions.
class cascada.linear.characteristic.Characteristic(input_mask, output_mask, assign_outmask_list, ch_model, external_masks=None, free_masks=None, empirical_ch_weight=None, empirical_data_list=None, is_valid=True)[source]

Bases: cascada.abstractproperty.characteristic.Characteristic

Represent linear characteristics over bit-vector functions.

Internally, this class is a subclass of abstractproperty.characteristic.Characteristic, where the Property is a LinearMask type.

As mentioned in abstractproperty.characteristic.Characteristic, the characteristic probability is defined as the product of the propagation probability (absolute correlation) of the LinearMask pairs (linear approximations) \((\Delta_{x_{i}} \mapsto \Delta_{x_{i+1}})\) over \(f_i\). If \(f\) has external variables, the characteristic probability approximates the absolute correlation of the input-output mask pair of the characteristic averaged over the set of all values of the external variables.

>>> from cascada.bitvector.core import Constant
>>> from cascada.bitvector.operation import RotateLeft, RotateRight
>>> from cascada.linear.mask import LinearMask, LinearMask
>>> from cascada.linear.chmodel import ChModel
>>> from cascada.linear.characteristic import Characteristic
>>> from cascada.primitives import speck
>>> Speck32_KS = speck.get_Speck_instance(speck.SpeckInstance.speck_32_64).key_schedule
>>> Speck32_KS.set_num_rounds(2)
>>> ch_model = ChModel(Speck32_KS, LinearMask, ["mk0", "mk1", "mk2"])
>>> zm = core.Constant(0, width=16)
>>> mk0 = RotateLeft(Constant(1, width=16), 8)  # mk0 >>> 7 == 0b0···010
>>> mx5 = RotateRight(mk0, 7)  # ~ mk0 >>> 7 == 0b0···010
>>> mx3__1 = RotateRight(Constant(1, width=16), 1)  # mx3__1 <<< 2 == 0b0···010
>>> mx3_out = core.Constant(0x8002, 16)
>>> assign_outmask_list = [zm, zm, zm, zm, mx5, mx3__1, mx5, mx5, zm, mx3_out, mx5]
>>> ch = Characteristic([mk0, zm, zm], [zm, mx3_out, mx5], assign_outmask_list, ch_model)
>>> ch  
Characteristic(ch_weight=1, assignment_weights=[0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
    input_mask=[0x0100, 0x0000, 0x0000], output_mask=[0x0000, 0x8002, 0x0002],
    assign_outmask_list=[0x0000, 0x0000, 0x0000, 0x0000, 0x0002, 0x8000, 0x0002, 0x0002, 0x0000, 0x8002, 0x0002])
>>> list(zip(ch.assignment_weights, ch.tuple_assign_outmask2op_model))  
[(Decimal('0'), (LinearMask(0x0000), LinearModelFreeBranch(LinearMask(0x0000)))),
 (Decimal('0'), (LinearMask(0x0000), LinearModelFreeBranch(LinearMask(0x0000)))),
 (Decimal('0'), (LinearMask(0x0000), LinearModelBvAdd([LinearMask(0x0000), LinearMask(0x0000)]))),
 (Decimal('0'), (LinearMask(0x0000), LinearModelBvXor([LinearMask(0x0000), LinearMask(0x0000)]))),
 (Decimal('0'), (LinearMask(0x0002), LinearModelFreeBranch(LinearMask(0x0000)))),
 (Decimal('0'), (LinearMask(0x8000), LinearModelFreeBranch(LinearMask(0x0000)))),
 (Decimal('1'), (LinearMask(0x0002), LinearModelBvAdd([LinearMask(0x0002), LinearMask(0x0002)]))),
 (Decimal('0'), (LinearMask(0x0002), LinearModelBvXor([LinearMask(0x0002), LinearMask(0x0002)]))),
 (Decimal('0'), (LinearMask(0x0000), LinearModelId(LinearMask(0x0000)))),
 (Decimal('0'), (LinearMask(0x8002), LinearModelId(LinearMask(0x8002)))),
 (Decimal('0'), (LinearMask(0x0002), LinearModelId(LinearMask(0x0002))))]
input_mask

a list of LinearMask objects containing the (constant) input mask (alias of abstractproperty.characteristic.Characteristic.input_prop).

output_mask

a list of LinearMask objects containing the (constant) output mask (alias of abstractproperty.characteristic.Characteristic.output_prop).

external_masks

a list containing the (constant) LinearMask of the external variables of the function (alias of abstractproperty.characteristic.Characteristic.external_props).

tuple_assign_outmask2op_model

a tuple where each element is a pair containing: (1) the output (constant) LinearMask \(\Delta_{x_{i+1}}\) of the non-trivial assignment \(x_{i+1} \leftarrow f_i(x_i)\) and (2) the linear.opmodel.OpModel of this assignment with a (constant) input LinearMask \(\Delta_{x_{i}}\) (alias of abstractproperty.characteristic.Characteristic.tuple_assign_outprop2op_model).

free_masks

a list of (symbolic) LinearMask objects of the Characteristic.ch_model, whose values do not affect the characteristic, and were replaced by constant masks in input_mask, output_mask, external_masks or tuple_assign_outmask2op_model (alias of abstractproperty.characteristic.Characteristic.free_props).

var_mask2ct_mask

a collections.OrderedDict mapping each symbolic LinearMask in the trail to its constant mask (alias of abstractproperty.characteristic.Characteristic.var_prop2ct_prop).

vrepr(ignore_external_masks=False)[source]

Return an executable string representation.

See also abstractproperty.characteristic.Characteristic.vrepr.

>>> from cascada.bitvector.core import Constant
>>> from cascada.bitvector.operation import RotateLeft, RotateRight
>>> from cascada.linear.mask import LinearMask
>>> from cascada.linear.chmodel import ChModel
>>> from cascada.primitives import speck
>>> Speck32_KS = speck.get_Speck_instance(speck.SpeckInstance.speck_32_64).key_schedule
>>> Speck32_KS.set_num_rounds(2)
>>> ch_model = ChModel(Speck32_KS, LinearMask, ["mk0", "mk1", "mk2"])
>>> zm = core.Constant(0, width=16)
>>> mk0 = RotateLeft(Constant(1, width=16), 8)  # mk0 >>> 7 == 0b0···010
>>> mx5 = RotateRight(mk0, 7)  # ~ mk0 >>> 7 == 0b0···010
>>> mx3__1 = RotateRight(Constant(1, width=16), 1)  # mx3__1 <<< 2 == 0b0···010
>>> mx3_out = core.Constant(0x8002, 16)
>>> assign_outmask_list = [zm, zm, zm, zm, mx5, mx3__1, mx5, mx5, zm, mx3_out, mx5]
>>> ch = Characteristic([mk0, zm, zm], [zm, mx3_out, mx5], assign_outmask_list, ch_model)
>>> ch.vrepr()  
"Characteristic(input_mask=[Constant(0x0100, width=16), Constant(0x0000, width=16), Constant(0x0000, width=16)],
    output_mask=[Constant(0x0000, width=16), Constant(0x8002, width=16), Constant(0x0002, width=16)],
    assign_outmask_list=[Constant(0x0000, width=16), Constant(0x0000, width=16), Constant(0x0000, width=16),
        Constant(0x0000, width=16), Constant(0x0002, width=16), Constant(0x8000, width=16), Constant(0x0002, width=16),
        Constant(0x0002, width=16), Constant(0x0000, width=16), Constant(0x8002, width=16), Constant(0x0002, width=16)],
    ch_model=ChModel(func=SpeckKeySchedule.set_num_rounds_and_return(2), mask_type=LinearMask,
        input_mask_names=['mk0', 'mk1', 'mk2'], prefix='mx'))"
>>> ch.srepr()
'Ch(w=1, id=0100 0000 0000, od=0000 8002 0002)'
split(mask_separators)[source]

Split into multiple Characteristic objects given the list of mask separators.

See also abstractproperty.characteristic.Characteristic.split.

>>> from cascada.bitvector.core import Constant, Variable
>>> from cascada.bitvector.operation import RotateLeft, RotateRight
>>> from cascada.linear.mask import LinearMask
>>> from cascada.linear.chmodel import ChModel
>>> from cascada.linear.characteristic import Characteristic
>>> from cascada.primitives import speck
>>> Speck32_KS = speck.get_Speck_instance(speck.SpeckInstance.speck_32_64).key_schedule
>>> Speck32_KS.set_num_rounds(2)
>>> ch_model = ChModel(Speck32_KS, LinearMask, ["mk0", "mk1", "mk2"])
>>> tuple(ch_model.ssa.assignments.items())  
((mx0, mk1 >>> 7), (mk2__0, Id(mk2)), (mk2__1, Id(mk2)), (mk2__2, Id(mk2)),
    (mx1, mx0 + mk2__0), (mx2, mk2__1 <<< 2), (mx3, mx2 ^ mx1),
(mx4, mk0 >>> 7), (mx3__0, Id(mx3)), (mx3__1, Id(mx3)), (mx3__2, Id(mx3)),
    (mx5, mx4 + mx3__0), (mx6, mx5 ^ 0x0001), (mx7, mx3__1 <<< 2), (mx8, mx7 ^ mx6),
(mk2_out, Id(mk2__2)), (mx3_out, Id(mx3__2)), (mx8_out, Id(mx8)))
>>> mask_separators = [ (LinearMask(Variable("mx2", width=16)), LinearMask(Variable("mx3", width=16))), ]
>>> zm = core.Constant(0, width=16)
>>> mk0 = RotateLeft(Constant(1, width=16), 8)  # mk0 >>> 7 == 0b0···010
>>> mx5 = RotateRight(mk0, 7)  # ~ mk0 >>> 7 == 0b0···010
>>> mx3__1 = RotateRight(Constant(1, width=16), 1)  # mx3__1 <<< 2 == 0b0···010
>>> mx3_out = core.Constant(0x8002, 16)
>>> assign_outmask_list = [zm, zm, zm, zm, mx5, mx3__1, mx5, mx5, zm, mx3_out, mx5]
>>> ch = Characteristic([mk0, zm, zm], [zm, mx3_out, mx5], assign_outmask_list, ch_model)
>>> for ch in ch.split(mask_separators): print(ch)  
Characteristic(ch_weight=0, assignment_weights=[0, 0, 0, 0, 0, 0, 0],
    input_mask=[0x0100, 0x0000, 0x0000],
    output_mask=[0x0100, 0x0000, 0x0000],
    assign_outmask_list=[0x0000, 0x0000, 0x0000, 0x0000, 0x0100, 0x0000, 0x0000])
Characteristic(ch_weight=1, assignment_weights=[0, 0, 1, 0, 0, 0, 0],
    input_mask=[0x0100, 0x0000, 0x0000],
    output_mask=[0x0000, 0x8002, 0x0002],
    assign_outmask_list=[0x0002, 0x8000, 0x0002, 0x0002, 0x0000, 0x8002, 0x0002])
classmethod random(ch_model, seed, external_masks=None)[source]

Return a random Characteristic with given linear.chmodel.ChModel.

See also abstractproperty.characteristic.Characteristic.random.

>>> from cascada.linear.mask import LinearMask
>>> from cascada.linear.chmodel import ChModel
>>> from cascada.linear.characteristic import Characteristic
>>> from cascada.bitvector.ssa import BvFunction
>>> class MyFoo(BvFunction):
...     input_widths, output_widths = [4, 4], [4, 4]
...     @classmethod
...     def eval(cls, a, b):  return a + b, a
>>> ch_model = ChModel(MyFoo, LinearMask, ["ma", "mb"])
>>> Characteristic.random(ch_model, 0)  
Characteristic(ch_weight=2, assignment_weights=[0, 2, 0, 0],
    input_mask=[0x2, 0x6], output_mask=[0x4, 0x5],
    assign_outmask_list=[0x7, 0x4, 0x4, 0x5])
compute_empirical_ch_weight(num_input_samples=None, num_external_samples=None, split_by_max_weight=None, split_by_rounds=False, seed=None, C_code=False, num_parallel_processes=None)[source]

Compute and store the empirical weight.

The main description of this method can be read from abstractproperty.characteristic.Characteristic.compute_empirical_ch_weight, simply by replacing Property by LinearMask and input-output pair by hull.

The basic subroutine in this case consists of computing the fraction of right inputs for num_input_samples sampled inputs. An input \(x\) is a right input if \(\langle \alpha, x \rangle = \langle \beta, f(x) \rangle\), where \(\alpha\) is input_mask, \(\beta\) is output_mask and \(f\) is the underlying bit-vector function.

>>> from cascada.bitvector.core import Constant
>>> from cascada.bitvector.operation import RotateLeft, RotateRight
>>> from cascada.linear.mask import LinearMask, LinearMask
>>> from cascada.linear.chmodel import ChModel
>>> from cascada.linear.characteristic import Characteristic
>>> from cascada.primitives import speck
>>> Speck32_KS = speck.get_Speck_instance(speck.SpeckInstance.speck_32_64).key_schedule
>>> Speck32_KS.set_num_rounds(2)
>>> ch_model = ChModel(Speck32_KS, LinearMask, ["mk0", "mk1", "mk2"])
>>> zm = core.Constant(0, width=16)
>>> mk0 = RotateLeft(Constant(1, width=16), 8)  # mk0 >>> 7 == 0b0···010
>>> mx5 = RotateRight(mk0, 7)  # ~ mk0 >>> 7 == 0b0···010
>>> mx3__1 = RotateRight(Constant(1, width=16), 1)  # mx3__1 <<< 2 == 0b0···010
>>> mx3_out = core.Constant(0x8002, 16)
>>> assign_outmask_list = [zm, zm, zm, zm, mx5, mx3__1, mx5, mx5, zm, mx3_out, mx5]
>>> ch = Characteristic([mk0, zm, zm], [zm, mx3_out, mx5], assign_outmask_list, ch_model)
>>> ch.compute_empirical_ch_weight(seed=0)
>>> ch.empirical_ch_weight
Decimal('1.093109404391481470675941626')
>>> for data in ch.empirical_data_list: print(data)  
EmpiricalWeightData(weight_avg_aux_prs=1.093109404391481470675941626,
    num_aux_weights=1, num_inf_aux_weights=0, num_input_samples=192, seed=0, C_code=False)
>>> ch.compute_empirical_ch_weight(seed=0, C_code=True)
>>> ch.empirical_ch_weight
Decimal('1.061400544664143309159590699')
class cascada.linear.characteristic.EncryptionCharacteristic(input_mask, output_mask, assign_outmask_list, ch_model, external_masks=None, free_masks=None, empirical_ch_weight=None, empirical_data_list=None, is_valid=True)[source]

Bases: cascada.abstractproperty.characteristic.EncryptionCharacteristic, cascada.linear.characteristic.Characteristic

Represent linear characteristics over encryption functions.

Given a Cipher, an EncryptionCharacteristic is a linear characteristic (see Characteristic) over the Cipher.encryption (where the Cipher.key_schedule is ignored and round key masks are given as constant LinearMask).

The propagation probability of an EncryptionCharacteristic is similar to the expected linear probability (ELP), but instead of multiplying the absolute correlations, the ELP multiplies the square of the correlations (see https://eprint.iacr.org/2005/212).

>>> from cascada.bitvector.core import Constant
>>> from cascada.bitvector.operation import RotateRight, RotateLeft
>>> from cascada.linear.mask import LinearMask
>>> from cascada.linear.chmodel import EncryptionChModel
>>> from cascada.linear.characteristic import EncryptionCharacteristic
>>> from cascada.primitives import speck
>>> Speck32 = speck.get_Speck_instance(speck.SpeckInstance.speck_32_64)
>>> Speck32.set_num_rounds(2)
>>> ch_model = EncryptionChModel(Speck32, LinearMask)
>>> zm = core.Constant(0, width=16)
>>> p1 = core.Constant(0x0600, width=16)
>>> c0 = core.Constant(0x60f0, width=16)
>>> c1 = core.Constant(0x60c0, width=16)
>>> k1 = core.Constant(0x0030, width=16)
>>> bv_1800 = core.Constant(0x1800, width=16)
>>> assign_outmask_list = [zm, zm, zm, bv_1800, bv_1800, k1, k1, k1, c1, c1, c0, c1]
>>> ch = EncryptionCharacteristic([zm, p1], [c0, c1], assign_outmask_list, ch_model, [zm, k1])
>>> ch  
EncryptionCharacteristic(ch_weight=1, assignment_weights=[0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
    input_mask=[0x0000, 0x0600], output_mask=[0x60f0, 0x60c0], external_masks=[0x0000, 0x0030],
    assign_outmask_list=[0x0000, 0x0000, 0x0000, 0x1800, 0x1800, 0x0030,
                         0x0030, 0x0030, 0x60c0, 0x60c0, 0x60f0, 0x60c0])
>>> list(zip(ch.assignment_weights, ch.tuple_assign_outmask2op_model))  
[(Decimal('0'), (LinearMask(0x0000), LinearModelFreeBranch(LinearMask(0x0600)))),
 (Decimal('0'), (LinearMask(0x0000), LinearModelBvAdd([LinearMask(0x0000), LinearMask(0x0000)]))),
 (Decimal('0'), (LinearMask(0x0000), LinearModelBvXor([LinearMask(0x0000), LinearMask(0x0000)]))),
 (Decimal('0'), (LinearMask(0x1800), LinearModelFreeBranch(LinearMask(0x0000)))),
 (Decimal('0'), (LinearMask(0x1800), LinearModelBvXor([LinearMask(0x1800), LinearMask(0x1800)]))),
 (Decimal('0'), (LinearMask(0x0030), LinearModelFreeBranch(LinearMask(0x1800)))),
 (Decimal('1'), (LinearMask(0x0030), LinearModelBvAdd([LinearMask(0x0030), LinearMask(0x0030)]))),
 (Decimal('0'), (LinearMask(0x0030), LinearModelBvXor([LinearMask(0x0030), LinearMask(0x0030)]))),
 (Decimal('0'), (LinearMask(0x60c0), LinearModelFreeBranch(LinearMask(0x0030)))),
 (Decimal('0'), (LinearMask(0x60c0), LinearModelBvXor([LinearMask(0x60c0), LinearMask(0x60c0)]))),
 (Decimal('0'), (LinearMask(0x60f0), LinearModelId(LinearMask(0x60f0)))),
 (Decimal('0'), (LinearMask(0x60c0), LinearModelId(LinearMask(0x60c0))))]