CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Do we know who we
are talking to yet?
Message digest
codes
What do we mean by
secure?
Creating MDCs
Iterated hash functions
Do we know who we are talking to yet?
Message digest codes
Creating MDCs
Part III
Cryptographic hashes
CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Do we know who we
are talking to yet?
Message digest
codes
What do we mean by
secure?
Creating MDCs
Iterated hash functions
Do we know who we are talking to yet?
Message digest codes
Creating MDCs
What do we mean by secure?
1 Do we know who we are talking to yet?
2 Message digest codes
What do we mean by secure?
3 Creating MDCs
Iterated hash functions
CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Do we know who we
are talking to yet?
Message digest
codes
What do we mean by
secure?
Creating MDCs
Iterated hash functions
Do we know who we are talking to yet?
Message digest codes
Creating MDCs
What do we mean by secure?
Three problems
If a hash function is to be considered secure we require
three problems to be di�cult to solve:
Preimage problem
Second preimage problem
Collision problem
CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Do we know who we
are talking to yet?
Message digest
codes
What do we mean by
secure?
Creating MDCs
Iterated hash functions
Do we know who we are talking to yet?
Message digest codes
Creating MDCs
What do we mean by secure?
Preimage problem
Problem
Inputs: h : X ! Y , y 2 Y
Find: x 2 X such that h(x) = y
CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Recall
Constructing an
Unkeyed Hash
Function
A family of hash
functions
MD5
SHA-1
Recall
Constructing an Unkeyed Hash Function
A family of hash functions
MD5
SHA-1
An example attack: first preimage
Message digests are also used to obscure passwords.
There is a natural first preimage attack in this case:
Alice sets a new password p, the password isn’t
stored on the system, the hash h(p) is stored.
If Alice wants to log in then her password is
requested, the password she gives is hashed and
compared with the stored value.
If Oscar had h(p) but not p then he has the input
for a first preimage attack.
If Oscar can find some p0 for which h(p0) = h(p)
then he can use p0 as a password for Alice’s
account and log in to the system as Alice.
CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Do we know who we
are talking to yet?
Message digest
codes
What do we mean by
secure?
Creating MDCs
Iterated hash functions
Do we know who we are talking to yet?
Message digest codes
Creating MDCs
What do we mean by secure?
Second preimage problem
Problem
Inputs: h : X ! Y , x 2 X
Find: x0 2 X such that h(x0) = h(x)
CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Recall
Constructing an
Unkeyed Hash
Function
A family of hash
functions
MD5
SHA-1
Recall
Constructing an Unkeyed Hash Function
A family of hash functions
MD5
SHA-1
An example attack: second preimage
Consider a digital signature scheme where the signatory
signs the hash h(x) rather than x itself.
1 Alice prepares x, some agreement she has with
Oscar, she calculates h(x) and signs it, sending x
and the signed hash to Oscar.
2 Oscar has x and h(x).
3 If h is not second preimage resistant Oscar may be
able to find x0 such that h(x) = h(x0).
4 He can now claim that Alice signed x0.
CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Do we know who we
are talking to yet?
Message digest
codes
What do we mean by
secure?
Creating MDCs
Iterated hash functions
Do we know who we are talking to yet?
Message digest codes
Creating MDCs
What do we mean by secure?
Collision problem
Problem
Inputs: h : X ! Y
Find: x, x0 2 X such that x 6= x0 and h(x) = h(x0)
CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Recall
Constructing an
Unkeyed Hash
Function
A family of hash
functions
MD5
SHA-1
Recall
Constructing an Unkeyed Hash Function
A family of hash functions
MD5
SHA-1
An example attack: collision
Now assume that Oscar is preparing the documents for
Alice to sign.
1 Oscar produces x and x0, h(x) = h(x0). x is the
agreement Alice expects and x0 is some other
agreement more favourable to Oscar.
2 Alice receives x, calculates h(x) and sends the
signed hash to Oscar.
3 Oscar can now claim that Alice signed x0.
CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Do we know who we
are talking to yet?
Message digest
codes
What do we mean by
secure?
Creating MDCs
Iterated hash functions
Do we know who we are talking to yet?
Message digest codes
Creating MDCs
What do we mean by secure?
Naive attack
h produces hashes of length n bits.
Let y = h(x) for some message x.
For random bitstrings x0 of bounded bitlength,
calculate h(x0) and check if h(x0) = y
CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Do we know who we
are talking to yet?
Message digest
codes
What do we mean by
secure?
Creating MDCs
Iterated hash functions
Do we know who we are talking to yet?
Message digest codes
Creating MDCs
What do we mean by secure?
The birthday “paradox”
The birthday “paradox”
In a group of 23 randomly chosen people, at least two
will share a birthday with probability at least 1
2
.
How is this relevant anyway?
Define h : people ! days of year by setting h(x)
equal to the birth day of person x.
Finding two people with the same birthday is the
same as finding a collision for this hash.
CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Do we know who we
are talking to yet?
Message digest
codes
What do we mean by
secure?
Creating MDCs
Iterated hash functions
Do we know who we are talking to yet?
Message digest codes
Creating MDCs
What do we mean by secure?
The birthday “paradox”
The birthday “paradox”
In a group of 23 randomly chosen people, at least two
will share a birthday with probability at least 1
2
.
How is this relevant anyway?
Define h : people ! days of year by setting h(x)
equal to the birth day of person x.
Finding two people with the same birthday is the
same as finding a collision for this hash.
CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Do we know who we
are talking to yet?
Message digest
codes
What do we mean by
secure?
Creating MDCs
Iterated hash functions
Do we know who we are talking to yet?
Message digest codes
Creating MDCs
What do we mean by secure?
The birthday “paradox”
The birthday “paradox”
In a group of 23 randomly chosen people, at least two
will share a birthday with probability at least 1
2
.
How is this relevant anyway?
Define h : people ! days of year by setting h(x)
equal to the birth day of person x.
Finding two people with the same birthday is the
same as finding a collision for this hash.
CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Do we know who we
are talking to yet?
Message digest
codes
What do we mean by
secure?
Creating MDCs
Iterated hash functions
Do we know who we are talking to yet?
Message digest codes
Creating MDCs
What do we mean by secure?
Cost of the birthday attack
What is the probability that k people don’t share a
birthday?
p = 1⇥
364
365
⇥
363
365
⇥ . . .⇥
365� (k � 1)
365
Probability that there is at least one shared
birthday amongst k people is 1� p
This exceeds 1
2
for k � 23.
CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Do we know who we
are talking to yet?
Message digest
codes
What do we mean by
secure?
Creating MDCs
Iterated hash functions
Do we know who we are talking to yet?
Message digest codes
Creating MDCs
What do we mean by secure?
An Upper Bound
Over K elements, there are K
2�K
2
distinct,
unordered pairs.
If h : X ! Y is uniformly distributed, the
probability that any one pair is a collision is 1|Y| .
So we can expect a collision if K �
p
2|Y|+ 1 —
i.e. (K � 1)2 � 2|Y |, so K
2�K
2|Y| � 1.
Let h : X ! Y produce hashes y of length n bits and
hence |Y| = 2n.
We expect to find a collision by brute force in around
2n/2 operations.
CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Do we know who we
are talking to yet?
Message digest
codes
What do we mean by
secure?
Creating MDCs
Iterated hash functions
Do we know who we are talking to yet?
Message digest codes
Creating MDCs
What do we mean by secure?
An Upper Bound
Over K elements, there are K
2�K
2
distinct,
unordered pairs.
If h : X ! Y is uniformly distributed, the
probability that any one pair is a collision is 1|Y| .
So we can expect a collision if K �
p
2|Y|+ 1 —
i.e. (K � 1)2 � 2|Y |, so K
2�K
2|Y| � 1.
Let h : X ! Y produce hashes y of length n bits and
hence |Y| = 2n.
We expect to find a collision by brute force in around
2n/2 operations.
CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Do we know who we
are talking to yet?
Message digest
codes
What do we mean by
secure?
Creating MDCs
Iterated hash functions
Do we know who we are talking to yet?
Message digest codes
Creating MDCs
What do we mean by secure?
An Upper Bound
Over K elements, there are K
2�K
2
distinct,
unordered pairs.
If h : X ! Y is uniformly distributed, the
probability that any one pair is a collision is 1|Y| .
So we can expect a collision if K �
p
2|Y|+ 1 —
i.e. (K � 1)2 � 2|Y |, so K
2�K
2|Y| � 1.
Let h : X ! Y produce hashes y of length n bits and
hence |Y| = 2n.
We expect to find a collision by brute force in around
2n/2 operations.
CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Do we know who we
are talking to yet?
Message digest
codes
What do we mean by
secure?
Creating MDCs
Iterated hash functions
Do we know who we are talking to yet?
Message digest codes
Creating MDCs
What do we mean by secure?
Summary
A n-bit unkeyed hash function is considered to be:
1 Preimage resistant if producing a preimage or a
second preimage requires approximately 2n
operations;
2 Collision Resistant if producing a collision requires
approximately 2n/2 operations.
CM30173: CryptographyPart III
Cryptographic hashes
Do we know who we are talking to yet?
Message digest codes
What do we mean by secure?
Creating MDCs
Iterated hash functions