Cryptography and Network Security (CNS)

UNIT-IV:
Cryptographic Hash Functions

Dr. Dwiti Krishna Bebarta

Hash Function

 The hash value represents

concisely the longer message
 may called the message digest

 A message digest is as a
``digital fingerprint'' of the
original document

condenses arbitrary message to fixed size

h = H(M)

2
Hashing V.S. Encryption
Hello, world. k NhbXBsZSBzZW50ZW5jZS
A sample sentence to E B0byBzaG93IEVuY3J5cHR
show encryption. pb24KsZSBzZ

Hello, world. k
NhbXBsZSBzZW50ZW5jZS
A sample sentence to D
B0byBzaG93IEVuY3J5cHR
show encryption. pb24KsZSBzZ

 Encryption is two way, and requires a key to encrypt/decrypt

This is a clear text that

can easily read without 52f21cf7c7034a20
using the key. The
h 17a21e17e061a863
sentence is longer than
the text above.

 Hashing is one-way. There is no 'de-hashing’

Motivation for Hash Algorithms
 Intuition
 Limitation on non-cryptographic checksum
 Very possible to construct a message that matches the
checksum
 Goal
 Design a code where the original message can not be inferred
based on its checksum
 such that an accidental or intentional change to the message
will change the hash value
Hash Function Applications
 Used Alone
 Fingerprint -- file integrity verification, public key fingerprint
 Password storage (one-way encryption)

 Combined with encryption functions

 Hash based Message Authentication Code (HMAC)
 protects both a message's integrity and confideltaility
 Digital signature
 Ensuring Non-repudiation
 Encrypt hash with private (signing) key and verify with public
(verification) key
Integrity

 to create a one-way password file

 store hash of password not actual password
 for intrusion detection and virus detection
 keep & check hash of files on system
Password Verification
Store Hashing Password Verification an input password against the stored hash

Iam#4VKU Iam#4VKU
Password
store

h h

661dce0da2bcb2d8 661dce0da2bcb2d8 661dce0da2bcb2d8

2884e0162acf8194 2884e0162acf8194 2884e0162acf8194

Hash Matching
Exactly?
Password
Yes No
store Deny
Grant
Topics
 Overview of Cryptography Hash Function
 Usages
 Properties
 Hashing Function Structure
 Attack on Hash Function
 The Road to new Secure Hash Standard
Hash Function Usages (Symmetric Key Cryptosystem)

Message encrypted : Confidentiality and authentication

Message unencrypted: Authentication

