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

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

#include "common.hh"
#include "adp-xor3.hh"
#include "tea.hh"
#include "eadp-tea-f.hh"
#include "tea-f-add-pddt.hh"

Functions

uint32_t tea_add_threshold_count_lp (differential_t trail[NROUNDS], uint32_t trail_len, double p_thres)
 
void tea_add_threshold_search (const int n, const int nrounds, const uint32_t npairs, const uint32_t key[4], gsl_matrix *A[2][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)
 
bool tea_add_is_trail_in_vector (differential_t trail[NROUNDS], std::vector< std::array< differential_t, NROUNDS >> trail_vec)
 
void tea_add_threshold_search_full (const int n, const int nrounds, const uint32_t npairs, const uint32_t key[4], gsl_matrix *A[2][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, std::multiset< differential_t, struct_comp_diff_p > *croads_diff_mset_p, std::set< differential_t, struct_comp_diff_dx_dy > *croads_diff_set_dx_dy, std::vector< std::array< differential_t, NROUNDS >> *trail_vec)
 
uint32_t tea_add_trail_search (uint32_t key[4], double B[NROUNDS], differential_t trail[NROUNDS])
 
uint32_t tea_add_trail_search_full (uint32_t key[4], double BB[NROUNDS], differential_t trail[NROUNDS], uint32_t num_rounds)
 

Detailed Description

Automatic search for ADD differential trails in block cipher TEA.

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

Function Documentation

uint32_t tea_add_threshold_count_lp ( differential_t  trail[NROUNDS],
uint32_t  trail_len,
double  p_thres 
)

Count the number of differentials in a trail that have probabilities below a given threshold.

Parameters
traila differential trail for trail_len rounds.
trail_lenlength of the differential trail.
p_thresprobability threshold.
void tea_add_threshold_search ( const int  n,
const int  nrounds,
const uint32_t  npairs,
const uint32_t  key[4],
gsl_matrix *  A[2][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 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).
keycryptographic key of TEA.
Atransition probability matrices for $\mathrm{adp}^{3\oplus}$ (adp_xor3_sf).
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 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.

Algorithm Outline:

The algorithm is based on Matsui search strategy described in [Sect. 4, Matsui, On correlation between the order of S-boxes and the strength of DES, EUROCRYPT'94]. The main idea is to view the F-function of TEA as an S-box for which a partial difference distribution table (pDDT) is constructed (tea_f_add_pddt). Then a recursive search for differential trails over a given number of rounds $n \ge 1$ is performed. From knowledge of the best probabilities $B_{1}, B_{2}, \ldots, B_{n-1}$ for the first $(n-1)$ rounds and an initial estimate ${\overline B_n}$ for the probability for $n$ rounds the best probability $B_{n}$ for $n$ rounds is derived. Note that for the estimate the following must hold: ${\overline B_n} \leq B_n$.

In addition to Matsui's notation for the probability of the best $n$-round trail $B_n$ and of its estimation ${\overline B_n}$ we introduce ${\widehat B_n}$ to denote the probability of the best found trail for $n$ rounds: ${\overline B_n} \leq {\widehat B_n} \leq B_n$. Given a pDDT $D$ of maximum size $m$, an estimation for the best $n$-round probability ${\overline B_n}$ with its corresponding $n$-round differential trail ${\overline T}$ and the probabilities ${{\widehat B_1}, {\widehat B_2}, \ldots, {\widehat B_{n-1}}}$ of the best found trails for the first $(n - 1)$ rounds, tea_add_threshold_search outputs an $n$-round trail ${\widehat T}$ that has probability ${\widehat{B_n}} \ge {\overline B_n}$.

tea_add_threshold_search operates by recursively extending a trail for $i$ rounds to $(i+1)$ rounds, beginning with $i = 1$ and terminating at $i = n$. This is done by exploring multiple differential trails constructed from the entries of the pDDT $D$ at every round. If, in the process, a differential that is not already in $D$ is encountered it is added to $D$, provided that the maximum size $m$ has not been reached. The recursion at level $i$ continues to level $(i+1)$ only if the probability of the constructed $i$-round trail multiplied by the probability of the best found trail for $(n - i)$ rounds is at least ${\overline B_n}$ i.e. if, $p_1 p_2 \ldots p_i\, {\widehat B_{n - i}} \ge {\overline B_n}$ holds. For $i = n$ the last equation is equivalent to: $p_1 p_2 \ldots p_n = {\widehat B_{n}} \ge {\overline B_n}$. If the latter holds, the initial estimate is updated with the new: ${\overline B_n} \gets {\widehat B_{n}}$ and the corresponding trail is also updated accordingly: ${\overline T_n} \gets {\widehat T_{n}}$. Upon termination the best found trail ${\widehat T_{n}}$ and its probability ${\widehat{B_n}}$ are returned as result.

Attention
In the process of the search if an input differences $\alpha$ is encountered for which a corresponding output difference $\beta$ is not found in the pDDT (i.e. the differential $(\alpha \rightarrow \beta_i)$ is not in the pDDT for no $i$), then an arbitarary non-zero probability output differnece $\beta$ is computed with the nz_eadp_tea_f procedure . See also tea_add_threshold_search_full where a more extensive search over the space of possible output differences $\beta$ is performed in this case.

Termination

The algorithm terminates when one of the following two events happens first:

  1. The initial estimate ${\overline B_n}$ can not be improved further.
  2. The maximum size $m$ of the pDDT $D$ is reached and all differentials in $D$ in every round have been explored.

Complexity

The complexity of tea_add_threshold_search depends on the following factors:

  1. The closeness of the best found probabilities ${{\widehat B_1}, {\widehat B_2}, \ldots, {\widehat B_{n-1}}}$ for the first $(n - 1)$ rounds to the actual best probabilities.
  2. The tightness of the initial estimate ${\overline B_n}$.
  3. The number of elements in $D$. The latter is determined by the probability threshold used to compute $D$ and by the maximum number of elements $m$ allowed.

In the worst-case, in every round, except the last, $m$ iterations will be executed. Therefore the worst-case complexity is $\mathcal{O}(m^{n-1})$, where $n$ is the number of rounds. Although the algorithm is worst-case exponential in the number of rounds, it is much more efficient in practice.

Attention
The algorithm does not guarantee to find the best trail.
Note
The pDDT of TEA contains the expected differential probabilities of F averaged over all keys and round constants. To obtain better estimate of the probabilities of trails for a fixed key and round constants, in the process of the search the probability of each differential is additionally adjusted to the value of the round key and constant by performing one-round encryptions over npairs pairs of chosen plaintexts.
See Also
tea_add_threshold_search_full
void tea_add_threshold_search_full ( const int  n,
const int  nrounds,
const uint32_t  npairs,
const uint32_t  key[4],
gsl_matrix *  A[2][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,
std::multiset< differential_t, struct_comp_diff_p > *  croads_diff_mset_p,
std::set< differential_t, struct_comp_diff_dx_dy > *  croads_diff_set_dx_dy,
std::vector< std::array< differential_t, NROUNDS >> *  trail_vec 
)

Full threshold search for ADD differential trails in block cipher TEA, that uses initial bounds pre-computed with 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).
keycryptographic key of TEA.
Atransition probability matrices for $\mathrm{adp}^{3\oplus}$ (adp_xor3_sf).
Barray of initial bounds pre-computed with tea_add_threshold_search .
Bnthe best 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)$ (Highways) ordered by probability p.
diff_set_dx_dyset of differentials $(dx,dy,p)$ (Highways) ordered by index $i = (dx~ 2^{n} + dy)$.
croads_diff_mset_ptemporrary set of differentials $(dx,dy,p)$ (Countryroads) ordered by probability p.
croads_diff_set_dx_dyset of differentials $(dx,dy,p)$ (Countryroads) ordered by index $i = (dx~ 2^{n} + dy)$.

Algorithm Outline:

The high-level logic of the algorithm is conceptually the same as tea_add_threshold_search . The main difference is in the way it handles the case when an input difference $\alpha$ is encountered for which a corresponding output difference $\beta$ is not found in the pre-computed pDDT. In this case a list of many possible output differences is computed and is explored during the search. More deatiled explanation follows.

Let $\alpha_r$ be an input difference to round $r$ such that the differential $(\alpha_r \rightarrow \beta_i)$ is not in the pDDT for no value of $i$. In this case the algorithm uses tea_f_da_add_pddt to compute all differences $\beta_i$ that satisfy the following conditions:

  1. The differential $(\alpha_r \rightarrow \beta_i)$ is such that its probability $p_r$ can still improve the probability of the best found trail for the given number of rounds i.e. $p_r \ge {{\overline B_n}}/{(p_1 p_2 \cdots p_{r-1} {\widehat B_{n-r}})}$.
  2. The output difference $\beta_i$ is such that it guarantees that the input difference for the next round $\alpha_{r+1} = \alpha_{r-1} + \beta_{i}$ will have a matching entry in the pre-computed pDDT. This condition guarantees that the resulting output difference $\alpha_{r+1}$ for the next round will have a matching output differences $\beta_{r+1}$ in the initial pDDT.

All differentials $(\alpha_r, \beta_r, p_r)$ computed according to the above rules are stored in a temporary pDDT. The differentials in this pDDT are explored during the next stages of the search togeter with the differentials from the initial pDDT.

The Highways and Countryroads Analogy

Denote the temporary pDDT constructed as explained above by $C$ and the initial pDDT that is pre-computed at the start of the search by $ H $. Then the two tables $ H $ and $C$ can be thought of as lists of highways and countryroads on a road map. The differentials contained in $H$ have high probabilities w.r.t. to the fixed probability threshold and correspond therefore to fast roads such as highways. Analogously, the differentials in $C$ have low probabilities and can be seen as slow roads or countryroads. To continue this analogy, the problem of finding a high probability differential trail for $n$ rounds can be seen as a problem of finding a fast route between points $1$ and $n$ on the map. Clearly such a route must be composed of as many highways as possible. Condition (2), mentioned above, essentially guarantees that any country road that we may take in our search for a fast route will bring us back on a highway. Note that it is possible that the fastest route contains two or more country roads in sequence. While such a case will be missed, it may be accounted for by lowering the initial probability threshold.

Full Threshold Search Pseudo-Code

threshold-search.png
Full Threshold Search Pseudo-Code
See Also
tea_add_threshold_search
uint32_t tea_add_trail_search ( uint32_t  key[4],
double  B[NROUNDS],
differential_t  trail[NROUNDS] 
)

Search for ADD differential trails in block cipher TEA: wrapper function for tea_add_threshold_search.

Parameters
keycryptographic key of TEA.
Barray of bounds.
trailbest found differential trail.

Algorithm Outline:

The procedure operates as follows:

  1. Compute a pDDT for F (tea_f_add_pddt).
  2. Adjust the probabilities of the pDDT to the round key and constant (tea_f_add_pddt_adjust_to_key).
  3. Execute the search for differential trails for $n$ rounds (n = NROUNDS) through a successive application of tea_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
tea_add_threshold_search
uint32_t tea_add_trail_search_full ( uint32_t  key[4],
double  BB[NROUNDS],
differential_t  trail[NROUNDS],
uint32_t  num_rounds 
)

Full threshold search using bounds pre-computed with tea_add_trail_search ; basically a wrapper function for tea_add_threshold_search_full .

Parameters
keycryptographic key of TEA.
BBarray of bounds.
trailbest found differential trail.

The function takes as input an array of initial bounds B and the corresponding best found trail, computed with a prior call to tea_add_trail_search and outputs a trail that is at least as good as the niput.

See Also
tea_add_threshold_search_full