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.

In this paper, we revisit related-key security of TWINE block cipher with 80-bit and 128-bit keys. Using an MILP-aided automatic search algorithm, we point out the previous evaluation of TWINE with a 80-bit key is wrong, and give a corrected evaluation result. Besides, we show a first security evaluation of TWINE with a 128-bit key in the related-key setting, which was infeasible due to the high computation cost in the original proposal.

HIGHT is a 64-bit block lightweight cipher, which adopts the ARX-based generalized Feistel network, and it accepts a 128-bit key. It is a standard encryption algorithm in South Korea and also is internationally standardized by ISO/IEC 18033-3. Therefore, many third-party cryptanalyses have been proposed against HIGHT. Impossible differential and integral attacks are applied to reduced-round HIGHT, and especially, the impossible differential attack causes the 27-round attack, which is the current best attack under the single-key setting. In this paper, we propose some improved integral attacks against HIGHT. We first apply the division property to HIGHT and find new 19-round integral characteristics, which are improved by two rounds compared with the previous best ones. We append 9-round key recovery to these characteristics and it enables us to attack 28-round HIGHT. Its time complexity is 2127.02 where 263 chosen plaintexts and 2117 memory are required. Moreover, we can attack 29-round HIGHT if the full codebook is used, where its time and memory complexities are 2126.07 and 2118, respectively. It improves by two rounds compared with the previous best attack.

Tweakable block cipher (TBC) is an extension of conventional block cipher. We study how to build a TBC based on generalized Feistel structure (GFS), a classical block cipher construction. While known dedicated TBC proposals are based on substitution-permutation network (SPN), GFS has not been used for building TBC. In particular, we take 64-bit GFS block cipher TWINE and try to make it tweakable with a minimum change. To find a best one from a large number of candidates, we performed a comprehensive search with a help of mixed integer linear programming (MILP) solver. As a result, our proposal TWINE is quite efficient, has the same number of rounds as TWINE with extremely simple tweak schedule.