Chapter 12
Cryptographic
Hash Functions
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
12.1
Chapter 12
Objectives
To introduce general ideas behind cryptographic
hash functions
To discuss the Merkle-Damgard scheme as the basis
for iterated hash functions
To distinguish between two categories of hash
functions:
To discuss the structure of SHA-512.
To discuss the structure of Whirlpool.
12.2
12-1 INTRODUCTION
A cryptographic hash function takes a message of
arbitrary length and creates a message digest of fixed
length. The ultimate goal of this chapter is to discuss
the details of the two most promising cryptographic
hash algorithms SHA-512 and Whirlpool.
Topics discussed in this section:
12.1.1 Iterated Hash Function
12.1.2 Two Groups of Compression Functions
12.3
12.1.1 Iterated Hash Function
Merkle-Damgard Scheme
Figure 12.1 Merkle-Damgard scheme
12.4
12.1.2 Two Groups of Compression Functions
1. The compression function is made from scratch.
Message Digest (MD)
2. A symmetric-key block cipher serves as a compression
function.
Whirlpool
12.5
12.1.2 Continued
12.6
12.1.2 Continued
Rabin Scheme
Figure 12.2 Rabin scheme
12.7
12.1.2 Continued
Davies-Meyer Scheme
Figure 12.3 Davies-Meyer scheme
12.8
12.1.2 Continued
Matyas-Meyer-Oseas Scheme
Figure 12.4 Matyas-Meyer-Oseas scheme
12.9
12.1.2 Continued
Miyaguchi-Preneel Scheme
Figure 12.5 Miyaguchi-Preneel scheme
12.10
12-2 SHA-512
SHA-512 is the version of SHA with a 512-bit message
digest. This version, like the others in the SHA family
of algorithms, is based on the Merkle-Damgard
scheme.
Topics discussed in this section:
12.2.1 Introduction
12.2.2 Compression Function
12.2.3 Analysis
12.11
12.2.1 Introduction
Figure 12.6 Message digest creation SHA-512
12.12
12.2.1 Continued
Message Preparation
SHA-512 insists that the length of the original message
be less than 2128 bits.
Note
SHA-512 creates a 512-bit message digest out of a
message less than 2128.
12.13
12.2.1 Continued
Figure 12.7 Padding and length field in SHA-512
12.14
12.2.1 Continued
Example 12.3
What is the number of padding bits if the length of the original
message is 2590 bits?
Solution
We can calculate the number of padding bits as follows:
The padding consists of one 1 followed by 353 0’s.
12.15
12.2.1 Continued
Example 12.4
Do we need padding if the length of the original message is
already a multiple of 1024 bits?
Solution
Yes we do, because we need to add the length field. So padding is
needed to make the new block a multiple of 1024 bits.
12.16
12.2.1 Continued
Words
Figure 12.8 A message block and the digest as words
12.17
12.2.1 Continued
Word Expansion
Figure 12.9 Word expansion in SHA-512
12.18
12.2.1 Continued
Example 12.6
Show how W60 is made.
Solution
Each word in the range W16 to W79 is made from four
previously-made words. W60 is made as
12.19
12.2.1 Continued
Message Digest Initialization
12.20
12.2.2 Compression Function
Figure 12.10 Compression function in SHA-512
12.21
12.2.2 Continued
Figure 12.11 Structure of each round in SHA-512
12.22
12.2.2 Continued
Majority Function
Conditional Function
Rotate Functions
12.23
12.2.2 Continued
12.24
12.2.3 Analysis
With a message digest of 512 bits, SHA-512 expected to
be resistant to all attacks, including collision attacks.
12.25
12-3 WHIRLPOOL
Whirlpool is an iterated cryptographic hash function,
based on the Miyaguchi-Preneel scheme, that uses a
symmetric-key block cipher in place of the
compression function. The block cipher is a modified
AES cipher that has been tailored for this purpose.
Topics discussed in this section:
12.3.1 Whirlpool Cipher
12.3.2 Summary
12.3.3 Analysis
12.26
12-3 Continued
Figure 12.12 Whirlpool hash function
12.27
12.3.1 Whirlpool Cipher
Figure 12.13 General idea of the Whirlpool cipher
12.28
12.3.1 Continued
Figure 12.14 Block and state in the Whirlpool cipher
12.29
12.3.1 Continued
Structure of Each Round
Each round uses four
transformations.
Figure 12.15 Structure of
each round in the Whirlpool
cipher
12.30
12.3.1 Continued
SubBytes Like in AES, SubBytes provide a nonlinear
transformation.
Figure 12.16 SubBytes transformations in the Whirlpool cipher
12.31
12.3.1 Continued
12.32
12.3.1 Continued
Figure 12.17 SubBytes in the Whirlpool cipher
12.33
12.3.1 Continued
ShiftColumns
Figure 12.18 ShiftColumns transformation in the Whirlpool cipher
12.34
12.3.1 Continued
Figure 12.19 MixRows transformation in the Whirlpool cipher
12.35
12.3.1 Continued
Figure 12.20 AddRoundKey transformation in the Whirlpool cipher
12.36
12.3.1 Continued
Figure 12.21 Key expansion in the Whirlpool cipher
12.37
12.3.1 Continued
Figure 12.22 Round constant for the third round
12.38
12.3.2 Summary
12.39
12.3.3 Analysis
Although Whirlpool has not been extensively studied or
tested, it is based on a robust scheme (Miyaguchi-
Preneel), and for a compression function uses a cipher
that is based on AES, a cryptosystem that has been proved
very resistant to attacks. In addition, the size of the
message digest is the same as for SHA-512. Therefore it is
expected to be a very strong cryptographic hash function.
12.40
