Cryptography Reference
In-Depth Information
additional assumptions. This property can be conditionally proved for some hash
functions under certain hypothesis such as the factoring assumption but these hash
functions turn out to be rather inefficient and here we will look at efficient functions
that are collision resistant in the above-mentioned informal sense and widely used
in practice.
The method we are going to describe is called the
Merkle-Damgård construction
and was independently discovered by these authors in the late 1980s. The idea is to
construct a hash function
h
}
∗
n
:{
0
,
1
→{
0
,
1
}
from a fixed-length hash function
n
+
r
n
g
0), usually called a
compression function
.This
construction is important because it preserves collision resistance, i.e., if
g
is collision
resistant then so is
h
. This facilitates the design of practical collision resistant hash
functions because compression functions are easier to handle.
There are different variants of the Merkle-Damgård construction according to
technical details such as the padding method employed and so on. We will focus on
the method applied to construct the SHA-1 hash function and the SHA-2 family of
hash functions that will be discussed below. Note that, in practice, the size of the
messages to which the hash function will be applied is limited and will typically be
well below 2
n
/
2
bits. Also, the compression function
g
:{
0
,
1
}
→{
0
,
1
}
(with
r
>
n
+
r
n
may,
:{
0
,
1
}
→{
0
,
1
}
n
r
n
.
for convenience, be seen as a function of two inputs
g
:{
0
,
1
}
×{
0
,
1
}
→{
0
,
1
}
Algorithm 5.2. Merkle-Damgård construction
.
n
r
n
be a compression function and
IV
an
n
-bit initialization
1. Let
g
:{
0
,
1
}
×{
0
,
1
}
→{
0
,
1
}
vector.
2. The message
x
is padded with a 1bit followed by a variable number of 0 bits and, finally,
the encoding of the message length in bits, so that the total length of the padded message
is the smallest possible multiple of
r
.
3. The padded message is parsed into a sequence of
r
-bit blocks
x
1
,
x
2
,...,
x
t
.
4. A hash value is initialized by setting
h
0
:=
IV
.
5. For
i
from 1 to
t
,
h
i
.
:=
g
(
h
i
−
1
,
x
i
)
is computed.
6. Set
h
(
x
)
:=
h
t
.
The following theorem, due to Merkle and Damgård, proves that this construction
preserves collision resistance:
