Computer Security
CS 426
Lecture 6
Cryptography: Message Authentication
Code
CS426 Fall 2010/Lecture 6 1
Announcements
• H
Homework
k1h
handled
dl d outt on S
Septt 1
1, d
due on S
Septt
10
• Will have first q
quiz on Sept
p 8
CS426 Fall 2010/Lecture 6 2
Limitation of Using Hash Functions
for Authentication
• R
Require
i an authentic
th ti channel
h l tto ttransmit
it th
the
hash of a message
– anyone can compute the hash value off a message, as
the hash function is public
– nott always
l possible
ibl
• How to address this?
– use more than one hash functions
– use a key to select which one to use
CS426 Fall 2010/Lecture 6 3
Hash Family
y
• A hash
h h ffamily
il iis a ffour-tuple
t l (X(X,Y,K,H
Y K H ),
) where
h
– X is a set of possible messages
– Y is a finite set of possible message digests
– K is the keyspace
– For each KK, there is a hash function hKH . Each
hK: X Y
• Alternatively, one can think off H as a function
f
KXY
CS426 Fall 2010/Lecture 6 4
Message
g Authentication Code
• A MAC scheme is a hash family, used for
message authentication
• MAC = CK(M)
• The sender and the receiver share K
• The sender sends (M,
(M Ck(M))
• The receiver receives (X,Y) and verifies that
CK(X)=Y,
(X)=Y if so,
so then accepts the message as
from the sender
• To be secure,
secure an adversary shouldn’t
shouldn t be able to
come up with (X’,Y) such that CK(X)=Y.
CS426 Fall 2010/Lecture 6 5
Example
p of Insecure Hash Families
• L
Lett h b
be a one-way hash
h h ffunction
ti
• H(K,M) = h(K || M), where || denote
concatenation
– Insecure as MAC
– Given M and a=h(K || M), can compute M’=M||… and
a’, such that h(K||M’) = a’
• H(K,M) = h(M || M),
– Also insecure as MAC
CS426 Fall 2010/Lecture 6 6
HMAC: Constructing MAC from
Cryptographic Hash Functions
HMACK[M] = Hash[(K+ opad) || Hash[(K+ ipad)||M)]]
• K+ is the key padded (with 0) to B bytes, the
i
inputt bl
blockk size
i off th
the h
hash
h ffunction
ti
• ipad = the byte 0x36 repeated B times
• opadd = ththe b
byte
t 0
0x5C
5C repeated
t d B titimes.
CS426 Fall 2010/Lecture 6 7
HMAC Overview
CS426 Fall 2010/Lecture 6 8
HMAC Security
y
• If used with a secure hash functions (e.g.,
SHA-256) and according to the specification
(key size, and use correct output), no known
practical attacks against HMAC
CS426 Fall 2010/Lecture 6 9
Encryption
yp and Authentication
• Three ways for encryption and authentication
– Authenticate-then-encrypt (AtE), used in SSL
• a = MAC(x)
MAC(x), C=E(x,a),
C=E(x a) transmit C
– Encrypt-then-authenticate (EtA), used in IPSec
• C=E(x),
C=E(x) a=MAC(C)
a=MAC(C), transmit (C
(C,a)
a)
– Encrypt-and-authenticate (E&A), used in SSH
•CC=E(x),
E(x), a
a=MAC(x),
MAC(x), transmit (C,a)
• Which way provides secure communications
when
e eembedded
bedded in a p
protocol
o oco that
a runs
u s in a real
ea
adversarial network setting?
CS426 Fall 2010/Lecture 6 10
Encryption Alone May Be
Ins fficient for Privacy
Insufficient Pri ac
• If an adversary
d can manipulate
i l t a ciphertext
i h t t suchh
that the observable behavior (such as success or
f il
failure off d
decryption)
ti ) diff
differs d
depending
di on ththe
content of plaintext, then information about
plaintext
l i t t can be
b lleaked
k d
• To defend against these, should authenticate
ciphertext, and only decrypt after making sure
ciphertext has not changed
• Encrypt-then-authenticate (EtA) is secure
– C=E(x), a=MAC(C), transmit (C,a)
CS426 Fall 2010/Lecture 6 11
Encryption Alone May Be Insufficient
f Privacy:
for Pi A
An AArtificial
tifi i l Example
E l
• Given a secure stream cipher (or even one
one-time
time pad) E
E,
Consider encryption E*
– E
E*[x]
[x] = E[encode[x]]
• encode[x] replaces 0 with 00, and 1 with either 01 or 10.
– How to decrypt?
– E*[x] is secure
• Using E* may not provide confidentiality in some usage
– Consider the case an adversary flips the first two bits of E*[x]
– When the bits are 01 or 10, flipping results in no change after decrypt
– When the bits are 00
00, flipping result in decryption failure
– Learning whether decryption succeeds reveal first bit
CS426 Fall 2010/Lecture 6 12
AtE and E&A are insecure
• A
Authenticate-then-encrypt
th ti t th t (AtE) iis nott always
l
secure
– a = MAC(x),
C( ) C C=E(x,a),
( ) transmit C
– As first step is decryption, its success or failure may
l k iinformation.
leak f ti
– AtE, however, can be secure for some encryption
schemes such as CBC or OTP (or stream ciphers)
schemes,
• Encrypt-and-authenticate (E&A) is not secure
– C=E(x)
C=E(x), a=MAC(x)
a=MAC(x), transmit (C
(C,a)
a)
– MAC has no guarantee for confidentiality
CS426 Fall 2010/Lecture 6 13
Readings
g for This Lecture
• Wikipedia
• Message Authentication
C d
Code
• Optional reading
• Hugo Krawzyck.: The Order
of Encryption and
Authentication for Protecting
Communications”
CS426 Fall 2010/Lecture 6 14
Coming
g Attractions …
• Operating
O ti System
S t Security
S it Basics
B i
CS426 Fall 2010/Lecture 6 15
