YAARX: Yet Another ARX Toolkit  0.1
 All Data Structures Files Functions Variables Macros Pages
rc5-eq.cc File Reference

Procedures for solving certain equations arising during the differential analysis of block cipher RC5 . One such equation is the following equation in x from the last round of RC5: More...

#include "common.hh"
#include "rc5-ref.hh"
#include "rc5-dc.hh"
#include "rc5-eq.hh"
#include "add-approx.hh"

Functions

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_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][2])
 
void rc5_last_round_eq_print_matrices (gsl_matrix *A[2][2][2])
 
void rc5_last_round_eq_normalize_matrices (gsl_matrix *A[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_key_sf (gsl_matrix *A[2][2][2][2])
 
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)
 
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_x_sf (gsl_matrix *A[2][2][2][2])
 
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_bit_i (const uint32_t i, const WORD_T x_i, 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)
 
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)
 
void rc5_last_round_eq_x_find_solutions_rec_i (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, std::vector< WORD_T > *sol_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)
 
double rc5_xdp_add_last_round_exper (WORD_T y, WORD_T yy, WORD_T dx)
 
double rc5_xdp_add_first_round_exper (WORD_T x, WORD_T xx, WORD_T dy)
 
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)
 
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)
 
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, const uint32_t rot_const_prev, 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, const uint32_t rot_const_prev, const double p_thres, const uint32_t hw_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_exper (const WORD_T y, const WORD_T yy, const double p_thres, std::vector< WORD_T > *dx_vec)
 
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_xy_sf (gsl_matrix *A[2][2][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_mid_round_eq_print_matrices (gsl_matrix *A[2][2])
 
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_xdp_add_mid_round_diff_set_out_exper (const WORD_T dy, const double p_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)
 
void rc5_xdp_add_mid_round_diff_set_out_i (const uint32_t i, const double p_thres, const uint32_t hw_thres, const gsl_matrix *A[2][2], const gsl_vector *L, const gsl_vector *C, const WORD_T dy, const WORD_T dx_prev, const uint32_t rot_const_prev, const WORD_T dx, const double p, 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, const WORD_T dx_prev, const uint32_t rot_const_prev, 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, const WORD_T dx_prev, const WORD_T rot_const_prev, const double p_thres, const uint32_t hw_thres, std::vector< WORD_T > *dx_vec)
 
bool rc5_struct_eq_x_params_compare_by_nvariants (const eq_x_params_t first, const eq_x_params_t second)
 

Detailed Description

Procedures for solving certain equations arising during the differential analysis of block cipher RC5 . One such equation is the following equation in x from the last round of RC5:

Author
V.Velichkov, vesse.nosp@m.lin..nosp@m.velic.nosp@m.hkov.nosp@m.@uni..nosp@m.lu $ y - x = y* - (x ^ dx) = k$
  where y,y* are ciphertexts that are the results of the
  modular addition with k in the last round; dx is a fixed XOR
  difference relating the inputs x,x* to the modular addition
  and x is unknown but is related to dx as x ^ x* = dx.

  Functions in this file compute all values of x that satisfy
  the above equation for an unknown but fixed key.

Function Documentation

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 
)

Consider an approximation of modular subtraction of order order. For fixed x, xx, and dy cycle over all possible 2^{order} values of y until we find at least one that satisfies the equation

((x -* y) ^ (xx -* (y ^ dy)))[i] = dz[i] ,

where -* denotes approximation of modular subtraction.

See xdp_sub_fixed_x_approx_rec

void rc5_last_round_eq_alloc_matrices_4d ( gsl_matrix *  A[2][2][2][2])

Allocate memory for the last round equation of RC5

void rc5_last_round_eq_free_matrices_3d ( gsl_matrix *  A[2][2][2])

Free memory reserved by a previous call to rc5_last_round_eq_alloc_matrices_3d .

void rc5_last_round_eq_free_matrices_4d ( gsl_matrix *  A[2][2][2][2])

Free memory reserved by a previous call to rc5_last_round_eq_alloc_matrices .

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 
)

