On The Recovery Of Secret Components For Substitution Bit-wise Permutation Structure

The SPN(substitution permutation network) is an important structure of block cipher. The substitution bit-wise permutation structure is a special SPN. In case the S-box and P-box are designed as the secret components which are key dependent, it can effectively strengthen the security of block ciphers. In this thesis, we present new methods of recovering the secret components for substitution bit-wise permutation structure using some cryptanalytic techniques, such as combined distinguisher based on multiple information collection, method of optimal distinguisher, clustering analysis, filtering method and algebraic techniques, and use them to investigate the new method of recovering the secret key of substitution bit-wise permutation structure. The contributions of the dissertation are outlined as follows:1. This paper investigates the construction of optimal distinguisher under the conditions of expected probability distribution is unknown. We propose the conception and the construction approach of approximate optimal distinguisher. Sequentially, the advantage of this new distinguisher is evaluated. The theoretical model suggests that the decision result between approximate optimal distinguisher under the condition of unknown expected probability distribution and optimal distinguisher under the condition of known one is in agreement to almost all the sample sequence, in case the data complexity is large enough. It shows that the limitation of the optimal distinguisher is equal to that of the approximate optimal distinguisher. This distinguisher can be used widely in the field of distinguishing attack and key recovery attack.2. The differential cryptanalysis on recovering the secret S-box of substitution bit-wise permutation structure is improved. We propose a new data collection method of secret S-box using multiple information collection technique and approximate optimal distinguisher, and use them to construct a new distinguisher with more distinguishing advantage. This method could make full use of all the differential information coming from multiple independent distinguishing characteristics synthetically, which can help us to reduce the time and data complexity significantly. Furthermore, we propose an efficient method of constructing the entire correct Slender-sets by pruning search algorithm with two filters proposed by Borghoff et al. This further reduces the data complexity. According to the method presented in this paper, we implemented a successful attack on the full round cipher Maya. Our attack is the best known differential result against the substitution bit-wise permutation structure with secret S-box.3. We first apply the differential cryptanalysis of recovering the key S-box to the substitution bit-wise permutation structure with public S-box. We present a new method of recovering the secret key. According to the method of approximate optimal distinguisher and the efficient distinguishing characteristics, which can distinguish the correct key and incorrect ones, we propose a new key recovery attack on the first round key using modified Slender-set differential cryptanalysis. In particular, we apply our attack on PRESENT and PRINTCIPHER. To the best of our knowledge, our attack is the best known differential attacks on PRESENT-80 and PRINTCIPHER in practice. This provides for us the new idea and techniques of differential attack against substitution bit-wise permutation structure with public S-box.4. By combining both algebraic technique and Slender-set cryptanalysis, we propose a new cryptanalytic method against substitution bit-wise permutation structure with secret S-box. The basic idea of our attack is to build the low degree multivariate system of equations arising from the Slender-set differential cryptanalysis with two filters and solve the equations system for recovering the coordinate functions of secret S-boxes. The Slender-set differential-algebraic attack is better than Slender-set differential attack in time complexity. This provides for us a new method of recovering the secret S-box of substitution bit-wise permutation structure with secret S-box.5. We give a new expression of the principle of Slender-set linear cryptanalysis. The linear cryptanalysis on recovering the secret S-box of substitution bit-wise permutation structure is revised and improved. By using the multiple information collection technique and weight estimation method, the construction of statistic and the method of partition during the Slender-set linear cryptanalysis are improved and fulfilled. Besides, we present a necessary condition of the correct coordinate functions of secret S-box. Sequentially, we propose a method of constructing all correct coordinate function of secret S-boxes by pruning search algorithm with efficient filtering method. Finally, we focus on the settings of substitution bit-wise permutation structure where the S-boxes are repeated for the first and last rounds. And we propose an effective method of determining the correct S-box from the equivalent ones. In particular, we implemented the improved Slender-set linear attack on the full round Maya cipher. To the best of our knowledge, our attack is the best known linear attacks on substitution bit-wise permutation structure. This result provides a more efficient linear cryptanalysis against the substitution bit-wise permutation structure with secret S-box.6. We first apply the linear cryptanalysis of recovering the secret key to the substitution bitwise permutation structure with public S-box. According to the distinguishing characteristics which can distinguish the correct key and incorrect ones, we present two methods of recovering the secret key using Slender-set linear cryptanalysis. One can recover the secret key in first round, the other can recover the secret key in both first and second rounds. We apply our attack to the cipher PRESENT-80. The experiments show that we can recover the entire 80 key bits of 12-rounds PRESENT-80 with 322 data complexity, 362 time complexity, and negligible memory complexity. This provides for us the new method and techniques of linear attack on substitution bit-wise permutation structure with public S-box.7. We investigate the linear cryptanalysis on substitution bit-wise permutation structure with secret permutations. For the m-bit S-box, we point out the information leakage between the only one nonzero m-bit masks and multi-nonzero m-bit masks for output of permutation when the input masks which weight is equal to or less than m. By guessing the 4-bit input positions of the secret permutation using exhaustive search, we construct a distinguisher with more advantages by combining multiple distinguishing characteristics, which are used in Slender-set linear cryptanalysis. This distinguisher can determine which 4-bit input positions of the secret permutation are mapped into the same S-box input. And then, we present a method of constructing the equivalent secret permutations based on this distinguisher. Finally, we focus on the settings of substitution bit-wise permutation structure where the permutations are repeated for the first and last rounds. And we propose a method of identifying the correct permutation from equivalent ones with low time complexity. We test our attack on 12-rounds substitution bit-wise permutation structure. The experiments show that the correct permutation can be recovered with 30.82 known plaintexts, 49.62 time complexity and 19.282 memory complexity at a success rate of 90%. The results obtained enrich the recovery method of secret components for substitution bit-wise permutation structure.