Research On GPU-Based Differential Analysis Method

Differential cryptanalysis has been one of the hot spots in cryptanalysis,whose strength and security of cryptographic algorithms can be deduced by studying the propagation of differential characteristic in order to defend against differential attacks,defense mechanisms such as obfuscation,masking and multi-round iteration are applied to cryptographic algorithms to increase the complexity of the differential propagation.At the same time,as the block size gets larger,the number of active S-boxes per round,and the number of output branches per active S-box increases,the candidate output difference generated in each round grows exponentially during the differential propagation.Conventional CPU computing methods have become increasingly difficult to cope with the computational demands of differential analysis.To improve the efficiency of differential attacks,GPU parallel computing techniques are introduced into differential analysis.In this paper,we study efficient differential analysis methods based on GPU parallel computing,and the main work is as follows:1)Cryptographic S-boxes is an indispensable and important component in the process of differential cryptanalysis,and a GPU-based evaluation method of differential uniform is proposed for large-state cryptographic S-boxes.By designing a GPU parallel solution for16/32-bit S-boxes,the kernel function is designed to decompose the multiple loops in the differential computation into GPU threads for parallel execution,and to find the maximum value of the computed differential distribution table using CUDA parallel reduction.Based on GPU parallel computing,the time of 16/32-bit S-box differential evaluation is greatly reduced.2)A multi-differential analysis method based on Branch-and-Bound（B&B）and the Meet-in-the-Middle-Attack（MITM）is proposed.Multi-differential analysis is to use multiple input differentials with multiple output differentials to search for a differential pair with a high probability of r rounds,which has a higher probability than the differential distinguisher probability searched in traditional analysis methods,and the time complexity and data complexity are lower when using this differential pair for key recovery.For GIFT-64,we perform multiple differential analysis based on the B&B and the MITM,and propose a differential storage strategy based on triple and adjacency list to solve the problem of effective storage matching at large data volumes,and finally obtain 42 13-round high probability differential pairs with the highest probability of 2^-60.41.3)The computational overhead of multi-difference analysis is high,and the search efficiency is low using CPU computing method.To reduce the computational overhead,it is usually necessary to set strict pruning conditions to narrow the search space,which leads to the possibility of discarding the high-probability difference paths during the search process.In order to search more high-probability differential pairs of GIFT-64,a GPU-based multi-differential analysis method is proposed.During the search process,the pruning condition is relaxed,the B&B is combined,and the CUDA collaborative group synchronization idea is used for thread synchronization,and 57 13-round high-probability difference pairs are searched,of which the highest probability is 2^-60.41.