Cryptography Reference
In-Depth Information
7.6. Suppose that you have a sorted list,
A
, of 16-bit values
m
j
and a sorted
list,
B
, of their hash values
h
(
m
j
) for
j
=1
,
2
,...
2
8
. You compare the
lists
A
and
B
pairwise, namely,
(
m
j
,h
(
m
j
))
against
(
m
k
,h
(
m
k
))
,
in order to seek out collisions, where
h
(
m
j
)=
h
(
m
k
). How many compar-
isons must you make to guarantee a success rate of at least 50%?
7.7. What is the maximum number of iterations to produce a collision with
SHA-1? (See pages 255-258.)
7.8. RIPEMD-160, described on page 259, uses little-Endian architecture (see
Footnote 9.24 on page 350). Explain why it must be ensured that the
message digest is independent from the underlying architecture.
7.9. Is A CBC-MAC a one-way transformation? (See page 261.)
7.10. Explain the security problems with an HMAC if it were possible to invert
the hash function
H
(see pages 263-264). In general, explain why hash
function must be practically noninvertible.
7.11. If it were possible to have a “perfect” hash function, then we would have
a powerful imaginary function called a
random oracle
. In other words, if
we could prove that hash functions behave like truly random functions,
we would have the existence of a random oracle. A random oracle has
output that is not only uniform, but also deterministic and eGcient. This
idealized model for a hash function is often called the
random oracle model
,
which was introduced in [14]. In the random oracle model, a hash function
is randomly selected, but we are not given an explicit description of how to
compute the hash values. We are allowed only to query a so-called
oracle
who has access to the function. Think of this as equivalent to looking up
a value of
h
(
m
) for a given
m
in some table. Thus, if we are given
m
then
h
will output the same value
h
(
m
) every time the oracle is queried with
that value. Moreover, if the oracle is not queried with a specific value,
then the output is a random value that has a uniform probability of being
chosen throughout the possible values in the range of
h
.
Based on the above description, suppose that Alice sends messages
m
to
Bob but does so as
h
(
m
) where
h
is a random oracle. Suppose that Mallory
has access to an oracle of his own that allows him to submit ciphertext
(
c,m
), which responds with
true
if
h
(
m
)=
c
and
false
otherwise. Is this
system secure against Mallory's attack?
7.12. Explain how Mallory could successfully impersonate Alice to Bob, in the
X.509 three-way authentication protocol described on pages 269 and 270
if timestamps are not employed.
(
Hint: See Exercise 5.3.
)
Search WWH ::
Custom Search