BCSE309L – Cryptographic and
Network Security
CNS_M4L1_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.
CNS: DrPS
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
CS526 CNS: Topic 5: Hash Functions and
DrPS
Message Authentication
Using Hash Functions for Message
Integrity
◼ Method 1: Uses a Hash Function h, assuming an authentic
(adversary cannot modify) channel for short messages
◼ Transmit a message M over the normal (insecure) channel
◼ Transmit the message digest h(M) over the secure channel
◼ When receiver receives both M’ and h, how does the receiver check
to make sure the message has not been modified?
◼ This is insecure. How to attack it?
◼ A hash function is a many-to-one function, so collisions can
happen.
CS526CNS: Topic 5: Hash Functions and
DrPS
Message Authentication
Hash Function
◼ A Hash function (H) accepts a variable-length block of
data M as input and produces a fixed-size hash value h
= H(M).
◼ A “good” hash function has the property that the
results of applying the function to a large set of inputs
will produce outputs that are evenly distributed and
apparently random.
◼ In general terms, the principal objective of a hash
function is data integrity.
CNS: DrPS
Cryptographic hash function
◼ A Cryptographic hash function: is an algorithm for
which it is computationally infeasible to find either
◼ (a) a data object that maps to a pre-specified hash
result (the one-way property) or
◼ (b) two data objects that map to the same hash result
(the collision-free property).
◼ Because of these characteristics, hash functions are
often used to determine whether or not data has
changed.
CNS: DrPS
Applications of Cryptographic
Hash Functions:
(1) Message authentication,
(2) Digital Signature,
(3) One-way password file,
(4) Intrusion detection,
(5) Virus detection,
(6) Pseudorandom number generation.
CNS: DrPS
Attacks on Hash Functions
◼ 1) Birthday Attack: the probability that in a set of n randomly
chosen people, some pair of them will have the same birthday.
Applied to hash function attacks, this means you have a 50%
chance to break the collision resistance.
◼ 2) Brute-Force Attack: is to pick values of y at random and try
each value until a collision occurs.
◼ 3) Preimage and Second Preimage Attack: For a preimage or
second preimage attack, an adversary wishes to find a value y
such that H(y) is equal to a given hash value h.
◼ 4) Collision Attack: For a collision resistant attack, an adversary
wishes to find two messages or data blocks, x and y, that yield
the same hash function.
CNS: DrPS
Security Requirements for
Cryptographic Hash Functions
Given a function h:X →Y, then we say that h is:
◼ preimage resistant (one-way):
if given y Y it is computationally infeasible to find a value x X s.t. h(x)
=y
◼ 2-nd preimage resistant (weak collision resistant):
if given x X it is computationally infeasible to find a value x’ X, s.t.
x’x and h(x’) = h(x)
◼ collision resistant (strong collision resistant):
if it is computationally infeasible to find two distinct values x’,x X, s.t.
h(x’) = h(x)
◼ Security Requirements of the Hash Functions:
(1) Variable input size, (2) Fixed output size, (3) Efficiency, (4) Preimage
resistant, (5) Second preimage resistant, (6) Collision resistant, (7)
Pseudorandomness.
CS526 CNS: Topic 5: Hash Functions and
Message Authentication DrPS
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
◼ Message authentication
◼ One-time passwords
◼ Digital signature
CS526 CNS: Topic 5: Hash Functions and
Message Authentication DrPS
Bruteforce Attacks on Hash
Functions
◼ Attacking one-wayness
◼ Goal: given h:X→Y, yY, find x such that h(x)=y
◼ Algorithm:
◼ pick a random value x in X, check if h(x)=y, if h(x)=y,
returns x; otherwise iterate
◼ after failing q iterations, return fail
◼ The average-case success probability is
= 1 − 1 − 1 | Y |
q
q
|Y |
◼ Let |Y|=2m, to get to be close to 0.5, q 2m-1
CS526 Topic 5: Hash Functions and
Message Authentication
Bruteforce Attacks on Hash
Functions
◼ Attacking collision resistance
◼ Goal: given h, find x, x’ such that h(x)=h(x’)
◼ Algorithm: pick a random set X0 of q values in X
for each xX0, computes yx=h(x)
if yx=yx’ for some x’x then return (x,x’) else fail
◼ The average success probability is
q(q−1)
− q(q−1)
1 2
1− 1− 1− e 2|Y |
|Y |
◼ Let |Y|=2m, to get to be close to 0.5, q 2m/2
◼ This is known as the birthday attack.
CS526 Topic 5: Hash Functions and
Message Authentication
Well Known Hash Functions
◼ Message Digest (MD): MD2, MD4, MD5 and MD6
◼ 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
CNS:
CS526 Topic 5: Hash Functions and
Message Authentication DrPS
Merkle-Damgard Construction
for Hash Functions
• Message is divided into fixed-size blocks and padded
• Uses a compression function f, which takes a chaining variable (of
size of hash output) and a message block, and outputs the next
chaining variable
• Final chaining variable is the hash value
M=m1m2…mn; C0=IV, Ci+1=f(Ci,mi); H(M)=Cn
CNS:
CS526 Topic 5: Hash Functions and
Message Authentication DrPS
References
◼ Books:
◼ Stallings, W. "Cryptography and Network Security:
Principles and Practice," 7th Edition.
◼ Further Reading:
◼ Menezes, A.J., van Oorschot, P.C., and Vanstone, S.A.
"Handbook of Applied Cryptography," 5th Edition.
CNS: DrPS
