CS306: Introduction to IT Security Fall 2020
Lecture 7: Public-key Cryptography
Instructor: Nikos Triandopoulos October 20, 2020
2
7.0 Announcements
CS306: Announcements
u HW2 did not come – too much in view of next week’s midterm exam 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
u online exam, quiz format
u accommodations to be provided as needed
u covers all materials discussed so far: lectures 1-7, labs 1-7, HW1 u Lab 7 will offer a general revision on most important topics
u exact list of topics to be provided tomorrow
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
Lecture 6
Lab 5
–
Oct 13
No class (Monday schedule)
Lab 6
7
Oct 20
Public-key cryptography
Lecture 7
Lab 7, HW2
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
Two weeks ago
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
6
Today
u Revision on message authentication & cryptographic hashing u Practical applications
u authenticated encryption, hash functions security strength, HMAC u Public-key (PK) cryptography
u Motivation, PK Infrastructure, PK encryption, digital signatures
u Discrete log problem, DH key agreement, hybrid encryption u Demo
u The length-extension attack…
7
8
7.1 Public-key encryption & digital signatures
Recall: Principles of modern cryptography
(A) security definitions, (B) precise assumptions, (C) formal proofs For symmetric-key message encryption/authentication
u adversary
u types of attacks
u trusted set-up
u secret key is distributed securely u secret key remains secret
u trust basis
u underlying primitives are secure u PRG, PRF, hashing, …
Alice m
kk
encrypt c c decrypt kk
m Bob
u e.g., block ciphers, AES, SHA-2, etc. 9
Alice m
“sign”
m, t
m’, t’
verify
rej
acc
Bob
On “secret key is distributed securely”
Alice & Bob (or 2 individuals) must securely obtain a shared secret key
u “securely obtain”
u need of a secure channel
u “shared secret key” u too many keys
strong assumption to accept challenging problem to manage
Public-key cryptography to the rescue…
10
On “secret key is distributed securely”
Alice & Bob (or 2 individuals) must securely obtain a shared secret key
u “securely obtain”
(A) strong assumption to accept
u requires secure channel for key distribution (chicken & egg situation) u seems impossible for two parties having no prior trust relationship
u not easily justifiable to hold a priori
u “shared secret key”
(B) challenging problem to manage
u requires too many keys, namely O(n2) keys for n parties to communicate u imposes too much risk to protect all such secret keys
u entails additional complexities in dynamic settings (e.g., user revocation)
11
Alternative approaches?
Need to securely distribute, protect & manage many session-based secret keys
u (A) for secure distribution, just “make another assumption…” u employ “designated” secure channels
u physically protected channel (e.g., meet in a “sound-proof” room) u employ “trusted” party
u entities authorized to distribute keys (e.g., key distribution centers (KDCs)) u (B) for secure management, just ‘live with it!”
Public-key cryptography to the rescue…
12
Public-key (or asymmetric) cryptography
disclaimer on names private = secret
Goal: devise a cryptosystem where key setup is “more” manageable
Main idea: user-specific keys (that come in pairs) u user U generates two keys (Upk, Usk)
u Upk is public – it can safely be known by everyone (even by the adversary)
u Usk is private – it must remain secret Usage
u employ public key Upk for certain “public” tasks
u employ private key Usk for certain “sensitive” tasks
Assumption
(even from other users) (performed by other users)
(performed by user U)
u public-key infrastructure (PKI): public keys become securely available to users 13
From symmetric to asymmetric encryption
secret-key encryption u mainlimitation
u session-specific keys public-key encryption
u main flexibility
u user-specific keys
kk
Alice m encrypt c
c decrypt m Bob
Alice m
BobPK encrypt
c
BobSK
c decrypt m Bob “sensitive” task
u messages encrypted by receiver’s PK can (only) be decrypted by receiver’s SK 14
From symmetric to asymmetric message authentication
secret-key message authentication (or MAC) u mainlimitation k
u session-specific keys Alice m “sign” public-key message authentication
m, t
m, t
k rej verify Bob
(or digital signatures) u main flexibility
u user-specific keys
AliceSK
Alice m sign “sensitive” task
acc
AlicePK rej verify
acc
u (only) messages signed by sender’s SK can be verified by sender’s PK 15
m,σ
m,σ
Bob
Thus: Principles of modern cryptography
(A) security definitions, (B) precise assumptions, (C) formal proofs For asymmetric-key message encryption/authentication
u adversary
u types of attacks
u trusted set-up
u PKI is needed
u secret keys remain secret
Alice m
BobPK encrypt
AliceSK
c
c
BobSK
decrypt m Bob AlicePK rej
u trust basis
u underlying primitives are secure
u typically, algebraic computationally-hard problems
u e.g., discrete log, factoring, etc.
16
m, t
m, t
verify
Alice m
“sign”
Bob
acc
General comparison
Symmetric crypto
u key management
u less scalable & riskier
u assumptions
u secret & authentic communication u secure storage
u primitives
u generic assumptions
u more efficiently in practice
Asymmetric crypto
u key management
u more scalable & simpler
u assumptions
u authenticity (PKI) u secure storage
u primitives
u math assumptions
u less efficiently in practice (2-3 o.o.m.)
17
Public-key infrastructure (PKI)
A mechanism for securely managing, in a dynamic multi-user setting, user-specific public-key pairs (to be used by some public-key cryptosystem)
u dynamic, multi-user
u the system is open to anyone; users can join & leave
u user-specific public-key pairs
u each user U in the system is assigned a unique key pair (Upk, Usk)
u secure management (e.g., authenticated public keys)
u public keys are authenticated: current Upk of user U is publicly known to everyone
Very challenging to realize
u currently using digital certificates; ongoing research towards a better approach…
18
Overall: Public-key encryption & signatures
Assume a trusted set-up
u publickeysaresecurelyavailable(PKI)&secretkeysremainsecret
Bpk
Alice m encrypt Ask
Alice m sign
c
c
Bsk
decrypt
Apk
verify
m Bob
m, σ
m, σ
Bob
A
rej
19
acc
Secret-key vs. public-key encryption
20
Public-key cryptography: Early history
Proposed by Diffie & Hellman
u u u
documented in “New Directions in Cryptography” (1976)
solution concepts of public-key encryption schemes & digital signatures key-distribution systems
Diffie-Hellman key-agreement protocol
u “reduces” symmetric crypto to asymmetric crypto
u
Public-key encryption was earlier (and independently) proposed by James Ellis u classified paper (1970)
u published by the British Governmental Communications Headquarters (1997)
u concept of digital signature is still originally due to Diffie & Hellman
21
22
7.2 Public-key certificates
How to set up a PKI?
u How are public keys stored? How to obtain a user’s public key?
u How does Bob know or ‘trust’ that APK is Alice’s public key?
u How APK (a bit-string) is securely bound to an entity (user/identity)?
public key: APK secret key: ASK
public key: BPK secret key: BSK
23
Achieving a PKI…
How can we maintain the invariant that at all times
u any given user U is assigned a unique public-private key pair; and u any other user known U’s current public key?
u secret keys can be lost, stolen or they should be revoked Recall
entails binding users/identities
to public keys
u PK cryptosystems come with a Gen algorithm which is run by U
u on input a security-strength parameter, it outputs a random valid key pair for U
u public keys can be made publicly available
u e.g., sent by email, published on web page, added into a public directory, etc.
24
Distribution of public keys
Public announcement
u users distribute public keys to recipients or broadcast to community at large Publicly available directory
u can obtain greater security by registering keys with a public directory Both approaches have problems and are vulnerable to forgeries
25
Do you trust your public key?
u Impostor claims to be a true party
u true party has a public and private key
u impostor also has a public and private key
u Impostor sends impostor’s own public key to the verifier u says, “This is the true party’s public key”
u this is the critical step in the deception
26
Certificates: Trustable identities & public keys
Certificate
u a public key & an identity bound together
u in a document signed by a certificate authority
Certificate authority (CA)
u an authority that users trust to securely bind identity to public keys
u CA verifies identities before generating certificates for these identities u secure binding via digital signatures
u ASSUMPTION: The authority’s PK CAPK is authentic 27
Public-key certificates in practice
Current (imperfect) practice for achieving trustable identities & public keys u everybody trusts a Certificate Authority (CA)
u everybody knows PKCA & trusts that CA knows the corresponding secret key CASK u a certificate binds identities to public keys in a CA-signed statement
u e.g., Alice obtains a signature on the statement “Alice’s public key is 1032xD” u users query CA for public keys of intended recipients or signers
u e.g., when Bob wants to send an encrypted message to Alice u he first obtains & verifies a certificate of Alice’s public key
u e.g., when Alice wants to verify the latest software update by Company u she first obtains & verifies a certificate of Company’s public key
28
Example
a certificate is a public key and an identity bound together and signed by a certificate authority (CA)
a certificate authority is an authority that users trust to accurately verify identities before generating certificates that bind those identities to keys
29
document signed by CA
Certificate hierarchy
Single CA certifying every public key is impractical
Instead, use trusted root certificate authorities
u root CA signs certificates for intermediate CAs, they sign certificates for lower-level CAs, etc.
u certificate “chain of trust”
u sigSymantec(“Stevens”, PKStevens) u sigUMD(“faculty”, PKfaculty)
u sigfaculty(“Nikos”, PKNikos)
30
Example 1: Certificate signing & hierarchy
To create Diana’s certificate:
Diana creates and delivers to Edward:
Edward adds:
Edward signs with his private key:
Which is Diana’s certificate.
To create Delwyn’s certificate:
Delwyn creates and delivers to Diana:
Diana adds:
Diana signs with her private key:
And appends her certificate:
Name: Diana
Position: Division Manager Public key: 17EF83CA …
Name: Diana
Position: Division Manager Public key: 17EF83CA …
hash value 128C4
Name: Delwyn
Position: Dept Manager Public key: 3AB3882C …
hash value 48CFA
Name: Diana
Position: Division Manager Public key: 17EF83CA …
hash value 128C4
Name: Delwyn Position: Dept Manager Public key: 3AB3882C …
hash value 48CFA
Name: Delwyn Position: Dept Manager Public key: 3AB3882C …
hash value 48CFA
Name: Diana
Position: Division Manager Public key: 17EF83CA …
hash value 128C4
31
Name: Delwyn
Position: Dept Manager Public key: 3AB3882C …
W hich is Delwyn’s certificate.
Example 2
Symantec
Rutgers staff Stevens
32
Faculty Nikos
What bad things can happen if the root CA system is compromised?
Secure communication over the Internet
What cryptographic keys are used to protect communication?
33
https://
X.509 certificates
Defines framework for authentication services
u defines that public keys stored as certificates in a public directory u certificates are issued and signed by a CA
Used by numerous applications: SSL
Example: see certificates accepted by your browser
34
35
7.3 Hybrid encryption
Secret-key cryptography is “reduced” to public-key
PK encryption can be used “on-the-fly” to securely distribute session keys
Main idea: Leverage PK encryption to securely distribute session keys
u sender generates a fresh session-specific secret key k and learns receiver’s public key Rpk u session key k is sent to receiver encrypted under key Rpk
u session key k is employed to run symmetric-key crypto
u e.g., how not to run above protocol
1
3
Bill, give me your public key
Here is my key, Amy 2
Here is a symmetric key we can use
36
.4,1 5abc2 6de3f pqr7s ghi tuv8jkl wxym9zno
4. , a5b c d6e f p 7q r s t 8u v w 9x y z
Hybrid encryption
“Reduces” secret-key crypto to public-key crypto
u better performance than block-based public-key CPA-encryption u main idea
u apply PK encryption on random key k u use k for secret-key encryption of m
37
Hybrid encryption using the KEM/DEM approach
“Reduces” secret-key crypto to public-key crypto
u main idea
u encapsulate secret key k into c
u use k for secret-key encryption of m
u KEM: key-encapsulation mechanism – Encaps u DEM: data encapsulation mechanism – Enc’
u KEM/DEM scheme
u CPA-secure if KEM is CPA-secure and Enc’ EAV-secure u CCA-secure if KEM and Enc’ are CCA-secure
38
39
7.4 The Discrete Log problem & its applications
The discrete logarithm problem
Setting
u ifpbeanoddprime,thenG=(Zp*,·)isacyclicgroupoforderp–1
u Zp* = {1, 2, 3, …, p-1}, generated by some g in Zp*
u for i = 0, 1, 2, …, p-2, the process gi mod p produces all elements in Zp*
u foranyxinthegroup,wehavethatgk modp=x,forsomeintegerk u k is called the discrete logarithm (or log) of x (mod p)
Example
u (Z17*,·)isacyclicgroupGwithorder16,3isthegeneratorofGand316=1mod17 u letk=4,34=13mod17(whichiseasytocompute)
u the inverse problem: if 3k = 13 mod 17, what is k? what about large p? 40
Computational assumption
Discrete-log setting
u cyclic G = (Zp*, ·) of order p – 1 generated by g, prime p of length t (|p|=t)
Problem
u given G, g, p and x in Zp*, compute the discrete log k of x (mod p)
u weknowthatx=gk modpforsomeuniquekin{0,1,…,p-2}…but
Discrete log assumption
u for groups of specific structure, solving the discrete log problem is infeasible u any efficient algorithm finds discrete logs negligibly often (prob = 2-t/2)
Brute force attack
u cleverly enumerate and check O(2t/2) solutions 41
ElGamal encryption
Assumes discrete-log setting (cyclic G = (Zp*, ·) =
Gen
u secret key: random number x Î Z*p public key: A = gx mod p, along w/ G, g, p Enc
u pickafreshrandomrÎZ*pandsetR=Ar (=gxr)
u send ciphertext EncPK(m) = (c1, c2) where c1 = gr, c2= m · R mod p
Dec
u DecSK(c1,c2) = c2 (1/c1x) mod p where c1x = gxr
Security is based on Computational Diffie-Hellman (CDH) assumption u given (g, ga,gb) it is hard to compute gab
A signature scheme can be also derived based on above discussion
42
Application: Key-agreement (KA) scheme
Alice and Bob want to securely establish a shared key for secure chatting over an insecure line u instead of meeting in person in a secret place, they want to use the insecure line…
u KA scheme: they run a key-agreement protocol Π to contribute to a shared key K
u correctness: KA = KB
u security: no PPT adversary A, given T, can distinguish K from a trully random one
Alice
Bob
input 1n
output K
input 1n
A
…
transcript T of exchanged messages 43
output K
A
B
Key agreement: Game-based security definition
u scheme Π(1n) runs to generate K = KA = KB and transcript T; random bit b is chosen
u adversary A is given T and kb; if b = 1, then kb = K, else kb is random (both n-bit long) u Aoutputsbitb’andwinsifb’=b
u then: Π is secure if no PPT A wins non-negligibly often
(A) Alice
(D) output b’
(E) A wins iff b’ = b
Bob
input 1n output K
A (C) T, kb …
input 1n
output K
A
(B) b is randomly chosen
transcript T of exchanged messages 44
B
The Diffie-Hellman key-agreement protocol
Alice and Bob want to securely establish a shared key for secure chatting over an insecure line u DH KA scheme Π
u discrete log setting: p, g public, where
input 1n
(1) randomly pick secret a (3) send ga mod p
(4) send gb mod p
Bob
input 1n
(2) randomly pick secret b
(5)setK=gab modp=(gb modp)a modp
45
(6)setK=gab modp=(ga modp)bmodp
Security
u discrete log assumption is necessary but not sufficient u decisional DH assumption
u given g, ga and gb, gab is computationally indistinguishable from uniform
46
Authenticated Diffie-Hellman
ga mod p MITM attacker gc mod p
gc mod p
gb mod p
Alice computes gac mod p and Bob computes gbc mod p !!!
Alice CA Bob
Yes Yes CAlice, ga mod p, SignAlice(ga mod p) CBob, gb mod p, SignBob(gb mod p)
Is CAlice Alice’s certificate?
Is CBob Bob’s certificate?
47