Transcript Public Key

A Computer and Network
Security Primer
Dr. Marwan Abu-Amara
King Fahd University of Petroleum & Minerals
Computer Engineering Department
Thursday May 5, 2016
Slides Original Source:
Mark Stamp, “Information Security: Principles and Practice,” 2nd
edition, John Wiley (http://www.cs.sjsu.edu/~stamp/infosec/)
1

Introduction

Crypto
Outline
o Classical Crypto
o Crypto Requirements
o Crypto Taxonomy
 Symmetric Key

Stream cipher (A5/1, RC4, …)

Block cipher (DES, AES, …), modes (ECB, CBC, ...)
 Public Key (RSA, DH)

Network Security (Authentication Protocols)
o Phases
o Real-life protocols (SSH, SSL, IPSec, …)
2

Introduction

Crypto
Outline
o Classical Crypto
o Crypto Requirements
o Crypto Taxonomy
 Symmetric Key

Stream cipher (A5/1, RC4, …)

Block cipher (DES, AES, …), modes (ECB, CBC, ...)
 Public Key (RSA, DH)

Network Security (Authentication Protocols)
o Phases
o Real-life protocols (SSH, SSL, IPSec, …)
3
The Cast of Characters
 Alice
and Bob are the good guys
 Trudy
is the bad “guy”
 Trudy
is our generic “intruder”
4
Alice’s Online Bank
 Alice
 What
opens Alice’s Online Bank (AOB)
are Alice’s security concerns?
 If
Bob is a customer of AOB, what
are his security concerns?
 How
are Alice’s and Bob’s concerns
similar? How are they different?
 How
does Trudy view the situation?
5
CIA
 CIA
== Confidentiality, Integrity, and
_____Availability
 AOB
must prevent Trudy from
learning Bob’s account balance
 Confidentiality:
prevent unauthorized
reading of information
o Cryptography used for confidentiality
6
CIA
 Trudy
must not be able to change
Bob’s account balance
 Bob
must not be able to improperly
change his own account balance
 Integrity:
detect unauthorized
writing of information
o Cryptography used for integrity
7
CIA


AOB’s information must be available
whenever it’s needed
Bob must be able to make transaction
o If not, he’ll take his business elsewhere

Availability: Data is available in a timely
manner when needed
8
Beyond CIA: Crypto
 How
does Bob’s computer know that
“Bob” is really Bob and not Trudy?
 Bob’s
password must be verified
o This requires some clever cryptography
 What
 Are
are security concerns of pwds?
there alternatives to passwords?
9
Beyond CIA: Protocols




When Bob logs into AOB, how does AOB
know that “Bob” is really Bob?
As before, Bob’s password is verified
Unlike the previous case, network security
issues arise
How do we secure network transactions?
o Protocols are critically important
o Crypto plays critical role in protocols
10
Beyond CIA: Access Control

Once Bob is authenticated by AOB, then
AOB must restrict actions of Bob
o Bob can’t view Charlie’s account info
o Bob can’t install new software, etc.


Enforcing these restrictions: authorization
Access control includes both
authentication and authorization
11
The People Problem
 People
often break security
o Both intentionally and unintentionally
o Here, we consider the unintentional
 For
example, suppose you want to buy
something online
12
The People Problem
 To
buy from amazon.com…
o Your Web browser uses SSL protocol
o SSL relies on cryptography
o Access control issues arise
o All security mechanisms are in software
 Suppose
all of this security stuff
works perfectly
o Then you would be safe, right?
13
The People Problem
 What
could go wrong?
 Trudy tries man-in-the-middle attack
o SSL is secure, so attack doesn’t “work”
o But, Web browser issues a warning
o What do you, the user, do?
 If
user ignores warning, attack works!
o None of the security mechanisms failed
o But user unintentionally broke security
14

Introduction

Crypto
Outline
o Classical Crypto
o Crypto Requirements
o Crypto Taxonomy
 Symmetric Key

Stream cipher (A5/1, RC4, …)

Block cipher (DES, AES, …), modes (ECB, CBC, ...)
 Public Key (RSA, DH)

Network Security (Authentication Protocols)
o Phases
o Real-life protocols (SSH, SSL, IPSec, …)
15
Crypto
 Cryptology
 The art and science of
making and breaking “secret codes”
 Cryptography
 making “secret codes”
 Cryptanalysis
 breaking “secret codes”
 Crypto
 all of the above (and more)
16
How to Speak Crypto

A cipher or cryptosystem is used to encrypt
the plaintext

The result of encryption is ciphertext

We decrypt ciphertext to recover plaintext

A key is used to configure a cryptosystem

A symmetric key cryptosystem uses the same
key to encrypt as to decrypt

A public key cryptosystem uses a public key to
encrypt and a private key to decrypt
17
Crypto as Black Box
plaintext
key1
key2
encrypt
decrypt
plaintext
ciphertext
Crypto
Keys
Symmetric Key
key1 = key2
Public Key
key1  key2
18
Crypto

Basic assumptions
o The system is completely known to the attacker
o Only the key is secret (and, obviously, the plaintext!)
o Crypto algorithms are not secret!

This is known as Kerckhoffs’ Principle

Why do we make this assumption?
o Experience has shown that secret algorithms are
weak when exposed
o Secret algorithms never remain secret
o Better to find weaknesses beforehand
19

Introduction

Crypto
Outline
o Classical Crypto
o Crypto Requirements
o Crypto Taxonomy
 Symmetric Key

Stream cipher (A5/1, RC4, …)

Block cipher (DES, AES, …), modes (ECB, CBC, ...)
 Public Key (RSA, DH)

Network Security (Authentication Protocols)
o Phases
o Real-life protocols (SSH, SSL, IPSec, …)
20
1. Simple Substitution
 Shift
by n for some n  {0,1,2,…,25}
 Then
key is n
 Example:
Plaintext
key n = 7
a b c d e f g h i j k l m n o p q r s t u v w x y z
Ciphertext H I J K L M N O P Q R S T U V W X Y Z A B C D E F G
21
Cryptanalysis I: Try Them All

A simple substitution (shift by n) is used
o But the key is unknown

Given ciphertext: CSYEVIXIVQMREXIH

How to find the key?

Only 26 possible keys  try them all!

Exhaustive key search

Solution: key is n = 4
22
1. Simple Substitution (modified)

In general, simple substitution key can be
any permutation of letters
o Not necessarily a shift of the alphabet

For example
Plaintext a b c d e f g h i j k l m n o p q r s t u v w x y z
Ciphertext J I C A X S E Y V D K W B Q T Z R H F M P N U L G O

Then 26! > 288 possible keys!
23
Cryptanalysis II: Be Clever
Cannot try all 288 simple substitution keys
 Can we be more clever?
 English letter frequency counts…

0.14
0.12
0.10
0.08
0.06
0.04
0.02
0.00
A
C
E
G
I
K
M
O
Q
S
U
W
Y
24
2. One-Time Pad: Encryption
e=000 h=001 i=010 k=011 l=100 r=101 s=110 t=111
Encryption: Plaintext  Key = Ciphertext
h
e
i
l
h
i
t
l
e
r
Plaintext: 001 000 010 100 001 010 111 100 000 101
Key: 111 101 110 101 111 100 000 101 110 000
Ciphertext: 110 101 100 001 110 110 111 001 110 101
s
r
l
h
s
s
t
h
s
r
25
2. One-Time Pad: Decryption
e=000 h=001 i=010 k=011 l=100 r=101 s=110 t=111
Decryption: Ciphertext  Key = Plaintext
s
r
l
h
s
s
t
h
s
r
Ciphertext: 110 101 100 001 110 110 111 001 110 101
Key: 111 101 110 101 111 100 000 101 110 000
Plaintext: 001 000 010 100 001 010 111 100 000 101
h
e
i
l
h
i
t
l
e
r
26
One-Time Pad Summary

Provably secure…
o Ciphertext provides no info about plaintext
o All plaintexts are equally likely

…but, only when used correctly
o Pad must be random, used only once
o Pad is known only to sender and receiver

Note: pad (key) is same size as message
27
Codebook Cipher

Literally, a book filled with “codewords”

Zimmerman Telegram encrypted via codebook
Februar
13605
fest
13732
finanzielle
13850
folgender
13918
Frieden
17142
Friedenschluss
17149
:
:

Must not use the codebook over and over!

Modern block ciphers are codebooks!
28

Introduction

Crypto
Outline
o Classical Crypto
o Crypto Requirements
o Crypto Taxonomy
 Symmetric Key

Stream cipher (A5/1, RC4, …)

Block cipher (DES, AES, …), modes (ECB, CBC, ...)
 Public Key (RSA, DH)

Network Security (Authentication Protocols)
o Phases
o Real-life protocols (SSH, SSL, IPSec, …)
29
Crypto Requirements
Most importantly:
1.
Key should be long enough to make
exhaustive key search infeasible
2.
No shortcut attack
3.
No reuse of the key
30

Introduction

Crypto
Outline
o Classical Crypto
o Crypto Requirements
o Crypto Taxonomy
 Symmetric Key

Stream cipher (A5/1, RC4, …)

Block cipher (DES, AES, …), modes (ECB, CBC, ...)
 Public Key (RSA, DH)

Network Security (Authentication Protocols)
o Phases
o Real-life protocols (SSH, SSL, IPSec, …)
31
Crypto Taxonomy

Symmetric Key
o Same key for encryption and decryption
o Two types
 Stream ciphers
 Block ciphers

Public Key (or asymmetric crypto)
o Two keys, one for encryption (public), and one for
decryption (private)
o And digital signatures  nothing comparable in
symmetric key crypto

Crypto Hash algorithms (not covered here!)
o Can be viewed as “one way” crypto
32
Cryptanalysis Taxonomy

From perspective of info available to Trudy
o Ciphertext only
o Known plaintext
o Chosen plaintext
 “Lunchtime attack”
 Protocols might encrypt chosen data
o Adaptively chosen plaintext
o Related key
o Forward search (public key crypto)
o And others…
33

Introduction

Crypto
Outline
o Classical Crypto
o Crypto Requirements
o Crypto Taxonomy
 Symmetric Key

Stream cipher (A5/1, RC4, …)

Block cipher (DES, AES, …), modes (ECB, CBC, ...)
 Public Key (RSA, DH)

Network Security (Authentication Protocols)
o Phases
o Real-life protocols (SSH, SSL, IPSec, …)
34
Symmetric Key Crypto

Stream cipher  based on one-time pad
o Except that key is relatively short
o Key is stretched into a long keystream
o Keystream is used just like a one-time pad

Block cipher  based on codebook concept
o Block cipher key determines a codebook
o Each key yields a different codebook
35

Introduction

Crypto
Outline
o Classical Crypto
o Crypto Requirements
o Crypto Taxonomy
 Symmetric Key

Stream cipher (A5/1, RC4, …)

Block cipher (DES, AES, …), modes (ECB, CBC, ...)
 Public Key (RSA, DH)

Network Security (Authentication Protocols)
o Phases
o Real-life protocols (SSH, SSL, IPSec, …)
36
Stream Ciphers
Today, not as popular as block ciphers
 A5/1

o Based on shift registers
o Used in GSM mobile phone system

RC4
o Based on a changing lookup table
o Used in many places




WEP
WPA (default algorithm)
BitTorrent protocol encryption
…
37

Introduction

Crypto
Outline
o Classical Crypto
o Crypto Requirements
o Crypto Taxonomy
 Symmetric Key

Stream cipher (A5/1, RC4, …)

Block cipher (DES, AES, …), modes (ECB, CBC, ...)
 Public Key (RSA, DH)

Network Security (Authentication Protocols)
o Phases
o Real-life protocols (SSH, SSL, IPSec, …)
38
(Iterated) Block Cipher
 Plaintext
and ciphertext consist of
fixed-sized blocks
 Ciphertext
obtained from plaintext
by iterating a round function
 Input
to round function consists of
key and output of previous round
 Usually
implemented in software
39
Data Encryption Standard

DES developed in 1970’s

Based on IBM’s Lucifer cipher

DES was U.S. government standard

DES development was controversial
o NSA secretly involved
o Design process was secret
o Key length reduced from 128 to 56 bits
o Subtle changes to Lucifer algorithm
40
DES Numerology

DES uses
o 64 bit block length
o 56 bit key length
o 16 rounds
o 48 bits of key used each round (subkey)

Each round is simple (for a block cipher)

Security depends heavily on “S-boxes”
o Each S-boxes maps 6 bits to 4 bits
41
Security of DES

Security depends heavily on S-boxes
o Everything else in DES is linear


Thirty+ years of intense analysis has
revealed no “back door”
Attacks: essentially exhaustive key search
42
Block Cipher Notation

P = plaintext block

C = ciphertext block

Encrypt P with key K to get ciphertext C
o C = E(P, K)

Decrypt C with key K to get plaintext P
o P = D(C, K)

Note: P = D(E(P, K), K) and C = E(D(C, K), K)
o But P  D(E(P, K1), K2) and C  E(D(C, K1), K2) when
K1  K2
43
Triple DES (3DES)

Today, 56 bit DES key is too small
o Exhaustive key search is feasible

But DES is everywhere, so what to do?

Triple DES or 3DES (112 bit key)
o C = E(D(E(P,K1),K2),K1)
o P = D(E(D(C,K1),K2),K1)

Why Encrypt-Decrypt-Encrypt with 2 keys?
o Backward compatible: E(D(E(P,K),K),K) = E(P,K)
o And 112 bits is enough (is it?)
44
Advanced Encryption Standard

Replacement for DES

AES competition (late 90’s)
o NSA openly involved
o Transparent process
o Many strong algorithms proposed
o Rijndael Algorithm ultimately selected
(pronounced like “Rain Doll” or “Rhine Doll”)
45
AES Overview
 Block
size: 128 bits
 Key length: 128, 192 or 256 bits
(independent of block size)
 10 to 14 rounds (depends on key length)
 Each round uses 4 functions
o
o
o
o
ByteSub (nonlinear layer)
ShiftRow (linear mixing layer)
MixColumn (nonlinear layer)
AddRoundKey (key addition layer)
46

Introduction

Crypto
Outline
o Classical Crypto
o Crypto Requirements
o Crypto Taxonomy
 Symmetric Key

Stream cipher (A5/1, RC4, …)

Block cipher (DES, AES, …), modes (ECB, CBC, ...)
 Public Key (RSA, DH)

Network Security (Authentication Protocols)
o Phases
o Real-life protocols (SSH, SSL, IPSec, …)
47
Multiple Blocks

How to encrypt multiple blocks?

Do we need a new key for each block?
o As bad as (or worse than) a one-time pad!

Encrypt each block independently?

Make encryption depend on previous block?
o That is, can we “chain” the blocks together?

How to handle partial blocks?
o Padding (how?)
48
Modes of Operation
Many modes  we discuss 2 most popular
 Electronic Codebook (ECB) mode

o Encrypt each block independently
o Most obvious, but has a serious weakness

Cipher Block Chaining (CBC) mode
o Chain the blocks together
o More secure than ECB, virtually no extra work
49
Electronic Codebook (ECB) Mode

Notation: C = E(P,K)

Given plaintext P0,P1,…,Pm,…

Most obvious way to use a block cipher:
Encrypt
C0 = E(P0, K)
C1 = E(P1, K)
C2 = E(P2, K) …

Decrypt
P0 = D(C0, K)
P1 = D(C1, K)
P2 = D(C2, K) …
For fixed key K, this is “electronic” version
of a codebook cipher (without additive)
o With a different codebook for each key
50
ECB Weakness
 Suppose
 Then
Pi = Pj
Ci = Cj and Trudy knows Pi = Pj
 This
gives Trudy some information,
even if she does not know Pi or Pj
 Trudy
 Is
might know Pi
this a serious issue?
51
Alice Hates ECB Mode

Alice’s uncompressed image, and ECB encrypted

Why does this happen?

Same plaintext yields same ciphertext!
52
Cipher Block Chaining (CBC) Mode




Blocks are “chained” together
A random initialization vector, or IV, is
required to initialize CBC mode
IV is random, but not secret
Encryption
Decryption
C0 = E(IV  P0, K),
C1 = E(C0  P1, K),
C2 = E(C1  P2, K),…
P0 = IV  D(C0, K),
P1 = C0  D(C1, K),
P2 = C1  D(C2, K),…
Analogous to classic codebook with additive
53
CBC Mode


Identical plaintext blocks yield different
ciphertext blocks  this is good!
If C1 is garbled to, say, G then
P1  C0  D(G, K), P2  G  D(C2, K)

But P3 = C2  D(C3, K), P4 = C3  D(C4, K),…

Automatically recovers from errors!
54
Alice Likes CBC Mode

Alice’s uncompressed image, Alice CBC encrypted

Why does this happen?

Same plaintext yields different ciphertext!
55
Integrity
56
Data Integrity


Integrity  detect unauthorized writing
_________(i.e., modification of data)
Example: Inter-bank fund transfers
o Confidentiality may be nice, integrity is critical


Encryption provides confidentiality
(prevents unauthorized disclosure)
Encryption alone does not provide integrity
o One-time pad, cut-and-paste, etc.
57
MAC
 Message
Authentication Code (MAC)
o Used for data integrity
o Integrity not the same as confidentiality
 MAC
is computed as CBC residue
o That is, compute CBC encryption, saving
only final ciphertext block, the MAC
58
MAC Computation
 MAC
computation (assuming N blocks)
C0 = E(IV  P0, K),
C1 = E(C0  P1, K),
C2 = E(C1  P2, K),…
CN1 = E(CN2  PN1, K) = MAC
sent with IV and plaintext
 Receiver does same computation and
verifies that result agrees with MAC
 Note: receiver must know the key K
 MAC
59
Confidentiality and Integrity
Encrypt with one key, MAC with another key
 Using different keys to encrypt and
compute MAC works, even if keys are
related

o But, twice as much work as encryption alone
o Can do a little better  about 1.5 “encryptions”

Confidentiality and integrity with same work
as one encryption is a research topic
60

Introduction

Crypto
Outline
o Classical Crypto
o Crypto Requirements
o Crypto Taxonomy
 Symmetric Key

Stream cipher (A5/1, RC4, …)

Block cipher (DES, AES, …), modes (ECB, CBC, ...)
 Public Key (RSA, DH)

Network Security (Authentication Protocols)
o Phases
o Real-life protocols (SSH, SSL, IPSec, …)
61
Public Key Cryptography

Two keys
o Sender uses recipient’s public key to encrypt
o Recipient uses his own private key to decrypt

Based on “trap door one way function”
o “One way” means easy to compute in one direction,
but hard to compute in other direction
o Example: Given p and q, product N = pq easy to
compute, but given N, it’s hard to find p and q
o “Trap door” used to create key pairs
62
Public Key Cryptography

Encryption
o Suppose we encrypt M with Bob’s public key
o Bob’s private key can decrypt to recover M

Digital Signature
o Sign by “encrypting” with your private key
o Anyone can verify signature by “decrypting”
with public key
o But only you could have signed
o Like a handwritten signature, but way better…
63
RSA
64
RSA

Rivest, Shamir, and Adleman
o RSA is the gold standard in public key crypto
Let p and q be two large prime numbers
 Let N = pq be the modulus
 Choose e relatively prime to (p1)(q1)
 Find d such that ed = 1 mod (p1)(q1)

o i.e., d = e-1 mod (p1)(q1)
Public key is (N,e)
 Private key is d

65
RSA
Message M is treated as a number
e
 To encrypt M: C = M mod N
d
 To decrypt C: M = C mod N
 Recall that e and N are public, and d is private


If Trudy can factor N=pq, she can use e to
easily find d since ed = 1 mod (p1)(q1)
 Factoring the modulus breaks RSA
66
Simple RSA Example
 Example
of RSA
o Select “large” primes p = 11, q = 3
o Then N = pq = 33 and (p − 1)(q − 1) = 20
o Choose e = 3 (relatively prime to 20)
o Find d such that ed = 1 mod 20
 We find that d = 7 works
 Public
key: (N, e) = (33, 3)
 Private key: d = 7
67
Simple RSA Example

Public key: (N, e) = (33, 3)

Private key: d = 7

Suppose message M = 8

Ciphertext C is computed as
C = Me mod N = 83 = 512 = 17 mod 33

Decrypt C to recover the message M by
M = Cd mod N = 177 = 410,338,673
= 12,434,505  33 + 8 = 8 mod 33
68
Diffie-Hellman
69
Diffie-Hellman Key Exchange
A
“key exchange” algorithm
o Used to establish a shared symmetric key
 Not
for encrypting or signing
 Based on discrete log problem:
o Given: g, p, and gk mod p
o Find: exponent k
70
Diffie-Hellman

Let p be prime, let g be a generator

Alice selects her private value a

Bob selects his private value b

Alice sends (ga mod p) to Bob

Bob sends (gb mod p) to Alice

Both compute shared secret, (gab mod p)

Shared secret can be used as symmetric key
71
Diffie-Hellman


Suppose Bob and Alice use Diffie-Hellman
to determine symmetric key K = (gab mod p)
Trudy can see (ga mod p) and (gb mod p)
o But… ga gb mod p = ga+b mod p  gab mod p

If Trudy can find a or b, she gets key K
 If Trudy can solve discrete log problem, she
__can find a or b
72
Diffie-Hellman
Public: g and p
 Private: Alice’s exponent a, Bob’s exponent b

ga mod p
gb mod p
Alice, a
Bob, b
Alice computes (gb)a = gba = gab mod p
 Bob computes (ga)b = gab mod p
 Use K = (gab mod p) as symmetric key

73
Diffie-Hellman

Subject to man-in-the-middle (MiM) attack
Alice, a
ga mod p
gt mod p
gt mod p
gb mod p
Trudy, t
Bob, b
Trudy shares secret (gat mod p) with Alice
 Trudy shares secret (gbt mod p) with Bob
 Alice and Bob don’t know Trudy exists!

74
Diffie-Hellman

How to prevent MiM attack?
o Encrypt DH exchange with symmetric key
o Encrypt DH exchange with public key
o Sign DH values with private key
o Other

At this point, DH may look pointless…
o …but it’s not (more on this later)

In any case, you MUST be aware of MiM
attack on Diffie-Hellman
75
Public Key Notation
 Sign
message M with Alice’s private key:
[M]Alice
 Encrypt message M with Alice’s public key:
{M}Alice
 Then
{[M]Alice}Alice = M
[{M}Alice]Alice = M
76
Public Key Infrastructure
(PKI)
77
Public Key Certificate

Certificate contains:
o name of user
o user’s public key
o possibly other info

It is signed by the issuer (Certificate
Authority - CA), such as VeriSign
M = (Alice, Alice’s public key), S = [M]CA
 Alice’s Certificate = (M, S)

Signature on certificate is verified using CA’s
public key:
 Verify that M = {S}CA
78
Certificate Authority


CA is a trusted 3rd party (TTP)  creates
and signs certificates
Verify signature to verify integrity & identity
of owner of corresponding private key
o Does not verify the identity of the transmitter of
certificate  certificates are public keys!
79
PKI

Public Key Infrastructure (PKI): the stuff
needed to securely use public key crypto
o Key generation and management
o Certificate authority (CA) or authorities
o Certificate revocation lists (CRLs), etc.

No general standard for PKI

Based completely on “trust models”!
o Monopoly (single trusted CA)
o Oligarchy (multiple trusted CAs) – used in web browsers
o Anarchy (everyone is a CA!)
80
Symmetric Key vs Public Key
 Symmetric
key +’s
o Speed
o No public key infrastructure (PKI) needed
 Public
Key +’s
o Signatures (non-repudiation)
o No shared secret (but, private keys…)
81

Introduction

Crypto
Outline
o Classical Crypto
o Crypto Requirements
o Crypto Taxonomy
 Symmetric Key

Stream cipher (A5/1, RC4, …)

Block cipher (DES, AES, …), modes (ECB, CBC, ...)
 Public Key (RSA, DH)

Network Security (Authentication Protocols)
o Phases
o Real-life protocols (SSH, SSL, IPSec, …)
82
Cryptographic Random Numbers

Random numbers used to generate keys
o Symmetric keys
o RSA: Prime numbers
o Diffie Hellman: secret values
o Authentication protocols

Random numbers also used in simulations,
statistics, etc.
o Such numbers need to be “statistically” random

Cryptographic random numbers must be
statistically random and unpredictable
83
Identify Friend or Foe (IFF) – Case 1
Country 2
Friend
E(Friend,K)
K
Country 1
K
84
(IFF – Case 1) Attack
Country 2
Foe
MiG
E(Friend,K)
Country 1
K
85
Identify Friend or Foe (IFF) – Case 2
Foe
MiG
Country 2
2. E(N,K)
Friend
K
1. N
Country 1
K
86
(IFF – Case 2) “MiG” in the Middle Attack
3. N
Friend
K
4. E(N,K)
Country 2
2. N
5. E(N,K)
Foe
MiG
6. E(N,K)
1. N
Country 1
K
87
Authentication Protocol
Requirements


IFF-Case 1  Must prove freshness of answer
(prevents replay attacks)
IFF-Case 2  Must prevent one party from
doing the work of the other party
88
Challenge-Response

To prevent replay, use challenge-response
o Goal is to ensure “freshness”

Can use crypto. random numbers as challenge

Suppose Bob wants to authenticate Alice
o Challenge sent from Bob to Alice

Challenge is chosen so that…
o Replay is not possible
o Only Alice can provide the correct response
o Bob can verify the response
89

Introduction

Crypto
Outline
o Classical Crypto
o Crypto Requirements
o Crypto Taxonomy
 Symmetric Key

Stream cipher (A5/1, RC4, …)

Block cipher (DES, AES, …), modes (ECB, CBC, ...)
 Public Key (RSA, DH)

Network Security (Authentication Protocols)
o Phases
o Real-life protocols (SSH, SSL, IPSec, …)
90
Authentication Protocols & Phases

Alice must prove her identity to Bob
o Alice and Bob can be humans or computers
May also require Bob to prove he’s Bob
(mutual authentication)
 Probably need to establish a session key

 Phases of a secure network protocol:
Authentication (one-way or mutual) using symmetric or
public key  establish session key
2. Encrypt/Decrypt data exchanged using established
session key
1.
91
Authentication: Symmetric Key
 Alice
 Key
and Bob share symmetric key K
K known only to Alice and Bob
 Authenticate
by proving knowledge of
shared symmetric key
 How
to accomplish this?
o Cannot reveal key, must not allow replay
(or other) attack, must be verifiable, …
92
Notation Reminder
 Public
key notation
o Sign M with Alice’s private key
 [M]Alice
o Encrypt M with Alice’s public key  {M}Alice
 Symmetric
key notation
o Encrypt P with symmetric key K  C = E(P,K)
o Decrypt C with symmetric key K  P = D(C,K)
93
One-way Authentication with
Symmetric Key
“I’m Alice”
R
Alice, K
E(R,K)
Bob, K

Secure method for Bob to authenticate Alice

Alice does not authenticate Bob

So, can we achieve mutual authentication?
94
Mutual Authentication
“I’m Alice”, RA
RB, E(RA, K)
Alice, K
E(RB, K)
Bob, K

This provides mutual authentication…

…or does it? See the next slide
95
Mutual Authentication Attack
1. “I’m Alice”, RA
2. RB, E(RA, K)
Bob, K
Trudy
3. “I’m Alice”, RB
4. RC, E(RB, K)
Trudy
Bob, K
96
Symmetric Key Mutual
Authentication
“I’m Alice”, RA
RB, E(“Bob”,RA,K)
E(“Alice”,RB,K)
Alice, K
Bob, K

Do these “insignificant” changes help?

Yes!
97
Session Key

Usually, a session key is required
o i.e., a symmetric key for a particular session
o Used for confidentiality and/or integrity

How to authenticate and establish a
session key (i.e., shared symmetric key)?
o When authentication completed, want Alice and
Bob to share a session key
o Trudy cannot break the authentication…
o …and Trudy cannot determine the session key
98
Public Key Authentication
and Session Key
“I’m Alice”, R
{[R,K]Bob}Alice
Alice

{[R +1,K]Alice}Bob
Bob
Mutual authentication and session key!
99

Introduction

Crypto
Outline
o Classical Crypto
o Crypto Requirements
o Crypto Taxonomy
 Symmetric Key

Stream cipher (A5/1, RC4, …)

Block cipher (DES, AES, …), modes (ECB, CBC, ...)
 Public Key (RSA, DH)

Network Security (Authentication Protocols)
o Phases
o Real-life protocols (SSH, SSL, IPSec, …)
100
Secure Shell (SSH)
101
SSH
 Creates
a “secure tunnel”
 Insecure command sent thru SSH
tunnel are then secure
 SSH used with things like rlogin
o Why is rlogin insecure without SSH?
o Why is rlogin secure with SSH?
 SSH
is a relatively simple protocol
102
SSH
 SSH
authentication can be based on:
o Public keys, or
o Digital certificates, or
o Passwords
 Here,
we consider certificate mode
o Other modes, see homework problems
 We
consider slightly simplified SSH…
103
Simplified SSH
Alice, CP, RA
CS, RB
Alice





ga mod p
gb mod p, certificateB, SB
E(Alice, certificateA, SA, K)
Bob
CP = “crypto proposed”, and CS = “crypto selected”
H = h(Alice,Bob,CP,CS,RA,RB,ga mod p,gb mod p,gab mod p)
SB = [H]Bob
SA = [H, Alice, certificateA]Alice
K = gab mod p
104
MiM Attack on SSH?
Alice, RA
Alice, RA
RB
ga mod p
RB
gt mod p
gt mod p, certB, SB
Alice E(Alice,certA,SA,K)


Trudy
gb mod p, certB, SB
E(Alice,certA,SA,K)
Bob
Where does this attack fail?
Alice computes:
o Ha = h(Alice,Bob,CP,CS,RA,RB,ga mod p,gt mod p,gat mod p)

But Bob signs:
o Hb = h(Alice,Bob,CP,CS,RA,RB,gt mod p,gb mod p,gbt mod p)
105
Secure Socket Layer
106
Socket layer


“Socket layer”
lives between
application
and transport
layers
SSL usually
between HTTP
and TCP
 HTTPS
Socket
“layer”
application
User
transport
OS
network
link
NIC
physical
107
What is SSL?
SSL is the protocol used for majority of
secure transactions on the Internet
 For example, if you want to buy a book at
amazon.com…

o You want to be sure you are dealing with Amazon
(authentication)
o Your credit card information must be protected
in transit (confidentiality and/or integrity)
o As long as you have money, Amazon does not
care who you are
o So, no need for mutual authentication
108
Simplified SSL Protocol
Can we talk?, cipher list, RA
certificate, cipher, RB
{S}Bob, E(h(msgs,CLNT,K),K)
Alice
h(msgs,SRVR,K)
Data protected with key K
Bob
S is known as pre-master secret
 K = h(S,RA,RB)
 “msgs” means all previous messages
 CLNT and SRVR are constants

109
SSL Authentication

Alice authenticates Bob, not vice-versa
o How does client authenticate server?
o Why would server not authenticate client?

Mutual authentication is possible: Bob
sends certificate request in message 2
o Then client must have a valid certificate
o But, if server wants to authenticate client,
server could instead require password
110
SSL MiM Attack?
RA
certificateT, RB
Alice


{S1}Trudy,E(X1,K1)
h(Y1,K1)
E(data,K1)
RA
certificateB, RB
Trudy
{S2}Bob,E(X2,K2)
h(Y2,K2)
E(data,K2)
Bob
Q: What prevents this MiM “attack”?
A: Bob’s certificate must be signed by a
certificate authority (CA)

What does browser do if signature not valid?

What does user do when browser complains?
111
Thank You! …
… Questions?
112
IPSec
113
IPSec and SSL
IPSec lives at
the network
layer
 IPSec is
transparent to
applications

SSL
IPSec
application
User
transport
OS
network
link
NIC
physical
114
IPSec and Complexity

IPSec is a complex protocol

Over-engineered
o Lots of (generally useless) features

Flawed
o Some significant security issues

Interoperability is serious challenge
o Defeats the purpose of having a standard!

Complex

And, did I mention, it’s complex?
115
IKE and ESP/AH
Two parts to IPSec
 IKE: Internet Key Exchange

o Mutual authentication
o Establish session key
o Two “phases”

 like SSL session/connection
ESP/AH
o ESP: Encapsulating Security Payload
 for
encryption and/or integrity of IP packets
o AH: Authentication Header
 integrity only
116
IKE
117
IKE

IKE has 2 phases
o Phase 1  IKE security association (SA)
o Phase 2  AH/ESP security association

Phase 1 is comparable to SSL session

Phase 2 is comparable to SSL connection

Not an obvious need for two phases in IKE

If multiple Phase 2’s do not occur, then it
is more costly to have two phases!
118
IKE Phase 1

Four different “key” options
o Public key encryption (original version)
o Public key encryption (improved version)
o Public key signature
o Symmetric key

For each of these, two different “modes”
o Main mode and aggressive mode
There are 8 versions of IKE Phase 1!
 Need more evidence it’s over-engineered?

119
IKE Phase 1

We discuss 6 of 8 Phase 1 variants
o Public key signatures (main & aggressive modes)
o Symmetric key (main and aggressive modes)
o Public key encryption (main and aggressive)

Why public key encryption and public key
signatures?
o Always know your own private key
o May not (initially) know other side’s public key
120
IKE Phase 1

Uses ephemeral Diffie-Hellman to
establish session key
o Provides perfect forward secrecy (PFS)

Let a be Alice’s Diffie-Hellman exponent

Let b be Bob’s Diffie-Hellman exponent

Let g be generator and p prime

Recall that p and g are public
121
IKE Phase 1: Digital Signature
(Main Mode)
IC, CP
IC,RC, CS
IC,RC, ga mod p, RA
Alice





IC,RC, gb mod p, RB
IC,RC, E(“Alice”, proofA, K)
IC,RC, E(“Bob”, proofB, K)
Bob
CP = crypto proposed, CS = crypto selected
IC = initiator “cookie”, RC = responder “cookie”
K = h(IC,RC,gab mod p,RA,RB)
SKEYID = h(RA, RB, gab mod p)
proofA = [h(SKEYID,ga mod p,gb mod p,IC,RC,CP,“Alice”)]Alice
122
IKE Phase 1: Public Key
Signature (Aggressive Mode)
IC, “Alice”, ga mod p, RA, CP
IC,RC, “Bob”, RB,
gb mod p, CS, proofB
Alice

IC,RC, proofA
Bob
Main difference from main mode
o Not trying to protect identities
o Cannot negotiate g or p
123
Main vs Aggressive Modes

Main mode MUST be implemented

Aggressive mode SHOULD be implemented
o So, if aggressive mode is not implemented, “you
should feel guilty about it”

Might create interoperability issues

For public key signature authentication
o Passive attacker knows identities of Alice and
Bob in aggressive mode, but not in main mode
o Active attacker can determine Alice’s identity
in main mode
124
IKE Phase 1: Symmetric Key
(Main Mode)
IC, CP
IC,RC, CS
IC,RC, ga mod p, RA
Alice
KAB

IC,RC, gb mod p, RB
IC,RC, E(“Alice”, proofA, K)
IC,RC, E(“Bob”, proofB, K)
Bob
KAB
Same as signature mode except
o
o
o
o
KAB = symmetric key shared in advance
K = h(IC,RC,gab mod p,RA,RB,KAB)
SKEYID = h(K, gab mod p)
proofA = h(SKEYID,ga mod p,gb mod p,IC,RC,CP,“Alice”)
125
Problems with Symmetric
Key (Main Mode)

Catch-22
o Alice sends her ID in message 5
o Alice’s ID encrypted with K
o To find K Bob must know KAB
o To get KAB Bob must know he’s talking to Alice!

Result: Alice’s ID must be IP address!

Useless mode for the “road warrior”

Why go to all of the trouble of trying to
hide identities in 6 message protocol?
126
IKE Phase 1: Symmetric Key
(Aggressive Mode)
IC, “Alice”, ga mod p, RA, CP
IC,RC, “Bob”, RB,
gb mod p, CS, proofB
Alice
IC,RC, proofA
Bob

Same format as digital signature aggressive mode

Not trying to hide identities…

As a result, does not have problems of main mode

But does not (pretend to) hide identities
127
IKE Phase 1: Public Key
Encryption (Main Mode)
IC, CP
IC,RC, CS
IC,RC, ga mod p, {RA}Bob, {“Alice”}Bob
IC,RC, gb mod p, {RB}Alice, {“Bob”}Alice
Alice





IC,RC, E(proofA, K)
IC,RC, E(proofB, K)
Bob
CP = crypto proposed, CS = crypto selected
IC = initiator “cookie”, RC = responder “cookie”
K = h(IC,RC,gab mod p,RA,RB)
SKEYID = h(RA, RB, gab mod p)
proofA = h(SKEYID,ga mod p,gb mod p,IC,RC,CP,“Alice”)
128
IKE Phase 1: Public Key
Encryption (Aggressive Mode)
IC, CP, ga mod p,
{“Alice”}Bob, {RA}Bob
IC,RC, CS, gb mod p,
{“Bob”}Alice, {RB}Alice, proofB
Alice
IC,RC, proofA
Bob
K, proofA, proofB computed as in main mode
 Note that identities are hidden

o The only aggressive mode to hide identities
o So, why have a main mode?
129
Public Key Encryption Issue?

In public key encryption, aggressive mode…

Suppose Trudy generates
o Exponents a and b
o Nonces RA and RB


Trudy can compute “valid” keys and proofs:
gab mod p, K, SKEYID, proofA and proofB
This also works in main mode
130
Public Key Encryption Issue?
IC, CP, ga mod p,
{“Alice”}Bob, {RA}Bob
IC,RC, CS, gb mod p,
{“Bob”}Alice, {RB}Alice, proofB
Trudy
as Alice
IC,RC, proofA
Trudy
as Bob
Trudy can create exchange that appears to
be between Alice and Bob
 Appears valid to any observer, including
Alice and Bob!

131
Plausible Deniability
Trudy can create “conversation” that
appears to be between Alice and Bob
 Appears valid, even to Alice and Bob!
 A security failure?
 In this IPSec key option, it is a feature…

o Plausible deniability: Alice and Bob can deny
that any conversation took place!

In some cases it might create a problem
o E.g., if Alice makes a purchase from Bob, she
could later repudiate it (unless she had signed)
132
IKE Phase 1 Cookies

IC and RC  cookies (or “anti-clogging
tokens”) supposed to prevent DoS attacks
o No relation to Web cookies



To reduce DoS threats, Bob wants to remain
stateless as long as possible
But Bob must remember CP from message 1
(required for proof of identity in message 6)
Bob must keep state from 1st message on
o So, these “cookies” offer little DoS protection
133
IKE Phase 1 Summary

Result of IKE phase 1 is
o Mutual authentication
o Shared symmetric key (i.e., session key)
o IKE Security Association (SA)

But phase 1 is expensive
o Especially in public key and/or main mode

Developers of IKE thought it would be used
for lots of things  not just IPSec
o Partly explains the over-engineering…
134
IKE Phase 2

Phase 1 establishes IKE SA

Phase 2 establishes IPSec SA

Comparison to SSL
o SSL session is comparable to IKE Phase 1
o SSL connections are like IKE Phase 2

IKE could be used for lots of things…

…but in practice, it’s not!
135
IKE Phase 2
IC,RC,CP,E(hash1,SA,RA,K)
IC,RC,CS,E(hash2,SA,RB,K)
Alice






IC,RC,E(hash3,K)
Bob
Key K, IC, RC and SA known from Phase 1
Proposal CP includes ESP and/or AH
Hashes 1,2,3 depend on SKEYID, SA, RA and RB
Keys derived from KEYMAT = h(SKEYID,RA,RB,junk)
Recall SKEYID depends on phase 1 key method
Optional PFS (ephemeral Diffie-Hellman exchange)
136
IPSec

After IKE Phase 1, we have an IKE SA

After IKE Phase 2, we have an IPSec SA

Both sides have a shared symmetric key

Now what?
o We want to protect IP datagrams

But what is an IP datagram?
o Considered from the perspective of IPSec…
137
IP Review

IP datagram is of the form
IP header

data
Where IP header is
138
IP and TCP
 Consider
Web traffic
o IP encapsulates TCP and…
o …TCP encapsulates HTTP
IP header
data
IP header
TCP hdr
 IP
HTTP hdr
app data
data includes TCP header, etc.
139
IPSec Transport Mode

IPSec Transport Mode
IP header data
IP header
ESP/AH
data

Transport mode designed for host-to-host

Transport mode is efficient
o Adds minimal amount of extra header

The original header remains
o Passive attacker can see who is talking
140
IPSec: Host-to-Host
 IPSec
transport mode
 There
may be firewalls in between
o If so, is that a problem?
141
IPSec Tunnel Mode

IPSec Tunnel Mode
IP header data
new IP hdr
ESP/AH
IP header data

Tunnel mode for firewall-to-firewall traffic

Original IP packet encapsulated in IPSec

Original IP header not visible to attacker
o New IP header from firewall to firewall
o Attacker does not know which hosts are talking
142
IPSec: Firewall-to-Firewall
 IPSec
tunnel mode
 Local
networks not protected
 Is there any advantage here?
143
Comparison of IPSec Modes
 Transport
Mode

o Host-to-host
IP header data

IP header
 Tunnel
ESP/AH
Mode
firewall


ESP/AH
IP header data
Tunnel Mode
o Firewall-to-
data
IP header data
new IP hdr
Transport Mode
Transport Mode
not necessary…
…but it’s more
efficient
144
IPSec Security

What kind of protection?
o Confidentiality?
o Integrity?
o Both?

What to protect?
o Data?
o Header?
o Both?

ESP/AH do some combinations of these
145
AH vs ESP

AH  Authentication Header
o Integrity only (no confidentiality)
o Integrity-protect everything beyond IP header
and some fields of header (why not all fields?)

ESP  Encapsulating Security Payload
o Integrity and confidentiality both required
o Protects everything beyond IP header
o Integrity-only by using NULL encryption
146
ESP’s NULL Encryption

According to RFC 2410
o NULL encryption “is a block cipher the origins of
o
o
o
o
o

which appear to be lost in antiquity”
“Despite rumors”, there is no evidence that NSA
“suppressed publication of this algorithm”
Evidence suggests it was developed in Roman
times as exportable version of Caesar’s cipher
Can make use of keys of varying length
No IV is required
Null(P,K) = P for any P and any key K
Bottom line: Security people can be strange
147
Why Does AH Exist? (1)

Cannot encrypt IP header
o Routers must look at the IP header
o IP addresses, TTL, etc.
o IP header exists to route packets!

AH protects immutable fields in IP header
o Cannot integrity protect all header fields
o TTL, for example, will change

ESP does not protect IP header at all
148
Why Does AH Exist? (2)



ESP encrypts everything beyond the IP
header (if non-null encryption)
If ESP-encrypted, firewall cannot look at
TCP header (e.g., port numbers)
Why not use ESP with NULL encryption?
o Firewall sees ESP header, but does not know
whether null encryption is used
o End systems know, but not the firewalls
149
Why Does AH Exist? (3)
 The
real reason why AH exists:
o At one IETF meeting “someone from
Microsoft gave an impassioned speech
about how AH was useless…”
o “…everyone in the room looked around and
said `Hmm. He’s right, and we hate AH
also, but if it annoys Microsoft let’s leave
it in since we hate Microsoft more than we
hate AH.’ ”
150