Information

Security
(3170720)
U N I T 5 : C R Y P TO G R A P H I C H A S H F U N C T I O N S , T H E I R A P P L I C AT I O N S ,
S I M P L E H A S H F U N C T I O N S , I T S R EQ U I R E M E N T S A N D S E C U R I T Y, H A S H
F U N C T I O N S B A S E D O N C I P H E R B LO C K C H A I N I N G , S E C U R E H A S H
A LG O R I T H M ( S H A )
R E F E R E N C E B O O K - C R Y P TO G R A P H Y A N D N E T W O R K S E C U R I T Y, P R I N C I P L E S
A N D P R A C T I C E S I X T H E D I T I O N , W I L L I A M S TA L L I N G S , P E A R S O N
CHAPTER -11
 Road Map

 Cryptographic Hash Function

 Application
 Simple Hash function
 Requirement and security
 Hash Function based on CBC
 Secure hash algorithm (SHA)
 Message Authentication
 message authentication is concerned with:
 protecting the integrity of a message
 validating identity of originator
 non-repudiation of origin (dispute resolution)
 three alternative functions used to achieve message
authentication:
 message encryption
 message authentication code (MAC)
 hash function
Hash Function
 Hash Function
 Varying length message to hash function  output is fixes
length
 Hash Function Properties
 A “good” hash function
has the property that the
results of applying the
function to a large set of
inputs will produce
outputs that are evenly
distributed and
apparently random.

 A change to any bit or

bits in M results, with
high probability, in a
change to the hash code
[Avalanche Effect]
Hashing vs Encryption
 Hash Function
 The kind of hash function needed for security applications is
referred to as a cryptographic hash function.

 A cryptographic hash function is an algorithm for which it is

computationally infeasible (because no attack is significantly
more efficient than brute force) to find either
 a data object that maps to a pre-specified hash result (the
one-way property) or
 two data objects that map to the same hash result (the
collision-free property). (to find the two message generate
same hash code it is only find by brute force attack)
 Because of these characteristics, hash functions are often used
to determine whether or not data has changed.
Application of Cryptographic Hash Function
 Message Authentication
 Digital Signatures
 One Way Password File
 Intrusion and virus detection
 Message Authentication
 Message authentication is a mechanism or service used to
verify the integrity of a message.
 Message authentication assures that data received are
exactly as sent (i.e., contain no modification, insertion,
deletion, or replay).
 When a hash function is used to provide message
authentication, the hash function value is often referred to as
a message digest.
How to check
Kill X Authenticity of
a message?

Help X
Use of Hash Function for message authentication
The essence of the use of a hash function for message authentication is
as follows.
 The sender computes a hash value as a function of the bits in the
message and transmits both the hash value and the message.
 The receiver performs the same hash calculation on the message bits
and compares this value with the incoming hash value.
 If there is a mismatch, the receiver knows that the message (or
possibly the hash value) has been altered
Method 1: Message and Hash Code encrypted
 The message plus
concatenated hash code is
encrypted using symmetric
encryption.
 Only A and B share the
secret key the message
must have come from A
and has not been altered.
 The hash code provides
the structure to achieve
authentication.

Because encryption is
applied to the entire
message plus hash
code, confidentiality is
also provided.
 Method 2: only Hash Code is Encrypted

 Only the hash code is encrypted, using symmetric

encryption.
 This reduces the processing burden for those
applications that do not require confidentiality
Method 3: sharing a secret value for message
authentication
It is possible to use
a hash function
but no encryption
for message
authentication.

 A and B share a common

secret value S.
 A computes the hash value
over the concatenation of M
and S and appends the
resulting hash value to M.
 Because B possesses S, it
can recompute the hash
value to verify.
 An opponent cannot modify
an intercepted message
Method 4: Adding Confidentiality to Method 3

 Confidentiality can be added to the approach of

method (3) by encrypting the entire message plus
the hash code.

