Multiple Linear Cryptanalysis of Reduced-Round SMS4 Block Cipher

SMS4 is a 32-round block cipher with 128-bit block size and key size. It has been widely implemented in Chinese WLAN industry. In this paper, we present a modified branch-and-bound algorithm which can be used for searching multiple linear characteristics for SMS4-like block ciphers. Furthermore, we find a series of 5-round iterative linear characteristics of SMS4. Then based on these 5-round iterative linear characteristics, a list of 18-round linear characteristics of SMS4 can be constructed. According to the framework of Biryukov et al from Crypto 2004, a key recovery attack can be mounted on 22-round SMS4 by utilizing the above 18-round linear characteristics. The data complexity of our attack is 2112 known plaintexts. Compared with the previously best cryptanalytic results on 22-round SMS4 (that is, the previously best cryptanalytic results on SMS4), our result has much lower data complexity as well as comparable time complexity and memory complexity.