4
$\begingroup$

AES uses 256 bit keys. Newer symmetric ciphers like Salsa20 still use at most 256 bit keys. But everyone talks about the security level after quantum computers so they say 128 bit key will provide 64 bit key, 256 bit will be 128 bit. So in the post quantum world we'll have no longer 256 bit security, right? So why don't these latest symmetric ciphers have longer keys like a Salsa20 with 512 bit key? Wouldn't it be more secure for post quantum world and for a very very long time?

$\endgroup$
1

5 Answers 5

9
$\begingroup$

If quantum operation is as cheap as a classical operation (that's a very big "if"), then 256-bit AES keys will be effectively reduced to 128 bits of security. Not only does Grover's algorithm really not parallelize very well, but quantum operations are currently quite slow.

In theory, a 128-bit block cipher used in certain ways can be vulnerable to a multi-target attack where an adversary needs only to find some keys and has access to a tremendous amount of known-plaintext encrypted under different keys. The problem stems from the fact that an adversary can try different keys against the entire batch of targets at once. This can be an issue with block ciphers in CTR mode with a fixed nonce. In such a situation, 128 bits of security may be insufficient.

A 256-bit key would only be insecure assuming:

  1. A multi-target attack is relevant, and
  2. Quantum operations are as cheap as classical operations.

All things considered, 256-bit security is still enough and will be for the foreseeable future.

$\endgroup$
2
  • 3
    $\begingroup$ Actually, I would posit that even if we had a multi-target attack, and quantum operations were as cheap as classical operations are currently, it would still be infeasible to attack. If we assumed the attacker had $2^{32}$ targets, then Grover's (without parallelization) would require circa $2^{112}$ cipher evaluations, which is still more than what we can do classically (and that's not taking into account that $2^{112}$ sequential operations is infeasible and adding parallelization would increase the total amount of computation $\endgroup$
    – poncho
    Aug 29, 2022 at 2:11
  • 1
    $\begingroup$ @poncho Hence "A multi-target attack is relevant". You need a lot of targets and a lot of computing power to pull that off, even when you can parallelize easily. $\endgroup$
    – forest
    Aug 29, 2022 at 3:39
3
$\begingroup$

We currently believe that 128-bit security is sufficient for all current and future computing needs. For example, using the theoretical minimum amount of energy, storing $ 2^{128} $ bits would require more energy than boiling the world's oceans. As such, providing 128 bits of security with a 256-bit key after quantum computing should be secure since an attacker is not typically expected to practically harness the energy resources of multiple celestial bodies.

It is the case that in certain situation, such as with block ciphers in CTR mode, you can be vulnerable to multitarget attacks where the attacker can attack many keys at once with the same input block at the same time. This is one case in which 128-bit security isn't ideal. However, this is easily avoided in many cases by deriving the IV and the key using a KDF, which many protocols do already, so it's not a serious risk in most cases.

It may in the future be such that we would like to hedge against future advances and build symmetric algorithms with 512-bit keys, but at this point, it doesn't seem practically necessary.

$\endgroup$
4
  • 2
    $\begingroup$ I have to disagree with this because it neglects to mention multitarget attacks which can be used against 128-bit keys in certain circumstances (e.g. CTR mode with a fixed nonce) and can recover a non-negligible number of them. $\endgroup$
    – forest
    Aug 29, 2022 at 0:46
  • $\begingroup$ While that's true, it's easy to avoid multitarget attacks by just using a KDF to generate both the key and IV. AES-CTR isn't suitable for use with random nonces anyway, so this is often a thing you'd want to do. $\endgroup$
    – bk2204
    Aug 29, 2022 at 21:32
  • $\begingroup$ Yeah, it is easy to avoid. I think it would be worthwhile if you edited your answer to point that out, since otherwise one could naïvely assume that 128 bits is safe in all contexts. $\endgroup$
    – forest
    Aug 29, 2022 at 21:35
  • $\begingroup$ whats the effect of quantum computers on block size of symmetric ciphers? do we need a larger block size too? $\endgroup$
    – crypt
    Jan 1, 2023 at 12:47
1
$\begingroup$

Because even 128 bits of security can't broken by brute force in any reasonable amount of time.

From 128 or 256 bit Encryption: Which Should I Use?

However, while this seems significant, it doesn’t break either algorithm. With the right quantum computer, AES-128 would take about 2.6110^12 years to crack, while AES-256 would take 2.2910^32 years. For reference, the universe is currently about 1.38×10^10 years old, so cracking AES-128 with a quantum computer would take about 200 times longer than the universe has existed.

Instead we hear a lot about side-channel attacks where the additional key size doesn't help nearly as much.

$\endgroup$
1
  • 1
    $\begingroup$ "AES-128 would take about 2.6110^12 years to crack"; that sounds wrong; to come up with such a figure, we would need to assume that the Quantum Computer would need circa 5 seconds to compute an entangled AES. IMHO, it would appear to be plausible that a CRQC might just be considerably faster than that (not to mention the possibility of speeding things up by using multiple in parallel; that dilutes the squareroot speed-up you get with Grover's, but it does speed things up) $\endgroup$
    – poncho
    Aug 27, 2022 at 21:54
0
$\begingroup$

Remember that crypto schemes always create an overhead on user experiences. Maybe, if Google takes five minutes in the name of security to open your inbox, you will search for an alternative tomorrow. Based on the underlined application, it is always tried to find an optimal balance between security cost and performance.

Now, coming to your question, below three justifications should justify your query,

  1. First, practical Quantum computers are still in science fictions and decades away.
  2. In speculated Quantum world, a 256-bit key would give at least 128-bit of security. Even if we assume that quantum operations are as cheap and fast as classical bit operations, brute force $2^{128}$ will take thousands of years. Here we assume the underline security algorithm has no potential vulnerability for key recovery.
  3. Larger keyed ciphers generally need more encryption rounds and are slower, which may potentially impact the user experience. Moreover, larger keys make key management immensely harder. On-chip key provisioning, key agreement, key table storing, and maintenance become very difficult. We can see that all the potential candidates of Post Quantum Cryptography (PQC) candidates have a key size in megabytes!

Adaptation of asymmetric key PQC algorithms and larger symmetric keys in resource (time, memory, area) constrained devices will create a lot of challenges!

$\endgroup$
-2
$\begingroup$

Theoretically, there is nothing stopping us from utilizing a more vast key space. Practically, this would be a waste of resources. 128 key spaces are already very secure, and will be in the foreseeable future. While scaremongers have been claiming that Quantum Computers will decrease the key space to 128, this is still not a large enough concern. 128 is far from being insecure, which is why many websites and web browsers that use the HTTPS protocol still use it.

You may be wondering why we do not use RSA which has a 4096 bit key space. The answer is that not only is RSA slow that encrypting data with it directly is frustrating, the key space is vulnerable to Shor's algorithm on Quantum Computers, but is also somewhat vulnerable to the General Field Number Sieve, which has brute-forced up to 829 bits.

This 829 Bit brute-force by no means means that 128 and 256 AES are insecure. RSA uses prime number factorization as its main security method while AES does not utilize prime factorization as its main security function.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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