Hash Functions

Data Integrity and Source

Authentication

• Encryption does not protect data from modification by

another party.
• Why?
• Need a way to ensure that data arrives at destination
in its original form as sent by the sender and it is
coming from an authenticated source.
 Hash Functions

A hash function maps a message of an arbitrary length

to a m-bit output
output known as the fingerprint or the message digest

What is an example of hash functions?

Give a hash function that maps Strings to integers in [0,2^{32}-1]

Cryptographic hash functions are hash functions with

additional security requirements
 Motivation
Problem:
Naive signing of long messages generates a signature of same length.

• Three Problems
• Computational overhead
• Message overhead
• Security limitations
• Attacker could re-order or re-use signed blocks
Solution:
Instead of signing the whole message, sign only a digest (=hash)
Also secure, but much faster
Needed:
5 Hash Functions
 Solution
• Hash, then sign

6
Principal input–output behavior of hash functions
Security Requirements of
Hash Functions
The three security properties of hash functions
 Hash Functions: Security Properties

•Preimage resistance: For a given output z, it is impossible to

find any input x such that h(x) = z, i.e., h(x) is one-way
(Also called one-wayness)

• Second preimage resistance: Given x1, and thus h(x1), it is

computationally infeasible to find any x2 such that h(x1) = h(x2)
(Also called weak collision resistance)

• Collision resistance: It is computationally infeasible to find

any pairs x1 ≠ x2 such that h(x1) = h(x2)
(Also called strong collision resistance)
Usages of Cryptographic Hash
Functions
Software integrity
E.g., tripwire
Timestamping
How to prove that you have discovered a
secret on an earlier date without disclosing it?
Covered later
Digital signature
Message authentication
One-time passwords
 Well Known Hash Functions
MD5
output 128 bits
collision resistance completely broken by researchers in China in 2004
SHA1
output 160 bits
no collision found yet, but method exist to find collisions in less than 2^80
considered insecure for collision resistance
one-wayness still holds
SHA2 (SHA-224, SHA-256, SHA-384, SHA-512)
outputs 224, 256, 384, and 512 bits, respectively
No real security concerns yet

11
 Hash Function Algorithms
MD5 hash function widely used (RFC 1321)
computes 128-bit message digest in 4-step process.
arbitrary 128-bit string x, appears difficult to construct msg m
whose MD5 hash is equal to x.
SHA-1 is also used.
US standard [NIST, FIPS PUB 180-1]
160-bit message digest
There are many hash functions, but most of them
do not satisfy cryptographic hash function
requirements
example: checksum
 Message-Digest Algorithm 5 (MD5)
Developed by Ron Rivest in 1991
Uses 128-bit hash values
Still widely used in legacy applications although considered
insecure
Various severe vulnerabilities discovered
Chosen-prefix collisions attacks found by Marc Stevens, Arjen
Lenstra and Benne de Weger
Start with two arbitrary plaintexts P and Q
One can compute suffixes S1 and S2 such that P||S1 and Q||S2
collide under MD5 by making 250 hash evaluations
Using this approach, a pair of different executable files or PDF
documents with the same MD5 hash can be computed
 Secure Hash Algorithm (SHA)
Developed by NSA and approved as a federal standard by NIST
SHA-0 and SHA-1 (1993)
160-bits
Considered insecure
Still found in legacy applications
Vulnerabilities less severe than those of MD5
SHA-2 family (2002)
256 bits (SHA-256) or 512 bits (SHA-512)
Still considered secure despite published attack techniques
Public competition for SHA-3 announced in 2007
 Iterated Hash Function
A compression function works on input values of fixed length
An iterated hash function extends a compression function to inputs
of arbitrary length
padding, initialization vector, and chain of compression functions
inherits collision resistance of compression function
MD5 and SHA are iterated hash functions
P1 P2 P3 P4

IV || || || || digest

SHA-1
Hashing Time MD5
0.06
0.05
0.04
msec

0.03
0.02
0.01
3/22/2021 0 Cryptography 15
0 100 200 300 400 500 600 700 800 900 1000
Input Size (Bytes)
Limitation of Using Hash Functions
for Authentication
Require an authentic channel to transmit
the hash of a message
Without such a channel, it is insecure, because anyone can
compute the hash value of any message, as the hash
function is public
Such a channel may not always exist
How to address this?
use more than one hash functions
use a key to select which one to use
 Hash Functions: Security

• Collison resistance causes most problems

• How hard is it to find a collision with a probability of 0.5 ?
• Related Problem: How many people are needed such that two
of them have the same birthday with a probability of 0.5 ?
• No! Not 365/2=183
• 23 are enough ! This is called the birthday paradox (Search
takes ≈√2n steps)
•To deal with this paradox, hash functions need a output size of
at least 160 bits
 Birthday Attack
The brute-force birthday attack aims at finding a collision for a hash function h
Randomly generate a sequence of plaintexts X1, X2, X3,…
For each Xi compute yi = h(Xi) and test whether yi = yj for some j < i
Stop as soon as a collision has been found
If there are m possible hash values, the probability that the i-th plaintext does not
collide with any of the previous i -1 plaintexts is 1 - (i - 1)/m
The probability Fk that the attack fails (no collisions) after k plaintexts is
Fk = (1 - 1/m) (1 - 2/m) (1 - 3/m) … (1 - (k - 1)/m)
Using the standard approximation 1 - x  e-x
Fk  e-(1/m + 2/m + 3/m + … + (k-1)/m) = e-k(k-1)/2m
The attack succeeds/fails with probability ½ when Fk = ½ , that is,
e-k(k-1)/2m = ½
k  1.17 m½
We conclude that a hash function with b-bit values provides about b/2 bits of
security
 Birthday Attacks

