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

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

#include "common.hh"
#include "adp-xor3.hh"
#include "adp-shift.hh"
#include "tea.hh"
#include "eadp-tea-f.hh"
#include "adp-tea-f-fk.hh"

Functions

bool rsh_condition_is_sat (const uint32_t k, const uint32_t new_da, const uint32_t new_dc)
 
bool lsh_condition_is_sat (const uint32_t k, const uint32_t new_da, const uint32_t new_db)
 
void tea_f_add_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][2], gsl_vector *C, uint32_t *da, uint32_t *db, uint32_t *dc, uint32_t *dd, double *p, const double p_thres, std::set< differential_t, struct_comp_diff_dx_dy > *diff_set_dx_dy)
 
void tea_f_add_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)
 
void tea_f_add_pddt_adjust_to_key (uint32_t nrounds, uint32_t npairs, uint32_t key[4], double p_thres, std::set< differential_t, struct_comp_diff_dx_dy > *diff_set_dx_dy)
 
void tea_f_add_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)
 
void tea_f_add_pddt_exper (gsl_matrix *A[2][2][2][2], uint32_t n, double p_thres, uint32_t lsh_const, uint32_t rsh_const, std::multiset< differential_t, struct_comp_diff_p > *diff_mset_p)
 
void tea_f_add_pddt_fk_exper (uint32_t n, double p_thres, uint32_t delta, uint32_t k0, uint32_t k1, uint32_t lsh_const, uint32_t rsh_const, std::multiset< differential_t, struct_comp_diff_p > *diff_mset_p)
 
bool 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 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 tea_f_da_db_dc_add_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][2], gsl_vector *C, const uint32_t da, const uint32_t db, const uint32_t dc, uint32_t *dd, double *p, const double p_thres, uint32_t da_prev, 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, std::multiset< differential_t, struct_comp_diff_p > *diff_mset_p, uint32_t *cnt_new)
 
uint32_t tea_f_da_add_pddt (uint32_t n, double p_thres, uint32_t lsh_const, uint32_t rsh_const, const uint32_t da, const uint32_t da_prev, 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, std::multiset< differential_t, struct_comp_diff_p > *diff_mset_p)
 

Detailed Description

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

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

Function Documentation

bool 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)

bool 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 .

bool lsh_condition_is_sat ( const uint32_t  k,
const uint32_t  new_da,
const uint32_t  new_db 
)

Check if two differences $da$ and $dc$, partially constructed up to bit $k$ (WORD_SIZE $> k \ge 0$), are valid input and output difference respectively, for the LSH operation.

Parameters
kbit position: WORD_SIZE $> k \ge 0$.
new_dainput difference to LSH partially constructed up to bit $k$.
new_dboutput difference from LSH partially constructed up to bit $k$.
Returns
TRUE if $dc$, after being fully constructed, will be a valid output difference from LSH, given the input difference $da$; FALSE otherwise.

More Details:

  1. If $ k < L $: check if $db[k:0] = 0$.
  2. If $k \ge L$: check if $(db \gg L)[n-(k-L+1):0] = da[n-(k-L+1):0]$.

where $L =$TEA_LSH_CONST, $n=$WORD_SIZE.

See Also
rsh_condition_is_sat
bool rsh_condition_is_sat ( const uint32_t  k,
const uint32_t  new_da,
const uint32_t  new_dc 
)

Check if two differences $da$ and $dc$, partially constructed up to bit $k$ (WORD_SIZE $> k \ge 0$), are valid input and output difference respectively, for the RSH operation. From the partial information for $dc$, the algorithm estimates if $dc$ belongs to one of the four possible differences after the RSH operation (see adp_rsh): $\{(da \gg R),~ (da \gg R) + 1,~ (da \gg R) - 2^{n-R},~ (da \gg R) - 2^{n-R} + 1\}$, where $R$ is the RSH constant (TEA_RSH_CONST).

Parameters
kbit position: WORD_SIZE $> k \ge 0$.
new_dainput difference to RSH partially constructed up to bit $k$.
new_dcoutput difference from RSH partially constructed up to bit $k$.
Returns
TRUE if $dc$, after being fully constructed, will be a valid output difference from RSH, given the input difference $da$; FALSE otherwise.
Attention
The function is not optimal, meaning that it is overly-restrictive: all diferences $(da,dc)$ which pass the checks are valid, but there also exist valid differences that do not pass the checks. The reason is that it is hard to detect all valid differences before they have been fully constructed.

More Details:

Given are two differences $da$ and $dc$, that are only partially constructed up to bit $k$ (counting from the LSB $k = 0$). rsh_condition_is_sat performs checks on $da$ and $dc$ and outputs if $dc$ is such that $dc = da \gg R$, where $R$ = TEA_RSH_CONST. The idea is to be able to discard pairs of diferences $(da, dc)$ before they have been fully constructed. This allows to more efficiently constrct a list of valid differentials for the TEA F-function recursively. We use these conditions in tea_f_add_pddt_i to discard invalid entries early in the recursion.

To perform the checks, the following relations are used:

