Cryptography Reference
In-Depth Information
I
=
(
,
,
)
Definition 5.1
A
message authentication code
is a 3-tuple
Gen
Mac
Ve r
of polynomial-time algorithms that satisfy the following conditions:
•
Gen
is a probabilistic algorithm that takes as input a
security parameter
1
n
and
outputs a key
k
such that len
1
n
(
k
)
≥
n
, which we denote, as usual, by
k
←
Gen
(
)
.
•
The tag generation algorithm
Mac
is either a probabilistic or a deterministic algo-
rithm that takes as input a key
k
and a message
m
and outputs a tag
t
. We write
this as
t
←
Mac
(
k
,
m
)
.
•
The verification algorithm
Ve r
is a deterministic algorithm that takes as input
akey
k
, a message
m
, and a tag
t
and outputs a bit
b
∈{
0
,
1
}
. This output
b
:=
Ve r
(
k
,
m
,
t
)
is interpreted as meaning
valid
when
b
=
1 and
invalid
when
b
=
0.
}
∗
,the
We require that, for any key
k
output by
Gen
and any message
m
∈{
0
,
1
following correctness condition holds:
Ve r
(
k
,
m
,
Mac
(
k
,
m
))
=
1. We sometimes
write
Mac
k
(
m
)
instead of
Mac
(
k
,
m
)
and
Ve r
k
(
m
,
t
)
instead of
Ve r
(
k
,
m
,
t
)
.
1
n
If, for each key
k
output by
Gen
(
)
,
Mac
(
k
,
−
)
is only defined for messages
of a given fixed length
(
n
)
, and
Ve r
(
k
,
m
,
t
)
=
0 for every message
m
of length
=
(
n
)
, then
I
is said to be a
fixed-length
MAC of length
(
n
)
.
5.2.2 Security for MACs
We have already seen that authentication security is not provided by encryption
security and so it is necessary to define the concept of security for a MAC. The
intuitive idea is very simple: an adversary should not be able to produce messages
that will look authentic to the receiver; only the sender should be able to do that.
Bearing in mind how the MAC algorithms are used, this means that no polynomial-
time adversary should be able to generate a pair
(
m
,
t
)
such that
Ve r
(
k
,
m
,
t
)
=
1,
where
m
is a message that did not originate with the sender.
The reader should be warned against misinterpreting the above requirement. For
example, it is clear that if an adversary
A
is able to recover the secret key
k
, then
A
is able to break this intuitive notion of security because it could then compute
Mac
for any
m
it chooses. However, as in the case of encryption schemes,
security against key recovery is far from fulfilling the requirement just stated because
there are many conceivable ways in which an adversary could
forge
a valid pair
(
k
,
m
)
)
without knowing the key. The definition of MAC security should capture the idea
that these forgeries should not be feasible. Note also that, as already mentioned, a
forgery in which
m
looks random should also count as a security break because the
concept of a meaningful message is application-dependent and the definition should
be as strong as possible to include a wide range of situations such as, for example,
when
m
is a randomly chosen key.
There is another kind of attack that allows the adversary to forge a valid pair
(
m
,
t
)
easily: the adversary can use such a pair if it was previously sent by the sender, and
such a pair will be accepted by the verification algorithm. This is called a
replay
(
,
m
t