Detect bits of the key that are fixed by y, yy, dx A = AA[0] + AA[1], where AA[k[i]][y[i]][yy[i]][dx[i]] Note: no fixed key bits exist

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 
)

Detect contradictions in the key bits: k[i] != kk[i] for some i A = AA[0] + AA[1], where AA[k[i]][y[i]][yy[i]][dx[i]]

void rc5_last_round_eq_key_sf ( gsl_matrix *  A[2][2][2][2])

Construct the transition probability matrices for the S-function corresponding to the following equation from the last round: $ y - x = y^{*} - (x \oplus \Delta{x}) = k$

Parameters
A$ A[k[i]][][][] $: zero-initialized set of matrices corresponding resp. to $k[i] = kk[i] = 0$ and $k[i] = kk[i] = 1$.
Returns
Transition probability matrices A for $ y - x = y^{*} - (x \oplus \Delta{x}) = k$

$A[2][2][2][2] = A[k[i]][y[i]][y^{*}[i]][\Delta{x[i]}]$, where

  • $y[i]$ : the i-th bit of the first output value.
  • $y^{*}[i]$ : the i-th bit of the second output value.
  • $\Delta{x[i]}$ : the i-th bit of the input difference.
void rc5_last_round_eq_print_matrices ( gsl_matrix *  A[2][2][2][2])

Print the matrices for last round eq. of RC5.

void rc5_last_round_eq_print_matrices ( gsl_matrix *  A[2][2][2])

Print the matrices for last round eq. of RC5.

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 
)

Check if the following holds:

x[(rot_const + log2(w)) : rot_const] = (rot_const_prev ^ rot_const),

where

rot_const = (ciphertext_left[n] & RC5_ROT_MASK) rot_const_prev = (ciphertext_left[n-1] & RC5_ROT_MASK)

For example in the GoUp filter the rotation constants in the last two rounds are resp. r6 and r7 and are of size log2(w) bits. In that case the equation is:

x[(r7 + log2(w)) : r7] = (r6 ^ r7),

In the function r7 = rot_const, seq = (r6 ^ r7) and seq_len is the bit length of seq. In RC5 seq_len is log2(word_size).

Parameters
xvalue
rot_constr7
bit_seqbit sequence that will be matched against seq_len bits rotated by rot_const in x . Example: r6 ^ r7 .
bit_seq_lenlength of the sequence of bits that is checked if it matches the same length of bits in x
See Also
eq_x_params_t .
bool rc5_last_round_eq_x_bit_seq_match_bit_i ( const uint32_t  i,
const WORD_T  x_i,
const uint32_t  rot_const,
const WORD_T  bit_seq,
const uint32_t  bit_seq_len 
)

Checks if the bit of x at position i matches a corresponding bit of a fixed sequence bit_seq. Returns false only if any of the required bits don't match. Otherwise returns true.

Parameters
x_ithe i-th bit of x (i.e. x[i])
See Also
rc5_last_round_eq_x_bit_seq_match_bitwise
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 
)

Wrapper for rc5_last_round_eq_x_bit_seq_match_bit_i . Returns false only if any of the required bits don't match. Otherwise returns true.

For Rc5: x = value, rot_const = r7, bit_seq = r6^r7, bit_seq_len = log2(w)

See Also
rc5_last_round_eq_x_bit_seq_match
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 
)

Wrapper for rc5_last_round_eq_x_find_solutions_rec_i

Parameters
Atransition matrix A[x[i]]|[y[i]][yy[i]][dx[i]]
void rc5_last_round_eq_x_find_solutions_rec_i ( 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,
std::vector< WORD_T > *  sol_vec 
)

Recursively find all solutions x to the equation: $ y - x = y* - (x ^ dx) = k$ where y, y* and dx are fixed.

Parameters
AAtransition matrix AA[x[i]]|[y[i]][yy[i]][dx[i]]
See Also
rc5_last_round_eq_x_count_solutions
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 
)

Check if there is at least one solution x that satisfies the equation: $ y - x = y* - (x ^ dx) = k$ where y, y* and dx are fixed.

