Message Authentication
• One of the most fascinating and complex areas of
cryptography is that of message authentication and the related
area of digital signatures.
• We now consider how to protect message integrity (ie
protection from modification), as well as confirming the identity
of the sender.
• This is the problem of message authentication, and in
eCommerce applications is arguably more important than
secrecy.
• Message Authentication is concerned with protecting the
integrity of a message, validating identity of originator, & non-
repudiation of origin (dispute resolution).
• There are three types of functions that may be used to produce an
authenticator: a hash function, message encryption, message
authentication code (MAC).
Message Security Requirements
Attack Security Measure
(1) Disclosure: Release of message contents to any person or Message
process. Confidentiality
(2) Traffic Analysis: Discovery of the pattern of traffic between Message
parties. Confidentiality
(3) Masquerade: Insertion of messages into the network from a Message
fraudulent source. Authentication
(4) Content Modification: Changes to the contents of a Message
message. Authentication
(5) Sequence Modification: Any modification to a sequence of Message
messages between parties. Authentication
(6) Timing Modification: Delay or replay of messages. Message
Authentication
(7) Source Repudiation: Denial of transmission of message by Digital Signature
source.
(8) Destination Repudiation: Denial of receipt of message by Digital Signature +
destination. Special Protocol
Symmetric Message Encryption
Øencryption can also provide authentication
Øif symmetric encryption is used then:
lreceiver know sender must have created it
lsince only sender and receiver know the key used
lThey know content cannot be altered
lif message has suitable structure, redundancy or a
checksum to detect any changes
Public-Key Message Encryption
•if public-key encryption is used:
• encryption provides no confidence of sender
• since anyone potentially knows public-key
• however if
• sender signs message using their private-key
• then encrypts with recipients public key
• have both secrecy and authentication
• The disadvantage of this approach is that the public-key algorithm,
which is complex, must be exercised four times rather than two in
each communication.
Message Authentication Code (MAC)
• An alternative authentication technique involves
the use of a secret key to generate a small fixed-
size block of data, known as a cryptographic
checksum or MAC that is appended to the
message as a signature.
• This technique assumes that two
communicating parties, say A and B, share a
common secret key K.
• A MAC function is similar to encryption, except
that the MAC algorithm need not be reversible, as
it must for decryption.
Message Authentication Code
Ø This technique assumes that two communicating parties, say A and B, share a
common secret key K.
Ø When A has a message to send to B, it calculates the MAC as a function of the
message and the key: MAC = C(K, M).
Ø The message plus MAC are transmitted to the intended recipient. The recipient
performs the same calculation on the received message, using the same secret key, to
generate a new MAC.
Ø The received MAC is compared to the calculated MAC.
Ø If we assume that only the receiver and the sender know the identity of the secret key,
and if the received MAC matches the calculated MAC, then the receiver is assured that
the message has not been altered, is from the alleged sender, and if the message
includes a sequence number then the receiver can be assured of the proper sequence
because an attacker cannot successfully alter the sequence number.
Ø A MAC function is similar to encryption. One difference is that the MAC algorithm need
not be reversible, as it must for decryption. In general, the MAC function is a many-to-
one function.
Message Authentication Codes
• The process depicted on the previous slide
provides authentication but not confidentiality,
because the message as a whole is transmitted in
the clear.
• Confidentiality can be provided by performing
message encryption either after or before the MAC
algorithm.
• In both these cases, two separate keys are needed,
each of which is shared by the sender and the
receiver.
• Finally, note that the MAC does not provide a digital
signature because both sender and receiver share
the same key.
MAC Properties
• A MAC (also known as a cryptographic checksum,
fixed-length authenticator, or tag) is generated by a
function C.
• The MAC is appended to the message at the source at
a time when the message is assumed or known to be
correct.
• The receiver authenticates that message by re-
computing the MAC.
• The MAC function is a many-to-one function, since
potentially many arbitrarily long messages can be
condensed to the same summary value, but don’t want
finding them to be easy.
Requirements for MACs
• In assessing the security of a MAC function, we need
to consider the types of attacks that may be mounted
against it. Hence it needs to satisfy the listed
requirements.
• The first requirement deals with message replacement
attacks, in which an opponent is able to construct a
new message to match a given MAC, even though the
opponent does not know and does not learn the key.
• The second requirement deals with the need to thwart
a brute-force attack based on chosen plaintext.
• The final requirement dictates that the authentication
algorithm should not be weaker with respect to certain
parts or bits of the message than others.
Security of MACs
• We can group attacks on hash functions and MACs into two
categories: brute-force attacks and cryptanalysis.
• A brute-force attack on a MAC is a more difficult undertaking than
a brute-force attack on a hash function because it requires known
message-tag pairs.
• The strength of a hash function against brute-force attacks
depends solely on the length of the hash code produced by the
algorithm, with cost O(2^m/2).
• A brute-force attack on a MAC has cost related to min(2^k, 2^n),
similar to symmetric encryption algorithms.
• It would appear reasonable to require that the key length and MAC
length satisfy a relationship such as min(k, n) >= N, where N is
perhaps in the range of 128 bits.
Security of MACs
• As with encryption algorithms, cryptanalytic attacks on hash
functions and MAC algorithms seek to exploit some property of
the algorithm to perform some attack other than an exhaustive
search.
• The way to measure the resistance of a hash or MAC algorithm
to cryptanalysis is to compare its strength to the effort required
for a brute-force attack.
• That is, an ideal hash or MAC algorithm will require a
cryptanalytic effort greater than or equal to the brute-force
effort.
• There is much more variety in the structure of MACs than in
hash functions, so it is difficult to generalize about the
cryptanalysis of MACs. Further, far less work has been done on
developing such attacks.
Keyed Hash Functions as MACs
• In recent years, there has been increased interest in developing a
MAC derived from a cryptographic hash function, because they
generally execute faster in software than symmetric block ciphers,
and because code for cryptographic hash functions is widely
available.
• A hash function such as SHA was not designed for use as a MAC
and cannot be used directly for that purpose because it does not
rely on a secret key.
• There have been a number of proposals for the incorporation of a
secret key into an existing hash algorithm, originally by just pre-
pending a key to the message.
• Problems were found with these earlier, simpler proposals, but
they resulted in the development of HMAC.
HMAC Design Objectives
• RFC 2104 lists the following design objectives for
HMAC:
• To use, without modifications, available hash functions.
• In particular, hash functions that perform well in software,
and for which code is freely and widely available.
• To allow for easy replaceability of the embedded hash
function in case faster or more secure hash functions are
found or required.
• To preserve the original performance of the hash function
without incurring a significant degradation.
• To use and handle keys in a simple way.
• To have a well understood cryptographic analysis of the
strength of the authentication mechanism based on
reasonable assumptions about the embedded hash
function.
HMAC
• The idea of a keyed hash evolved into HMAC,
designed to overcome some problems with the
original proposals.
• It involves hashing padded versions of the key
concatenated with the message, and then with
another outer hash of the result prepended by
another padded variant of the key.
• The hash function need only be used on 3 more
blocks than when hashing just the original message
(for the two keys + inner hash).
• HMAC can use any desired hash function, and has
been shown to have the same security as the
underlying hash function.
HMAC Overview
The overall operation of HMAC:
HMACK = Hash[(K+ XOR opad) ||
Hash[(K+ XOR ipad) || M)]
where:
K+ is K padded with zeros on the left
so that the result is b bits in length
ipad is a pad value of 36 hex repeated
to fill block
opad is a pad value of 5C hex repeated
to fill block
M is the message input to HMAC
(including the padding specified in the
embedded hash function)
Note that the XOR with ipad results in
flipping one-half of the bits of K.
• Note that the XOR with ipad results in flipping one-half of
the bits of K. Similarly, the XOR with opad results in
flipping one-half of the bits of K, but a different set of bits.
• In effect, pseudorandomly generated two keys from K.
• HMAC should execute in approximately the same time as
the embedded hash function for long messages.
• HMAC adds three executions of the hash compression
function (for Si, So, and the block produced from the inner
hash).
• A more efficient implementation is possible by
precomputing the internal hash function on (K+ XOR
opad) and (K+ XOR ipad) and inserting the results
into the hash processing at start & end.
• With this implementation, only one additional instance of
the compression function is added to the processing
normally produced by the hash function.
• This is especially worthwhile if most of the messages for
which a MAC is computed are short.
HMAC Security
• proved security of HMAC relates to that of the underlying hash
algorithm
• attacking HMAC requires either:
• brute force attack on key used
• birthday attack (but since keyed would need to observe a very large
number of messages)
• choose hash function used based on speed verses security
constraints
Using Symmetric Ciphers for MACs
• can use any block cipher chaining mode and use final block as a
MAC
• Data Authentication Algorithm (DAA) is a widely used MAC
based on DES-CBC
• using IV=0 and zero-pad of final block
• encrypt message using DES in CBC mode
• and send just the final block as the MAC
• or the leftmost M bits (16≤M≤64) of final block
• but final MAC is now too small for security
Data Authentication Algorithm
Summary
• have considered:
• message authentication requirements
• message authentication using encryption
• MACs
• HMAC authentication using a hash function