Cryptography Reference
In-Depth Information
if M
1
,...,
which are sent by the adversary
to the oracle, we assume that the total number of blocks is less than q. The purpose of
the adversary is to output a message M which is different from all M
i
together with its
MAC value c. The probability of success of any adversary (i.e. the probability that the
MAC value is correct) is smaller than
M
d
denote the finite block sequences on
M
q
(
q
+
1)
1
1
×
q
+
d
.
2
N
−
N
−
Note that this is less than q
2
/
N when
4
≤
q
≤
N
/
4
.
√
N
, this is approximately
θ
e
−
θ
2
)
. Therefore,
2
2
When
q
=
θ
(which is greater than 1
−
if the total length of all authenticated messages is negligible against
√
N
, there is no
better way than brute force attack to get collisions on the CBC-MAC (provided that
C
1
and
C
2
are perfectly random!).
Proof.
First of all, we can assume without loss of generality that all
M
i
are pairwise
different. The next step consists of transforming the adversary into a
nonadaptive
collision finder against a hash function
H
defined by
H
(
x
1
,...,
x
)
=
C
1
(
···
C
1
(
C
1
(
x
1
)
⊕
x
2
)
⊕···⊕
x
−
1
)
⊕
x
.
Let
A
be the adversary against the MAC function. We define a collision finder
B
against
H
as follows.
1. We pick a random permutation
C
2
.
2. We simulate
A
. Every time that
A
tries to send a query
M
i
to the oracle, we
answer
c
i
=
c
2
(
H
(
M
i
)) to
A
(
i
=
1
,...,
d
). The simulation ends when
A
issues
a pair (
M
,
c
) or fails.
3. If
A
failed, we send
M
1
,...,
M
d
to oracle
H
. If it outputs no collision, then
B
fails; otherwise it succeeds.
4. If
A
issues a forged pair (
M
,
c
) and if
c
is different from all the
c
i
's, then
B
fails. Otherwise we send
M
1
,...,
M
d
,
M
to oracle
H
. If it outputs no collision,
then
B
fails; otherwise it succeeds.
Let
E
s
be the event that
A
succeeds when run with the MAC oracle. Let
p
s
=
Pr[
E
s
].
1
N
−
d
. Then
B
succeeds with a probability
p
, which is at least
p
s
−
We will prove that
we conclude using Lemma 3.5 given later.
When running
A
with the MAC oracle, let
E
c
be the event that some queries collide,
i.e. that MAC(
M
i
)
=
MAC(
M
j
) for some 1
≤
i
<
j
≤
d
. Clearly,
H
(
M
i
)
=
H
(
M
j
),
so
B
will succeed.
c
d
in the simulation is
exactly the same as the distribution of the MAC(
M
i
) values. Hence the simulation of
Provided that
E
c
does not occur, the distribution of
c
1
,...,
Search WWH ::
Custom Search