The maximum ADD differential probability of the sequence of operations: ADD, LROT, XOR (ARX): $\max_{de}~\mathrm{adp}^{\mathrm{ARX}}(da,db,dd \rightarrow de)$ . More...

#include "common.hh"
#include "adp-arx.hh"
#include "max-adp-arx.hh"

Functions
void	max_adp_arx_bounds_0 (uint32_t k, const uint32_t n, const uint32_t lrot_const, double p, uint32_t de, gsl_matrix A[2][2][2][2], gsl_vector B[ADP_ARX_NISTATES][WORD_SIZE+1], gsl_vector C[ADP_ARX_NISTATES], const uint32_t dc, const uint32_t dd, uint32_t de_max, double *p_max)

void	max_adp_arx_bounds_i (uint32_t k, const uint32_t n, const uint32_t lrot_const, double p, uint32_t de, gsl_matrix A[2][2][2][2], gsl_vector B[WORD_SIZE+1], gsl_vector C, const uint32_t dc, const uint32_t dd, uint32_t de_max, double *p_max)

void	max_adp_arx_bounds (gsl_matrix A[2][2][2][2], gsl_vector B[ADP_ARX_NISTATES][WORD_SIZE+1], const uint32_t lrot_const, const uint32_t dc, const uint32_t dd, uint32_t *de_max)

void	max_adp_arx_print_bounds (gsl_vector *B[ADP_ARX_NISTATES][WORD_SIZE+1])

double	max_adp_arx (gsl_matrix A[2][2][2][2], const uint32_t lrot_const, const uint32_t da, const uint32_t db, const uint32_t dd, uint32_t de_max)

double	max_adp_arx_exper (gsl_matrix A[2][2][2][2], const uint32_t lrot_const, const uint32_t da, const uint32_t db, const uint32_t dd, uint32_t de_max)

Detailed Description

The maximum ADD differential probability of the sequence of operations: ADD, LROT, XOR (ARX): $\max_{de}~\mathrm{adp}^{\mathrm{ARX}}(da,db,dd \rightarrow de)$ .

Author: V.Velichkov, vesse.nosp@m.lin..nosp@m.velic.nosp@m.hkov.nosp@m.@uni..nosp@m.lu

Date: 2012-2013

Function Documentation

double max_adp_arx	(	gsl_matrix *	A[2][2][2][2],
		const uint32_t	lrot_const,
		const uint32_t	da,
		const uint32_t	db,
		const uint32_t	dd,
		uint32_t *	de_max
	)

Compute the maximum probability output difference $de$ from ARX: $\max_{de}~\mathrm{adp}^{\mathrm{ARX}}(da,db,dd \rightarrow de)$ – a wrapper function for max_adp_arx+bounds_0 .

Parameters

A	transition probability matrices.
lrot_const	the rotation constant of the LROT operation in ARX.
da	first input difference (input to the ADD in ARX).
db	second input difference (input to the ADD in ARX).
dd	third input difference (input to the XOR in ARX).
de_max	maximum probability output difference from ARX (computed).

Returns: $\mathrm{adp}^{\mathrm{ARX}}(da,db,dd \rightarrow de)$

See Also: max_adp_arx_bounds, max_adp_arx_bounds_i, max_adp_arx_bounds_0

void max_adp_arx_bounds	(	gsl_matrix *	A[2][2][2][2],
		gsl_vector *	B[ADP_ARX_NISTATES][WORD_SIZE+1],
		const uint32_t	lrot_const,
		const uint32_t	dc,
		const uint32_t	dd,
		uint32_t *	de_max
	)

Compute an array of bounds to be used in the computation of the maximum differential probability.

Parameters

A	transition probability matrices.
B	array of bounds for every initial state: $s: 0 \le s <$ ADP_ARX_NISTATES and every bit position $k: 0 \le k \le$ WORD_SIZE.
lrot_const	LROT constant.
dc	input difference to the LROT operation in ARX.
dd	input difference to the XOR operation in ARX.
de_max	maximum probability output difference from ARX (not used).

