UNIT III

HASH FUNCTIONS AND DIGITAL SIGNATURES

Authentication requirement – Authentication function –

MAC – Hash function – Security of hash function and
MAC –MD5 - SHA - HMAC – CMAC - Digital signature
and authentication protocols – DSS – EI Gamal – Schnorr.

1
 Authentication Requirements
 Kind of attacks (threats) in the context of communications across a network
1. Disclosure
2. Traffic analysis
3. Masquerade
4. Content modification
5. Sequence modification
6. Timing modification
7. Repudiation
 Measures to deal with first two attacks:
– In the realm of message confidentiality, and are addressed with encryption
 Measures to deal with items 3 thru 6
– Message authentication
 Measures to deal with items 7
– Digital signature

2
 Authentication Requirements
• Message authentication
– A procedure to verify that messages come from the
alleged source and have not been altered
– Message authentication may also verify sequencing and
timeliness
• Digital signature
– An authentication technique that also includes
measures to counter repudiation by either source or
destination
3
 Authentication Functions

• Message authentication or digital signature mechanism can

be viewed as having two levels
– At lower level: there must be some sort of functions
producing an authenticator – a value to be used to
authenticate a message
– This lower level functions is used as primitive in a higher
level authentication protocol

4
 Authentication Functions
• Three classes of functions that may be used to produce an
authenticator
– Message encryption

• Cipher text itself serves as authenticator

– Message authentication code (MAC)

• A public function of the message and a secret key that

produces a fixed-length value that serves as the
authenticator
– Hash function

• A public function that maps a message of any length into a

5
fixed-length hash value, which serves as the authenticator
 Message Encryption
• Conventional encryption can serve as authenticator
– Conventional encryption provides authentication as well
as confidentiality
– Requires recognizable plaintext or other structure to
distinguish between well-formed legitimate plaintext and
meaningless random bits
• e.g., ASCII text, an appended checksum, or use of
layered protocols

6
Basic Uses of Message Encryption

7
 Ways of Providing Structure
• Append an error-detecting code (frame check sequence
(FCS)) to each message

8
 Ways of Providing Structure
• Suppose all the datagram's except the IP header is encrypted.

• If an opponent substituted some arbitrary bit pattern for the

encrypted TCP segment, the resulting plaintext would not include a
meaningful header

9
Confidentiality and Authentication Implications
of Message Encryption

10
 Message Authentication Code

• Uses a shared secret key to generate a fixed-size block of data

(known as a cryptographic checksum or MAC) that is appended
to the message

• MAC = CK(M)

• Assurances:

– Message has not been altered

– Message is from alleged sender

– Message sequence is unaltered (requires internal sequencing)

• Similar to encryption but MAC algorithm needs not be reversible

11
Basic Uses of MAC

12
Basic Uses of MAC

13
 Why Use MACs?

– i.e., why not just use encryption?

• Clear text stays clear
• MAC might be cheaper
• Broadcast
• Authentication of executable codes
• Architectural flexibility
• Separation of authentication check from message use

14
 Hash Function
• Converts a variable size message M into fixed size hash
code H(M) (Sometimes called a message digest)
• Can be used with encryption for authentication
– E(M || H)
– M || E(H)
– M || signed H
– E( M || signed H ) gives confidentiality
– M || H( M || K )
– E( M || H( M || K ) )
15
Basic Uses of Hash Function

16
Basic Uses of Hash Function

17
Basic Uses of Hash Function

18
 Message Authentication Code (MAC)
• generated by an algorithm that creates a small fixed-sized block

– depending on both message and some key

– like encryption though need not be reversible

• appended to message as a signature

• receiver performs same computation on message and checks it

matches the MAC
• provides assurance that message is unaltered and comes from
sender

19
 Message Authentication Code

 a small fixed-sized block of data

 generated from message + secret key
 MAC = C(K,M)
 appended to message when sent

20
 Message Authentication Codes
• as shown the MAC provides authentication

• can also use encryption for secrecy

– generally use separate keys for each

– can compute MAC either before or after encryption

– is generally regarded as better done before

• why use a MAC?

– sometimes only authentication is needed

– sometimes need authentication to persist longer than the

encryption (eg. archival use)
• note that a MAC is not a digital signature 21
 MAC Properties

• a MAC is a cryptographic checksum

