YAARX: Yet Another ARX Toolkit  0.1
 All Data Structures Files Functions Variables Macros Pages
Macros | Functions
xtea-f-xor-pddt.cc File Reference

Computing an XOR partial difference distribution table (pDDT) for the F-function of block cipher XTEA. More...

#include "common.hh"
#include "xdp-add.hh"
#include "xtea.hh"
#include "xdp-xtea-f-fk.hh"

Macros

#define RESTRICT_CROADS   1
 

Functions

void xtea_f_xor_pddt_i (const uint32_t k, const uint32_t n, const uint32_t lsh_const, const uint32_t rsh_const, gsl_matrix *A[2][2][2], gsl_vector *C, uint32_t *da, uint32_t *db, uint32_t *dc, double *p, const double p_thres, std::set< differential_t, struct_comp_diff_dx_dy > *diff_set_dx_dy)
 
void xtea_f_xor_pddt (uint32_t n, double p_thres, uint32_t lsh_const, uint32_t rsh_const, std::set< differential_t, struct_comp_diff_dx_dy > *diff_set_dx_dy)
 
bool xtea_is_dx_in_set_dx_dy (uint32_t dy, uint32_t dx_prev, std::set< differential_t, struct_comp_diff_dx_dy > diff_set_dx_dy)
 
bool xtea_is_dx_in_set_dx_dy_mask_i (uint32_t mask_i, const uint32_t dy, const uint32_t dx_prev, std::set< differential_t, struct_comp_diff_dx_dy > diff_set_dx_dy)
 
void xtea_f_da_db_xor_pddt_i (const uint32_t k, const uint32_t n, const uint32_t lsh_const, const uint32_t rsh_const, gsl_matrix *A[2][2][2], gsl_vector *C, const uint32_t da_prev, const uint32_t da, const uint32_t db, uint32_t *dc, double *p, const double p_thres, std::set< differential_t, struct_comp_diff_dx_dy > *hways_diff_set_dx_dy, std::multiset< differential_t, struct_comp_diff_p > *hways_diff_mset_p, std::set< differential_t, struct_comp_diff_dx_dy > *diff_set_dx_dy, uint32_t *cnt_new)
 
uint32_t xtea_f_da_db_xor_pddt (uint32_t n, double p_thres, uint32_t lsh_const, uint32_t rsh_const, const uint32_t da_prev, const uint32_t da_in, std::set< differential_t, struct_comp_diff_dx_dy > *hways_diff_set_dx_dy, std::multiset< differential_t, struct_comp_diff_p > *hways_diff_mset_p, std::set< differential_t, struct_comp_diff_dx_dy > *diff_set_dx_dy)
 
void xtea_xor_pddt_adjust_to_key (uint32_t nrounds, uint32_t npairs, uint32_t lsh_const, uint32_t rsh_const, uint32_t key, uint32_t delta, double p_thres, std::set< differential_t, struct_comp_diff_dx_dy > *diff_set_dx_dy)
 
void xtea_xor_pddt_dxy_to_dp (std::multiset< differential_t, struct_comp_diff_p > *diff_mset_p, const std::set< differential_t, struct_comp_diff_dx_dy > diff_set_dx_dy)
 

Detailed Description

Computing an XOR partial difference distribution table (pDDT) for the F-function of block cipher XTEA.

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

Function Documentation

uint32_t xtea_f_da_db_xor_pddt ( uint32_t  n,
double  p_thres,
uint32_t  lsh_const,
uint32_t  rsh_const,
const uint32_t  da_prev,
const uint32_t  da_in,
std::set< differential_t, struct_comp_diff_dx_dy > *  hways_diff_set_dx_dy,
std::multiset< differential_t, struct_comp_diff_p > *  hways_diff_mset_p,
std::set< differential_t, struct_comp_diff_dx_dy > *  diff_set_dx_dy 
)

Wrapper for xtea_f_da_db_xor_pddt_i

See Also
tea_f_da_add_pddt
void xtea_f_da_db_xor_pddt_i ( const uint32_t  k,
const uint32_t  n,
const uint32_t  lsh_const,
const uint32_t  rsh_const,
gsl_matrix *  A[2][2][2],
gsl_vector *  C,
const uint32_t  da_prev,
const uint32_t  da,
const uint32_t  db,
uint32_t *  dc,
double *  p,
const double  p_thres,
std::set< differential_t, struct_comp_diff_dx_dy > *  hways_diff_set_dx_dy,
std::multiset< differential_t, struct_comp_diff_p > *  hways_diff_mset_p,
std::set< differential_t, struct_comp_diff_dx_dy > *  diff_set_dx_dy,
uint32_t *  cnt_new 
)

Add entries to the pDDT for fixed input diference da and a given prob. threshold. The same as xtea_f_xor_pddt_i, but da is fixed .

See Also
tea_f_da_db_dc_add_pddt_i, xtea_f_xor_pddt_i
void xtea_f_xor_pddt ( uint32_t  n,
double  p_thres,
uint32_t  lsh_const,
uint32_t  rsh_const,
std::set< differential_t, struct_comp_diff_dx_dy > *  diff_set_dx_dy 
)

Compute an XOR partial DDT (pDDT) for the XTEA F-function: wrapper function of xtea_f_xor_pddt_i . By definition a pDDT contains only differentials that have probability above a fixed probability thershold.