Parameters
Atransition matrix AA[x[i]]|[y[i]][yy[i]][dx[i]]
See Also
rc5_last_round_eq_x_find_solutions_rec_i, rc5_last_round_eq_x_find_solutions_rec
void rc5_last_round_eq_x_sf ( gsl_matrix *  A[2][2][2][2])

Construct the transition matrices for counting the number of solutions x of the equation from the last round of RC5:

$ y - x = y* - (x ^ dx) = k$

for fixed y, y* and dx.

Parameters
A[x[i]][y[i]][y*[i]][dx[i]]zero-initialized set of matrices
Returns
Transition probability matrices A for $ y - x = y* - (x ^ dx) = k$.

$A[2][2][2][2] = A[x[i]][y[i]][yy[i]][dx[i]]$, where

  • $y[i]$ : the i-th bit of the first output value.
  • $yy[i]$ : the i-th bit of the second output value.
  • $dx[i]$ : the i-th bit of the input difference.

The same matrices can also be used for counting the number of solutions y of the equation from the FIRST round of RC5:

$ y - x = (y ^ dy) - x* = k$

for fixed x, x* and dy, where x and x* are the chosen plaintexts satisfying a fixed input difference dx = x ^ x*.

When used for the FIRST round the meaning of the dimensions of the A matrices is: A[y][x][xx][dy] (as opposed to A[x][y][yy][dx] for the FIRST round).

LAST round: A[x][y][yy][dx] : LAST round (y, yy, dx - fixed) FIRST round: A[y][x][xx][dy] : FIRST round (x, xx, dy - fixed)

void rc5_mid_round_eq_add_matrices ( gsl_matrix *  A[2][2],
gsl_matrix *  AA[2][2][2][2] 
)

RC5 middle round: compute A from AA where

AA[2][2][2][2] = AA[y[i]][x[i]][dy[i]][dx[i]]

A[2][2] = A[dy[i]][dx[i]] = {(i,j)} AA[i][j][dy[i]][dx[i]]

void rc5_mid_round_eq_alloc_matrices_4d ( gsl_matrix *  A[2][2][2][2])

Allocate memory for the mid round equation of RC5

void rc5_mid_round_eq_free_matrices_4d ( gsl_matrix *  A[2][2][2][2])

Free memory reserved by a previous call to rc5_mid_round_eq_alloc_matrices .

void rc5_mid_round_eq_print_matrices ( gsl_matrix *  A[2][2])

Print the matrices for mid round eq. of RC5.

bool rc5_mid_round_eq_xy_find_solutions_exper ( const WORD_T  dy,
const WORD_T  dx,
std::vector< WORD_T > *  sol_vec 
)

Experimentally list all solutions (x,y) of the equation:

y - x = (y ^ dy) - (x ^ dx) (= k)

See Also
rc5_last_round_eq_x_find_solutions_exper
void rc5_mid_round_eq_xy_sf ( gsl_matrix *  A[2][2][2][2])

Construct the transition matrices for counting the number of solutions (x,y) of the equation from a middle round of RC5:

y - x = (y^dy) - (x^dx) (= k) .

for fixed dy, dx.

Parameters
A[x[i]][y[i]][dy[i]][dx[i]]zero-initialized set of matrices
Returns
Transition probability matrices A for $ y - x = (y^dy) - (x^dx) = k$.

$A[2][2][2][2] = A[y[i]][x[i]][dy[i]][dx[i]]$, where

  • $x[i]$ : the i-th bit of the output value.
  • $y[i]$ : the i-th bit of the input value.
  • $dx[i]$ : the i-th bit of the output difference.
  • $dy[i]$ : the i-th bit of the input difference.
See Also
rc5_last_round_eq_x_sf
double rc5_xdp_add_first_round_exper ( WORD_T  x,
WORD_T  xx,
WORD_T  dy 
)

Experimental computation of the probability:

xdp^{+}_FR(x, xx -> dy) over all keys)

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 
)

Theoretical computation of the probability:

xdp^{+}_LR(y, yy -> dx) over all keys)

Counts the number of solutions x to the equation:

$ y - x = y* - (x ^ dx) = k$

