Header file for tea-f-add-pddt.cc. More...

Functions
bool	rsh_condition_is_sat (const uint32_t k, const uint32_t new_da, const uint32_t new_dc)

bool	lsh_condition_is_sat (const uint32_t k, const uint32_t new_da, const uint32_t new_db)

void	tea_f_add_pddt_i (const uint32_t k, const uint32_t n, const uint32_t lsh_const, const uint32_t rsh_const, gsl_matrix A[2][2][2][2], gsl_vector C, uint32_t da, uint32_t db, uint32_t dc, uint32_t dd, double p, const double p_thres, std::set< differential_t, struct_comp_diff_dx_dy > diff_set_dx_dy)

void	tea_f_add_pddt (uint32_t n, double p_thres, uint32_t lsh_const, uint32_t rsh_const, std::set< differential_t, struct_comp_diff_dx_dy > *diff_set_dx_dy)

bool	is_dx_in_set_dx_dy (uint32_t dy, uint32_t dx_prev, std::set< differential_t, struct_comp_diff_dx_dy > diff_set_dx_dy)

void	tea_f_da_add_pddt_i (const uint32_t k, const uint32_t n, const uint32_t lsh_const, const uint32_t rsh_const, gsl_matrix A[2][2][2][2], gsl_vector C, const uint32_t da, uint32_t db, uint32_t dc, uint32_t dd, double p, const double p_thres, std::set< differential_t, struct_comp_diff_dx_dy > diff_set_dx_dy, std::multiset< differential_t, struct_comp_diff_p > diff_mset_p, uint32_t *cnt_new)

uint32_t	tea_f_da_add_pddt (uint32_t n, double p_thres, uint32_t lsh_const, uint32_t rsh_const, const uint32_t da, const uint32_t da_prev, std::set< differential_t, struct_comp_diff_dx_dy > hways_diff_set_dx_dy, std::multiset< differential_t, struct_comp_diff_p > hways_diff_mset_p, std::set< differential_t, struct_comp_diff_dx_dy > diff_set_dx_dy, std::multiset< differential_t, struct_comp_diff_p > diff_mset_p)

void	tea_f_add_pddt_adjust_to_key (uint32_t nrounds, uint32_t npairs, uint32_t key[4], double p_thres, std::set< differential_t, struct_comp_diff_dx_dy > *diff_set_dx_dy)

void	tea_f_add_pddt_dxy_to_dp (std::multiset< differential_t, struct_comp_diff_p > *diff_mset_p, const std::set< differential_t, struct_comp_diff_dx_dy > diff_set_dx_dy)

void	tea_f_add_pddt_exper (gsl_matrix A[2][2][2][2], uint32_t n, double p_thres, uint32_t lsh_const, uint32_t rsh_const, std::multiset< differential_t, struct_comp_diff_p > diff_mset_p)

void	tea_f_add_pddt_fk_exper (uint32_t n, double p_thres, uint32_t delta, uint32_t k0, uint32_t k1, uint32_t lsh_const, uint32_t rsh_const, std::multiset< differential_t, struct_comp_diff_p > *diff_mset_p)

Detailed Description

Header file for tea-f-add-pddt.cc.

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

Date: 2012-2013

Function Documentation

bool is_dx_in_set_dx_dy	(	uint32_t	dy,
		uint32_t	dx_prev,
		std::set< differential_t, struct_comp_diff_dx_dy >	diff_set_dx_dy
	)

For a given difference dx, check if in the list of differentials set_dx_dy exists an entry (dx -> dy)

bool lsh_condition_is_sat	(	const uint32_t	k,
		const uint32_t	new_da,
		const uint32_t	new_db
	)

Check if two differences $da$ and $dc$ , partially constructed up to bit $k$ (WORD_SIZE $> k \ge 0$ ), are valid input and output difference respectively, for the LSH operation.

Parameters

k	bit position: WORD_SIZE $> k \ge 0$ .
new_da	input difference to LSH partially constructed up to bit .
new_db	output difference from LSH partially constructed up to bit .

Returns: TRUE if , after being fully constructed, will be a valid output difference from LSH, given the input difference ; FALSE otherwise.

More Details:

