Further Results on Efficient Implementations of Block Cipher Linear Layers

At the FSE conference of ToSC 2018, Kranz et al. presented their results on shortest linear programs for the linear layers of several well known block ciphers in literature. Shortest linear programs are essentially the minimum number of 2-input xor gates required to completely describe a linear system of equations. In the above paper the authors showed that the commonly used metrics like d-xor/s-xor count that are used to judge the “lightweightedness” do not represent the minimum number of xor gates required to describe a given MDS matrix. In fact they used heuristic based algorithms of Boyar-Peralta and Paar to find implementations of MDS matrices with even fewer xor gates than was previously known. They proved that the AES mixcolumn matrix can be implemented with as little as 97 xor gates. In this paper we show that the values reported in the above paper are not optimal. By suitably including random bits in the instances of the above algorithms we can achieve implementations of almost all matrices with lesser number of gates than were reported in the above paper. As a result we report an implementation of the AES mixcolumn matrix that uses only 95 xor gates. In FSE conference of ToSC 2019, Li et al. had tweaked the Boyar-Peralta algorithm to get low depth implementations of many matrices. We show that by introducing randomness in the tweaked algorithm, it is again possible to get low depth implementations with lesser number of gates than the above paper. As a result, we report a depth implementation of the AES mixcolumn matrix that uses only 103 xor gates, which is 2 gates less than the previous implementation. In the second part of the paper, we observe that most standard cell libraries contain both 2 and 3-input xor gates, with the silicon area of the 3-input xor gate being smaller than the sum of the areas of two 2-input xor gates. Hence when linear circuits are synthesized by logic compilers (with specific instructions to optimize for area), most of them would return a solution circuit containing both 2 and 3-input xor gates. Thus from a practical point of view, reducing circuit size in presence of these gates is no longer equivalent to solving the shortest linear program. In this paper we show that by adopting a graph based heuristic it is possible to convert a circuit constructed with 2-input xor gates to another functionally equivalent circuit that utilizes both 2 and 3-input xor gates and occupies less hardware area. As a result we obtain more lightweight implementations of all the matrices listed in the ToSC paper.

More Results on Shortest Linear Programs

Subhadeep Banik

At the FSE conference of ToSC 2018, Kranz et al. presented their results on shortest linear programs for the linear layers of several well known block ciphers in literature. Shortest linear programs are essentially the minimum number of 2-input xor gates required to completely describe a linear system of equations. In the above paper the authors showed that the commonly used metrics like d-xor/s-xor count that are used to judge the ``lightweightedness'' do not represent the minimum number of xor gates required to describe a given MDS matrix. In fact they used heuristic based algorithms of Boyar/Peralta and Paar to find implementations of MDS matrices with even fewer xor gates than was previously known. They proved that the AES mixcolumn matrix can be implemented with as little as 97 xor gates. In this paper we show that the values reported in the above paper are not optimal. By suitably including random bits in the instances of the above algorithms we can achieve implementations of almost all matrices with lesser number of gates than were reported in the above paper. As a result we report an implementation of the AES mixcolumn matrix that uses only 95 xor gates. In the second part of the paper, we observe that most standard cell libraries contain both 2 and 3-input xor gates, with the silicon area of the 3-input xor gate being smaller than the sum of the areas of two 2-input xor gates. Hence when linear circuits are synthesized by logic compilers (with specific instructions to optimize for area), most of them would return a solution circuit containing both 2 and 3-input xor gates. Thus from a practical point of view, reducing circuit size in presence of these gates is no longer equivalent to solving the shortest linear program. In this paper we show that by adopting a graph based heuristic it is possible to convert a circuit constructed with 2-input xor gates to another functionally equivalent circuit that utilizes both 2 and 3-input xor gates and occupies less hardware area. As a result we obtain more lightweight implementations of all the matrices listed in the ToSC paper.

2019

Serial Lightweight Implementation Techniques for Block Ciphers

Muhammed Fatih Balli

Most of the cryptographic protocols that we use frequently on the internet are designed in a fashion that they are not necessarily suitable to run in constrained environments. Applications that run on limited-battery, with low computational power, or area constraints, therefore requires the new designs as well as improved implementations of cryptographic primitives, hence emerges the field lightweight cryptography. In this thesis, we contribute to this effort in few separate directions, in particular regarding block ciphers and block-cipher-based authentication scheme implementations as application-specific integrated circuits (ASIC). First, we look at optimizations that can be achieved at higher level. In particular, we show that the complete AES family (with varying key sizes 128, 192 and 256) can be realized as combined lightweight circuit, in a manner that shares the storage elements in order to save up silicon area. Secondly, we contribute in the evaluation of a new design paradigm of fork cipher. We look at how much lightweight efficiency can be gained with this new AEAD design approach, by implementing ForkAES both in round-based and byte-serial implementations. Our comparison with respect to silicon area and energy consumption provides useful insights into AEAD design process. Lastly, in the large portion of this thesis, we look at the permutation layer of block ciphers from the perspective of serial-circuits. Based on the permutation theory, we establish a method to divide the permutation layers of AES, SKINNY, GIFT and PRESENT into simpler swap operations. Given that these swap operations are cheap in ASIC, we further provide architectural optimization techniques for the implementation of these block ciphers, and we provide the smallest 1-bit implementations of them.

EPFL2021

More Results on Shortest Linear Programs

Subhadeep Banik

At the FSE conference of ToSC 2018, Kranz et al. presented their results on shortest linear programs for the linear layers of several well known block ciphers in literature. Shortest linear programs are essentially the minimum number of 2-input xor gates required to completely describe a linear system of equations. In the above paper the authors showed that the commonly used metrics like d-xor/s-xor count that are used to judge the ``lightweightedness'' do not represent the minimum number of xor gates required to describe a given MDS matrix. In fact they used heuristic based algorithms of Boyar/Peralta and Paar to find implementations of MDS matrices with even fewer xor gates than was previously known. They proved that the AES mixcolumn matrix can be implemented with as little as 97 xor gates. In this paper we show that the values reported in the above paper are not optimal. By suitably including random bits in the instances of the above algorithms we can achieve implementations of almost all matrices with lesser number of gates than were reported in the above paper. As a result we report an implementation of the AES mixcolumn matrix that uses only 95 xor gates. In the second part of the paper, we observe that most standard cell libraries contain both 2 and 3-input xor gates, with the silicon area of the 3-input xor gate being smaller than the sum of the areas of two 2-input xor gates. Hence when linear circuits are synthesized by logic compilers (with specific instructions to optimize for area), most of them would return a solution circuit containing both 2 and 3-input xor gates. Thus from a practical point of view, reducing circuit size in presence of these gates is no longer equivalent to solving the shortest linear program. In this paper we show that by adopting a graph based heuristic it is possible to convert a circuit constructed with 2-input xor gates to another functionally equivalent circuit that utilizes both 2 and 3-input xor gates and occupies less hardware area. As a result we obtain more lightweight implementations of all the matrices listed in the ToSC paper.

2019