Is this EAX extension weakening the (provable) security of EAX?

Question

I would like to insert a key deriving function into EAX mode, in order to hamper brute-force attacks for a key-size restricted cipher (56 bits). The modification inserts an identical multi-block pattern $S$ behind the corresponding tweaks:

Original: $OMAC(T||...)$ where the 128-bit tweak $T$ is either 0, 1, 2.

Modification: $OMAC(T||S||...)$

The state of the MAC behind $S$ is different for disjunct tweaks, because the MAC's state behind $S$ can be decrypted back to the original tweak, and identical states would yield identical tweaks.

Is this EAX extension weakening the (provable) security of EAX?

Answer 1

So you want to use EAX with a block cipher with a 56-bit key. Presumably, this is for a good reason.

Your idea is to include a (long!) fixed string in the OMAC to slow down nonce creation. Since the attacker must know the nonce to test if a key is correct, this should also slow down a brute force attack.

Instead of modifying EAX, you could use EAX in a slightly different way: Always prefix the EAX nonce by S, and always prefix the associated data by S. This seems to be equivalent in operation to your proposed modification. I don't think the EAX security proof covers this specific case, but I wouldn't be surprised if it could be adapted to this case. (Probably, you could argue that a random-looking function remains random-looking even when its inputs are restricted.) Which means that this should be ok.

You should note that including S in the associated data doesn't hinder the attacker, only the users of the system. So probably, S should only be included with the EAX nonce.

PS. You need a really good reason to use a 56-bit block cipher today.