XEX Mode (with two tweaks) is the following scheme:

$X = E_{k}(I) \otimes \alpha^j \\ C = E_{K}(P \oplus X) \oplus X$

where $I$ and $j$ are both tweaks (sector number and block number respectively). If I wanted to use only one tweak, $I$, is the following correct and safe?

$X = E_{k}(I) \\ C = E_{K}(P \oplus X) \oplus X$

Essentially $j$ is treated as $0$, which I believe eliminates it from the equation.

To clarify what I mean by "safe"; does the second scheme I show have the same security guarantees that the first scheme has, as outlined in Rogaway's paper? I skimmed the paper, but remain unclear as to whether the second scheme is included in the XEX family as Rogaway defined it.

  • 2
    $\begingroup$ Word safe is ambiguous. Please, define in more detail what is your intended security model. $\endgroup$ – user4982 Apr 30 '14 at 14:40
  • $\begingroup$ It would also be quite slower than original XEX, because you need two encryptions for each block, instead of one per block + one per sector. $\endgroup$ – Paŭlo Ebermann May 1 '14 at 9:36
  • $\begingroup$ @PaŭloEbermann: Correct, but not in all cases. If the application performs many random, block sized reads/writes then the simplified scheme (as corrected in the answer below) would be faster (requiring 2 encryptions, instead of 2 encryptions + GF(2^128) multiplication). But really, I was just curious how to do it; less so actually implementing XEX/XTS like that. $\endgroup$ – Xor May 1 '14 at 20:24

No, using XEX mode with $j = 0$ is not entirely safe. As noted in section 6 of the Rogaway (2004) paper (emphasis mine):

"Some added care is needed to address the security of XEX. Suppose, to be concrete, that we are looking at $\mathsf{XEX}[E,2^{\mathbf I}]$ and $\mathbf I=[0\mathop{..}2^{n-2}]$. Let the adversary ask a deciphering query with ciphertext $C=0^n$ and tweak $(0^n,0)$. If the adversary has a construction-based deciphering oracle then it will get a response of $M=\tilde D_K^{0^n}\,^0(0^n)=D_K(Δ)⊕Δ=D_K(\mathsf N)⊕\mathsf N=0^n⊕\mathsf N=\mathsf N$, where $\mathsf N = E_K(0^n) = Δ$. This allows the adversary to defeat the CCA-security. For example, enciphering $2M=2\mathsf N$ with a tweak of $(0^n,1)$ and enciphering $4M=4\mathsf N$ with a tweak of $(0^n,2)$ will give identical results (if the adversary has the construction-based enciphering oracle). Corresponding to this attack we exclude any tweak $(N,i_1,\dotsc,i_k)$ for which $(i_1,\dotsc,i_k)$ is a representative of $1$—that is, any tweak $(N,i_1,\dotsc,i_k)$ for which $α_1^{i_1} \dotsb α_k^{i_k} = 1$. In particular, this condition excludes any tweak $(N,0,\dotsc,0)$."

However, using $j = 1$ is safe, and, indeed, is explicitly used as an example of a valid tweak by Rogaway e.g. in section 3:

"Tweaks that are not the increment of a prior tweak will also arise, and they will typically look like $(N,1,0\dotsc,0)$. Constructions should be reasonably efficient in dealing with such tweaks."

Also, in their comments on the XTS mode, Liskov and Minematsu confirm that, indeed, $j=0$ is a bad choice for XEX (emphasis original):

"Note that $j = 0$ must be excluded, as $f(0, v) = v$ for any $v$, which implies $ρ = 1$. Moreover, if $j = 0$ was allowed, a simple attack based on this fact existed, as pointed out by [6] and [3]. Hence if XEX is used, one must be careful to avoid $j$ being $0$."

However (while generally criticizing the choice to use two keys for XTS), they also note that this requirement to avoid $j = 0$ only applies to the single-key XEX mode, and not to XTS, which uses separate keys for the tweak and encryption stages:

"Note that XTS does not require to avoid $j = 0$, as the offset function of XTS needs not be $(ϵ,γ,ρ)$-uniform, but only be $ϵ$-AXU if it is combined with URP. This difference is significant in security, but has no impact on effectiveness for practical applications."

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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