CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Recall
Using unkeyed hash
functions
Motivation for security
requirements
Constructing an
Unkeyed Hash
Function
A family of hash
functions
MD5
SHA-1
Recall
Using unkeyed hash functions
Constructing an Unkeyed Hash Function
A family of hash functions
MD5
SHA-1
Part III
Cryptographic hashes
CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Recall
Using unkeyed hash
functions
Motivation for security
requirements
Constructing an
Unkeyed Hash
Function
A family of hash
functions
MD5
SHA-1
Recall
Using unkeyed hash functions
Constructing an Unkeyed Hash Function
A family of hash functions
MD5
SHA-1
1 Recall
2 Using unkeyed hash functions
Motivation for security requirements
3 Constructing an Unkeyed Hash Function
4 A family of hash functions
5 MD5
6 SHA-1
CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Recall
Using unkeyed hash
functions
Motivation for security
requirements
Constructing an
Unkeyed Hash
Function
A family of hash
functions
MD5
SHA-1
Recall
Using unkeyed hash functions
Constructing an Unkeyed Hash Function
A family of hash functions
MD5
SHA-1
Definition of an unkeyed hash function
Definition
An unkeyed hash function is a function h : X ! Y
where:
1 X is the set of possible messages
2 Y is a finite set of possible message digests
A pair (x, y), x 2 X , y 2 Y is valid if h(x) = y.
CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Recall
Using unkeyed hash
functions
Motivation for security
requirements
Constructing an
Unkeyed Hash
Function
A family of hash
functions
MD5
SHA-1
Recall
Using unkeyed hash functions
Constructing an Unkeyed Hash Function
A family of hash functions
MD5
SHA-1
Security
A n-bit unkeyed hash function is considered to be
secure if:
1 Given a hash output producing a preimage or a
second preimage requires approximately 2n
operations;
2 Producing a collision requires approximately 2n/2
operations.
CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Recall
Using unkeyed hash
functions
Motivation for security
requirements
Constructing an
Unkeyed Hash
Function
A family of hash
functions
MD5
SHA-1
Recall
Using unkeyed hash functions
Constructing an Unkeyed Hash Function
A family of hash functions
MD5
SHA-1
1 Recall
2 Using unkeyed hash functions
Motivation for security requirements
3 Constructing an Unkeyed Hash Function
4 A family of hash functions
5 MD5
6 SHA-1
CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Recall
Using unkeyed hash
functions
Motivation for security
requirements
Constructing an
Unkeyed Hash
Function
A family of hash
functions
MD5
SHA-1
Recall
Using unkeyed hash functions
Constructing an Unkeyed Hash Function
A family of hash functions
MD5
SHA-1
Iterative hash function
CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Recall
Using unkeyed hash
functions
Motivation for security
requirements
Constructing an
Unkeyed Hash
Function
A family of hash
functions
MD5
SHA-1
Recall
Using unkeyed hash functions
Constructing an Unkeyed Hash Function
A family of hash functions
MD5
SHA-1
The Merkle-Damg̊ard construction
Theorem
Any collision resistant compression function can be
extended to a collision resistant hash function which
takes arbitrary length inputs.
This can be done e�ciently by the
Merkle-Damg̊ard construction
This construction specialises the generic
construction above
CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Recall
Using unkeyed hash
functions
Motivation for security
requirements
Constructing an
Unkeyed Hash
Function
A family of hash
functions
MD5
SHA-1
Recall
Using unkeyed hash functions
Constructing an Unkeyed Hash Function
A family of hash functions
MD5
SHA-1
The Merkle-Damg̊ard construction
Let compress : {0, 1}n+t ! {0, 1}n be a collision
resistant compression function (t � 1).
We construct a collision resistant hash function:
h :
1[
i=n+t+1
{0, 1}i ! {0, 1}n
Break input x, of bitlength b, into blocks
x1, . . . , xr. Set yi = xi, each of bitlength t,
padding out the last block with 0’s if needed.
Put yr+1 = (right justified) binary representation of
b (assume b < 2t) (MD strengthening).
CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Recall
Using unkeyed hash
functions
Motivation for security
requirements
Constructing an
Unkeyed Hash
Function
A family of hash
functions
MD5
SHA-1
Recall
Using unkeyed hash functions
Constructing an Unkeyed Hash Function
A family of hash functions
MD5
SHA-1
The Merkle-Damg̊ard construction
Let compress : {0, 1}n+t ! {0, 1}n be a collision
resistant compression function (t � 1).
We construct a collision resistant hash function:
h :
1[
i=n+t+1
{0, 1}i ! {0, 1}n
Break input x, of bitlength b, into blocks
x1, . . . , xr. Set yi = xi, each of bitlength t,
padding out the last block with 0’s if needed.
Put yr+1 = (right justified) binary representation of
b (assume b < 2t) (MD strengthening).
CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Recall
Using unkeyed hash
functions
Motivation for security
requirements
Constructing an
Unkeyed Hash
Function
A family of hash
functions
MD5
SHA-1
Recall
Using unkeyed hash functions
Constructing an Unkeyed Hash Function
A family of hash functions
MD5
SHA-1
The Merkle-Damg̊ard construction
Let compress : {0, 1}n+t ! {0, 1}n be a collision
resistant compression function (t � 1).
We construct a collision resistant hash function:
h :
1[
i=n+t+1
{0, 1}i ! {0, 1}n
Break input x, of bitlength b, into blocks
x1, . . . , xr. Set yi = xi, each of bitlength t,
padding out the last block with 0’s if needed.
Put yr+1 = (right justified) binary representation of
b (assume b < 2t) (MD strengthening).
CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Recall
Using unkeyed hash
functions
Motivation for security
requirements
Constructing an
Unkeyed Hash
Function
A family of hash
functions
MD5
SHA-1
Recall
Using unkeyed hash functions
Constructing an Unkeyed Hash Function
A family of hash functions
MD5
SHA-1
The Merkle-Damg̊ard construction
Algorithm
Construct y = y1ky2k . . . kyr+1
z0 = 0
n for i = 1 to r + 1 do
zi = compress(zi�1kyi)
end do
return h(x) = zr+1
CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Recall
Using unkeyed hash
functions
Motivation for security
requirements
Constructing an
Unkeyed Hash
Function
A family of hash
functions
MD5
SHA-1
Recall
Using unkeyed hash functions
Constructing an Unkeyed Hash Function
A family of hash functions
MD5
SHA-1
Conclusions
The Merkle-Damg̊ard construction provably generates a
collision-resistant hash-function from a
collision-resistant compression function. But:
How do we know that our compression function is
collision-resistant?
The hash function will not be preimage-resistant, in
general.
One collision yields further collisions by extension
attack.
CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Recall
Using unkeyed hash
functions
Motivation for security
requirements
Constructing an
Unkeyed Hash
Function
A family of hash
functions
MD5
SHA-1
Recall
Using unkeyed hash functions
Constructing an Unkeyed Hash Function
A family of hash functions
MD5
SHA-1
1 Recall
2 Using unkeyed hash functions
Motivation for security requirements
3 Constructing an Unkeyed Hash Function
4 A family of hash functions
5 MD5
6 SHA-1
CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Recall
Using unkeyed hash
functions
Motivation for security
requirements
Constructing an
Unkeyed Hash
Function
A family of hash
functions
MD5
SHA-1
Recall
Using unkeyed hash functions
Constructing an Unkeyed Hash Function
A family of hash functions
MD5
SHA-1
A family of hash functions
SHA−1
SHA−384 SHA−512SHA−256
SHA RIPEMD
RIPEMD−160RIPEMD−128
MD4
MD5
CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Recall
Using unkeyed hash
functions
Motivation for security
requirements
Constructing an
Unkeyed Hash
Function
A family of hash
functions
MD5
SHA-1
Recall
Using unkeyed hash functions
Constructing an Unkeyed Hash Function
A family of hash functions
MD5
SHA-1
MD5: summary of status
The MD5 algorithm is described by Rivest in
Internet Working Group, RFC 1321, April 1992
http://portal.acm.org/citation.cfm?id=RFC1321,
(includes a reference implementation)
MD5 is an extension of MD4 and is deemed to be
more conservative
Mid-1990s: Collisions found in compression
function
2004: Wang et al. produced a collision for MD5
2008: Chosen prefix collision attacks.
2013: 218 collion attacks announced.
http://www.win.tue.nl/hashclash/ChosenPrefixCollisions/
CM30173: CryptographyPart III
http://portal.acm.org/citation.cfm?id=RFC1321
http://www.win.tue.nl/hashclash/ChosenPrefixCollisions/
CM30173:
Cryptography
Part III
Recall
Using unkeyed hash
functions
Motivation for security
requirements
Constructing an
Unkeyed Hash
Function
A family of hash
functions
MD5
SHA-1
Recall
Using unkeyed hash functions
Constructing an Unkeyed Hash Function
A family of hash functions
MD5
SHA-1
MD5: summary of status
The MD5 algorithm is described by Rivest in
Internet Working Group, RFC 1321, April 1992
http://portal.acm.org/citation.cfm?id=RFC1321,
(includes a reference implementation)
MD5 is an extension of MD4 and is deemed to be
more conservative
Mid-1990s: Collisions found in compression
function
2004: Wang et al. produced a collision for MD5
2008: Chosen prefix collision attacks.
2013: 218 collion attacks announced.
http://www.win.tue.nl/hashclash/ChosenPrefixCollisions/
CM30173: CryptographyPart III
http://portal.acm.org/citation.cfm?id=RFC1321
http://www.win.tue.nl/hashclash/ChosenPrefixCollisions/
CM30173:
Cryptography
Part III
Recall
Using unkeyed hash
functions
Motivation for security
requirements
Constructing an
Unkeyed Hash
Function
A family of hash
functions
MD5
SHA-1
Recall
Using unkeyed hash functions
Constructing an Unkeyed Hash Function
A family of hash functions
MD5
SHA-1
MD5: summary of status
The MD5 algorithm is described by Rivest in
Internet Working Group, RFC 1321, April 1992
http://portal.acm.org/citation.cfm?id=RFC1321,
(includes a reference implementation)
MD5 is an extension of MD4 and is deemed to be
more conservative
Mid-1990s: Collisions found in compression
function
2004: Wang et al. produced a collision for MD5
2008: Chosen prefix collision attacks.
2013: 218 collion attacks announced.
http://www.win.tue.nl/hashclash/ChosenPrefixCollisions/
CM30173: CryptographyPart III
http://portal.acm.org/citation.cfm?id=RFC1321
http://www.win.tue.nl/hashclash/ChosenPrefixCollisions/
CM30173:
Cryptography
Part III
Recall
Using unkeyed hash
functions
Motivation for security
requirements
Constructing an
Unkeyed Hash
Function
A family of hash
functions
MD5
SHA-1
Recall
Using unkeyed hash functions
Constructing an Unkeyed Hash Function
A family of hash functions
MD5
SHA-1
MD5: summary of status
The MD5 algorithm is described by Rivest in
Internet Working Group, RFC 1321, April 1992
http://portal.acm.org/citation.cfm?id=RFC1321,
(includes a reference implementation)
MD5 is an extension of MD4 and is deemed to be
more conservative
Mid-1990s: Collisions found in compression
function
2004: Wang et al. produced a collision for MD5
2008: Chosen prefix collision attacks.
2013: 218 collion attacks announced.
http://www.win.tue.nl/hashclash/ChosenPrefixCollisions/
CM30173: CryptographyPart III
http://portal.acm.org/citation.cfm?id=RFC1321
http://www.win.tue.nl/hashclash/ChosenPrefixCollisions/
CM30173:
Cryptography
Part III
Recall
Using unkeyed hash
functions
Motivation for security
requirements
Constructing an
Unkeyed Hash
Function
A family of hash
functions
MD5
SHA-1
Recall
Using unkeyed hash functions
Constructing an Unkeyed Hash Function
A family of hash functions
MD5
SHA-1
MD5: summary of status
The MD5 algorithm is described by Rivest in
Internet Working Group, RFC 1321, April 1992
http://portal.acm.org/citation.cfm?id=RFC1321,
(includes a reference implementation)
MD5 is an extension of MD4 and is deemed to be
more conservative
Mid-1990s: Collisions found in compression
function
2004: Wang et al. produced a collision for MD5
2008: Chosen prefix collision attacks.
2013: 218 collion attacks announced.
http://www.win.tue.nl/hashclash/ChosenPrefixCollisions/
CM30173: CryptographyPart III
http://portal.acm.org/citation.cfm?id=RFC1321
http://www.win.tue.nl/hashclash/ChosenPrefixCollisions/
CM30173:
Cryptography
Part III
Recall
Using unkeyed hash
functions
Motivation for security
requirements
Constructing an
Unkeyed Hash
Function
A family of hash
functions
MD5
SHA-1
Recall
Using unkeyed hash functions
Constructing an Unkeyed Hash Function
A family of hash functions
MD5
SHA-1
MD5: summary of status
The MD5 algorithm is described by Rivest in
Internet Working Group, RFC 1321, April 1992
http://portal.acm.org/citation.cfm?id=RFC1321,
(includes a reference implementation)
MD5 is an extension of MD4 and is deemed to be
more conservative
Mid-1990s: Collisions found in compression
function
2004: Wang et al. produced a collision for MD5
2008: Chosen prefix collision attacks.
2013: 218 collion attacks announced.
http://www.win.tue.nl/hashclash/ChosenPrefixCollisions/
CM30173: CryptographyPart III
http://portal.acm.org/citation.cfm?id=RFC1321
http://www.win.tue.nl/hashclash/ChosenPrefixCollisions/
CM30173:
Cryptography
Part III
Recall
Using unkeyed hash
functions
Motivation for security
requirements
Constructing an
Unkeyed Hash
Function
A family of hash
functions
MD5
SHA-1
Recall
Using unkeyed hash functions
Constructing an Unkeyed Hash Function
A family of hash functions
MD5
SHA-1
Flame Malware Attack
“[Flame is] ... arguably the most complex malware ever
found”
Flame was discovered in 2012 but probably existed
since 2010. It appears to target Iranian computers
for the purpose of espionage.
Flame authenticates itself to its host using a forged
a Microsoft Terminal Server licensing certificate.
The forgery uses a (unknown) chosen prefix attack
on MD5.
CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Recall
Using unkeyed hash
functions
Motivation for security
requirements
Constructing an
Unkeyed Hash
Function
A family of hash
functions
MD5
SHA-1
Recall
Using unkeyed hash functions
Constructing an Unkeyed Hash Function
A family of hash functions
MD5
SHA-1
1 Recall
2 Using unkeyed hash functions
Motivation for security requirements
3 Constructing an Unkeyed Hash Function
4 A family of hash functions
5 MD5
6 SHA-1
CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Recall
Using unkeyed hash
functions
Motivation for security
requirements
Constructing an
Unkeyed Hash
Function
A family of hash
functions
MD5
SHA-1
Recall
Using unkeyed hash functions
Constructing an Unkeyed Hash Function
A family of hash functions
MD5
SHA-1
SHA- 1: Basic information
Input: message of maximum length 264 � 1
Output: 160 bit message digest
Iterated hash function
Based on the Merkle-Damg̊ard construction
It operates on words of 32 bits
Three steps:
1 Preprocessing: append padding bits, append
length, initialisation
2 Iteration of a compression function
3 Output of hash
CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Recall
Using unkeyed hash
functions
Motivation for security
requirements
Constructing an
Unkeyed Hash
Function
A family of hash
functions
MD5
SHA-1
Recall
Using unkeyed hash functions
Constructing an Unkeyed Hash Function
A family of hash functions
MD5
SHA-1
SHA: summary of status
SHA (referred to as SHA-0), is considered
insecure). SHA-1 (a minor variation of SHA) is
described in FIPS publication 180-1,
http://www.itl.nist.gov/fipspubs/fip180-1.htm
2005: Wang et al. showed collisions can be found
in SHA-1 in less than 263 steps. However, attempts
to find a collision have failed:
http://boinc.iaik.tugraz.at/
Members of the SHA-2 family (SHA-256,
SHA-384, SHA-512) are more complex than
SHA-1. They are currently considered secure.
CM30173: CryptographyPart III
http://www.itl.nist.gov/fipspubs/fip180-1.htm
http://boinc.iaik.tugraz.at/
CM30173:
Cryptography
Part III
Recall
Using unkeyed hash
functions
Motivation for security
requirements
Constructing an
Unkeyed Hash
Function
A family of hash
functions
MD5
SHA-1
Recall
Using unkeyed hash functions
Constructing an Unkeyed Hash Function
A family of hash functions
MD5
SHA-1
SHA: summary of status
SHA (referred to as SHA-0), is considered
insecure). SHA-1 (a minor variation of SHA) is
described in FIPS publication 180-1,
http://www.itl.nist.gov/fipspubs/fip180-1.htm
2005: Wang et al. showed collisions can be found
in SHA-1 in less than 263 steps. However, attempts
to find a collision have failed:
http://boinc.iaik.tugraz.at/
Members of the SHA-2 family (SHA-256,
SHA-384, SHA-512) are more complex than
SHA-1. They are currently considered secure.
CM30173: CryptographyPart III
http://www.itl.nist.gov/fipspubs/fip180-1.htm
http://boinc.iaik.tugraz.at/
CM30173:
Cryptography
Part III
Recall
Using unkeyed hash
functions
Motivation for security
requirements
Constructing an
Unkeyed Hash
Function
A family of hash
functions
MD5
SHA-1
Recall
Using unkeyed hash functions
Constructing an Unkeyed Hash Function
A family of hash functions
MD5
SHA-1
SHA: summary of status
SHA (referred to as SHA-0), is considered
insecure). SHA-1 (a minor variation of SHA) is
described in FIPS publication 180-1,
http://www.itl.nist.gov/fipspubs/fip180-1.htm
2005: Wang et al. showed collisions can be found
in SHA-1 in less than 263 steps. However, attempts
to find a collision have failed:
http://boinc.iaik.tugraz.at/
Members of the SHA-2 family (SHA-256,
SHA-384, SHA-512) are more complex than
SHA-1. They are currently considered secure.
CM30173: CryptographyPart III
http://www.itl.nist.gov/fipspubs/fip180-1.htm
http://boinc.iaik.tugraz.at/
CM30173:
Cryptography
Part III
Recall
Using unkeyed hash
functions
Motivation for security
requirements
Constructing an
Unkeyed Hash
Function
A family of hash
functions
MD5
SHA-1
Recall
Using unkeyed hash functions
Constructing an Unkeyed Hash Function
A family of hash functions
MD5
SHA-1
What now?
NIST has released a policy on use of hashes in the
SHA family:
http://csrc.nist.gov/groups/ST/hash/policy.html
NIST cryptographic hash project:
http://www.nist.gov/hash-competition
CM30173: CryptographyPart III
http://csrc.nist.gov/groups/ST/hash/policy.html
http://www.nist.gov/hash-competition
CM30173:
Cryptography
Part III
Recall
Using unkeyed hash
functions
Motivation for security
requirements
Constructing an
Unkeyed Hash
Function
A family of hash
functions
MD5
SHA-1
Recall
Using unkeyed hash functions
Constructing an Unkeyed Hash Function
A family of hash functions
MD5
SHA-1
SHA-3
The hash function Keccak was chosen by NIST as
the basis for a new standard - SHA-3 (2014).
SHA-3 does not replace SHA-2 (which still
considered secure) but has some operational
advantages.
It is based on an iterated sponge construction (not
Merkle-Damg̊ard) : at each iteration, a block of
the message is XORed into the current state, and
then substitution and permutation operations are
performed.
CM30173: CryptographyPart III