Optimal Key Length for Encryption Protocols Balancing Security and Performance

Question

Imagine a scenario where you can generate encryption keys of arbitrary bit lengths, with a trade-off: longer keys make encryption slightly slower, but not prohibitively so. For context, consider a baseline of a 10,000-bit key offering:

Near-perfect entropy (~8.0 bits/byte),
Avalanche effect around 50%,
Exceptional performance on NIST statistical tests for randomness.

If you were designing a protocol under these conditions, what key length would you choose? How would you balance security, computational efficiency, and practical implementation?

Answer 1

See "Quick Summary" for a quick summary of my recommendations.

It depends on the target platforms that you will be using the cryptosystem on. I'm assuming that you are talking about symmetric encryption only to simplify things. Parameters for hash functions or asymmetric cryptosystems like PKE or key agreements(KEM, KEX, and etc) are different and need their own discussion.

First of all, what is your platform's resources and what constraints do you have? Are you able to have hardware acceleration for the block cipher/stream cipher?

If you are able to, 256 bit keys are optimal. These days encryption doesn't really take up much resources or time given the fact that we either have fast hardware support(see AES-NI on intel CPUs and various instruction sets for others). 256 bit keys completely negate any need to worry about someone somehow using Grover's algorithm on quantum computing to crack your encryption*. No one will fault you for using 256 bit keys in terms of security. However, if you are on a system that has very low resources(ie slow clock and low ram microprocessor in IoT doing RTOS stuff) or that has very tight latency requirements(ie 100 Gb/s switch with no hardware acceleration), 256 bits might be too much.

The next possible key size that's talked about is 192 bits. This gives decent protection against stuff like multi target attacks and is plenty for most purposes. The problem is that basically nothing actively supports 192 bit encryption. It is standardized but most platforms do not provide it as a default or at all. 128 bit keys is the next rung down. This key size is widely supported by all platforms and provides sufficient security for almost all use cases. It's also faster than the other common option(256 bits). However, 128 bit keys may provoke some questions. People might wonder about quantum computers* or multi target attacks**. For example, if you are trying to attack a collection of 2^40 different AES keys(ie from all TLS traffic and AES encrypted drives), you would expect to crack one of them in 2^88 attempts(2^128 possible keys/2^40 used keys = 2^88). Whether this is a concern is unknown. However, even this would require dedicated resources to perform and the attacker has no way to target a particular user's key. If you are concerned about this above performance/resource constraints, you can just bump up to 256 bit keys instead. Most people are pretty comfortable with this key size. You won't get into trouble for choosing this although you might get some complaints by users who want larger keys.

Finally, the last significant key size is 96 bits. At this size one is already at the point where an attacker may with considerable expense be able to semi reliably attack a single key. 96 bits is used in the smallest symmetric encryption primitives because it provides the best performance while still remaining barely out of reach of attackers.

