Cryptography Reference
In-Depth Information
Properties of Hash Functions
1.
Arbitrary message size
h
(
x
) can be applied to messages
x
of any size.
2.
Fixed output length
h
(
x
) produces a hash value
z
of fixed length.
3.
Efficiency
h
(
x
) is relatively easy to compute.
4.
Preimage resistance
For a given output
z
, it is impossible to find any
input
x
such that
h
(
x
)=
z
, i.e,
h
(
x
) is one-way.
5.
Second preimage resistance
Given
x
1
, and thus
h
(
x
1
), it is computa-
tionally infeasible to find any
x
2
such that
h
(
x
1
)=
h
(
x
2
).
6.
Collision resistance
It is computationally infeasible to find any pairs
x
1
=
x
2
such that
h
(
x
1
)=
h
(
x
2
).
11.3 Overview of Hash Algorithms
So far we only discussed the requirements for hash functions. We now introduce
how to actually built them. There are two general types of hash functions:
1.
Dedicated hash functions
These are algorithms that are specifically designed to
serve as hash functions.
2.
Block cipher-based hash functions
It is also possible to use block ciphers such
as AES to construct hash functions.
As we saw in the previous section, hash functions can process an arbitrary-length
message and produce a fixed-length output. In practice, this is achieved by segment-
ing the input into a series of blocks of equal size. These blocks are processed se-
quentially by the hash function, which has a compression function at its heart. This
iterated design is known as
Merkle-Damgard construction
. The hash value of the
input message is then defined as the output of the last iteration of the compression
function (Fig. 11.5).
Fig. 11.5
Merkle-Damgard hash function construction