If : check if .
If $k \ge L$ : check if $(db \gg L)[n-(k-L+1):0] = da[n-(k-L+1):0]$ .

where $L =$ TEA_LSH_CONST, $n=$ WORD_SIZE.

See Also: rsh_condition_is_sat

bool rsh_condition_is_sat	(	const uint32_t	k,
		const uint32_t	new_da,
		const uint32_t	new_dc
	)

Check if two differences $da$ and $dc$ , partially constructed up to bit $k$ (WORD_SIZE $> k \ge 0$ ), are valid input and output difference respectively, for the RSH operation. From the partial information for $dc$ , the algorithm estimates if $dc$ belongs to one of the four possible differences after the RSH operation (see adp_rsh): $\{(da \gg R),~ (da \gg R) + 1,~ (da \gg R) - 2^{n-R},~ (da \gg R) - 2^{n-R} + 1\}$ , where $R$ is the RSH constant (TEA_RSH_CONST).

Parameters

k	bit position: WORD_SIZE $> k \ge 0$ .
new_da	input difference to RSH partially constructed up to bit .
new_dc	output difference from RSH partially constructed up to bit .

Returns: TRUE if , after being fully constructed, will be a valid output difference from RSH, given the input difference ; FALSE otherwise.

Attention: The function is not optimal, meaning that it is overly-restrictive: all diferences which pass the checks are valid, but there also exist valid differences that do not pass the checks. The reason is that it is hard to detect all valid differences before they have been fully constructed.

More Details:

Given are two differences $da$ and $dc$ , that are only partially constructed up to bit $k$ (counting from the LSB $k = 0$ ). rsh_condition_is_sat performs checks on $da$ and $dc$ and outputs if $dc$ is such that $dc = da \gg R$ , where $R$ = TEA_RSH_CONST. The idea is to be able to discard pairs of diferences $(da, dc)$ before they have been fully constructed. This allows to more efficiently constrct a list of valid differentials for the TEA F-function recursively. We use these conditions in tea_f_add_pddt_i to discard invalid entries early in the recursion.

To perform the checks, the following relations are used:

$dc = (da \gg R) \Longrightarrow dc \in \{dc_0, dc_1, dc_2, dc_3\}$ where:

$dc_0 = (da \gg R)$ .
$dc_2 = (da \gg R) - 2^{n-R}$ .
$dc_1 = (da \gg R) + 1$ .
$dc_3 = (da \gg R) - 2^{n-R} + 1$ .

Depending on the bit position $k$ (some of) the following checks are performed:

If perform check on the LS bits. If we check if the first LSB bits of are equal to the first bits of according to the above equations. So we check if any of the following four equations hold:
- $(da \gg R)[0:(k - R)] = (dc_0)[0:(k - R)]$ .
- $(da \gg R)[0:(k - R)] = (dc_0 + 2^{n-R})[0:(k - R)]$ .
- $(da \gg R)[0:(k - R)] = (dc_0 - 1)[0:(k - R)]$ .
- $(da \gg R)[0:(k - R)] = (dc_0 + 2^{n-R} - 1)[0:(k - R)]$ .
Check that the LS bits of are not zero $da[(r-1):0] \neq 0$ .
If check the MS bits. When , and we check the top MS bits of . More specifically, we check if the initial four equations hold for the MS bits of the operands:
- $dc_0[(n-1):(n-R+1)] = (da \gg R)[(n-1):(n-R+1)]$ .
- $dc_1[(n-1):(n-R+1)] = ((da \gg R) + 1)[(n-1):(n-R+1)]$ .
- $dc_2[(n-1):(n-R+1)] = ((da \gg R) - 2^{n-R})[(n-1):(n-R+1)]$ .
- $dc_3[(n-1):(n-R+1)] = ((da \gg R) - 2^{n-R} + 1)[(n-1):(n-R+1)]$ .

void tea_f_add_pddt	(	uint32_t	n,
		double	p_thres,
		uint32_t	lsh_const,
		uint32_t	rsh_const,
		std::set< differential_t, struct_comp_diff_dx_dy > *	diff_set_dx_dy
	)

Compute a partial DDT (pDDT) for the TEA F-function: wrapper function of tea_f_add_pddt_i . By definition a pDDT contains only differentials that have probability above a fixed probability thershold.

