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

Automatic search for ADD differential trails in TEA using full DDT-s. More...

#include "common.hh"
#include "tea.hh"
#include "adp-tea-f-fk-ddt.hh"

Functions

double verify_trail (uint64_t npairs, differential_t trail[NROUNDS], uint32_t nrounds, uint32_t key[4], uint32_t delta, uint32_t lsh_const, uint32_t rsh_const)
 
void round_ddt (const int n, const int nrounds, differential_t **RSDDT_E, differential_t **RSDDT_O, differential_t *SDDT_O, double B[NROUNDS], double *Bn, const differential_t diff_in[NROUNDS], differential_t trail[NROUNDS])
 
void tea_search_ddt (uint32_t key[4])
 
void round_xddt (const int n, const int nrounds, differential_t ***XRSDDT_E, differential_t ***XRSDDT_O, differential_t **XSDDT_O, const double B[NROUNDS], double *Bn, differential_t diff_in[NROUNDS], differential_t trail[NROUNDS])
 
void tea_search_xddt (uint32_t key[4])
 
void round_xddt_bottom_up (const int n, const int nrounds, differential_t ***XRSDDT_E, differential_t ***XRSDDT_O, differential_t **XSDDT_E, differential_t **XSDDT_O, const double B[NROUNDS], double *Bn, differential_t diff_in[NROUNDS], differential_t trail[NROUNDS])
 
void tea_search_xddt_bottom_up (uint32_t key[4])
 

Detailed Description

Automatic search for ADD differential trails in TEA using full DDT-s.

Author
V.Velichkov, vesse.nosp@m.lin..nosp@m.velic.nosp@m.hkov.nosp@m.@uni..nosp@m.lu
Attention
Exponential complexity in the word size; infeasible for word sizes bigger than $11$ bits. Used only for tests and verification.

Function Documentation

void round_ddt ( const int  n,
const int  nrounds,
differential_t **  RSDDT_E,
differential_t **  RSDDT_O,
differential_t *  SDDT_O,
double  B[NROUNDS],
double *  Bn,
const differential_t  diff_in[NROUNDS],
differential_t  trail[NROUNDS] 
)

Automatic search for ADD differential trails using precomputed full difference distribution tables (DDT) for a modified version of TEA that uses the same round constant $\delta$ in every round.

Attention
  1. Assumes the same $\delta$ constant is used at every round of TEA.
  2. Two DDT-s are computed: DDT_E contains fixed-key probabilities for the round keys applied in all even rounds: $0,2,4,\ldots$; DDT_O contains fixed-key probabilities for the round keys applied in all odd rounds: $1,3,5,\ldots$.
Parameters
nindex of the current round: $0 \le n < \mathrm{nrounds}$.
RSDDT_Ea DDT for the keys of all even rounds $0,2,4,\ldots$ with the elements in each row (i.e. for a fixed input difference) sorted in descending order of their probability (a Row-Sorted DDT_E).
RSDDT_Oa DDT for the keys of all odd rounds $1,3,5,\ldots$ with the elements in each row (i.e. for a fixed input difference) sorted in descending order of their probability (a Row-Sorted DDT_O).
SDDT_Oa DDT for the keys of all odd rounds will all elements sorted in descending order of their probability (a Sorted DDT_O).
nroundstotal number of rounds (NROUNDS).
Barray containing the best differential probabilities for i rounds: $0 \le i < n$.
Bnthe best probability on $n$ rounds, updated dynamically.
diff_inarray of differentials.
trailbest differential trail for nrounds.

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 round_xddt ( const int  n,
const int  nrounds,
differential_t ***  XRSDDT_E,
differential_t ***  XRSDDT_O,
differential_t **  XSDDT_O,
const double  B[NROUNDS],
double *  Bn,
differential_t  diff_in[NROUNDS],
differential_t  trail[NROUNDS] 
)

Automatic search for ADD differential trails using precomputed full difference distribution tables (DDT) for the original version of TEA.

Attention
For every round constant $\delta$, two DDT-s are computed: DDT_E containing the fixed-key fixed- $\delta$ probabilities for the round keys applied in all even rounds: $0,2,4,\ldots$ and DDT_O containing the fixed-key fixed- $\delta$ probabilities for the round keys applied in all odd rounds: $1,3,5,\ldots$. Since $\delta$ is updated every second round, for $N$ rounds $2(N/2)$ DDT-s will be computed.
Parameters
nindex of the current round: $0 \le n < \mathrm{nrounds}$.
nroundstotal number of rounds (NROUNDS).
XRSDDT_Ean array of fixed-key fixed- $\delta$ DDT-s for all even rounds $0,2,4,\ldots$ with the elements in each row (i.e. for a fixed input difference) sorted in descending order of their probability (an eXtended Row-Sorted DDT_E).
XRSDDT_Oan array of fixed-key fixed- $\delta$ DDT-s for all odd rounds $1,3,5,\ldots$ with the elements in each row (i.e. for a fixed input difference) sorted in descending order of their probability (an eXtended Row-Sorted DDT_O).
XSDDT_Oan array of fixed-key fixed- $\delta$ DDT-s for all odd rounds will all elements sorted in descending order of their probability (an eXtended Sorted DDT_O).
Barray containing the best differential probabilities for i rounds: $0 \le i < n$.
Bnthe best probability on $n$ rounds, updated dynamically.
diff_inarray of differentials.
trailbest differential trail for nrounds.

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
round_ddt
void round_xddt_bottom_up ( const int  n,
const int  nrounds,
differential_t ***  XRSDDT_E,
differential_t ***  XRSDDT_O,
differential_t **  XSDDT_E,
differential_t **  XSDDT_O,
const double  B[NROUNDS],
double *  Bn,
differential_t  diff_in[NROUNDS],
differential_t  trail[NROUNDS] 
)

