rc5-eq.hh

Go to the documentation of this file.

/*
 *    Copyright (c) 2012-2014 Luxembourg University,
 *    Laboratory of Algorithmics, Cryptology and Security (LACS).
 *
 *    This file is part of the YAARX toolkit. YAARX stands for
 *    Yet Another ARX toolkit for analysis of ARX cryptographic algorithms.
 *
 *    YAARX is free software: you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation, either version 3 of the License, or
 *    (at your option) any later version.
 *
 *    YAARX is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License
 *    along with YAARX.  If not, see <http://www.gnu.org/licenses/>.
 */
#ifndef RC5_EQ_H
#define RC5_EQ_H

#define RC5_ADD_APPROX 0
#define RC5_LAST_ROUND_ADD_APPROX 0
#define RC5_LAST_ROUND_PARAMS_INCLUDE_DX 0

#define RC5_LAST_ROUND_PARAMS_NVARIANTS_CUT_THRES 5

#define RC5_ADD_APPROX_ORDER 5//8

#define RC5_ADD_APPROX_P_THRES 1.0//((double)1.0 / (double)((1U <<  5) + 1))

typedef struct { 
  WORD_T plaintext_first[2];
  WORD_T plaintext_second[2];
  WORD_T ciphertext_first[2];
  WORD_T ciphertext_second[2];
  bool b_good; 
  WORD_T rand[2]; 
} pair_t;

typedef struct {
  WORD_T val;
  WORD_T pos;
} bits_t;

typedef struct {
  pair_t cp_pair;
  WORD_T dx;
  WORD_T y;
  WORD_T yy;
  uint32_t rot_const;
  uint32_t rot_const_prev;
  bool b_aux_data;
  uint64_t nvariants;
} eq_x_params_t;

struct rc5_eq_x_params_equal_to
  : std::binary_function<eq_x_params_t, eq_x_params_t, bool>
{
  bool operator()(eq_x_params_t const& first, eq_x_params_t const& second) const
  {
         bool b_equal = (
#if RC5_LAST_ROUND_PARAMS_INCLUDE_DX // <--- ! do  not consider the output difference
                    (first.dx == second.dx) &&
#endif // #if RC5_LAST_ROUND_PARAMS_INCLUDE_DX
                                                  (first.y == second.y) && 
                                                  (first.yy == second.yy) &&
                                                  (first.b_aux_data == second.b_aux_data) && 
                                                  (first.rot_const == second.rot_const) && 
                                                  (first.rot_const_prev == second.rot_const_prev));
         return b_equal;
  }
};

struct rc5_eq_x_params_hash
  : std::unary_function<eq_x_params_t, std::size_t>
{
  std::size_t operator()(eq_x_params_t const& params) const
  {
         std::size_t seed = 0;
#if RC5_LAST_ROUND_PARAMS_INCLUDE_DX // <--- ! do  not consider the output difference
         boost::hash_combine(seed, params.dx);
#endif // #if RC5_LAST_ROUND_PARAMS_INCLUDE_DX
         boost::hash_combine(seed, params.y);
         boost::hash_combine(seed, params.yy);
         boost::hash_combine(seed, params.rot_const);
         boost::hash_combine(seed, params.rot_const_prev);
         boost::hash_combine(seed, params.b_aux_data);
         return seed;
  }
};

#define RC5_LAST_ROUND_NMATRIX 8 // A[y[i]][yy[i]][dx[i]]
#define RC5_LAST_ROUND_MSIZE 4 /* Number of state values (s1, s2) */
#define RC5_LAST_ROUND_ISTATE 3 // initial state
#define RC5_XDP_ADD_LAST_ROUND_COLSUM 2 
#define RC5_XDP_ADD_LAST_ROUND_NORM 1.0 /(double)RC5_XDP_ADD_LAST_ROUND_COLSUM 
#define RC5_MID_ROUND_ISTATE 3 // initial state
#define RC5_MID_ROUND_NMATRIX 4 // A[dy[i]][dx[i]] 
#define RC5_MID_ROUND_MSIZE 4 /* Number of state values (s1, s2) */
#define RC5_XDP_ADD_MID_ROUND_COLSUM 4 
#define RC5_XDP_ADD_MID_ROUND_NORM 1.0 /(double)RC5_XDP_ADD_MID_ROUND_COLSUM 
//#if (WORD_SIZE == 32)
//#define RC5_XDP_ADD_MID_ROUND_P_THRES (double)1.0 / (double)(1UL << 8)//8)//0.001//0.005//0.001//0.03//0.01//0.001//0.0//0.001//0.005
//#define RC5_XDP_ADD_LAST_ROUND_P_THRES (double)1.0 / (double)(1UL << 8)//12)//0.005//0.005
//#endif // #if (WORD_SIZE == 32)
//#if (WORD_SIZE == 16)
//#define RC5_XDP_ADD_MID_ROUND_P_THRES 0.01//(double)1.0 / (double)(1UL << 12)//0.001//0.005//0.001//0.03//0.01//0.001//0.0//0.001//0.005
//#define RC5_XDP_ADD_LAST_ROUND_P_THRES 0.01//(double)1.0 / (double)(1UL << 12)//0.005//0.005
//#endif // #if (WORD_SIZE == 32)

