In the title, $n$ is the block size in bits and will not be used to denote it in the body of this question unless otherwise stated. Imagine that we have $\mathbb{K} \in \{0, 1\}^{\ell_{K}}$, $\mathbb{T} \in \{0, 1\}^{\ell_{T}}$, and $\mathbb{X} \in \{0, 1\}^{\ell_{X}}$, $E(K, T, X): \mathbb{K} \times \mathbb{T} \times \mathbb{X} \rightarrow \mathbb{X}$, and $D(K, T, X): \mathbb{K} \times \mathbb{T} \times \mathbb{X} \rightarrow \mathbb{X}$. We have a tweakable block cipher where the encryption of a block of data is returned by $E(K, T, X)$, the decryption of a block of data is returned by $D(K, T, X)$, $K$ is the secret key, $T$ is the tweak, and $X$ is the block of data. Suppose that this tweakable block cipher is meant to be used in such a way that $T$ is equal to the block number. If $\ell_{T}$ is sufficiently large, then will the maximum number of blocks that can be encrypted under this scheme be equal to or possibly even greater than $2^{\frac{\ell_{X}}{2}}$ or even $2^{\ell_{X}}$?
1 Answer
Abstractly, there is no $2^{l_X/2}$ limit on the security of a block cipher. The security claim is that the block cipher is indistinguishable from a random permutation which it may remain even after the adversary has seen all its inputs and outputs (for a particular key). Similarly, there is no reason a tweakable block cipher needs to become insecure after a certain number of blocks are encrypted.
In practice the security of a block cipher depends on the mode of operation you use and most of those break down one way or another after $2^{l_X/2}$ blocks.
Practical ciphers also do not claim perfect security. AES-128 security claim is only "128-bit security". If you construct a tweakable block cipher from AES-128 the security bound is even lower. E.g. XEX/XTS security proof adds a term that is proportional to the square of the number of encryptions. So you should not use it more than AES itself, but in fact a small factor fewer times.
If you have a tweakable block cipher that is not constructed from another block cipher, its security claim may or may not depend on its block size. So using it like you describe may or may not be secure for more than $2^{l_X/2}$ blocks.
-
$\begingroup$ Is every tweakable block cipher that is constructed from a normal block cipher going to be insecure for more than $2^{0.5 \times \ell_{X}}$ encryptions? $\endgroup$– MelabCommented Dec 28, 2017 at 21:17
-
$\begingroup$ @Melab using XTS, yes. Other constructions, maybe not. I don't think they have to. $\endgroup$– otusCommented Dec 28, 2017 at 21:20
-
$\begingroup$ @otus I would intuitively guess that it may not be possible to avoid the birthday bound, because you're trying to get $2^{\ell_T}$ independent choices of PRP out of a single PRP. Under a single key, there's only one permutation, not $2^{\ell_T}$ independent ones, and a lack of collisions in the outputs for different tweaks might reveal something; if you try to pick different subkeys for each tweak, the subkeys themselves might collide. (This is nowhere near a formal argument, of course, just a hazy intuition!) $\endgroup$ Commented Dec 29, 2017 at 4:50
-
$\begingroup$ @SqueamishOssifrage you are probably right when considering simple (efficient) constructions with a single key and no rekeying. However, when you use more than one key the birthday bound can be avoided. Likely also with constructions that somehow mix the tweak into the key input (which is slow with AES). $\endgroup$– otusCommented Dec 29, 2017 at 8:11