Automatic search for ADD differential trails using precomputed full difference distribution tables (DDT) for the original version of TEA.

round_xddt_bottom_up is conceptually the same as round_xddt, except that the search proceeds from the bottom up i.e. first finds the best 1-round trail for the last round $N$, next finds the best 2-round trail for rounds $N-1, N$, etc. finds the best $i$-round trail for rounds $i, i+1, \ldots, N$ and finally finds the best $N$-round trail.

Attention
For every round constant $\delta$, two DDT-s are computed: DDT_E containing the fixed-key fixed- $\delta$ probabilities for the round keys applied in all even rounds: $0,2,4,\ldots$ and DDT_O containing the fixed-key fixed- $\delta$ probabilities for the round keys applied in all odd rounds: $1,3,5,\ldots$. Since $\delta$ is updated every second round, for $N$ rounds $2(N/2)$ DDT-s will be computed.
Parameters
nindex of the current round: $0 \le n < \mathrm{nrounds}$.
nroundstotal number of rounds (NROUNDS).
XRSDDT_Ean array of fixed-key fixed- $\delta$ DDT-s for all even rounds $0,2,4,\ldots$ with the elements in each row (i.e. for a fixed input difference) sorted in descending order of their probability (an eXtended Row-Sorted DDT_E).
XRSDDT_Oan array of fixed-key fixed- $\delta$ DDT-s for all odd rounds $1,3,5,\ldots$ with the elements in each row (i.e. for a fixed input difference) sorted in descending order of their probability (an eXtended Row-Sorted DDT_O).
XSDDT_Oan array of fixed-key fixed- $\delta$ DDT-s for all odd rounds will all elements sorted in descending order of their probability (an eXtended Sorted DDT_O).
XSDDT_Ean array of fixed-key fixed- $\delta$ DDT-s for all even rounds will all elements sorted in descending order of their probability (an eXtended Sorted DDT_E).
Barray containing the best differential probabilities for i rounds: $0 \le i < n$.
Bnthe best probability on $n$ rounds, updated dynamically.
diff_inarray of differentials.
trailbest differential trail for nrounds.

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

  • $B[0]$: best probability for $n$ rounds.
  • $B[1]$: best probability for $(n-1)$ rounds.
  • $\ldots$
  • $B[i]$: best probability for $(n-i)$ rounds (rounds $n-i, n-i+1, \ldots, n$).
  • $\ldots$
  • $B[n-2]$: best probability for $2$ rounds (rounds $n-1,n$).
  • $B[n-1]$: best probability for $1$ round (round $n$).
See Also
round_xddt
void tea_search_ddt ( uint32_t  key[4])

Search for ADD differential trails in a modified version of block cipher TEA that uses the same round constant $\delta$ in every round. Computes full difference distribution tables (DDT) for every key and the same round constant: a wrapper function for round_ddt.

Parameters
keycryptographic key of TEA.
Attention
Assumes the same $\delta$ constant is used at every round of TEA.
See Also
tea_add_trail_search
void tea_search_xddt ( uint32_t  key[4])

Search for ADD differential trails in the original version of block cipher TEA. Computes full difference distribution tables (DDT) for every key and every round constant: a wrapper function for round_xddt.

Parameters
keycryptographic key of TEA.
See Also
round_xddt
void tea_search_xddt_bottom_up ( uint32_t  key[4])

Search for ADD differential trails in the original version of block cipher TEA. Computes full difference distribution tables (DDT) for every key and every round constant. Conceptually the same as tea_search_xddt, except that the search starts from the last round and proceeds up to the first (i.e. in a bottom-up amnner). This function is a wrapper for round_xddt_bottom_up.

Parameters
keycryptographic key of TEA.
See Also
round_xddt_bottom_up
double verify_trail ( uint64_t  npairs,
differential_t  trail[NROUNDS],
uint32_t  nrounds,
uint32_t  key[4],
uint32_t  delta,
uint32_t  lsh_const,
uint32_t  rsh_const 
)

Experimentally verify the probabilities of the 1-round differentials composing an N-round differential trail for block cipher TEA, against the exact probabilities from a DDT.

Parameters
npairsnumber of chosen plaintext pairs (NPAIRS).
trailbest differential trail for nrounds.
nroundstotal number of rounds (NROUNDS).
keycryptographic key of TEA.
deltaround constant.
lsh_constLSH constant (TEA_LSH_CONST).
rsh_constRSH constant (TEA_RSH_CONST).