MACs and Authentication

Wikipedia · Message authentication code · CC BY-SA 4.0

A message authentication code (MAC) is a short tag computed from a message and a secret key. The receiver recomputes the tag and checks it matches. If it does, the message was not tampered with and came from someone who knows the key. A hash alone is not enough: anyone can compute H(m). A MAC requires the key.

HMAC construction

HMAC combines a hash function H with a key K using two passes: HMAC(K, m) = H((K XOR opad) || H((K XOR ipad) || m)). The inner and outer padding constants (ipad = 0x36, opad = 0x5C) ensure the two hash applications behave differently. This construction is provably secure if the underlying hash is a pseudorandom function.

Scheme

; HMAC construction (simplified with toy hash)
; HMAC(K, m) = H((K xor opad) || H((K xor ipad) || m))

(define IPAD #x36)
(define OPAD #x5C)

(define (toy-hash nums)
  ;; Simple hash over a list of numbers
  (let loop ((acc 1) (ns nums))
    (if (null? ns)
      (modulo acc 65536)
      (loop (modulo (+ (* acc 31) (car ns)) 65536)
            (cdr ns)))))

(define (hmac key message)
  (let* ((k-ipad (bitwise-xor key IPAD))
         (k-opad (bitwise-xor key OPAD))
         ;; Inner hash: H(K xor ipad || message)
         (inner (toy-hash (cons k-ipad message)))
         ;; Outer hash: H(K xor opad || inner-hash)
         (outer (toy-hash (list k-opad inner))))
    outer))

(define key 42)
(define msg (list 72 101 108 108 111))  ; "Hello"

(display "HMAC(42, 'Hello') = ")
(display (hmac key msg)) (newline)

;; Different key -> different tag
(display "HMAC(99, 'Hello') = ")
(display (hmac 99 msg)) (newline)

;; Different message -> different tag
(display "HMAC(42, 'Hellp') = ")
(display (hmac key (list 72 101 108 108 112))) (newline)

;; Without the key, you cannot forge the tag
(display "Attacker cannot compute tag without key")

; HMAC construction (simplified with toy hash)
; HMAC(K, m) = H((K xor opad) || H((K xor ipad) || m))

(define IPAD #x36)
(define OPAD #x5C)

(define (toy-hash nums)
  ;; Simple hash over a list of numbers
  (let loop ((acc 1) (ns nums))
    (if (null? ns)
      (modulo acc 65536)
      (loop (modulo (+ (* acc 31) (car ns)) 65536)
            (cdr ns)))))

(define (hmac key message)
  (let* ((k-ipad (bitwise-xor key IPAD))
         (k-opad (bitwise-xor key OPAD))
         ;; Inner hash: H(K xor ipad || message)
         (inner (toy-hash (cons k-ipad message)))
         ;; Outer hash: H(K xor opad || inner-hash)
         (outer (toy-hash (list k-opad inner))))
    outer))

(define key 42)
(define msg (list 72 101 108 108 111))  ; "Hello"

(display "HMAC(42, 'Hello') = ")
(display (hmac key msg)) (newline)

;; Different key -> different tag
(display "HMAC(99, 'Hello') = ")
(display (hmac 99 msg)) (newline)

;; Different message -> different tag
(display "HMAC(42, 'Hellp') = ")
(display (hmac key (list 72 101 108 108 112))) (newline)

;; Without the key, you cannot forge the tag
(display "Attacker cannot compute tag without key")

Encrypt-then-MAC vs MAC-then-encrypt

There are three ways to combine encryption and authentication. Encrypt-then-MAC (encrypt the plaintext, then MAC the ciphertext) is the recommended approach. The receiver checks the MAC first, rejecting tampered messages before decrypting. MAC-then-encrypt (MAC the plaintext, then encrypt both) is weaker because the receiver must decrypt before verifying integrity, which opens the door to padding oracle attacks.

Scheme

; Encrypt-then-MAC: the right order
; 1. Encrypt the plaintext
; 2. MAC the ciphertext (not the plaintext)
; 3. Send ciphertext + tag

(define (encrypt plaintext key)
  ;; XOR cipher for simplicity
  (map (lambda (b) (bitwise-xor b key)) plaintext))

(define (toy-hash nums)
  (let loop ((acc 1) (ns nums))
    (if (null? ns) (modulo acc 65536)
        (loop (modulo (+ (* acc 31) (car ns)) 65536) (cdr ns)))))

(define (mac key msg)
  (toy-hash (cons key msg)))

;; Sender
(define plaintext (list 72 101 108 108 111))
(define enc-key 42)
(define mac-key 99)

(define ciphertext (encrypt plaintext enc-key))
(define tag (mac mac-key ciphertext))

(display "Ciphertext: ") (display ciphertext) (newline)
(display "Tag: ") (display tag) (newline)

;; Receiver: verify MAC first, then decrypt
(define computed-tag (mac mac-key ciphertext))
(display "Tag valid? ") (display (= tag computed-tag)) (newline)

(define recovered (encrypt ciphertext enc-key))
(display "Recovered:  ") (display recovered)

Neighbors

Foundations (Wikipedia)

← Hash Functions by june.kim Key Exchange →