Algorithm Outline:

For each initial state $s: 0 \le s <$ ADP_ARX_NISTATES, WORD_SIZE, initialize to the corresponding final states (see ADP_ARX_FSTATES): $B[s][n] = L^{s}$ , where $L^{0} = (1,1,0,0,0,0,0,0)$ , $L^{1} = (0,0,1,1,0,0,0,0)$ $L^{2} = (0,0,0,0,1,1,0,0)$ , $L^{3} = (0,0,0,0,0,0,1,1)$ (performed by the caller).
For every bit position k from (WORD_SIZE - 1) down to 0
- For every initial state from 0 to (ADP_ARX_NISTATES - 1):
  - For every state from 0 to (ADP_ARX_MSIZE - 1):
    - Initialize $B[s][k][i] \leftarrow p_{\mathrm{max}} = 0$
    - Let $C^{i}_{k-1}$ be a column unit vector of size ADP_ARX_MSIZE with 1 at position .
    - Recursively assign values to the bits of the output difference starting at bit popsition and terminating at bit position WORD_SIZE.
    - The recursion proceeds to bit postion only if the probability of the partially constructed differential $(dc[j:k], dd[j+r:k+r] \rightarrow de[j+r:k+r])$ multiplied by the bound of the probability until the end , where $r=\mathrm{lrot\_const}$ , is bigger than the best probability found so far i.e. if: $B[s][j+1] A_{j} A_{j-1} \ldots A_{k} C^{i}_{k-1} > p_{\mathrm{max}}$ .
      Note
      This step is performed by max_adp_arx_bounds_i .
    - When update the maximum $p_{\mathrm{max}} \leftarrow p_{n-1} = \mathrm{dp}(dc[n-1:k],dd[n-1+r:k+r] \rightarrow de[n-1+r:k+r])$ .
    - At the end of the recursion set the maximum value for state and initial state at bit position : $B[s][k][i] \leftarrow p_{\mathrm{max}}$ .

Meaning of the bounds B:

For any $i: 0 \le i <$ ADP_ARX_MSIZE, the probability $B[s][k][i]$ computed with the above algorithm is an upper bound on on the maximum probability of the differential $(dc[n-1:k], dd[n-1+r:k+r] \rightarrow de[n-1+r:k+r])$ , computed from initial state $i$ and terminating at final state $L^{s}$ . In other words, for any choice of the following $(n-k)$ bits of de: $de[n-1+r:k+r]$ , the probability $L^{s} A_{n-1} A_{n-2} \ldots A_{k} C^{i}_{k-1}$ will never be bigger than $B[s][k][i]$ . Furthermore, let $G[s][k] = L^{s} A_{n-1} A_{n-2} \ldots A_{k}$ be the multiplication of the corresponding transition probability matrices for the following $(n-k)$ bits of de: $de[n-1+r:k+r]$ and let $H[s][k-1] = A_{k-1} A_{k-2} \ldots A_{0} C^i_{k-1}$ and $H[-1] = C^{2s}$ . Then $\mathrm{dp}(dc,dd \rightarrow de) = \sum_{s}(G[s][k]~ H[s][k-1]) \le \sum_{s}(B[s][k]~ H[s][k-1])$ . Threfore $\sum_{s}(B[s][k]~ H[s][k-1])$ is an upper bound on the proability $\mathrm{adp}^{\mathrm{ARX}}(da,db,dd \rightarrow de)$ . Note that $\mathrm{dp}(dc,dd \rightarrow de) = \mathrm{adp}^{\mathrm{ARX}}(da,db,dd \rightarrow de)$ , where $da + db = dc$ .

See Also: max_adp_arx_bounds_i, max_adp_xor_bounds

