Message Authentication Codes

Cryptographic Goals
Cryptographic goals

Confidentiality Data integrity Authentication Non-repudiation

Symmetric-key Arbitrary length Entity authentication Digital signatures

ciphers: hash functions
Authentication
▪Block ciphers
primitives
▪Stream ciphers Message
Authentication
Public-key codes (MACs) Message authentication
ciphers
Digital signatures MACs

Digital
signatures
2
 Message Authentication Codes

• MAC f(x, key):{0,1}* → {0,1}n

– knowing x and key f is easy to compute
– it is infeasible to calculate f(x,key) without the key

• MAC are often block cipher based

– message m, secret key k
– specification of block cipher E
• MAC (m) = E( m, key )
• MAC (m) = E(hash(m), key )

3
 Message Authentication
➢ Message authentication is concerned with:
⚫ protecting the integrity of a message
⚫ validating identity of originator
⚫ non-repudiation of origin (dispute resolution)

➢ Then will consider the security requirements

➢ Subsequently three alternative functions used:
⚫ hash function
⚫ message encryption
⚫ message authentication code (MAC)
Message Security Requirements
▪ disclosure
▪ traffic analysis
▪ masquerade (pretend to be someone)
▪ content modification deals with Message
Authentication
▪ sequence modification
▪ timing modification
▪ source repudiation
▪ destination repudiation
Symmetric Message Encryption
• Encryption can also provide authentication
• If symmetric encryption is used then:
• receiver know sender must have created it
• since only sender & receiver know key used,
known content cannot have been altered.
• recognise a valid message → Ciphertext
serves as authenticator
 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
⚫ Again need to recognize corrupted messages
⚫ But at cost of two public-key uses on message
Public-Key Message Encryption…

- Every time you encrypt, size expands

- Due to protections in PKCS#1
- Signing (by encryption) then encrypting,
the size is more than doubled!
 Use of a MAC
• MAC - Message Authentication Code Used to
provide
– Data integrity -- Message authentication

Secret key

MAC Secret key

message
algorithm
MAC
Unsecured channel
verification
Ok /
message MAC
algorithm
Not Ok

Signer Verifier
9
 Message Authentication Code (MAC)

- An alternative authentication technique

- use of a secret key to generate a small fixed-
size block of data → cryptographic checksum
or MAC
- that is appended to the message
- 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.
 Message Authentication Code…

In cryptography, a message authentication

code (MAC) (sometimes known as a tag)

- is a short piece of information used

to authenticate a message

- to confirm that the message came from the

stated sender (its authenticity) and has not been
changed
Message Authentication Code…
 Message Authentication Code…

• Generated by an algorithm that creates a

small fixed-sized block
• depending on both message and secret key

• appended to message as a “signature”

• receiver performs same computation on
message and checks it matches the MAC
• provides assurance that message is unaltered
and comes from sender
 Message Authentication Code…
• a small fixed-sized block of data
– generated from message + secret key
– MAC = C(K,M)
– appended to message when sent
 Message Authentication Code…

• As said, MAC provides authentication

• It can also use encryption for secrecy
– generally use separate keys for each
– can compute MAC either before or after
encryption
(generally regarded as better done before)
 Message Authentication Code…

• why use a MAC?

– sometimes only authentication is needed
– sometimes need authentication to persist longer
than the encryption (e.g. archival use)
• note that a MAC is not a digital signature
• Does NOT provide non-repudiation
 MAC Properties
• a MAC is a cryptographic checksum
– MAC = CK(M)
– condenses a variable-length message M
– using a secret key K
– to a fixed-sized authenticator
• is a many-to-one function
– potentially many messages have same MAC
– but finding these needs to be very difficult
 Requirements for MACs
▪ taking into account the types of attacks
▪ need the MAC to satisfy the following:
– knowing a message and MAC, is infeasible
to find another message with same MAC
– MACs should be uniformly distributed
– MAC should depend equally on all bits of the
message
 Security of MACs
➢ brute-force attacks exploiting
- brute-force attack on a MAC is more difficult than
a brute-force attack on a hash function because it
requires known message-tag pairs

⚫ MACs with known message-MAC pairs

•can either attack keyspace ( key search) or MAC
•at least 128-bit MAC is needed for security
 Security of MACs…
➢ cryptanalytic attacks exploit structure
⚫ like block ciphers want brute-force attacks to
be the best alternative

➢ more variety of MACs so harder to generalize

about cryptanalysis
 Keyed Hash Functions as MACs
