Cryptography Reference
In-Depth Information
Chapter 8
Cryptographic Hash Functions
In this chapter, we elaborate on cryptographic hash functions. More specifically,
we introduce the basic principles and properties of such functions in Section 8.1,
address a basic construction (i.e., the Merkle-Damgard construction) in Section 8.2,
overview exemplary cryptographic hash functions in Section 8.3, and conclude with
some final remarks in Section 8.4.
8.1
INTRODUCTION
As mentioned in Section 2.1.2 and formally expressed in Defintion 2.3, a
hash
function
is an efficiently computable function
h
:Σ
in
→
Σ
out
that takes an
arbitrarily sized
1
Σ
in
(with Σ
in
representing the input alphabet)
input word
x
∈
Σ
out
(with Σ
out
representing the output alphabet)
of size
n
.Furthermore,a
cryptographic hash function
is a hash function that has
specific properties. There are basically three properties that are relevant from a
cryptographic viewpoint.
and generates an output word
y
∈
•
A hash function
h
is
preimage resistant
if it is computationally infeasible to
find an input word
x
Σ
in
∈
with
h
(
x
)=
y
for a given (and randomly chosen)
∈
R
Σ
out
.
output word
y
•
A hash function
h
is
second-preimage resistant
or
weak collision resistant
if
it is computationally infeasible to find a second input word
x
∈
Σ
in
with
x
=
x
and
h
(
x
)=
h
(
x
) for a given (and randomly chosen) input word
∈
R
Σ
in
.
x
Remember from Section 2.1.2 that one usually has to assume a maximum length
n
max
for input
words. In this case, the hash function is formally expressed as
h
:Σ
n
max
in
1
→
Σ
out
.
