A block cipher whose key changes after each block

Question

I have been reading about various block cipher modes of operation, and all of them seem to treat the block cipher (including it's key and key schedule) as a sort of immutable black box.

I would like to know whether or not any one has designed a mode of operation where the effective key schedule of the cipher is changed between each block encrypted.

Suppose, purely for example, that we had a 256 bit block cipher, using a simple a 4 round Feistel structure. The expanded key, generated from a secure hash of the user-supplied key and an IV, would be 512 bits. In between each pair of blocks encrypted, we treat these 512 bits as the state of a 512-bit linear feedback shift register, advance the LFSR one step, then use the result as the scheduled key for the next block of data encrypted.

Like CTR mode, encryption and decryption are parallelizable, and it has the property of random read access.

Does anything remotely like that exist?

If not, is it because it would be obviously horribly secure in a way I'm not seeing, or for some other reason?

Answer 1

In general you want to treat primitives like block ciphers as black boxes. You first analyze and try to break the block cipher. Once it is proven to operate correctly you can use it as primitive for a block cipher mode of operation. The mode of operation can then be proven to be secure assuming that the block cipher primitive operates well.

If you don't treat the block cipher as a black box then you will basically have to show that the mode of operation doesn't invalidate the security analysis of the block cipher.

---

The subkey derivation may not be the most important part of a cipher, but that doesn't mean that there aren't many things to consider.

---

It seems that tweakable block ciphers do indeed provide an answer to what you want to achieve (see the answer of pg1989 and the comment of SEJPM).

Lets quote the paper that introduced them:

Block ciphers (pseudorandom permutations) are inherently deterministic: every encryption of a given message with a given key will be the same. Many modes of operation and other applications using block ciphers have nonetheless a requirement for “essentially different” instances of the block cipher in order to prevent attacks that operate by, say, permuting blocks of the input. Attempts to resolve the conflict between keeping the same key for efficiency and yet achieving variability often results in a design that uses a fixed key, but which attempts to achieve variability by manipulating the input before encryption, the output after encryption, or both. Such designs seem inelegant—they are attempting to solve a problem with a primitive (a basic block cipher) that is not well suited for the problem at hand. Better to rethink what primitives are really wanted for such a problem.

That's from the introduction of the paper Moses Liskov, Ronald L. Rivest, and David Wagner: Tweakable Block Ciphers.

Answer 2

I doubt something like this exists, because it would be more or less equivalent to having some internal block cipher in a non-standard mode of operation.

Also, changing keys is to be avoided when designing high-performance primitives, because it's pretty slow in most modern ciphers. You'd need a weird cipher that had really high key agility, but then you'd also need this to not affect security. This is one of the design motivations for tweakable ciphers, which SEJPM pointed out in a comment. A 'tweak' is kind of like a secondary key that's not as expensive to change as a block cipher key.

It's anyway not clear what this would buy you in terms of security, since modern ciphers and modes of operation already have crazy huge security margins when used correctly.