| Home Page |

| Course Page |

Chapter 12. Message Authentication Codes

Lecture Notes

Rochester Institute of Technology—Department of Computer Science

- Goals of MACs
- Authentication
- Integrity
- But
*not*nonrepudiation

- MAC operation
- Alex and Blake have a secret authentication key K
- Alex computes
**tag**T on message M: T = MAC_{K}(M) - Alex sends M and T to Blake
- Blake verifies tag T on message M: Verify
_{K}(M,T) → {verified, not verified}- Blake computes T' = MAC
_{K}(M) - The verification succeeds if T' = T

- Blake computes T' = MAC
- A MAC is not encryption

- Sometimes, "additional authenticated data" is included in the MAC computation
- This could be software version ID, message sequence number, encryption nonce, etc.
- Alex computes
**tag**T on additional data A and message M: T = MAC_{K}(A||M) - Alex sends M and T to Blake
- Alex doesn't send A; Blake already knows A

- Blake verifies tag T on message M: Verify
_{K}(A||M,T) → {verified, not verified}- Blake computes T' = MAC
_{K}(A||M) - The verification succeeds if T' = T

- Blake computes T' = MAC

- Security requirements:
- Uniqueness of tags
- Changing the message, or the key, or both, should (almost certainly) yield a different tag

- Second preimage resistance
- Given a message M1 and its tag MAC
_{K}(M1), but not the key K . . . - It must be hard to find a message M2 such that M1 and M2 have the same tag, MAC
_{K}(M1) = MAC_{K}(M2) - Specifically, it should take 2
^{n}operations, where*n*is the desired security level - If the MAC is not second preimage resistant, an attacker can observe a message and its tag, then generate another message that looks authentic, without knowing the key

- Given a message M1 and its tag MAC
- Key security
- Given a message M1 and its tag MAC
_{K}(M1), but not the key K . . . - It must be hard to find K
- Specifically, it should take 2
^{k}operations, where*k*is the key size in bits - If an attacker can derive the key given one or more messages and their tags, the attacker can generate messages that look authentic

- Given a message M1 and its tag MAC

- Secret prefix: MAC
_{K}(M) = Hash(K||M): No good- Susceptible to a length extension attack (for a Merkle-Damgård hash function)
- Alex computes Hash(Key||M1||M2||M3) = T1
- Alex sends message (M1||M2||M3) and tag T1 to Blake; Harry observes these
- Harry picks message block M4 and computes Compress(T1,M4) = T2
- Harry sends message (M1||M2||M3||M4) and tag T2 to Blake
- But T2 is the tag that Alex would have computed for message (M1||M2||M3||M4), so Blake's verification succeeds
- Harry was able to forge a message without knowing the key

- Secret suffix: MAC
_{K}(M) = Hash(M||K): Be careful- Susceptible to a collision attack (for any iterative hash function)
- Find M1 and M2 that yield an internal state collision before K
- Get the MAC's owner to compute T = Hash(M1||K)
- Send message M2 with tag T; it will look authentic
- This is a distinguishing attack

- To get a security level of
*n*bits, must use a 2*n*-bit hash function - Then a collision attack takes 2
^{(2n)/2}= 2^{n}operations - The attack can be done "offline," i.e., without knowing K

