YAARX: Yet Another ARX Toolkit  0.1
 All Data Structures Files Functions Variables Macros Pages
adp-xor-pddt.hh File Reference

Header file for adp-xor-pddt.cc. More...

Go to the source code of this file.

Functions

uint32_t adp_xor_ddt_exper (std::multiset< differential_3d_t, struct_comp_diff_3d_p > *diff_set, double p_thres)
 
void adp_xor_pddt_i (const uint32_t k, const uint32_t n, const double p_thres, gsl_matrix *A[2][2][2], gsl_vector *C, uint32_t *da, uint32_t *db, uint32_t *dc, double *p, std::multiset< differential_3d_t, struct_comp_diff_3d_p > *diff_set)
 
void adp_xor_ddt (uint32_t n, double p_thres)
 

Detailed Description

Function Documentation

void adp_xor_ddt ( uint32_t  n,
double  p_thres 
)

Compute a partial DDT for $\mathrm{adp}^{\oplus}$: wrapper function of adp_xor_pddt_i.

Parameters
nword size.
p_thresprobability threshold.
See Also
adp_xor_pddt_i.
uint32_t adp_xor_ddt_exper ( std::multiset< differential_3d_t, struct_comp_diff_3d_p > *  diff_set,
double  p_thres 
)

Compute a partial DDT for $\mathrm{adp}^{\oplus}$ by exhasutive search over all input and output differences.

Parameters
diff_setset of all differentials with probability not less than the threshold (the pDDT)
p_thresprobability threshold.
Returns
number of elements in the pDDT.
See Also
adp_xor_pddt_i
void adp_xor_pddt_i ( const uint32_t  k,
const uint32_t  n,
const double  p_thres,
gsl_matrix *  A[2][2][2],
gsl_vector *  C,
uint32_t *  da,
uint32_t *  db,
uint32_t *  dc,
double *  p,
std::multiset< differential_3d_t, struct_comp_diff_3d_p > *  diff_set 
)

Recursively compute all ADD differentials $(da, db \rightarrow dc)$ for XOR that have probability $\mathrm{adp^{\oplus}}$ larger than a fixed probability threshold p_thres.

The function works recursively starting from the LS bit k = 0 and terminating at the MS bit n. At every bit position i it assigns values to the i-th bits of the differences da, db, dc and evaluates the probability of the resulting partial (i+1)-bit differential: $(da[i:0], db[i:0] \rightarrow dc[i:0])$. The recursion proceeds only if this probability is not less than the threshold p_thres. When i = n, the differential $(da[n-1:0], db[n-1:0] \rightarrow dc[n-1:0])$ is stored in an STL multiset structure (internally implemented as a Red-Black tree).

The complexity is strongly dependent on the threshold and is worst-case exponential in the word size: $O(2^{3n})$.

Note
If p_thres = 0.0 then the full DDT is computed.
Can be used also to compute all differentials that have non-zero probability by setting p_thres > 0.0 .
For 32 bit words, recommended values for the threshold are p_thres >= 0.5.
Parameters
kcurrent bit position in the recursion.
nword size.
p_thresprobability threshold.
Atransition probability matrices for $\mathrm{adp}^{\oplus}$.
Cunit column vector for computing $\mathrm{adp}^{\oplus}$ (adp_xor).
dafirst input difference.
dbsecond input difference.
dcoutput difference.
pprobability of the differential $(da[k:0], db[k:0] \rightarrow dc[k:0])$.
diff_setset of all differentials with probability not less than the threshold (the pDDT)