$dc = (da \gg R) \Longrightarrow dc \in \{dc_0, dc_1, dc_2, dc_3\}$ where:

  • $dc_0 = (da \gg R)$.
  • $dc_2 = (da \gg R) - 2^{n-R}$.
  • $dc_1 = (da \gg R) + 1$.
  • $dc_3 = (da \gg R) - 2^{n-R} + 1$.

Depending on the bit position $k$ (some of) the following checks are performed:

  1. If $(k \ge R)$ perform check on the $(k-R)$ LS bits. If $(k >= R)$ we check if the first $(k-R)$ LSB bits of $(da \gg R)$ are equal to the first $(k-R)$ bits of $dc_i,~ 0 \le i < 4$ according to the above equations. So we check if any of the following four equations hold:
    • $(da \gg R)[0:(k - R)] = (dc_0)[0:(k - R)]$.
    • $(da \gg R)[0:(k - R)] = (dc_0 + 2^{n-R})[0:(k - R)]$.
    • $(da \gg R)[0:(k - R)] = (dc_0 - 1)[0:(k - R)]$.
    • $(da \gg R)[0:(k - R)] = (dc_0 + 2^{n-R} - 1)[0:(k - R)]$.
  2. Check that the $R$ LS bits of $da$ are not zero $da[(r-1):0] \neq 0$.
  3. If $(k >= R) \wedge (k > (n - R))$ check the $(n-R)$ MS bits. When $(k > (n - R))$, $(da \gg R)[k] = 0$ and we check the top $(n-R)$ MS bits of $dc$. More specifically, we check if the initial four equations hold for the $(n-R)$ MS bits of the operands:
    • $dc_0[(n-1):(n-R+1)] = (da \gg R)[(n-1):(n-R+1)]$.
    • $dc_1[(n-1):(n-R+1)] = ((da \gg R) + 1)[(n-1):(n-R+1)]$.
    • $dc_2[(n-1):(n-R+1)] = ((da \gg R) - 2^{n-R})[(n-1):(n-R+1)]$.
    • $dc_3[(n-1):(n-R+1)] = ((da \gg R) - 2^{n-R} + 1)[(n-1):(n-R+1)]$.
void tea_f_add_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 a partial DDT (pDDT) for the TEA F-function: wrapper function of tea_f_add_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 TEA_ADD_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.
See Also
tea_f_add_pddt_i.
void tea_f_add_pddt_adjust_to_key ( uint32_t  nrounds,
uint32_t  npairs,
uint32_t  key[4],
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 tea_f_add_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).
keycryptographic key of TEA.
p_thresprobability threshold (TEA_ADD_P_THRES).
diff_set_dx_dyset of differentials (the pDDT) ordered by index $i = (dx~ 2^{n} + dy)$ - smallest first.
void tea_f_add_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 form 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.
void tea_f_add_pddt_exper ( gsl_matrix *  A[2][2][2][2],
uint32_t  n,
double  p_thres,
uint32_t  lsh_const,
uint32_t  rsh_const,
std::multiset< differential_t, struct_comp_diff_p > *  diff_mset_p 
)

Experimentally compute the full DDT of the TEA F-function containining expected probabilities, averaged over all keys and round constants. An exhautive search is performed over all input and output differences. Complexity: $O(2^{2n})$.

Parameters
Atransition probability matrices for $\mathrm{adp}^{3\oplus}$ (adp_xor3_sf).
nword size (default is WORD_SIZE).
p_thresprobability threshold (default is TEA_ADD_P_THRES).
lsh_constLSH constant (TEA_LSH_CONST).
rsh_constRSH constant (TEA_RSH_CONST).
diff_mset_pset of differentials $(dx \rightarrow dy)$ ordered by probability (the DDT).
void tea_f_add_pddt_fk_exper ( uint32_t  n,
double  p_thres,
uint32_t  delta,
uint32_t  k0,
uint32_t  k1,
uint32_t  lsh_const,
uint32_t  rsh_const,
std::multiset< differential_t, struct_comp_diff_p > *  diff_mset_p 
)

Experimentally compute the full DDT of the TEA F-function containining probabilities for a fixed key and round constant. An exhautive search is performed over all input and output differences. Complexity: $O(2^{2n})$.

Parameters
nword size (default is WORD_SIZE).
p_thresprobability threshold (default is TEA_ADD_P_THRES).
deltaround constant.
k0first round key.
k1second round key.
lsh_constLSH constant (TEA_LSH_CONST).
rsh_constRSH constant (TEA_RSH_CONST).
diff_mset_pset of differentials $(dx \rightarrow dy)$ ordered by probability (the DDT).
void tea_f_add_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][2],
gsl_vector *  C,
uint32_t *  da,
uint32_t *  db,
uint32_t *  dc,
uint32_t *  dd,
double *  p,
const double  p_thres,
std::set< differential_t, struct_comp_diff_dx_dy > *  diff_set_dx_dy 
)