- Susceptible to a collision attack (for any iterative hash function)
- Hash-MAC (HMAC): RFC 2104, http://www.ietf.org/rfc/rfc2104.txt
- Let B = hash function's block size in bytes
- Let K' = key K padded with zero bytes to a length of B
- MAC
_{K}(M) = Hash (K'⊕opad || Hash (K'⊕ipad || M)) - opad = 5C5C...5C5C hexadecimal (same size as K')
- ipad = 3636...3636 hexadecimal (same size as K')

- Length extension attack is not possible
- Given message M1, append one more message block to get M2
- With HMAC, the longer message has to go through two hash computations . . .
- And the second hash computation includes the secret key, which the attacker doesn't know

- Collision attack is not possible
- Given message M1, replace the first (or any other) message block X to get M2
- Collision attack requires knowing the chaining value before message block X
- With HMAC, this chaining value depends on the secret key, which the attacker doesn't know

- Deriving the authentication key is not possible
- Requires finding a preimage of the hash function
- If the hash size (
*n*bits) is greater than or equal to the key size (*k*bits), then a preimage search on the hash function takes the same or more time as a brute force search on the key

- Alternative: Cipher Block Chaining Message Authentication Code (CBC-MAC)
- E
_{K}= block cipher encryption with key K - + = bitwise exclusive-or

- E
- CBC-MAC has security weaknesses
- Harry observes Alex send message = M1 (a one-block message) with tag = T1
- Harry tricks Alex into authenticating message = T1 (a one-block message), yielding tag = T2
- Harry sends message (M1||0) (a two-block message); this message's tag is T2 also
- Harry has successfully forged a message that looks like it came from Alex
**Existential forgery**

- Alternative: Cipher-based Message Authentication Code (CMAC). http://csrc.nist.gov/publications/nistpubs/800-38B/SP_800-38B.pdf
- Same as CBC-MAC, except the final message block is also exclusive-ored with a subkey derived from the key
- If the message length is a multiple of the block size, subkey = K1
- If the message length is not a multiple of the block size, the final message block is padded with 10...00 bits and subkey = K2
- K1 and K2 are computed using GF(2
^{n}) multiplication, where*n*is the block size (64 or 128 bits)- Irreducible polynomial =
*x*^{64}+*x*^{4}+*x*^{3}+ x + 1 for*n*= 64 - Irreducible polynomial =
*x*^{128}+*x*^{7}+*x*^{2}+ x + 1 for*n*= 128

- Irreducible polynomial =
- K1 = E
_{K}(000...000) ⋅*x* - K2 = K1 ⋅
*x*

- Alternative: Galois MAC (GMAC). http://csrc.nist.gov/publications/nistpubs/800-38D/SP-800-38D.pdf
- A special case of the Galois/Counter Mode (GCM) for authenticated encryption (discussed later)
- Similar to CBC-MAC, except the MAC is computed by a chained Galois field multiplication

- An algorithm designed specifically as a MAC, not based on a hash function or block cipher
- Example:
**SipHash**- J. Aumasson and D. Bernstein. SipHash: a fast short-input PRF. Cryptology ePrint Archive, Report 2012/351, June 20, 2012. http://eprint.iacr.org/2012/351
- Key size: 128 bits
- Tag size: 64 bits
- Selectable number of SipRounds after each message block
- Selectable number of SipRounds after final message block

Aumasson & Bernstein,*op. cit.*

Aumasson & Bernstein,*op. cit.* - SipHash is not collision resistant
- Can find collisions with a generic 2
^{32}birthday attack - However, the collision attack must be done online
- SipHash should not be used if collision resistance is required

- Can find collisions with a generic 2
- Use cases for SipHash:
- Message authentication
- SipHash is specifically designed to be efficient on short messages, unlike most hash- or cipher-based MACs

- Keyed hash function for hash tables
- To defend against "hash flooding" denial-of-service attacks
- The attacker inserts into the hash table a large number of keys all with the same hash value
- Having many keys in the same hash bucket increases the lookup time
- Using a fast, keyed hash function rather than a normal unkeyed hash function prevents the attacker from finding keys with the same hash value

- Example:
**Chaskey**- N. Mouha, B. Mennink, A. Van Herrewege, D. Watanabe, B. Preneel, and I. Verbauwhede. Chaskey: an efficient MAC algorithm for 32-bit microcontrollers. Cryptology ePrint Archive, Report 2014/386, May 28, 2014. http://eprint.iacr.org/2014/386
- Key size: 128 bits
- Tag size: selectable, up to 128 bits
- Designed to be efficient in software on 32-bit microcontrollers

Mouha*et al., op. cit.* - Upper diagram used when message is a multiple of the block size (128 bits)
- Lower diagram used when message is not a multiple of the block size
- Subkeys K1 and K2 computed using GF(2
^{128}) multiplication with irreducible polynomial*x*^{128}+*x*^{7}+*x*^{2}+ x + 1- K1 = K ⋅
*x* - K2 = K1 ⋅
*x*

- K1 = K ⋅
- The bijective function
*π*is computed by iterating the following round function for 8 rounds - Optionally, 16 rounds for more security

Mouha*et al., op. cit.*

- Alternative: Encrypt-then-MAC
- Ciphertext = Encrypt
_{K1}(Plaintext) - Tag = MAC
_{K2}(Additional data||Ciphertext) - Additional data is typically included in the MAC; e.g.:
- Protocol version
- Block cipher mode IV (nonce)
- Message sequence number

- Requires two secret keys
- K1 = encryption key
- K2 = authentication key

- Ciphertext = Encrypt
- Alternative: Counter with CBC-MAC (CCM) mode.
http://csrc.nist.gov/publications/nistpubs/800-38C/SP800-38C_updated-July20_2007.pdf
CBC-MAC computation CCM encryption - Alternative: Galois/Counter Mode (GCM). http://csrc.nist.gov/publications/nistpubs/800-38D/SP-800-38D.pdf
- GCTR
_{K}is counter mode encryption with key K, like CCM- GCM is defined only for a cipher block size of 128 bits

- GHASH
_{H}is tag computation with subkey H- Uses a chained GF(2
^{128}) multiplication with irreducible polynomial*x*^{128}+*x*^{7}+*x*^{2}+ x + 1

NIST,*op. cit.* - Uses a chained GF(2
- GMAC is just GCM with no confidential data (C is empty)

NIST,*op. cit.* - GCTR
- Alternative: Duplex sponge construction
- Brought to you by the designers of Keccak, the SHA-3 winner
- G. Bertoni, J. Daemen, M. Peeters, and G. Van Assche.
Duplexing the sponge: single-pass authenticated encryption and other applications.
*18th International Workshop on Selected Areas in Cryptography (SAC 2011),*LNCS 7118, 2011, pages 320-337. http://sponge.noekeon.org/SpongeDuplex.pdf

Bertoni*et al., op. cit.* - Feed in key-plus-nonce as input block
*σ*_{0} - Feed in plaintext blocks as input blocks
*σ*_{1},*σ*_{2}, . . .*σ*_{n} - Use output blocks
*Z*_{0},*Z*_{1}, . . .*Z*_{n−1}as the keystream - Ciphertext = plaintext XOR keystream
- Ciphertext blocks = (
*σ*_{1}⊕*Z*_{0}), (*σ*_{2}⊕*Z*_{1}), (*σ*_{3}⊕*Z*_{2}), . . .

- Ciphertext blocks = (
- Use output block
*Z*_{n}as the authentication tag

- A new multiyear competition to produce authenticated encryption algorithms was announced in January 2013
- Competition for Authenticated Encryption: Security, Applicability, and Robustness (CAESAR)
- http://competitions.cr.yp.to/caesar.html
- Promulgated by University of Chicago Professor Daniel Bernstein, not by NIST
- 56 first-round candidate algorithms published March 22, 2014
- 29 second-round candidate algorithms published July 7, 2015
- 15 third-round candidate algorithms published August 15, 2016
- 7 finalist candidate algorithms published March 5, 2018
- 6 winner algorithms announced February 20, 2019

- For secure communication from Alex to Blake with:
- Confidentiality
- Authentication
- Integrity
- No replays

- Alex and Blake establish a secret
**session key**- See Chapter 13

- Alex and Blake initialize
**sequence number**to 0 - Alex sends a message to Blake
- Increment sequence number
- Encrypt-and-MAC the message
- Use session key as block cipher key
- Use sequence number as block cipher mode IV (nonce)
- Include protocol version, IV, etc. as additional authenticated data in MAC

- Send IV, ciphertext, and tag to Blake

- Blake receives a message from -- who knows?
- If received IV ≤ sequence number, stop and reject message (replay)
- Decrypt-and-verify-MAC the ciphertext and tag
- Use session key as block cipher key
- Use received IV as block cipher mode IV (nonce)
- Include protocol version, IV, etc. as additional authenticated data in MAC

- If MAC does not verify, stop and reject message (authentication or integrity failure)
- If MAC verifies, accept message and set sequence number ← received IV

- To communicate from Blake to Alex as well, set up a second secure channel in the other direction
- Establish second session key separately
- Or, derive both channel keys from the same session key using a Key Derivation Function (KDF)
- Alex's key = Hash("Alex"||session key)
- Blake's key = Hash("Blake"||session key)

- Achieving the four security goals with the secure channel
- Confidentiality
- Authentication
- Integrity
- No replays

- Skein web site: http://www.skein-hash.info/
- Skein specification v1.3: http://www.skein-hash.info/sites/default/files/skein1.3.pdf
- A SHA-3 hash competition candidate that made it to the final round, but didn't win
- Based on a new, "tweakable" block cipher, Threefish, in Matyas-Meyer-Oseas mode
- State sizes of 256, 512, and 1024 bits
- Security levels of 2
^{128}, 2^{256}, and 2^{512}

- The same Skein algorithm can be:
- A hash function with any digest length
- A MAC; authentication key included in the hash
- A randomized hash; salt (nonce) included in the hash
- A hash function for use in a digital signature; public verifying key included in the hash
- A KDF; identifier of derived key included in the hash
- A cryptographic pseudorandom number generator (PRNG)
- A stream cipher keystream generator

- Combined encryption and authentication with Skein
- One instance of Skein to generate a stream cipher keystream
- Another instance of Skein to compute a MAC
- Keystream XORed with message and MAC

| Course Page |

| Home Page |