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_t *	sddt_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

DDT	DDT.
dx	input difference.
dy	output 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

da	input difference.
db	output difference.
k0	first round key.
k1	second round key.
delta	round constant.
lsh_const	LSH constant.
rsh_const	RSH 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

a	row of differentials in a DDT.
b	row 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

T	a DDT as a 2D array containing number of right pairs..
k0	first round key.
k1	second round key.
delta	round constant.
lsh_const	LSH constant.
rsh_const	RSH 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

T	a 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

T DDT.

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

SDDT	DDT 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

T	a difference distribution table (DDT).

void ddt_sort_rows ( differential_t ** T )

Sort every row by decreasing number of right pairs.

Parameters

T	a difference distribution table (DDT).

void ddt_to_diff_struct	(	uint32_t **	DDT,
		differential_t **	SDDT
	)

Convert a DDT to 2D array of differentials.

Parameters

DDT	difference distribution table.
SDDT	array differentials.

void ddt_to_list	(	uint32_t **	DDT,
		differential_t *	SDDT
	)

Convert a DDT to a list of differentials.

Parameters

DDT	difference distribution table.
SDDT	list 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

DDT	DDT.
dx	input difference.
dy	maximum 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

da	input difference.
db	output difference.
k0	first round key.
k1	second round key.
delta	round constant.
lsh_const	LSH constant.
rsh_const	RSH 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

TS	a DDT in which the differentials in every row are sorted by decreasing number of probability.
dx	input difference.
dy	maximum 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

RSDDT DDT as a 2D list of differentials.

void print_sddt ( differential_t * SDDT )

Print the elements of a DDT.

Parameters

SDDT	DDT 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

T	a 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

ST	a 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

T	an 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

T	an 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

ST	an array of DDTs: each DDT is a 1D list of differentials.

Functions

Detailed Description

Function Documentation