Cryptography Reference
In-Depth Information
These properties are just mentioned for completeness; they are not further used
in this topic.
Having the previously mentioned properties (i.e., preimage, second-preimage,
and collision resistance) in mind, one can define
one-way hash functions
(OWHFs),
collision resistant hash functions
(CRHFs), and
cryptographic hash functions
as
suggested in Definitions 8.1 and 8.2.
Definition 8.1 (One-way hash function)
An
OWHF
is a hash function
h
:Σ
in
→
Σ
out
that is preimage resistant and second-preimage resistant.
Definition 8.2 (Collision resistant hash function)
A
CRHF
is a hash function
h
:
Σ
in
→
Σ
out
that is preimage resistant and collision resistant.
Note that a CRHF is always an OWHF (whereas the converse may not be
true). Also note that alternative terms sometimes used in the literature are
weak one-
way hash functions
for OWHFs and
strong one-way hash functions
for CRHFs. As
suggested in Definition 2.4, we use the term
cryptographic hash function
to refer to
either of them.
MERKLE-DAMG ARD CONSTRUCTION
8.2
Most cryptographic hash functions in use today follow a construction that was
independently proposed by Ralph C. Merkle and Ivan B. Damgard in the late 1980s
[1, 2].
3
According to their construction, an
iterated hash function
h
is computed by
repeated application of a collision resistant compression function
f
:Σ
m
Σ
n
−→
and
m>n
to successive blocks
x
1
,...,x
n
of a message
x
.
4
As illustrated in Figure 8.1, the compression function
f
takes two input
arguments:
with
m, n
∈
N
1. A
b
-bit message block;
2. An
l
-bit chaining value (sometimes referred to as
H
i
for
i
=0
,...,n
).
In a typical setting,
l
is 128 or 160 bits and
b
is 512 bits. The output of the
compression function can be used as a new
l
-bit chaining value, which is input to
the next iteration of the compression function. Referring to the notation introduced
earlier,
m
=
b
+
l
and
n
=
l
.
3
Both papers were presented at CRYPTO '89.
4
Note that the input alphabet Σ
in
and the output alphabet Σ
out
are assumed to be the same (denoted
as Σ).
