cascada.differential.difference module

Represent types of difference properties in the context of differential cryptanalysis.

`Difference`	Represent difference properties.
`XorDiff`	Represent XOR difference properties.
`RXOp`	The difference operation of `RXDiff` given by `(x, y) \|--> (x <<< 1) ^ y.`
`RXInvOp`	The inverse of the difference operation of `RXDiff` given by `(x, d) \|--> (x <<< 1) ^ d.`
`RXDiff`	Represent rotational-XOR (RX) difference properties.

class cascada.differential.difference.Difference(value)[source]

Bases: cascada.abstractproperty.property.Property

Represent difference properties.

The difference between two Term objects \(x\) and \(y\) is defined as \(\alpha = y - x\) for some difference operation \(-\) (a bit-vector Operation). In other words, the pair \((x, x + \alpha)\) has difference \(\alpha\), where \(+\) is the “inverse” of the difference operation.

Given a function \(f\), a Difference property pair (also called a differential) \((\alpha, \beta)\) is a bit-vector Property \((\alpha, \beta)\) where the propagation probability (also called the differential probability) is defined as \(DP(\alpha, \beta) = \# \{ x \ : \ f(x + \alpha) - f(x) = \beta \} / 2^{n}\), that is, the fraction of input pairs with input difference \(\alpha\) that lead to output pairs with difference \(\beta\).

The most common difference used in differential cryptanalysis is the XOR difference XorDiff (where the difference operation is BvXor). Other examples are the additive difference (where the difference operation is BvSub) or the rotational-XOR difference RXDiff.

This class is not meant to be instantiated but to provide a base class to represent types of differences.

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

diff_op: the difference Operation.

inv_diff_op: the inverse of the difference operation.

get_pair_element(x)[source]: Return the Term \(y\) such that \(y = \alpha + x\).

classmethod from_pair(x, y)[source]: Return the Difference \(\alpha = y - x\) given two Term.

class cascada.differential.difference.XorDiff(value)[source]

Bases: cascada.differential.difference.Difference

Represent XOR difference properties.

The XOR difference of two Term is given by the XOR of the terms. In other words, the difference operation of XorDiff is the BvXor (see Difference).

>>> from cascada.bitvector.core import Constant, Variable
>>> from cascada.differential.difference import XorDiff
>>> x, y = Constant(0b000, 3), Constant(0b000, 3)
>>> alpha = XorDiff.from_pair(x, y)
>>> alpha
XorDiff(0b000)
>>> alpha.get_pair_element(x)
0b000
>>> x, y = Constant(0b010, 3), Constant(0b101, 3)
>>> alpha = XorDiff.from_pair(x, y)
>>> alpha
XorDiff(0b111)
>>> alpha.get_pair_element(x)
0b101
>>> k = Variable("k", 8)
>>> alpha = XorDiff.from_pair(k, k)
>>> alpha
XorDiff(0x00)
>>> alpha.get_pair_element(k)
k

diff_op: alias of cascada.bitvector.operation.BvXor

inv_diff_op: alias of cascada.bitvector.operation.BvXor

classmethod propagate(op, input_diff)[source]

Propagate the given input difference of type XorDiff through the given operation.

For any operation op linear with respect to BvXor and any input difference input_diff, the output difference is uniquely determined and its bit-vector value is f(input_diff.val).

See Property.propagate for more information.

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

>>> from cascada.bitvector.core import Variable, Constant
>>> from cascada.bitvector.operation import BvXor, BvAdd, BvIdentity
>>> from cascada.bitvector.operation import make_partial_operation
>>> from cascada.differential.difference import XorDiff
>>> d1, d2 = XorDiff(Variable("d1", 8)), XorDiff(Variable("d2", 8))
>>> XorDiff.propagate(BvXor, [d1, d2])
XorDiff(d1 ^ d2)
>>> Xor1 = make_partial_operation(BvXor, tuple([None, Constant(1, 8)]))
>>> XorDiff.propagate(Xor1, d1)
XorDiff(d1)
>>> XorDiff.propagate(BvAdd, [d1, d2])
XorModelBvAdd([XorDiff(d1), XorDiff(d2)])
>>> Add1 = make_partial_operation(BvAdd, tuple([None, Constant(1, 8)]))
>>> XorDiff.propagate(Add1, d1)
XorModelBvAddCt_{·, 0x01}(XorDiff(d1))
>>> XorDiff.propagate(BvIdentity, d1)
XorModelId(XorDiff(d1))

class cascada.differential.difference.RXOp(**kwargs)[source]

Bases: cascada.bitvector.operation.SecondaryOperation

The difference operation of RXDiff given by (x, y) |--> (x <<< 1) ^ y.

classmethod condition(x, y)[source]: Check if the operands verify the restrictions of the operator.

classmethod output_width(x, y)[source]: Return the bit-width of the resulting bit-vector.

classmethod eval(x, y)[source]

Evaluate the operator with given operands.

This is an internal method that assumes the list args has been parsed. To evaluate a bit-vector operation, instantiate a new object with the operands as the object arguments (i.e., use the Python operator ()).

class cascada.differential.difference.RXInvOp(**kwargs)[source]

Bases: cascada.bitvector.operation.SecondaryOperation

The inverse of the difference operation of RXDiff given by (x, d) |--> (x <<< 1) ^ d.

classmethod condition(x, d)[source]: Check if the operands verify the restrictions of the operator.

classmethod output_width(x, d)[source]: Return the bit-width of the resulting bit-vector.

classmethod eval(x, d)[source]

Evaluate the operator with given operands.

This is an internal method that assumes the list args has been parsed. To evaluate a bit-vector operation, instantiate a new object with the operands as the object arguments (i.e., use the Python operator ()).

class cascada.differential.difference.RXDiff(value)[source]

Bases: cascada.differential.difference.Difference

Represent rotational-XOR (RX) difference properties.

The pair (x, (x <<< 1) ^ d) has RX difference d. In other words, the RX difference of two Term x and y is defined as (x <<< 1) ^ y.

This definition of rotational-XOR difference is equivalent but slightly different to the definitions presented in Rotational Cryptanalysis in the Presence of Constants and Rotational-XOR Cryptanalysis of Reduced-round SPECK.

See Difference for more information.

>>> from cascada.bitvector.core import Constant, Variable
>>> from cascada.bitvector.operation import RotateLeft
>>> from cascada.differential.difference import RXDiff
>>> x, y = Constant(0b000, 3), Constant(0b000, 3)
>>> alpha = RXDiff.from_pair(x, y)
>>> alpha
RXDiff(0b000)
>>> alpha.get_pair_element(x)
0b000
>>> x, y = Constant(0b000, 3), Constant(0b001, 3)
>>> alpha = RXDiff.from_pair(x, y)
>>> alpha
RXDiff(0b001)
>>> alpha.get_pair_element(x)
0b001
>>> x, y, d = Variable("x", 3),  Variable("y", 3), Variable("d", 3)
>>> RXDiff.from_pair(x, y).val.doit()  # RXOp is a SecondaryOperation
(x <<< 1) ^ y
>>> RXDiff.from_pair(x, RotateLeft(x, 1) ^ d).val.doit()
d
>>> RXDiff(d).get_pair_element(x).doit()
(x <<< 1) ^ d

diff_op: alias of cascada.differential.difference.RXOp

inv_diff_op: alias of cascada.differential.difference.RXInvOp

classmethod propagate(op, input_diff)[source]

Propagate the given input difference of type RXDiff through the given operation.

For any operation op linear with respect to RXOp and any input difference input_diff, the output difference is uniquely determined and its bit-vector value is f(input_diff.val).

See Property.propagate for more information.

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

>>> from cascada.bitvector.core import Variable, Constant
>>> from cascada.bitvector.operation import BvAdd, BvXor, BvShl, BvIdentity
>>> from cascada.bitvector.operation import make_partial_operation
>>> from cascada.differential.difference import RXDiff
>>> d1, d2 = RXDiff(Variable("d1", 8)), RXDiff(Variable("d2", 8))
>>> RXDiff.propagate(BvXor, [d1, d2])
RXDiff(d1 ^ d2)
>>> Xor1 = make_partial_operation(BvXor, tuple([None, Constant(1, 8)]))
>>> RXDiff.propagate(Xor1, d1)
RXDiff(d1 ^ 0x03)
>>> RXDiff.propagate(BvAdd, [d1, d2])
RXModelBvAdd([RXDiff(d1), RXDiff(d2)])
>>> Shl1 = make_partial_operation(BvShl, tuple([None, Constant(1, 8)]))
>>> RXDiff.propagate(Shl1, d1)
RXModelBvShlCt_{·, 0x01}(RXDiff(d1))
>>> RXDiff.propagate(BvIdentity, d1)
RXModelId(RXDiff(d1))