void rc5_last_round_eq_alloc_matrices_3d(gsl_matrix* A[2][2][2]);
void rc5_last_round_eq_free_matrices_3d(gsl_matrix* A[2][2][2]);
void rc5_last_round_eq_alloc_matrices_4d(gsl_matrix* A[2][2][2][2]);
void rc5_last_round_eq_free_matrices_4d(gsl_matrix* A[2][2][2][2]);
void rc5_last_round_eq_print_matrices(gsl_matrix* A[2][2][2]);
void rc5_last_round_eq_print_matrices(gsl_matrix* A[2][2][2][2]);
void rc5_last_round_eq_add_matrices(gsl_matrix* A[2][2][2], gsl_matrix* AA[2][2][2][2]);
void rc5_last_round_eq_normalize_matrices(gsl_matrix* A[2][2][2]);
// key equation
void rc5_last_round_eq_key_sf(gsl_matrix* A[2][2][2][2]);
bool rc5_last_round_eq_key_is_contradicting(const gsl_matrix* A[2][2][2], const gsl_vector* L, const gsl_vector* C,
                                                                                                                  const WORD_T y, const WORD_T yy, const WORD_T dx, double* nval);
bool rc5_last_round_eq_key_check_conflict_exper(WORD_T y, WORD_T yy, WORD_T dx);
void rc5_last_round_eq_key_detect_fixed_key_bits(const gsl_matrix* A[2][2][2],
                                                                                                                                 const gsl_matrix* AA[2][2][2][2],
                                                                                                                                 const gsl_vector* L, const gsl_vector* C,
                                                                                                                                 const WORD_T y, const WORD_T yy, const WORD_T dx);
// x value equation
bool rc5_struct_eq_x_params_compare_by_nvariants(const eq_x_params_t first, const eq_x_params_t second);
void rc5_last_round_eq_x_sf(gsl_matrix* A[2][2][2][2]);
void rc5_last_round_eq_x_count_solutions_all_inputs(const gsl_matrix* A[2][2][2], const gsl_matrix* AA[2][2][2][2]);
uint32_t rc5_last_round_eq_x_count_solutions_exper(uint32_t y, uint32_t yy, uint32_t dx, std::vector<uint32_t>* sol_vec);
double rc5_xdp_add_last_round(const gsl_matrix* A[2][2][2],
                                                                                const gsl_vector* L, const gsl_vector* C,
                                                                                const WORD_T y, const WORD_T yy, const WORD_T dx);
void rc5_xdp_add_last_round_diff_set_out_exper(const WORD_T y, const WORD_T yy,
                                                                                                                          const double p_thres,
                                                                                                                          std::vector<WORD_T>* dx_vec);
void rc5_xdp_add_last_round_diff_set_out_wrapper(const WORD_T y, const WORD_T yy,
                                                                                                                                 const double p_thres,
                                                                                                                                 std::vector<WORD_T>* dx_vec);
void rc5_xdp_add_last_round_diff_set_out_i(const uint32_t i, 
                                                                                                                 const double p_thres, const uint32_t hw_thres,
                                                                                                                 const gsl_matrix* A[2][2][2], 
                                                                                                                 const gsl_vector* L, const gsl_vector* C, 
                                                                                                                 const WORD_T y, const WORD_T yy, 
                                                                                                                 const WORD_T dx_prev, // D[6] <<< S[6]
                                                                                                                 const uint32_t rot_const_prev, // S[6]
                                                                                                                 const WORD_T dx, 
                                                                                                                 const double p, 
                                                                                                                 std::vector<WORD_T>* dx_vec);
void rc5_xdp_add_last_round_diff_set_out(const gsl_matrix* A[2][2][2], const gsl_vector* L, const gsl_vector* C, 
                                                                                                          const WORD_T y, const WORD_T yy,
                                                                                                          const WORD_T dx_prev, // D[6] >>> S[6]
                                                                                                          const uint32_t rot_const_prev, // S[6]
                                                                                                          const double p_thres,
                                                                                                          const uint32_t hw_thres,
                                                                                                          std::vector<WORD_T>* dx_vec);
