Cryptography Reference
In-Depth Information
Theorem 5.3
If, in the Merkle-Damgård construction, g is a collision resistant
compression function, then h is a collision resistant hash function.
Proof
The idea is to prove that a collision for
h
gives two different intermediate
values
h
i
−
1
,
x
i
)
(
h
i
−
1
,
x
i
)
=
(
which are a collision for
g
. Indeed, suppose that
x
t
be
the sequences of blocks corresponding to the padded messages. Similarly, let
h
i
and
h
i
be as in Algorithm 5.2 so that, by hypothesis, we have that
h
t
x
are two strings such that
h
x
)
x
t
and
x
1
,...,
x
=
(
x
)
=
h
(
and let
x
1
,...,
h
t
and hence
=
h
t
−
1
,
x
t
)
g
(
h
t
−
1
,
x
t
)
=
g
(
. Then, either this is a collision for
g
or both inputs are
x
t
which, in particular means that len
x
)
equal, in which case
x
t
=
(
x
)
=
len
(
and
t
. Thus we also have that
h
t
−
1
=
h
t
−
1
and hence
g
hence that
t
=
(
h
t
−
2
,
x
t
−
1
)
=
h
t
−
2
,
x
t
−
1
)
h
t
−
2
. Since
g
(
. Then, again, either this is a collision for
g
or
h
t
−
2
=
x
x
i
x
=
there must exist an index
i
,1
≤
i
≤
t
, such that
x
i
=
and the pair
h
i
−
1
,
x
i
)
(
h
i
−
1
,
x
i
)
,
(
is a collision for
g
.
5.6.3 SHA-
256
We are going to apply the Merkle-Damgård construction to obtain SHA-256 (where
the initials SHA stand for
Secure Hash Algorithm
), a hash function with a 256-bit
output which is, for now, collision resistant in the practical sense that no efficient
collision-finding algorithm is known. This function, together with SHA-224, SHA-
384 and SHA-512, forms the SHA-2 family that, like the hash function SHA-1, is
specified by NIST in [74] in the framework of the
Secure Hash Standard
(SHS).
The hash functions in the SHA-2 family are some of the best available today, after
other widely used hash functions like MD5 and SHA-1 itself have been shown to be
insecure (we will discuss the security of hash functions later).
Next we describe the SHA-256 function. We start by defining the compression
function that is used to generate it and we shall denote this function by
C
. We need
a series of auxiliary functions in order to define
C
. These functions act on 32-bit
words, represented here by the letters
x
,
y
,
z
, and produce as output a new 32-bit
word. The auxiliary functions are the following:
•
Ch
(
x
,
y
,
z
)
=
(
x
∧
y
)
⊕
(
¬
x
∧
z
)
,
•
Maj
(
x
,
y
,
z
)
=
(
x
∧
y
)
⊕
(
x
∧
z
)
⊕
(
y
∧
z
)
,
•
{
256
}
0
ROTR
2
ROTR
13
ROTR
22
(
x
)
=
(
x
)
⊕
(
x
)
⊕
(
x
)
,
•
{
256
}
1
ROTR
6
ROTR
11
ROTR
25
(
x
)
=
(
x
)
⊕
(
x
)
⊕
(
x
)
,
•
σ
{
256
}
0
ROTR
7
ROTR
18
SHR
3
(
x
)
=
(
x
)
⊕
(
x
)
⊕
(
x
)
,
•
σ
{
256
}
1
ROTR
17
ROTR
19
SHR
10
(
)
=
(
)
⊕
(
)
⊕
(
)
x
x
x
x
,
where
the bitwise Xor,
ROTR
n
the cyclic right shift by
n
positions, and
SHR
n
the right shift by
n
positions.
In Algorithm 5.3 we give the compression function, where the symbol '+' represents
addition modulo 2
32
.
∧
represents the bitwise And,
¬
the bitwise complement,
⊕
