Symmetric cipher key size vs number of rounds. Longer key = more secure cipher?

Question

I would have questions related to discussion under this article. Bruce Schneier answered questions regarding key size vs number or rounds:

Why do you need more rounds with longer keys? And how did you come up with these seemingly arbitrary numbers for more rounds?

When block ciphers get broken, they're invariably broken due to diffusion failures. What more rounds give you is more diffusions ... the key is twice as long, so it takes more rounds to get complete diffusion of the key.

As to your second question, choosing the number of rounds for a cipher is a combination of experience and guesswork.

For example Threefish 512 has 72 rounds and Threefish 1024 has 80 rounds.

I would like to know your opinion on theses questions:

• If Threefish 1024 would have only 72 rounds (as Threefish 512), could it be in some way less secure than Threefish 512?

• If the number of rounds is a "guesswork", could Threefish 1024 (full 80 rounds) be still less secure than Threefish 512 (72 rounds), because of "incorrect guesswork" (8 additional rounds wouldn't be enough to provide more diffusion to maintain the longer key)?

Answer 1

With enough plaintext/ciphertext available (sizably more plaintext than keysize), any cipher can be attacked by trying all the keys; that's brute force. Therefore, for any cipher, too short key ⟹ insecure cipher.

A common symmetric cipher design goal is that the best attack is brute force as limited by key size, within a small factor. Therefore, for a symmetric cipher meeting that design goal, longer key ⟺ more secure cipher.

A common block cipher design goal is that it is as fast as possible while meeting its security level (matching its keysize per the previous goal). Increasing the number of rounds can make a cipher more secure, but does make it slower. Hence, for a cipher design meeting its security and speed design goals, more secure cipher ⟺ more rounds.

There is no definitive method to find the adequate number of rounds. A typical approach is to examine known attacks; try to make conservative estimate of how many rounds they can break for some security level and extrapolate to the desired security level (perhaps much higher); then take the largest number of rounds found for all attacks, and then some as a design margin.

I pass at the Threefish aspect of the question.

Answer 2

We can make an educated guess. We usually show that a minimal number of rounds is needed for certain diffusion properties and than increase. For instance we show that a single bit flip will flip 50% of output/state bits after k rounds and then require some significantly larger number of rounds.

If you look at the AES and SHA3 competitions, you saw plenty of effort spent attacking reduced round versions. In some cases you saw applicants increase the number of rounds, when they didn't like the small gap between the number of rounds with a better than trivial attack and their recommended number of rounds.

In many ways all of symmetric cipher design is educated guesses. If smart people who have been good at breaking ciphers in the past can't break your cipher or even find weaknesses in slightly weakend versions of it, then we deem it secure. This kind of proof by lack of counterexample is sadly the best we can do.

Answer 3

Mainly it is a question of wanting higher security for a 1024-bit cipher. That is, the variant with the larger key has more rounds so that it has 1024-bit security rather than "only" 512-bit.

However, it is possible that a variant with the same number of rounds but a larger key is weaker, at least theoretically. The extra key bits give more freedom to a related key attack. That is not a very realistic attack model in many use cases, but would matter for using the cipher as a hash function, for example.

So would 72-round 1024-bit Threefish be weaker than 512-bit? Probably not, since brute force attacks on the key are the best we know against the latter. It would have less security margin, however.