Is there a counter mode of encryption where the key is being changed for every block of data?

Question

I thought like encrypting an IV concatenated with a CTR but instead of XOR-ing this output with the plaintext this output should be used as a temporary key for another encryption block that actually converts the plain- to ciphertext. In other words in a regular CTR mode of operation the XOR would be replaced by a full encryption algorithm and the OTP would be its key.

Answer 1

There are some ciphers which do this, most notably E0, a 128-bit stream cipher based on four LFSRs that is used in older versions of the Bluetooth protocol. As vulnerabilities have been found in E0, a scheme was devised to reduce the security impact called two-level E0. Normally, the cipher encrypts 2745 bits (one Bluetooth frame) at a time. With two-level E0, every 128 bits of the keystream is used to seed another instance of E0 which generates only 2745 bits of keystream from that key.

Note that this is not a special mode of encryption, but the use of true stream ciphers. This difference is minor, as counter mode is merely a way to convert a block cipher into a stream cipher. Most block ciphers (and many stream ciphers) have a key schedule, which is an expensive setup phase whenever a new key is used, making it impractical to frequently switch keys. The stream cipher E0 does not have a complicated key schedule. The 128-bit key is used directly as the cipher's inner state (specifically, it is split up into 25, 31, 33, and 39 bits, each of which is used as the initial state for each of the cipher's four LFSRs). This allows it to change keys frequently without a significant performance impact.

---

Please note that E0, even two-level E0, is not a particularly secure cipher. The key must be changed very regularly or known-plaintext attacks can allow for key recovery. These weaknesses stem from both problems in the design of two-level E0, as well as the fact that E0 is built off of LFSRs, which are non-cryptographic algorithms. Using AES in CTR mode will be far more secure than any type of E0.

Answer 2

Probably not any standardized mode. Block ciphers are normally modeled as a family of bijective functions (permutations). A random function chosen from this family is supposed to be indistinguishable from an actual random permutation. (Even if the entire set of functions is known.) A set of (mathematical) functions with this property is called a pseudorandom permutation (PRP).

When selecting which function in a PRP to use, we need to use a uniform distribution for choosing that specific function. And generally block cipher algorithms require that your key is chosen randomly from a large uniform distribution.

If a block cipher's key is not chosen this way then there may be detectable non-random behavior. And if you have two related keys (like K₂ = K₁ + 1) then you might be vulnerable to a "related key attack". Block ciphers are typically not designed to be used that way.^*

You could try some more complicated key relation, but if the keys aren't derived using a cryptographic function (appearing random for all practical purposes) then there may be a problem. Or one could generate a new 128 bit key for every 128 bit block, but you don't gain much.^**

---

_{^{* See: "standard model" vs. "ideal model" of block ciphers. There are tweakable block ciphers as well, but outside of Skein and disk encryption they probably aren't used very often.
** If you have a secure reproducible random number generator then you have something that can be trivially turned into a stream cipher. Plus algorithm implementations that use key expansion as an optimization would have extra overhead if keys are replaced for each block.}}

Answer 3

Your proposed mode is:

$$ C_i = E_{E_k(\mathrm{IV} || i)}(P_i) $$

... where $E_k(m)$ is the block cipher application with key $k$ to input block $m$, $i$ is the block counter, and $C_i$ and $P_i$ are the $i$th ciphertext and plaintext blocks respectively.

To me this bears resemblance to modes for tweakable block ciphers (TBCs), an extended type of block cipher that in addition to the conventional key and message inputs also take a per-encryption tweak argument. (See the linked Q&A.)

In the Liskov, Rivest and Wagner paper that introduced the notion of tweakable block ciphers, we find this mode:

As the legend explains, the $Z_i$ values that are being used as tweaks to the cipher are IV/counter concatenations. On the left half of the diagram, the message blocks other than the last one are being encrypted by applying the TBC directly to them. (The rest of the diagram shows the last message block being encrypted by a kind of stream cipher, and the computation of an authentication tag.)

We could take your idea of deriving a key for each message block by encrypting an IV and block counter with a master key and think of refactoring it into a construction of a TBC $E^T_k$ out of a conventional block cipher $E'_k$:

$$ E^T_k(m) = E'_{E'_k(T)}(m) $$

I don't know if that is a secure TBC, but the paper offers this construction that doesn't need to rekey the underlying block cipher (an operation that's expensive with many ciphers):

$$ E^T_k(m) = E'_k(T \oplus E'_k(m)) $$

Refactoring your mode to use that construction we'd get something like:

$$ C_i = E'_k(IV || i \oplus E'_k(P_i)) $$

And it seems to me any chosen-plaintext attack on the confidentiality of this simpler mode would imply a corresponding attack on TAE, so the security of TAE would imply the confidentiality of this mode.

---

It should probably go without saying that you'd have to be nuts to implement any of this on your own.