Hash Function Usages (Public Key Cryptosystem

Authentication, digital signature

Authentication, digital signature, confidentiality

Topics
 Overview of Cryptography Hash Function
 Usages
 Properties
 Hashing Function Structure
 Attack on Hash Function
 The Road to new Secure Hash Standard
Hash Function Properties
 Arbitrary-length message to fixed-length digest

 Preimage resistant (One-way property)

 Second preimage resistant (Weak collision resistant)

 Collision resistant (Strong collision resistance)

Properties : Fixed length

Hello, world 661dce0da2bcb2d8

h 2884e0162acf8194

Fixed length L
This is a clear text that
can easily read without
52f21cf7c7034a20
using the key. The h
17a21e17e061a863
sentence is longer than
the text above.

 Arbitrary-length message to fixed-length digest

Preimage resistant
 This measures how difficult to devise a message which hashes to the
known digest
 Roughly speaking, the hash function must be one-way.

Given only a message digest, can’t find any message

(or preimage) that generates that digest.
Second preimage resistant
 This measures how difficult to devise a message which hashes to the
known digest and its message

 For a given message x1, it is hard to find a second

message x2≠x1 with H(x1)=H(x2).
Collision Resistant

 It is hard to find a pair of messages x1≠x2 with H(x1)=H(x2).

Topics
 Overview of Cryptography Hash Function
 Usages
 Properties
 Hashing Function Structure
 Attack on Hash Function
 The Road to new Secure Hash Standard
Merkle-Damgard Scheme

 Well-known method to build cryptographic hash function

 A message of arbitrary length is broken into blocks
 length depends on the compression function f
 padding the size of the message into a multiple of the block size.
 sequentially process blocks , taking as input the result of the hash so far and the current
message block, with the final fixed length output
Hash Functions Family
 MD (Message Digest)
 Designed by Ron Rivest
 Family: MD2, MD4, MD5
 SHA (Secure Hash Algorithm)
 Designed by NIST
 Family: SHA-0, SHA-1, and SHA-2
 SHA-2: SHA-224, SHA-256, SHA-384, SHA-512
 SHA-3: New standard in competition

 RIPEMD (Race Integrity Primitive Evaluation Message

Digest)
 Developed by Katholieke University Leuven Team
 Family : RIPEMD-128, RIPEMD-160, RIPEMD-256, RIPEMD-320
MD5, SHA-1, and RIPEMD-160

20
 Little and Big Endian Mystery
Little and big endian are two ways of storing multibyte data-types ( int, float,
etc).
In little endian machines, last byte of binary representation of the multibyte
data-type is stored first.
In big endian machines, first byte of binary representation of the multibyte
data-type is stored first.
Suppose integer is stored as 4 bytes (For those who are using DOS-based
compilers such as C++ 3.0, integer is 2 bytes) then a variable x with value
0x01234567 will be stored as following.
MD2, MD4 and MD5
 Family of one-way hash functions by Ronald Rivest
 All produces 128 bits hash value
 MD2: 1989
 Optimized for 8 bit computer
 Collision found in 1995
 MD4: 1990
 Full round collision attack found in 1995
 MD5: 1992
 Specified as Internet standard in RFC 1321
 since 1997 it was theoretically not so hard to create a collision
 Practical Collision MD5 has been broken since 2004
 CA attack published in 2007
MD5 Overview

2. Append
length
(64bits)

1. Append padding
bits
(to 448 mod 512)

3. Initialize MD buffer (4x32 bits Word)

Word A = 01 23 45 67
Word B = 89 AB CD EF
Word C = FE DC BA 98
Word D = 76 54 32 10
Hash Algorithm Design – MD5

16 steps

X[k] = M [q*16+k] (32 bit)

Constructed from sine function

The ith 32-bit word in matrix T, constructed from the sine function

M [q*16+k] = the kth 32-bit word from the qth 512-bit block of the msg

Single step
Working of the MD5 Algorithm:
MD5 algorithm follows the following steps
Append Padding Bits: In the first step, we add padding bits in the original
message in such a way that the total length of the message is 64 bits less than the
exact multiple of 512.
Suppose we are given a message of 1000 bits. Now we have to add padding bits
to the original message. Here we will add 472 padding bits to the original
message. After adding the padding bits the size of the original message/output of
the first step will be 1472 i.e. 64 bits less than an exact multiple of 512 (i.e. 512*3 =
1536).
Length(original message + padding bits) = 512 * i – 64 where i = 1,2,3 . . .
Initialize MD buffer: Here, we use the 4 buffers i.e. J, K, L,
and M. The size of each buffer is 32 bits.
- J = 0x67425301
- K = 0xEDFCBA45
- L = 0x98CBADFE
- M = 0x13DCE476

B = (((((A+g(B,C,D) + x[k]) + T[i]) <<< S) + B)

 Process Each 512-bit Block: This is the most important
step of the MD5 algorithm. Here, a total of 64 operations
are performed in 4 rounds. We apply a different function
on each round i.e. for the 1st round we apply the F
function, for the 2nd G function, 3rd for the H function,
and 4th for the I function.
We perform OR, AND, XOR, and NOT (basically these are
logic gates) for calculating functions. We use 3 buffers for
each function i.e. K, L, M.
 - F(K,L,M) = (K AND L) OR (NOT K AND M) - G(K,L,M) = (K
AND L) OR (L AND NOT M) - H(K,L,M) = K XOR L XOR M -
I(K,L,M) = L XOR (K OR NOT M)
Topics
 Overview of Cryptography Hash Function
 Usages
 Properties
 Hashing Function Structure
 MD5
 SHA
 Attack on Hash Function
 The Road to new Secure Hash Standard
Secure Hash Algorithm
 SHA originally designed by NIST & NSA in 1993
 revised in 1995 as SHA-1
 US standard for use with DSA signature scheme
 standard is FIPS 180-1 1995, also Internet RFC3174
 based on design of MD4 with key differences
 produces 160-bit hash values
 recent 2005 results on security of SHA-1 have raised concerns
on its use in future applications
Revised SHA
 NIST issued revision FIPS 180-2 in 2002
 adds 3 additional versions of SHA
 SHA-256, SHA-384, SHA-512
 designed for compatibility with increased security
provided by the AES cipher
 structure & detail is similar to SHA-1
 hence analysis should be similar
 but security levels are rather higher
 SHA Versions

MD5 SHA-0 SHA-1 SHA-224 SHA-256 SHA-384 SHA-512

Digest size 128 160 160 224 256 384 512

Message size 264-1 264-1 264-1 264 -1 264-1 2128-1 2128-1

Block size 512 512 512 512 512 1024 1024
Word size 32 32 32 32 32 64 64
# of steps 64 64 80 64 64 80 80

Full collision found

Sample Processing

Type bits data processed

MD5 128 469.7 MB/s
SHA-1 160 339.4 MB/s
SHA-512 512 177.7 MB/s

 Mac Intel 2.66 Ghz core i7

 1024 bytes block of data
SHA-512
 Introduction
Message digest creation SHA-512
SHA-512 Round Function
Summary
 Hash functions are keyless
 Applications for digital signatures and in message authentication codes
 The three security requirements for hash functions are
 one-wayness, second preimage resistance and collision resistance
 MD5 and SHA-0 is insecure
 Serious security weaknesses have been found in SHA-1
 should be phased out
 SHA-2 appears to be secure
 May use SHA-512 and use the first 256 bytes
 The ongoing SHA-3 competition will result in new standardized
hash functions in a next year