MAC = CK(M)

– condenses a variable-length message M

– using a secret key K
– to a fixed-sized authenticator
• is a many-to-one function
– potentially many messages have same MAC
– but finding these needs to be very difficult
22
 Requirements for MACs
• taking into account the types of attacks
• need the MAC to satisfy the following:
1. knowing a message and MAC, is infeasible to find
another message with same MAC
2. MACs should be uniformly distributed
3. MAC should depend equally on all bits of the message

23
 Security of MACs
• like block ciphers have:
• brute-force attacks exploiting

– strong collision resistance hash have cost 2m/2

• 128-bit hash looks vulnerable, 160-bits better

– MACs with known message-MAC pairs
• can either attack keyspace (cf key search) or MAC
• at least 128-bit MAC is needed for security

24
 Security of MACs
• cryptanalytic attacks exploit structure
– like block ciphers want brute-force attacks to be the best
alternative
• more variety of MACs so harder to generalize about
cryptanalysis

25
 Hash Functions

• h = H(M)
• M is a variable-length message, h is a fixed-length hash
value, H is a hash function
• The hash value is appended at the source
• The receiver authenticates the message by recomputing the
hash value
• Because the hash function itself is not considered to be
secret, some means is required to protect the hash value

26
 Hash Function Requirements

1. H can be applied to any size data block

2. H produces fixed-length output

3. H(x) is relatively easy to compute for any given x

4. H is one-way, i.e., given h, it is computationally infeasible to

find any x s.t. h = H(x)
5. H is weakly collision resistant: given x, it is computationally
infeasible to find any y  x s.t. H(x) = H(y)
6. H is strongly collision resistant: it is computationally
infeasible to find any x and y s.t. H(x) = H(y)
27
 Hash Function Requirements

• One-way property is essential for authentication

• Weak collision resistance is necessary to prevent forgery
• Strong collision resistance is important for resistance to
birthday attack

28
 Simple Hash Functions
• Operation of hash functions

– The input 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
• Simplest hash function: Bitwise XOR of every block

– Ci = bi1  bi2  …  bim

• Ci = i-th bit of the hash code, 1  i  n

• m = number of n-bit blocks in the input

• bij = i-th bit in j-th block

– Known as longitudinal redundancy check

29
 Simple Hash Functions
• Improvement over the simple
bitwise XOR
– Initially set the n-bit hash value
to zero
– Process each successive n-bit
block of data as follows
» Rotate the current hash
value to the left by one bit
» XOR the block into the hash
value

30
 Birthday Attack
• If the adversary can generate 2m/2 variants of a valid message
and an equal number of fraudulent messages
• The two sets are compared to find one message from each set
with a common hash value
• The valid message is offered for signature

• The fraudulent message with the same hash value is inserted in

its place
• If a 64-bit hash code is used, the level of effort is only on the
order of 232
• Conclusion: the length of the hash code must be substantial
31
 Generating 2m/2 Variants of Valid Messages

• Insert a number of
“space-backspace-space”
character pairs between
words throughout the
document.
Variations could then be
generated by substituting
“space-backspace-space”
in selected instances
• Alternatively, simply
reword the message but
retain the meaning
32
 Security of Hash Functions and MACs
Brute-Force Attack of Hash Functions

• Three desirable properties of hash functions

– One-way: For any given code h, it is computationally
infeasible to find x s.t. H(x) = h
– Weak collision resistance: For any given block x, it is
computationally infeasible to find y  x s.t. H(y) =
H(x)
– Strong collision resistance: It is computationally
infeasible to find any pair (x, y) s.t. H(y) = H(x)

33
 Cntd..
• Brute-force attack on n-bit hash code

– One-way and weak collision require 2n effort

– Strong collision requires 2n/2 effort

–  If strong collision resistance is required (and this is

desirable for a general-purpose secure hash code), 2n/2
determines the strength of hash code against brute-force
attack
– Currently, two most popular hash codes, SHA-1 and
RIPEMD-160, provide a 160-bit hash code length
34
 Hash Function Cryptanalysis
 cryptanalytic attacks exploit some property of alg so faster
than exhaustive search
 hash functions use iterative structure

process message in blocks (incl length)
 attacks focus on collisions in function f

35
 MD5

• designed by Ronald Rivest (the R in RSA)

