# CMAC vs HMAC security strength

From the perspective of a Birthday Paradox attack, isn't it true that CMAC based on AES-128 is weaker than HMAC-SHA-1? The attack on CMAC-AES-128 requires about $2^{64}$ operations whereas the same attack on HMAC-SHA-1 requires $2^{80}$.

Regardless from the comparison of the CMAC-AES-128 with HMAC-SHA-1 it seems to me that running the birthday attack with about $2^{64}$ operations on CMAC-AES-128 is "somewhat trivial", so it can't be considered to be secure anymore. DES that has a key size of 56 bits can be broken easily with $2^{56}$.

-
The birthday attack on DES is only 2^28, half the number of bits. –  Jeff-Inventor ChromeOS Aug 10 '14 at 0:35

Comparing a brute force attack on DES (with $2^{56}$ operations) to a birthday attack on CMAC (with $2^{64}$ operations) would appear to be an apples-to-Volkswagen comparison; they are assuming two things are similar, when they really aren't.

The brute force attack on DES involves obtaining a single plaintext/ciphertext block pair, and then going through the possible DES keys, and looking for a key that encrypts that plaintext block into that ciphertext block. The key here is that, once the attacker does have that plaintext/ciphertext pair, he no longer needs anything else from the attackee Alice -- he runs all these trial encryptions on his own hardware, and if he feels the search isn't going fast enough, he just buys more hardware. The speed of the attack is limited only by the attackers budget.

On the other hand, the birthday attack on CMAC involves asking Alice for the MAC of a huge number of messages (and then digging through those MACs to find a duplicate). The key point is that we need a great deal more from Alice; it is not sufficient to obtain a limited number of bits, instead if we need to generate the MAC of $2^{64}$ messages, that means that we need to present those $2^{64}$ messages to Alice, and we need her to compute the MACs of all those messages.

That's the key point: Alice will compute those MACs only so fast, and the attacker cannot speed it up by parallelism or anything. If Alice is able to generate only 1 MAC per nanosecond, that means that it'll take over 500 years to generate the MAC for all $2^{64}$ messages.

In summary: any attack that requires $2^{64}$ exchanges with Alice cannot be considered "somewhat trivial"; even if a brute force attack with the same abstract effort would be.

-
I wan't comparing the brute force attack with the birthday attack. I was just discussing about the possibility to have attacks that required 2^56 partially complex operations. –  BlaX Aug 10 '14 at 16:32
@user1204481: well, as above, it depends on what those operations are. If they require interaction with the system under attack, such an attack would appear to be less feasible than if that attack could be done entirely by the attacker. –  poncho Aug 10 '14 at 19:17
I was assuming that the attack is initiated on a random string. The adversary does not have to communicate with anyone, so the bottleneck that Alice creates can be ignored and the attacker can be working on several GPUs. I still didn't get a clear answer to my both questions. –  BlaX Aug 10 '14 at 22:51
@user1204481: so, how do you perform the attack without being able to get MACs of chosen messages? –  poncho Aug 11 '14 at 1:15
@user1204481: remember, the attacker cannot compute the MAC of any message (he doesn't have the keys). So, how does he find two messages m and m' where he knows that both MACs are equal (and without asking Alice for the MACs for a huge number of messages)? –  poncho Aug 11 '14 at 12:52