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 $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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
Block cipherSMS4Linear characteristicMultiple linear cryptanalysisBranch-and-bound
Contact author(s)
ilu_zq @ sjtu edu cn
History
2009-06-01: received
Short URL
https://ia.cr/2009/256
License
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2009/256}},
      url = {https://eprint.iacr.org/2009/256}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.