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

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

#include "common.hh"
#include "adp-xor.hh"
#include "max-adp-xor.hh"
#include "adp-xor-fi.hh"
#include "max-adp-xor-fi.hh"
#include "adp-shift.hh"
#include "xtea.hh"
#include "adp-xtea-f-fk.hh"
#include "xtea-f-add-pddt.hh"

Functions

void xtea_add_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], gsl_matrix *AA[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)
 
void xtea_add_trail_search (uint32_t key[4], uint32_t round_key[64], uint32_t round_delta[64])
 

Detailed Description

Automatic search for ADD 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

void xtea_add_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],
gsl_matrix *  AA[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 
)

Automatic search for ADD differential trails in block cipher XTEA using pDDT.

Note
For more details on the algorithm see tea_add_threshold_search.
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{adp}^{\oplus}$ (adp_xor_sf).
AAtransition probability matrices for XOR with fixed input $\mathrm{adp}^{\oplus}_{\mathrm{FI}}$ (adp_xor_fixed_input_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_pset of differentials $(dx,dy,p)$ (the pDDT) ordered by probability p.
diff_set_dx_dyset of differentials $(dx,dy,p)$ (the pDDT) ordered by index $i = (dx~ 2^{n} + dy)$.

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.
See Also
tea_add_threshold_search.
void xtea_add_trail_search ( uint32_t  key[4],
uint32_t  round_key[64],
uint32_t  round_delta[64] 
)

Search for ADD 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_add_pddt).
  2. Adjust the probabilities of the pDDT to the round key and constant (adp_xtea_f_approx).
  3. Execute the search for differential trails for $n$ rounds (n = NROUNDS) through a successive application of xtea_add_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]$.
  4. Print the best found trail on $n$ rounds on standrad output and terminate.
See Also
xtea_add_threshold_search, tea_add_trail_search