Cryptographic Hash Functions

Contents
Section 3.1
Cryptographic hash functions,
Properties of secure hash function,
MD5
SHA
MAC
HMAC
CMAC
 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 requirement

Message authentication functions:

● message encryption
● message authentication code (MAC)
● hash function
 Security Requirements
Disclosure
Traffic Analysis
Masquerade
Content Modification
Sequence Modification
Timing Modification
Source Repudiation
Destination Repudiation
 Message Encryption
message encryption by itself also provides a measure of
authentication
if symmetric encryption is used then:
● receiver know sender must have created it
● since only sender and receiver now key used
● know content cannot of been altered
● if message has suitable structure, redundancy or a
checksum to detect any changes
 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 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
Message Authentication Code
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
 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
 Using Symmetric Ciphers for
MACs
can use any block cipher chaining mode and use final
block as a MAC
Data Authentication Algorithm (DAA) is a widely used
MAC based on DES-CBC
● using IV=0 and zero-pad of final block
● encrypt message using DES in CBC mode
● and send just the final block as the MAC
• or the leftmost M bits (16≤M≤64) of final block
but final MAC is now too small for security
Data Authentication Algorithm
 MD5 Algorithm
MD5 is a cryptographic hash function algorithm that
takes the message as input of any length and changes
it into a fixed-length message of 16 bytes. It stands for
the Message-Digest algorithm.
MD5 was developed in 1991 by Ronald Rivest with
advanced security purposes.
The output of MD5 (Digest size) is always 128 bits.
MD5 is still the most commonly used message digest
for non-cryptographic functions, such as used as a
checksum to verify data integrity, compressing large
files into smaller ones securely, etc.
Fig. MD-5 Algorithm
 Working of MD5 Algorithm
1. 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.
2. Append Length Bits: In this step, we add the length bit in
the output of the first step in such a way that the total
number of the bits is the perfect multiple of 512. Simply,
here we add the 64-bit as a length bit in the output of the
first step.
3. Initialize MD buffer: Here, we use the 4 buffers i.e. A B,
C, and D. The size of each buffer is 32 bits.
Fig. One round of MD5 Algorithm
4. 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.
● In each round 16 operations will be performed.
● 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 for calculating
functions. We use 3 buffers for each function B, C, D.
5. After applying the function now we perform an operation
on each block. For performing operations we need
● Add modulo 232
● M[i] – 32 bit message.
● K[i] – 32-bit constant.
Fig. Functions of MD5 Algorithm
● <<<n – Left shift by n bits.
6. Now take input as initialize MD buffer i.e. A, B, C, D.
Output of B will be fed in C, C will be fed into D, and D will
be fed into J. After doing this now we perform some
operations to find the output for A.
● In the first step, Outputs of B, C, and D are taken and
then the function F is applied to them. We will add
modulo 232 bits for the output of this with A.
● In the second step, we add the M[i] bit message with the
output of the first step.
● Then add 32 bits constant i.e. K[i] to the output of the
second step.
 At last, we do left shift operation by n (can be any value
of n) and addition modulo by 232.
After all steps, the result of A will be fed into B. Now same
steps will be used for all functions G, H, and I. After
performing all 64 operations we will get our message digest.

Output:
After all rounds have been performed, the buffer A, B, C, and
D contains the MD5 output starting with the lower bit A and
ending with Higher bits D.
 Hash Functions
condenses arbitrary message to fixed size
h = H(M)
usually assume that the hash function is public and not
keyed
● cf. MAC which is keyed
hash used to detect changes to message
can use in various ways with message
most often to create a 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
1. computationally infeasible to find data mapping
to specific hash (one-way property)
2. computationally infeasible to find two data to
same hash (collision-free property)
Cryptographic Hash Function
Hash Function Uses
➢ Message Integrity Check (MIC)
1. send hash of message (digest)
2. MIC always encrypted, message optionally
➢ Message Authentication Code (MAC)
1. send keyed hash of message
2. MAC, message optionally encrypted
➢ Digital Signature (non-repudiation)
1. Encrypt hash with private (signing) key
2. Verify with public (verification) key
 1. Create information
2. Calculate hash value
3. Encrypt information
4. Send encrypted information and hash value
5. Receive encrypted information and hash value
6. Decrypt information
7. Calculate its hash value at receiving end
8. Match source and destination hash
9. If matched, process information
10. If not matched, reject information
Hash Functions & Digital
Signatures
 Requirements for Hash