void max_adp_arx_bounds_0	(	uint32_t	k,
		const uint32_t	n,
		const uint32_t	lrot_const,
		double *	p,
		uint32_t *	de,
		gsl_matrix *	A[2][2][2][2],
		gsl_vector *	B[ADP_ARX_NISTATES][WORD_SIZE+1],
		gsl_vector *	C[ADP_ARX_NISTATES],
		const uint32_t	dc,
		const uint32_t	dd,
		uint32_t *	de_max,
		double *	p_max
	)

Compute the maximum probability output difference $de$ from ARX: $\max_{de}~\mathrm{adp}^{\mathrm{ARX}}(da,db,dd \rightarrow de)$ , given upper bounds on the probabilities $B[s][k]$ for every initial state $s: 0 \le s <$ ADP_ARX_NISTATES and every bit postion $k: 0 \le k <$ WORD_SIZE, computed with max_adp_arx_bounds .

Parameters

k	current bit position: $n \ge > k \ge 0$ ; initialized to 0.
n	word size (WORD_SIZE).
lrot_const	LROT constant.
p	the estimated probability at bit position .
de	output difference.
A	transition probability matrices (adp_arx_sf).
B	array of bounds for every initial state: $s: 0 \le s <$ ADP_ARX_NISTATES and every bit position $k: 0 \le k \le$ WORD_SIZE.
C	a set of ADP_ARX_NISTATES unit row vectors of size ADP_ARX_MSIZE. Each one is initialized with 1 at one of the four initial states (ADP_ARX_ISTATES).
dc	input difference to the LROT operation in ARX.
dd	input difference to the XOR operation in ARX.
de_max	maximum probability output difference from ARX (not used).
p_max	the maximum probability.

Returns: $\mathrm{adp}^{\mathrm{ARX}}(da,db,dd \rightarrow de)$

Algorithm Outline:

Recursively assign values to the bits of the output difference starting at bit popsition and terminating at bit position WORD_SIZE.
The recursion proceeds to bit postion only if the sum of the probabilities of the partially constructed differential $(dc[j:0], dd[j+r:r] \rightarrow de[j+r:r])$ computed starting from initial position , multiplied by the bound of the probability until the end , is bigger than the best probability found so far i.e. if: $\sum_{s} (B[s][j+1]~ A_{j} A_{j-1} \ldots A_{0} C^{s}_{-1}) > p_{\mathrm{max}}$ .
When update the maximum $p_{\mathrm{max}} \leftarrow p_{n-1} = \sum_{s} (L^{s}~ A_{n-1} A_{n-2} \ldots A_{0} C^{s}_{-1})$ $= \mathrm{dp}(dc[n-1:0],dd[n-1+r:r] \rightarrow de[n-1+r:r])$ . Note that must be are initialized to $L^{s}$ by the caller, where $L^{0} = (1,1,0,0,0,0,0,0)$ , $L^{1} = (0,0,1,1,0,0,0,0)$ $L^{2} = (0,0,0,0,1,1,0,0)$ , $L^{3} = (0,0,0,0,0,0,1,1)$ .
At the end of the recursion $p_\mathrm{max} = \mathrm{adp}^{\mathrm{ARX}}(da,db,dd \rightarrow de)$ , since $\mathrm{dp}(dc,dd \rightarrow de) = \mathrm{adp}^{\mathrm{ARX}}(da,db,dd \rightarrow de)$ , where .
Store and return $p_\mathrm{max}$ .

See Also: max_adp_arx_bounds_i

void max_adp_arx_bounds_i	(	uint32_t	k,
		const uint32_t	n,
		const uint32_t	lrot_const,
		double *	p,
		uint32_t *	de,
		gsl_matrix *	A[2][2][2][2],
		gsl_vector *	B[WORD_SIZE+1],
		gsl_vector *	C,
		const uint32_t	dc,
		const uint32_t	dd,
		uint32_t *	de_max,
		double *	p_max
	)

