Cryptography: Authenticating MessagesSlide 2The Problem: authenticate messagesAuthenticating messages - alternativesMessage Authentication Code (MAC)MAC useWhy use MAC, given encryption?Hash functionSimple Hash functionHash function (H) useAttacks on Hash Functions and MACsHMAC – combine MAC and HashCryptography: Authenticating MessagesAnita JonesCS551/651 Information Assurance Copyright(C) Anita Jones9/06 Requirementsdisclosure - prevent release of message contentstraffic analysis - prevent discovery of traffic pattern between partiesmasquerade - prevent insertion of messages by fraudulent sourcecontent modification - prevent itsequence modification - prevent ittiming modification -- prevent delay or replayrepudiation - prevent denial of a send or a receive9/06 The Problem: authenticate messagescontent is authentic – bits are as sentsequence of messages is properNote: Separate problems-confidentiality – i.e. encrypt the message-authenticate that the sender is genuine9/06 Authenticating messages - alternativesauthenticator - a value that authenticates a message contentmessage encryption - ciphertext of entire msgmessage authentication code, MAC (cryptographic checksum) - public function & secret key produce fixed length valuehash - public function maps message (any length) to fixed-length hash value (hash code also called a message digest) – no key9/06 Message Authentication Code (MAC)Objective: assure authentic contentMessage is not encryptedMAC is small fixed-size data block, appended to message MA and B share secret keyMACK[M] = F(M, key)9/06 MAC usemessage authentication (no confidentiality) A->B: [M, MACK [M]]authentication and confidentiality A->B: EK1[M, MACK [M]]authentication and confidentiality A->B: [EK1[M], MACK [EK1[M]]]Note: MAC function not necessarily reversible9/06 Why use MAC, given encryption?message may not need to be secret, but must be authenticbroadcast - only have one site responsible for monitoring authenticity. Broadcast plaintext plus MACoverload - send plaintext messages (ie. receiver need not decrypt. Authenticate selectively9/06 Hash functionalso called a “message digest”no keylike MAC, small amount of data; hash of message gives fixed-size valuedefine hash function so that change of any one bit of message will result in different hash valuehash function is not secretone-way; receiver recomputes hash function9/06 Simple Hash functionparity, or longitudinal redundancy checkprocess one bit at a timeuse XOR ( x )input – arbitrary length messagesize of processed block – one bitoutput – one bitC = b1 x b2 x b3 x . . . x bn9/06 Hash function (H) useA->B: M, H [M]can cryptographically protect Hhash provides redundant authentication A->B: EK[M, H [M]]only hash code encrypted, i.e. a MAC! Authentication, but no confidentiality A->B: M, EK [H[M]]9/06 Attacks on Hash Functions and MACsHash functions – strength of hash function depends solely on length of hash code producedGiven code h = H[M], try to find Y, H[Y]=hBrute-force attack on a MAC requires known some message/MAC pairsGiven MACK[M] = X, try all values for key – (key attack)Try different message values, M, trying to get value X9/06 HMAC – combine MAC and HashCryptographic hash functionWhy?Hashing is faster than encryptionNo export control on cryptographicApproachAppend key to each (hashed) block of messageThen hashRemember, a hash function is