Parameters

n	word size (default is WORD_SIZE).
p_thres	probability threshold (default is TEA_ADD_P_THRES).
lsh_const	LSH constant (TEA_LSH_CONST).
rsh_const	RSH constant (TEA_RSH_CONST).
diff_set_dx_dy	set of differentials $(dx \rightarrow dy)$ in the pDDT ordered by index $i = (dx~ 2^{n} + dy)$ ; stored in an STL set structure, internally implemented as a Red-Black binary search tree.

See Also: tea_f_add_pddt_i.

void tea_f_add_pddt_adjust_to_key	(	uint32_t	nrounds,
		uint32_t	npairs,
		uint32_t	key[4],
		double	p_thres,
		std::set< differential_t, struct_comp_diff_dx_dy > *	diff_set_dx_dy
	)

Adjust the probabailities of the differentials in a pDDT computed with tea_f_add_pddt , to the value of a fixed key by performing one-round TEA encryptions over a number of chosen plaintext pairs drawn uniformly at random.

Parameters

nrounds	total number of rounds (NROUNDS).
npairs	number of chosen plaintext pairs (NPAIRS).
key	cryptographic key of TEA.
p_thres	probability threshold (TEA_ADD_P_THRES).
diff_set_dx_dy	set of differentials (the pDDT) ordered by index $i = (dx~ 2^{n} + dy)$ - smallest first.

void tea_f_add_pddt_dxy_to_dp	(	std::multiset< differential_t, struct_comp_diff_p > *	diff_mset_p,
		const std::set< differential_t, struct_comp_diff_dx_dy >	diff_set_dx_dy
	)

From a pDDT represented in the form of a set of differentials ordered by index, compute a pDDT as a set of differentials ordered by probability.

Parameters

diff_mset_p	output pDDT: set of differentials $(dx \rightarrow dy)$ ordered by probability; stored in an STL multiset structure, internally implemented as a Red-Black binary search tree.
diff_set_dx_dy	input pDDT: set of differentials $(dx \rightarrow dy)$ ordered by index $i = (dx~ 2^{n} + dy)$ ; stored in an STL set structure, internally implemented as a Red-Black binary search tree.

void tea_f_add_pddt_exper	(	gsl_matrix *	A[2][2][2][2],
		uint32_t	n,
		double	p_thres,
		uint32_t	lsh_const,
		uint32_t	rsh_const,
		std::multiset< differential_t, struct_comp_diff_p > *	diff_mset_p
	)

Experimentally compute the full DDT of the TEA F-function containining expected probabilities, averaged over all keys and round constants. An exhautive search is performed over all input and output differences. Complexity: $O(2^{2n})$ .

Parameters

A	transition probability matrices for $\mathrm{adp}^{3\oplus}$ (adp_xor3_sf).
n	word size (default is WORD_SIZE).
p_thres	probability threshold (default is TEA_ADD_P_THRES).
lsh_const	LSH constant (TEA_LSH_CONST).
rsh_const	RSH constant (TEA_RSH_CONST).
diff_mset_p	set of differentials $(dx \rightarrow dy)$ ordered by probability (the DDT).

void tea_f_add_pddt_fk_exper	(	uint32_t	n,
		double	p_thres,
		uint32_t	delta,
		uint32_t	k0,
		uint32_t	k1,
		uint32_t	lsh_const,
		uint32_t	rsh_const,
		std::multiset< differential_t, struct_comp_diff_p > *	diff_mset_p
	)

Experimentally compute the full DDT of the TEA F-function containining probabilities for a fixed key and round constant. An exhautive search is performed over all input and output differences. Complexity: $O(2^{2n})$ .

Parameters

n	word size (default is WORD_SIZE).
p_thres	probability threshold (default is TEA_ADD_P_THRES).
delta	round constant.
k0	first round key.
k1	second round key.
lsh_const	LSH constant (TEA_LSH_CONST).
rsh_const	RSH constant (TEA_RSH_CONST).
diff_mset_p	set of differentials $(dx \rightarrow dy)$ ordered by probability (the DDT).

