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
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?
I have a cunning plan…
Why not recycle?
Lets construct a MAC as follows:
Take your favourite secure unkeyed iterated hash
function h which uses compress:
{0, 1}m+t ! {0, 1}m as the compression function
For simplicity assume there is no preprocessing step
and no output transformation
Hence every message x will need to have length a
multiple t
Let hk be created by setting IV = k and keeping
the IV secret.
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?
…but Oscar knows better
Suppose Oscar has a valid pair (x, hk(x)) and a
message extension x0 of length t.
Oscar can calculate a valid pair for the extended
message xkx0 without knowledge of k
(Extension 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?
Problem solved?
We try to stop this forgery by re-introducing the
preprocessing step (padding):
Oscar has valid pair (x, hk(x)). The preprocessing step
for x produces:
y = xkpad(x), |y| = rt for some r 2 Z
Let w be of length t and define
x0 = ykw = xkpad(x)kw
The preprocessing step for x0 produces:
y0 = x0kpad(x0) = xkpad(x)kwkpad(x0)
where |y0| = r0t, r0 > r
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?
Problem solved?
Oscar wishes to find hk(x
0) without knowledge of
k. He has hk(x) which would be the current state
at round r in this computation. He computes:
zr+1 = compress(hk(x)ky
0
r+1)
zr+2 = compress(zr+1ky
0
r+2)
…
…
hk(x
0) = zr0 = compress(zr0�1ky
0
r0)
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?
What about incorporating the key in other ways?
Perhaps we could set
hk(x) = h(kkx)
This will fail for the same reasons as above!
Or we could set
hk(x) = h(xkk)
Susceptible to a birthday attack
MAC value depends only on the last chaining
value, key is only used in one step
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?
What about incorporating the key in other ways?
Perhaps we could set
hk(x) = h(kkx)
This will fail for the same reasons as above!
Or we could set
hk(x) = h(xkk)
Susceptible to a birthday attack
MAC value depends only on the last chaining
value, key is only used in one step
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?
What about incorporating the key in other ways?
Perhaps we could set
hk(x) = h(kkx)
This will fail for the same reasons as above!
Or we could set
hk(x) = h(xkk)
Susceptible to a birthday attack
MAC value depends only on the last chaining
value, key is only used in one step
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?
Su�x and postfix key
The above attacks suggest that the MAC key should be
used as both a su�x and a postfix:
hk(x) = h(kkpkxkk)
with padding to ensure that there is at least two
iterations in the computation of h.
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?
HMAC
Algorithm
Inputs: key k, MDC h
Define ipad and opad each of length 512 bits:
ipad = 3636 . . . 36
opad = 5C5C . . . 5C
HMACk(x) = h
�
(k � opad
� ��h((k � ipad)kx)
�
Keyed-Hash Message Authentication Code, FIPS
standard 198, 2002
h can be any approved unkeyed hash, examples in
the standard use SHA-1.
Argument for security is given in course book
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?
CBC-MAC: Basic idea
Construct a MAC using a block cipher in CBC mode
with a fixed, public, IV.
x1
y1
ek ekk k
y2
x2
…IV=y0
Given a sequence x1x2 . . . of plaintext blocks
y0 = IV
yi = ek(yi�1 � xi) i � 1
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?
CBC-MAC algorithm
Algorithm
Inputs: x, (P , C,K, E ,D), k 2 K, ek 2 E
Output: hk(x)
x = x1kx2k · · · kxn
IV = 00 . . . 0
y0 = IV
for i from 1 to n do
yi = ek(yi�1 � xi)
end do
return yn
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?
CBC-MAC security
We may need to pad x so it is an appropriate
length. Consideration of padding is required for
secure implementation.
If the block cipher used satisfies certain security
properties then CBC-MAC is secure.
CBC-MAC strengthening: Optionally we can
use a second key k0 6= k
y0n = dk0(yn) and set hk(x) = ek(y
0
n).
This reduces the threat of exhaustive key search
with minimal impact on e�ciency.
CBC-MAC is also susceptible to existential forgery
by extension 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?
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?
How are they used?
A MAC can be combined with encryption to provide
data integrity with confidentiality. This is achieved
as it is when using an MDC.
Downside: now there are two keys to manage
A MAC can be used to provide data integrity without
confidentiality:
Alice and Bob share a key k. Alice computes hk(x)
and sends x and hk(x) to Bob.
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?
How are they used?
A MAC can be combined with encryption to provide
data integrity with confidentiality. This is achieved
as it is when using an MDC.
Downside: now there are two keys to manage
A MAC can be used to provide data integrity without
confidentiality:
Alice and Bob share a key k. Alice computes hk(x)
and sends x and hk(x) to Bob.
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?