5
$\begingroup$

It is well-known that the Grover's algorithm reduces cryptographic strength of symmetric ciphers to a square-root - e.g. AES-256 becomes only 2128 strong.

However, these statements are always made about the raw block ciphers. How about GCM-AES256, CCM-AES256 and the like? The MAC tag in GCM is at most 128 bits. Does this mean GCM is not post-quantum secure, even if I use AES-256? What mode of operation that gives me authenticated encryption also gives me post-quantum security?

UPDATE

So I have found some interesting papers, namely:

GCM uses Carter-Wegman MAC, and per the second paper (p. 18): This MAC is not, in general, secure in the quantum setting. But the authors (Dan Boneh and Mark Zhandry) do give an example of a modified CW-MAC that is secure in quantum settings. So I guess that rules out the GCM mode, but what about CCM and others?

I am not sure whether the construction of MAC is the only issue in authenticated crypto, or the MAC tag space as well.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
6
$\begingroup$

This [Carter-Wegman] MAC is not, in general, secure in the quantum setting

This is true; however we need to ask "what is this setting, and is it a realistic one?"

This setting is one where the adversary can ask queries that are composed of a superposition of quantum states, and the oracle returns the superposition of the answers. In other words, the oracle (that is, the device with the MAC key that computes the MAC) must compute the answer without any decoherence in the quantum state, and the messages to and from the adversary must also not have any decoherence. As far as we know, any significant amount of computation without decoherence must be done using Quantum Error Correction (to adjust for the decoherence that just occurs naturally), this effectively means that the device with the MAC key must be a part of the quantum computer (but, for some reason, the attacker doesn't look inside the device and just extract the MAC key).

I would argue that this is not an attack model that we need to worry about, if we're just creating devices that exchange messages, and are worried about someone building a Quantum Computer.

We do need to worry about Grover's algorithm, which given a function $F(x)$ with an unknown $n$-bit input, find an $x$ where $F(x)$ is a specific value in $O(2^{n/2})$ time. However, the attacker can't take advantage to try to compute a 128-bit MAC tag; because, in addition to the tag that the attacker is searching for, the algorithm also has the key as the input, and the attacker doesn't know that. Grover's algorithm could be used to attack the key itself; we can prevent that from being a possibility by using a 256 bit key.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Thanks for your answer. Actually when writing my question, I was kinda worried whether the math that's behind some of these MACs can't be attacked by quantum computers, since many use primes in some way. GHASH in GCM already has some problems, so I thought that maybe these can lead to real problems with quantum computers. $\endgroup$
    – Paya
    Commented Jun 16, 2015 at 14:10
  • $\begingroup$ @Paya: no, symmetric crypto such as MACs generally don't need to worry about Shor's algorithm (and Grover's just does key-halving). As for GCM, well, unless AES is broken, the security proof still holds, even if the attacker has a QC. $\endgroup$
    – poncho
    Commented Jun 16, 2015 at 14:31
  • $\begingroup$ New paper claims to break GCM, CBC-MAC, OCB, etc. on quantum computer: arxiv.org/abs/1602.05973 $\endgroup$
    – dchest
    Commented Feb 22, 2016 at 12:58
  • 2
    $\begingroup$ @dchest: assuming, of course, this completely unrealistic attack model. $\endgroup$
    – poncho
    Commented Feb 24, 2016 at 18:18
  • $\begingroup$ Is this attack model somehow a sidestep? Do the authors agree this attack model is unrealistic? $\endgroup$
    – Melab
    Commented Jan 14, 2018 at 23:08
-3
$\begingroup$

Actually, a post-quantum security is truly achieveable in a cipher-combo only. So - take a look at AES-finalist-candidates, like Serpent, and use it too or just it, but in 512 bit keys. Here is the starting point for you : enter link description here

Improve this answer
$\endgroup$
2
  • 4
    $\begingroup$ -1 Combinations of ciphers have nothing to do with post-quantum crypto. AES-256 by itself is secure in a post-quantum world, because quantum computers only give a quadratic speedup and 128-bits is secure. OTOH, combining ciphers gives you nothing special, since the best attacks against symmetric crypto are general search algorithms that don't care how you're encrypting the message, just how long the key is. $\endgroup$
    – cpast
    Commented May 19, 2015 at 2:16
  • 1
    $\begingroup$ That's the point : 512 bit key will help for sure, but it's not H/W accelerated yet. That's why I've mentioned the cipher stack : it will not add the lengths of the keys, of course, but it is able to give you 256+ bit security WITH hardware acceleration. If you just need a security boost and don't care about the speed - use 512 bit variants from the AES finalists $\endgroup$
    – Alexey Vesnin
    Commented May 27, 2015 at 15:53

Not the answer you're looking for? Browse other questions tagged or ask your own question.