Research On Quantum Attacks On Feistel-2~* And OTR Structure

Introducing quantum algorithms into the field of cryptanalysis has become a research hotspot in recent years.Quantum cryptographic analysis is an indispensable and important component in the design and evaluation of cryptographic protocols,which provides a reference for the analysis and design of cryptography in the post quantum world.Currently,the urgent issues to be solved in the field of quantum cryptography analysis are reducing attack complexity and improving the probability of forgery success.Based on this,in order to reduce attack complexity and improve the probability of forgery success,an in-depth exploration of the Feistel-2 * structure of block cipher,the OTR structure of authentication encryption algorithm,and its variant Pr(?)st-OTR Even-Mansour structure has been conducted in this paper.The main works are as follows.(1)A quantum all subkeys recovery attack on a six-round Feistel-2* structure based on multi equations quantum claw finding algorithm is proposed in this paper,which can recover all subkeys of six-round Feistel-2* structure using only three plaintext and ciphertext pairs,and greatly reduce the original data complexity.Because the existing claw search algorithm is a single equation claw finding algorithm,it cannot solve the multi equations claw finding problem.Therefore,a multi equations quantum claw finding algorithm is proposed firstly to solve the multi equation claw search problem.In addition,the Grover algorithm is also used to accelerate the recovery of remaining subkeys.Compared to other attacks,our attack data complexity has decreased from(2)nO to O)1(,while the time complexity and memory complexity have also significantly decreased.(2)A quantum forgery attack method against OTR structures based on Simon algorithm is proposed in this paper,which improves the success probability of the original attack and loosens the forgery attack scenario.The attacker uses Simon algorithm to find the period of the tag generation function in the OTR,and then can successfully forge a new ciphertext C’’(C’≠C)C for the intercepted tag T.Compared with the state-of-the-art classical forgery attacks,our attack only need some ciphertexts or plaintexts,query complexity is n O)(,and its success probability is very close to 100%.(3)A generic forgery attack against Pr(?)st-OTR Even-Mansour structure based on Simon algorithm is proposed in this paper,which first uses the Simon algorithm to obtain the secret parameter L,and then use the secret parameter L to find keys1 k and2k,so that an attacker can forge the changed message.Only a few blocks of plaintext are needed to help obtain the key to forge any message.If an attacker is allowed to change a single block within it,it is easy to generate the correct token for any given message.Performance analysis shows that our attack query complexity is n O)(,and its success probability is very close to 100%.