Automatic search for XOR differentials in block cipher Simon. More...

#include "common.hh"
#include "xdp-and.hh"
#include "xdp-rot-and.hh"
#include "simon.hh"
#include "simon-xor-threshold-search.hh"

Macros
#define	PRINT_NODE_INFO 0

#define	VERBOSE 1

#define	PRINT_TRAIL_FILE 1

#define	PRINT_TRAIL 0

#define	SIMON_PRINT_DIFFS_TO_FILE 1

#define	CLEAR_CROADS 1

#define	USE_PRECOMPUTED_BOUNDS 0

Functions
std::string	trail_to_string (differential_t *trail, uint32_t trail_len)

std::string	diff_to_string (differential_t *trail, uint32_t trail_len)

std::string	differential_to_string (const differential_t diff)

uint32_t	differential_to_num (const differential_t diff)

void	simon_print_diff_array (std::array< differential_t, SIMON_NDIFFS > diff_array)

void	simon_print_diff_hash_map (boost::unordered_map< std::array< differential_t, SIMON_NDIFFS >, uint32_t, simon_diff_hash, simon_diff_equal_to > diffs_hash_map)

void	simon_print_trail_array (std::array< differential_t, NROUNDS > trail_array)

void	simon_print_trail_hash_map (boost::unordered_map< std::array< differential_t, NROUNDS >, uint32_t, simon_trail_hash, simon_trail_equal_to > trails_hash_map)

void	simon_print_round_diffs_latex (FILE *fp, uint32_t nrounds, uint32_t keys[4], differential_t trail[NROUNDS+1])

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

uint32_t	simon_verify_xor_trail (uint32_t nrounds, uint32_t npairs, uint32_t key_in[SIMON_MAX_NROUNDS], differential_t trail[NROUNDS], uint32_t dy_init, uint32_t lrot_const_s, uint32_t lrot_const_t, uint32_t lrot_const_u)

void	simon_trail_to_round_diffs (differential_t trail_in[NROUNDS], differential_t round_diffs[NROUNDS+1], uint32_t nrounds, uint32_t lrot_const_s, uint32_t lrot_const_t, uint32_t lrot_const_u)

uint32_t	simon_verify_xor_differential (uint32_t nrounds, uint32_t npairs, uint32_t key_in[SIMON_MAX_NROUNDS], differential_t trail_in[NROUNDS], uint32_t dy_init, uint32_t lrot_const_s, uint32_t lrot_const_t, uint32_t lrot_const_u)

void	simon_diff_graph_print_nodes (std::map< simon_diff_graph_node_t, simon_diff_graph_node_t, simon_diff_graph_node_comp > V)

bool	simon_diff_vec_comp (std::pair< simon_diff_graph_node_t, simon_diff_graph_node_t > a, std::pair< simon_diff_graph_node_t, simon_diff_graph_node_t > b)

void	simon_diff_graph_extract_nodes (std::vector< simon_diff_graph_edge_t > E, std::map< simon_diff_graph_node_t, simon_diff_graph_node_t, simon_diff_graph_node_comp > *V)

void	simon_cluster_trails_datfile_read (std::vector< simon_diff_graph_edge_t > *E)

void	simon_graphviz_write_file (char datfile, char datfile_con, std::vector< simon_diff_graph_edge_t > E)

double	simon_verify_differential_approx (const uint32_t key_in[SIMON_MAX_NROUNDS], const differential_t input_diff, const differential_t output_diff, const uint32_t nrounds, const uint64_t npairs, std::vector< simon_diff_graph_edge_t > *E)

double	simon_verify_differential (const uint32_t key_in[SIMON_MAX_NROUNDS], const differential_t input_diff, const differential_t output_diff, const uint32_t nrounds, const uint64_t npairs, std::vector< simon_diff_graph_edge_t > *E)

void	simon_print_hash_table (std::unordered_map< std::string, differential_t ** > trails_hash_map, uint32_t trail_len)

void	simon_boost_new_trail_store_to_file (uint32_t dx_in, uint32_t dy_in, differential_t trail[NROUNDS], uint32_t trail_len)

void	simon_boost_print_hash_table (boost::unordered_map< std::array< differential_t, NROUNDS >, uint32_t, simon_trail_hash, simon_trail_equal_to > trails_hash_map, uint32_t trail_len)

void	simon_print_diff_hash_table (std::unordered_map< std::string, differential_t ** > diffs_hash_map, uint32_t nrounds)

void	simon_boost_print_diff_hash_table (boost::unordered_map< std::array< differential_t, SIMON_NDIFFS >, uint32_t, simon_diff_hash, simon_diff_equal_to > diffs_hash_map)

void	simon_trails_hash_map_add_new (differential_t diff[NROUNDS], const uint32_t trail_len, std::unordered_map< std::string, differential_t ** > *trails_hash_map)

void	simon_diffs_hash_map_add_new (differential_t diff[NROUNDS], const uint32_t trail_len, std::unordered_map< std::string, differential_t ** > *diffs_hash_map)

