Let's suppose I encrypt something with AES-256 in XTS mode two times (there will be 4 four keys, 2 for each encryption operation), wanting to achive 512-bits of security.
Will this scheme be susceptible to Meet-in-the-middle attacks?
I'm asking this because there are more operations on XTS mode than only directly encrypting the plaintext.
Short answer is "yes, this setup is vulnerable". If you want some math, you can read an explanation below.
In XTS two keys are independent, so it already has 512 bit security (there are no attacks for now, that decrease this number*). So, I'll explain why using double encryption in XTS mode does not increase security.
Let's look closely at encryption equation with XTS mode: $$ c_i = f(m_i, (K_1, K_2)) = T_i\oplus E_{K_1}(m_1\oplus T_i) \\ T_i=E_{K_2}(SN)\otimes\alpha^{i-1} $$ where $SN$ is a sector number, $(K_1,K_2)$ - encryption keys, $m_i, c_i$ - plaintext and ciphertext blocks respectively and $\alpha$ is primitive element of $GF(2^l)$ ($|m_i|=l$).
Now let's consider a block cipher encryption function: $$ E_K=\pi_{q_{r+1}}\circ\varphi_{q_r}\circ... \circ\varphi_{q_1}\circ\delta_{q_0} $$ where $r$ is a number of rounds, $q_i,i=\overline{1,r}$ are round keys (derived from the encryption key using a special set of functions called "key schedule"), $\varphi_{q_i},i=\overline{1,r}$ are round functions, $\pi_{q_{r+1}}, \delta_{q_0}$ are output and input functions with their keys respectively (these two functions may not depend on the key).
Existence of these input and output functions are the key for your question. Let's consider a block cipher with the following encryption equation: $$ E_{K_1,K_2} = \underbrace{\pi'_{q_{r+1}}\circ \pi^{\varepsilon}_{q_{r+1}}}_{\pi_{q_{r+1}}} \circ\overbrace{\varphi^{\varepsilon}_{q_r}\circ... \circ\varphi^{\varepsilon}_{q_1}}^{\varphi_{q_r}\circ... \circ\varphi_{q_1}} \circ\underbrace{\delta^{\varepsilon}_{q_0}\circ \delta'_{q_0}}_{\delta_{q_0}},\ q_0=q_{r+1}=(K_2,SN) $$ where $\varphi^{\varepsilon}_{q_i}=\varphi_{q_i}, i=\overline{1,r}$ - round functions of an underlying block cipher $\varepsilon$ (AES in your case), $\pi^{\varepsilon}_{q_{r+1}}, \delta^{\varepsilon}_{q_0}$ - output and input functions of the underlying block cipher and $\pi'_{q_{r+1}}(x)=E_{K_2}(SN)\oplus x$, $\delta'_{q_0}(x)=E_{K_2}(SN)\oplus x$.
There are some problems with this equation in case of real dependency of $\pi^{\varepsilon}_{q_{r+1}}$ and $\delta^{\varepsilon}_{q_0}$ on their keys (which are different), but they can be easily eliminated by proper choice of key schedule functions. I'll not do that for now to prevent excessive complexity.
Finally we got a block cipher built on top of the existing one by modifying it's output and input functions.
In the simplest case of Meet-in-the-middle attack you create two tables: $$ s_i = E_{K_1,K_2}(m_i) \\ s'_i = E^{-1}_{K'_1,K'_2}(c_i) $$
After that you look for equal values $s_i=s'_i$. This algorithm is suitable for any block cipher and for our one too, so the construction, that was built right now, is vulnerable to this attack, just because XTS adds nothing special to block cipher, i.e. you can consider encryption in XTS mode as block-wise encryption, when each block is encrypted with it's own key.
Knowing the sector number and block position you build two tables as described above for this particular block and find out encryption keys. In the worst case you need to enumerate all pairs of keys $(K_1, K_2)$ twice. So asymptotically there's no increase of security.
* - there is an attack, that allows you to obtain each tweak, when there are two different blocks in the same sector with some condition hold for ciphertexts and plaintexts, but it doesn't recover a tweak key. You can read more about this attack in public comments on XTS-AES.
