Search

CN-121984664-A - Method for searching impossible differential differentiator of SKINNY128,128 algorithm

CN121984664ACN 121984664 ACN121984664 ACN 121984664ACN-121984664-A

Abstract

The invention discloses a SKINNY algorithm impossible differential differentiator searching method, which combines differential set propagation with a Boolean satisfaction problem (SAT) modeling technology and integrates the idea of a MISS-in-the-middle. Firstly, simulating the propagation of a differential set in SKINNY round functions from encryption and decryption directions respectively by using probability 1, recording all possible propagation modes, then constructing a bit-oriented SAT constraint model based on the propagation modes, then constructing constraints for possible contradiction points in intermediate rounds, and finally searching for an effective impossible differential divider by solving the SAT model and taking the model solution as a judging condition. The invention overcomes the defects that contradiction points cannot be positioned and indirect contradiction cannot be processed in the prior art, and can automatically and comprehensively search SKINNY for the impossible differential differentiator with longer round number of the algorithm.

Inventors

  • LI LINGCHEN
  • DAI YIMING
  • LIU CHUNYANG
  • WEI YONGZHUANG

Assignees

  • 桂林电子科技大学

Dates

Publication Date
20260505
Application Date
20260209

Claims (7)

  1. 1. A method for searching impossible differential differentiators of SKINNY128,128 algorithm, comprising the steps of: S1, modeling forward differential set propagation: Setting initial input differential which only contains single active byte from input side, simulating forward propagation process of the differential set through SKINNY algorithm multi-round encryption operation, calculating and recording all possible output differential sets of elements in the input differential set aiming at nonlinear S-box operation and linear exclusive OR operation in the propagation process, and forming forward differential set propagation mode set; S2, modeling reverse differential set propagation: setting initial output difference only containing single active byte from output side, simulating reverse propagation process of the difference set through SKINNY algorithm multiple decryption operation, calculating and recording all possible output difference sets of elements in input difference set to form reverse difference set propagation mode set aiming at nonlinear S box operation and linear exclusive OR operation in the propagation process; s3, analyzing contradiction point modes: Comparing and analyzing the state differential set which is transmitted to the middle wheel in the forward direction and is transmitted to the middle wheel in the reverse direction and is obtained in the step S2, and finding out differential value pairs which are positioned at the same state byte position and are mutually incompatible in the two sets to form a contradiction point mode set; s4, constructing an SAT constraint model: Based on the difference set propagation mode set recorded in the steps S1 and S2, constructing SAT constraint describing the difference to propagate forward and backward with probability 1, and based on the contradiction point mode set obtained in the step S3, constructing SAT constraint for triggering contradiction at the appointed middle round and the appointed byte position; s5, model solving and distinguishing device obtaining: And (3) combining all SAT constraints constructed in the step (S4) into an integral solving model, calling a SAT solver to solve, and if the model has a solution, forming an effective SKINNY algorithm impossible differential differentiator by the input differential and the output differential corresponding to the solution, wherein the position of a contradiction point is determined by the added contradiction point constraint.
  2. 2. The method according to claim 1, wherein in steps S1 and S2, the calculating and recording all possible output differential sets of elements in the input differential set specifically includes: for large state S box operation, mapping each element in the input differential set into all possible output differential sets by querying a Differential Distribution Table (DDT) thereof, and merging all outputs; For the exclusive-or operation, the elements in the two differential sets participating in the operation are exclusive-or two by two, and all possible result sets are generated and combined.
  3. 3. The method according to claim 1, wherein in step S4, the building of SAT constraints describing differential propagation, in particular, introducing boolean variables for each possible differential value involved in the differential propagation process, and building boolean logic constraints reflecting the conversion relations between differential values according to the propagation pattern set.
  4. 4. The method of claim 1, wherein in step S4, the contradictory point constraints allow manual configuration to specify target turns and byte positions at which contradictions occur.
  5. 5. The method according to any one of claims 1 to 4, wherein the method uses a SAT model solution as a determination condition that a differential discriminator is not possible.
  6. 6. An electronic device comprising a memory, a processor and a computer program stored on the memory and executable on the processor, wherein the processor implements the steps of the method of any of claims 1-5 when the program is executed.
  7. 7. A computer readable storage medium, on which a computer program is stored, characterized in that the program, when being executed by a processor, implements the steps of the method according to any of claims 1-5.

