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

Automatic search for XOR differential trails in block cipher XTEA. More...

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

Macros

#define XTEA_P_ADJUST_APPROX   1
 

Functions

double xtea_xor_init_estimate (uint32_t next_round, uint32_t lsh_const, uint32_t rsh_const, uint32_t npairs, gsl_matrix *A[2][2][2], double B[NROUNDS], differential_t trail[NROUNDS], 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 round_key[64], uint32_t round_delta[64])
 
void xtea_xor_threshold_search (const int n, const int nrounds, const uint32_t npairs, const uint32_t round_key[64], const uint32_t round_delta[64], gsl_matrix *A[2][2][2], double B[NROUNDS], double *Bn, const differential_t diff_in[NROUNDS], differential_t trail[NROUNDS], uint32_t lsh_const, uint32_t rsh_const, std::multiset< differential_t, struct_comp_diff_p > *diff_mset_p, std::set< differential_t, struct_comp_diff_dx_dy > *diff_set_dx_dy, uint32_t dxx_init, uint32_t *dxx_init_in)
 
uint32_t xtea_xor_trail_search (uint32_t key[4], uint32_t round_key[64], uint32_t round_delta[64], std::set< differential_t, struct_comp_diff_dx_dy > *diff_set_dx_dy, std::multiset< differential_t, struct_comp_diff_p > *diff_mset_p, double B[NROUNDS], differential_t trail[NROUNDS])
 
void xtea_xor_threshold_search_full (const int n, const int nrounds, const uint32_t npairs, const uint32_t round_key[64], const uint32_t round_delta[64], gsl_matrix *A[2][2][2], double B[NROUNDS], double *Bn, const differential_t diff_in[NROUNDS], differential_t trail[NROUNDS], uint32_t lsh_const, uint32_t rsh_const, std::multiset< differential_t, struct_comp_diff_p > *diff_mset_p, std::set< differential_t, struct_comp_diff_dx_dy > *diff_set_dx_dy, uint32_t dxx_init, uint32_t *dxx_init_in)
 
uint32_t xtea_xor_trail_search_full (uint32_t key[4], uint32_t round_key[64], uint32_t round_delta[64], std::set< differential_t, struct_comp_diff_dx_dy > diff_set_dx_dy, std::multiset< differential_t, struct_comp_diff_p > diff_mset_p, double BB[NROUNDS], differential_t trail[NROUNDS])
 

Detailed Description

Automatic search for XOR differential trails in block cipher XTEA.

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

Function Documentation

double xtea_xor_init_estimate ( uint32_t  next_round,
uint32_t  lsh_const,
uint32_t  rsh_const,
uint32_t  npairs,
gsl_matrix *  A[2][2][2],
double  B[NROUNDS],
differential_t  trail[NROUNDS],
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  round_key[64],
uint32_t  round_delta[64] 
)

Compute an initial estimate of the probability of a differential trail on $(n+1)$ rounds, by greedily extending the best found trail for $n$ rounds.

Parameters
next_roundindex of round $(n+1)$ to which a trail on $n$ rounds will be extended.
lsh_constLSH constant (TEA_LSH_CONST).
rsh_constRSH constant (TEA_RSH_CONST).
npairsnumber of chosen plaintext pairs (NPAIRS).
Atransition probability matrices for $\mathrm{xdp}^{+}$ (xdp_add_sf).
Barray containing the best differential probabilities for i rounds: $0 \le i < n$.
trailbest found differential trail for n rounds.
diff_set_dx_dypDDT as a set of differentials $(dx,dy,p)$ ordered by index $i = (dx~ 2^{n} + dy)$.
round_keyall round keys for the full XTEA.
round_deltaall round constants for the full XTEA.
See Also
xtea_xor_trail_search
void xtea_xor_threshold_search ( const int  n,
const int  nrounds,
const uint32_t  npairs,
const uint32_t  round_key[64],
const uint32_t  round_delta[64],
gsl_matrix *  A[2][2][2],
double  B[NROUNDS],
double *  Bn,
const differential_t  diff_in[NROUNDS],
differential_t  trail[NROUNDS],
uint32_t  lsh_const,
uint32_t  rsh_const,
std::multiset< differential_t, struct_comp_diff_p > *  diff_mset_p,
std::set< differential_t, struct_comp_diff_dx_dy > *  diff_set_dx_dy,
uint32_t  dxx_init,
uint32_t *  dxx_init_in 
)

Automatic search for XOR differential trails in block cipher TEA. using pDDT.

