XTS mode with the tweak key as the sole secret

Question

The keyspace of XTS is $2^{512}$ due to its use of two distinct keys, and the most effective attack (a meet-in-the-middle attack) brings this down to $2^{384}$. This implies that knowledge of either the main key or the tweak key does not significantly reduce security. What confuses me is the idea that the scheme is still secure even if the main key is known and only the tweak key is kept secret. This idea I got from an answer to another question which notes that an attack revealing the main key but not the tweak key is not a fatal attack, leaving the scheme with a remaining $2^{256}$ keyspace. Looking at a diagram of XEX mode and trying to imagine how it would remain secure when $K_1$ is known, I could not think of any possible way it'd be true:

$K_1$ is the main key and $K_2$ is the tweak key.

XTS mode, sans ciphertext stealing, is defined as:

$$C_{ij} = E_{K_1}(P_{ij} \oplus (E_{K_2}(i) \otimes \alpha^j)) \oplus (E_{K_2}(i) \otimes \alpha^j)$$

Here, $i$ is the sector number and $j$ is the block number within the sector. For the purpose of this question, only one sector matters so $i$ can be considered a constant. Since this makes it such that $E_{K_2}(i)$ is a secret value that never changes, we can define $K^\prime = E_{K_2}(i)$, giving us:

$$C_{j} = E_{K_1}(P_{j} \oplus (K^\prime \otimes \alpha^j)) \oplus (K^\prime \otimes \alpha^j)$$

Because $K_1$ is not secret for our purposes, we can model $E_{K_1}$ as a public PRP $\pi$:

$$C_{j} = \pi(P_{j} \oplus (K^\prime \otimes \alpha^j)) \oplus (K^\prime \otimes \alpha^j)$$

If we simplify things and look at a single $j$, we can say $K^{\prime\prime} = K^\prime \otimes \alpha^j$. Now we have:

$$C = \pi(P \oplus K^{\prime\prime}) \oplus K^{\prime\prime}$$

It looks to me that knowledge of $K_1$ allows an attacker with a plaintext/ciphertext pair to easily derive $K_2$, which, according to the above-linked answer, is not true. Where is the error in my logic?

Answer 1

Actually, you can't remove the $E_{k_2}$ as you did. You had:

$$C_{j} = E_{K_2}(P_{j} \oplus (K^\prime \otimes \alpha^j)) \oplus (K^\prime \otimes \alpha^j)$$

Let me replace the term $(K^\prime \otimes \alpha^j)$ with $K^{\prime\prime}$ and eliminate the $j$ to makes things easier to read. The result is:

$$C = E_{K_2}(P \oplus K^{\prime\prime}) \oplus K^{\prime\prime}$$

This form is that of a type of Even-Mansour cipher. It is a block cipher formed with a public (pseudo-random) permutation $\pi$ and one or more keys with a length equal to the block length. It looks like:

$$C = \pi(P \oplus K_a) \oplus K_b$$

XEX mode uses the same construction to make a tweakable block cipher. In XEX the permutation used is not public. (It is a block cipher with a secret key.) For an EM block cipher the permutation does not need to be secret. (Therefore you can use a block cipher with a non-secret key.) Its security claims just depend on the block size, the assumption that $\pi$ is a pseudo-random permutation, and that the keys are unpredictable and from a uniform distribution.

You cannot eliminate the $\pi$ as you did.

$$\pi(P \oplus K_a) \oplus K_b \neq (P \oplus {K_a}^\prime) \oplus {K_b}^\prime$$

---

Given plaintext ciphertext pairs:

If you omit $K_a$ then you can trivially recover $K_b$. $$C = \pi(P) \oplus K_b$$ $$C \oplus \pi(P) = K_b$$

If you omit $K_b$ then you can trivially recover $K_a$. $$C = \pi(P \oplus K_a)$$ $$\pi^{-1}(C) = P \oplus K_a$$ $$\pi^{-1}(C) \oplus P = K_a$$

If both keys are present, then the best attacks on a generic _{^{single round*}}EM cipher require about $D$ plaintext/ciphertext pairs (D for data) and $T$ evaluations of $\pi$ (T for time) such that $DT \geq 2^n$ where $n$ is the block size.

As for the question "So in essence, the output of $\pi$ will necessarily not be known because of the [correction: $K_a$] added to the input?"

Yes, basically. The exact behavior is a bit subtle and I don't want to cause confusion. So actually either $K_a$ or $K_b$ being unknown is sufficient to make the ciphertext impossible for the adversary to predict IF no plaintext/ciphertext pairs are known.

I actually mean $K_a$ added to the input of $\pi$ makes the new output of $\pi$, that is $\pi(x \oplus K_a)$, impossible for the adversary to calculate because the "real" input, that is $x \oplus K_a$, is not known by him.

If you skip the second XOR ($K_b$) then from one pair you can recover $K_a$ as described above using the inverse of $\pi$.

Similarly if have secret $K_b$ the adversary can compute $\pi^{-1}(x)$ but not $\pi^{-1}(x \oplus K_b)$. The adversary needs to know the difference between $E^{-1}(C) = K_a \oplus \pi^{-1}(C \oplus K_b)$ and $\pi^{-1}(C \oplus K_b)$ to recover $K_a$.

So you can't recover the pre-key ($K_a$) efficiently without knowing the post-key ($K_b$). You can't recover the post-key easily without knowing the pre-key. Both are essential. One protects the other from being recovered.

I hope that makes sense. I struggled to phrase it in a way that made sense without resorting to formal arguments. I will look for references later.

The claim that an EM cipher is secure may not pass the smell test, though. And that's because I forgot to emphasize that you can't actually make a claim to that their security level is equal to their key-size. $|K_a| + |K_b| = 2n$ but the worst case security level is $O(n / 2$) if measured in terms of $min(D + T)$. And you don't limit $D$.

It's better to use larger block ciphers or permutations for that reason. I recall reading using more rounds brings the security level closer to $n$ bits.

(If for some reason we lost the ability to use typical block ciphers we would be perfectly fine using only one round EM ciphers with a "standard" block size of 256 bits instead of 128. We also wouldn't need double the key bulk if we did this. The different subkeys can be generated by KDF. For the single round version there is no loss in security on the generic construct if the pre- and post-keys are equal.)

Also the symmetry of the construct makes informal reasoning a bit easier. Whatever logic applies to encryption or the forward public permutation function also applies to decryption and the inverse permutation function. ie.

$$E_1(P, K_a, K_b) \text{ corresponds to:}\\ \begin{align} X &= P \oplus K_a; \\ Y &= \pi(X); \\ C &= Y \oplus K_b \end{align}$$

$$E_2(P, K_b, K_a) \text{ corresponds to:}\\ \begin{align} X &= P \oplus K_b; \\ Y &= \pi^{-1}(X); \\ C &= Y \oplus K_a \end{align}$$

_{* Rounds in the context of EM ciphers refers to the number of times $\pi$ is used. One round is XOR → permute → XOR. Two is XOR → permute → XOR → permute → XOR. And so on.}