Multiple Linear Cryptanalysis of Reduced-Round SMS4 Block Cipher

Zhiqiang Liu; Dawu Gu; Jing Zhang

Paper 2009/256

Multiple Linear Cryptanalysis of Reduced-Round SMS4 Block Cipher

Zhiqiang Liu, 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 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.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Published elsewhere. Unknown where it was published
Keywords: Block cipher SMS4 Linear characteristic Multiple linear cryptanalysis Branch-and-bound
Contact author(s): ilu_zq @ sjtu edu cn
History: 2009-06-01: received
Short URL: https://ia.cr/2009/256
License: CC BY

BibTeX

@misc{cryptoeprint:2009/256,
      author = {Zhiqiang Liu and Dawu Gu and Jing Zhang},
      title = {Multiple Linear Cryptanalysis of Reduced-Round {SMS4} Block Cipher},
      howpublished = {Cryptology {ePrint} Archive, Paper 2009/256},
      year = {2009},
      url = {https://eprint.iacr.org/2009/256}
}