Cryptography Reference
In-Depth Information
1. The message
m
is block encoded, meaning that it is encoded as a collection
of
n
message blocks (i.e.,
m
=
m
1
m
n
);
2. A finite PRF is applied to each message block, creating a set of PRF images;
m
2
...
3. The PRF images are added modulo 2, building the XOR MAC.
Note that there are different choices for a block encoding in step 1 and a finite
PRF in step 2, and that each of these choices yields a different XOR MAC construc-
tion. In fact, a randomized (and stateless) XOR MAC construction
XMACR
F,b
and
a deterministic (and stateful)
7
XOR MAC construction
XMACC
F,b
can be defined
for every family
F
of finite PRFs and every block size
b
. Both constructions can be
shown to be secure if the underlying family
F
of finite PRFs is secure.
8
As mentioned earlier, the two MAC constructions can be instantiated using
the DES. For any 56-bit DES key
k
and
l
-bit message block
m
i
(
i
=1
,...,n
),
let
f
k
(
m
i
) be the first 48 bits of
DES
k
(
m
i
).
9
Consequently,
f
k
specifies a pseudo-
random function that is keyed with
k
, and this key is shared between the sender and
recipient of the message
m
to be authenticated. We assume the length of
M
(i.e.,
|
) is a multiple of 32 bits.
10
m
|
The message
m
can then be viewed as a sequence
of
n
32-bit blocks,
m
=
m
1
m
2
...
M
[
n
] with
|
m
i
|
=32. Furthermore, let
i
denote the binary representation of the message block index
i
for
i
=1
,...,n
.
11.2.3.1
Randomized XOR MAC
The
randomized XOR MAC
(XMACR) to authenticate message
m
is computed as
follows:
1. A random 63-bit string
r
is selected as a seed;
2. The value
z
is computed as follows:
z
=
f
k
(0
r
)
⊕
f
k
(1
1
m
1
)
⊕
f
k
(1
2
m
2
)
⊕
...
f
k
(1
n
m
n
)
7
In a stateful MAC the sender maintains information, such as a counter, which he or she updates each
time a message is authenticated.
8
In formalizing this, security of a family of finite PRFs means that it is indistinguishable from a
family of random functions in the sense of [16].
9
Note that
f
k
outputs only 48 bits and not the full 64-bit ciphertext block. The output is truncated
because DES is a pseudorandom permutation, while what we want is a pseudorandom function.
10
This can easily be achieved by a suitable padding.