International Association for Cryptologic Research

International Association
for Cryptologic Research


Bing Sun


Feistel-like Structures Revisited: Classification and Cryptanalysis
In 2022, Liu et al. summarized the Feistel-like structures which use a single round function, and proposed the unified form of these structures which is named the unified structure. This paper focuses on the unified structures which satisfy the following two conditions: (1) the round function is a permutation and (2) the size of the round function is the same as that of the branch. The main results are as follows: First of all, we give the definition of Affine Equivalence of different structures, present a condition for two structures being affine equivalent, and give two normalized forms of a unified structure. Surprisingly, we find that a target-heavy generalised Feistel structure is always affine equivalent to a source-heavy generalised Feistel structure, which shows these two structures always have almost the same cryptographic properties. Secondly, we give the definition of a self-equivalent structure, whose dual structure is affine equivalent to the structure itself. We prove that there is a large portion of the unified structures such as the SM4 structure and the Mars structure that are among the self-equivalent ones. For these structures, there is a one-to-one correspondence beween the impossible differentials and the zero correlation linear hulls, which shows that the longest integrals of a self-equivalent structure cover at least the rounds of the longest zero correlation linear hulls/impossible differentials. At last, we give the refined full-diffusion round of unified structures, and exploit the $\epsilon-\delta$ technique to compute this value, which can be further used to give a provable security evaluation of unified structures against the impossible differential and zero correlation linear cryptanalysis. For example, we prove that both the longest impossible differential and zero correlation linear hull of the $d$-branch SM4-like structures cover exactly $3d-1$ rounds.
Links between Quantum Distinguishers Based on Simon’s Algorithm and Truncated Differentials
In this paper, we study the quantum security of block ciphers based on Simon’s period-finding quantum algorithm. We explored the relations between periodic functions and truncated differentials. The basic observation is that truncated differentials with a probability of 1 can be used to construct periodic functions, and two such constructions are presented with the help of a new notion called difference-annihilation matrix. This technique releases us from the tedious manual work of verifying the period of functions. Based on these new constructions, we find an 8-round quantum distinguisher for LBlock and a 9/10/11/13/15-round quantum distinguisher for SIMON-32/48/64/96/128 which are the best results as far as we know. Besides, to explore the security bounds of block cipher structures against Simon’s algorithm based quantum attacks, the unified structure, which unifies the Feistel, Lai-Massey, and most generalized Feistel structures, is studied. We estimate the exact round number of probability 1 truncated differentials that one can construct. Based on these results, one can easily check the quantum security of specific block ciphers that are special cases of unified structures, when the details of the non-linear building blocks are not considered.
Programming the Demirci-Selçuk Meet-in-the-Middle Attack with Constraints
Cryptanalysis with SAT/SMT, MILP and CP has increased in popularity among symmetric-key cryptanalysts and designers due to its high degree of automation. So far, this approach covers differential, linear, impossible differential, zero-correlation, and integral cryptanalysis. However, the Demirci-Selçuk meet-in-the-middle ($$\mathcal {DS}$$-$$\mathsf {MITM}$$) attack is one of the most sophisticated techniques that has not been automated with this approach. By an in-depth study of Derbez and Fouque’s work on $$\mathcal {DS}$$-$$\mathsf {MITM}$$ analysis with dedicated search algorithms, we identify the crux of the problem and present a method for automatic $$\mathcal {DS}$$-$$\mathsf {MITM}$$ attack based on general constraint programming, which allows the cryptanalysts to state the problem at a high level without having to say how it should be solved. Our method is not only able to enumerate distinguishers but can also partly automate the key-recovery process. This approach makes the $$\mathcal {DS}$$-$$\mathsf {MITM}$$ cryptanalysis more straightforward and easier to follow, since the resolution of the problem is delegated to off-the-shelf constraint solvers and therefore decoupled from its formulation. We apply the method to SKINNY, TWINE, and LBlock, and we get the currently known best $$\mathcal {DS}$$-$$\mathsf {MITM}$$ attacks on these ciphers. Moreover, to demonstrate the usefulness of our tool for the block cipher designers, we exhaustively evaluate the security of $$8! = 40320$$ versions of LBlock instantiated with different words permutations in the F functions. It turns out that the permutation used in the original LBlock is one of the 64 permutations showing the strongest resistance against the $$\mathcal {DS}$$-$$\mathsf {MITM}$$ attack. The whole process is accomplished on a PC in less than 2 h. The same process is applied to TWINE, and similar results are obtained.

Program Committees

Asiacrypt 2023
FSE 2018