When confidentiality is not required, method (2) has an advantage over

methods (1) and (4), which encrypts the entire message, in that less computation
is required.
 MAC – Message Authentication Code
 More commonly, message authentication is achieved using a
message authentication code (MAC), also known as a keyed
hash function.
 Typically, MACs are used between two parties that share a
secret key to authenticate information exchanged between
those parties.
 A MAC function takes as input a secret key and a data block
and produces a hash value, referred to as the MAC
 The combination of hashing and encryption results in an
overall function that is, in fact, a MAC That is, E(K, H(M))
is a function of a variable-length message M and a
secret key K, and it produces a fixed-size output that is
secure against an opponent who does not know the
secret key
Application of Cryptographic Hash Function
 Message Authentication
 Digital Signatures
 One Way Password File
 Intrusion and virus detection
Digital Signature
 Method 1: Only hash code is encrypted

 The hash code is encrypted, using public-key encryption with the

sender’s private key  this provide authentication
 It also provides a digital signature, because only the sender could
have produced the encrypted hash code.
 Method 2: Both hash code and message are
encrypted

 If confidentiality as well as a digital signature is desired, then the

message plus the private-key-encrypted hash code can be encrypted
using a symmetric secret key
 One Way Password File
 Hash functions are commonly used to create a one-way password file,
in which a hash of a password is stored by an operating system rather
than the password itself.
 Thus, the actual password is not retrievable by a hacker who gains
access to the password file.
 In simple terms, when a user enters a password, the hash of that
password is compared to the stored hash value for verification.
 This approach to password protection is used by most operating
systems.
One Way Password File
 Intrusion and Virus Detection
 Hash functions can be used for intrusion detection and virus
detection.
 Store H(F) for each file on a system and secure the hash values
(e.g., on a CD-R that is kept secure).
 One can later determine if a file has been modified by
recomputing H(F).
 An intruder would need to change F without changing H(F).
 Two simple Hash Function
 The input (message, file, etc.) is viewed as a sequence of n-bit
blocks.
 The input is processed one block at a time in an iterative fashion
to produce an n-bit hash function.
 First Method

This operation produces a simple parity for each bit position and is known as a
longitudinal redundancy check.
 Two simple Hash Function
 Second Method
 Perform a one-bit circular shift, or rotation, on the hash value
after each block is processed.
 The procedure can be summarized as follows.
1. Initially set the n-bit hash value to zero.
2. Process each successive n-bit block of data as follows:
a. Rotate the current hash value to the left by one bit.
b. XOR the block into the hash value.

The second procedure provides a good measure of data integrity, it is virtually useless for
data security when an encrypted hash code is used with a plaintext message.
Requirement/Properties of Hash Function
 Requirement of Hash Function
 Properties – Variable input size and fixed output size
 Requirement of Hash Function
 Properties – Preimage Resistant (One Way Property)
 For a hash value h = H(x), we say that x is the preimage of h. That
is, x is a data block whose hash function, using the function H, is h.
 This property means that it should be computationally hard to
reverse a hash function.
 In other words, if a hash function h produced a hash value z,
then it should be a difficult process to find any input value x that
hashes to z.
 This property protects against an attacker who only has a hash
value and is trying to find the input.
 Requirement of Hash Function
Properties – secondary preimage Resistant (Weak Collision
Property)

 This property means It’s hard to find

an input that gives the same hash as a
certain other input.
 In other words, if a hash function h for
an input x produces hash value h(x),
then it should be difficult to find any
other input value y such that h(y) =
h(x).
 This property of hash function protects
against an attacker who has an input
value and its hash, and wants to
substitute different value as legitimate
value in place of original input value
 Requirement of Hash Function
Properties – Collision Resistance
 This property means it should be hard to find two different inputs of any
length that result in the same hash. This property is also referred to as
collision free hash function.
 In other words, for a hash function h, it is hard to find any two different