Parameters
nindex of the current round: $0 \le n < \mathrm{nrounds}$.
nroundstotal number of rounds (NROUNDS).
npairsnumber of chosen plaintext pairs (NPAIRS).
round_keyall round keys for the full XTEA.
round_deltaall round constants for the full XTEA.
Atransition probability matrices for $\mathrm{xdp}^{+}$ (xdp_add_sf).
Barray containing the best differential probabilities for i rounds: $0 \le i < n$.
Bnthe best found probability on $n$ rounds, updated dynamically.
diff_inarray of differentials.
trailbest found differential trail for nrounds.
lsh_constLSH constant (TEA_LSH_CONST).
rsh_constRSH constant (TEA_RSH_CONST).
diff_mset_ppDDT as a set of differentials $(dx,dy,p)$ ordered by probability p.
diff_set_dx_dypDDT as a set of differentials $(dx,dy,p)$ ordered by index $i = (dx~ 2^{n} + dy)$.
dxx_initinitial left input difference to XTEA
dxx_init_inthe initial left input difference to XTEA corresponding to the best found trail (initialized to dxx_init and updated dynamically).
Attention
The pDDT contains differentials and their probabilities for the XTEA F-function $F$ (xtea_f) as opposed to the function $F'$ (xtea_f2) that also includes the second ADD operation. In other words, the pDDT does not take into account the differential probabilities arising from the second ADD operation. The latter are computed during the search.

The outline of the array of bounds $B$ is the following:

  • $B[0]$: best probability for $1$ round.
  • $B[1]$: best probability for $2$ rounds.
  • $\ldots$
  • $B[i]$: best probability for $(i+1)$ rounds.
  • $\ldots$
  • $B[n-2]$: best probability for $(n-1)$ rounds.
  • $B[n-1]$: best probability for $n$ rounds.

More Details

The differential probability (DP) for one round of XTEA is computed as the product of the DP of $F$ (xtea_f) and the DP of the modular addition in F' (xtea_f2). The functions $F$ and $F'$ are defined as: $F(x) = y = x + ((x \ll 4) \oplus (x \gg 5))$, $ F'(xx, x) = yy = xx + (y \oplus (\delta + \mathrm{key}))$. Thus the DP of one round of XTEA is essentiallly the DP of $F'$ and is approximated as:

$\mathrm{xdp}^{F'}(dxx, dx \rightarrow dyy) = \mathrm{xdp}^{F}(dx \rightarrow dy) \cdot \mathrm{xdp}^{+}(dy, dxx \rightarrow dyy)$.

Attention
The pDDT contais entries of the form $(dx,~ dy,~ \mathrm{xdp}^{F}(dx \rightarrow dy))$. However, every entry in the arrays of differentials trail and diff_in contains elements of the form: $(dx,~ dyy,~ \mathrm{xdp}^{F'}(dxx, dx \rightarrow dyy))$. Although trail and dif_in do not contain the difference $dxx$, the latter can be easily computed noting that $dxx = dx_{-1}$, where $dx_{-1}$ is the input difference to $F$ from the previous round.

For more details on the search algorithm see tea_add_threshold_search .

See Also
xtea_xor_trail_search
void xtea_xor_threshold_search_full ( const int  n,
const int  nrounds,
const uint32_t  npairs,
const uint32_t  round_key[64],
const uint32_t  round_delta[64],
gsl_matrix *  A[2][2][2],
double  B[NROUNDS],
double *  Bn,
const differential_t  diff_in[NROUNDS],
differential_t  trail[NROUNDS],
uint32_t  lsh_const,
uint32_t  rsh_const,
std::multiset< differential_t, struct_comp_diff_p > *  diff_mset_p,
std::set< differential_t, struct_comp_diff_dx_dy > *  diff_set_dx_dy,
uint32_t  dxx_init,
uint32_t *  dxx_init_in 
)

Full threshold search.

uint32_t xtea_xor_trail_search ( uint32_t  key[4],
uint32_t  round_key[64],
uint32_t  round_delta[64],
std::set< differential_t, struct_comp_diff_dx_dy > *  diff_set_dx_dy,
std::multiset< differential_t, struct_comp_diff_p > *  diff_mset_p,
double  B[NROUNDS],
differential_t  trail[NROUNDS] 
)

Search for XOR differential trails in block cipher XTEA: wrapper function for tea_add_threshold_search.

Parameters
keycryptographic key of XTEA.
round_keyall round keys for the full XTEA.
round_deltaall round constants for the full XTEA.

Algorithm Outline:

The procedure operates as follows:

  1. Compute a pDDT for F (xtea_f_xor_pddt).
  2. Execute the search for differential trails for $n$ rounds (n = NROUNDS) through a successive application of xtea_xor_threshold_search :
    • Compute the best found probability on 1 round: $B[0]$.
    • Using $B[0]$ compute the best found probability on 2 rounds: $B[1]$.
    • $\ldots$
    • Using $B[0],\ldots,B[i-1]$ compute the best found probability on $(i+1)$ rounds: $B[i]$.
    • $\ldots$
    • Using $B[0],\ldots,B[n-2]$ compute the best found probability on $n$ rounds: $B[n-1]$.
  3. Print the best found trail on $n$ rounds on standrad output and terminate.
See Also
xtea_xor_threshold_search
uint32_t xtea_xor_trail_search_full ( uint32_t  key[4],
uint32_t  round_key[64],
uint32_t  round_delta[64],
std::set< differential_t, struct_comp_diff_dx_dy >  diff_set_dx_dy,
std::multiset< differential_t, struct_comp_diff_p >  diff_mset_p,
double  BB[NROUNDS],
differential_t  trail[NROUNDS] 
)

Full threshold search using xtea_xor_threshold_search_full