When the term "XEX" or the phrase "XOR-encrypt-XOR" is used, does it refer only to the scheme $CT = E_{K}(PT \oplus T) \oplus T$/$PT = E_{K}(CT \oplus T) \oplus T$ (where $T$ is the whitening/tweak value), leaving out how the value of $T$ is changed between blocks if it is even specified to be changed at all? Or does it also refer to a specific method of changing $T$ between blocks?

If it is the former, then does that mean the birthday bound will apply to any mode of operation constructed around it where $T$ is deterministically generated? For instance, let's say we use the second method of generating the tweak as specified in this question where $T = E_K(IV \boxplus i)$. What would happen if this were used to encrypt more than $2^{0.5 \times n}$ blocks?

If it is the latter, then does the birthday bound only apply to when $T$ is stepped using finite field multiplication as in XTS?

  • $\begingroup$ Can you find the answers to your question in the paper that introduced XEX, Phillip Rogaway, ‘Efficient Instantiations of Tweakable Blockciphers and Refinements to Modes OCB and PMAC’, Tech report, September 24, 2004? $\endgroup$ Commented Dec 4, 2017 at 2:29
  • $\begingroup$ @SqueamishOssifrage The answer from it is unclear. I see talk about a polynomial-derived tweak, but nothing about whether or not it is the reason the birthday bound applies, so it doesn't answer my second question. $\endgroup$
    – Melab
    Commented Dec 4, 2017 at 4:01
  • 1
    $\begingroup$ See the detailed security reduction theorems and proofs. Generally, wherever you see a $q^2$, that's a likely candidate for collisions and birthday bounds. But the details are more complicated than that—the birthday paradox manifests in many ways, and is usually not articulated as such but rather as collision probabilities, replacement of random functions by random permutations, etc. $\endgroup$ Commented Dec 4, 2017 at 17:00
  • $\begingroup$ @SqueamishOssifrage By "my second question" I was referring to my question about using same block cipher to encrypt a counter to generate the tweak value. $\endgroup$
    – Melab
    Commented Dec 4, 2017 at 18:40
  • $\begingroup$ Permuting the set of tweaks is not going to change any of the security. Mapping them through a function that, unlike a permutation, is not injective and may have collisions, on the other hand, may change things, because of those collisions. $\endgroup$ Commented Dec 4, 2017 at 21:05


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.