Cryptographic Hash Functions

by M.K.Chavan

1
Topics
 Overview of Cryptography Hash Function
 Usages
 Properties
 Hashing Function Structure
 Attack on Hash Function
 The Road to new Secure Hash Standard

2
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)

3
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’

4
Motivation for Hash Algorithms
 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

5
Hash Function Applications
 Used Alone
 Fingerprint -- file integrity verification
 Password storage (one-way encryption)

 Combined with encryption functions

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

6
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

7
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

8
Topics
 Overview of Cryptography Hash Function
 Usages
 Properties
 Hashing Function Structure
 Attack on Hash Function
 The Road to new Secure Hash Standard

9
Hash Function Usages (I)

Message encrypted : Confidentiality and authentication

Message unencrypted: Authentication

10
Hash Function Usages (II)

Message encrypted : Authentication (no encryption needed!)

Message unencrypted: Authentication, confidentiality

11
Hash Function Usages (III)

Authentication, digital signature

Authentication, digital signature, confidentiality

12
Topics
 Overview of Cryptography Hash Function
 Usages
 Properties
 Hashing Function Structure
 Attack on Hash Function
 The Road to new Secure Hash Standard

13
Hash Function Properties
 Arbitrary-length message to fixed-length digest

 Preimage resistant (One-way property)

 Collision resistant (Strong collision resistance)

14
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

15
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.
16
Collision Resistant

 Can’t find any two different messages with the same message digest
 Collision resistance implies second preimage resistance
 Collisions, if we could find them, would give signatories a way to repudiate their signatures

17
Topics
 Overview of Cryptography Hash Function
 Usages
 Properties
 Hashing Function Structure
 Attack on Hash Function
 The Road to new Secure Hash Standard

18
Two Group of Compression Functions
 The compression function is made from scratch
 Message Digest

 A symmetric-key block cipher serves as a compression

function
 Whirlpool

19
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
20
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

21
MD5, SHA-1, and RIPEMD-160

22
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
 Practical Collision MD5 has been broken since 2004
 CA attack published in 2007

23
Topics
 Overview of Cryptography Hash Function
 Usages
 Properties
 Hashing Function Structure
 MD5
 SHA
 Attack on Hash Function
 The Road to new Secure Hash Standard

24
Topics
 Overview of Cryptography Hash Function
 Usages
 Properties
 Hashing Function Structure
 MD5
 SHA
 Attack on Hash Function
 The Road to new Secure Hash Standard

25
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

26
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

27
 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

28
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

29
SHA-512 Overview

30
Padding and length field in SHA-512

 What is the number of padding bits if the length of the original message
is 2590 bits?
 We can calculate the number of padding bits as follows:

 The padding consists of one 1 followed by 353 0’s.

31
SHA-512 Round Function

32
Topics
 Overview of Cryptography Hash Function
 Usages
 Properties
 Hashing Function Structure
 MD5
 SHA

33
Hash Function Cryptanalysis
➢ cryptanalytic attacks exploit some property of algorithm
so faster than exhaustive search
➢ hash functions use iterative structure
⚫ process message in blocks (incl length)
➢ attacks focus on collisions in function f

34
Attacks on Hash Functions
➢ brute-force attacks and cryptanalysis
➢ cryptanalytic attacks exploit some property of algorithm so
faster than brute-force
➢ a preimage or second preimage attack
⚫ find y such that H(y)equals a given hash value
➢ collision resistance
⚫ find two messages x & y with same hash so H(x) = H(y)

"md5 and sha1 are both clearly broken (in terms of collision-resistance”
Ron Rivest

http://mail.python.org/pipermail/python-dev/2005-December/058850.html

35
Topics
 Overview of Cryptography Hash Function
 Usages
 Properties
 Hashing Function Structure
 MD5
 SHA
 Attack on Hash Function
 The Road to new Secure Hash Standard

36
The need of new Hash standard
➢ MD5 should be considered cryptographically broken and
unsuitable for further use, US CERT 2010
➢ In 2004, a collision for the full SHA-0 algorithm was
announced

➢ SHA-1 not yet fully “broken”

⚫ but similar to the broken MD5 & SHA-0
⚫ so considered insecure and be fade out
➢ SHA-2 (esp. SHA-512) seems secure
⚫ shares same structure and mathematical operations as
predecessors so have concern
37
 SHA-3 Requirements
