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

Computing the full difference distribution table (DDT) for the F-function of block cipher TEA by exaustive search over all inputs. Complexity $O(2^{2n})$. More...

#include "common.hh"
#include "tea.hh"

Functions

void ddt_sort_rows (differential_t **T)
 
bool comp_rows (differential_t *a, differential_t *b)
 
void ddt_sort_first_col (differential_t **T)
 
void ddt_to_list (uint32_t **DDT, differential_t *SDDT)
 
void ddt_to_diff_struct (uint32_t **DDT, differential_t **SDDT)
 
void ddt_sort (differential_t *SDDT)
 
void print_rsddt (differential_t **RSDDT)
 
void print_sddt (differential_t *SDDT)
 
double adp_f_exper_fixed_key_all (const uint32_t da, const uint32_t db, const uint32_t k0, const uint32_t k1, const uint32_t delta, uint32_t lsh_const, uint32_t rsh_const)
 
double max_adp_f_exper_fixed_key_all (const uint32_t da, uint32_t *db, const uint32_t k0, const uint32_t k1, const uint32_t delta, uint32_t lsh_const, uint32_t rsh_const)
 
differential_t ** rsddt_alloc ()
 
void rsddt_free (differential_t **T)
 
differential_tsddt_alloc ()
 
void sddt_free (differential_t *ST)
 
uint32_t ** ddt_alloc ()
 
void ddt_free (uint32_t **T)
 
void ddt_f (uint32_t **T, uint32_t k0, uint32_t k1, uint32_t delta, uint32_t lsh_const, uint32_t rsh_const)
 
void ddt_print (uint32_t **T)
 
double adp_f_ddt (uint32_t **DDT, uint32_t dx, uint32_t dy)
 
double max_adp_f_ddt (uint32_t **DDT, uint32_t dx, uint32_t *dy)
 
double max_adp_f_rsddt (differential_t **TS, uint32_t dx, uint32_t *dy)
 
uint32_t *** xddt_alloc ()
 
void xddt_free (uint32_t ***T)
 
differential_t *** xrsddt_alloc ()
 
void xrsddt_free (differential_t ***T)
 
differential_t ** xsddt_alloc ()
 
void xsddt_free (differential_t **ST)
 

Detailed Description

Computing the full difference distribution table (DDT) for the F-function of block cipher TEA by exaustive search over all inputs. Complexity $O(2^{2n})$.

Author
V.Velichkov, vesse.nosp@m.lin..nosp@m.velic.nosp@m.hkov.nosp@m.@uni..nosp@m.lu
Date
2012-2013 All functions in this file have exponential complexity in the word size. They are useful only for verifying other computations on small word sizes, typically $n \le 10$.

Function Documentation

double adp_f_ddt ( uint32_t **  DDT,
uint32_t  dx,
uint32_t  dy 
)

Compute the ADD differential probability of the TEA F-function from the full DDT, precomputed for a a fixed key and round constant.

Parameters
DDTDDT.
dxinput difference.
dyoutput difference.
Returns
DDT[da][db] = $\mathrm{adp}^{F}(k_0, k_1, \delta |~ da \rightarrow dd)$.
See Also
adp_f_exper_fixed_key_all
double adp_f_exper_fixed_key_all ( const uint32_t  da,
const uint32_t  db,
const uint32_t  k0,
const uint32_t  k1,
const uint32_t  delta,
uint32_t  lsh_const,
uint32_t  rsh_const 
)

Compute the ADD differential probability of the TEA F-function for a fixed key and round constants ( $\mathrm{adp}^{F}(k_0, k_1, \delta |~ da \rightarrow dd)$) by exhaustive searc over all inputs. Complexity $O(2^n)$.

Parameters
dainput difference.
dboutput difference.
k0first round key.
k1second round key.
deltaround constant.
lsh_constLSH constant.
rsh_constRSH constant.
Returns
$\mathrm{adp}^{F}(k_0, k_1, \delta |~ da \rightarrow dd)$.
bool comp_rows ( differential_t a,
differential_t b 
)

Compare two rows in a row-sorted DDT by their first (max) element. Assumes that the elemnets in a row are sorted in descending order.

Parameters
arow of differentials in a DDT.
brow of differentials in a DDT.
uint32_t** ddt_alloc ( )

Allocate memory for a DDT as a 2D array containingg number of rigt pairs.

Returns
a DDT as a 2D array containing number of rigt pairs.
See Also
ddt_free
void ddt_f ( uint32_t **  T,
uint32_t  k0,
uint32_t  k1,
uint32_t  delta,
uint32_t  lsh_const,
uint32_t  rsh_const 
)

Compute the full difference distribution table (DDT) for the F-function of block cipher TEA for a fixed key and round constant, by exaustive search over all input values and differences. Complexity $O(2^{2n})$.

Parameters
Ta DDT as a 2D array containing number of right pairs..
k0first round key.
k1second round key.
deltaround constant.
lsh_constLSH constant.
rsh_constRSH constant.
Returns
full DDT for the TEA F-function.
void ddt_free ( uint32_t **  T)

Free the memory reserved for a DDT as a 2D array containingg number of rigt pairs.

Parameters
Ta DDT as a 2D array containing number of rigt pairs.
See Also
ddt_alloc
void ddt_print ( uint32_t **  T)

Print the entries of a DDT.

Parameters
TDDT.
void ddt_sort ( differential_t SDDT)

