Cryptography Reference
In-Depth Information
and accepts the XMACC if and only if
z
=
z
.
11.2.3.3
Discussion
Similar to other MAC constructions, such as HMAC, the security of XOR MACs
can be formally analyzed and quantified. In fact, an adversary's inability to forge an
XOR MAC can be expressed in terms of his or her (presumed) inability to break the
underlying PRF.
The major advantage of XOR MACs (compared to other MAC constructions)
is parallelizability, meaning that all
n
invocations of the PRF (to generate or verify
an XOR MAC) can be done in parallel. As mentioned later, this fact is important and
may be a prerequisite for message authentication in high-speed networks. Similarly,
message authentication can proceed even if the message blocks arrive out of order.
It is only required that each message block
m
i
comes along with its index
i
.
Out-of-order MAC verification is in fact a very useful property in contemporary
networks, such as the Internet (because of packet losses and retransmission delays).
Furthermore, an XOR MAC is incremental in the sense of [17]. Suppose, for
example, that the message block
m
i
is modified to a new 32-bit value
m
i
. Then,
for a long message
m
, one can update the XOR MAC much faster than it would take
to recompute it. For example, let (
r, z
) be an XMACR for message
m
and let
m
be
m
with message block
i
replaced by
m
i
. To compute an XMACR for
m
, one can
randomly select
r
and compute
z
=
z
r
)
m
i
)
.
⊕
f
k
(0
r
)
⊕
f
k
(0
⊕
f
k
(1
i
m
i
)
⊕
f
k
(1
i
The pair (
r
,z
) then represents the XMACR for
m
. Note that this works
because adding a value twice modulo 2 entirely removes its impact.
One disadvantage of XOR MACs is performance. This disadvantage, however,
largely depends on the family of finite PRFs in use. In the case of DES (as discussed
earlier), the number of DES computations for an XOR MAC is twice that of a CBC
MAC (because XOR MACs operate on 32-bit blocks instead of 64-bit blocks). So
an XOR MAC may be twice as slow as a CBC MAC.
In summary, XOR MACs have many properties that make them an appropriate
choice in many situations, especially if one considers high-speed networks that do
not guarantee an absolutely reliable data transmission. If the computer systems
communicating over the network are powerful, then the performance degradation
with a factor of two (as in the case of DES) is not particularly worrisome.
