Compute a partial difference distribution table (pDDT) for $\mathrm{xdp}^{+}$ . More...

#include "common.hh"
#include "xdp-add.hh"

Functions
uint32_t	xdp_add_pddt_exper (std::multiset< differential_3d_t, struct_comp_diff_3d_p > *diff_mset_p, double p_thres)

void	xdp_add_pddt_i (const uint32_t k, const uint32_t n, const double p_thres, gsl_matrix A[2][2][2], gsl_vector C, uint32_t da, uint32_t db, uint32_t dc, double p, std::set< differential_3d_t, struct_comp_diff_3d_dx_dy_dz > diff_set_dx_dy_dz, std::multiset< differential_3d_t, struct_comp_diff_3d_p > diff_mset_p, uint64_t max_size)

void	xdp_add_pddt (uint32_t n, double p_thres, const uint64_t max_size, std::set< differential_3d_t, struct_comp_diff_3d_dx_dy_dz > diff_set_dx_dy_dz, std::multiset< differential_3d_t, struct_comp_diff_3d_p > diff_mset_p)

bool	xdp_add_is_dz_in_set_dx_dy_dz (uint32_t dx, uint32_t dy, std::set< differential_3d_t, struct_comp_diff_3d_dx_dy_dz > diff_set_dx_dy_dz)

void	xdp_add_dx_dy_pddt_i (const uint32_t k, const uint32_t n, gsl_matrix A[2][2][2], gsl_vector C, const uint32_t da, const uint32_t db, uint32_t dc, double p, std::set< differential_3d_t, struct_comp_diff_3d_dx_dy_dz > hways_diff_set_dx_dy_dz, std::multiset< differential_3d_t, struct_comp_diff_3d_p > hways_diff_mset_p, std::set< differential_3d_t, struct_comp_diff_3d_dx_dy_dz > croads_diff_set_dx_dy_dz, std::multiset< differential_3d_t, struct_comp_diff_3d_p > croads_diff_mset_p, uint32_t right_rot_const, uint32_t left_rot_const, const double p_thres, uint32_t max_size)

uint32_t	xdp_add_dx_dy_pddt (uint32_t da, uint32_t db, std::set< differential_3d_t, struct_comp_diff_3d_dx_dy_dz > hways_diff_set_dx_dy_dz, std::multiset< differential_3d_t, struct_comp_diff_3d_p > hways_diff_mset_p, std::set< differential_3d_t, struct_comp_diff_3d_dx_dy_dz > croads_diff_set_dx_dy_dz, std::multiset< differential_3d_t, struct_comp_diff_3d_p > croads_diff_mset_p, uint32_t right_rot_const, uint32_t left_rot_const, double p_thres, uint32_t max_size)

Detailed Description

Compute a partial difference distribution table (pDDT) for $\mathrm{xdp}^{+}$ .

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

Date: 2012-2013

Function Documentation

uint32_t xdp_add_dx_dy_pddt	(	uint32_t	da,
		uint32_t	db,
		std::set< differential_3d_t, struct_comp_diff_3d_dx_dy_dz > *	hways_diff_set_dx_dy_dz,
		std::multiset< differential_3d_t, struct_comp_diff_3d_p > *	hways_diff_mset_p,
		std::set< differential_3d_t, struct_comp_diff_3d_dx_dy_dz > *	croads_diff_set_dx_dy_dz,
		std::multiset< differential_3d_t, struct_comp_diff_3d_p > *	croads_diff_mset_p,
		uint32_t	right_rot_const,
		uint32_t	left_rot_const,
		double	p_thres,
		uint32_t	max_size
	)

For given input XOR differences da,db to ADD compute a pDDT of differentials (da,db->dc) with probability above a fixed threshold p_thres.

right_rot_const and left_rot_const are the rotation constants of block cipher Speck speck.cc .

