PaperlayerView exact revision on arXiv

Source-linked AI summary

Breaking Symmetric Cryptosystems using Quantum Period Finding

Marc Kaplan, Gaëtan Leurent, Anthony Leverrier, María Naya-Plasencia

arXiv:1602.05973v3quant-phcs.CR

TL;DR

The paper asks whether symmetric cryptosystems remain secure against quantum adversaries with superposition access, a setting where real-world quantum security is less understood. It applies Simon’s algorithm and its collision-tolerant variants to cryptanalytic constructions, finding exponential speed-ups and complete breaks of many authentication and authenticated-encryption modes. The results show that several symmetric primitives considered secure classically are vulnerable in the quantum setting.

  • Problem

    Real-world security of symmetric primitives against quantum adversaries is much less understood than their classical security, despite generic analyses suggesting that doubling key lengths may suffice.

  • Method

    The paper applies Simon’s algorithm to quantum-queryable functions derived from encryption oracles, extending it to tolerate additional collisions and using recovered periods in cryptanalytic attacks.

  • Results

    The authors find exponential quantum speed-ups for symmetric cryptanalysis and completely break many widely used authentication and authenticated-encryption modes.

  • Takeaways & Limitations

    For the analyzed symmetric primitives, doubling the key length is not sufficient to restore quantum security.

  • Takeaways & Limitations

    The attacks have no obvious application to CCM because all its computations depend on the nonce, whose non-repetition is unclear in the quantum setting.

Abstract

from arXiv · show

Due to Shor's algorithm, quantum computers are a severe threat for public key cryptography. This motivated the cryptographic community to search for quantum-safe solutions. On the other hand, the impact of quantum computing on secret key cryptography is much less understood. In this paper, we consider attacks where an adversary can query an oracle implementing a cryptographic primitive in a quantum superposition of different states. This model gives a lot of power to the adversary, but recent results show that it is nonetheless possible to build secure cryptosystems in it. We study applications of a quantum procedure called Simon's algorithm (the simplest quantum period finding algorithm) in order to attack symmetric cryptosystems in this model. Following previous works in this direction, we show that several classical attacks based on finding collisions can be dramatically sped up using Simon's algorithm: finding a collision requires $Ω(2^{n/2})$ queries in the classical setting, but when collisions happen with some hidden periodicity, they can be found with only $O(n)$ queries in the quantum model. We obtain attacks with very strong implications. First, we show that the most widely used modes of operation for authentication and authenticated encryption e.g. CBC-MAC, PMAC, GMAC, GCM, and OCB) are completely broken in this security model. Our attacks are also applicable to many CAESAR candidates: CLOC, AEZ, COPA, OTR, POET, OMD, and Minalpher. This is quite surprising compared to the situation with encryption modes: Anand et al. show that standard modes are secure with a quantum-secure PRF. Second, we show that Simon's algorithm can also be applied to slide attacks, leading to an exponential speed-up of a classical symmetric cryptanalysis technique in the quantum model.

1 Introduction

The paper examines symmetric cryptography against quantum adversaries with superposition access to cryptographic oracles, where real-world security is less established than classical security. It applies Simon’s algorithm to show powerful attacks against authentication, authenticated-encryption modes, and slide cryptanalysis.

  • 1 Introduction: Quantum attacks on symmetric primitives remain less understood than attacks on public-key systems, despite Grover’s quadratic generic speed-up.The passages distinguish ideal generic security from the limited knowledge of real-world quantum attacks.
  • Our results.: The authors extend Simon’s algorithm to functions with additional collisions and use it to analyze symmetric constructions.The extension supports settings where collisions are not restricted exclusively to a hidden period.
  • Our results.: The work gives an attack against LRW and quantizes slide attacks, extending Simon-based attacks beyond previously studied Feistel and Even-Mansour constructions.These constructions can be classically provably secure yet insecure against quantum adversaries.
  • Our results.: Authentication and authenticated-encryption modes including CBC-MAC, PMAC, GMAC, GCM, and OCB admit forgery attacks with complexity O(n).The attacks also apply to CAESAR candidates CLOC, AEZ, COPA, OTR, POET, OMD, and Minalpher.
  • Our results.: For the analyzed symmetric primitives, doubling the key length is insufficient to restore security against quantum adversaries.The authors therefore call for substantial quantum cryptanalysis of symmetric primitives.
  • 1 Introduction: The paper develops quantum cryptanalysis in a model where adversaries query cryptographic oracles in arbitrary superpositions.The oracle maps |x⟩|y⟩ to |x⟩|y ⊕ O_k(x)⟩, enabling superposition attacks.

2 Simon’s algorithm and attack strategy

