On the security of CBC-MAC constructions

Hello everyone,

I've got some questions on the security of the CBC-MAC.

As far as I know the security of all CBC-MAC constructions (basic, RMAC, EMAC, XCBC, TMAC, OMAC) is roughly only half that of the block length,
i.e. a successful forgery can be expected after about k*2^(n/2)+something known text-MAC pairs and one chosen text, where k small and n = block length.

As far as I understand these upper bounds on the security are due to attacks presented by Preneel and Oorschot in "MDx-MAC and Building Fast MACs from Hash Functions". These attacks exploit internal collisions within the MAC constructions.

Now I wonder if these attacks are possible if the following conditions hold:
- messages are length-prepended
- message sizes are multiples of a CBC-MAC block length
- message data is uniformly distributed (e.g. through encryption)

Reason:
Forgery can only be conducted if messages x|s and y|s (where s is a common trailing block) can be found such that
h(x|s) = h(y|s), h = CBC-MAC
The probability of finding such collision is ~2^(n/2) due to the birthday phenomenon. When such collision occurs then it occurs also without s, i.e. h(x) = h(y).
The probability that both messages have a common trailing block s is again ~2^(n/2) due to the birthday phenomenon, and because block data is uniformly distributed.
Both events are independent, so the probability that such messages can be found is ~ 2^(n/2)*2^(n/2) = ~2^n. This means the attack described is not applicable.

Now I don't understand if there is anything else that proves that a CBC-MAC provides only half the security?

Some documents suggest that a CBC-MAC-128 truncated up to 64 bits provides full security. Isn't security then also only half the MAC length? Or is it really only dependent on the block length?

I've stated that before and ask again: the CCM authenticated encrypted mode encrypts the CBC-MAC, claiming that this prevents the cited attack because an adversary cannot see collisions. Now does this mean CCM provides full MAC security?

Sorry again for any stupid questions :-)
--Michael Noisternig
.

Relevant Pages

  • Re: On the security of CBC-MAC constructions
    ... message data is uniformly distributed (e.g. through encryption) ... value (which will be used as the message input to CBC-MAC). ... My model was in fact more complex where adversaries could chose the clear text packet headers but not the following chiphertext block. ... bound doesn't promise anything more than square-root security. ...
    (sci.crypt)
  • Re: On the security of CBC-MAC constructions
    ... message data is uniformly distributed (e.g. through encryption) ... value (which will be used as the message input to CBC-MAC). ... The other problem is that we don't know if the internal collision attacks ... bound doesn't promise anything more than square-root security. ...
    (sci.crypt)
  • Re: On the security of CBC-MAC constructions
    ... you can't get more than 64 bits of security when you use any CBC-MAC ... The workfactor to break AES-CBC-MAC ... But do you really you want to encrypt that many blocks of data, ...
    (sci.crypt)
  • >>> MAC SECURITY <<<
    ... mac home security ... free security software for mac ... internet security for mac ...
    (rec.equestrian)
  • Re: the exploit that wasnt
    ... The other Mac Book Pro? ... brought Microsoft into a security discussion about Mac OS X. ... The number of security patches, ... if you were to scan random machines on the internet for a week, ...
    (comp.sys.mac.advocacy)