void tea_f_add_pddt_i	(	const uint32_t	k,
		const uint32_t	n,
		const uint32_t	lsh_const,
		const uint32_t	rsh_const,
		gsl_matrix *	A[2][2][2][2],
		gsl_vector *	C,
		uint32_t *	da,
		uint32_t *	db,
		uint32_t *	dc,
		uint32_t *	dd,
		double *	p,
		const double	p_thres,
		std::set< differential_t, struct_comp_diff_dx_dy > *	diff_set_dx_dy
	)

Computes a partial difference distribution table (pDDT) for the F-function of block cipher TEA.

Parameters

k	current bit position in the recursion.
n	word size (default is WORD_SIZE).
lsh_const	LSH constant (default is 4).
rsh_const	RSH constant (default is 5).
A	transition probability matrices for $\mathrm{adp}^{3\oplus}$ (adp_xor3_sf).
C	unit column vector for computing $\mathrm{adp}^{3\oplus}$ (adp_xor3).
da	first input difference to the XOR operation in F.
db	second input difference to the XOR operation in F.
dc	third input difference to the XOR operation in F.
dd	output difference from the XOR operation in F.
p	probability of the partially constructed differential $(da[k:0], db[k:0], dc[k:0] \rightarrow dd[k:0])$ .
p_thres	probability threshold (default is TEA_ADD_P_THRES).
diff_set_dx_dy	set of differentials $(dx \rightarrow dy)$ in the pDDT ordered by index $i = (dx~ 2^{n} + dy)$ ; stored in an STL set structure, internally implemented as a Red-Black binary search tree.

Attention: The computed pDDT is based on the expected additive differential probability of the TEA F-function (eadp_tea_f), averaged over all round keys and round constants $\delta$ and therefore contains average (as opposed to fixed-key fixed-constants adp_f_fk) probabilities.

Algorithm Outline:

Applies conceptually the same logic as adp_xor_pddt_i. It recursively constructs all differentials for the XOR operation with three inputs $(da, db, dc \rightarrow dd)$ , with the additional requirement that they must satisfy the following properties:

$\mathrm{adp}^{3\oplus}(da, db, dc \rightarrow dd) > p_\mathrm{thres}$ .
$db = da \ll 4$ .
$dc \in {(da \ll R), (da \ll R) + 1, (da \ll R) - 2^{n-R}, (da \ll R) - 2^{n-R} + 1}$ , so that $dc = (da \ll R)$ where TEA_RSH_CONST.

Only the entries for which $\mathrm{eadp}^{F}(da \rightarrow dd) > p_\mathrm{thres}$ are stored.

See Also: adp_xor_pddt_i, lsh_condition_is_sat, rsh_condition_is_sat.

uint32_t tea_f_da_add_pddt	(	uint32_t	n,
		double	p_thres,
		uint32_t	lsh_const,
		uint32_t	rsh_const,
		const uint32_t	da,
		const uint32_t	da_prev,
		std::set< differential_t, struct_comp_diff_dx_dy > *	hways_diff_set_dx_dy,
		std::multiset< differential_t, struct_comp_diff_p > *	hways_diff_mset_p,
		std::set< differential_t, struct_comp_diff_dx_dy > *	diff_set_dx_dy,
		std::multiset< differential_t, struct_comp_diff_p > *	diff_mset_p
	)

Wrapper for tea_f_da_db_dc_add_pddt_i . Returns the number of new entries that were added .

Parameters

n	word size (default is WORD_SIZE).
p_thres	probability threshold (default is TEA_ADD_P_THRES).
lsh_const	LSH constant (default is TEA_LSH_CONST).
rsh_const	RSH constant (default is TEA_RSH_CONST).
da	input difference to F.
da_prev	input difference to the previous round.
hways_diff_set_dx_dy	set of differentials (Highways) ordered by index $i = (dx~ 2^{n} + dy)$ .
hways_diff_mset_p	set of differentials (Highways) ordered by probability p.
diff_set_dx_dy	set of differentials (Countryroads) ordered by index $i = (dx~ 2^{n} + dy)$ .
diff_mset_p	temporrary set of differentials (Countryroads) ordered by probability p.

Returns: number of output differences that were added to diff_set_dx_dy .

Functions

Detailed Description

Function Documentation