Study On The Techniques For Retrieval Of LFSR And Counter Structure By Scan-based Side Channel Attack

The reverse engineering of the integrated circuit(IC)refers to the obtaining the original design from the chip products.Base on the extraction and analysis of the circuit inside the chip,the original design can be deduced.The traditional image-based reverse engineering faces great challenges from many aspects.The adoption of the advanced process makes the disassembly of chip much expensive than ever.The embrace of electronic design automation(EDA)tools leads to the loss of the intelligible information that presented in original design.Thus,the reconstruction of the original high-level design is not feasible anymore.For the feasibility of IC testing,the scan chain has been widely adopted as it provides access to each register.However,the unprotected scan chain has also provided a side channel for the attacker to get the internal state of flip-flops.The attack using the scan chain to get information is called scan-based side-channel attack.The real-time information of the sequential circuit provided by the scan-based attack can help reverse engineering.A new way of sequential circuit reverse engineering arises.However,as the massive number of registers used in the chip,it is hard to identify useful registers from the scan data.Thus,many analysis techniques are proposed for identification.In this dissertation,the analysis technique of two sequential circuits is proposed,which are the linear feedback shift register(LFSR)and the counter.LFSR can be used in stream cipher,while the counter is an important control unit.The reverse engineering of LFSR can be split into two parts: identification and reconstruction of LFSR.Different methods are proposed for each type of LFSR.We first discuss the scan-based attack on standard LFSR.The relation between each pair of the register that belongs to standard Fibonacci LFSR and Galois LFSR is explored.As the register of Fibonacci LFSR is a shift register,the shifting relation can be used to identify the Fibonacci LFSR register.We propose an algorithm called sr-search to check if two registers are obeying the relation of Fibonacci LFSR and to find all Fibonacci LFSR register with order.The improved algorithm fast-sr-search to accelerate the search procedure is proposed.As the first and last bit of Galois LFSR are connected directly,this peculiarity can be used for the start of identification.As the value of the next bit is decided by the former bit and the least significant bit,we can calculate all bit of Galois LFSR.We propose an algorithm called galo-search to check if the register is the next bit of LFSR and to find all LFSR register.The improved algorithm fast-galo-search to accelerate the search procedure is proposed.For the synthesis of LFSR,we conclude the problem of Fibonacci LFSR to a problem of a system of linear equation.And the reconstruction of Galois LFSR is solved during the identification of Galois LFSR.For the scan-based attack of LFSR with external input,the relation between the LFSR register is explored with the single external input.The proposed algorithm sr-search and fast-sr-search are still suitable for Fibonacci LFSR with single external input.For the Galois LFSR with single external input,we discover that the influence of external input can be eliminated by XOR two tap bit.Then the sequence of external input can be deduced.The proposed algorithm galo-search and fast-galo-search can be used to solve the problem.An algorithm called galo-search-input is proposed to implement the above procedure.For the scan-based attack of LFSR with irregular clock,two methods are proposed for the scenario that the LFSR runs continuously for a long time,and the LFSR runs off and on.As the length of LFSR is quite long,we can assume that the shift register in design is mainly the register of LFSR.Thus,we can identify the clock that LFSR is running by check the number of existing shifting relations between each pair of registers.For the scenario that LFSR runs continuously before stopped,the continuous clock period that the number of shifting register is high is obviously the clock that LFSR is running.Then remove the data of other clocks from scan data.The previously proposed method for normal LFSR can be applied to identify the LFSR register.For the scenario that LFSR runs off and on,a method based on the examination of the probability of register that shift relation meets is proposed.For the scan-based attack of the counter,the characteristic of the counter is explored.A method base on toggling frequency is proposed to detect binary counter register.A method for alignment is proposed to distinguish each binary counter.A method based on the likelihood of running period is proposed to find the running clock of the counter.The decade counter can be identified by the method for the binary counter.The ring and Johnson counter can be identified by the identification scheme of Fibonacci LFSR.