◼ Birthday paradox
◼ In a group of 23 randomly chosen people, at least two will

share a birthday with probability at least 50%. If there

are 30, the probability is around 70%.

◼ Finding two people with the same birthday is the same

thing as finding a collision for this particular hash function.

19
 Birthday Attacks

◼ The probability that all 23 people have different birthdays

is
1 2 22
1 (1 - )(1 - )...(1 - ) = 0.493
365 365 365
Therefore, the probability of at least two having the
same birthday is 1- 0.493=0.507
◼ More generally, suppose we have N objects, where N is

large. There are r people, and each chooses an object.

Then
20
-r / 2 N
P( there is a match )  1 - e
2
Birthday Attacks

◼ Choosing r2/2N = ln2, we find that if r≈1.177 ,N then the

probability is 50% that at least two people choose the
same object.
◼ If there are N possibilities and we have a list of length N ,
then there is a good chance of a match.
◼ If we want to increase the chance of a match, we can
make a list of length of a constant times N.

21
 Birthday Attacks
(Example) We have 40 license plates, each ending
in a 3-digit number. What is the probability that two
of the license plates end in the same 3 digits?
(Solution) N=1000, r=40
1. Approximation:
-402 / 21000
1- e = 0.551
2. The exact answer:

1 2 39
1 - (1 - )(1 - )...(1 - ) = 0.54622
1000 1000 1000
Birthday Attacks

◼ What is the probability that none of these 40 license

plates ends in the same 3 digits as yours?
1 40
(1 - ) = 0.961
1000
◼ The reason the birthday paradox works is that we are not
just looking for matches between one fixed plate and the
other plates. We are looking for matches between any
two plates in the set, so there are more opportunities for
matches.
23
 Birthday Attacks
◼ The birthday attack can be used to find collisions for hash
functions if the output of the hash function is not
sufficiently large.
◼ Suppose h is an n-bit hash function. Then there are N = 2n
possible outputs. We have the situation of list of length r≈
“people” with N possible “birthdays,” so there is a good
chance of having two values with the same hash value.
◼ If the hash function outputs
N 128-bit values, then the lists
have length around 264 ≈1019, which is too large, both in
time and in memory.

24
 Birthday Attacks
◼ Suppose there are N objects and there are two groups of r
people. Each person from each group selects an object.
What is the probability that someone from the first group
choose the same object as someone from the second
group?
P( there is a match between tw o groups )
-r 2 / N
= 1- e
◼ Eg. If we take N=365 and r=30, then
P( there is a match between tw o groups)
-302 / 365
= 1- e = 0.915
Choosing the length of Hash outputs

The Weakest Link Principle:

A system is only as secure as its weakest link.
Hence all links in a system should have similar
levels of security.
Because of the birthday attack, the length of hash
outputs in general should double the key length of
block ciphers
SHA-224 matches the 112-bit strength of triple-DES
(encryption 3 times using DES)
SHA-256, SHA-384, SHA-512 match the new key lengths
(128,192,256) in AES
26
SHA - Padding
Input: a message of b bits
Padding makes the message length a multiple of 512
bits
The input is always padded (even if its length is
already a multiple of 512)
Padding is accomplished by appending
to the input:
A single bit, 1
Enough additional bits, all 0, to make the final 512-bit
block exactly 448 bits long
A 64-bit integer representing the length of the
original message in bits
Message Authentication
Code
A MAC scheme is a hash family, used for
message authentication
MAC(K,M) = HK(M)
The sender and the receiver share secret K
The sender sends (M, Hk(M))
The receiver receives (X,Y) and verifies that
HK(X)=Y, if so, then accepts the message as
from the sender
To be secure, an adversary shouldn’t be able
to come up with (X’,Y’) such that HK(X’)=Y’.
Security Requirements for MAC
Resist the Existential Forgery under Chosen
Plaintext Attack
Challenger chooses a random key K
Adversary chooses a number of messages M1, M2, .., Mn,
and obtains tj=MAC(K,Mj) for 1jn
Adversary outputs M’ and t’
Adversary wins if j M’≠Mj, and t’=MAC(K,M’)

Basically, adversary cannot create the MAC for

a message for which it hasn’t seen an MAC
Constructing MAC from
Hash Functions
Let h be a one-way hash function

MAC(K,M) = h(K || M), where || denote

concatenation
Insecure as MAC
Because of the Merkle-Damgard construction for
hash functions, given M and t=h(K || M),
adversary can compute M’=M||Pad(M)||X and t’,
such that h(K||M’) = t’
 HMAC: Constructing MAC from
Cryptographic Hash Functions

HMACK[M] = Hash[(K+  opad) || Hash[(K+  ipad)||M)]]

K+ is the key padded (with 0) to B bytes, the input

block size of the hash function
ipad = the byte 0x36 repeated B times
opad = the byte 0x5C repeated B times.

At high level, HMACK[M] = H(K || H(K || M))

 HMAC Security

If used with a secure hash functions (e.g.,

SHA-256) and according to the
specification (key size, and use correct
output), no known practical attacks against
HMAC