Why there are still no keys longer than 256 bit?

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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!

Answer 5

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.