Why nobody considers counter re-keying as a standard Block Cipher Mode?

Question

One of the simplest possible cipher modes is setting each successive key as a function F of the previous one.

K[0] = Master key
C[i] = E(K[i],P[i]), K[i]=F(K[i-1])

This is similar to the counter mode CTR, but the key is incremented instead of the plaintext.

Obviously this mode is slower than the others, since key schedule takes generally more time than encryption (2 times more for AES). Nevertheless some ciphers have very fast re-keying. Also there is the problem with related keys attacks, and some ciphers are not well protected to them — but still this is not a problem for all ciphers.

I wonder why it is not even mentioned as an alternative block mode nor it has a proper name.
Does it have any security drawback? Is it broken?

Answer 1

A tweakable blockcipher where the tweak is set to a counter, and the plaintext gets encrypted directly has the same properties as your idea.

When these properties are desired, you can use either a specialized tweakable blockcipher such as threefish, or you turn a normal blockcipher into a tweakable blockcipher.

When using AES, a typical choice is XTS, which has higher performance and avoids related keys. Such a mode is useful for disk encryption, TrueCrypt is a prominent example using it. And it's documentation has a description of XTS

I believe the encryption part of OCB can be viewed as a tweakable blockcipher as well.

These modes achieve the same thing as your idea, while avoiding the downsides(performance, related keys), so it's not surprising that rekeying isn't used to construct tweakable blockciphers.

---

If you don't use AES, but a cipher with a fast re-keying and no related key vulnerabilities, you can simply concatenate key and counter, which is pretty similar to your idea. I believe this would work with the blockcipher underlying BLAKE. Threefish treats key and counter almost the same way, so you can view as using the concatenation of key and tweak as its key.

---

Another downside of your mode is that it allows a multi-target attack on the key:

When you encrypt a constant file of n blocks (say a zero initialized file), a brute-force attacker can recover your key with $2^k/n$ operations where $k$ is the size of the key, so you should use larger keys, probably 160+ bits or so.

The attacker encrypts the fixed and known plaintext block with varying keys and compares it against all the know ciphertext blocks. This comparison is O(1) using a hashtable. Each attempt has a $n$ in $2^k$ chance of succeeding, since there are $n$ targets. Thus the cost of the attack is $2^k/n$ invocations of the blockcipher.

Answer 2

There are problems with the approach you describe. The biggest is that if changing the key every block causes a significant slowdown. Many block ciphers get a significant speedup by precalculating the key schedule once and then reusing this for many encryptions; your proposal blocks that optimization and thus has a significant performance penalty.

There are also potential security costs. If you use many keys, then time-space-data tradeoff attacks become possible. For a 256-bit key, those attacks are not going to make a difference (as long as you choose $K$ appropriately), but for a 128-bit key, there is some a non-trivial and measurable security loss.

For these reasons, I think your proposed mode is not a good idea. It is slower and less secure than the standard schemes.

And, finally, there is the last most important reason: the standard modes are good enough and are well-vetted. Your proposal doesn't have significant enough advantages to outweigh how thoroughly vetted the standard schemes are.