Cryptography Reference
In-Depth Information
Each transformation layer uses an
f
i
function and a
k
i
constant.
f
i
is a bitwise
Boolean function defined by
,
,
=
f
1
(
b
c
d
)
if
b
then
c
else
d
f
2
(
b
,
c
,
d
)
=
b
XOR
c
XOR
d
f
3
(
b
,
c
,
d
)
=
majority(
b
,
c
,
d
)
f
4
(
b
,
c
,
d
)
=
b
XOR
c
XOR
d
where the majority function is defined by
majority(
b
,
c
,
d
)
=
(
b
AND
c
)OR(
c
AND
d
)OR(
d
AND
b
)
.
(As a Boolean function, if two bits out of
b
,
c
, and
d
are equal, then majority(
b
,
c
,
d
)
is equal to that bit.)
As previously mentioned, the difference between SHA and SHA-1 is little. SHA
has exactly the same compression function except for the “key schedule” which is
replaced by
1:
for
i
=
16 to 79
do
2:
x
i
←
x
i
−
3
XOR
x
i
−
8
XOR
x
i
−
14
XOR
x
i
−
16
3:
end for
with the ROTL rotation missing!
For completeness we mention that the the US standard on secure hash algorithms
also includes four other algorithms called SHA224, SHA256, SHA384, and SHA512
(see Ref. [17]). These four algorithms are quite similar, and are more complex variants of
SHA-1. The message digest length is 224, 256, 384, and 512 bits respectively. SHA384
and SHA512 work with 64-bit words instead of 32-bit words, and cut messages in
blocks of 1024 bits instead of 512.
3.2
The Birthday Paradox
If the hashed value is of size
n
, regular brute force preimage or second preimage attacks
require 2
n
hash computations: we iteratively pick a random
x
until we find a solution.
The probability that the complexity is exactly
i
(which means that the
i
-th trial succeeds,
and all previous ones fail) is (1
2
−
n
)
i
−
1
2
−
n
. Thus, the average complexity in terms
of number of hash computations is
−
+∞
2
−
n
)
i
−
1
2
−
n
2
n
i
(1
−
=
.
i
=
1
Collisions are easier to find with the attack in Fig. 3.7, thanks to the
birthday
paradox
. This paradox simply notices that if we pick 23 people, by assuming that their
Search WWH ::
Custom Search