inputs x and y such that h(x) = h(y).
 Since, hash function is compressing function with fixed hash length, it is
impossible for a hash function not to have collisions. This property of collision
free only confirms that these collisions should be hard to find.
 This property makes it very difficult for an attacker to find two input values
with the same hash.
 Also, if a hash function is collision-resistant then it is second pre-image
resistant.
 Attack on Hash Function
 Brute force Attack
A) A preimage or second preimage attack
 An adversary wishes to find a value y such that H(y) is equal to a given hash value h.
 The brute-force method is to pick values of y at random and try each value until a
collision occurs.
 For an m-bit hash value, the level of effort is proportional to 2m.
 Specifically, the adversary would have to try, on average, 2m-1 values of y to find one
that generates a given hash value h.

B) Collision Resistance attack

 find two messages x & y with same hash so H(x) = H(y)

 The probability that any two numbers are same exceeds 0.5 after roughly about
square root of N trials.
 So for m bit hash function, there are 2m possible hash values, square root of 2m = 2(m/2).
Thus, 2(m/2) determines strength of hash code.
 Example: Birthday attack (two person have same birthdate)
 Attack on Hash Function
 Cryptanalysis
 cryptanalytic attacks on hash functions seek to exploit some property of the algorithm
to perform some attack other than an exhaustive search.
 To understand these, we need to look at the overall structure of a typical secure hash
function  Input message partitions into L
fixed-sized blocks of b bits
each. If necessary, the final
block is padded to b bits.
 The final block also includes
the value of the total length of
the input to the hash function
 The hash algorithm involves
repeated use of a compression
function, f, that takes two
inputs (an n-bit input from the
General Structure of Secure Hash Code previous step, and a b-bit
block) and produces an n-bit
output.
 Cryptanalysis of hash functions focuses on the internal
structure of f and is based on attempts to find efficient
techniques for producing collisions for a single execution
of f.
 Once that is done, the attack must take into account the
fixed value of IV.
Hash Function Based on Cipher Block Chaining
 A number of proposals have been made for hash functions based on using a
cipher block chaining technique, but without using the secret key.
 Rabin approach : Divide a message M into fixed-size blocks M1, M2, …, MN and
use a symmetric encryption system such as DES to compute the hash code G
as

 This is similar to the CBC technique, but in this case, there is no secret key.

 Resulting hash is too small (64-bit) hence following attack can possible
 birthday attack
 “meet-in-the-middle” attack

 other variants also susceptible to attack

 Secure Hash Algorithm (SHA)
 SHA was designed by US government standard agency NIST (national
institute of standards and technology)
 Types of SHA
 SHA-0: FIPS PUB 180, 1993
 SHA-1: FIPS Pub 180-1, 1995
 bitwise rotation of message schedule of SHA-0 changed
 widely-used security applications and protocols such as
 TLS and SSL, PGP, SSH, S/MIME, and IPsec
 SHA-2: FIPS Pub 180-2, 2001
 SHA-224, SHA-256, SHA-384, and SHA-512
 SHA-3 : was announced by NIST in October 2012
 Overview of SHA 512
Input message

The algorithm takes as

input a message with a
maximum length of less than
2128 bits
SHA-512
and produces as output a 512-
bit message digest.

512 bit
Message Digest
(hash value)
The input is processed in 1024-bit blocks.
 SHA 512 logic
Step 1: Append padding bits
Step 2: Append length
Step 3: Initialize hash buffer
Step 4: Process the message in 1024-bit (128-word) blocks, which
forms the heart of the algorithm
SHA-512
Step 5: Output the final state value as the resulting hash
Step 1: Append padding bits

SHA-512
 Step 1: Append padding bits
 The message is padded so that its length is congruent to 896
modulo 1024 [length  896(mod 1024)].
i.e. len mod 1024 = 896
(length of original message is added in last block in form of 128
bits)
SHA-512
 Padding is always added, even if the message is already of the