Description

Method for searching impossible differential differentiator of SKINNY128,128 algorithm Technical Field The invention relates to the technical field of information security and password analysis, in particular to an automatic searching method for an impossible differential discriminator of a block password algorithm SKINNY. Background The impossibility of differential analysis is an important means of evaluating the security of block ciphers, the core of which is to use differential features with a probability of zero to exclude erroneous key candidates. The automatic search impossible differential differentiator is the current mainstream research direction, and mainly depends on Mixed Integer Linear Programming (MILP), boolean satisfaction problem (SAT) and other technologies. For SKINNY128,128 algorithms, existing automatic searching methods for impossible differential differentiators are mainly divided into two categories. The first is a bit-based accurate characterization method that models the differential characteristics of an 8-bit S-box in detail, looking for a differentiator by determining if the SAT/MILP model is solution-free. However, the main drawback is that the model can only prove the "impossibility" of the differentiator without solution, the specific contradiction positions which cause impossibility cannot be revealed, and the direct contradiction or the indirect contradiction cannot be distinguished. The second type is a byte-based miss-in-the-middle method, which respectively builds a model of difference propagation with probability 1 in encryption and decryption directions, and determines an effective discriminator when direct contradiction occurs between two directions propagated to an intermediate state. However, this approach generally captures only direct, explicit contradictions, which are difficult to identify for indirect contradictions that need to be exposed through multi-step reasoning or nonlinear operations. To sum up, the prior art either fails to locate contradictory details or has limited search capabilities, failing to fully mine SKINNY for potentially all impossible differential features in the algorithm. Therefore, a new search method is needed, which can precisely describe the details of the algorithm components, realize the positioning and the constraint of contradiction points, and can process indirect contradiction, so as to find more and longer effective impossible differential differentiators. Disclosure of Invention The invention aims to overcome the defects of the prior art and provide a SKINNY algorithm which combines the ideas of differential set propagation, SAT modeling and MIss-in-the-middle, and an automatic search method of a differential divider is impossible. The method can accurately restrict the positions of contradiction points, effectively process indirect contradiction, and realize more efficient and comprehensive search by taking model solutions as judgment conditions. In order to achieve the above purpose, the invention adopts the following technical scheme: a method of searching for impossible differential differentiators for SKINNY128,128 algorithm, comprising the steps of: S1, modeling forward differential set propagation: In the S box replacement and column confusion exclusive OR operation of each round, not probability screening is carried out, all possible output differences corresponding to each input difference in the current difference set are calculated, the outputs are combined to form a new difference set, and the propagation modes of all input differences and output difference sets are completely recorded to form a forward difference set propagation mode set, and the process is continuously carried out to a designated middle round; Calculating the forward direction The method comprises, starting from the first round, making the state of the input differential set be,The state of the differential set obtained after the replacement of the large-state S box layer is as followsThen, through the row shift operation, the differential set state is obtainedObtaining the output differential set state of the first round through the column-passing confusion operationThen makeI.e. it continues to propagate backwards as the input set for the next round, until the th roundThe state of the output differential set is obtained by the round; In the process of the collective state propagation, only one active byte exists in the initial differential stateAnd initialize the corresponding differential set on the byteThe differential set is then calculated from the round function of SKINNY's algorithmAll sets of elements in (a) that may be generated during differential propagationAnd record all possible propagation modes of the S-box and exclusive-or operation. S2, modeling reverse differential set propagation: using the same principle as the first step, calculating and recording all possible propagation modes of the differential set in each round of opera