# Is using EAX mode with a 64-bit block cipher a bad idea?

EAX mode produces an authentication tag no longer than the length of the underlying cipher's blocksize. So in the case of using Blowfish (a 64-bit block cipher) in EAX mode, the resulting tag would be 8 bytes.

Is an 8-byte tag sufficiently long (I doubt it)? Could such a short tag subject the ciphertext to any sort of cryptanalysis to which a longer tag could resist?

I understand, of course, that there are plenty of reasons to prefer a 128-bit block cipher... I'm merely curious.

-
A 64 bit authentication tag isn't a big problem. Authentiation tags are not subject to offline attacks. With an ideal 64 bit MAC each forgery has a $2^{-64}$ chance of being accepted. Thus HMAC-SHA256 with a 128 bit key truncated to 64 bits would give okay security. But I don't know how close EAX is to an ideal MAC. Many AEAD schemes decay as message length increases or as more messages are observed. I'm too lazy to investigate how EAX fares. There is also the concern of birthday problem related attacks with $2^{32}$ cost. –  CodesInChaos Jun 19 '13 at 19:50
64 bit authentication tags are however subject to online attacks. Normally you can live with a $2^{-64}$ risk of someone generating a valid tag by pure chance, but it might be a problem if the authentication scheme is such that the attacker might lower the odds of success by collecting lots of known plain/cipher text pairs. –  Henrick Hellström Jun 19 '13 at 20:07

Using EAX with a 64-bit block cipher is problematic, because the short block size causes some weaknesses due to internal collisions. I do not recommend it. Use a 128-bit block cipher.

Indeed, the world has moved away from 3DES and towards AES exactly because of these fundamental problems with a 64-bit block size: the internal collision effect means that, with a 64-bit block cipher, once you encrypt more than about $2^{32}$ blocks of data, it is very likely that there will be at least partial leakage of secret information. This problem is not specific to EAX: it is endemic to essentially every block-cipher-based mode of operation around.

We can be more precise and quantify the nature of the problem by looking at the security theorem for EAX.

• Confidentiality. The security theorem (Corollary 6 in the EAX paper) says that, assuming our block cipher is perfect, an adversary who wants to violate confidentiality can do so with advantage at most $9.5 \sigma^2/2^n$. Here $\sigma$ counts the number of $n$-bit blocks that are encrypted, and $n$ is the block size. If you want to use EAX with a 64-bit block cipher, then you have $n=64$, so this expression for the adversary's advantage evaluates to $9.5 \sigma^2/2^{64}$. For good security, you want to keep this number significantly lower than 1. Unfortunately, if you encrypt one billion blocks (8 GB of data, i.e., $\sigma = 2^{30}$), then this expression evaluates to $0.59$, so the adversary's advantage might be that big.

In rough intuitive terms, if you encrypt 8GB of data under a single key using EAX with a 64-bit block cipher, there's at least a 50% chance that the attacker learns some partial information about the secret messages. That's not good. Instead of 50%, we would much prefer this number to be much smaller: like one in a million or something. So, the security level obtained is not really acceptable.

• Integrity. The same security theorem also gives us a bound on the chances that the attacker is able to create a forged packet, assuming the attacker gets a single attempt. This probability is at most $11 \sigma^2/2^n + 1/2^\tau$, where $\sigma,n$ are as before and where $\tau$ is the length of the authentication tag. Assuming you use a 64-bit authentication tag (which I recommend), the security level is $(11 \sigma^2 + 1)/2^{64}$. For $\sigma=2^{30}$ (8GB of data), this probability is about $0.69$.

In other words, if you encrypt up to 8GB of data using EAX with 64-bit block cipher (using the same key for all data), then an attacker who makes a single attempt at forgery might have as large as a $0.69$ chance of success, with just a single attempt. If the attacker makes multiple attempts (which of course the attacker can do), then the attacker's success probability might increase even more. This is totally unacceptable. We probably want the attacker's success probability, after making (say) a billion attempts, to be small (say, one in a million or something). A 64-bit block cipher falls far short.

TL;DR: Use a 128-bit block cipher. A 64-bit block cipher is cutting things too fine.

-