8 November 2021 in IEEE Access
Bit permutations are efficient linear functions often used for lightweight cipher designs. However, they have low diffusion effects, compared to word-oriented binary and maximum distance separable (MDS) matrices. Thus, the security of bit permutation-based ciphers is significantly affected by differential and linear branch numbers (DBN and LBN) of nonlinear functions. In this paper, we introduce a widely applicable method for constructing S-boxes with high DBN and LBN. Our method exploits constructions of S-boxes from smaller S-boxes and it derives/proves the required conditions for smaller S-boxes so that the DBN and LBN of the constructed S-boxes are at least 3. These conditions enable us to significantly reduce the search space required to create such S-boxes. Using the unbalanced- Bridge and unbalanced- MISTY structures, we develop a variety of new lightweight S-boxes that provide not only both DBN and LBN of at least 3 but also efficient bitsliced implementations including at most 11 nonlinear bitwise operations. The new S-boxes are the first that exhibit these characteristics.
3 June 2021 in IEEE Access
Substitution boxes (S-boxes) are essential components of many cryptographic primitives. The Dijkstra algorithm, SAT solvers, and heuristic methods have been used to find bitsliced implementations of S-boxes. However, it is difficult to apply these methods for 8-bit S-boxes because of their size. Therefore, to implement these S-boxes so that the countermeasure of side-channel attack can be applied efficiently, using structures such as Feistel, Lai-Massey, and MISTY that can be bitsliced implemented with a small number of nonlinear operations has been widely used. Since S-boxes constructed with structures consist of small S-boxes and have specific designs, there are limitations to their cryptographic security and efficiency. In this paper, we propose a new method for generating S-boxes by stacking bitwise operations from the identity function, an approach that is different from existing methods. This method can be expressed in Markov decision process, and reinforcement learning is a suitable solver for Markov decision process. Our goal is to train this method to an agent through reinforcement learning to generate S-boxes to which the masking scheme, which is a countermeasure of side-channel attack, can be efficiently applied. In particular, our method provided various S-boxes superior or comparable to existing S-boxes. We produced 8-bit S-boxes with differential uniformity 16 (resp. 32) and linearity 128 (resp. 128), generated with nine (resp. eight) nonlinear operations, for the first time. To our best knowledge, this is the first study to construct cryptographic S-Box by incorporating reinforcement learning.
13 January 2022 in Cryptography and Communications
1 July 2024 in IEEE Internet of Things Journal
In this paper, we propose a methodology for finding impossible differential distinguishers for permutations used in sponge-like constructions. Given the difference between typical block ciphers and such permutations in terms of key additions, we initiate the construction of an impossible differential trail starting from the middle round. Based on the proposed methodology, we present several new or improved truncated and impossible distinguishers for ASCON, DRYGASCON, SYCON, and SHAMASH, all of which were submitted to the NIST Lightweight Cryptography project. For ASCON, we significantly reduce the attack complexity compared to existing results, and notably, this marks the first instance of proposing specific truncated and impossible differential trails for SYCON and SHAMASH. Finally, we discuss how truncated differential distinguishers, identified using our methodology, enable key-recovery attacks in weak-key setting. The methodology of this paper is significant not only for the ciphers considered but also for other permutation-based ciphers with similar structures. Given that the target algorithms are suitable for resource-constrained devices, our results provide new insights into security for the Internet of Things.
10 May 2024 in IEEE Transactions on Computers
In this paper, we present a new method to find Sbox circuits with optimal multiplicative complexity (MC), i.e., MC-optimal S-box circuits. We provide new observations for efficiently constructing circuits and computing MC, combined with a popular pathfinding algorithm named A*. In our search, the A* algorithm outputs a path of length MC, corresponding to an MC-optimal circuit. Based on an in-depth analysis of the process of computing MC, we enable the A* algorithm to function within our graph to investigate a wider range of S-boxes than existing methods such as the SAT-solver-based tool [1] and LIGHTER [2]. We provide implementable MC-optimal circuits for all the quadratic 5-bit bijective S-boxes and existing 5-bit almost-perfect nonlinear (APN) S-boxes. Furthermore, we present MC-optimal circuits for 6-bit S-boxes such as Sarkar Gold, Sarkar Quadratic, and some quadratic permutations. Finally, we theoretically demonstrate new lower bounds for the MCs of S-boxes, providing tighter bounds for the MCs of AES and MISTY S-boxes than previously known. This study complements previous results on MC-optimal S-box circuits and is intended to provide further insight into this field.
4 January 2022 in IEEE Access
The substitution box (S-box) is one of the major components of cryptographic algorithms. An important issue for cryptographic algorithm designers in ensuring sufficient security from linear cryptanalysis, one of the most powerful attacks, is finding an S-box with a sufficiently low linear spectrum. However, to the best of our knowledge, most of the published S-box analysis tools cannot generate linear approximation tables for large S-boxes, such as 16-bit S-boxes. Even tools that support the generation of 16-bit linear approximation tables using parallel processing, such as Eval16BitSbox, require a long time.We used bitslice, which can efficiently process bitwise operations in parallel by taking advantage of independent operations, for generating a linear approximation table. In this study, the linear approximation table generation method implemented using the element unit operation of the existing S-box was upgraded to a vector unit operation in a bitslice manner. This improved method enabled the immediate creation of tables, even for 16-bit Sboxes. This approach allows cryptographic algorithm designers to consider a wider variety of S-boxes.