The paper uses Simon’s algorithm to recover hidden periods from quantum-queryable functions derived from encryption oracles. It extends the method to tolerate unwanted collisions and defines a construction strategy linking recovered periods to cryptanalytic breaks.

  • Dealing with unwanted collisions: Theorem 1 shows that additional collisions do not significantly increase attack complexity when the function’s deviation from Simon’s promise is bounded away from one.Choosing c ≥ 3/(1 − p0) makes the error decrease exponentially with n.
  • Simon’s problem: Simon’s algorithm recovers a hidden string s from a function whose collisions occur exactly at differences 0 or s.Classical collision search costs Θ(2^n/2), whereas Simon’s algorithm uses O(n) quantum queries.
  • Simon’s algorithm: The algorithm repeatedly measures vectors orthogonal to s and recovers s by solving the resulting linear system.O(n) repetitions provide n − 1 independent orthogonal vectors with high probability.
  • Dealing with unwanted collisions: Without a bound on unwanted collisions, a vector orthogonal to all measured vectors still yields a high-probability collision relation under the theorem’s conditions.Theorem 2 states that the probability becomes exponentially close to one for c ≥ 3/(1 − p0).
  • Attack strategy: The attack strategy constructs a Simon function from the encryption oracle whose hidden period is sufficient to break the cryptographic scheme.Typically, the period is an internal-state difference s = E(α0) ⊕ E(α1), embedded into the function’s input.
  • Construction of Simon’s functions: The constructed functions use controlled classical transformations and permutations while avoiding control of the cryptographic oracle itself.The paper notes that extra registers can hinder periodicity and must be accounted for in a reversible implementation.

3 Previous works

Previous work applied Simon’s algorithm to quantum attacks on three-round Feistel and Even–Mansour constructions, recovering hidden periods or key differences. The paper extends these analyses to random functions and approximate Simon promises.

  • Prior Simon attacks: Simon’s algorithm previously broke the Even–Mansour construction and the three-round Feistel scheme with superposition queries.These attacks exploit hidden periodicity in functions derived from the constructions.
  • Three-round Feistel: A three-round Feistel scheme is built from three round functions R1, R2, and R3 using the standard Feistel recurrence.The construction maps input halves (xL, xR) to output halves (yL, yR).
  • Three-round Feistel: The Feistel attack defines f(b, x) from encryption queries at two distinct constants and obtains the period 1 ∥ R1(α0) ⊕ R1(α1).Simon’s algorithm recovers the round-function difference, distinguishing the Feistel scheme from a random permutation.
  • Three-round Feistel: The Feistel attack assumes superposition access that returns only the encryption’s left part, because complete outputs can entangle the input register with other registers.Simon’s algorithm requires the input register to be completely disentangled from the others.
  • Three-round Feistel: The Feistel analysis extends from permutation round functions to random functions despite additional collisions with random differences.The same hidden period remains, and the distinguisher is valid when unwanted collisions occur with sufficiently low probability.
  • Even–Mansour: For Even–Mansour, Simon’s algorithm recovers k1 from a periodic function, after which one additional classical query recovers k2.Either Simon’s algorithm succeeds, or an alternative classical distinguishing attack exists; the latter occurs with negligible probability for a random permutation.

4 Application to the LRW construction

The paper applies Simon’s algorithm to the LRW tweakable-block-cipher construction, recovering hidden hash-related periods with quantum oracle access. This distinguishes LRW from an ideal tweakable block cipher and affects several widely used instantiations and modes.

  • LRW construction: The LRW construction turns a block cipher into a tweakable block cipher using an almost-universal hash function.Tweakable block ciphers support modes for encryption, authentication, and authenticated encryption.
  • Quantum attack: Simon’s algorithm returns h(t0) ⊕ h(t1) when the LRW-derived function has hidden period s = h(t0) ⊕ h(t1).The analysis assumes the block cipher behaves as a pseudorandom permutation, which bounds unwanted collisions with overwhelming probability.
  • Caveat: A block cipher exhibiting the required higher-order differential with probability 1/2 would indicate a structural weakness, although the differential may depend on the key.Some later attacks can be mounted without assumptions on the block cipher.
  • Quantum attack: O(n) quantum queries distinguish LRW from an ideal tweakable block cipher by exploiting a nonzero period orthogonal to Simon measurements.For a random function, such a common nonzero orthogonal value would not exist.
  • Instantiations: For common finite-field instantiations, recovering h(t0) ⊕ h(t1) recovers the secret offset L.The relevant forms include h(t) = γ(t) · L and h(t) = 2^t · L.
  • Implications: The attack applies to LRW-inspired constructions and CAESAR candidates including AEZ, COPA, OCB, OTR, Minalpher, OMD, and POET.The paper states that variants of the attack can be applied to each listed mode.

