4003-482-01/4005-705-01 Cryptography
Chapter 12. Message Authentication Codes
Lecture Notes

The High Level Picture

• Goals of MACs
  • Authentication
  • Integrity
  • But not nonrepudiation

• MAC operation
  • Alice and Bob have a secret authentication key K
  • Alice computes tag T on message M: T = MAC_K(M)
  • Alice sends M and T to Bob
  • Bob verifies tag T on message M: Verify_K(M,T) → {verified, not verified}
  • A MAC is not encryption

• Security requirements
  • Without the secret authentication key, it must be impossible to compute a MAC that will verify
  • More precisely, given M but not K, finding MAC_K(M) should take 2ⁿ operations, where n is the desired security level
  • Given M and T = MAC_K(M), it must be impossible to find K
  • More precisely, finding K should take 2^m operations, where m is the key size in bits

MAC From a Hash Function

• Secret prefix: MAC_K(M) = Hash(K||M): No good
  • Susceptible to a length extension attack (for a Merkle-Damgård hash function)

• Secret suffix: MAC_K(M) = Hash(M||K): Be careful
  • Susceptible to a collision attack (for any iterative hash function)
  • To get a security level of n bits, must use a 2n-bit hash function
  • Then a collision attack takes 2^(2n)/2 = 2ⁿ operations
  • The attack can be done "offline," i.e., without knowing K

• Hash-MAC (HMAC): RFC 2104, http://www.ietf.org/rfc/rfc2104.txt
  • 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, because of the double hashing

• Collision attacks are possible
  • To get a security level of n bits, must use a 2n-bit hash function
  • However, the attack must be done "online," i.e., you have to get K's owner to compute MAC_K for you

• 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 (m 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)

  

• CBC-MAC has security weaknesses

• 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 masked with a bit string derived from the key

• Alternative: Galois MAC (GMAC). http://csrc.nist.gov/publications/nistpubs/800-38D/SP-800-38D.pdf
  • 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
  
  Aumasson & Bernstein, op. cit.
  
  Aumasson & Bernstein, op. cit.

• SipHash is not collision resistant
  • Can find collisions with a generic 2³² 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

Combined Encryption and Authentication

• Alternative: Ciphertext = Encrypt_K1(Plaintext||MAC_K2(Extra data||Plaintext))
  • Extra 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
  • Similar to CCM, except the MAC is computed by a chained Galois field multiplication

• 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 σ₀
  • Feed in plaintext blocks as input blocks σ₁, σ₂, . . . σ_n
  • Use output blocks Z₀, Z₁, . . . Z_n−1 as the keystream
  • Ciphertext = plaintext XOR keystream
  • 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

The Secure Channel

• For secure communication from Alice to Bob with:
  • Confidentiality
  • Authentication
  • Integrity
  • No replays

• Alice and Bob establish a secret session key
  • See Chapter 13

• Alice and Bob initialize sequence number to 0

• Alice sends a message to Bob
  • 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. in MAC
  • Send IV and ciphertext to Bob

• Bob receives a message from -- who knows?
  • If received IV ≤ sequence number, stop and reject message (replay)
  • Decrypt-and-verify-MAC the message
    • Use session key as block cipher key
    • Use received IV as block cipher mode IV (nonce)
    • Include protocol version, IV, etc. 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 Bob to Alice 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)
    • Alice's key = Hash("Alice"||session key)
    • Bob's key = Hash("Bob"||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.2: http://www.skein-hash.info/sites/default/files/skein1.2.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¹²⁸, 2²⁵⁶, and 2⁵¹²

• 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

Cryptography • 4003-482-01/4005-705-01 • Spring Quarter 2013

Course Page

Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4486 + 2220 = 6706

Home Page

Copyright © 2013 Alan Kaminsky. All rights reserved. Last updated 21-Mar-2013. Please send comments to ark­@­cs.rit.edu.