• latest in a series of MD2, MD4
• produces a 128-bit hash value
• until recently was the most widely used hash algorithm
– in recent times have both brute-force & cryptanalytic
concerns
• specified as Internet standard RFC1321

36
 MD5 Overview
1. pad message so its length is 448 mod 512
2. append a 64-bit length value to message
3. initialise 4-word (128-bit) MD buffer (A,B,C,D)
4. process message in 16-word (512-bit) blocks:
– using 4 rounds of 16 bit operations on message block &
buffer
– add output to buffer input to form new buffer value

5. output hash value is the final buffer value

37
MD5 Overview

38
 MD5 Compression Function
• each round has 16 steps of the form:

a = b+((a+g(b,c,d)+X[k]+T[i])<<<s)
• a,b,c,d refer to the 4 words of the buffer, but used in varying
permutations
– note this updates 1 word only of the buffer
– after 16 steps each word is updated 4 times
• where g(b,c,d) is a different nonlinear function in each round
(F,G,H,I)
• T[i] is a constant value derived from sin
39
MD5 Compression Function

40
 MD4

• precursor to MD5
• also produces a 128-bit hash of message
• has 3 rounds of 16 steps versus 4 in MD5
• design goals:
– collision resistant (hard to find collisions)
– direct security (no dependence on "hard" problems)
– fast, simple, compact
– favors little-endian systems (eg PCs)
41
 Strength of MD5

• MD5 hash is dependent on all message bits

• Rivest claims security is good as can be

• known attacks are:

– Berson 92 attacked any 1 round using differential cryptanalysis (but

can’t extend)
– Boer & Bosselaers 93 found a pseudo collision (again unable to
extend)
– Dobbertin 96 created collisions on MD compression function (but
initial constants prevent exploit)
• conclusion is that MD5 looks vulnerable soon
42
 Secure Hash Algorithm
 SHA originally designed by NIST & NSA in 1993
 was revised in 1995 as SHA-1
 US standard for use with DSA signature scheme

standard is FIPS 180-1 1995, also Internet RFC3174

nb. the algorithm is SHA, the standard is SHS
 based on design of MD4 with key differences
 produces 160-bit hash values
 2005 results on security of SHA-1 raised concerns on its use in
future applications 43
 Revised Secure Hash Standard

 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
44
SHA Versions

45
SHA-512 Overview

46
 SHA-512 Compression Function
 heart of the algorithm
 processing message in 1024-bit blocks
 consists of 80 rounds

updating a 512-bit buffer

using a 64-bit value Wt derived from the current message
block

and a round constant based on cube root of first 80 prime
numbers

47
SHA-512 Round Function

48
SHA-512 Round Function

49
 SHA-3
 SHA-1 not yet "broken”

but similar to broken MD5 & SHA-0

so considered insecure
 SHA-2 (esp. SHA-512) seems secure

shares same structure and mathematical operations as
predecessors so have concern
 NIST announced in 2007 a competition for the SHA-3 next
gen NIST hash function
 Keccak winner Oct 2012 – std in Q2,2014 50
 SHA-3 Requirements
 replace SHA-2 with SHA-3 in any use

so use same hash sizes
 preserve the online 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
51
 HMAC

• specified as Internet standard RFC2104

• uses hash function on the message:

HMACK = Hash[(K+ XOR opad) ||

Hash[(K+ XOR ipad)||M)]]

• where K+ is the key padded out to size

• and opad, ipad are specified padding constants

• overhead is just 3 more hash calculations than the message needs

alone
• any of MD5, SHA-1, RIPEMD-160 can be used
52
HMAC Overview

53
 HMAC Security
• know that the security of HMAC relates to that of the
underlying hash algorithm
• attacking HMAC requires either:
– brute force attack on key used
– birthday attack (but since keyed would need to observe a
very large number of messages)
• choose hash function used based on speed verses security
constraints

54
 CMAC

• previously saw the DAA (CBC-MAC)

• widely used in govt & industry
• but has message size limitation
• can overcome using 2 keys & padding
• thus forming the Cipher-based Message Authentication Code
(CMAC)
• adopted by NIST SP800-38B

55
CMAC Overview

56
 Digital Signatures