Parameters
nword size (default is WORD_SIZE).
p_thresprobability threshold (default is XTEA_XOR_P_THRES).
lsh_constLSH constant (TEA_LSH_CONST).
rsh_constRSH constant (TEA_RSH_CONST).
diff_set_dx_dyset of differentials $(dx \rightarrow dy)$ in the pDDT ordered by index $i = (dx~ 2^{n} + dy)$; stored in an STL set structure, internally implemented as a Red-Black binary search tree.
Note
The compuation of the pDDT is based on the ADD operation in the XTEA F-function: the only non-linear componenet with respect to XOR differences.
See Also
xtea_f_xor_pddt_i.
void xtea_f_xor_pddt_i ( const uint32_t  k,
const uint32_t  n,
const uint32_t  lsh_const,
const uint32_t  rsh_const,
gsl_matrix *  A[2][2][2],
gsl_vector *  C,
uint32_t *  da,
uint32_t *  db,
uint32_t *  dc,
double *  p,
const double  p_thres,
std::set< differential_t, struct_comp_diff_dx_dy > *  diff_set_dx_dy 
)

Computes an ADD partial difference distribution table (pDDT) for the F-function of block cipher TEA.

Parameters
kcurrent bit position in the recursion.
nword size (default is WORD_SIZE).
lsh_constLSH constant (TEA_LSH_CONST).
rsh_constRSH constant (TEA_RSH_CONST).
Atransition probability matrices for ADD $\mathrm{xdp}^{+}$ (xdp_add_sf).
Cunit column vector for computing $\mathrm{xdp}^{+}$ (xdp_add).
dainput difference to the F-function of XTEA.
dboutput difference from the $f_\mathrm{LXR}$ component of F ((xtea_f_lxr)).
dcoutput difference from the F-function of XTEA.
pprobability of the partially constructed differential $(da[k:0], db[k:0] \rightarrow dc[k:0])$ for the ADD operation in F.
p_thresprobability threshold (default is XTEA_XOR_P_THRES).
diff_set_dx_dyset of differentials $(dx \rightarrow dy)$ in the pDDT ordered by index $i = (dx~ 2^{n} + dy)$; stored in an STL set structure, internally implemented as a Red-Black binary search tree.

Algorithm Outline:

  1. Treat the two inputs to the ADD operation: $a$ and $b = ((a << 4) ^ (a >> 5))$ as independent.
  2. Recursively construct a list of differentials $(da, db \rightarrow dc)$ for the ADD operation in F with probability bigger than $p_{\mathrm{thres}}$ (see xdp_add_pddt_i).
  3. Of the constructed differentials store in an pDDT only those for which it holds $db = (da \ll 4) \oplus (da \gg 5)$.
  4. Return pDDT.
See Also
xtea_f_xor_pddt
bool xtea_is_dx_in_set_dx_dy ( uint32_t  dy,
uint32_t  dx_prev,
std::set< differential_t, struct_comp_diff_dx_dy >  diff_set_dx_dy 
)

For a given difference dx, check if in the list of differentials set_dx_dy exists an entry (dx -> dy)

See Also
is_dx_in_set_dx_dy
bool xtea_is_dx_in_set_dx_dy_mask_i ( uint32_t  mask_i,
const uint32_t  dy,
const uint32_t  dx_prev,
std::set< differential_t, struct_comp_diff_dx_dy >  diff_set_dx_dy 
)

Same as is_dx_in_set_dx_dy but on the mask_i LSBs .

See Also
is_dx_in_set_dx_dy_mask_i
void xtea_xor_pddt_adjust_to_key ( uint32_t  nrounds,
uint32_t  npairs,
uint32_t  lsh_const,
uint32_t  rsh_const,
uint32_t  key,
uint32_t  delta,
double  p_thres,
std::set< differential_t, struct_comp_diff_dx_dy > *  diff_set_dx_dy 
)

Adjust the probabailities of the differentials in a pDDT computed with xtea_f_xor_pddt , to the value of a fixed key by performing one-round TEA encryptions over a number of chosen plaintext pairs drawn uniformly at random.

Parameters
nroundstotal number of rounds (NROUNDS).
npairsnumber of chosen plaintext pairs (NPAIRS).
lsh_constLSH constant (TEA_LSH_CONST).
rsh_constRSH constant (TEA_RSH_CONST).
keyround key.
deltaround constant.
p_thresprobability threshold (XTEA_XOR_P_THRES).
diff_set_dx_dyset of differentials $(dx \rightarrow dy)$ in the pDDT ordered by index $i = (dx~ 2^{n} + dy)$.
void xtea_xor_pddt_dxy_to_dp ( std::multiset< differential_t, struct_comp_diff_p > *  diff_mset_p,
const std::set< differential_t, struct_comp_diff_dx_dy >  diff_set_dx_dy 
)

From a pDDT represented in the from of a set of differentials ordered by index, compute a pDDT as a set of differentials ordered by probability.

Parameters
diff_mset_poutput pDDT: set of differentials $(dx \rightarrow dy)$ ordered by probability; stored in an STL multiset structure, internally implemented as a Red-Black binary search tree.
diff_set_dx_dyinput pDDT: set of differentials $(dx \rightarrow dy)$ ordered by index $i = (dx~ 2^{n} + dy)$; stored in an STL set structure, internally implemented as a Red-Black binary search tree.
See Also
xtea_add_pddt_dxy_to_dp