# 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
@CodesInChaos In contrast to D.W.'s answer, do you think there is still an argument in favor of using a 64 bit block cipher with EAX mode of operation (when a 128 bit block cipher is not available)? – Maarten Bodewes Aug 26 '14 at 17:55
@owlstead 1) I don't get your question. In my comment I worry about birthday attacks, and D.W.'s answer confirms that the proof of security breaks down as you approach the birthday bound. So we're saying pretty much the same thing, except that D.W. wasn't too lazy to look at the details. 2) As a software guy, a cipher not being available doesn't enter my considerations. There are so many good ciphers that I certainly wouldn't bother with a 64 bit cipher, unless I specifically want one. For my taste even 128 bit blocks are a bit on the low side, I prefer 256 bit blocks. – CodesInChaos Aug 27 '14 at 8:04
@CodesInChaos OK, thanks. I think you understood my question sufficiently to answer. Interesting thought about the 256 bit blocks size for cipher. I'm mostly on embedded, so ciphers not being a available is/was something to consider, unfortunately. – Maarten Bodewes Aug 27 '14 at 8:11

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.

-

CMAC (or OMAC1) is the underlying MAC algorithm that provides authentication and integrity for EAX. Is stated in NIST SP 800-38B:

Because CMAC is based on an approved symmetric key block cipher, such as the Advanced Encryption Standard (AES) algorithm that is specified in Federal Information Processing Standard (FIPS) Pub. 197 [3], CMAC can be considered a mode of operation of the block cipher. CMAC is also an approved mode of the Triple Data Encryption Algorithm (TDEA) [10]; however, as discussed in Appendix B, the recommended default message span for TDEA is much more restrictive than for the AES algorithm, due to the smaller block size of TDEA.

How restrictive quickly becomes clear:

For any system in which CMAC is implemented, the risk that an attacker can detect and exploit a collision shall be limited to a level that is appropriate to the value of the data. A simple and prudent method to achieve this goal is to establish and enforce an appropriate limit on the message span of any CMAC key, which in turn limits the probability that a collision will even occur. For general-purpose applications, the default recommendation is to limit the key to no more than $2^{48}$ messages when the block size of the underlying block cipher is 128 bits, as with the AES algorithm, and $2^{21}$ messages when the block size is 64 bits, as with TDEA. Within these limits, the probability that a collision will occur is expected to be less than one in a billion for the AES algorithm, and less than one in a million for TDEA.

only to continue with:

For applications where higher confidence in the security is required, the message span of a key may be measured in terms of the total number of message blocks. The recommendation in this case is to limit the key to no more than $2^{48}$ message blocks ($2^{22}$ Gbytes) when the block size is 128 bits, and $2^{21}$ message blocks (16 Mbytes) when the block size is 64 bits. Within these limits, the probability that a collision will occur is proved to be less than one in a billion for the AES algorithm, and less than one in a million for TDEA, assuming that the underlying block cipher has no weakness...

I've included these quotes mainly to back up the thoughts written down by D.W.. One in a million is not good enough for current cryptographic purposes, and 16 Mbytes of data isn't much either.

Basically this all says: use a 128 bit cipher unless you have a very restrictive, very well designed protocol as well as a very good reason to use a 64 bit block cipher. Even more basically this should tell you not to use a 64 bit block cipher at all for CMAC or EAX.

-