Cryptography Reference
In-Depth Information
not able in principle—although the security provided by this method is often weak
in practice due to the use of a weak hash function—to recover the password that
would allow them to impersonate the legitimate user. A similar method is used to
protect PIN numbers in ATM machines. It is clear that, for this setup to be effective,
the hash function used should be at least preimage resistant but collision resistance
is not required.
Authentication and digital signatures.
The main cryptographic application of
hash functions is in authentication. We have already seen that the tag generation
algorithm of a MAC is really a keyed hash function and also how universal hash
functions can be used for building MACs. But the unkeyed hash functions that we
are now considering are also very important for authentication and we will see in
Sect.
5.6.5
how they can be used to build MACs. Another reason for their crypto-
graphic interest is that they allow the use of cryptographic primitives that accept only
short inputs in cryptographic schemes that accept much longer inputs. For example,
if we have a MAC
that serves to authenticate short messages, we can extend its
domain by first applying a hash function
h
to the message to be authenticated and
then applying
I
I
that computes the tag
I
's
Mac
algorithm, obtaining a new MAC
of
m
as
Mac
(
; the verification algorithm must be modified
accordingly by first applying the hash function to the message. If
h
is collision resis-
tant and
k
,
m
)
:=
Mac
(
k
,
h
(
m
))
I
can be shown to be UF-CMA
secure too, the intuitive reason being that an adversary that comes up with a forgery
(
I
is UF-CMA secure, then the new MAC
I
either has to find a collision
h
m
,
t
)
for
(
m
)
=
h
(
m
i
)
for some of its queries
m
i
(
)
=
(
m
i
)
(thus breaking the collision resistance of
h
)or,if
h
m
h
for each query, then
(
(
),
)
I
the pair
.
raphy, were it is used to build digital signature schemes from public-key encryption
schemes. In both cases, what is really authenticated (or signed) is not the message
itself but the hash of the message so that, when signing a particular message, all
messages with the same hash value are also signed. From a practical point of view it
might seem that it is sufficient that
h
is second preimage resistant because this will
prevent an adversary from producing a forgery for a given message it chooses. How-
ever, this is really not enough because there are many concrete scenarios in which
the stronger property of collision resistance is needed. For example, a party willing
to sign a certain message (which could be a contract), might prepare in advance two
versions of the message with entirely different meanings but with the same hash
value. In Example 5.12 we show a concrete way in which this can be accomplished.
h
m
t
gives a valid MAC forgery for
5.6.2 The Merkle-Damgård Construction
We have not yet seen any examples of collision resistant hash functions but in this
section we are going to give a construction that is widely used for the purpose
of building such functions. It should be emphasized, however, that there are no
known examples of hash functions whose collision resistance can be proved without
