UNIT-4

Cryptographic Hash Functions & Digital Signature

Hash Functions:
 condenses arbitrary message to fixed size

h = H(M)

 usually assume hash function is public

 hash used to detect changes to message

 want a cryptographic hash function

 computationally infeasible to find data mapping to specific hash (one-way

property)

 computationally infeasible to find two data to same hash (collision-free

property)

Hash Function Uses:

 Message Integrity Check (MIC)

 send hash of message (digest)

 MIC always encrypted, message optionally

 Message Authentication Code (MAC)

 send keyed hash of message

 MAC, message optionally encrypted

 Digital Signature (non-repudiation)

 Encrypt hash with private (signing) key

 Verify with public (verification) key

Hash Function Requirements:

Attacks on Hash Functions:

 have brute-force attacks and cryptanalysis

 a preimage or second preimage attack

 find y s.t. H(y) equals a given hash value

 collision resistance

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

 hence value 2m/2 determines strength of hash code against brute-force attacks

 128-bits inadequate, 160-bits suspect

Birthday Attacks:

 might think a 64-bit hash is secure

 but by Birthday Paradox is not

 birthday attack works thus:

 given user prepared to sign a valid message x

 opponent generates 2m/2 variations x’ of x, all with essentially the same meaning,
and saves them

 opponent generates 2m/2 variations y’ of a desired fraudulent message y

 two sets of messages are compared to find pair with same hash (probability > 0.5
by birthday paradox)

 have user sign the valid message, then substitute the forgery which will have a
valid signature

 conclusion is that need to use larger MAC/hash

 What are chances we get a match?

 N distinct values, k randomly chosen ones

 P(N,i) = prob(i randomly selected values from 1..N have at least one match)

 P(N,2) = 1/N

 P(N,i+1) = P(N,i)+(1-P(N,i))(i/N)

 For P(N,k)>0.5, need k ≈ N1/2

 Need double # bits in hash value

Hash Functions & Message Authentication:

a) Message encrypted b) Message unencrypted

Symmetric Key Keyed Hash c)Message unencrypted d) Message encrypted

Hash Functions & Digital Signatures – PKCS:

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

SHA Versions:
SHA-512 Overview:

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

SHA-512 Round Function:

Message Authentication:
 message authentication is concerned with:

 protecting the integrity of a message

 validating identity of originator

 non-repudiation of origin (dispute resolution)

 will consider the security requirements

 then three alternative functions used:

 hash function (see Ch 11)

 message encryption

 message authentication code (MAC)

Message Security Requirements:

 disclosure

 traffic analysis

 masquerade
  content modification

 sequence modification

 timing modification

 source repudiation

 destination repudiation

Symmetric Message Encryption:

 encryption can also provides authentication

 if symmetric encryption is used then:

 receiver know sender must have created it

 since only sender and receiver know key used

 know content cannot have been altered...

 ... if message has suitable structure, redundancy or a suitable checksum to

detect any changes

Public-Key Message Encryption:

 if public-key encryption is used:

 encryption provides no confidence of sender

• since anyone potentially knows public-key

  however if

• sender signs message using their private-key

• then encrypts with recipients public key

• have both secrecy and authentication

 again need to recognize corrupted messages

 but at cost of two public-key uses on message

Message Authentication Code (MAC):

 generated by an algorithm that creates a small fixed-sized block

 depending on both message and secret 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

 a small fixed-sized block of data

 generated from message + secret key

 MAC = C(K,M)

 appended to message when sent

  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, but see Generic Composition

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

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

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

HMAC Design Objectives:

 use, without modifications, hash functions

 allow for easy replacement of embedded hash function

 preserve original performance of hash function without significant degradation

 use and handle keys in a simple way.

 have well understood cryptographic analysis of authentication mechanism strength

HMAC:

 specified as Internet standard RFC2104

 uses hash function on the message:

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

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

 where K+ is the key padded out to block size

 opad, ipad are specified padding constants

 overhead is just 3 more hash block calculations than the message needs alone
 any hash function can be used

 eg. MD5, SHA-1, RIPEMD-160, Whirlpool

HMAC Security:

 proved 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

 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

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

Digital Signature Model:
 Digital Signature Model:

Attacks and Forgeries:

 attacks

 key-only attack

 known message attack

 generic chosen message attack

  directed chosen message attack

 adaptive chosen message attack

 break success levels

 total break

 selective forgery

 existential forgery