▪ want a MAC based on a hash function
▪ because hash functions are generally faster
▪ crypto hash function code is widely available
▪ hash includes a key along with message
▪ original proposal:
▪ KeyedHash = Hash(Key|Message)

▪ some weaknesses were found with this

▪ eventually led to development of HMAC
 Problem with Keyed Hash
▪ KeyedHash = Hash(Key|Message)
▪ Recall hash function works on blocks
▪ Let M = Key | Message | Padding and M
▪ M=M1 M2 … ML, where |Mi| = Blocksize
▪ Hash=H(H(…H(H(IV,M1),M2),…,ML)
▪ But can add extra block(s) ML+1 by
▪ Hash’=H(Hash,ML+1)
MAC Based on Hash Functions: HMAC

RFC 2104 - design objectives for HMAC:

• Use hash functions (without modifications)
• allow for easy replacement of embedded hash
function
• preserve original performance of hash function
without significant degradation
• use and handle keys in a simple way.
• have well understood cryptographic analysis of
authentication mechanism strength
 HMAC
▪ specified as Internet standard RFC2104

▪ uses hash function on the message:

▪ HMACK(M)= Hash[(K+ XOR opad) ||
Hash[(K+ XOR ipad) || M)] ]
▪ where K+ is the key padded out to block size
▪ opad, ipad are specified padding constants

▪ Hash fn. need to be used on 3 more blocks calculations

( 2 keys + inner Hash)
▪ any hash function can be used
▪ Ex: MD5, SHA-1, RIPEMD-160, Whirlpool
HMAC Overview
 HMAC Overview…
Note:
- XOR with ipad results in flipping one-half of the bits of K.
- Similarly, XOR with opad results in flipping one-half of the bits
of K, but a different set of bits.
- 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, & the block produced from inner hash).
- A more efficient implementation is possible by precomputing
internal hash function on K+ XOR opad and K+ XOR ipad
- And then inserting the results into the hash processing at
start & end.
HMAC → more efficient
way of implementation
Two quantities are
precomputed:
f(IV, (K + ipad))
f(IV, (K + opad))
 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
MAC s Based on Block Ciphers:
DAA and CMAC
Two MACs that are based on the use of a block cipher
mode of operation.
- DAA
- CMAC
 Data Authentication Algorithm (DAA)

• This Algorithm is based on using the cipher block

chaining (CBC) mode of operation of DES with an
initialization vector of zero.

• The data (message/record/file/program) to be

authenticated are grouped into contiguous 64-bit
blocks: D1, D2,….., DN.
• If necessary, the final block is padded on the right
with zeroes to form a full 64-bit block.
Data Authentication Algorithm (DAA)…
 Data Authentication Algorithm (DAA)…

• Using the DES encryption algorithm E and a secret key K,

a Data Authentication Code (DAC) is calculated as follows:

- Earlier, it was used as most widely used MACs

- The algorithm is both a FIPS publication (FIPS PUB 113) and an
ANSI standard (X9.17).
- Data Authentication Algorithm (DAA), which is now obsolete.
Then CMAC is designed to overcome the deficiencies of DAA.
 CMAC

▪ Forming the Cipher-based Message

Authentication Code (CMAC)
▪ adopted by NIST SP800-38B
▪ limitation (of handling fixed length message) can be
overcome using multiple keys → derived from a
single key
CMAC Overview
 CMAC Overview…

T = message authentication code (Referred as tag)

Tlen = bit length of T
MSBs(X) = the s leftmost bits of the bit string X
 CMAC Structure
CMAC → uses block size of underlying cipher
(ie 128-bits for AES or 64-bits for triple-DES)
- message is divided into n blocks M1..Mn,
(padded if necessary)
- The algorithm makes use of a k-bit
encryption key K
(For AES → key size k 128/192/ 256 bits
for triple DES→ key size is 112 /168 bits)
- Two constants K1 & K2 (n-bit → depending on
whether the message was padded or not)
- K1 & K2 are derived from original key K using
encryption of 0 and multiplication in GF(2^n).
Key wrapping
• Key wrapping is the process of encrypting one
key using another key, in order to securely store
it or transmit it over an untrusted channel.
Key wrapping…
• The purpose of key wrapping (KW) is to
securely exchange a symmetric key to be
shared by two parties, using a symmetric key
already shared by those parties.
• The latter key is called a key encryption key
(KEK)
– Key Wrap (KW) mode of operation → uses
AES or triple DEA as encryption algorithm
Further reference
• https://player.slideplayer.com/36/10557480/#

• https://asecuritysite.com/wrap/kek