cascada.linear.mask module

Represent linear mask properties in the context of linear cryptanalysis.

LinearMask

Represent linear mask properties.

class cascada.linear.mask.LinearMask(value)[source]

Bases: cascada.abstractproperty.property.Property

Represent linear mask properties.

Given a function \(f\), a LinearMask property pair (also called a linear approximation) \((\alpha, \beta)\) is a bit-vector Property \((\alpha, \beta)\) where the propagation probability is the absolute correlation \(| C(\alpha, \beta) |\).

The absolute correlation of a linear approximation with input mask \(\alpha\) and output mask \(\beta\) over a Operation \(f\) is defined as \(| C(\alpha, \beta) | = | 2 \times \left( \# \{ x \ : \langle \alpha, x \rangle = \langle \beta, f(x) \rangle \} / 2^n \right) \ \ - \ \ 1 |\), where \(n\) is the bit-width of the input \(x\). Other related notions are the bias of an approximation (its correlation divided by two) or the linear probability or potential (the square of its correlation).

The inner product \(\langle a, b \rangle\) is defined as \((a_0 \wedge b_0) \oplus (a_1 \wedge b_1) \oplus \dots \oplus (a_{n-1} \wedge b_{n-1})\).

Internally, LinearMask is a subclass of Property (as XorDiff). The LinearMask methods inherited from Property requiring arguments of type Property should be called instead with arguments of type LinearMask.

>>> from cascada.bitvector.core import Constant, Variable
>>> from cascada.linear.mask import LinearMask
>>> alpha = LinearMask(Constant(0b001, 3))
>>> alpha
LinearMask(0b001)
>>> alpha.apply(Constant(0b011, 3))
0b1
>>> LinearMask(Variable("alpha", 3))
LinearMask(alpha)

apply(x)[source]: Return the inner product of the mask and x.

classmethod propagate(op, input_mask)[source]

Propagate the given input LinearMask through the given operation.

For any linear (over the binary finite field) operation op and any input mask input_mask, the output mask output_mask is uniquely determined and its bit-vector value satisfies input_mask.val == M(output_mask.val), where \(M\) is the transpose of the binary matrix representing op.

See Property.propagate for more information.

User-defined or new Operation op can store its associated linear linear.opmodel.OpModel in op.linear_model, as this method first checks whether op has its associated linear.opmodel.OpModel stored in the class attribute linear_model.

>>> from cascada.bitvector.core import Variable, Constant
>>> from cascada.bitvector.operation import BvXor, RotateLeft, BvIdentity
>>> from cascada.bitvector.operation import make_partial_operation
>>> from cascada.linear.mask import LinearMask
>>> d1, d2 = LinearMask(Variable("d1", 8)), LinearMask(Variable("d2", 8))
>>> LinearMask.propagate(BvXor, [d1, d2])
LinearModelBvXor([LinearMask(d1), LinearMask(d2)])
>>> Xor1 = make_partial_operation(BvXor, tuple([None, Constant(1, 8)]))
>>> LinearMask.propagate(Xor1, d1)
LinearMask(d1)
>>> Rotate1 = make_partial_operation(RotateLeft, tuple([None, 1]))
>>> LinearMask.propagate(Rotate1, d1)
LinearMask(d1 <<< 1)
>>> LinearMask.propagate(BvIdentity, d1)
LinearModelId(LinearMask(d1))