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
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
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
Goals
Confidentiality: Keeping information a secret from
those not authorised to have it.
Data integrity: Ensuring information has not
been altered by those not authorised to do so.
Authentication: Confirmation of the identity of
an entity.
Message authentication: Confirmation of the
source of information.
…
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
One-way hash functions are a cryptographic construct
used in many applications. They are used in conjunction
with public-key algorithms for both encryption and
digital signatures. They are used in integrity checking.
They are used in authentication. They have all sorts of
applications in a great many di↵erent protocols. Much
more than encryption algorithms, one-way hash
functions are the workhorses of modern cryptography.
Bruce Schneier
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
Examples
Alice sends Bob a (long) message: how can they
establish that what he received was what she sent?
Alica ands Bob two messages: how can they
establish that they are from the same source?
I want to electronically sign a contract so that it
cannot be tampered with.
In each case, using just encryption is unnecessary and
ine�cient.
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
Two important subclasses
We will meet
Unkeyed hashes:
Message digest codes (MDC)
Keyed hashes: Message authentication codes
(MAC)
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
Two important subclasses
We will meet
Unkeyed hashes: Message digest codes (MDC)
Keyed hashes: Message authentication codes
(MAC)
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
Two important subclasses
We will meet
Unkeyed hashes: Message digest codes (MDC)
Keyed hashes:
Message authentication codes
(MAC)
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
Two important subclasses
We will meet
Unkeyed hashes: Message digest codes (MDC)
Keyed hashes: Message authentication codes
(MAC)
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
A hash function
Informally, a hash function h is a function which has the
following properties:
1 Compression: h maps an input x to an output
y = h(x) of fixed length
2 Computability: given h and x, h(x) is “easy” to
compute
We will assume that the hash function h is public.
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
A hash function
Informally, a hash function h is a function which has the
following properties:
1 Compression: h maps an input x to an output
y = h(x) of fixed length
2 Computability: given h and x, h(x) is “easy” to
compute
We will assume that the hash function h is public.
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
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
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
Definition of a family of keyed hash functions
Definition
A family of keyed hash functions is a four-tuple
(X ,Y ,K,H) where:
1 X is the set of possible messages
2 Y is a finite set of possible authentication tags
3 For each k 2 K, the finite set of possible keys,
there is a hash function hk 2 H
hk : X ! Y
A pair (x, y), x 2 X , y 2 Y is valid under key k if
hk(x) = 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?
Applications
Integrity checking: Alice sends Bob the pair
(x, h(x)) 2 X ⇥ Y . Bob receives (x0, y) 2 X ⇥ Y ,
and checks that h(x0) = y.
Passwords: Alice chooses a password x 2 X for
Bob.com, which stores h(x) 2 Y wth her
username. At login, her attempt is hashed to y 2 Y
and sent to Bob.com, who compare it to h(x).
Message authenticity: Alice combines her message
m with a secret key k (shared with Bob), and
sends him (m,h(k,m)).
Digital signature: Alice hashes her message, and
signs the hash with her private key.
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