Why is RMAC resistant to birthday attacks?

Adam Back adam at cypherspace.org
Tue Oct 22 01:09:32 EDT 2002

I think they are presuming there will be no encryption, so Eve can
verify collisions by observing the MAC values.  Eve just records
messages and their MACs that Alice sends Bob.  They are also presuming
exceedingly long lived MAC keys.  (If you changed keys the collection
of messages would have to start over).  The optional salt ensures that
K3 (the key used to do the final encryption of the CBC-MAC computed
using K1) is different even if the same MAC keys are used
indefinately.  (K3 = K2 xor salt).

Note also in A.3 they are talking about a full collision rather than
just an equal MAC.  If the MAC is truncated (m<b), then you can have
equal truncated MACs but different untruncated MACs.

So the full collision looks like: 

MAC(x) = MAC(x')

they then observe that for RMAC (and many other MACs) given (1)

MAC(x||y) = MAC(x'||y) (2)

and (2) means that if an attacker can get MAC(x||y) he automatically
has MAC(x'||y) for all values of y he can induce Alice into MACing as
they have the same full MACs (and truncated MACs).

This leads to the comment that:

(from A.3):
| Moreover, if a parameter set is chosen in which m<b, i.e., if
| CIPHK3(On) is truncated to produce the MAC, then the discarded bits
| may be difficult for an unauthorized party to determine, so collisions
| may be difficult to detect.

which means that if the MAC is truncated it could suprisingly be
actually stronger (against this attack anyway) because the attacker
can't distinguish a truncated MAC collision from a full MAC collision
because he only sees the truncated MACs.  Truncated MAC collisions are
still useful to the attacker probably: he can swap the messages and
fool the verifier.  But full MAC collisions allow the attacker --
presuming he passively sees or can actively persuade Alice to compute
multiple MAC(x||y) for different y values -- then he can subject to
that limitation re-use the work of finding the full MAC collision.


Victor.Duchovni at morganstanley.com wrote:
> So Eve wants to convince Bob that a message really is from
> Alice. What does Eve do?  Does Eve somehow entice Alice to send
> ~sqrt(2^n) messages to Bob? How does the birthday attack come into
> play when the attacker cannot independently test potential
> collisions?

The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com

More information about the cryptography mailing list