• have looked at message authentication
– but does not address issues of lack of trust
• digital signatures provide the ability to:
– verify author, date & time of signature
– authenticate message contents
– be verified by third parties to resolve disputes
• hence include authentication function with additional
capabilities

57
 Digital Signature Properties

• must depend on the message signed

• must use information unique to sender
– to prevent both forgery and denial
• must be relatively easy to produce
• must be relatively easy to recognize & verify
• be computationally infeasible to forge
– with new message for existing digital signature
– with fraudulent digital signature for given message
• be practical save digital signature in storage 58
 Direct Digital Signatures
• involve only sender & receiver
• assumed receiver has sender’s public-key
• digital signature made by sender signing entire message or
hash with private-key
• can encrypt using receivers public-key
• important that sign first then encrypt message & signature
• security depends on sender’s private-key

59
 Arbitrated Digital Signatures
• involves use of arbiter A
– validates any signed message
– then dated and sent to recipient
• requires suitable level of trust in arbiter
• can be implemented with either private or public-key
algorithms
• arbiter may or may not see message

60
 Authentication Protocols

• used to convince parties of each others identity and to

exchange session keys
• may be one-way or mutual
• key issues are
– confidentiality – to protect session keys
– timeliness – to prevent replay attacks

61
 Replay Attacks

• where a valid signed message is copied and later resent

– simple replay
– repetition that can be logged
– repetition that cannot be detected
– backward replay without modification
• countermeasures include
– use of sequence numbers (generally impractical)
– timestamps (needs synchronized clocks)
– challenge/response (using unique nonce) 62
 Using Symmetric Encryption

• as discussed previously can use a two-level hierarchy of keys

• usually with a trusted Key Distribution Center (KDC)
– each party shares own master key with KDC
– KDC generates session keys used for connections between
parties
– master keys used to distribute these to them

63
 Needham-Schroeder Protocol
• original third-party key distribution protocol
• for session between A B mediated by KDC
• protocol overview is:

1. A→KDC: IDA || IDB || N1

2. KDC→A: EKa[Ks || IDB || N1 || EKb[Ks||IDA] ]

3. A→B: EKb[Ks||IDA]

4. B→A: EKs[N2]

5. A→B: EKs[f(N2)]
64
 Needham-Schroeder Protocol

• used to securely distribute a new session key for

communications between A & B
• but is vulnerable to a replay attack if an old session key has
been compromised
– then message 3 can be resent convincing B that is
communicating with A
• modifications to address this require:
– timestamps (Denning 81)
– using an extra nonce (Neuman 93) 65
 Using Public-Key Encryption

• have a range of approaches based on the use of public-key

encryption
• need to ensure have correct public keys for other parties
• using a central Authentication Server (AS)
• various protocols exist using timestamps or nonces

66
 Denning AS Protocol

• Denning 81 presented the following:

1. A→AS: IDA || IDB

2. AS→A: EKRas[IDA||KUa||T] || EKRas[IDB||KUb||T]

3. A→B: EKRas[IDA||KUa||T] || EKRas[IDB||KUb||T] ||

EKUb[EKRas[Ks||T]]

• note session key is chosen by A, hence AS need not be trusted

to protect it
• timestamps prevent replay but require synchronized clocks
67
 One-Way Authentication

• required when sender & receiver are not in communications at

same time (eg. email)
• have header in clear so can be delivered by email system
• may want contents of body protected & sender authenticated

68
 Using Symmetric Encryption

• can refine use of KDC but can’t have final exchange of

nonces, vis:

1. A→KDC: IDA || IDB || N1

2. KDC→A: EKa[Ks || IDB || N1 || EKb[Ks||IDA] ]

3. A→B: EKb[Ks||IDA] || EKs[M]

• does not protect against replays

– could rely on timestamp in message, though email delays
make this problematic
69
 Public-Key Approaches
• have seen some public-key approaches
• if confidentiality is major concern, can use:

A→B: EKUb[Ks] || EKs[M]

– has encrypted session key, encrypted message

• if authentication needed use a digital signature with a digital
certificate:

A→B: M || EKRa[H(M)] || EKRas[T||IDA||KUa]

– with message, signature, certificate

70
 Digital Signature Standard (DSS)
• US Govt approved signature scheme

• designed by NIST & NSA in early 90's

• published as FIPS-186 in 1991

• revised in 1993, 1996 & then 2000

• uses the SHA hash algorithm