➢ NIST announced in 2007 a competition for the SHA-3 next
gen hash function
 Replace SHA-2 with SHA-3 in any use
 so use same hash sizes
 preserve the nature of SHA-2
 so must process small blocks (512 / 1024 bits)
 evaluation criteria
 security close to theoretical max for hash sizes
 cost in time & memory
 characteristics: such as flexibility & simplicity

38
Timeline Competition
 Nov 2007: Announce public competition
 Oct 2008: 64 Entries
 Dec 2008: 51 Entries as 1st Round
 Jul 2009: 14 Entries as 2nd Round
 Dec 2010: 5 Entries as 3rd Round
 Jan 2011: Final packages submission and enter public
comments
 2012: SHA-3 winner announcement (Still in progress)

39
Five SHA-3 Finalists

 BLAKE
 Grøstl
 JH
 Keccak
 Skien
http://csrc.nist.gov/groups/ST/hash/sha-3/Round3/submissions_rnd3.html

40
Secure Hash Algorithm-512 (SHA-512)

M.K.Chavan

41 November 30, 2022

 Outlines
❑ SHA-512 overview
❑ processing of SHA-521
❑ word expansion
❑ compression function
❑ round function
❑ additive constants
❑ example using SHA-512
❑ applications
❑ cryptanalysis

42 November 30, 2022

Secure Hash Algorithm-512
(SHA-512)

November 30, 2022 43

 Outlines
❑ SHA-512 overview
❑ processing of SHA-521
❑ word expansion
❑ compression function
❑ round function
❑ additive constants
❑ example using SHA-512
❑ applications
❑ cryptanalysis

November 30, 2022

44
 Overview


November 30, 2022

45
 Processing of SHA-512

Figure: SHA-512 Processing of a Single 1024-Bit Block 46

Message block and digest word

Figure: A message block and the digest as words

Figure: Padding and length field

November 30, 2022 47
 Processing of SHA-512
❑ appending padding and fixed 128 bit length field
❑ dividing the augmented message into blocks
❑ using a 64-bit word derived from the current message
block
❑ using 8 constants based on square root of first 8 prime
numbers (2-19)
❑ updating a 512-bit buffer
❑ using a round constant based on cube root of first 80
prime numbers (2-409)

November 30, 2022 48

 Message block and digest word
❑ operates on words
❑ each block consists of sixteen 64 bits(1024 bits)
words
❑ message digest has eight 64 bits (512 bits) words
named A,B,C,D,E,F,G,H
❑ expanding 80 words from sixteen 64 bits words

November 30, 2022 49

 SHA-512 Initial Values & Word Expansion
Buffer Value (in Hexadecimal) Buffer Value (in Hexadecimal)
A0 6A09E667F3BCC908 E0 510E527FADE682D1
B0 BB67AE8584CAA73B F0 9B05688C2B3E6C1F
C0 3C6EF372FE94F82B G0 1F83D9ABFB41BD6B
D0 A54FF53A5F1D36F1 H0 5BE0CD19137E2179

Table : Values of constants in message digest initialization of SHA-512

Figure: Word expansion in SHA-512 50

 Calculation of constants


The fraction part: (6C44198C4A475817)16

November 30, 2022 51
SHA-512 Compression Function

Figure: Compression Function in SHA-512 52

SHA-512 Round constants (K)

Figure: List of round constants used in SHA-512

53
 SHA-512 Round Function

54
Figure: Structure of each round in SHA-512
SHA-512 Round Function
Majority Function

Conditional Function

Rotate Functions

November 30, 2022 55

 SHA-512 Majority Function calculation
❑ We apply the Majority function on buffers A, B, and C. If
the leftmost hexadecimal digits of these buffers are 0x7,
0xA, and 0xE, respectively, what is the leftmost digit of
the result?
Solution

The digits in binary are 0111, 1010, and 1110.

a. The first bits are 0, 1, and 1. The majority is 1.
b. The second bits are 1, 0, and 1. The majority is 1.
c. The third bits are 1, 1, and 1. The majority is 1.
d. The fourth bits are 1, 0, and 0. The majority is 0.

The result is 1110, or 0xE in hexadecimal.

November 30, 2022 56
 SHA-512 Conditional Function calculation

❑ We apply the Conditional function on E, F, and G

