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

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?

-
Related question: Can I build a secure tweakable block cipher from a normal one by adding key and tweak?. That idea seems to be the same as yours. –  CodesInChaos Feb 22 '13 at 20:36
Interestingly those approaches are looked at carefully in the context of side channel attacks : this prevents differential power analysis (since we cannot get traces on the same key) and the counter measures for SPA are well understood –  Alexandre Yamajako Feb 23 '13 at 0:41
Your question is based upon the assumption that nobody has considered this alternative. That assumption is wrong. Please rephrase the question to avoid making such tendentious assumptions. –  D.W. Feb 23 '13 at 7:20
I inserted the word "standard" in the question. –  SDL Feb 24 '13 at 5:53

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.

-
Note that this lets you set the tweak directly to $i$, rather than running it through some more complex function $F$. Also, you CAN build a tweakable cipher by running the tweak through a PRF and using that as a blockcipher key (which correponds roughly to SDL's scheme), but this is pretty slow. –  Seth Feb 22 '13 at 20:39
CodesInChaos: What is k? Can you describe the said multi-target attack more clearly? Maybe add some links? thanx –  SDL Feb 22 '13 at 20:54
@SDL Does the update do a better job at explaining the attack? –  CodesInChaos Feb 22 '13 at 20:57
@CodesInChaos: Great! –  SDL Feb 22 '13 at 21:02

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.

-