For a fixed initial state $s$ and bit position $k$ , compute an upper bound $B[s][k][i]$ on the probability of the differential $(dc[n-1:k], dd[n-1+r:k+r] \rightarrow de[n-1+r:k+r])$ computed from initial state $i$ and terminating at final state $L^{s}$ , where $s: 0 \le s <$ ADP_ARX_NISTATES i.e. compute a bound on the probability $\mathrm{dp}(dc[n-1:k],dd[n-1+r:k+r] \rightarrow de[n-1+r:k+r]) = L^{s} A_{n-1} A_{n-2} \ldots A_{k} C^{i}_{k-1}$ , given the upper bounds $B[s][k]$ on the probabilities of the differentials $(dc[n-1:j], dd[n-1+r:j+r] \rightarrow de[n-1+r:j+r])$ for $j = k+1, k+2, \ldots, n-1$ , where $L^{0} = (1,1,0,0,0,0,0,0)$ , $L^{1} = (0,0,1,1,0,0,0,0)$ $L^{2} = (0,0,0,0,1,1,0,0)$ , $L^{3} = (0,0,0,0,0,0,1,1)$ and $C^{i}_{k-1}$ is a column unit vector of size ADP_ARX_MSIZE with 1 at position $i$ ,

Parameters

k	current bit position: $n \ge > k \ge 0$ .
n	word size (WORD_SIZE).
lrot_const	LROT constant.
p	the estimated probability at bit position .
de	output difference.
A	transition probability matrices.
B	array of bounds for a fixed initial state , set by the caller and every bit position $k: 0 \le k \le$ WORD_SIZE.
C	unit row vector of size ADP_ARX_MSIZE, initialized with 1 at state index .
dc	input difference to the LROT operation in ARX.
dd	input difference to the XOR operation in ARX.
de_max	maximum probability output difference from ARX (not used).
p_max	the maximum probability.

Algorithm Outline:

Recursively assign values to the bits of the output difference starting at bit popsition and terminating at bit position WORD_SIZE.
The recursion proceeds to bit postion only if the probability of the partially constructed differential $(dc[j:k], dd[j+r:k+r] \rightarrow de[j+r:k+r])$ multiplied by the bound of the probability until the end , where $r=\mathrm{lrot\_const}$ , is bigger than the best probability found so far i.e. if: $B[s][j+1] A_{j} A_{j-1} \ldots A_{k} C^{i}_{k-1} > p_{\mathrm{max}}$ .
When update the maximum $p_{\mathrm{max}} \leftarrow p_{n-1} = \mathrm{dp}(dc[n-1:k],dd[n-1+r:k+r] \rightarrow de[n-1+r:k+r])$ .
Store and return.

See Also: max_adp_arx_bounds

double max_adp_arx_exper	(	gsl_matrix *	A[2][2][2][2],
		const uint32_t	lrot_const,
		const uint32_t	da,
		const uint32_t	db,
		const uint32_t	dd,
		uint32_t *	de_max
	)

Compute the maximum differential probability by exhaustive search over all output differences. Complexity: $O(2^n)$ .

Parameters

A	transition probability matrices.
lrot_const	the rotation constant of the LROT operation in ARX.
da	first input difference.
db	second input difference.
dd	third input difference.
de_max	maximum probability output difference.

Returns: $\max_{de}~\mathrm{adp}^{\mathrm{ARX}}(da,db,dd \rightarrow de)$

See Also: max_adp_xor

void max_adp_arx_print_bounds ( gsl_vector * B[ADP_ARX_NISTATES][WORD_SIZE+1] )

Print the array of bounds computed with max_adp_arx_bounds .

Parameters

B	array of bounds for every initial state: $s: 0 \le s <$ ADP_ARX_NISTATES and every bit position $k: 0 \le k \le$ WORD_SIZE.

See Also: max_adp_arx_bounds.

Functions

Detailed Description

Function Documentation