Cryptography Reference
In-Depth Information
One might think that this example is not relevant because of the artificial nature
of the
Mac
algorithm used. But this is not a worthwhile objection because a secure
construction should be secure in
all
its variants. Moreover, it is easy to see that this
construction is not secure either if an ordinary MAC with unique tags—such as, for
example, CMAC—is used. Indeed, we may consider an adversary that queries the
oracle for authenticated encryption of several messages—which might be chosen at
random—until finding two messages,
m
0
,
m
1
say, with different MAC tags
t
0
,
t
1
,
respectively (note that, with high probability, any pair or random messages will have
this property). Then the eavesdropper indistinguishability experiment is performed
for the pair
m
0
,
m
1
, so that the adversary receives a challenge ciphertext
t
b
)
resulting from applying the scheme to
m
b
for a random bit
b
. Now, if the adversary
had only
c
b
at its disposal, it would be unable to output the correct bit because we
are assuming the encryption scheme is CPA secure but, in this case, the adversary
also sees
t
b
which must be equal to exactly one of the tags
t
0
,
t
1
.If
t
b
(
c
b
,
=
t
0
then
the adversary outputs 0 and if
t
b
t
1
then it outputs 1. In each case the adversary
guess is correct with probability 1 and so the scheme does not have indistinguishable
encryptions.
=
5.4.2.2 Mac-then-Encrypt
The previous approach fails because MACs do not protect confidentiality and a
natural way to remedy this deficiency is to first authenticate and then encrypt.
This is accomplished as follows: given a message
m
, the receiver is sent
c
where
c
. In this case the authentication tag is concate-
nated to the plaintext and sent encrypted inside the ciphertext. As in the previous
case, the receiver computes
m
=
Enc
k
1
(
m
||
t
)
with
t
=
Mac
k
2
(
m
)
||
t
=
Dec
k
1
(
c
)
and
Ve r
k
2
(
m
,
t
)
and outputs
m
if veri-
fication is successful and
otherwise. It is clear that now the previous attack on the
Encrypt-and-Mac approach will not work because the MAC tag is encrypted and so
it cannot leak information about the message. But this scheme is also insecure as the
following easy example from [106] shows:
⊥
Example 5.8
Suppose that we have a CPA secure encryption scheme and a UF-CMA
secure MAC and that we replace the encryption algorithm
Enc
of the encryption
scheme by
Enc
defined by
Enc
k
(
m
)
:=
Enc
k
(
m
)
||
1
,
i.e., a 1bit is appended to the ciphertext obtained by applying
Enc
. Of course, the
corresponding decryption algorithm
Dec
proceeds by simply stripping out the last
ciphertext bit and then applying the original decryption algorithm
Dec
.
Now suppose that we use the original MAC and themodified encryption scheme in
the previously describedmanner consisting of authentication followed by encryption.
Although we have not yet formally defined the security concept for authenticated
encryption (the formal definition is given below), it is easy to figure out what is going
