Cryptography Reference
In-Depth Information
hence an equivalent formulation of the security definition is that the advantage of
any PPT adversary is negligible.
Example 5.2 Let us reconsider the situation of Example 5.1, where Alice wishes to
send to Bob the message:
> m := "Please transfer from my account to Eve's account the amount of $1000"
but suppose that now, instead of encrypting the message, Alice sends a message/tag
pair
where t has been computed with a UF-CMA secure MAC. Eve nowwants
to replace m by:
(
m
,
t
)
> m' := "Please transfer from my account to Eve's account the amount of $9000"
However, since an authenticationMAC is being used, Eve has to compute a forgery
m ,
t )
(
and, by Definition 5.3, she can only do that with negligible probability. The
fact that m is closely related to m does not help Eve in this case.
Exercise 5.1
I = (
(i) Let F be a block cipher of length n and consider theMAC
Gen
,
Mac
,
Ve r
)
,
n and, if m
{
,
}
=
m 1 ||
m 2 || ... ||
where Gen chooses k uniformly at random in
0
1
(
,
) =
F k (
m 1 )
F k (
m 2 )
m
, where each m i is an n -bit block, then Mac
k
m
...
(while Ve r is the algorithm that computes the tag of a message
and compares it to the given one). Show that this MAC is not CMA secure and
that there are adversaries that, even without making any oracle queries, have
advantage 1. (Hint: Remember that an adversary is successful if it can forge a
pair
F k (
m )
1, where m is any message of its choice
whose tag has not been previously computed by the honest parties.)
(ii) Consider the followingmodification of the precedingMAC. If m
(
m
,
t
)
satisfying Ve r
(
k
,
m
,
t
) =
=
m 1 || ... ||
m
,
n
/
2 , then Mac
where m i
∈{
0
,
1
}
(
k
,
m
) =
F k (
1
||
m 1 ) ...
F k ( ||
m
)
, where
-bit encoding of the integer i . Show that there is an adversary
which makes three oracle queries and has advantage 1.
i
is a binary
(
n
/
2
)
5.3 Constructing MACs
We have defined MACs and we have also given a definition of security for MACs.
In this section we show how to construct MACs that meet the requirements of these
definitions.
5.3.1 MACs from Pseudo-Random Functions
A natural approach to construct a MAC is just to take a (keyed) pseudo-random
function F and to consider the tag obtained by directly applying this function to
the message m . We will consider messages of fixed length n and the MAC
I F
=
(
Gen
,
Mac
,
Ve r
)
given by the following algorithms:
 
Search WWH ::




Custom Search