Sort all elements of a DDT, represented as a 1D list of differentials, in descending order by the number of right pairs.

Parameters
SDDTDDT as a 1D list of differentials.
void ddt_sort_first_col ( differential_t **  T)

Sorts the rows of a difference distribution table (DDT) 2D by the probability of the elements in the first column – highest probability first.

Parameters
Ta difference distribution table (DDT).
void ddt_sort_rows ( differential_t **  T)

Sort every row by decreasing number of right pairs.

Parameters
Ta difference distribution table (DDT).
void ddt_to_diff_struct ( uint32_t **  DDT,
differential_t **  SDDT 
)

Convert a DDT to 2D array of differentials.

Parameters
DDTdifference distribution table.
SDDTarray differentials.
void ddt_to_list ( uint32_t **  DDT,
differential_t SDDT 
)

Convert a DDT to a list of differentials.

Parameters
DDTdifference distribution table.
SDDTlist of differentials.
double max_adp_f_ddt ( uint32_t **  DDT,
uint32_t  dx,
uint32_t *  dy 
)

For a fixed input difference to the TEA F-function compute the maximum probability output ADD difference from the full DDT, precomputed for a fixed key and round constant. Complexity $O(1)$.

Parameters
DDTDDT.
dxinput difference.
dymaximum probability output difference.
Returns
$\max_{dd} \mathrm{adp}^{F}(k_0, k_1, \delta |~ dx \rightarrow dy)$.
See Also
max_adp_f_exper_fixed_key_all
double max_adp_f_exper_fixed_key_all ( const uint32_t  da,
uint32_t *  db,
const uint32_t  k0,
const uint32_t  k1,
const uint32_t  delta,
uint32_t  lsh_const,
uint32_t  rsh_const 
)

For a fixed input difference to the TEA F-function compute the maximum probability output ADD difference for a fixed key and round constant by exhaustive search over all inputs and output differences. Complexity $O(2^{2n})$.

Parameters
dainput difference.
dboutput difference.
k0first round key.
k1second round key.
deltaround constant.
lsh_constLSH constant.
rsh_constRSH constant.
Returns
$\max_{dd} \mathrm{adp}^{F}(k_0, k_1, \delta |~ da \rightarrow dd)$.
See Also
max_adp_f_ddt, max_adp_f_rsddt
double max_adp_f_rsddt ( differential_t **  TS,
uint32_t  dx,
uint32_t *  dy 
)

For a fixed input difference to the TEA F-function compute the maximum probability output ADD difference from the full DDT represented as a 2D array of differentials. In this DDT the differentials in every row are sorted by decreasing probability. Complexity $O(1)$.

Parameters
TSa DDT in which the differentials in every row are sorted by decreasing number of probability.
dxinput difference.
dymaximum probability output difference.
Returns
TS[dx][0] = $\max_{dd} \mathrm{adp}^{F}(k_0, k_1, \delta |~ dx \rightarrow dy)$.
See Also
max_adp_f_ddt, max_adp_f_exper_fixed_key_all
void print_rsddt ( differential_t **  RSDDT)

Print the elements of a DDT.

Parameters
RSDDTDDT as a 2D list of differentials.
void print_sddt ( differential_t SDDT)

Print the elements of a DDT.

Parameters
SDDTDDT as a 1D list of differentials.
differential_t** rsddt_alloc ( )

Allocate memory for a DDT as a 2D array of differentials.

Returns
a DDT as a 2D array of differentials.
See Also
rsddt_free
void rsddt_free ( differential_t **  T)

Free the memory reserved for a DDT as a 2D array of differentials.

Parameters
Ta DDT as a 2D array of differentials.
See Also
rsddt_alloc
differential_t* sddt_alloc ( )

Allocate memory for a DDT as a 1D array of differentials.

Returns
a DDT as a 1D array of differentials.
See Also
sddt_free
void sddt_free ( differential_t ST)

Free the memory reserved for a DDT as a 1D array of differentials.

Parameters
STa DDT as a 1D array of differentials.
See Also
sddt_alloc
uint32_t*** xddt_alloc ( )

Allocate memory for a an array of NDELTA DDTs. Each DDT represents a 2D array containing numbers of rigt right pairs and generated for a fixed value of the $\delta$ constant of the TEA F-function.

Returns
array of DDTs: each DDT represents a 2D array containing number of right pairs.
void xddt_free ( uint32_t ***  T)

Free the memory reserved from a previous call to xddt_alloc()

Parameters
Tan array of DDTs: each DDT is a 2D array containing number of right pairs.
differential_t*** xrsddt_alloc ( )

Allocate memory for a an array of NDELTA DDTs. Each DDT represents a 2D array of differentials, generated for a fixed value of the $\delta$ constant of the TEA F-function.

Returns
array of DDTs: each DDT represents a 2D array of differentials.
void xrsddt_free ( differential_t ***  T)

Free the memory reserved from a previous call to xrsddt_alloc()

Parameters
Tan array of DDTs: each DDT is a 2D array of differentials.
differential_t** xsddt_alloc ( )

Allocate memory for a an array of NDELTA DDTs. Each DDT represents a 1D list of differentials, generated for a fixed value of the $\delta$ constant of the TEA F-function.

Returns
array of DDTs: each DDT represents a 1D list of differentials,
void xsddt_free ( differential_t **  ST)

Free the memory reserved from a previous call to xrsddt_free()

Parameters
STan array of DDTs: each DDT is a 1D list of differentials.