I would like to insert a key deriving function into EAX mode, in order to hamper
ID: 649239 • Letter: I
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?
Explanation / Answer
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.