• DSS is the standard, DSA is the algorithm

• FIPS 186-2 (2000) includes alternative RSA & elliptic curve

signature variants
• DSA is digital signature only unlike RSA

• is a public-key technique 71
DSS vs RSA Signatures

72
 Digital Signature Algorithm (DSA)

 creates a 320 bit signature

 with 512-1024 bit security
 smaller and faster than RSA
 a digital signature scheme only
 security depends on difficulty of computing discrete
logarithms
 variant of ElGamal & Schnorr schemes

73
 DSA Key Generation
• have shared global public key values (p,q,g):

– choose 160-bit prime number q

– choose a large prime p with 2L-1 < p < 2L

• where L= 512 to 1024 bits and is a multiple of 64

• such that q is a 160 bit prime divisor of (p-1)

– choose g = h(p-1)/q

• where 1<h<p-1 and h(p-1)/q mod p > 1

• users choose private & compute public key:

– choose random private key: x<q

– compute public key: y = gx mod p 74

 DSA Signature Creation

 to sign a message M the sender:

• generates a random signature key k, k<q

• nb. k must be random, be destroyed after use, and never be
reused
 then computes signature pair:

r = (gk mod p)mod q

s = [k-1(H(M)+ xr)] mod q
 sends signature (r,s) with message M
75
 DSA Signature Verification
• having received M & signature (r,s)
• to verify a signature, recipient computes:

w = s-1 mod q
u1= [H(M)w ]mod q
u2= (rw)mod q
v = [(gu1 yu2)mod p ]mod q
• if v=r then signature is verified
• see Appendix A for details of proof why
76
DSS Overview

77
 ElGamal Digital Signatures

• signature variant of ElGamal, related to D-H

– so uses exponentiation in a finite (Galois)

– with security based difficulty of computing discrete logarithms,

as in D-H
• use private key for encryption (signing)

• uses public key for decryption (verification)

• each user (eg. A) generates their key

– chooses a secret key (number): 1 < x A < q-1

xA
– compute their public key: yA = a mod q 78
 ElGamal Digital Signature
• Alice signs a message M to Bob by computing

– the hash m = H(M), 0 <= m <= (q-1)

– chose random integer K with 1 <= K <= (q-1) and gcd(K,q-1)=1
k
– compute temporary key: S1 = a mod q

– compute K-1 the inverse of K mod (q-1)

– compute the value: S2 = K-1(m-xAS1) mod (q-1)

– signature is:(S1,S2)

• any user B can verify the signature by computing

m
– V1 = a mod q

– V2 = yAS1 S1S2 mod q

– signature is valid if V1 = V2 79
 ElGamal Signature Example
• use field GF(19) q=19 and a=10

• Alice computes her key:

16
– A chooses xA=16 & computes yA=10 mod 19 = 4

• Alice signs message with hash m=14 as (3,4):

– choosing random K=5 which has gcd(18,5)=1

5
– computing S1 = 10 mod 19 = 3

– finding K-1 mod (q-1) = 5-1 mod 18 = 11

– computing S2 = 11(14-16.3) mod 18 = 4

• any user B can verify the signature by computing

14
– V1 = 10 mod 19 = 16

– V2 = 43.34 = 5184 = 16 mod 19

80
– since 16 = 16 signature is valid
 Schnorr Digital Signatures

• also uses exponentiation in a finite (Galois)

– security based on discrete logarithms, as in D-H
• minimizes message dependent computation
– multiplying a 2n-bit integer with an n-bit integer
• main work can be done in idle time
• have using a prime modulus p
– p–1 has a prime factor q of appropriate size
– typically p 1024-bit and q 160-bit numbers
81
 Schnorr Key Setup
• choose suitable primes p , q

• choose a such that aq = 1 mod p

• (a,p,q) are global parameters for all

• each user (eg. A) generates a key

– chooses a secret key (number): 0 < sA < q

-sA
– compute their public key: vA = a mod q

82
 Schnorr Signature
• user signs message by
– choosing random r with 0<r<q and computing x = ar mod p
– concatenate message with x and hash result to computing: e =
H(M || x)
– computing: y = (r + se) mod q
– signature is pair (e, y)
• any other user can verify the signature as follows:
– computing: x' = ayve mod p
– verifying that: e = H(M || x’)

83