void	simon_hash_map_update (differential_t diff[NROUNDS], const uint32_t trail_len, std::unordered_map< std::string, differential_t ** > diffs_hash_map, std::unordered_map< std::string, differential_t * > trails_hash_map, differential_t *diff_max)

void	simon_boost_hash_map_update (differential_t diff[NROUNDS], const uint32_t trail_len, boost::unordered_map< std::array< differential_t, SIMON_NDIFFS >, uint32_t, simon_diff_hash, simon_diff_equal_to > diffs_hash_map, boost::unordered_map< std::array< differential_t, NROUNDS >, uint32_t, simon_trail_hash, simon_trail_equal_to > trails_hash_map, differential_t **diff_max)

uint32_t	simon_diffsets_remove_rot_equivalent (std::multiset< differential_t, struct_comp_diff_p > diff_mset_p, std::set< differential_t, struct_comp_diff_dx_dy > diff_set_dx_dy)

uint32_t	simon_diffsets_remove_rot_equivalent_diff (differential_t diff, std::multiset< differential_t, struct_comp_diff_p > *diff_mset_p)

void	simon_xor_threshold_search (const int n, const int nrounds, double B[NROUNDS], double Bn, const differential_t diff_in[NROUNDS], differential_t trail[NROUNDS], const uint32_t dyy_init, uint32_t lrot_const_s, uint32_t lrot_const_t, uint32_t lrot_const_u, 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 > hways_diff_mset_p, std::set< differential_t, struct_comp_diff_dx_dy > hways_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, boost::unordered_map< std::array< differential_t, SIMON_NDIFFS >, uint32_t, simon_diff_hash, simon_diff_equal_to > diffs_hash_map, boost::unordered_map< std::array< differential_t, NROUNDS >, uint32_t, simon_trail_hash, simon_trail_equal_to > trails_hash_map, differential_t *diff_max, bool b_hash_map, double p_eps, double p_thres)

void	simon_diff_mset_p_to_mset_hw (std::multiset< differential_t, struct_comp_diff_p > diff_mset_p, std::multiset< differential_t, struct_comp_diff_hw > *diff_mset_hw)

uint32_t	simon_xor_trail_search (uint32_t key[SIMON_MAX_NROUNDS], double B[NROUNDS], differential_t best_trail[NROUNDS], uint32_t *best_trail_len)

void	simon_xor_cluster_trails (const int n, const int nrounds, const double B[NROUNDS], const differential_t diff_in[NROUNDS], const differential_t best_trail[NROUNDS], std::unordered_map< std::string, differential_t ** > trails_hash_map, const differential_t input_diff, const differential_t output_diff, uint32_t lrot_const_s, uint32_t lrot_const_t, uint32_t lrot_const_u, 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, double eps)

void	simon_trail_cluster_search (std::unordered_map< std::string, differential_t ** > trails_hash_map, double B[NROUNDS], const differential_t trail_in[NROUNDS], uint32_t trail_len, uint32_t dyy_init)

void	simon_xor_cluster_trails_boost (const int n, const int nrounds, const double B[NROUNDS], const differential_t diff_in[NROUNDS], const differential_t best_trail[NROUNDS], boost::unordered_map< std::array< differential_t, NROUNDS >, uint32_t, simon_trail_hash, simon_trail_equal_to > trails_hash_map, const differential_t input_diff, const differential_t output_diff, uint32_t lrot_const_s, uint32_t lrot_const_t, uint32_t lrot_const_u, 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 > hways_diff_mset_p, std::set< differential_t, struct_comp_diff_dx_dy > hways_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, double eps)

void	simon_trail_cluster_search_boost (boost::unordered_map< std::array< differential_t, NROUNDS >, uint32_t, simon_trail_hash, simon_trail_equal_to > trails_hash_map, double B[NROUNDS], const differential_t trail_in[NROUNDS], uint32_t trail_len, uint32_t dyy_init)

Detailed Description

Automatic search for XOR differentials in block cipher Simon.

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

Date: 2012-2013

Function Documentation

void simon_diffs_hash_map_add_new	(	differential_t	diff[NROUNDS],
		const uint32_t	trail_len,
		std::unordered_map< std::string, differential_t ** > *	diffs_hash_map
	)

Add new differential in the hash table.

void simon_hash_map_update	(	differential_t	diff[NROUNDS],
		const uint32_t	trail_len,
		std::unordered_map< std::string, differential_t ** > *	diffs_hash_map,
		std::unordered_map< std::string, differential_t ** > *	trails_hash_map,
		differential_t **	diff_max
	)

Check if a trail and its corresponding diferential are already in the hash maps and if not – add them. Also update the probability of the maximum differential if necessary.

void simon_trail_cluster_search	(	std::unordered_map< std::string, differential_t ** > *	trails_hash_map,
		double	B[NROUNDS],
		const differential_t	trail_in[NROUNDS],
		uint32_t	trail_len,
		uint32_t *	dyy_init
	)

Search for differentials in Simon: a wrapper for simon_xor_cluster_trails

Parameters

