Classical forgery attacks against Offset Two-round (OTR) structures require some harsh conditions, such as some plaintext and ciphertext pairs need to be known, and the success probability is not too high. To solve these problems, a quantum forgery attack on OTR structure using Simon’s algorithm is proposed. The attacker intercepts the ciphertext-tag pair [Formula: see text] between the sender and receiver, while Simon’s algorithm is used to find the period of the tag generation function in OTR, then we can successfully forge new ciphertext [Formula: see text] ([Formula: see text]) for intercepted tag [Formula: see text]. For a variant of OTR structure (Prøst-OTR-Even-Mansour structure), a universal forgery attack, in which it is easy to generate the correct tag of any given message if the attacker is allowed to change a single block in it, is proposed. It first obtains the secret parameter [Formula: see text] using Simon’s algorithm, then the secret parameter [Formula: see text] is used to find the keys [Formula: see text] and [Formula: see text], so that an attacker can forge the changed messages. It only needs several plaintext blocks to help obtain the keys to forge any messages. Performance analysis shows that the query complexity of our attack is [Formula: see text], and its success probability is very close to 1.
Classical forgery attacks against Offset Two-round (OTR) structures require some harsh conditions, such as some plaintext and ciphertext pairs need to be known, and the success probability is not too high. To solve these problems, a quantum forgery attack on OTR structure using Simon’s algorithm is proposed. The attacker intercepts the ciphertext-tag pair [Formula: see text] between the sender and receiver, while Simon’s algorithm is used to find the period of the tag generation function in OTR, then we can successfully forge new ciphertext [Formula: see text] ([Formula: see text]) for intercepted tag [Formula: see text]. For a variant of OTR structure (Prøst-OTR-Even-Mansour structure), a universal forgery attack, in which it is easy to generate the correct tag of any given message if the attacker is allowed to change a single block in it, is proposed. It first obtains the secret parameter [Formula: see text] using Simon’s algorithm, then the secret parameter [Formula: see text] is used to find the keys [Formula: see text] and [Formula: see text], so that an attacker can forge the changed messages. It only needs several plaintext blocks to help obtain the keys to forge any messages. Performance analysis shows that the query complexity of our attack is [Formula: see text], and its success probability is very close to 1.
Abstract Due to its innovative and performance advantages, Prøst‐COPA and Prøst‐OTR have attracted widespread attention. For the Prøst‐COPA without associated data and with associated data, the corresponding quantum key recovery attacks are proposed using Simon's algorithm, respectively. In the first scenario, the messages are used to calculate the Message Authentication Code (MAC) and construct a period function to recover the secret parameter . Then, utilizing ciphertext, a periodic function is constructed with a periodic value equal to the key value. MAC is calculated from messages and the associated data in the second scenario. Considering the impact of the associated data on the periodicity of the function, the messages are treated as a constant and further construct two periodic functions to recover the secret parameter and the key. For Prøst‐OTR, by constructing two periodic functions using two tags with different numbers of message blocks, the secret parameter can be recovered, and then the key can be recovered using Simon's algorithm. Compared to the classical attacks, the quantum‐based methods only require quantum queries (where is the message block size), resulting in an exponential speed acceleration and the success probability of the method is close to 1. These methods also show a lower query complexity than the state‐of‐the‐art quantum methods.
In recent years, some general cryptographic technologies have been widely used in network platforms related to the national economy and people’s livelihood, effectively curbing network security risks and maintaining the orderly operation and normal order of society. However, due to the fast development and considerable benefits of quantum computing, the classical cryptosystem faces serious security threats, so it is crucial to analyze and assess the anti-quantum computing ability of cryptographic algorithms under the quantum security model, to enhance or perfect the design defects of related algorithms. However, the current design and research of anti-quantum cryptography primarily focus on the cryptographic structure or working mode under the quantum security model, and there is a lack of quantum security analysis on instantiated cryptographic algorithms. This paper investigates the security of AES-OTR, one of the third-round algorithms in the CAESAR competition, under the Q2 model. The periodic functions of the associated data were constructed by forging the associated data according to the parallel and serial structure characteristics of the AES-OTR algorithm in processing the associated data, and the periodic functions of the associated data were constructed multiple times based on the Simon quantum algorithm. By using the collision pair, two collision forgery attacks on the AES-OTR algorithm can be successfully implemented, and the period s is obtained by solving with a probability close to 1. The attacks in this paper caused a significant threat to the security of the AES-OTR algorithm.
We present new connections between quantum information and the field of classical cryptography. In particular, we provide examples where Simon’s algorithm can be used to show insecurity of commonly used cryptographic symmetric-key primitives. Specifically, these examples consist of a quantum distinguisher for the 3-round Feistel network and a forgery attack on CBC-MAC which forges a tag for a chosen-prefix message querying only other messages (of the same length). We assume that an adversary has quantum-oracle access to the respective classical primitives. Similar results have been achieved recently in independent work by Kaplan et al. [KLLNP16]. Our findings shed new light on the post-quantum security of cryptographic schemes and underline that classical security proofs of cryptographic constructions need to be revisited in light of quantum attackers.
Abstract QSimon algorithm (a full quantum version of Simon's algorithm) is used to find periods in commitment functions and does not require classical calculations. However, QSimon algorithm circuit is incomplete, and the implementation of an essential component (solving boolean linear equations) has high resource consumption. This work further studies QSimon algorithm and applies QSimon algorithm to attack the offset two‐round (OTR) scheme. QSimon algorithm is established by quantum boolean linear equations solving algorithm and general quantum truncation technique, which can obtain the period of any truncated function with overwhelming probability. The confidentiality and integrity of the OTR scheme are compromised by employing QSimon algorithm. The attacks ensure a high success rate and realize exponential speedup compared with classical versions.
Simon's algorithm is one of the most widely used quantum algorithms in cryptanalysis of symmetric ciphers, which has a significant advantage over its classical counterparts. However, if the number of unwanted collisions of the target function is large or if the number of adversary's quantum superposition queries is limited, the Simon's algorithm is not able to unambiguously compute the actual period. This problem can lead to the failure of period-finding-based quantum attacks. In this paper we first show that using Simon's algorithm, one can find proper partial periods of Boolean vector functions, such that the corresponding probabilities, independent of the target function, are directly related to the number of quantum queries. Next, we examine how to use the partial period instead of actual one in quantum period-finding-based attacks. As a result, the advantage of our proposed relaxing method is twofold: It improves success probabilities of quantum period-finding-based distinguishers, provided that the adversary is limited to a specified small number of queries, in contrast to the previous ones. On the other hand, our proposed method generalizes the previous forgery attacks on modes of operation for message authentication codes.
With the development of quantum technology, quantum computing has an increasingly significant impact on cryptanalysis. Several quantum algorithms, such as Simon’s algorithm, Grover’s algorithm, the Bernstein–Vazirani algorithm, Shor’s algorithm, and the Grover-meets-Simon algorithm, have been proposed successively. However, almost all cryptanalysis is based on the quantum chosen-plaintext attack (qCPA) model. This paper focuses on a powerful cryptanalytic model, quantum related-key attack (qRKA), and proposes a strategy of qRKAs against symmetric ciphers using Simon’s algorithm. We construct a periodic function to efficiently recover the secret key of symmetric ciphers if the attacked symmetric ciphers satisfy Simon’s promise, and present the complexity analysis on specific symmetric ciphers. Then, we apply qRKA to the Even–Mansour cipher and SoEM construction, recover their secret keys, and show their complexity comparison in the distinct attack models. This work is of great significance for the qRKA cryptanalysis of existing provably secure cryptographic schemes and the design of future quantum secure cryptographic schemes.