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

Header file for max-adp-xor3-set.cc. More...

Go to the source code of this file.

Macros

#define ADP_XOR3_SET_SIZE   4
 

Functions

void max_adp_xor3_set_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[ADP_XOR3_SET_SIZE], const uint32_t da, const uint32_t db, const uint32_t dc[ADP_XOR3_SET_SIZE], uint32_t *dd_max, double *p_max)
 
double max_adp_xor3_set (gsl_matrix *A[2][2][2][2], const uint32_t da, const uint32_t db, const uint32_t dc[ADP_XOR3_SET_SIZE], double p_dc[ADP_XOR3_SET_SIZE], uint32_t *dd_max)
 
double max_adp_xor3_set_exper (gsl_matrix *A[2][2][2][2], const uint32_t da, const uint32_t db, const uint32_t dc[ADP_XOR3_SET_SIZE], double p_dc[ADP_XOR3_SET_SIZE], uint32_t *dd_max)
 

Detailed Description

Header file for max-adp-xor3-set.cc.

Author
V.Velichkov, vesse.nosp@m.lin..nosp@m.velic.nosp@m.hkov.nosp@m.@uni..nosp@m.lu
Date
2012-2013

Macro Definition Documentation

#define ADP_XOR3_SET_SIZE   4

Number of input differences in the set.

Function Documentation

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

Compute the maximum differential probability over all output differences for a set of input differenecs: $\max_{dd} \mathrm{adp}^{\oplus}_{\mathrm{SET}}(da, db, \{{dc}_0, {dc}_1, \ldots\} \rightarrow dd)$.

Complexity c: $O(n R) \le c \le O(2^{nR})$, where $R$ is the size of the set of input differences $dc_r$.

Parameters
Atransition probability matrices.
dafirst input difference.
dbsecond input difference.
dcset of input difference.
dd_maxmaximum probability output difference.
p_dcprobabilities of the set of differentials corresponding to the set of differences (used for testing and debug only).
Returns
$\mathrm{max}_{dd}~\mathrm{adp}^{\oplus}_{\mathrm{SET}}(da, db, \{{dc}_0, {dc}_1, \ldots\} \rightarrow dd)$.

Algorithm Outline:

  • Compute the bounds for each of the differences in the set independently using max_adp_xor_bounds i.e. compute $B_{r}[k]$ - the bounds ror the $R$ differentials: $\mathrm{dp}(da[n-1:k],db[n-1:k],dc_r[n-1:k] \rightarrow dd[n-1:k])$ corresponding to the r-th input differences $dc_{r}$ in the set.
  • Compute a single array of bounds $B_{\mathrm{max}}$ as the maximum of the bounds $B_{r}[k]$ at every bit position $0 \le k \le n$ for every S-function state $0 \le i < A_{\mathrm{size}}$: $B_{\mathrm{max}}[k][i] = \mathrm{max}_{r}~B[k][i],~ 0 \le k \le n,~ 0 \le i < A_{\mathrm{size}}$.
  • Call max_adp_xor3_set_i with the array of bounds $B_{\mathrm{max}}[k][i]$ to compute the final maximum probability $\mathrm{max}_{dd}~\mathrm{adp}^{\oplus}_{\mathrm{SET}}$.
See Also
max_adp_xor3_set_i, max_adp_xor_bounds, max_adp_xor
double max_adp_xor3_set_exper ( gsl_matrix *  A[2][2][2][2],
const uint32_t  da,
const uint32_t  db,
const uint32_t  dc[ADP_XOR3_SET_SIZE],
double  p_dc[ADP_XOR3_SET_SIZE],
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.
dcset of input difference.
dd_maxmaximum probability output difference.
p_dcprobabilities of the set of differentials corresponding to the set of differences; normally set to 1 (used for testing and debug only).
Returns
$\mathrm{max}_{dd}~\mathrm{adp}^{\oplus}_{\mathrm{SET}}(da, db, \{{dc}_0, {dc}_1, \ldots\} \rightarrow dd)$.
See Also
max_adp_xor3_set
void max_adp_xor3_set_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[ADP_XOR3_SET_SIZE],
const uint32_t  da,
const uint32_t  db,
const uint32_t  dc[ADP_XOR3_SET_SIZE],
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_0[n-1:k],dc_1[n-1:k],\ldots\} \rightarrow dd[n-1:k])$, starting from initial state i of the S-function and given the upper bounds $B[k][i]$ on the probabilities of the differentials $(da[n-1:j],db[n-1:j],\{dc_0[n-1:j],dc_1[n-1:j],\ldots\} \rightarrow dd[n-1:j])$ for $j = k+1, k+2, \ldots, n-1$, where $\{dc_0[n-1:k],dc_1[n-1:k],\ldots\}$ is a finite set of input differences.

Parameters
iindex of the state of the S-function: A_size $> i \ge 0$.
kcurrent bit position: $ n > k \ge 0$.
nword size.
pthe estimated probability 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.
dcset of input differences.
dd_maxmaximum probability output difference.
p_maxthe maximum probability.

Algorithm Outline:

The bound for the set of differences is computed as the sum of the bounds of the differentials obtained from each of the elements of the set: $B[k][i] = \sum_{r}~B_{r}[k][i]$, where $B_{r}[k][i]$ is an upper bound on the maximum probability of the differential corresponding to the r-th input difference $dc_{r}$ i.e. $\mathrm{dp}(da[n-1:k],db[n-1:k],dc_r[n-1:k] \rightarrow dd[n-1:k])$ computed as in max_adp_xor_i.

See Also
max_adp_xor3_set, max_adp_xor_i