Cryptographic Hash Functions
Introduction
Perhaps the most versatile cryptographic algorithm is the cryptographic hash
function
It is used in a wide variety of security applications and Internet protocols
To better understand some of the requirements and security implications for
cryptographic hash functions, it is useful to look at the range of applications in
which it is employed
You, in you daily life make use of Hash Functions that maintain Data Integrity
without even realizing. The biggest example of this is your Windows passwords
Let’s have a look at major applications of Hashing
Message Authentication
Message authentication is a mechanism or service used to verify that the message
has not been modified in transit (data integrity)
Message authentication assures that data received are exactly as sent (i.e., contain
no modification, insertion, deletion, or replay)
In many cases, there is a requirement that the authentication mechanism assures
that purported identity of the sender is valid
Message authentication does not necessarily include the property of non-
repudiation
When a hash function is used to provide message authentication, the hash
function value is often referred to as a message digest
Approaches to Message Authentication
Message Encryption (Symmetric, Asymmetric)
Hash Functions (MD5, SHA)
MAC
Symmetric Message Encryption
Well ! Encryption can also provide authentication
Since only sender and receiver know the shared key, this implies
that the message would have only been sent by the legitimate sender
A checksum can be added to detect any change in the message
Asymmetric Message Encryption
Public key encryption provides no confidence of sender, since anyone potentially
knows public-key
However if the sender signs the message using his private-key, then encrypts with
the recipients public key, then this approach can provide both secrecy and
authentication
Again there is a need to recognize corrupted messages
Hash Functions
The essence of the use of a hash function for message authentication is that the
sender computes a hash value as a function of the bits in the message and
transmits both the hash value and the message
If there is a mismatch, the receiver knows that the message (or possibly the hash
value) has been altered
..contd
M = input message
H = Hash function
h = H(M)
Message of arbitrary length (M)
(H)
(H)Hash
Hash
function
function
Hash (h)
Hash Verification
generation
Message M h
HH
message h
verification
HH
compare
compare
yes/no
Man in the Middle Attack
The hash function must be transmitted in a secure fashion
That is, the hash function must be protected so that if an adversary
alters or replaces the message, it is not feasible for adversary to also
alter the hash value to fool the receiver
For instance
Alice transmits a data block and attaches a hash value
Darth intercepts the message, alters or replaces the data block, and calculates
and attaches a new hash value
Bob receives the altered data with the new hash value and does not detect the
change.
MiTM Attack
Hash Function Properties
Variable Input Size: H can be applied to a block of data of any size.
Fixed output: H produces a fixed length output.
Efficient: H(x) is easy to compute for any given x making both hardware and
software implementations practical.
Preimage Resistant (One way property): For any given value h, it is
computationally infeasible to find x such that H(x) = h.
Second Preimage Resistant (weak collision resistant): For any given block x, it
is computationally infeasible to find any y with H(y) = H(x), y ≠ x.
Pseudorandomness: Output of H meets standard tests for pseudorandomness
Applications of Hash Functions
To create a one-way password file
OS stores hash of password not actual password
When user enters the password, the hash of that password is compared to the stored
hash value for verification.
For intrusion detection and virus detection
keep & check hash of files on system
Use of Hash Functions for Message
Authentication (Case-1)
There are a variety of ways in which a hash code can be used to provide
message authentication
The message plus concatenated hash code is encrypted using symmetric
encryption.
Because 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 or redundancy required to achieve
authentication
Because encryption is applied to the entire message plus hash code,
confidentiality is also provided
Case-1
Case-2
Only the hash code is encrypted, using symmetric encryption. This
reduces the processing burden for those applications that do not
require confidentiality
Case-3
It is possible to use a hash function but no encryption for message
authentication. The technique assumes that the two communicating
parties 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
Because the secret value itself is not sent, an opponent cannot
modify an intercepted message and cannot generate a false message
Case-3
Case-4
Confidentiality can be added to Case-3 by encrypting the entire
message plus the hash code
What to Use and When?
When confidentiality is not required, Case-2 has an advantage over Case-1 and
Case-4
Because it does not encrypt the entire message but only the hash, in that less
computation is required
Nevertheless, there has been growing interest in techniques that avoid encryption
like Case-3
Why not Encryption?
Encryption software is relatively slow. Even though the amount of data to be
encrypted per message is small, there may be a steady stream of messages into
and out of a system
Encryption hardware costs are not negligible. Low-cost chip implementations of
DES are available, but the cost adds up if all nodes in a network must have this
capability
Encryption hardware is optimized toward large data sizes. For small blocks of
data, a high proportion of the time is spent in initialization/invocation overhead
Message Authentication Code
Message authentication is achieved using a message authentication code
(MAC), also known as a keyed hash function. Its also called a tag
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, which is associated with the protected message
If the integrity of the message needs to be checked, the MAC function can be
applied to the message and the result compared with the associated MAC value
An attacker who alters the message will be unable to alter the associated MAC
value without knowledge of the secret key
Message Authentication Code
Message of arbitrary length M
MAC = F(K, M)
MAC
MAC
M = input message function
secret key K
function
F = MAC function
K = shared secret key
fixed length MAC
MAC Generation and Verification
Secret Key K
generation Message M MAC
FF
message MAC
verification
FF
compare
compare
Secret Key
yes/no
Digital Signatures
Another important application, which is similar to the message authentication
application, is the digital signature
The operation of the digital signature is similar to that of the MAC. In the case of
the digital signature, the hash value of a message is encrypted with a user’s
private key
Anyone who knows the user’s public key can verify the integrity of the message
that is associated with the digital signature
In this case, an attacker who wishes to alter the message would need to know the
user’s private key
Digital Signature (contd)
MAC vs. DS
MAC differs from DS because MAC values are both generated and
verified using same secret key
This implies the sender and receiver both have to agree on the same
key before initiating communications, as with symmetric encryption
MACs don’t provide non-repudiation, DS does