Functions
1. can be applied to any sized message M
2. produces fixed-length output h
3. is easy to compute h=H(M) for any message M
4. given h is infeasible to find x s.t. H(x)=h
● one-way property
5. given x is infeasible to find y s.t. H(y)=H(x)
● weak collision resistance
6. is infeasible to find any x,y s.t. H(y)=H(x)
● strong collision resistance
 Properties of Hash Functions
1. One way only
2. Any length input, fixed output
3. No secrecy involved: It does not require a key
and neither it requires any secret.
4. Small input variation produces large output
variations: High avalanche effect
5. Collisions are possible: It is situation where two
inputs produce same hash output. Algorithms
like MD5, MD4, MD5, SHA-1 have been shown
to produce collisions. Hence these are no more
used in industry today.
 Simple Hash Functions

are several proposals for simple functions

based on XOR of message blocks
not secure since can manipulate any
message and either not change hash or
change hash also
need a stronger cryptographic function
(next chapter)
 Birthday Attacks
might think a 64-bit hash is secure
but by Birthday Paradox is not
birthday attack works thus:
● opponent generates 2m/2 variations of a valid message
all with essentially the same meaning
● opponent also generates 2m/2 variations of a desired
fraudulent message
● 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
Block Ciphers as Hash Functions
can use block ciphers as hash functions
● using H0=0 and zero-pad of final block
● compute: Hi = EMi [Hi-1]
● and use final block as the hash value
● similar to CBC but without a key
resulting hash is too small (64-bit)
● both due to direct birthday attack
● and to “meet-in-the-middle” attack
other variants also susceptible to attack
Hash Functions & MAC Security

like block ciphers have:

brute-force attacks exploiting
● strong collision resistance hash have cost 2m/2
• have proposal for h/w MD5 cracker
• 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
Hash Functions & MAC Security
cryptanalytic attacks exploit structure
● like block ciphers want brute-force attacks to be the
best alternative
have a number of analytic attacks on iterated
hash functions
● CVi = f[CVi-1, Mi]; H(M)=CVN
● typically focus on collisions in function f
● like block ciphers is often composed of rounds
● attacks exploit properties of round functions
 Hash and MAC Algorithms
Hash Functions
● condense arbitrary size message to fixed size
● by processing message in blocks
● through some compression function
● either custom or block cipher based
Message Authentication Code (MAC)
● fixed sized authenticator for some message
● to provide authentication for message
● by using block cipher mode or hash function
Hash Algorithm Structure
 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
recent 2005 results on security of SHA-1 have
raised concerns on its use in future applications
Fig. Steps to produce hash value in SHA-1
Revised Secure Hash Standard

NIST issued revision FIPS 180-2 in 2002

adds 3 additional versions of SHA-3
● 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-512 Overview
 Continued..
The processing consists of the following steps:
• Step 1: Append padding bits
• Step 2: Append length
• Step 3: Initialize hash buffer
• Step 4: Process the message in 1024-bit (128-word)
blocks, which forms the heart of the algorithm
• Step 5: Output the final state value as the resulting hash
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
Keyed Hash Functions as MACs
want a MAC based on a hash function
● because hash functions are generally faster
● code for crypto hash functions widely available
hash includes a key along with message
original proposal:
KeyedHash = Hash(Key|Message)
● some weaknesses were found with this
eventually led to development of HMAC
 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 hash function can be used
● eg. MD5, SHA-1, RIPEMD-160, Whirlpool
HMAC Overview
On sender’s side, the message and a pre-shared key is
passed together into a hash function to compute a
MAC.
Computed MAC and original message is sent to
receiver.
Here, key is just a random value that when passed with
that message to a hashing function generates a MAC
value.
On receiver’s side, message is again passed through
same hashing function using same pre-shared key.
MAC value is computed and is matched with MAC value
that came from sender.
If two MAC values match, accept the message else
reject.
 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 versus
security constraints
 CMAC
In CMAC, a symmetric block cipher encryption
function is used as the MAC function to calculate
MAC value.
It is widely used in govt & industry
CMAC is calculated using AES-128 algorithm
and provides strongest form of message
authentication and integrity.
It is also known as One-Key MAC or OMAC.
Can overcome using 2 keys & padding
Fig. CMAC
CMAC Overview