Tweakable SM4: How to tweak SM4 into tweakable block ciphers?

SM4 is China's commercial block cipher standard and an ISO/IEC international standard. While SM4 withstood a great deal of analysis, its non-tweakable structure makes it inflexible. In this paper, we study three different methods to turn SM4 into a tweakable block cipher. Based on the Tweak-aNd-Tweak (TNT) introduced by Bao et al. at EUROCRYPT 2020, we propose the first scheme, called TNT-SM4, which can be treated as an instantiation of TNT. For comparative analysis, the 128 and 32 bits tweaks are both adopted, which is denoted as TNT-SM4-128 and TNT-SM4-32, respectively. By taking full advantage of the structural characteristics of SM4, we also propose the second method, which studies how to tweak SM4 into a tweakable block cipher in a direct way. With the design goal of reducing the design, security evaluation, and implementation costs, we use SM4 as is and attach a lightweight linear tweak schedule to it. The biggest challenge is to find the best insertion location for tweaks in both aspects of security and efficiency. We extensively utilize mixed integer linear programming (MILP) to perform a comprehensive search. The third method adopts the same tweak schedule as the key schedule of SM4, which is equivalent to one more key schedule for SM4. We analyze the security of the three schemes, focusing on related-key and related-tweak attacks, and provide a comparative analysis of the three schemes. The results show that our schemes are secure, and a better scheme that makes SM4 more flexible is obtained from the comparison of the three schemes.