Simon Algorithm Symmetric Cryptanalysis

Short answer: Simon's algorithm is the simplest quantum period-finding algorithm, and researchers have used it to attack symmetric cryptography in a strong model where the attacker can query a cipher in quantum superposition. Papers report that several authentication and authenticated-encryption modes, and some Feistel constructions, fall in that model. The model is demanding and these are theoretical attacks, so they do not show that everyday encryption is broken.

The attack model

A 2016 paper by Leurent and co-authors, hosted on a researcher's site, says that because of Shor's algorithm quantum computers are a severe threat to public key cryptography, while the impact on secret key cryptography is much less understood. It considers attacks where an adversary can query an oracle implementing a cryptographic primitive in a quantum superposition of different states. The authors say this model gives the adversary a lot of power, though recent results show it is still possible to build secure cryptosystems in it.

What Simon's algorithm does

The paper describes Simon's algorithm as the simplest quantum period-finding algorithm. It says that finding a collision classically takes a number of queries exponential in the block size n, but when collisions happen with some hidden periodicity, they can be found with only O(n) queries in the quantum model. That is the speedup behind the attacks below.

Results on authentication modes

The 2016 paper reports that the most widely used modes of operation for authentication and authenticated encryption, naming CBC-MAC, PMAC, GMAC, GCM and OCB, are completely broken in this security model. It says the attacks also apply to many CAESAR candidates, naming CLOC, AEZ, COPA, OTR, POET, OMD and Minalpher. It calls this surprising compared to encryption modes, for which earlier work shows standard modes are secure with a quantum-secure pseudorandom function. It also shows that Simon's algorithm can be applied to slide attacks, giving an exponential speedup of a classical symmetric cryptanalysis technique in the quantum model.

Feistel constructions

A 2017 ePrint paper says that at Asiacrypt 2017 Leander and May combined Grover's and Simon's algorithms to break FX-based block ciphers. It studies Feistel constructions with the same two algorithms to produce new quantum key-recovery attacks on different numbers of rounds, requiring 2^(nr/4 - 3n/4) quantum queries to break an r-round Feistel construction. It reports a time complexity lower than quantum brute-force search by a factor of 2^(0.75n), and lower than the best classical attacks, from Dinur and co-authors in 2015, by a factor of 2^(0.5n) without extra memory cost. The paper notes that an earlier quantum distinguisher attack by Kuwakado and Morii could distinguish a 3-round Feistel cipher from a random permutation in polynomial time.

Automating the search

A 2022 ePrint paper says it automates the search for new attacks with Simon's algorithm and finds the first efficient key-recovery attacks against constructions such as 5-round MISTY L-FK and 5-round Feistel-FK. It also studies generalizations using non-standard Hadamard matrices, and concludes that none of them extends the toolkit beyond period finding, so breaking symmetric primitives that way would need fundamentally new attacks.

What this does not tell you

All these attacks assume the adversary can send quantum superposition queries to the cipher, which is a stronger assumption than in most real deployments. The papers do not say that symmetric ciphers in general are broken, and they do not report attacks run on a quantum computer.

FAQ

What is Simon's algorithm?

The simplest quantum period-finding algorithm, per the 2016 paper.

Which modes does it break?

In the superposition-query model, the paper reports CBC-MAC, PMAC, GMAC, GCM and OCB as broken.

Does this break AES in practice?

These papers do not claim that. They concern a specific attack model and specific constructions.

What about Feistel ciphers?

A 2017 paper gives key-recovery attacks combining Grover's and Simon's algorithms, with lower complexity than quantum brute force.

Can the technique be extended?

A 2022 paper concludes that non-standard Hadamard generalizations do not help and new attacks would be needed.