CS306: Introduction to IT Security Fall 2020
Lecture 6: MACs & Hashing
Instructor: Nikos Triandopoulos October 6, 2020
2
6.0 Announcements
CS306: Other announcements
u HW2 to come by Friday this week
u Road ahead
u no lecture on October 13 (next week, classes will run on Monday schedule) u regular lecture on October 20
u midterm exam on October 27 (in whatever format)
3
CS306: Tentative Syllabus
Week
Date
Topics
Reading
Assignment
1
Sep 1
Introduction
Lecture 1
–
2
Sep 8
Symmetric-key encryption
Lecture 2
Lab 1
3
Sep 15
Perfect secrecy
Lecture 3
Lab 2, HW 1
4
Sep 22
Ciphers in practice I
Lecture 4
Lab 3, HW 1
5
Sep 29
Ciphers in practice II
Lecture 5
Lab 4
6
Oct 6
MACs & hashing
–
Oct 13
No class (Monday schedule)
7
Oct 20
Public-key cryptography
4
CS306: Tentative Syllabus
(continued)
Week
Date
Topics
Reading
Assignment
8
Oct 27
Midterm
All materials covered
9
Nov 3
Network/Web security
10
Nov 10
Software/Database security
11
Nov 17
Cloud security
12
Nov 24
AC/Authentication/Privacy
13
Dec 1
Economics
14
Dec 8
Legal & ethical issues
15
Dec 10 (or later)
Final
(closed “books”)
All materials covered*
5
* w/ focus on what covered after midterm
Last week
u Ciphers in practice u Revision
u the big picture, computational security, pseudo-randomness, stream ciphers, PRGs u Block ciphers, pseudorandom functions
u Modes of operations
u DES, AES
u Demo
u The Caesar and Vigenère ciphers and their cryptanalysis (Afternoon) u Pseudo-randomness in practice (Evening)
6
Today
u Message authentication u MACs
u Replay attacks
u Constructions
u Cryptographic hashing
u Hash functions
u Constructions u Demo
u Hash functions in practice
7
8
6.1 Message authentication
Recall: Integrity
Fundamental security property
u an asset is modified only by authorized parties u “I” in the CIA triad
“computer security seeks to prevent unauthorized viewing (confidentiality) or modification (integrity) of data while preserving access (availability)”
Alteration
u main threat against integrity of
in-transit data
u e.g., MITM attack
9
Security problems studied by modern cryptography
u Classical cryptography: message encryption u early crypto schemes tried to provide secrecy / confidentiality
u Modern cryptography: wide variety of security problems u today we need to study a large set of security properties beyond secrecy
u The sibling of message encryption: message authentication
u another cornerstone of any secure system aiming to provide authenticity & integrity
10
Message authentication: Motivation
Information has value, but only when it is correct
u random, incorrect, inaccurate or maliciously altered data is useless or harmful
u message authentication = message integrity + authenticity
u while in transit (or at rest), no message should be modified by an outsider u no outsider can impersonate the stated message sender (or owner)
u it is often necessary / worth to protect critical / valuable data u message encryption
u while in transit (or at rest), no message should be leaked to an outsider 11
Example 1
Secure electronic banking
u a bank receives an electronic request to transfer $1,000 from Alice to Bob Concerns
u who ordered the transfer, Alice or an attacker (e.g., Bob)?
u is the amount the intended one or was maliciously modified while in transit?
u adversarial Vs. random message-transmission errors
u standard error-correction is not sufficient to address this concern
12
Example 2
Web browser cookies
u a user is performing an online purchase at Amazon
u a “cookie” contains session-related info, as client-server HTTP traffic is stateless
u stored at the client, included in messages sent to server u containsclient-specificinfothataffectsthetransaction
u e.g.,theuser’sshoppingcartalongwithadiscountduetoacoupon Concern
u wassuchstatemaliciouslyalteredbytheclient(possiblyharmingtheserver)? 13
Integrity of communications / computations
Highly important
u any unprotected system cannot be assumed to be trustworthy w.r.t.
u origin/source of information (due to impersonation attacks, phishing, etc.)
u contents of information (due to man-in-the-middle attacks, email spam, etc.) u overall system functionality
Prevention Vs. detection
u unless system is “closed,” adversarial tampering with its integrity cannot be avoided!
u goal: identify system components that are not trustworthy u detect tampering or prevent undetected tampering
u e.g., avoid “consuming” falsified information 14
Encryption does not imply authentication
A common misconception
“since ciphertext c hides message m, Mallory cannot meaningfully modify m via c”
Why is this incorrect?
u all encryption schemes (seen so far) are based on one-time pad, i.e., masking via XOR u consider flipping a single bit of ciphertext c; what happens to plaintext m?
u such property of one-time pad does not contradict the secrecy definitions Generally, secrecy and integrity are distinct properties
u encrypted traffic generally provides no integrity guarantees
15
16
6.2 Message authentication codes (MACs)
Problem setting: Reliable communication
Two parties wish to communicate over a channel
u Alice (sender/source) wants to send a message m to Bob (recipient/destination) Underlying channel is unprotected
u Mallory (attacker/adversary) can manipulate any sent messages
u e.g., message transmission via a compromised router
Mallory Alice m m
m Bob
17
Solution concept: Symmetric-key message authentication
Main idea
u secretly annotate or “sign” message so that it is unforgeable while in transit
u Alice tags her message m with tag t, which is sent along with plaintext m u Bob verifies authenticity of received message using tag t
u Mallory can manipulate m, t but “cannot forge” a fake verifiable pair m’, t’ u Alice and Bob share a secret key k that is used for both operations
kk
REJECT
m Bob ACCEPT
Mallory Alice m tag/sign m,t
m’,t’
verify
18
Security tool: Symmetric Message Authentication Code
Abstract cryptographic primitive, a.k.a. MAC, defined by u a message space M; and
u a triplet of algorithms (Gen, Mac, Vrf)
u Gen, Mac are probabilistic algorithms, whereas Vrf is deterministic u Gen outputs a uniformly random key k (from some key space K)
M: set of possible messages
Gen
kk
REJECT
m’ Bob ACCEPT
Alice m
Mallory
Mac m,t
m’,t’
19
Vrf
Desired properties for MACs
By design, any MAC should satisfy the following
u efficiency: u correctness: u security:
M: set of possible messages
key generation & message transformations “are fast” for all m and k, it holds that Vrfk(m, Mack(m)) = ACCEPT one “cannot forge” a fake verifiable pair m’, t’
Gen
kk
REJECT
m Bob ACCEPT
Alice m
Mallory
Mac m,t
m’,t
20
Vrf
Main application areas
Secure communication
u verify authenticity of messages sent among parties
u assumption
u Alice and Bob securely generate,
distribute and store shared key k
u attacker does not learn key k Mallory
Secure storage
u verify authenticity of files outsourced to the cloud
u assumption
u Alice securely generates and stores
key k
u attacker does not learn key k Mallory
kkk
Alice Bob
messages
Alice
files
21
Conventions
Random key selection
u typically, Gen selects key k uniformly at random from the key space K
Canonical verification
u when Mac is deterministic, Vrf typically amounts to re-computing the tag t
u Vrfk(m, t): 1. t’ := Mack(m) 2. if t = t’, output ACCEPT else output REJECT u but conceptually the following operations are distinct
u authenticating m (i.e., running Mac) Vs. verifying authenticity of m (i.e., running Vrf)
22
MAC security
Attacker wins the game if (Gen, Mac, Vrf) m1
t1 m2
t2 …
1. Vrfk(m*,t*) = ACCEPT & 2. m* not in Q
MAC scheme
AMac(k, ) Q = m1, m2, …
T
Gen → k Mack(mi) → ti
m*,t*
The MAC scheme is secure if any PPT A wins the game only negligibly often. 23
24
6.3 Replay attacks
Recall: MAC
Abstract cryptographic primitive, a.k.a. MAC, defined by u a message space M; and
u a triplet of algorithms (Gen, Mac, Vrf)
M: set of possible messages
Gen
kk
REJECT
m’ Bob ACCEPT
Alice m
Mallory
Mac m,t
m’,t’
25
Vrf
Recall: MAC security
Attacker wins the game if (Gen, Mac, Vrf) m1
t1 m2
t2 …
1. Vrfk(m*,t*) = ACCEPT & 2. m* not in Q
MAC scheme
AMac(k, ) Q = m1, m2, …
T
Gen → k Mack(mi) → ti
m*,t*
The MAC scheme is secure if any PPT A wins the game only negligibly often. 26
Real-life attacker
In practice, an attacker may
u observe a traffic of authenticated (and successfully verified) messages u manipulate (or often also partially influences) traffic
u aims at inserting an invalid but verifiable message m*, t* into the traffic
u interesting case: forged message is a new (unseen) one
u trivial case: forged message is a previously observed one, a.k.a. a replay attack u launch a brute-force attack (given that Mack(m) → t is publicly known)
u given any observed pair m, t, exhaustively search key space to find the used key k 27
Threat model
In the security game, Mallory is an adversary A who is u “active” (on the wire)
u we allow A to observe and manipulate sent messages u “well-informed”
u we allow A to request MAC tags of messages of its choice u “replay-attack safe”
u we restrict A to forge only new messages u “PPT”
u we restrict A to be computationally bounded
u new messages may be forged undetectably only negligibly often
28
Notes on security definition
Is it a rather strong security definition?
u we allow A to query MAC tags for any message
u but real-world senders will authenticate only “meaningful” messages u we allow A to break the scheme by forging any new message
u but real-world attackers will forge only “meaningful” messages Yes, it is the right approach…
u message “meaningfulness” depends on higher-level application
u text messaging apps require authentication of English-text messages
u other apps may require authentication of binary files
u security definition should better be agnostic of the specific higher application
29
Notes on security definition (II)
Are replay attacks important in practice?
u absolutely yes: a very realistic & serious threat!
u e.g., what if a money transfer order is “replayed”?
Yet, a “replay-attack safe” security definition is preferable
u again, whether replayed messages are valid depends on higher-lever app u better to delegate to this app the specification of such details
u e.g., semantics on traffic or validity checks on messages before they’re “consumed” Eliminating replay attacks
u use of counters (i.e., common shared state) between sender & receiver
u use of timestamps along with a (relaxed) authentication window for validation 30
31
6.4 MAC constructions
Three generic MAC constructions
u fixed-length MAC
u direct application of a PRF for tagging u limited applicability
u domain extension for MACs
u straightforward secure extension of fix-length MAC u inefficient
u CBC-MAC
u resembles CBC-mode encryption u efficient
32
1. Fixed-length MAC
u based on use of a PRF
u employ a PRF Fk in the obvious way
to compute and canonically verify tags
u set tag t to be the pseudorandom string derived by evaluating Fk on message m
u secure, provided that Fk is a secure PRF
x
Fk
y = Fk(x)
MAC scheme Π
Gen(1n): {0,1}n → k Mack(m): set t = Fk(m)
Vrfyk(m,t): return 1 iff t = Fk(m)
33
2. Domain extension for MACs (I)
u suppose we have the previous fix-length MAC scheme
u how can we authenticate a message m of arbitrary length?
u naïve approach
u padmandviewitasdblocksm1,m2,…,md u separately apply MAC to block mi
m = m1 m2 md
u security issues
u reordering attack; verify block index, t = Fk(mi||i)
u truncation attack; verify message length δ = |m|, t = Fk(mi||i||δ)
u mix-and-match attack; randomize tags (using message-specific fresh nonce) 34
t=
Fk Fk … Fk
t1 =Fk(m1) t2 =Fk(m2) td =Fk(md)
2. Domain extension for MACs (II)
Final scheme
u assumes a secure MAC scheme for messages of size n u set tag of message m of size δ at most 2n/4 as follows
u choose fresh random nonce r of size n/4; view m as d blocks of size n/4 each
u separately apply MAC on each block, authenticating also its index, δ and nonce r
Security
u extension is secure, if Fk is a secure PRF
r||1||δ||m1 r||2||δ||m2 r||d||δ||md
Fk Fk…Fk 35t=r, t1, t2, td
3. CBC-MAC
Idea
u employ a PRF in a manner similar to CBC-mode encryption
Security
u extension is secure, if
u Fk is a secure PRF; and
u only fixed-length messages are authenticated
u messages of length equal to any multiple of n can be authenticated
u but this length need be fixed in advance u insecure, otherwise
36
3. CBC-MAC Vs. previous schemes
m
Fk
t = Fk(m)
u can authenticate longer messages than basic PRF-based scheme (1)
Scheme (1)
Scheme (2)
u more efficient than domain-extension MAC scheme (2)
37
r||1||δ||m1 r||2||δ||m1 r||d||δ||m1
Fk Fk…Fk t=r, t1, t2, td
3. CBC-MAC Vs. CBC-mode encryption
u crucially for their security
u CBC-MAC uses no IV (or uses an IV set to 0) and only the last PRF output u CBC-mode encryption uses a random IV and all PRF outputs
u “simple”, innocent modification can be catastrophic…
CBC-MAC
CBC-mode encryption
38
39
6.5 Hash functions
Cryptographic hash functions
Basic cryptographic primitive
u maps “objects” to a fixed-length binary strings
u core security property: mapping avoids collisions
input
arbitrarily
output
long string
u collision: distinct objects (x ≠ y) are mapped to the same hash value (H(x) = H(y))
short digest, fingerprint, “secure”
H
description
u although collisions necessarily exist, they are infeasible to find
Important role in modern cryptography
u lie between symmetric- and asymmetric-key cryptography
u capture different security properties of “idealized random functions” u qualitative stronger assumption than PRF
77
Hash & compression functions
Map messages to short digests
u a general hash function H() maps
u a message of an arbitrary length to a l(n)-bit string
input
arbitrarily long string
H
output
l(n)-bit string
u a compression (hash) function h() maps
u a long binary string to a shorter binary string
u an l’(n)-bit string to a l(n)-bit string, with l’(n) > l(n)
input
l’(n)-bit string
h
output
l(n)-bit string
41
Collision resistance (CR)
Attacker wins the game if x ≠ x’ & H(x) = H(x’)
description of H
x, x’
H is collision-resistant if any PPT A wins the game only negligibly often. 42
A
Hash function H
T
Weaker security notions
Given a hash function H: X ® Y, then we say that H is
u preimage resistant (or one-way)
u if given y Î Y, finding a value x Î X s.t. H(x) = y happens negligibly often
u 2-nd preimage resistant (or weak collision resistant)
u ifgivenauniformxÎX,findingavaluex’ÎX,s.t.x’1xandH(x’)=H(x)
happens negligibly often
u cf. collision resistant (or strong collision resistant)
u if finding two distinct values x’, x Î X, s.t. H(x’) = H(x) happens negligibly often 43
44
6.6 Design framework
Domain extension via the Merkle-Damgård transform
General design pattern for cryptographic hash functions
u reduces CR of general hash functions to CR of compression functions
input
H
u thus, in practice, it suffices to realize a collision-resistant compression function h
input
output
arbitrarily long string
output
≤ l’(n)-bit string
l(n)-bit string
l(n)-bit string
h
u compressing by 1 single bit is a least as hard as compressing by any number of bits!
45
Merkle-Damgård transform: Design
Suppose that h: {0,1}2n→ {0,1}n is a collision-resistant compression function Consider the general hash function H: M = {x : |x|<2n} → {0,1}n, defined as
Merkle-Damgård design
u H(x) is computed by applying h() in a “chained” manner over n-bit message blocks
u pad x to define a number, say B, message blocks x1, ..., xB, with |xi| = n
u set extra, final, message block xB+1 as an n-bit encoding L of |x|
u starting by initial digest z0 = IV = 0n, output H(x) = zB+1, where zi = hs(zi-1||xi)
46
Merkle-Damgård transform: Security
If the compression function h is CR,
then the derived hash function H is also CR!
47
Compression function design: The Davies-Meyer scheme
Employs PRF w/ key length m & block length n u define h: {0,1}n+m → {0,1}n as
h(x||k) = Fk(x) XOR x
Security
u hisCR,ifFisanidealcipher
48
Well known hash functions
u MD5 (designed in 1991)
u output 128 bits, collision resistance completely broken by researchers in 2004 u today (controlled) collisions can be found in less than a minute on a desktop PC
u SHA1 – the Secure Hash Algorithm (series of algorithms standardized by NIST) u output 160 bits, considered insecure for collision resistance
u broken in 2017 by researchers at CWI
u SHA2 (SHA-224, SHA-256, SHA-384, SHA-512)
u outputs 224, 256, 384, and 512 bits, respectively, no real security concerns yet u based on Merkle-Damgård + Davies-Meyer generic transforms
u SHA3(Kessac)
u completely new philosophy (sponge construction + unkeyed permutations)
49
SHA-2-512 overview
50
Current hash standards
51