bool rc5_last_round_eq_x_find_solutions_rec(const gsl_matrix* A[2][2][2][2],
                                                                                                                  const eq_x_params_t eq_params,
                                                                                                                  std::vector<WORD_T>* sol_vec);
bool rc5_last_round_eq_x_has_solution(const uint32_t i, const gsl_matrix* A[2][2][2][2],
                                                                                                  const gsl_vector* L, const gsl_vector* C, 
                                                                                                  const eq_x_params_t eq_params, 
                                                                                                  const WORD_T x_sol, WORD_T* sol);
bool rc5_last_round_eq_x_find_solutions_exper(WORD_T y, WORD_T yy, WORD_T dx, std::vector<WORD_T>* sol_vec);
bool rc5_last_round_eq_x_is_solution(const WORD_T x, const WORD_T y, const WORD_T yy, const WORD_T dx);
bool rc5_last_round_eq_x_bit_seq_match(const WORD_T x, const uint32_t rot_const, 
                                                                                                        const WORD_T bit_seq, const uint32_t bit_seq_len);
bool rc5_last_round_eq_x_bit_seq_match_bitwise(const WORD_T x, const uint32_t rot_const, 
                                                                                                                          const WORD_T bit_seq, const uint32_t bit_seq_len);
double rc5_xdp_add_last_round_exper(WORD_T y, WORD_T yy, WORD_T dx);
double rc5_xdp_add_last_round(uint32_t y, uint32_t yy, uint32_t dx);
bool rc5_last_round_add_approx_match(const uint32_t i, const WORD_T x_in, const WORD_T xx_in, 
                                                                                                 const WORD_T dy, const WORD_T dz, const uint32_t order_in);

// --- RC5 mid round ---
double rc5_xdp_add_mid_round_exper(const WORD_T dy, const WORD_T dx);
bool rc5_mid_round_eq_xy_find_solutions_exper(const WORD_T dy, const WORD_T dx, std::vector<WORD_T>* sol_vec);

void rc5_mid_round_eq_xy_sf(gsl_matrix* A[2][2][2][2]);
void rc5_mid_round_eq_alloc_matrices_2d(gsl_matrix* A[2][2]);
void rc5_mid_round_eq_free_matrices_2d(gsl_matrix* A[2][2]);
void rc5_mid_round_eq_alloc_matrices_4d(gsl_matrix* A[2][2][2][2]);
void rc5_mid_round_eq_free_matrices_4d(gsl_matrix* A[2][2][2][2]);
void rc5_mid_round_eq_add_matrices(gsl_matrix* A[2][2], gsl_matrix* AA[2][2][2][2]);
void rc5_mid_round_eq_normalize_matrices(gsl_matrix* A[2][2]);
void rc5_mid_round_eq_print_matrices(gsl_matrix* A[2][2]);
double rc5_xdp_add_mid_round(const gsl_matrix* A[2][2],
                                                                          const gsl_vector* L, const gsl_vector* C,
                                                                          const WORD_T dy, const WORD_T dx);
void rc5_xdp_add_mid_round_diff_set_out_exper(const WORD_T dy,
                                                                                                                         const double p_thres,
                                                                                                                         std::vector<WORD_T>* dx_vec);
void rc5_xdp_add_mid_round_diff_set_out(const gsl_matrix* A[2][2], 
                                                                                                         const gsl_vector* L, const gsl_vector* C, 
                                        const WORD_T dy, // D[7]
                                                                                                         const WORD_T dx_prev, // D[6] >>> S[6]
                                                                                                         const uint32_t rot_const_prev, // S[6]
                                                                                                         const double p_thres,
                                                                                                         const WORD_T hw_thres,
                                                                                                         std::vector<WORD_T>* dx_vec);
void rc5_xdp_add_mid_round_diff_set_out(const WORD_T dy, // D[7]
                                                                                                         const WORD_T dx_prev, // D[6] >>> S[6]
                                                                                                         const WORD_T rot_const_prev, // S[6]
                                                                                                         const double p_thres,
                                                                                                         const uint32_t hw_thres,
                                                                                                         std::vector<WORD_T>* dx_vec);
bool rc5_mid_round_add_approx_match(const uint32_t i, const WORD_T dx, 
                                                                                                const WORD_T dy, const WORD_T dz, const uint32_t order_in);
// --- RC5 last round ---
double rc5_xdp_add_first_round_exper(WORD_T x, WORD_T xx, WORD_T dy);
#endif  // #ifndef RC5_DC_H