Computes a 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 (default is 4).
rsh_constRSH constant (default is 5).
Atransition probability matrices for $\mathrm{adp}^{3\oplus}$ (adp_xor3_sf).
Cunit column vector for computing $ \mathrm{adp}^{3\oplus}$ (adp_xor3).
dafirst input difference to the XOR operation in F.
dbsecond input difference to the XOR operation in F.
dcthird input difference to the XOR operation in F.
ddoutput difference from the XOR operation in F.
pprobability of the partially constructed differential $(da[k:0], db[k:0], dc[k:0] \rightarrow dd[k:0])$.
p_thresprobability threshold (default is TEA_ADD_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.
Attention
The computed pDDT is based on the expected additive differential probability of the TEA F-function (eadp_tea_f), averaged over all round keys and round constants $\delta$ and therefore contains average (as opposed to fixed-key fixed-constants adp_f_fk) probabilities.

Algorithm Outline:

Applies conceptually the same logic as adp_xor_pddt_i. It recursively constructs all differentials for the XOR operation with three inputs $(da, db, dc \rightarrow dd)$, with the additional requirement that they must satisfy the following properties:

  1. $\mathrm{adp}^{3\oplus}(da, db, dc \rightarrow dd) > p_\mathrm{thres}$.
  2. $db = da \ll 4$.
  3. $dc \in {(da \ll R), (da \ll R) + 1, (da \ll R) - 2^{n-R}, (da \ll R) - 2^{n-R} + 1}$, so that $dc = (da \ll R)$ where $R =$TEA_RSH_CONST.

Only the entries for which $\mathrm{eadp}^{F}(da \rightarrow dd) > p_\mathrm{thres}$ are stored.

See Also
adp_xor_pddt_i, lsh_condition_is_sat, rsh_condition_is_sat.
uint32_t tea_f_da_add_pddt ( uint32_t  n,
double  p_thres,
uint32_t  lsh_const,
uint32_t  rsh_const,
const uint32_t  da,
const uint32_t  da_prev,
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,
std::multiset< differential_t, struct_comp_diff_p > *  diff_mset_p 
)

Wrapper for tea_f_da_db_dc_add_pddt_i . Returns the number of new entries that were added .

Parameters
nword size (default is WORD_SIZE).
p_thresprobability threshold (default is TEA_ADD_P_THRES).
lsh_constLSH constant (default is TEA_LSH_CONST).
rsh_constRSH constant (default is TEA_RSH_CONST).
dainput difference to F.
da_previnput difference to the previous round.
hways_diff_set_dx_dyset of differentials $(dx,dy,p)$ (Highways) ordered by index $i = (dx~ 2^{n} + dy)$.
hways_diff_mset_pset of differentials $(dx,dy,p)$ (Highways) ordered by probability p.
diff_set_dx_dyset of differentials $(dx,dy,p)$ (Countryroads) ordered by index $i = (dx~ 2^{n} + dy)$.
diff_mset_ptemporrary set of differentials $(dx,dy,p)$ (Countryroads) ordered by probability p.
Returns
number of output differences that were added to diff_set_dx_dy .
void tea_f_da_db_dc_add_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][2],
gsl_vector *  C,
const uint32_t  da,
const uint32_t  db,
const uint32_t  dc,
uint32_t *  dd,
double *  p,
const double  p_thres,
uint32_t  da_prev,
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,
std::multiset< differential_t, struct_comp_diff_p > *  diff_mset_p,
uint32_t *  cnt_new 
)
Parameters
kcurrent bit position in the recursion.
nword size (default is WORD_SIZE).
lsh_constLSH constant (default is 4).
rsh_constRSH constant (default is 5).
Atransition probability matrices for $\mathrm{adp}^{3\oplus}$ (adp_xor3_sf).
Cunit column vector for computing $ \mathrm{adp}^{3\oplus}$ (adp_xor3).
dafirst input difference to the XOR operation in F.
dbsecond input difference to the XOR operation in F.
dcthird input difference to the XOR operation in F.
ddoutput difference from the XOR operation in F.
pprobability of the partially constructed differential $(da[k:0], db[k:0], dc[k:0] \rightarrow dd[k:0])$.
p_thresprobability threshold (default is TEA_ADD_P_THRES).
da_previnput difference to the previous round.
hways_diff_mset_pset of differentials $(dx,dy,p)$ (Highways) ordered by probability p.
hways_diff_set_dx_dyset of differentials $(dx,dy,p)$ (Highways) ordered by index $i = (dx~ 2^{n} + dy)$.
diff_mset_ptemporrary set of differentials $(dx,dy,p)$ (Countryroads) ordered by probability p.
diff_set_dx_dyset of differentials $(dx,dy,p)$ (Countryroads) ordered by index $i = (dx~ 2^{n} + dy)$.
cnt_newnumber of output differences that were added .

For a fixed input difference $\alpha_r$ to round $r$ compute a list of output differences $\beta_r$ that satisfy the following conditions:

  1. The probability of the differential $(\alpha_r \rightarrow \beta_r)$ is bigger than a pre-defined threshold p_thres .
  2. The input difference $\alpha_{r+1} = \alpha_{r-1} + \beta_{r}$ to the next round has a matching entry in the pre-computed pDDT hways_diff_set_dx_dy.
See Also
tea_f_add_pddt_i , tea_add_threshold_search_full