On The Design And Analysis Of Lightweight Block Ciphers' S-boxes

As a new generation of network application,the Internet of Things(Io T)extends the Internet technology from human communication to object communication,which brings great convenience to our lives.As the rapid development of Io T,people pay more attention to data's confidentiality,integrity and availability.Cryptology is the key technology to guarantee the whole system's information security.However,traditional cryptographic algorithms(e.g.,AES)are hard to meet the characteristics of low power consumption and limited computing resources in Io T.As a result,a new class of cryptographic algorithm,lightweight cipher,has been proposed.The so-called lightweight refers to considering the characteristics of hardware environment when designing the algorithms.It strives to achieve the fastest speed and the highest efficiency,while meet a certain level of security.Lightweight block cipher is widely used in Io T and plays an important role in ensuring the normality,stability and security.As the non-linear component,S-box plays a significant role in supporting the security of lightweight block cipher algorithm.Considering the balance between security and efficiency,lightweight block cipher usually adopts 4-bit S-boxes.One special kind of S-box is valued by algorithm designers.It is called involutive S-box.An input remains unchanged after processed by an involutive S-box twice.An involutive S-box has advantages of space and efficiency in circuit implementation.However,further analysis is needed for its security.Lightweight block cipher faces complex implementing environment.An attacker can physically access the cryptographic algorithm chip and launch a special type of attack: differential power analysis(DPA)attack.By collecting the leaked information during the implementation,an attacker can break the whole system using statistic analysis.There are multiple methods of resisting DPA attack.One common way is the threshold implementation proposed by Nikova et al.,which is called the sharing method.It combines secret sharing,threshold cryptography and secure multi-party method to redesign the S-box.This method is provably secure against DPA attack.However,its complexity is so high that it is not effective in practice.Thus,it is important for secure lightweight block cipher algorithm to investigate an efficient,effective and general method of sharing an S-box.With the rapid development of computers,the demand of accelerating cryptanalysis is also increasing.As a promising hardware accelerator,GPU is a low-cost platform with powerful parallel computing.Many research institutes start using general purpose computing on GPU(GPGPU)for non-graphic scientific computing.Thus,the combination of GPU and cryptanalysis becomes a novel research field.By optimizing GPU implementation with respect to the characteristics of cryptanalysis,it can speedup the analysis process greatly,making the cryptanalysis more effective and practical.This thesis investigates the security of 4-bit S-boxes in lightweight block cipher algorithm,and optimize the analysis process using GPGPU.The contributions are as follows:1.We investigate the security of 4-bit involutive S-boxes,including linear resistance,differential resistance and almost-resilient property.We find that 4-bit involutive S-boxes is secure with respect to linear resistance,but fail in strictly satisfying differential resistance requirement.We indicate that almost-resilient property is not so effective for verifying the security of an S-box.We also provide several secure involutive S-boxes for reference.2.We propose an automatic search method for 4-bit S-box's threshold implementation resisting DPA attack.It is a general method that can be applied to any 4-bit S-box.We have successfully found the threshold implementations for several lightweight block ciphers' S-boxes.We also analyze the case of 4-bit involutive S-boxes.3.We investigate the optimization of software pipelining technique in GPGPU.We prove that even partition is the most optimal way for data partition.We propose optimal schedules for different situations and theoretically analyze the best data granularity.Our optimizations achieve around 31%–59% performance improvement using software pipelining.4.We analyze how to use GPGPU to accelerate the automatic search process for S-box's threshold implementation.We propose a GPU-based approach that is sufficiently optimized.The approach is 5-50 times faster than a method without optimization,and approximately 300 times faster than the original CPU implementation.