buffers. If the leftmost hexadecimal digits of these
buffers are 0x9, 0xA, and 0xF respectively, what is the
leftmost digit of the result?
Solution

The digits in binary are 1001, 1010, and 1111.

a. The first bits are 1, 1,and 1.The result is F1, which is 1.
b. The second bits are 0,0, and 1. The result is G2, which
is 1.
c. The third bits are 0,1,and 1.The result is G3, which is 1.
d. The fourth bits are 1,0,and 1.The result is F4, which is 0.
The result is 1110, or 0xE in hexadecimal.
November 30, 2022 57
 Example using SHA-512
ASCII characters: “abc”, which is equivalent to the following 24-bit binary string:

01100001 01100010 01100011 = 616263 in Hexadecimal

The original length is 24 bits, or a hexadecimal value of 18.

the 1024-bit message block, in hexadecimal, is

6162638000000000 0000000000000000 0000000000000000 0000000000000000

0000000000000000 0000000000000000 0000000000000000 0000000000000000
0000000000000000 0000000000000000 0000000000000000 0000000000000000
0000000000000000 0000000000000000 0000000000000000 0000000000000018

W0 = 6162638000000000 W5 = 0000000000000000
W1 = 0000000000000000 W6 = 0000000000000000
W2 = 0000000000000000 W7 = 0000000000000000
W3 = 0000000000000000 W8 = 0000000000000000
W4 = 0000000000000000 W9 = 0000000000000000
W10 = 0000000000000000 W13 = 0000000000000000
W11 = 0000000000000000 W14 = 0000000000000000
W12 = 0000000000000000 W15 = 0000000000000018
November 30, 2022 58
 Example using SHA-512
The following table shows the initial values of these variables and their values after
each of the first two rounds.
a 6a09e667f3bcc908 f6afceb8bcfcddf5 1320f8c9fb872cc0
b bb67ae8584caa73b 6a09e667f3bcc908 f6afceb8bcfcddf5
c 3c6ef372fe94f82b bb67ae8584caa73b 6a09e667f3bcc908
d a54ff53a5f1d36f1 3c6ef372fe94f82b bb67ae8584caa73b
e 510e527fade682d1 58cb02347ab51f91 c3d4ebfd48650ffa
f 9b05688c2b3e6c1f 510e527fade682d1 58cb02347ab51f91
g 1f83d9abfb41bd6b 9b05688c2b3e6c1f 510e527fade682d1
h 5be0cd19137e2179 1f83d9abfb41bd6b 9b05688c2b3e6c1f

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

73a54f399fa4b1b2 10d9c4c4295599f6 d67806db8b148677 654ef9abec389ca9

d08446aa79693ed7 9bb4d39778c07f9e 25c96a7768fb2aa3 ceb9fc3691ce8326

59
 Example using SHA-512

The hash value is then calculated as

H1,7 = 5be0cd19137e2179 + ceb9fc3691ce8326 = 2a9ac94fa54ca49f

H1,6 = 1f83d9abfb41bd6b + 25c96a7768fb2aa3 = 454d4423643ce80e
H1,5 = 9b05688c2b3e6c1f + 9bb4d39778c07f9e = 36ba3c23a3feebbd
H1,4 = 510e527fade682d1 + d08446aa79693ed7 = 2192992a274fc1a8
H1,3 = a54ff53a5f1d36f1 + 654ef9abec389ca9 = 0a9eeee64b55d39a
H1,2 = 3c6ef372fe94f82b + d67806db8b148677 = 12e6fa4e89a97ea2
H1,1 = bb67ae8584caa73b + 10d9c4c4295599f6 = cc417349ae204131
H1,0 = 6a09e667f3bcc908 + 73a54f399fa4b1b2 = ddaf35a193617aba

The resulting 512-bit message digest is

ddaf35a193617aba cc417349ae204131 12e6fa4e89a97ea2 0a9eeee64b55d39a

2192992a274fc1a8 36ba3c23a3feebbd 454d4423643ce80e 2a9ac94fa54ca49f

60
 SHA-512 Applications

❑ Used as part of a system to authenticate archival

video from the International Criminal Tribunal of the
Rwandan genocide.
❑ Proposed for use in DNSSEC
❑ are moving to 512-bit SHA-2 for secure password
hashing by Unix and Linux vendors