Digital Signature Requirements:

 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

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

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 < xA < q-1

 compute their public key: yA = axA mod q

 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

 compute temporary key: S1 = ak 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

 V1 = am mod q

 V2 = yAS1 S1S2 mod q

 signature is valid if V1 = V2

 use field GF(19) q=19 and a=10

 Alice computes her key:

 A chooses xA=16 & computes yA=1016 mod 19 = 4

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

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

 computing S1 = 105 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

 V1 = 1014 mod 19 = 16

 V2 = 43.34 = 5184 = 16 mod 19

 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

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

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

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

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
DSS vs RSA Signatures:

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

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

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

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

Key Management and Distribution:
 topics of cryptographic key management / key distribution are complex

 cryptographic, protocol, & management issues

 symmetric schemes require both parties to share a common secret key

 public key schemes require parties to acquire valid public keys

 have concerns with doing both

Key Distribution:

 symmetric schemes require both parties to share a common secret key

 issue is how to securely distribute this key

 whilst protecting it from others

  frequent key changes can be desirable

 often secure system failure due to a break in the key distribution scheme

 given parties A and B have various key distribution alternatives:

 A can select key and physically deliver to B

 third party can select & deliver key to A & B

 if A & B have communicated previously can use previous key to encrypt a new
key

 if A & B have secure communications with a third party C, C can relay key
between A & B

Key Distribution Scenario:

Key Hierarchy:

 typically have a hierarchy of keys

 session key

 temporary key

 used for encryption of data between users

 for one logical session then discarded

 master key

 used to encrypt session keys

 shared by user & key distribution center

Key Distribution Issues:

 hierarchies of KDC’s required for large networks, but must trust each other

 session key lifetimes should be limited for greater security

 use of automatic key distribution on behalf of users, but must trust system

 use of decentralized key distribution

 controlling key usage

Symmetric Key Distribution Using Public Keys:

 public key cryptosystems are inefficient

 so almost never use for direct data encryption

 rather use to encrypt secret keys for distribution

Simple Secret Key Distribution:

 Merkle proposed this very simple scheme

 allows secure communications

 no keys before/after exist

Man-in-the-Middle Attack:

 this very simple scheme is vulnerable to an active man-in-the-middle attack

Secret Key Distribution with Confidentiality and Authentication:

Hybrid Key Distribution:

 retain use of private-key KDC

 shares secret master key with each user

 distributes session key using master key

 public-key used to distribute master keys

 especially useful with widely distributed users

 rationale

 performance

 backward compatibility

Distribution of Public Keys:

 can be considered as using one of:

 public announcement

 publicly available directory

 public-key authority

 public-key certificates

Public Announcement:

 users distribute public keys to recipients or broadcast to community at large

 eg. append PGP keys to email messages or post to news groups or email list

 major weakness is forgery

 anyone can create a key claiming to be someone else and broadcast it

 until forgery is discovered can masquerade as claimed user

Publicly Available Directory:

 can obtain greater security by registering keys with a public directory

 directory must be trusted with properties:

  contains {name,public-key} entries

 participants register securely with directory

 participants can replace key at any time

 directory is periodically published

 directory can be accessed electronically

Public-Key Authority:

 improve security by tightening control over distribution of keys from directory

 has properties of directory

 and requires users to know public key for the directory

 then users interact with directory to obtain any desired public key securely

 does require real-time access to directory when keys are needed

 may be vulnerable to tampering

Public-Key Certificates:

 certificates allow key exchange without real-time access to public-key authority

 a certificate binds identity to public key

 usually with other info such as period of validity, rights of use etc

 with all contents signed by a trusted Public-Key or Certificate Authority (CA)

 can be verified by anyone who knows the public-key authorities public-key

X.509 Authentication Service :
X.509 Certificates:

 any user with access to CA can get any certificate from it

 only the CA can modify a certificate

 because cannot be forged, certificates can be placed in a public directory

 if both users share a common CA then they are assumed to know its public key

 otherwise CA's must form a hierarchy

 use certificates linking members of hierarchy to validate other CA's

 each CA has certificates for clients (forward) and parent (backward)

 each client trusts parents certificates

 enable verification of any certificate from one CA by users of all other CAs in hierarchy