Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4572 + 2433 = 7005
 Foundations of Cryptography • CSCI 662-01 • Spring Semester 2018
Course Page

## CSCI 662—Foundations of Cryptography Chapter 12. Message Authentication Codes Lecture Notes

Prof. Alan Kaminsky
Rochester Institute of Technology—Department of Computer Science

### The High Level Picture

• 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 = MACK(M)
• Alex sends M and T to Blake
• Blake verifies tag T on message M: VerifyK(M,T) → {verified, not verified}
• Blake computes T' = MACK(M)
• The verification succeeds if T' = T
• 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 = MACK(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: VerifyK(A||M,T) → {verified, not verified}
• Blake computes T' = MACK(A||M)
• The verification succeeds if T' = T

• 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 MACK(M1), but not the key K . . .
• It must be hard to find a message M2 such that M1 and M2 have the same tag, MACK(M1) = MACK(M2)
• Specifically, it should take 2n 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

• Key security
• Given a message M1 and its tag MACK(M1), but not the key K . . .
• It must be hard to find K
• Specifically, it should take 2k 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

### MAC From a Hash Function

• Secret prefix: MACK(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: MACK(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 2n-bit hash function
• Then a collision attack takes 2(2n)/2 = 2n operations
• The attack can be done "offline," i.e., without knowing K

• 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

• 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

### MAC From a Block Cipher

• Alternative: Cipher Block Chaining Message Authentication Code (CBC-MAC)

• EK = block cipher encryption with key K
• + = bitwise exclusive-or

• 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(2n) multiplication, where n is the block size (64 or 128 bits)
• Irreducible polynomial = x64 + x4 + x3 + x + 1 for n = 64
• Irreducible polynomial = x128 + x7 + x2 + x + 1 for n = 128
• K1 = EK(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

### MAC From a Dedicated Algorithm

• 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 232 birthday attack
• However, the collision attack must be done online
• SipHash should not be used if collision resistance is required

• 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

• 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(2128) multiplication with irreducible polynomial x128 + x7 + x2 + x + 1
• K1 = K ⋅ x
• K2 = K1 ⋅ x
• 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.

### Combined Encryption and Authentication

• Alternative: Encrypt-then-MAC
• Ciphertext = EncryptK1(Plaintext)
• 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

• 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

NIST, op. cit.

• GCTRK is counter mode encryption with key K, like CCM
• GCM is defined only for a cipher block size of 128 bits
• GHASHH is tag computation with subkey H
• Uses a chained GF(2128) multiplication with irreducible polynomial x128 + x7 + x2 + x + 1

NIST, op. cit.

• GMAC is just GCM with no confidential data (C is empty)

• 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 Z0, Z1, . . . Zn−1 as the keystream
• Ciphertext = plaintext XOR keystream
• Ciphertext blocks = (σ1 ⊕ Z0), (σ2 ⊕ Z1), (σ3 ⊕ Z2), . . .
• Use output block Zn 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

### The Secure Channel

• 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

• 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 2128, 2256, and 2512

• 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

 Foundations of Cryptography • CSCI 662-01 • Spring Semester 2018
Course Page
 Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4572 + 2433 = 7005