I've read "A Parallelizable Enciphering Mode" by Halevi and Rogaway about the encrypt-mix-encrypt mode for ciphers and was asking myself if this mode provides "full" diffusion.
So if an attacker alters one bit of the ciphertext, how many bits (all?) get scrambled on decryption? (if using AES and blocks of size 4096 bits (drive sector size))
Or in other words: Does this mode turns a "narrow" block cipher into a "wide" cipher and hence would be a perfect choice for full-disk encryption (FDE)?
Yes, EME is a wideblock cipher. Theorem 1 (in Section 4, top of page 5) states that EME is secure as a wideblock (tweakable) cipher under the assumption that AES (or whatever blockcipher you use) is secure.
Specifically, to someone who doesn't know the key, EME will look like a set of random, independent permutations (one for each tweak). This is true even if the attacker can both encrypt and decrypt whatever they wish. This in turn implies that all the bits get scrambled upon decryption if a single ciphertext bit is corrupted. (The definition at the bottom of page two captures these ideas, and then Theorem 1 states that EME meets this definition).
Yes, but.
While EME is a secure block cipher, its security is not as good as a regular block cipher of that size would be. Theorem 1 of the linked paper shows that the adversary has an advantage after ~$2^{n/2}$ oracle queries, which is expected with an $n$-bit block cipher, rather than $2^{m/2}$ as we would desire for an $m$-bit wide block cipher.
Since it's tweakable, it's better than most non-wide modes for disk encryption, but it isn't as good for general purpose encryption as an $m$-bit wide block cipher would be. The 128-bit block size of AES (if you use that as the cipher) still means the attacker has an advantage once you get close to $2^{64}$ blocks encrypted.
