YAARX: Yet Another ARX Toolkit  0.1
 All Data Structures Files Functions Variables Macros Pages
speck-best-linear-search-tests.cc File Reference

Tests for automatic search for the best XOR linear trail in block cipher Speck . More...

#include "common.hh"
#include "speck.hh"
#include "xlp-add.hh"

Macros

#define UPDATE_BOUND   false
 
#define EPS   (1.0 / (double)(1ULL << 1))
 

Functions

void speck_round_masks_to_add_masks (const WORD_T ml_prev, const WORD_T mr_prev, const WORD_T ml, const WORD_T mr, WORD_T *alpha, WORD_T *beta, WORD_T *gamma)
 
void speck_print_linear_trail (differential_t T[NROUNDS+1])
 
void speck_print_linear_hull (differential_t T[NROUNDS+1])
 
void speck_print_linear_trail (differential_t T[NROUNDS+1], uint32_t nrounds)
 
void speck_add_mask_to_trail (differential_t T[NROUNDS+1], const uint32_t i, const differential_t new_mask)
 
void speck_remove_mask_from_trail (differential_t T[NROUNDS+1], const uint32_t i)
 
void speck_copy_linear_trail (const differential_t from_T[NROUNDS+1], differential_t to_T[NROUNDS+1])
 
void speck_print_linear_trail_cstyle (differential_t T[NROUNDS+1])
 
void speck_best_linear_search_full (differential_t T_best[NROUNDS+1], double *corr_best)
 
void speck_best_linear_search_i (const uint32_t iround, const int32_t ibit, const WORD_T alpha_in, const WORD_T beta_in, const WORD_T gamma_in, const WORD_T imask_R_in)
 
void speck_best_linear_search ()
 
void speck_verify_linear_trail (const uint32_t nrounds, const uint32_t npairs, const WORD_T master_key[SPECK_MAX_NROUNDS], const differential_t T[NROUNDS+1])
 
void test_speck_verify_linear_trail ()
 
void test_speck_best_linear_search_full ()
 
int main ()
 

Variables

const uint32_t g_r1 = SPECK_RIGHT_ROT_CONST_16BITS % WORD_SIZE
 
const uint32_t g_r2 = SPECK_LEFT_ROT_CONST_16BITS % WORD_SIZE
 
const double g_best_B [NROUNDS_MAX]
 
double g_Bn = g_best_B[NROUNDS - 1] * EPS
 
differential_t g_T [NROUNDS+1] = {{0, 0, 0, 0.0}}
 
differential_t g_best_T [NROUNDS+1] = {{0, 0, 0, 0.0}}
 
differential_t g_meiqin_T32 [NROUNDS_MAX+1]
 
differential_t g_vpv_T32 [NROUNDS_MAX+1]
 

Detailed Description

Tests for automatic search for the best XOR linear trail in block cipher Speck .

Author
V.Velichkov, vesse.nosp@m.lin..nosp@m.velic.nosp@m.hkov.nosp@m.@uni..nosp@m.lu
Date
2012-2015

Macro Definition Documentation

#define UPDATE_BOUND   false

If UPDATE_BOUND is false then the algorithm will find ALL trails with probability (g_Bn * EPS) or higher.

Function Documentation

int main ( )

Main function.

void speck_add_mask_to_trail ( differential_t  T[NROUNDS+1],
const uint32_t  i,
const differential_t  new_mask 
)

Add new element at position i in the trail T

void speck_best_linear_search_full ( differential_t  T_best[NROUNDS+1],
double *  corr_best 
)

Full search for the best linear trail of block cipher SPECK (non-recursive).

Note
Feasible for up to 4 bit words and up to 3 rounds.
The complexity is 2^{(n+1) (2*w)}, where n is the total number of rounds and w is the word size. Therefore this function is exponential in the word size and in the number of rounds.

The structure differential_t contains left and right linear masks ml_i and ml_i, input to round i, organized as follow:

T[0] = ml_0, mr_1, 1.0 T[1] = ml_1, mr_1, corr_1 ... T[i] = ml_i, mr_i, corr_i ... T[r] = ml_r, mr_r, corr_r

such that corr_i = corr(ml_{i-1}, mr_{i-1} -> ml_i, mr_i) is the correlation that inout mask propagates to output mask.

The input/output masks alpha_i, beta_i, gamma_i to the modular addition at round i are related to the input/output masks ml_{i-1}, mr_{i-1}, ml_i, mr_i of round i as follow:

alpha_i = ml_{i-1} >>> r1 beta_i = mr_{i-1} ^ (mr_i >>> r2) gamma_i = ml_i ^ mr_i

See Also
speck_best_trail_search_full
void speck_best_linear_search_i ( const uint32_t  iround,
const int32_t  ibit,
const WORD_T  alpha_in,
const WORD_T  beta_in,
const WORD_T  gamma_in,
const WORD_T  imask_R_in 
)

