Search

Search Results

• COMPUTATIONALLY EFFICIENT METHOD FOR DETERMINING THE AVERAGE LINEAR PROPERTIES OF PSEUDO-DYNAMIC SUBSTITUTIONS

  S.V. Polikarpov, V.A. Prudnikov, K.E. Rumyantsev

  2021-01-19

  Abstract ▼

  Pseudo-dynamic substitutions PD-sbox can become an effective replacement for fixed substitutions
  in pseudo-random functions, since they have the positive properties of both fixed substitutions
  (low consumption of computational resources) and dynamic substitutions (which can radically complicate
  the application of statistical cryptanalysis methods). The problem of active implementation of
  pseudo-dynamic substitutions is, inter alia, the absence of a computationally efficient method for
  determining the averaged linear properties for the entire set of equivalent substitutions generated
  using PD-sbox, while in most cases, only the determination of the maximum values of the prevalence
  (bias) bias (α, β) from the ideal value 1/2. To solve this problem, an original method is proposed,
  which consists in the fact that the maximum dominance values are calculated only for relatively small
  fixed substitutions included in the PD-sbox, and the resulting maximum dominance values are obtained
  by iterative calculation using a logical-probabilistic expression for the Exclusive OR operation
  -NO (XNOR). The effect of using the proposed method is a dramatic reduction in computational
  operations and, accordingly, the possibility of determining on a typical personal computer the maximum
  values of the prevalence bias (α, β) for 16-element PD-sboxes consisting of 8-bit fixed substitutions
  (which is unattainable when using a trivial method).

• SYNTHESIS OF PSEUDO-DYNAMIC FUNCTIONS PD-sbox-ARX-32

  S.V. Polikarpov, V. А. Prudnikov, К.Е. Rumyantsev

  2024-11-10

  Abstract ▼

  The aim of the work is to develop a method for synthesizing optimal pseudo-dynamic functions
  PD-sbox-ARX-32, 32-bit in size, in accordance with conflicting requirements for cryptographic characteristics
  of the considered structure. The methods for synthesizing classical sbox’es are considered, including
  those using evolutionary and genetic methods. The requirements for cryptographic characteristics are
  presented, both for the PD-sbox functions and for their constituent elements (classical sbox and ARX functions).
  A method for synthesizing pseudo-dynamic functions PD-sbox-ARX-32 is proposed, including two
  stages: 1) heuristic search for a structure corresponding to conflicting requirements for the resulting cryptographic
  characteristics, consumed software and hardware resources, as well as the speed of operation of the
  presented function; 2) search for optimal parameters of the main element of PD-sbox-ARX-32 – ARX functions,
  using the evolutionary method, the essence of which is to select the values of cyclic shifts in ARX functions.
  As a result, a set of four ARX functions was obtained for the pseudo-dynamic transformation of PDsbox-
  ARX-32, having the weight of linear characteristics equal to and difference characteristics equal
  to (in this case the empirical weight is ). To determine the weights of cryptographic characteristics,
  methods based on the use of SAT solvers were used in the work. The paper concludes that the selected
  structure of the 32-bit ARX function in the PD-sbox allows for a critical path (maximum number of sequential
  addition operations modulo ) that is four times smaller than that of the 8-iteration 32-bit
  Alzette-like structure, with a twofold increase in the number of operations and comparable maximum values
  of the weights of the difference and linear characteristics. A similar result is obtained when comparing
  the 32-bit ARX function with the 8-iteration 32-bit transformation from the Speck32 block cryptographic
  algorithm. The proposed method for synthesizing the parameters of the 32-bit ARX function allows for
  minimizing the number of assembler instructions spent on cyclic shift operations when implemented on
  low-resource 8-bit microcontrollers AVR (for example ATmega328P).

• STUDY OF THE MINIVERSION PROPERTIES IN THE PSEUDO-RANDOM FUNCTION PCOLLAPSER

  S.V. Polikarpov, V.А. Prudnikov, К. Е. Rumyantsev

  2023-02-27

  Abstract ▼

  The aim of the work is to evaluate the cryptographic properties of the pCollapser family of pseudo-
  random functions (PRF) based on the study of the properties of its mini_pCollapser_12x12 miniversion
  using fixed substitutions with extremely low cryptographic properties. As a comparison element,
  we used a mini-version of a typical function based on an SP-net, containing a similar number of fixed
  substitutions, and having a similar input/output dimension equal to 12 bits. To achieve this goal, the
  following tasks were solved: – determination of the structure of the studied functions and the number of
  rounds; – definition of a model for the formation of fixed substitutions with extremely low cryptographic
  properties; – generation of sets of 6-bit fixed substitutions with extremely low cryptographic properties; – inclusion of the substitutions obtained into the functions under study and determination of the main
  cryptographic properties of functions – the maximum dominance value for individual key values and the
  maximum dominance value averaged over the entire set of keys, the maximum and averaged over the
  entire set of keys value in the difference distribution table, algebraic degree and algebraic immunity;
  – analysis of the obtained results. The paper presents two models for the formation of fixed substitutions
  with extremely low cryptographic properties – based on the mixing of cell values in a pre-filled table
  and based on the simplest ARX function (consisting of modulo addition, cyclic shift and XOR). The use
  of fixed substitutions with extremely low non-linearity makes it possible to estimate how complex (nonlinear)
  the function under study is and what minimum level of non-linearity is necessary to effectively
  destroy the statistical dependencies between input/output data. In addition, it becomes clear that ARX
  functions can be used as non-linear elements, which often have controversial and clearly low cryptographic
  properties, but allow creating high-speed software and hardware implementations. It has been
  determined that the PRF pCollapser mini-version, in contrast to the typical function based on the SP
  network, makes it possible to obtain a high-quality non-linear function from the set of ARX-functions
  with extremely low cryptographic properties, given that no other non-linear elements are presented in
  pCollapser. The obtained results reflect the existence of a fundamental difference between the
  pCollapser PRF and a typical SP-network based PRF and confirm the correctness of the concept of
  PD-sbox pseudo-dynamic substitutions and the pCollapser function consisting of them as a whole.