61
 SHA-512 Cryptanalysis
Published in Year Attack method Rounds
New Collision Attacks Against
2008 Deterministic 24/80
Up To 24-step SHA-2
Preimages for step-reduced Meet-in-the- 42/80
2009
SHA-2 middle 46/80
Advanced meet-in-the-middle Meet-in-the-
2010 42/80
preimage attacks middle
Bicliques for Preimages: Attacks 50/80
on 2011 Biclique
57/80
Skein-512 and the SHA-2 family
Branching Heuristics in
Heuristic
Differential Collision Search with 2014 38/80
differential
Applications to SHA-512

62
Summary
 Hash functions are keyless
 Applications for digital signatures and in message authentication codes
 The three security requirements for hash functions are
 one-wayness 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
 SHA-3 (Secure Hash Algorithm 3) is the latest member of
the Secure Hash Algorithm family of standards, released
by NIST on August 5, 2015

63
Authentication
Applications

64
 Outline
• Security Concerns
• Kerberos
• X.509 Authentication Service
• Recommended reading and Web Sites

65
 KERBEROS

In Greek mythology, a many headed dog,

the guardian of the entrance of Hades
66
 KERBEROS
• Users wish to access services on
servers.
• Three threats exist:
– User pretend to be another user.
– User alter the network address of a
workstation.
– User eavesdrop on exchanges and use a
replay attack.
67
 KERBEROS
• Provides a centralized authentication
server to authenticate users to
servers and servers to users.
• Relies on conventional encryption,
making no use of public-key
encryption
• Two versions: version 4 and 5
• Version 4 makes use of DES
68
 Kerberos Version 4
• Terms:
– C = Client
– AS = authentication server
– V = server
– IDc = identifier of user on C
– IDv = identifier of V
– Pc = password of user on C
– ADc = network address of C
– Kv = secret encryption key shared by AS an V
– TS = timestamp
– || = concatenation 69
 A Simple Authentication
Dialogue
(1) C  AS: IDc || Pc || IDv
(2) AS  C: Ticket
(3) C  V: IDc || Ticket

Ticket = EKv[IDc || Pc || IDv]

70
Overview of Kerberos

71
Request for Service in
Another Realm

72
 Difference Between
Version 4 and 5
• Encryption system dependence (V.4 DES)
• Internet protocol dependence
• Message byte ordering
• Ticket lifetime
• Authentication forwarding
• Interrealm authentication

73
Kerberos Encryption Techniques

74
PCBC Mode

75
 Kerberos - in practice
• Currently have two Kerberos versions:
• 4 : restricted to a single realm
• 5 : allows inter-realm authentication, in beta test
• Kerberos v5 is an Internet standard
• specified in RFC1510, and used by many utilities
• To use Kerberos:
• need to have a KDC on your network
• need to have Kerberised applications running on all
participating systems
• major problem - US export restrictions
• Kerberos cannot be directly distributed outside the
US in source format (& binary versions must obscure
crypto routine entry points and have no encryption)
• else crypto libraries must be reimplemented locally
76
 X.509 Authentication
Service
• Distributed set of servers that
maintains a database about users.
• Each certificate contains the public
key of a user and is signed with the
private key of a CA.
• Is used in S/MIME, IP Security,
SSL/TLS and SET.
• RSA is recommended to use.
77
X.509 Formats

78
Typical Digital Signature
Approach

79
 Obtaining a User’s
Certificate
• Characteristics of certificates
generated by CA:
– Any user with access to the public key of
the CA can recover the user public key
that was certified.
– No part other than the CA can modify
the certificate without this being
detected.

80
X.509 CA Hierarchy

81
 Revocation of Certificates
• Reasons for revocation:
– The users secret key is assumed to be
compromised.
– The user is no longer certified by this
CA.
– The CA’s certificate is assumed to be
compromised.

82
Authentication Procedures

83
 Recommended Reading and
WEB Sites
• www.whatis.com (search for kerberos)
• Bryant, W. Designing an Authentication
System: A Dialogue in Four Scenes.
http://web.mit.edu/kerberos/www/dialogue.html
• Kohl, J.; Neuman, B. “The Evolotion of
the Kerberos Authentication Service”
http://web.mit.edu/kerberos/www/papers.html
• http://www.isi.edu/gost/info/kerberos/
84