A quantum distinguisher for 7/8-round SMS4 block cipher

Constructions of quantum distinguishers (extended to key recovery attacks) for generalized Feistel networks have been recently proposed in several works, where the main focus has been on Type 1 and 2 schemes. In this work, we derive a quantum distinguisher for 7 and 8 rounds of the SMS4 block cipher, which belongs to the class of unbalanced (contracting) generalized Feistel schemes.

In the former case, by applying Simon’s quantum algorithm we construct a quantum distinguisher that runs in (quantum) polynomial time O(n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {O}(n)$$\end{document} (n is the branch size), while later we need to combine Simon’s and Grover’s algorithms in context of the amplitude amplification technique.

We show that for the 8-round SMS4 cipher a quantum distinguisher can be constructed in both Q1 and Q2 attack models. This is achieved by applying the method of asymmetric search of a period, introduced by Bonnetain et al. (Advances in cryptology ASIACRYPT 2019, LNCS, 2019), where online and offline queries to the encryption oracle are separated.

In this context, we answer the open problem posed by Dong et al. (Sci China Inf Sci 62:22501, 2019), which has been left open for construction of quantum distinguishers for ≥7\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ge 7$$\end{document} rounds.

Moreover, we show that for the specific instance when the quantum oracle for 8 rounds of SMS4 cipher is available, one can extract the master secret key with the same complexity and number of qubits required for the 8-round distinguisher.