However, 96 bits is still very much potentially marginal. Consider for example an IoT sensor that is deployed around the world. Let's say that the sensor is a highly successful product and 2^32 devices are made and deployed. Let's say each sensor on average uses 2^16 different 96 bit keys(We'll assume each key is unique) because of rapid key rotation or PFS. The total amount of target keys is 2^48 keys(2^32 devices*2^16 keys per device). The amount of computation required to crack one of the keys is expected to be around 2^48 operations(2^96 total keys / 2^48 target keys).

Let's take some real life figures into account. The bitcoin mining networks in the world right now(ie as of the time I am writing this post) are computing a bit more than 854 exahashes(exa is a prefix for 1,000,000,000,000,000,000 or 10^18) a second. Assuming that each hash computation is equivalent to trying to attack a single (or for the multi target setting the entire target set) key. This means that an attacker the size of the world's bitcoin mining effort can perform around an excess of 2^69*** operations a second. Clearly against our multi target scenario(2^48 keys), the world miner adversary near instantly starts breaking different 96 bit keys in the target set of 2^48 keys. Against a single 96 bit key, this attacker has a 2^-48 bit chance to successfully break it per second. After 1 hour, the attacker will have done 2^81 operations and have a 2^-15 chance of cracking a single targeted 96 bit key. Finally, after a month(assuming a 3 week month), the attacker has done 2^90 operations and have a 2^-6 chance ie a 1 in 64 chance of successfully breaking the target key. That's a 1.5625% chance of success and way better than the lottery to say the least.

As another point of reference, there have been multiple different machines designed(and even made in real life) that are able to attack DES(which has an actual key size of 56 bits, 8 bits are parity and do not actually contribute to the encryption). Let's take EFF's DES Cracker("Deep Crack"). It uses ASICs to attack DES and costed \$250,000. It easily exceeds the target 2^48 computations for the first cracked key in the multi target setting. Deep Crack takes around 9 days to attack all 2^56 possible keys. COPACOBANA is a different system that uses FPGAs(which means it can be repurposed for different attacks) that costs \$10,000 to make. It can attack all keys in under 13 days(total key exhaustion takes double the time for average key break, ie 6.4 days).

Suffice to say, 96 bit keys are at the bare edge of being worth it to attack. Note that the attacker only needs to target the key for a multi target attack. This means for example that different devices using different software for different purposes that only use the same 96 bit key cipher for encryption(with different methods for key derivation) can all be attacked in the same multi target attack. Anything less than 96 bit keys is too low for cryptographic security worth using in terms of encryption. Anything less than 64 bits is basically entirely worthless. You only need 256 of the DES crackers equivalent hardware to be able to crack 64 bit keys in the same amount of time as cracking DES normally. Also note that these crackers are using older technology. FPGAs have likely gotten faster and larger recently with the corresponding speedup in brute force.

Quick Summary-Symmetric key size:

256 bits- Default secure answer. It might be too expensive resource or performance wise. Supported by many platforms but might not be default. Completely removes concerns about multi target or attackers with ludicrously fast or large quantum computers.

192 bits- Tradeoff between 256 and 128 bits in terms of both security and performance/resource. Expect less platforms and software to support this key size.

128 bits- Common key size, might be attackable by using extreme amounts of computational power and a very large multi target attack. Supported by many platforms, likely default as it is smaller. Few will complain about 128 bit keys.

96 bits- Smallest usable key size for security. Vulnerable to a multi target attack by an attacker that has medium resources(ie storage for around 2^48 ciphertexts and can buy FPGAs). Very much vulnerable against an attacker like the NSA(who can lob large budgets, datacenters, and supercomputing resources). Useful for IoT and constrained devices that are unable to support larger key sizes. Avoid using for anything that can handle 128 bit keys(which is only 4 bytes larger).

64 bits- NO. JUST NO. DO NOT USE. There are machines that have been designed and made in real life that could be used to attack this key size in less than a month. How does \$2,560,000 to guarantee breaking all keys in less than a month sound? Or \$320,000 for all keys in less than 6 months?

Less than 64 bits- SEE ABOVE. And it's worse because you have a smaller key size. Choosing a key this small is like expecting Mifare Classic to be secure(it is hilariously insecure).

*In reality, running Grover's algorithm to attack symmetric encryption is unlikely to work for even 128 bits. Grover's algorithm is essentially strictly serial, requiring all/almost iterations to return a useful output with high probability. Each operation on a quantum computer is slow enough that trying to run for example 2^64 Grover iterations(needed to target 128 bit keys) is unlikely to ever occur. Trying to parrallelize the computation is also a no go given that parallel Grover is much slower. You only get a square root speed up at best which means for example using 2^16 quantum computers give a 2^15 speedup. This means in order to for example get a run time of 2^32 against a 128 bit key(2^64 for a single QC), you would need 2^33 QCs, each doing 2^32 Grover iterations. Not a likely thing given that QCs do not perform elementary operations as fast as normal computers(ie on GHz speeds). See these two stack exchange answers for more info.

**See this for information on how a multi target attack might work. Link to the most recent version of the paper.

*** 854 exahash/s = 854*(1018) which is approximately equal to 2^69.53 hashes/operations a second

Answer 2

It could be argued that there isn't really a general "optimal key length" that is optimal irrespective of a cryptosystem. Most cryptographers and e.g. NIST do expect a specific, related key strength of 128 bits (efficient but secure) to 256 bits (for higher confidence in the security, usually at the expense of performance). NIST usually also identifies 192 as an in-between security level, but that generally receives less attention - at least for symmetric operations where the overhead of 256 bit security isn't that large.

However, most symmetric cryptosystems - and you seem to be proposing a symmetric cipher - manage to have a key size that is close to this security level. So AES-128 provides near 128-bit security, using 128 bit keys as the name suggests. This could be considered the optimal key length for the simple reason that it is the smallest key size that delivers the required level of security.

Quantum computing muddles the water though. Not all algorithms are quantum-safe. Hoever, most symmetric ciphers and derived constructions such as secure hash-algorithms are relatively safe. They can still be attacked using Grover's algorithm, and possibly by hybrid classical / quantum computer based attacks. Grover requires a lot of qubits though and a pretty stable quantum computer. In that case the strength against quantum computers is halved. It seems that your algorithm was designed to take this in mind.

So assuming that a shorter key size is considered beneficial then a 256 bit key size should be plenty to achieve 128 bit security in the theoretical sense. According to most cryptographers here the practical security may be higher than that due to the requirements asked of the quantum computer required to perform the attacks. Anything higher than this will make the use of the algorithm inefficient, and key sizes of 10k or higher (such as proposed in the question) will be especially problematic in many situations.