Cryptography Reference
In-Depth Information
Problems
12.1.
As we have seen, MACs can be used to authenticate messages. With this prob-
lem, we want to show the difference between two protocols—one with a MAC, one
with a digital signature. In the two protocols, the sending party performs the follow-
ing operation:
1. Protocol A:
y
=
e
k
1
[
x
||
h
(
k
2
||
x
)]
where
x
is the message,
h
() is a hash function such as SHA-1,
e
is a private-key
encryption algorithm, “
” denotes simple concatenation, and
k
1
,
k
2
are secret
keys which are only known to the sender and the receiver.
2. Protocol B:
||
sig
k
pr
(
h
(
x
))]
Provide a step-by-step description (e.g., with an itemized list) of what the receiver
does upon receipt of
y
. You may want to draw a block diagram for the process on
the receiver's side, but that's optional.
y
=
e
k
[
x
||
12.2.
For hash functions it is crucial to have a sufficiently large number of output
bits, with, e.g., 160 bits, in order to thwart attacks based on the birthday paradox.
Why are much shorter output lengths of, e.g., 80 bits, sufficient for MACs?
For your answer, assume a message
x
that is sent in clear together with its MAC
over the channel: (
x
,
MAC
k
(
x
)). Exactly clarify what Oscar has to do to attack this
system.
12.3.
We study two methods for integrity protection with encryption.
1. Assume we apply a technique for combined encryption and integrity protection
in which a ciphertext
c
is computed as
c
=
e
k
(
x
||
h
(
x
))
where
h
() is a hash function. This technique is not suited for encryption with
stream ciphers if the attacker knows the whole plaintext
x
. Explain
exactly
how
an active attacker can now
replace x
by an arbitrary
x
of his/her choosing and
compute
c
such that the receiver will verify the message correctly. Assume that
x
and
x
are of equal length. Will this attack work too if the encryption is done
with a one-time pad?
2. Is the attack still applicable if the checksum is computed using a keyed hash
function such as a MAC:
c
=
e
k
1
(
x
||
MAC
k
2
(
x
))
Assume that
e
() is a stream cipher as above.
12.4.
We will now discuss some issues when constructing an efficient MAC.