Search for the best linear trail of block cipher SPECK.

Parameters
iroundcurrent round: $ 0 \ge r < NROUNDS$
ibitcurrent bit position (from w-1 to -1)
alphafirst input mask to the addition of round iround
betasecond input mask to the addition of round iround
gammaoutput mask from the addition of round iround
imask_R_inright input mask to the iround-th round
See Also
speck_best_diff_search_i

If UPDATE_BOUND is false then the algorithm will find ALL trails with probability (g_Bn * EPS) or higher.

void speck_copy_linear_trail ( const differential_t  from_T[NROUNDS+1],
differential_t  to_T[NROUNDS+1] 
)

Copy trail from_T to to_T

void speck_print_linear_trail_cstyle ( differential_t  T[NROUNDS+1])

Print the trail in C-style

See Also
speck_print_linear_trail
void speck_remove_mask_from_trail ( differential_t  T[NROUNDS+1],
const uint32_t  i 
)

Remove element from position i in the trail T (sets differences and prob. to zero)

void speck_round_masks_to_add_masks ( const WORD_T  ml_prev,
const WORD_T  mr_prev,
const WORD_T  ml,
const WORD_T  mr,
WORD_T *  alpha,
WORD_T *  beta,
WORD_T *  gamma 
)

From the input and output masks of one round, extract the input and output masks of the linear addtion, using the following relations:

Parameters
ml_prevleft input mask to one round
mr_prevright input mask to one round
mlleft output mask from one round
mrright output mask from one round
alphafirst input mask to the modular adition of one round
betasecond input mask to the modular adition of one round
gammaoutput mask from the modular adition of one round

alpha_i = ml_{i-1} >>> r1 beta_i = mr_{i-1} ^ (mr_i >>> r2) gamma_i = ml_i ^ mr_i

void speck_verify_linear_trail ( const uint32_t  nrounds,
const uint32_t  npairs,
const WORD_T  master_key[SPECK_MAX_NROUNDS],
const differential_t  T[NROUNDS+1] 
)

Given an XOR linear trail for $N$ rounds, experimentally verify the probabilities of the corresponding $N$ one-round linear approximations:

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

bias = prob - 1/2 corr = (2 * bias) = (2 * prob) - 1

See Also
speck_verify_xor_trail

Variable Documentation

const double g_best_B[NROUNDS_MAX]
Initial value:
= {
(1.0 / (double)(1ULL << 0)),
(1.0 / (double)(1ULL << 0)),
(1.0 / (double)(1ULL << 1)),
(1.0 / (double)(1ULL << 3)),
(1.0 / (double)(1ULL << 5)),
(1.0 / (double)(1ULL << 7)),
(0.0 / (double)(1ULL << 9)),
(0.0 / (double)(1ULL << 12)),
(0.0 / (double)(1ULL << 14)),
(0.0 / (double)(1ULL << 17)),
}
differential_t g_meiqin_T32[NROUNDS_MAX+1]
Initial value:
= {
{ 0xA0, 0x629, 0, (1.0 / (double)(1ULL << 0))},
{ 0x78A0, 0x18A1, 0, (1.0 / (double)(1ULL << 1))},
{ 0x90, 0x6021, 0, (1.0 / (double)(1ULL << 4))},
{ 0x6080, 0x4081, 0, (1.0 / (double)(1ULL << 1))},
{ 0x80, 0x1, 0, (1.0 / (double)(1ULL << 1))},
{ 0x1, 0, 0, (1.0 / (double)(1ULL << 0))},
{ 0xE00, 0xC00, 0, (1.0 / (double)(1ULL << 1))},
{ 0x3040, 0x3058, 0, (1.0 / (double)(1ULL << 3))},
{ 0x82, 0xC0E2, 0, (1.0 / (double)(1ULL << 2))},
{ 0x1F8E, 0x1B8F, 0, (1.0 / (double)(1ULL << 1))},
{ 0, 0, 0, (1.0 / (double)(1ULL << 0))},
}
Initial value:
= {
{ 0xA0, 0x3021, 0, (1.0 / (double)(1ULL << 0))},
{ 0x80, 0x4081, 0, (1.0 / (double)(1ULL << 1))},
{ 0x200, 0x201, 0, (1.0 / (double)(1ULL << 0))},
{ 0x818, 0x81C, 0, (1.0 / (double)(1ULL << 1))},
{ 0x8000, 0xA010, 0, (1.0 / (double)(1ULL << 2))},
{ 0x85C2, 0x8442, 0, (1.0 / (double)(1ULL << 1))},
{ 0, 0, 0, (1.0 / (double)(1ULL << 0))},
{ 0, 0, 0, (1.0 / (double)(1ULL << 0))},
{ 0, 0, 0, (1.0 / (double)(1ULL << 0))},
{ 0, 0, 0, (1.0 / (double)(1ULL << 0))},
{ 0, 0, 0, (1.0 / (double)(1ULL << 0))},
}