desired length.
 Thus, the number of padding bits is in the range of 1 to 1024.
 The padding consists of a single 1 bit followed by the necessary
number of 0 bits. (padding: 10000…)
 Step 1: Append padding bits
 Consider the input message =“abc”
 Represent in binary : 01100001 01100010 01100011
 Msg_len = 24bits
 Now, Msg_len mod 1024 = 896
hence 24 + 872 mod 1024= 896  pad 872 bits in message
such that Msg_len mod 1024 =SHA-512
896
 872 bits to be padded  1bit followed by 871 0’s
 So message now becomes as follows:
6162638000000000 0000000000000000 0000000000000000 0000000000000000
0000000000000000 0000000000000000 0000000000000000 0000000000000000
0000000000000000 0000000000000000 0000000000000000 0000000000000000
0000000000000000 0000000000000000
 Exercise
 How many bits you will pad for input message length of 2348
bits ?
 2348 mod 1024 =300 hence pad 596 bits to make it 896.
 Message length =2348 +596 = 2944
 Pad 128 bit length at end
 Total message length =SHA-512
3072 bits
 No of block = 3072/1024 = 3 block
 Step 2: Append length
 Pad the original length of message as 128bits at the end of
message.
 Msg_len = 24bits
 Hex value of 24 is 18.
 Message length represented in 128 bits in hexadecimal is
SHA-512
0000000000000000 0000000000000018
 Final message
6162638000000000 0000000000000000 0000000000000000 0000000000000000
0000000000000000 0000000000000000 0000000000000000 0000000000000000
0000000000000000 0000000000000000 0000000000000000 0000000000000000
0000000000000000 0000000000000000 0000000000000000 0000000000000018
SHA 512 overall design

SHA-512
 Step 3: Initialize the hash buffer
 The outcome of the first two steps yields a message that is an integer
multiple of 1024 bits in length.
 The expanded message is represented as the sequence of 1024-bit blocks M1,
M2, …, MN, so that the total length of the expanded message is N * 1024 bits.
 A 512-bit buffer is used to hold intermediate and final results of the hash
function.
 The buffer can be represented as eight 64-bit registers (a, b, c, d, e, f, g, h).
SHA-512
Step 4: Process message in 1024 (128-word) bit block

 The heart of the algorithm is a

module F that consists of 80
rounds.
 Message Schedule Module takes
1024 bits (16 words 0-15) as input
and generate 80 words as output
(0-79).
 Each round takes three input SHA-512
 Message word – 64bit
 Previous Hash buffer value -
512 bit
 Round constant (K) – 64bit
 Each round takes as input the 512-
bit buffer value, abcdefgh, and
updates the contents of the buffer.
Step 4: Process message in 1024 (128-word) bit block

 Each round also makes

use of an additive
constant Kt, where 0  t
 79 indicates one of
the 80 rounds.
 These words represent
the first 64 bits of the
fractional parts of the SHA-512
cube roots of the first
80 prime numbers.
 The constants provide a
“randomized” set of 64-
bit patterns, which
should eliminate any
regularities in the input
data
Step 4: Process message in 1024 (128-word) bit block

 The output of the

eightieth round is added
to the input to the first
round (Hi-1) to produce
Hi.

SHA-512
 Step 5: Output

 After all N 1024-bit blocks have been processed, the output from the Nth stage
is the 512-bit message digest.
 Hash Buffer Update
SHA 512 (Round Function) Operation
b=a
c=b
d=c
f=e
g=f
h=g
T2 T1 e = d + T1
a = T1 + T2
SHA 512 (Round Function)
Message Schedule : Create 80 words from Plaintext
Block
 Message Schedule : Create 80 words from Plaintext
Block

 The first 16 values of Wt are taken directly from the 16 words of the current block.
 The remaining values are defined as as a function of the earlier values using
