If using large keysizes, is McOE-X actually safe? After reading the this question, I found the McOE mode of operation for tweakable block ciphers along with its "X" and "G" conversions for normal block ciphers. A quick research yielded the paper "A Simple Key-Recovery Attack on McOE-X" by Mendel, Mennink, Rijmen and Tischhauser which says that McOE-X is severely broken with $2\cdot 2^{n/2}$ effort (n being block / key size).

Now I want to implement McOE, because of the other nice properties it features but before I do that I need clarity on the security properties, namely:


Is McOE-G unbroken (to public knowledge) as of today?
With the hard requirement of at least 256-bit block / keysize, is using McOE-X still safe?
Basically they state that to break a key of length $n$, you need "just" $2^{n/2}$ complexity in both the offline and online phase. This is similar to the birthday paradox, where finding a collision also happens after $\approx 2^{n/2}$ steps for a $n$ bit hash.

With today's computation power, something like DES with 56 bits is possible to brute force. If you have a symmetric cipher with 128 bit, this is actually bad news, because $2^{64}$ isn't impossible to brute force (given enough ressources and time - in a realistic amount).

However, there is also that part of the attack, which is: $2^{n/2}$ online steps. If you willingly let that one happen in your system, and your server can actually handle that amount of requests, this becomes an issue. Actually, this might not really be possible in a realistic scenario, because $2^{64}$ is still a lot. And there is quite a difference when you compare the time for an online request from a server and an exeution of a symmetric cipher on an FPGA.

But anyway, going for a keysize of 256 bit solves that issue. Brute forcing 128 bit is well beyond anything we could ever achieve. Speaking in the terms of Universal security; from bits and mips to pools, lakes -- and beyond by Lenstra et al., 2013, this is more than "global security": The required energy would be more than to bring the water of the entire planet to boil.

Im summary, the attack is not a real danger, even with 128 bit encryption. The online phase should be far from realistic in a practical setup, easily noticable and easy to counter with a limit of requests your server answers. But you should nevertheless choose 256 bit keylength at least, and then it should be fine.

The switching of keys for the cipher might allow key-related attacks, like they were studied for AES. Then for the specific cipher of your choice there might be consequences. For example I am not aware if 3DES was analyzed for related-key attacks. But any decent modern symmetric cipher should be okay.