5 Application to block cipher modes of operations

The paper reduces forgery attacks on block-cipher MACs and authenticated-encryption modes to Simon’s problem under quantum superposition queries. It obtains O(n)-query attacks against standardized modes and several CAESAR candidates that have classical birthday-bound security.

  • Scope: The attacks target CBC-MAC, PMAC, GMAC, GCM, OCB, and several CAESAR candidates using superposition queries.The listed standardized modes are proven secure up to 2^(n/2) queries in the classical setting.
  • Quantum model: O(n) quantum queries suffice for forgery attacks after reducing each mode-specific construction to Simon’s problem.The security model gives the adversary an oracle that evaluates MACs on superpositions of messages.
  • Scope: The analysis assumes full-block, n-bit, non-truncated MAC inputs, although most attacks can be adapted to arbitrary inputs or truncated MACs.This is a scope condition stated in the paper’s preliminaries.
  • CBC-MAC: CBC-MAC yields the hidden difference E_k(α0) ⊕ E_k(α1), enabling a tag-valid message transformation.A tag for α0 ∥ m1 also validates α1 ∥ m1 ⊕ E_k(α0) ⊕ E_k(α1).
  • CBC-MAC: CBC-MAC is existentially forgeable because 2(q′ + 1) valid messages can be produced after 2q′ + 1 oracle queries.Here q′ = O(n) is the number of quantum queries used to recover the block-cipher difference.
  • PMAC: For two-block PMAC, the CBC-MAC attack recovers E_k(α0) ⊕ E_k(α1) and supports analogous tag forgeries.A second PMAC attack recovers offset differences, then derives L and all offsets Δ_i.
  • PMAC: The PMAC offset attack can recover L from Δ0 ⊕ Δ1 and then compute all Δ_i for arbitrary-message forgeries.The offsets satisfy Δ_i = γ(i) · L with L = E_k(0).

5.2 Randomized MAC: GMAC

The paper attacks GMAC by adapting the CBC-MAC Simon-function construction to its polynomial-hashing structure. Because nonce repetition is unclear for superposition queries, the analysis uses a weaker random-nonce security model and still obtains existential forgery attacks.

  • Construction: GMAC is a randomized Carter-Wegman MAC built from polynomial evaluation in a Galois field and a non-repeating nonce.GMAC is the underlying MAC of the standardized GCM construction.
  • Simon attack: GMAC’s two-block structure permits a Simon function whose hidden period is (α0 ⊕ α1) · H.The function uses fixed blocks α0 and α1 and evaluates GMAC under a nonce N.
  • Role of the nonce: The quantum model lacks a clear definition of a non-repeating nonce when the nonce itself may be queried in superposition.The paper therefore lets the oracle choose a random nonce and returns it with the GMAC tag.
  • Simon attack: O(n) Simon steps recover (α0 ⊕ α1) · H even when each step uses a different random nonce, allowing recovery of H.Each step returns a vector orthogonal to the hidden period for its randomly chosen nonce.
  • Forgery: A tag for N, m1 ∥ m2 also validates m1 ⊕ 1 ∥ m2 ⊕ H under the same nonce N.Repeating this transformation yields an existential forgery attack.

5.3 Classical Authenticated Encryption Schemes: GCM and OCB

The attacks exploit nonce-independent authentication components in GCM and OCB, using Simon’s algorithm to recover hidden differences or keys and generate forgeries. CCM is an exception because all computations depend on the nonce.

  • GCM and OCB: GCM and OCB authenticate associated data independently of the nonce, enabling a generic Simon-based attack with random nonces.The attack recovers a secret difference Δ; when carefully constructed, that difference suffices for forgery.
  • Limitation: CCM is a notable exception because all computations depend on the nonce, leaving no obvious way to apply these attacks.
  • GCM: GCM becomes GMAC when the message is empty, allowing recovery of the hash key H and an immediate forgery attack.
  • OCB: In OCB’s associated-data attack, Simon’s algorithm recovers Δ0 ⊕ Δ1, after which two messages with valid tags can be generated from one classical query.
  • OCB: Repeating the OCB procedure yields an existential forgery attack.
  • OCB: OCB’s encryption component can also be attacked by recovering secret offsets and swapping the first and second block-cipher inputs.The resulting ciphertext and tag form a valid authenticated encryption under the same nonce.

5.4 New Authenticated Encryption Schemes: CAESAR Candidates

