CM30173: Cryptography
eserved@d =[@let@token art III
CM30173:
Cryptography
Part III
Message
authentication
codes
What do we mean by
secure?
How to create a MAC?
How to create a MAC
(for real this time)
How are they used?
Message authentication codes
Part III
Cryptographic hashes
CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Message
authentication
codes
What do we mean by
secure?
How to create a MAC?
How to create a MAC
(for real this time)
How are they used?
Message authentication codes
1 Message authentication codes
What do we mean by secure?
How to create a MAC?
How to create a MAC (for real this time)
How are they used?
CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Message
authentication
codes
What do we mean by
secure?
How to create a MAC?
How to create a MAC
(for real this time)
How are they used?
Message authentication codes
What do we mean by secure?
How to create a MAC?
How to create a MAC (for real this time)
How are they used?
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 K is the keyspace, a finite set of possible keys
4 For each k 2 K, 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
Message
authentication
codes
What do we mean by
secure?
How to create a MAC?
How to create a MAC
(for real this time)
How are they used?
Message authentication codes
What do we mean by secure?
How to create a MAC?
How to create a MAC (for real this time)
How are they used?
1 Message authentication codes
What do we mean by secure?
How to create a MAC?
How to create a MAC (for real this time)
How are they used?
CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Message
authentication
codes
What do we mean by
secure?
How to create a MAC?
How to create a MAC
(for real this time)
How are they used?
Message authentication codes
What do we mean by secure?
How to create a MAC?
How to create a MAC (for real this time)
How are they used?
Example: Data Integrity
Alice and Bob agree a private key k over a secure
channel.
When Alice wishes to send a message x with
authentication, she computes y = hk(x) and sends
(x, y).
Bob receives (x, y), and verifies that y = hk(x).
Only someone knowing k (i.e. Alice) could have
sent this message, and it is resistant to tampering.
Note that this does not allow for non-repudiation:
Anyone who knows k (e.g. Bob) could forge messages
from Alice.
CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Message
authentication
codes
What do we mean by
secure?
How to create a MAC?
How to create a MAC
(for real this time)
How are they used?
Message authentication codes
What do we mean by secure?
How to create a MAC?
How to create a MAC (for real this time)
How are they used?
1 Message authentication codes
What do we mean by secure?
How to create a MAC?
How to create a MAC (for real this time)
How are they used?
CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Message
authentication
codes
What do we mean by
secure?
How to create a MAC?
How to create a MAC
(for real this time)
How are they used?
Message authentication codes
What do we mean by secure?
How to create a MAC?
How to create a MAC (for real this time)
How are they used?
Properties
Recall:
Compression:
hk maps an input x to an output
y = hk(x) of fixed length
Computability: given k and x, hk(x) is “easy” to
compute
In addition, given a description of the hash family and a
secret key k, we require:
Computation-resistance: without prior
knowledge of k, given zero or more pairs
(xi, hk(xi)) it is computationally infeasible to
compute (x, hk(x)) for a new input x 6= xi
CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Message
authentication
codes
What do we mean by
secure?
How to create a MAC?
How to create a MAC
(for real this time)
How are they used?
Message authentication codes
What do we mean by secure?
How to create a MAC?
How to create a MAC (for real this time)
How are they used?
Properties
Recall:
Compression: hk maps an input x to an output
y = hk(x) of fixed length
Computability: given k and x, hk(x) is “easy” to
compute
In addition, given a description of the hash family and a
secret key k, we require:
Computation-resistance: without prior
knowledge of k, given zero or more pairs
(xi, hk(xi)) it is computationally infeasible to
compute (x, hk(x)) for a new input x 6= xi
CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Message
authentication
codes
What do we mean by
secure?
How to create a MAC?
How to create a MAC
(for real this time)
How are they used?
Message authentication codes
What do we mean by secure?
How to create a MAC?
How to create a MAC (for real this time)
How are they used?
Properties
Recall:
Compression: hk maps an input x to an output
y = hk(x) of fixed length
Computability:
given k and x, hk(x) is “easy” to
compute
In addition, given a description of the hash family and a
secret key k, we require:
Computation-resistance: without prior
knowledge of k, given zero or more pairs
(xi, hk(xi)) it is computationally infeasible to
compute (x, hk(x)) for a new input x 6= xi
CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Message
authentication
codes
What do we mean by
secure?
How to create a MAC?
How to create a MAC
(for real this time)
How are they used?
Message authentication codes
What do we mean by secure?
How to create a MAC?
How to create a MAC (for real this time)
How are they used?
Properties
Recall:
Compression: hk maps an input x to an output
y = hk(x) of fixed length
Computability: given k and x, hk(x) is “easy” to
compute
In addition, given a description of the hash family and a
secret key k, we require:
Computation-resistance: without prior
knowledge of k, given zero or more pairs
(xi, hk(xi)) it is computationally infeasible to
compute (x, hk(x)) for a new input x 6= xi
CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Message
authentication
codes
What do we mean by
secure?
How to create a MAC?
How to create a MAC
(for real this time)
How are they used?
Message authentication codes
What do we mean by secure?
How to create a MAC?
How to create a MAC (for real this time)
How are they used?
Properties
Recall:
Compression: hk maps an input x to an output
y = hk(x) of fixed length
Computability: given k and x, hk(x) is “easy” to
compute
In addition, given a description of the hash family and a
secret key k, we require:
Computation-resistance:
without prior
knowledge of k, given zero or more pairs
(xi, hk(xi)) it is computationally infeasible to
compute (x, hk(x)) for a new input x 6= xi
CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Message
authentication
codes
What do we mean by
secure?
How to create a MAC?
How to create a MAC
(for real this time)
How are they used?
Message authentication codes
What do we mean by secure?
How to create a MAC?
How to create a MAC (for real this time)
How are they used?
Properties
Recall:
Compression: hk maps an input x to an output
y = hk(x) of fixed length
Computability: given k and x, hk(x) is “easy” to
compute
In addition, given a description of the hash family and a
secret key k, we require:
Computation-resistance: without prior
knowledge of k, given zero or more pairs
(xi, hk(xi)) it is computationally infeasible to
compute (x, hk(x)) for a new input x 6= xi
CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Message
authentication
codes
What do we mean by
secure?
How to create a MAC?
How to create a MAC
(for real this time)
How are they used?
Message authentication codes
What do we mean by secure?
How to create a MAC?
How to create a MAC (for real this time)
How are they used?
MAC forgery
If a MAC is not computation-resistant it is subject to
MAC forgery.
Computation-resistance ) key non-recovery
key non-recovery 6) computation-resistance
Attack models:
Known-text attack
Chosen-text attack
Adaptive chosen-text attack
CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Message
authentication
codes
What do we mean by
secure?
How to create a MAC?
How to create a MAC
(for real this time)
How are they used?
Message authentication codes
What do we mean by secure?
How to create a MAC?
How to create a MAC (for real this time)
How are they used?
MAC forgery
If a MAC is not computation-resistant it is subject to
MAC forgery.
Computation-resistance ) key non-recovery
key non-recovery 6) computation-resistance
Attack models:
Known-text attack
Chosen-text attack
Adaptive chosen-text attack
CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Message
authentication
codes
What do we mean by
secure?
How to create a MAC?
How to create a MAC
(for real this time)
How are they used?
Message authentication codes
What do we mean by secure?
How to create a MAC?
How to create a MAC (for real this time)
How are they used?
MAC forgery
If a MAC is not computation-resistant it is subject to
MAC forgery.
Computation-resistance ) key non-recovery
key non-recovery 6) computation-resistance
Attack models:
Known-text attack
Chosen-text attack
Adaptive chosen-text attack
CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Message
authentication
codes
What do we mean by
secure?
How to create a MAC?
How to create a MAC
(for real this time)
How are they used?
Message authentication codes
What do we mean by secure?
How to create a MAC?
How to create a MAC (for real this time)
How are they used?
MAC forgery
If a MAC is not computation-resistant it is subject to
MAC forgery.
Computation-resistance ) key non-recovery
key non-recovery 6) computation-resistance
Attack models:
Known-text attack
Chosen-text attack
Adaptive chosen-text attack
CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Message
authentication
codes
What do we mean by
secure?
How to create a MAC?
How to create a MAC
(for real this time)
How are they used?
Message authentication codes
What do we mean by secure?
How to create a MAC?
How to create a MAC (for real this time)
How are they used?
MAC forgery
If a MAC is not computation-resistant it is subject to
MAC forgery.
Computation-resistance ) key non-recovery
key non-recovery 6) computation-resistance
Attack models:
Known-text attack
Chosen-text attack
Adaptive chosen-text attack
CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Message
authentication
codes
What do we mean by
secure?
How to create a MAC?
How to create a MAC
(for real this time)
How are they used?
Message authentication codes
What do we mean by secure?
How to create a MAC?
How to create a MAC (for real this time)
How are they used?
MAC forgery: severity of attack
The attacker is able to produce a new valid pair
(x, hk(x)):
Existential Forgery for some message x.
Selective Forgery for a predetermined message x.
Universal Forgery For any message x.
but has no control over the value of k.
CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Message
authentication
codes
What do we mean by
secure?
How to create a MAC?
How to create a MAC
(for real this time)
How are they used?
Message authentication codes
What do we mean by secure?
How to create a MAC?
How to create a MAC (for real this time)
How are they used?
Key recovery by exhaustive search
Input: (x, hk(x)), key of length l
Output: k
Compute n-bit MAC using all possible keys
This requires 2l MAC operations.
In an ideal MAC, 2l�n keys will remain as
candidates
Further valid pairs can test the remaining
candidates
A MAC key should not be recoverable in fewer
than 2l operations.
CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Message
authentication
codes
What do we mean by
secure?
How to create a MAC?
How to create a MAC
(for real this time)
How are they used?
Message authentication codes
What do we mean by secure?
How to create a MAC?
How to create a MAC (for real this time)
How are they used?
Key recovery by exhaustive search
Input: (x, hk(x)), key of length l
Output: k
Compute n-bit MAC using all possible keys
This requires 2l MAC operations.
In an ideal MAC, 2l�n keys will remain as
candidates
Further valid pairs can test the remaining
candidates
A MAC key should not be recoverable in fewer
than 2l operations.
CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Message
authentication
codes
What do we mean by
secure?
How to create a MAC?
How to create a MAC
(for real this time)
How are they used?
Message authentication codes
What do we mean by secure?
How to create a MAC?
How to create a MAC (for real this time)
How are they used?
Cost of guessing a MAC
For an n-bit MAC we expect to guess a correct MAC
with probability 2�n.
But we cannot check guesses without either the key or
an (adaptive) chosen-text scenario.
We should not be able to produce MAC forgeries
with probability higher than max(2�l, 2�n)
CM30173: CryptographyPart III
CM30173:
Cryptography
Part III
Message
authentication
codes
What do we mean by
secure?
How to create a MAC?
How to create a MAC
(for real this time)
How are they used?
Message authentication codes
What do we mean by secure?
How to create a MAC?
How to create a MAC (for real this time)
How are they used?
Cost of guessing a MAC
For an n-bit MAC we expect to guess a correct MAC
with probability 2�n.
But we cannot check guesses without either the key or
an (adaptive) chosen-text scenario.
We should not be able to produce MAC forgeries
with probability higher than max(2�l, 2�n)
CM30173: CryptographyPart III
Message authentication codes
What do we mean by secure?
How to create a MAC?
How to create a MAC (for real this time)
How are they used?