Cryptology ePrint Archive: Report 2009/256

Multiple Linear Cryptanalysis of Reduced-Round SMS4 Block Cipher

Zhiqiang Liu and Dawu Gu and Jing Zhang

Abstract: SMS4 is a 32-round unbalanced Feistel block cipher with its block size and key size being 128 bits. As a fundamental block cipher used in the WAPI standard, the Chinese national standard for WLAN, 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 unbalanced Feistel block ciphers. Furthermore, we find a series of 5-round iterative linear characteristics of SMS4 when applying the modified algorithm in SMS4. Then based on each 5-round iterative linear characteristic mentioned above, an 18-round linear characteristic of SMS4 can be constructed, thus leading to a list of 18-round linear characteristics of SMS4. According to the framework of Biryukov $et\ al.$ from Crpto 2004, a key recovery attack can be mounted on 22-round SMS4 by utilizing the above multiple linear characteristics. As a matter of fact, our result has much lower data complexity than the previously best known cryptanalytic result on 22-round SMS4, which is also the previously best known result on SMS4.

Category / Keywords: secret-key cryptography / Block cipher, SMS4, Linear characteristic, Multiple linear cryptanalysis, Branch-and-bound

Date: received 1 Jun 2009

Contact author: ilu_zq at sjtu edu cn

Available formats: PDF | BibTeX Citation

Version: 20090601:153529 (All versions of this report)

Discussion forum: Show discussion | Start new discussion