TrCBC: Another look at CBC-MAC

CBC-MAC is the first block-cipher-based MAC algorithm. Despite of its advantages, e.g. minimum key size and minimum number of block-cipher invocations, it is commonly known that CBC-MAC cannot deal with arbitrary-length messages safely. Several variants of CBC-MAC have been proposed to fix this flaw; however, all of them do this at a cost of increasing either key size or number of block-cipher invocations, or even both. In this paper, we solve this problem by applying two different truncation methods to CBC-MAC. The proposed TrCBC is provably secure for arbitrary-length messages, still achieving minimum key size and minimum number of block-cipher invocations. At an expense, TrCBC can only produce short tags and has a relatively larger provable security bound. So, TrCBC is suitable for environments where (1) resources (memory, power, etc.) are limited; (2) high speed is required; (3) low security level is enough; (4) short messages are the majority; (5) short tags are required.