Background
I have an Lua Environment which has the blowfish crypto (CBC, IV = {00..0}) builtin. AES is not available and pure Lua AES-Implementations are way to slow.
Problem
I want to generate a CMAC according to the algorithm specified in RFC 4493, which is AES based. As I need this CMAC for exchange between the Lua environment and another program built by myself, I thought I just change all AES crypt functions to Blowfish ones.
The input length for each CMAC is 26 Byte, whereas only a few bytes change between different CMAC generations. For example:
AAAAAAAAAAAA BA AACCCCCCCDDDDDDDDDFFFFFFFFFFFFFFFFFFFF
AAAAAAAAAAAA AB AACCCCCCCDDDDDDDDDFFFFFFFFFFFFFFFFFFFF
which results in the problem, that the first part of the CMAC is identical for each input and only the last part changes:
0123456789ABCDEF 48534593402BC93D
0123456789ABCDEF DF82BC920DA92383
Is this a problem of the blowfish algorithm? Is there anything I can do (change the CMAC algo) to ensure, that I get different results, especially with only small changes to the input?
By design CMAC can be used with 64-bit block ciphers such as Blowfish. But the output will also be 64 bit. You should not change anything in the algorithm. See http://csrc.nist.gov/publications/nistpubs/800-38B/SP_800-38B.pdf for reference. Also note that the security of 64bit MACs is quite low.