ROTates, SHIFTs and XORs as shown
 Message Schedule : Create 80 words from Plaintext
Block
 For the remaining 64 steps, the value of Wt consists of the circular left
shift by one bit of the XOR of four of the preceding values of Wt,
with two of those values subjected to shift and rotate operations.
 This introduces a great deal of redundancy and interdependence
into the message blocks that are compressed, which complicates
the task of finding a different message block that maps to the same
compression function output.
 The SHA-512 algorithm has the property that every bit of the hash
code is a function of every bit of the input.
 The complex repetition of the basic function F produces results that are
well mixed; that is, it is unlikely that two messages chosen at random,
even if they exhibit similar regularities, will have the same hash code.
 Unless there is some hidden weakness in SHA-512, which has not so far
been published, the difficulty of coming up with two messages having the
same message digest is on the order of 2256 operations, while the
difficulty of finding a message with a given digest is on the order of 2512
operations.
 SHA-512: Example
 Input message =“abc”

 Binary form: 01100001 01100010 01100011

 Message After Padding:

6162638000000000 0000000000000000 0000000000000000 0000000000000000

0000000000000000 0000000000000000 0000000000000000 0000000000000000
0000000000000000 0000000000000000 0000000000000000 0000000000000000
0000000000000000 0000000000000000
 Final message : padding + length padding
6162638000000000 0000000000000000 0000000000000000 0000000000000000
0000000000000000 0000000000000000 0000000000000000 0000000000000000
0000000000000000 0000000000000000 0000000000000000 0000000000000000
0000000000000000 0000000000000000 0000000000000000 0000000000000018
 SHA-512: Example
Message Schedule - This block is assigned to the words W0, ….,W15 of the message
schedule, which appears as follows.
6162638000000000 0000000000000000 0000000000000000 0000000000000000
0000000000000000 0000000000000000 0000000000000000 0000000000000000
0000000000000000 0000000000000000 0000000000000000 0000000000000000
0000000000000000 0000000000000000 0000000000000000 0000000000000018
the eight 64-bit variables, a through h,
are initialized to values H0,0 through
H0,7.
The following table shows the initial
values of these variables and their
values after each of the first two
rounds.
After 1st round

After 2nd round

The process continues through 80 rounds. The output of the final round is

73a54f399fa4b1b2 10d9c4c4295599f6 d67806db8b148677 654ef9abec389ca9

d08446aa79693ed7 9bb4d39778c07f9e 25c96a7768fb2aa3 ceb9fc3691ce8326

The resulting 512-bit message digest is

ddaf35a193617aba cc417349ae204131 12e6fa4e89a97ea2 0a9eeee64b55d39a

2192992a274fc1a8 36ba3c23a3feebbd 454d4423643ce80e 2a9ac94fa54ca49f
Suppose now that we change the input message by one bit, from “abc” to “cbc.”
Then, the 1024-bit message block is
“cbc” message
6362638000000000 0000000000000000 0000000000000000 0000000000000000
0000000000000000 0000000000000000 0000000000000000 0000000000000000
0000000000000000 0000000000000000 0000000000000000 0000000000000000
0000000000000000 0000000000000000 0000000000000000 0000000000000018
The resulting 512-bit message digest is
531668966ee79b70 0b8e593261101354 4273f7ef7b31f279 2a7ef68d53f93264
319c165ad96d9187 55e6a204c2607e27 6e05cdf993a64c85 ef9e1e125c0f925f
Compare with “abc” message 512-bit message digest is
ddaf35a193617aba cc417349ae204131 12e6fa4e89a97ea2 0a9eeee64b55d39a
2192992a274fc1a8 36ba3c23a3feebbd 454d4423643ce80e 2a9ac94fa54ca49f

The number of bit positions that differ between the two hash values is 253,
almost exactly half the bit positions, indicating that SHA-512 has a good
avalanche effect
Difference between MAC and hash function
Difference between MAC and hash function