The paper extends its Simon-based forgery attacks to several CAESAR authenticated-encryption candidates whose authentication of associated data is nonce-independent. Minalpher and OMD require adaptations because their internal primitives differ from PMAC.

  • The attacks extend to several CAESAR candidates, including CLOC, AEZ, COPA, OTR, POET, OMD, and Minalpher.
  • CLOC: CLOC inherits the CBC-MAC attack because its associated data is processed independently of the nonce.The related mode SILC is excluded because it processes the nonce before the data in CBC-MAC.
  • AEZ, COPA, OTR, and POET: AEZ, COPA, OTR, and POET inherit the PMAC attack because their associated-data authentication does not use the nonce.The attacks are nonce-respecting even though some candidates also claim security under nonce misuse.
  • OMD and Minalpher: OMD and Minalpher use PMAC-like associated-data authentication, so the attack applies despite their different internal primitives.
  • Minalpher: For Minalpher, the recovered value s = P(α0 ⊕ Δ1) ⊕ P(α1 ⊕ Δ1) is nonce-independent, enabling Simon’s algorithm and forgery generation.

6 Simon’s algorithm applied to slide attacks

Simon’s algorithm turns slide attacks into an exponentially faster quantum cryptanalytic technique by recovering the secret key from a hidden periodicity. The attack complexity drops from O(2^n/2) to O(n).

  • Result: O(2^n/2) to O(n): Simon’s algorithm reduces the complexity of slide attacks exponentially.The paper presents this as the first known exponential quantum speed-up of a classical symmetric cryptanalytic technique.
  • Classical slide attacks: Classically, slide attacks collect 2^n/2 encryptions to find a slid pair satisfying R(P0) = P1 and consequently R(C0) = C1.
  • Classical slide attacks: For TREYFER, the classical slide attack uses data complexity 2^32 and time complexity 2^44, compared with exhaustive key search at 2^64.
  • Quantum slide attack: The constructed function satisfies Simon’s promise with secret period s = 1 ∥ k, allowing recovery of k when relevant compositions behave as random permutations.
  • Quantum slide attack: The security argument fails only if Ek ◦ P or P ◦ Ek has a differential with probability 1/2; for random permutations, such differentials occur with negligible probability.

7 Conclusion

The paper concludes that symmetric cryptography is not ready for the post-quantum world: quantum attacks obtain exponential speed-ups, breaking some systems considered safe classically. It also identifies many authenticated-encryption modes as completely broken in this model.

  • Exponential speed-ups on attacks make some cryptosystems believed safe classically vulnerable to quantum adversaries.
  • The slide-attack result is presented as the first known exponential quantum speed-up of a classical attack.
  • Many authenticated-encryption modes considered solid and secure classically become completely broken in the post-quantum world.The paper suggests that further constructions might be broken using the same ideas.

A Proof of Theorem 1

The proof establishes Simon’s algorithm’s success by showing that its output vectors are orthogonal to the hidden period and collectively span the orthogonal subspace. It then bounds failure using independence, a union bound, and a probability estimate for individual outputs.

  • Single-output probability: The lemma’s nonzero-t case is proved by evaluating g at selected points, using normalization, and decomposing g into two counted terms.The counting distinguishes x = 0, x = t, and all other x values.
  • Proof strategy: Each Simon subroutine call returns a vector orthogonal to the hidden period s.This follows from the periodicity condition f(x) = f(x ⊕ s).
  • Proof strategy: cn output vectors recover s unambiguously when they span the (n − 1)-dimensional space orthogonal to s.The proof therefore analyzes the probability that the sampled vectors fail to span that space.
  • Failure analysis: The failure probability is bounded by considering whether a nonzero vector other than s is orthogonal to every sampled output.The displayed bound uses a union-bound argument over candidate vectors.
  • Failure analysis: The proof uses independence of the cn subroutine outputs to bound the probability that all sampled vectors are orthogonal to a fixed t.It suffices to show that a single output satisfies Pr[u · t = 0] bounded away from 1 for every t outside {0, s}.
  • Single-output probability: Simon’s final premeasurement state is decomposed to calculate the probability that its output u satisfies u · t = 0.The calculation invokes a lemma concerning a Fourier-type sum over vectors orthogonal to t and the identity δ(x, 0).

B Proof of Theorem 2

The proof of Theorem 2 fixes a value t and expresses the probability that all Simon-generated vectors are orthogonal to t. It then uses this expression to bound the probability of returning a value with low collision probability.

  • Proof setup: For a fixed t, the proof defines p_t as the probability that f(x ⊕ t) = f(x).It then analyzes the probability that every one of the cn vectors returned by Simon’s algorithm is orthogonal to t.
  • Proof setup: The resulting expression bounds the probability that Simon’s algorithm returns a value t with p_t < p_0.The supplied passage introduces this bound but does not include its completed quantitative form.
Loading 1602.05973v3…