void xdp_add_dx_dy_pddt_i	(	const uint32_t	k,
		const uint32_t	n,
		gsl_matrix *	A[2][2][2],
		gsl_vector *	C,
		const uint32_t	da,
		const uint32_t	db,
		uint32_t *	dc,
		double *	p,
		std::set< differential_3d_t, struct_comp_diff_3d_dx_dy_dz > *	hways_diff_set_dx_dy_dz,
		std::multiset< differential_3d_t, struct_comp_diff_3d_p > *	hways_diff_mset_p,
		std::set< differential_3d_t, struct_comp_diff_3d_dx_dy_dz > *	croads_diff_set_dx_dy_dz,
		std::multiset< differential_3d_t, struct_comp_diff_3d_p > *	croads_diff_mset_p,
		uint32_t	right_rot_const,
		uint32_t	left_rot_const,
		const double	p_thres,
		uint32_t	max_size
	)

See Also: xdp_add_dx_dy_pddt

bool xdp_add_is_dz_in_set_dx_dy_dz	(	uint32_t	dx,
		uint32_t	dy,
		std::set< differential_3d_t, struct_comp_diff_3d_dx_dy_dz >	diff_set_dx_dy_dz
	)

For given input differences dx,dy, check if in the list of differentials set_dx_dy_dz exists an entry (dx,dy->dz)

void xdp_add_pddt	(	uint32_t	n,
		double	p_thres,
		const uint64_t	max_size,
		std::set< differential_3d_t, struct_comp_diff_3d_dx_dy_dz > *	diff_set_dx_dy_dz,
		std::multiset< differential_3d_t, struct_comp_diff_3d_p > *	diff_mset_p
	)

Compute a partial DDT for $\mathrm{xdp}^{+}$ : wrapper function of xdp_add_pddt_i.

Parameters

n	word size.
p_thres	probability threshold.

See Also: xdp_add_pddt_i.

uint32_t xdp_add_pddt_exper	(	std::multiset< differential_3d_t, struct_comp_diff_3d_p > *	diff_mset_p,
		double	p_thres
	)

Compute a partial DDT for $\mathrm{xdp}^{+}$ by exhasutive search over all input and output differences.

Parameters

diff_mset_p	set of all differentials with probability not less than the threshold (the pDDT)
p_thres	probability threshold.

Returns: number of elements in the pDDT.

See Also: xdp_add_pddt_i

void xdp_add_pddt_i	(	const uint32_t	k,
		const uint32_t	n,
		const double	p_thres,
		gsl_matrix *	A[2][2][2],
		gsl_vector *	C,
		uint32_t *	da,
		uint32_t *	db,
		uint32_t *	dc,
		double *	p,
		std::set< differential_3d_t, struct_comp_diff_3d_dx_dy_dz > *	diff_set_dx_dy_dz,
		std::multiset< differential_3d_t, struct_comp_diff_3d_p > *	diff_mset_p,
		uint64_t	max_size
	)

Recursively compute all XOR differentials $(da, db \rightarrow dc)$ for ADD that have probability $\mathrm{xdp^{+}}$ larger than a fixed probability threshold p_thres.

The function works recursively starting from the LS bit k = 0 and terminating at the MS bit n. At every bit position i it assigns values to the i-th bits of the differences da, db, dc and evaluates the probability of the resulting partial (i+1)-bit differential: $(da[i:0], db[i:0] \rightarrow dc[i:0])$ . The recursion proceeds only if this probability is not less than the threshold p_thres. When i = n, the differential $(da[n-1:0], db[n-1:0] \rightarrow dc[n-1:0])$ is stored in an STL multiset structure (internally implemented as a Red-Black tree).

The complexity is strongly dependent on the threshold and is worst-case exponential in the word size: $O(2^{3n})$ .

Note: If p_thres = 0.0 then the full DDT is computed.; Can be used also to compute all differentials that have non-zero probability by setting p_thres > 0.0 .; For 32 bit words, recommended values for the threshold are p_thres >= 0.7.

Parameters

k	current bit position in the recursion.
n	word size.
p_thres	probability threshold.
A	transition probability matrices for $\mathrm{xdp}^{+}$ (xdp_add_sf).
C	unit column vector for computing $\mathrm{xdp}^{+}$ (xdp_add).
da	first input difference.
db	second input difference.
dc	output difference.
p	probability of the differential $(da[k:0], db[k:0] \rightarrow dc[k:0])$ .
diff_mset_p	set of all differentials with probability not less than the threshold (the pDDT)

Functions

Detailed Description

Function Documentation