3
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ Feb 22, 2013 at 20:36
  • $\begingroup$ 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 $\endgroup$ Feb 23, 2013 at 0:41
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Feb 23, 2013 at 7:20
  • $\begingroup$ I inserted the word "standard" in the question. $\endgroup$
    – SDL
    Feb 24, 2013 at 5:53

2 Answers 2

7
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Seth
    Feb 22, 2013 at 20:39
  • $\begingroup$ CodesInChaos: What is k? Can you describe the said multi-target attack more clearly? Maybe add some links? thanx $\endgroup$
    – SDL
    Feb 22, 2013 at 20:54
  • $\begingroup$ @SDL Does the update do a better job at explaining the attack? $\endgroup$ Feb 22, 2013 at 20:57
  • $\begingroup$ @CodesInChaos: Great! $\endgroup$
    – SDL
    Feb 22, 2013 at 21:02
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.