Design And Implementation Of S-boxes In Lightweight Symmetric Primitives

In the era of the Internet of Everything(IoE),network security is facing more and more challenges with the development of the Internet of Things(IoT).As the cornerstone for the network security,cryptographic schemes plays a critical role in information transfer,encipherment protection,and security authentication.The traditional symmetric cryptographic primitives are designed to maximize security strength and are mainly used in resource-rich scenarios such as desktops and servers.In resource-constrained environments,the design of symmetric cryptographic primitives tends to be lightweight.Designers require a decent trade-off between the software and hardware implementation performance and the security.Consequently,the lightweight symmetric cryptographic primitives have gradually become one of the research hotspots in recent years.In essence,the core of the design and implementation of lightweight symmetric primitives is the research on components.The innovation of the component design for symmetric primitives is the key to solve the new challenges posed by information systems.The S-box is the nonlinear component of symmetric cryptographic primitives since it provides "confusion" for ciphers.The design of lightweight S-boxes is divided into two main aspects:security properties and hard ware/soft ware implementation performance.From the perspective of security,it is necessary to accurately control multiple cryptographic properties to meet different security requirements.From the perspective of software/hardware implementation,Although some commercial software can optimize for circuits in general scenarios,the small-sized s-boxes(e.g.4-bit or 5-bit)adopted in lightweight symmetric primitives need a specialized optimization method for implementation.In summary,we carry out the research and the results are as follows:We propose an SAT/SMT-based model toward design Sboxes.In previous work,designers pay more attention to differential uniformity and linearity.These two properties influence the resistance against differential and linear attacks.However,in the lightweight S-boxes,other cryptographic properties,such as the frequency of differential uniformity and linearity,the number of BIBO(Bad Input and Bad Output)patterns in the differential distribution table(DDT)and linear approximation table(LAT),can more accurately measure the resistance against differential and linear attack.When considering multiple security properties,the existing S-box design methods need to be filtered step by step.It will lead to low efficiency,coarse granularity,and the loss of some S-boxes.To precisely control and consider multiple security properties,we propose an SAT-based automatic model to search for S-boxes.According to our research,most of the security properties can be directly reflected by the difference distribution table and linear approximation table of the S-box.Based on this,we put forward a new design idea:we can first construct the difference distribution table and linear approximation table that meet the security requirements and then reconstruct the corresponding S-box in reverse.·Firstly,we transform the relationship between S-box and its DDT and LAT into satisfiability problem.With the given DDT and LAT,we can reconstruct the corresponding S-boxes by SAT solver.We use the DDT of PRESENT’s and KECCAK’s Sboxes as examples and reconstruct all 256 4-bit S-boxes and 1024 5-bit S-boxes,respectively.·Secondly,we transform the security requirements for DDT and LAT into constraints,which are encoded in the form of Boolean equations and added to the model.Then,we can use the reconstructing method to search for desired S-boxes.Compared with the previous methods,we can consider multiple cryptographic properties in a more fine-grained way.For 4-bit S-boxes,we search out 3723/947/620 S-boxes with the same properties as S-boxes of PRESENT/GIFT/RECTANGLE,respectively.In addition,we find 834 new S-boxes with fewer BIBO patterns in the DDT and LAT at the cost of a slight increase of the difference uniformity.For 5-bit S-boxes,we search out 31/28 S-boxes with the same properties as S-boxes of KECCAK/ASCON,respectively.Furthermore,we find 17 new S-boxes with lower differential uniformity.When we get an S-box with good properties,we can get a class of S-boxes with the same properties through equivalent transformation.Therefore,the theoretical research of S-box equivalent classification is also of great significance.In the Journal of Designs,Codes and Cryptography(DCC)2019,Boura et al.presented a conjecture about the DDTequivalence class of S-boxes:if rows of a DDT are pairwise distinct,the corresponding Sboxes are trivially DDT-equivalent to each other.We creatively put forward a proposition and two corollaries and successfully narrow the verification range from 244 to 259.Finally,we use the reconstructing method to prove the correctness of the conjecture for 4-bit Sboxes.We propose an SAT/SMT-based model for optimaizing the implementation of S-boxes.The area cost is one of the most important criteria for lightweight S-boxes.However,before that,there is no effective method to search for the smallest area implementation of S-box.The existing optimization methods can be classified into two categories.Heuristic method aims at finding an implementation but not with the smallest area cost.The other one is an SAT-based method which focuses on the minimized gates.Nevertheless,implementation with the least number of gates would not always lead to the smallest area cost.We re-encode the multi-inputs standard cell gates and take the area cost as the objective function to search for the implementation of a given S-box.In order to improve the search speed,we propose a parallel algorithm and a precomputing algorithm for determining the upper and lower bounds of the number of standard cell gates.Finally,we apply the model to the 4-bit S-boxes in PICCOLO,SKINNY,RECTANGLE and LBLOCK,respectively.Compared with the previous work,the area cost of RECTANGLE’s S-box is reduced to 18.00 GE under the same technology library and standard cell gates.At the same time,it proves that the existing hardware implementation area of S-boxes in PICCOLO,SKINNY and LBLOCK is optimal.Thanks to the accelerated techniques,our model is also applicable to the search of 5-bit S-box hardware implementation in KECCAK and ASCON.