YAARX: Yet Another ARX Toolkit  0.1
 All Data Structures Files Functions Variables Macros Pages
Data Structures | Macros | Functions
simon-xor-threshold-search.hh File Reference

Header file for xdp-rot-and.cc: More...

Go to the source code of this file.

Data Structures

struct  simon_diff_equal_to
 
struct  simon_diff_hash
 
struct  simon_trail_equal_to
 
struct  simon_trail_hash
 
struct  simon_diff_graph_node_comp
 
struct  simon_diff_graph_node_alloc
 

Macros

#define SIMON32_TRAIL_LEN   15
 
#define SIMON48_TRAIL_LEN   20
 
#define SIMON64_TRAIL_LEN   21
 

Functions

void simon_diff_graph_check_edge (std::vector< simon_diff_graph_edge_t > *E, const simon_diff_graph_edge_t new_edge)
 
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)
 
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)
 
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)
 
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)
 
void simon_graphviz_write_file (char *datfile, char *datfile_con, std::vector< simon_diff_graph_edge_t > E)
 
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_encrypt_pairs (uint32_t key[SIMON_MAX_NROUNDS], uint32_t nrounds, uint32_t *x_in, uint32_t *y_in, uint32_t *xx_in, uint32_t *yy_in)
 
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_print_round_diffs_latex (FILE *fp, uint32_t nrounds, uint32_t keys[4], differential_t trail[NROUNDS+1])
 
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)
 
std::string trail_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_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_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)
 
void simon_print_hash_table (std::unordered_map< std::string, differential_t ** > trails_hash_map, 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_cluster_trails_datfile_read (std::vector< simon_diff_graph_edge_t > *E)
 
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_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)
 

Detailed Description

Header file for xdp-rot-and.cc:

Author
A.Roy, V.Velichkov, arnab.nosp@m..roy.nosp@m.@uni..nosp@m.lu, vesse.nosp@m.lin..nosp@m.velic.nosp@m.hkov.nosp@m.@uni..nosp@m.lu
Date
2012-2013

Function Documentation

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_maphash table for storing the trails
Barray of best diff. prob. for N rounds computed with simon_xor_threshold_search
trailBest found trail with simon_xor_threshold_search
taril_lenlength 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.

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
Barray of the probabilities of the best found trails for up to simon_xor_threshold_search nrounds . Computed by
trailbest trail found by simon_xor_threshold_search .
input_diffinput difference of the differential.
output_diffoutput difference of the differential.
epstimes 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
traila differential trail for trail_len rounds.
trail_lenlength of the differential trail.
p_thresprobability 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_initinitial 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_trailbest found trail with prob. below exhaustive search
lowp_trailbest found trail with prob. above exhaustive search (best low prob. trail)