YAARX: Yet Another ARX Toolkit  0.1
 All Data Structures Files Functions Variables Macros Pages
Functions
max-adp-xor3.cc File Reference

The maximum ADD differential probability of XOR with three inputs: $\max_{dd}~\mathrm{adp}^{3\oplus}(da, db, dc \rightarrow dd)$. More...

#include "common.hh"
#include "adp-xor3.hh"

Functions

void max_adp_xor3_i (const int i, const uint32_t k, const uint32_t n, double *p, uint32_t *dd, gsl_matrix *A[2][2][2][2], gsl_vector *B[WORD_SIZE+1], gsl_vector *C, const uint32_t da, const uint32_t db, const uint32_t dc, uint32_t *dd_max, double *p_max)
 
void max_adp_xor3_bounds (gsl_matrix *A[2][2][2][2], gsl_vector *B[WORD_SIZE+1], const uint32_t da, const uint32_t db, const uint32_t dc, uint32_t *dd_max)
 
double max_adp_xor3 (gsl_matrix *A[2][2][2][2], const uint32_t da, const uint32_t db, const uint32_t dc, uint32_t *dd_max)
 
void max_adp_xor3_rec_i (const uint32_t k, const uint32_t n, double *p, uint32_t *dd, gsl_matrix *A[2][2][2][2], gsl_vector *C, const uint32_t da, const uint32_t db, const uint32_t dc, uint32_t *dd_max, double *p_max)
 
double max_adp_xor3_rec (gsl_matrix *A[2][2][2][2], gsl_vector *C, const uint32_t da, const uint32_t db, const uint32_t dc, uint32_t *dd_max)
 
double max_adp_xor3_exper (gsl_matrix *A[2][2][2][2], const uint32_t da, const uint32_t db, const uint32_t dc, uint32_t *dd_max)
 

Detailed Description

The maximum ADD differential probability of XOR with three inputs: $\max_{dd}~\mathrm{adp}^{3\oplus}(da, db, dc \rightarrow dd)$.

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

Function Documentation

double max_adp_xor3 ( gsl_matrix *  A[2][2][2][2],
const uint32_t  da,
const uint32_t  db,
const uint32_t  dc,
uint32_t *  dd_max 
)

Compute the maximum differential probability over all output differences: $\mathrm{max}_{dc}~\mathrm{adp}^{\oplus}(da,db,dc \rightarrow dd)$. Complexity c: $O(n) \le c \le O(2^n)$.

Parameters
Atransition probability matrices.
dafirst input difference.
dbsecond input difference.
dcthird input difference.
dd_maxmaximum probability output difference.
See Also
max_adp_xor3_bounds, max_adp_xor3_i
void max_adp_xor3_bounds ( gsl_matrix *  A[2][2][2][2],
gsl_vector *  B[WORD_SIZE+1],
const uint32_t  da,
const uint32_t  db,
const uint32_t  dc,
uint32_t *  dd_max 
)

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

Parameters
Atransition probability matrices.
Barray of size A_size rows by (n + 1) columns containing upper bounds on the maximum probabilities of all j bit differentials $n \ge j \ge 1$ beginning from any state i: A_size $> i \ge 0$.
dafirst input difference.
dbsecond input difference.
dcthird input difference.
dd_maxmaximum probability output difference.
See Also
max_adp_xor_bounds, max_adp_xor3_i
double max_adp_xor3_exper ( gsl_matrix *  A[2][2][2][2],
const uint32_t  da,
const uint32_t  db,
const uint32_t  dc,
uint32_t *  dd_max 
)

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

Parameters
Atransition probability matrices.
dafirst input difference.
dbsecond input difference.
dcthird input difference.
dd_maxmaximum probability output difference.
Returns
$\mathrm{max}_{dd}~\mathrm{adp}^{\oplus}(da,db,dc \rightarrow dd)$
See Also
max_adp_xor
void max_adp_xor3_i ( const int  i,
const uint32_t  k,
const uint32_t  n,
double *  p,
uint32_t *  dd,
gsl_matrix *  A[2][2][2][2],
gsl_vector *  B[WORD_SIZE+1],
gsl_vector *  C,
const uint32_t  da,
const uint32_t  db,
const uint32_t  dc,
uint32_t *  dd_max,
double *  p_max 
)

