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.
• Instead of creating a hash function with variable
size input, hash function with fixed size input will
be created and it will be used required number of
time.
• The fixed size input function is known as
compression function.
• The Scheme is referred as iterated cryptographic
hash function.

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)
Secure Hash Algorithm(SHA)
RIPEMD-160
2. A symmetric-key block cipher serves as a compression
function.
Whirlpool

12.5
 Hash Function Made from Scratch

Message Digest(MD)
Designed by Ron Rivest
versions- MD2,MD4,MD5

MD5 divided msg into blocks of 512 bits and creates

128-bit digest which is too small to resist collision

attack.
Secure Hash Function(SHA)
Based on MD5
Versions- SHA-128, SHA-224, SHA-256, SHA-384

and SHA-512

12.6
 Hash Function Made from Scratch

Other Algorithms
RACE Integrity Primitives Evaluation message
Digest(RIPMED)
RIPMED-160 is based on MD5 but two line of parallel

execution is there.
HAVAL is variable length hashing algorithm with

message digest size 128, 160, 192, 224 and 256 where
block size is 1024.

12.7
 Comparison of SHA

12.8
 Hash Functions based on block cipher

Rabin Scheme

Figure 12.2 Rabin scheme

12.9
 12.1.2 Continued

Davies-Meyer Scheme

Figure 12.3 Davies-Meyer scheme

12.10
 12.1.2 Continued

Matyas-Meyer-Oseas Scheme

Figure 12.4 Matyas-Meyer-Oseas scheme

12.11
 12.1.2 Continued
Miyaguchi-Preneel Scheme

Figure 12.5 Miyaguchi-Preneel scheme

12.12
 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.13
 12.2.1 Introduction

Figure 12.6 Message digest creation SHA-512

12.14
 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.15
 12.2.1 Continued

Figure 12.7 Padding and length field in SHA-512

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

Message Digest Initialization

• Each Value is a fraction part of the square root of the

corresponding prime after converting to the binary and
keeping only the 64 bits.
• Ex: 8th prime=19
• sqrt(19)= 4.35889894354(100.0101 …1001)2
(4. 5BE0CD19137E2179)16
12.19
 12.2.2 Compression Function
Figure 12.10 Compression function in SHA-512

12.20
 12.2.2 Continued
Figure 12.11 Structure of each round in SHA-512

12.21
 12.2.2 Continued
Majority Function

Conditional Function

Rotate Functions

12.22
 12.2.2 Continued

12.23
 12.2.2 Continued

There are 80 constants, K0 to K79, each of 64 bits. Similar

These values are calculated from the first 80 prime
numbers (2, 3,…, 409). For example, the 80th prime is
409, with the cubic root (409)1/3 = 7.42291412044.
Converting this number to binary with only 64 bits in the
fraction part, we get

The fraction part: (6C44198C4A475817)16

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
 Questions

1. Find the result of RotR12(x) if

X=1234 5678 ABCD 2345 34564 5678 ABCD 2468
2.Find the result of ShL12(x) if
X=1234 5678 ABCD 2345 34564 5678 ABCD
2468
2.Find the result of Rotate(x) if
X=1234 5678 ABCD 2345 34564 5678 ABCD
2468
2.Find the majority (x,y,z) and Conditional (x,y,z) if
X=1234 5678 ABCD 2345 34564 5678 ABCD
2468
12.26
y=2234 5678 ABCD 2345 34564 5678 ABCD
 MD Family

12.27
Introduction MD5
 Fifth iteration developed by Professor Ronald L.
Rivest (RSA) in 1991.
 According to RFC 1321, “MD5 message-digest
algorithm takes as input a message of arbitrary
length and produces as output a 128-bit
"fingerprint" or "message digest" of the input …
 The MD5 algorithm is intended for digital
signature applications, where a large file must be
"compressed" in a secure manner before being
encrypted with a private (secret) key under a
public-key cryptosystem such as RSA.”
 MD5 is optimized for use on 32-bit computers
MD5 Algorithm Structure
MD5 Algorithm
Implementation Steps

Step1 Append padding bits

The input message is "padded" (extended) so that

its length (in bits) equals to 448 mod 512.

Padding is always performed, even if the length of

the message is already 448 mod 512.

Padding is performed as follows: a single "1" bit is

appended to the message, and then "0" bits are

appended so that the length in bits of the padded
message becomes congruent to 448 mod 512.
At least one bit and at most 512 bits are
appended.
Implementation Steps

Step2. Append length

A 64-bit representation of the length of the

message is appended to the result of step1.
If the length of the message is greater than 2^64,

only the low-order 64 bits will be used.

The resulting message (after padding with bits and

with b) has a length that is an exact multiple of 512

bits.
The input message will have a length that is an

exact multiple of 16 (32-bit) words.

Implementation Steps

Step3. Initialize MD buffer

A four-word buffer (A, B, C, D) is used to compute

the message digest. Each of A, B, C, D is a 32-bit

register. These registers are initialized to the
following values in hexadecimal, low-order bytes
first):

word A: 01 23 45 67
word B: 89 ab cd ef
word C: fe dc ba 98
word D: 76 54 32 10
Implementation Steps
Implementation Steps

Round 1.

[abcd k s i] denote the operation a = b + ((a + F (b, c, d)

+ X [k] + T [i]) <<< s).

Do the following 16 operations.

[ABCD 0 7 1] [DABC 1 12 2] [CDAB 2 17 3] [BCDA 3 22 4]
[ABCD 4 7 5] [DABC 5 12 6] [CDAB 6 17 7] [BCDA 7 22
8]
[ABCD 8 7 9] [DABC 9 12 10] [CDAB 10 17 11] [BCDA 11 22
12]
[ABCD 12 7 13] [DABC 13 12 14] [CDAB 14 17 15] [BCDA 15 22
16]
MD5 vs. MD4

 A fourth round has been added.

 Each step has a unique additive constant.
 The function g in round 2 was changed from (XY v
XZ v YZ) to (XZ v Y not(Z)).
 Each step adds in the result of the previous step.
 The order in which input words are accessed in
rounds 2 and 3 is changed.
 The shift amounts in each round have been
optimized. The shifts in different rounds are
distinct.
Summary

 Comparing to other digest algorithms, MD5 is

simple to implement, and provides a "fingerprint"
or message digest of a message of arbitrary
length.
 It performs very fast on 32-bit machine.
 MD5 is being used heavily from large
corporations, such as IBM, Cisco Systems, to
individual programmers.
 MD5 is considered one of the most efficient
algorithms currently available.
 Thank You…

12.38