Algorithm for Non-Linear Feedback Shift Registers Delay Optimization

Abstract: Information Technology has revolutionized the way of our life, the raise of information technology has given birth to the information security. The design and implementation of information security techniques especially for wireless systems such as Mobiles, and RFIDs is receiving a lot of attentions. Stream ciphers are very good candidates for providing information security to wireless systems specially for RFIDs, because they are fast as compared to block ciphers, easy to implement, have small footprint, and consume less power. LFSRs can be use to implement the stream ciphers but they care exposed to different kind of cryptanalytic attacks on the other hand NLFSR based stream ciphers are resistant to cryptanalytic attacks to which pure LFSR based stream cipher are exposed. Just like LFSRs the NLFSRs can also be implemented in two types of configurations i.e. Fibonacci and Galois. The critical path of the Galois based NLFSRs is smaller than the Fibonacci NLFSRs this make Galois NLFSRs favorite for applications which need to run at a faster speed. Fibonacci NLFSRs can be converted to Galois NLFSRs but the conversion from Fibonacci to Galois is one-to-many relation i.e. for a single Fibonacci NLFSR we can have many equivalent Galois NLFSRs. The dilemma is that not all the equivalent Galois NLFSRs are optimal so in order for efficient implementation one has to search for the best possible Galois NLFSR. The complexity of search space is 0(nk), here represents the n − bit NLFSR and represents the number of products in the ANF of the feedback function of Fibonacci NLFSR, the NLFSR used in existing stream cipher usually havek less than or equal to 32( for hardware efficiency reasons) and n is of order of 128 (for cryptographic security reasons). The complexity of the search space shows that the normal brute force method will take considerable amount of time to produce the results. To address this problem a heuristic algorithm is proposed in [6] which uses the Primary Cost Function to estimate the critical path of the NLFSRs and produce the results, however the algorithm in [6] did not addressed a lot of issues for example it was unable to divide the products among the functions equally, it was unable to divide the product in such a way which would lead to optimization by synthesis tool. The Primary Cost Function proposed in [6] had flaws it was unable to find the difference between the function which can be optimized and which cannot be. This thesis proposes another heuristic algorithm which addresses the problem present in the [6]. The Primary Cost Function used in the [6] is also used in the proposed algorithm but with some modification and improvements. Besides using Primary Cost function, the proposed algorithm also uses other cost functions such Secondary Cost, XOR reduced Cost and Number of Literals Cost functions to find the best possible Galois NLFSR. The algorithm proposed in this thesis was tested on Vest, Achterbahn, Gain-128/80 ciphers and Cipher [8]. The Vest improved by 5.28% in delay and 17.39% in terms of area as compared to the results of [6], similarly Achterbahn, Gain, and Cipher [8] improved by 1.79%, 16.63%, 1.43% in delay and improvement in area were 2.09%, 1.001% , - 0.101% respectively.