Compute an upper bound $B[k][i]$ on the maximum probability of the differential $(da[n-1:k], db[n-1:k], dc[n-1:k] \rightarrow dd[n-1:k])$ starting from initial state i of the S-function given the upper bounds $B[k][i]$ on the probabilities of the differentials $(da[n-1:j], db[n-1:j], dc[n-1:j] \rightarrow dd[n-1:j])$ for $j = k+1, k+2, \ldots, n-1$.

Parameters
iindex of the state of the S-function: A_size $> i \ge 0$.
kcurrent bit position: $ n > k \ge 0$.
nword size.
pthe transition probability of state i at bit position k.
ddoutput difference.
Atransition probability matrices.
Barray of size A_size rows by (n + 1) columns containing upper bounds on the maximum probabilities of all j bit differentials $n \ge j \ge 1$ beginning from any state i: A_size $> i \ge 0$.
Cunit row vector of size A_size rows, initialized with 1 at state index i.
dafirst input difference.
dbsecond input difference.
dcthird input difference.
dd_maxmaximum probability output difference.
p_maxthe maximum probability.
See Also
max_adp_xor_i
double max_adp_xor3_rec ( gsl_matrix *  A[2][2][2][2],
gsl_vector *  C,
const uint32_t  da,
const uint32_t  db,
const uint32_t  dc,
uint32_t *  dd_max 
)

Recursively compute the maximum differential probability over all output differences: $\mathrm{max}_{dd}~\mathrm{adp}^{\oplus}(da,db,dc \rightarrow dd)$. Complexity c: $O(n) \le c \le O(2^n)$.

Parameters
Atransition probability matrices.
Cunit row vector initialized with 1 at the nitial state.
dafirst input difference.
dbsecond input difference.
dcthird input difference.
dd_maxmaximum probability output difference.
Returns
$\mathrm{max}_{dd}~\mathrm{adp}^{\oplus}(da,db,dc \rightarrow dd)$
Note
This function max_adp_xor3_rec is more efficient than exhaustive search over all output differences max_adp_xor3_exper, but is less efficient than the function max_adp_xor3 that uses bounds. The reason is that at every bit position, max_adp_xor3_rec (by max_adp_xor3_rec_i) implicitly assumes that the remaining probability until the end (i.e. until the MSB) is 1, while the bounds computed by max_adp_xor3 are tighter and thus more branches of the recursion are cut earlier in the computation.

See also: max_adp_xor3_i()

void max_adp_xor3_rec_i ( const uint32_t  k,
const uint32_t  n,
double *  p,
uint32_t *  dd,
gsl_matrix *  A[2][2][2][2],
gsl_vector *  C,
const uint32_t  da,
const uint32_t  db,
const uint32_t  dc,
uint32_t *  dd_max,
double *  p_max 
)

Recursively compute the maximum differential probability over all output differences of the partial $(n-k)$-bit differential $\mathrm{max}_{dd}~\mathrm{adp}^{\oplus}(da[n-1:k],db[n-1:k],dc[n-1:k] \rightarrow dd[n-1:k])$.

Parameters
kcurrent bit position: $ n > k \ge 0$.
nword size.
pthe probability at bit position k.
ddoutput difference.
Atransition probability matrices.
Cunit row vector initialized with 1 at the nitial state.
dafirst input difference.
dbsecond input difference.
dcthird input difference.
dd_maxmaximum probability output difference.
p_maxthe maximum probability.

Algorithm Outline:

The function recursively assigns the bits of the output difference starting at the LS bit position $k = 0$ and proceeding to $k+1$ only if the probability so far is still above the maximum that was found up to now. The initial value for the maximum probability p_max is 0 and is updated dynamically during the process every time a higher probability is encountered. The recursion stops at the MSB $k = n$.

See also: max_adp_xor3_rec()