trails_hash_map	hash table for storing the trails
B	array of best diff. prob. for `N` rounds computed with simon_xor_threshold_search
trail	Best found trail with simon_xor_threshold_search
taril_len	length of `trail`

void simon_trail_to_round_diffs	(	differential_t	trail_in[NROUNDS],
		differential_t	round_diffs[NROUNDS+1],
		uint32_t	nrounds,
		uint32_t	lrot_const_s,
		uint32_t	lrot_const_t,
		uint32_t	lrot_const_u
	)

Transforms a trail obtained using threshold search into a sequence of input/output differences to each round suitable for verifying the trail.

void simon_trails_hash_map_add_new	(	differential_t	diff[NROUNDS],
		const uint32_t	trail_len,
		std::unordered_map< std::string, differential_t ** > *	trails_hash_map
	)

Add new trail in the hash table.

uint32_t simon_verify_xor_differential	(	uint32_t	nrounds,
		uint32_t	npairs,
		uint32_t	key_in[SIMON_MAX_NROUNDS],
		differential_t	trail_in[NROUNDS],
		uint32_t	dy_init,
		uint32_t	lrot_const_s,
		uint32_t	lrot_const_t,
		uint32_t	lrot_const_u
	)

Given an XOR trail for $N$ rounds, experimentally verify the probabilities of the corresponding $N$ differentials:

  - Differential for 1 round: round 0. 
  - Differential for 2 rounds: rounds \form#316. 
  - Differential for 3 rounds: rounds \form#317. 
  -  \form#318
  - Differential for \form#315 rounds: rounds \form#319.

uint32_t simon_verify_xor_trail	(	uint32_t	nrounds,
		uint32_t	npairs,
		uint32_t	key_in[SIMON_MAX_NROUNDS],
		differential_t	trail[NROUNDS],
		uint32_t	dy_init,
		uint32_t	lrot_const_s,
		uint32_t	lrot_const_t,
		uint32_t	lrot_const_u
	)

Experimentally verify the probability of all 1-round differentials from which an N round trail for Simon is composed.

void simon_xor_cluster_trails	(	const int	n,
		const int	nrounds,
		const double	B[NROUNDS],
		const differential_t	diff_in[NROUNDS],
		const differential_t	best_trail[NROUNDS],
		std::unordered_map< std::string, differential_t ** > *	trails_hash_map,
		const differential_t	input_diff,
		const differential_t	output_diff,
		uint32_t	lrot_const_s,
		uint32_t	lrot_const_t,
		uint32_t	lrot_const_u,
		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,
		double	eps
	)

Compute (an approximation of) the probability of a differential corresponding to the best trail found by simon_xor_threshold_search . The algorithm grows a cluster of differential trails, each of which connects the input and outout differences corresponding to the best found trail. The sum of their probabilities is an approximation of the prob. of the differential.

Parameters

B	array of the probabilities of the best found trails for up to simon_xor_threshold_search nrounds . Computed by
trail	best trail found by simon_xor_threshold_search .
input_diff	input difference of the differential.
output_diff	output difference of the differential.
eps	times away from the optimal (e.g. eps = 2, 3, 2^{10}, ...).

uint32_t simon_xor_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

trail	a differential trail for `trail_len` rounds.
trail_len	length of the differential trail.
p_thres	probability threshold.

See Also: tea_add_threshold_count_lp

void simon_xor_threshold_search	(	const int	n,
		const int	nrounds,
		double	B[NROUNDS],
		double *	Bn,
		const differential_t	diff_in[NROUNDS],
		differential_t	trail[NROUNDS],
		const uint32_t	dyy_init,
		uint32_t	lrot_const_s,
		uint32_t	lrot_const_t,
		uint32_t	lrot_const_u,
		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 > *	hways_diff_mset_p,
		std::set< differential_t, struct_comp_diff_dx_dy > *	hways_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,
		boost::unordered_map< std::array< differential_t, SIMON_NDIFFS >, uint32_t, simon_diff_hash, simon_diff_equal_to > *	diffs_hash_map,
		boost::unordered_map< std::array< differential_t, NROUNDS >, uint32_t, simon_trail_hash, simon_trail_equal_to > *	trails_hash_map,
		differential_t **	diff_max,
		bool	b_hash_map,
		double	p_eps,
		double	p_thres
	)

The pDDT contains entries of the form (dx, dy, p) where dx and dy are resp. the input and output differences of the ROT-AND component f of Simon: y = f(x) = (x <<< s) & (x <<< t)

If b_hash_map is TRUE, then the algorithm searches for differentials and stores them in diffs_hash_map

Parameters

dyy_init initial right input difference to Simon

uint32_t simon_xor_trail_search	(	uint32_t	key[SIMON_MAX_NROUNDS],
		double	B[NROUNDS],
		differential_t	best_trail[NROUNDS],
		uint32_t *	best_trail_len
	)

Parameters

best_trail	best found trail with prob. below exhaustive search
lowp_trail	best found trail with prob. above exhaustive search (best low prob. trail)

Macros

Functions

Detailed Description

Function Documentation