where y, y* and dx are fixed.

A[y[i]][yy[i]][dx[i]]

Warning
Can be used also to compute the "first round" probability:

xdp^{+}_FR(x, xx -> dy) over all keys)

Counts the number of solutions y to the equation:

$ y - x = (y ^ dy) - x* = k$

where x, x* and dy are fixed.

A[x[i]][xx[i]][dy[i]]

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,
const uint32_t  rot_const_prev,
const double  p_thres,
const uint32_t  hw_thres,
std::vector< WORD_T > *  dx_vec 
)

Wrapper for rc5_xdp_add_last_round_diff_set_out_i . Same as rc5_xdp_add_last_round_diff_set_out but with pre-computed matrices.

Parameters
dx_prevthe left ciphertext rotated right by the last rot const
rot_const_prevthe last rot const
See Also
rc5_xdp_add_last_round_diff_set_out_i , rc5_xdp_add_last_round_diff_set_out .
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,
const uint32_t  rot_const_prev,
const WORD_T  dx,
const double  p,
std::vector< WORD_T > *  dx_vec 
)

For fixed y,yy generate all output differences dx for which the probability xdp^{+}_LR(y, yy -> dx) over all keys is above a certain threshold.

rot_const_next_vec_2d contains a list of possible rot constants for every difference in dx_vec

Check if a sequence of log2(n) bits of dx starting from position rot_const_prev is equal to the 0 bit sequence. This check is relevant only for RC5 and is related to the equal rotation constant requirement.

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 
)
double rc5_xdp_add_last_round_exper ( WORD_T  y,
WORD_T  yy,
WORD_T  dx 
)

Experimental computation of the probability:

xdp^{+}_LR(y, yy -> dx) over all keys)

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 
)

Theoretical computation of the probability:

xdp^{+}_MR(dy -> dx) over all tuples (x,y)

It counts the number of solutions (x,y) s.t.:

y - x = (y ^ dy) - (x ^ dx) (= k) for fixed dx, dy

Note
A[dy[i]][dx[i]]
See Also
rc5_xdp_add_last_round
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,
const WORD_T  dx_prev,
const uint32_t  rot_const_prev,
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,
const WORD_T  dx_prev,
const WORD_T  rot_const_prev,
const double  p_thres,
const uint32_t  hw_thres,
std::vector< WORD_T > *  dx_vec 
)
void rc5_xdp_add_mid_round_diff_set_out_exper ( const WORD_T  dy,
const double  p_thres,
std::vector< WORD_T > *  dx_vec 
)

Experimentally generate all dx s.t. xdp^{+}_MR(dy -> dx) > p_thres

void rc5_xdp_add_mid_round_diff_set_out_i ( const uint32_t  i,
const double  p_thres,
const uint32_t  hw_thres,
const gsl_matrix *  A[2][2],
const gsl_vector *  L,
const gsl_vector *  C,
const WORD_T  dy,
const WORD_T  dx_prev,
const uint32_t  rot_const_prev,
const WORD_T  dx,
const double  p,
std::vector< WORD_T > *  dx_vec 
)

For fixed dy generate all output differences dx for which the probability xdp^{+}_MR(dy -> dx) over all keys is above a certain threshold.

The set of output differences satisfies the following conditions:

  • xdp^{+}_MR(dy -> dx) > p_thres
  • HW(dx ^ dx_prev) <= hw_thres (HW = Hamming Weight)
See Also
rc5_xdp_add_last_round_diff_set_out_i

Check if a sequence of log2(n) bits of dx starting from position rot_const_prev is equal to the 0 bit sequence. This check is relevant only for RC5 and is related to the equal rotation constant requirement.

apply approximation only if the prob threshold is very low (e.g. below 2^-5)

double rc5_xdp_add_mid_round_exper ( const WORD_T  dy,
const WORD_T  dx 
)

Experimental computation of the probability:

xdp^{+}_MR(dy -> dx) over all tuples (x,y)

It counts the number of solutions (x,y) s.t.:

y - x = (y ^ dy) - (x ^ dx) (= k)

See Also
rc5_xdp_add_last_round_exper