Transcript Why: m - Faculty Personal Homepage

Network Security
 Taken mostly from “Network and Internetwork
Security” William Stallings 1995
 Overview
 Conventional encryption
 Confidentiality using conventional encryption
 Public-Key Cryptography
 Authentication and Digital Signatures
 Intruders
 Practice
Network Security
1
Overview
 What do we want to achieve?
Bob
Alice
Trudy
Network Security
2
Security Services
 Confidentiality
 Authentication
 Integrity
 Non-repudiation
 Access Control
 Availability
Network Security
3
Confidentiality
 The data must be hidden
Trudy cannot see the message
 Trudy cannot seen that a message was sent

 How long must confidentiality be
preserved?
Network Security
4
Authentication
 Are the receiver and sender who they
claim to be?
Am I really talking to Bob?
 Is that really Alice telling me that she no
longer loves me?

Network Security
5
Integrity
 Ensure the entire message is transmitted,
and nothing in addition to the entire
message
Alice says “Please buy 100 shares of Nortel”
 Bob see “Please buy 100,000 shares of Nortel”

Network Security
6
Non-Repudiation
 After the message is transmitted and
received, neither party can deny that fact

“No, really, I certainly did not order 100,000
shares of Nortel at $125 per share last March.”
 Note: Alice and Bob do not necessarily
trust each other!
Network Security
7
Access Control
 Control access to hosts and applications

Everything looks like its from Alice, but it turns
out that Trudy has broken into Alice’s machine
and successfully emulated Alice
Network Security
8
Availability
 The communication channel must remain
open

“That’s odd, I haven’t heard from Alice in three
weeks, and she usually calls me twice a day.”
Network Security
9
Security Threats
 Passive Attacks

Content observation
• “I wonder want people would think if they knew what
Alice and Bob were planning?”

Traffic Analysis
• “Gee, the American third battalion was transmitting
more and more information, and then they suddenly
ceased all communication.”
Network Security
10
Interruption
 Trudy prevents Alice from talking to Bob
Bob
Alice
Trudy
Network Security
11
Interception
 Trudy overhears Alice’s message
Bob
Alice
Trudy
Network Security
12
Modification
 Trudy changes Alice’s message
Bob
Alice
Trudy
Network Security
13
Fabrication
 Trudy send a message claiming to be from
Alice
Bob
Alice
Trudy
Network Security
14
Conventional Encryption Model
 AKA:
Symmetric
 shared-key
 single-key
 private-key

 Plaintext: the original message
 Ciphertext: the encrypted message
 Secret key: the key used to encrypt and
decrypt the message
Network Security
15
Model
X?
Cryptanalyst
K?
Message
Source
X
Encrypt
Insecure Channel
Y
X
decrypt
Message
Destination
Secret Key
Secure Channel
Network Security
16
Conventional Encryption Model
 Message Source: X = [X1,X2, … XM]
 M elements are over some finite alphabet
 Y = [Y1,Y2, … YN]
 Y = EK(X)
 X = DK(Y)
Network Security
17
The Opponent: Cryptanalyst
 Kerchoff’s Principle

The security of a cryptosystem must not
depend on keeping the algorithm secret
 Types of Attack:
 Ciphertext
only
 Known plaintext
 Chosen plaintext
Network Security
18
Degree of Security
 Unconditionally secure
The ciphertext does not contain sufficient
information to uniquely determine the
corresponding plaintext
 One time pad

 Computationally secure
 The cost of breaking the cipher exceeds the
value of the encrypted information
 The time required exceeds the useful lifetime
of the information
Network Security
19
Classical Encryption Techniques
 Steganography:
“Covered Writing”
 Examples:

•
•
•
•
•
•

Character marking
Invisible ink
Pin punctures
Use low-order bits of image encoding
Communication frequency
Etc.
Drawbacks:
• Fails Kerchoff’s principle!
Network Security
20
Steganography
 (a) Three zebras and a tree. (b)
Three zebras, a tree, and the
complete text of five plays by
William Shakespeare.
Network Security
21
Cryptography
 Operation types:

Substitution v. Transposition
 Number of keys
 1: private key, symmetric, secret- or single-key
 2: public key, asymmetric, two-key
 Data processing
 Block v. Stream
Network Security
22
Substitution
 Caesar
 Monoalphabetic
 Multi-letter
 Polyalphabetic

One-time pad
Network Security
23
Caesar Cipher
Meet me after the toga party
 Phhw pd diwhu wkh wrjd sduwb

 C = E(p) = (p+k)mod(26)
 For the above, k = 3
 p = D(C) = (C-k)mod(26)
Network Security
24
Caesar Security
 Vulnerable to brute-force attack
Algorithms are known
 25 possible keys
 Language of plaintext is known

Network Security
25
Monoalphabetic Ciphers
 Use arbitrary substitution
 Key is then 26 character mapping
 26! (>4x1026) possible keys
 (DES has only 256 or >7x1016 keys)
 So what is
 UZQSOVUOHXMOPVGP … ?
Network Security
26
How Secure is Monoalphabet?
 Vulnerable to letter-frequency analysis
 In English:
 E 12.75%
 T 9.25%
 R 8.50%
 Etc.
 Based on frequency of letters in ciphertext, make
tentative assignment
 Then move to digraph and trigraph frequency
analysis

E.g. “t?e” is probably “the”
Network Security
27
Better Monoalphabets
 Use homophones
E.g. use several different mappings for the
letter “e”
 This eliminates the single-letter frequency
information
 But it doesn’t eliminate digraph, trigraph, etc.
frequency information

 The basic problem is that the ciphertext is
maintaining the structure of the original
Network Security
28
Multi-letter encryption
 Monoalphabet:
E(l): L -> L
E(l1 l2 … lN): LN -> LN
 Multiletter:
 Playfair algorithm:
• Given a key “monarchy” create the following table
M
C
E
L
O
H
F
P
N
Y
G
Q
A
B
I/J
S
R
D
K
T
U
V
W
X
Z
Network Security
29
Multi-letter encryption
 Encode letter pairs as follows:
 Letter pairs with duplicate letters are
separated by a filler letter
 If letters are on the same row, use the letter
to the right
 If letters are in the same column, use the
letter below
 Otherwise, form a square and use the other
corners
 Thus: “bad grade” first becomes
 “ba” “’dg” “ra” “de”
 And then: “IB” “YK” “MR” “KC”
Network Security
30
Is Playfair Any Good?
 Digraphs are harder to identify
 Considered unbreakable for a long time
 Used by British in WWI
 US Army in WWII
 Actually relatively easy to break

Letter frequencies are still far from equal
Network Security
31
Polyalphabetic Ciphers
 Use a set of monoaphabetic ciphers
 Key determines which cipher is used for
which letter
 Vigenere cipher
a is shift by 0, b is shift by 1, etc.
 Now use a keyword repetitively to determine
the encoding
 Thus “deceptive” encoding “wearediscovered”
produces “ZICVTWQNGRZGVTW”

Network Security
32
Breaking Polyalphabetic Ciphers
 First determine key length

E.g. sequence VTW is repeated at length 9
• Therefore length is either 3 or 9
 Then we have a key length monoalphabetic
ciphers
 Use autokey system:
The key specifies the initial encoding
 The remainder is determined by the message
 Problem: key and plaintext share same letter
frequency distribution

Network Security
33
One-Time Pad
 Vernam (1918)
 ci
= pi XOR ki
 Theoretically unbreakable
 Why?
 Because if we have a message of length N, and
we try all possible keys, we will simply generate
all possible messages of length N.
 Thus: “Attack at dawn” could also decode to
“Eat a Big Mac!” using brute force attack
Network Security
34
One-Time Pad
 So why not use it everywhere?
Key size
 Key distribution
 Correctly generating random key
 Must destroy pad after use

• Why?
Network Security
35
Transposition
 Reorder letter sequence
 Rail fence
 E.g. “meet me at the toga party” with rail fence
of length 4 becomes
ME E T
MMTOAEEHGREAEATTTTPY
ME A T
T HE T
OG A P
AR TY
 Trivial to cryptanalyze
Network Security
36
Transposition
 Improvements
Use a key to permute the columns
 Thus using key 4312 to permute the columns,
we get

• TTTPYEAEATMMTOAEEHGR
Doesn’t help much, because the letter
frequencies remain the same and the structure
is still fairly close to the original
 Look at the letter positions:

• 4 8 12 16 20 3 7 11 15 19 1 5 9 13 17 2 6 10 14 18
Network Security
37
Multistage Transposition
 Re-encode the ciphertext using the same
(or a different!) key
Thus, if we re-encode using the 4312 key, we
get PEMERTAMAGTYATETETOH
 Which has the letter positions

• 16 11 5 2 18 12 7 1 17 14 4 20 15 9 6 8 3 19 13 10
T T T P
Y E A E
A T M M
T O A E
E H G R
4
8 12 16
20 3 7 11
15 19 1 5
9 13 17 2
6 10 14 18
Network Security
38
Rotor Machines
 Single rotor is a monoalphabet that rotates
by one after each key input
 Thus equivalent to polyalphabet with period
equal to size of alphabet
 Concatenate rotors, and rotate at
different speeds
Thus inner rotor rotates one per key press
 Next rotor rotates one per inner rotor rotation
 For three rotors, 26x26x26 = 17,576 different
substitution alphabets before repetition

Network Security
39
Data Encryption Standard (DES)
 FIPS PUB 46 (1977)
 See http://www.itl.nist.gov/fipspubs/fip46-2.htm
 Encrypts 64-bit blocks using a 56-bit key
 Same steps, same key to decrypt
 Started as project LUCIFER, used 128-bit key,
for Lloyd’s of London
 Reduced key size to 56 bits to fit on chip
 Two complaints:


Key size reduction
S-box structure was classified
Network Security
40
64-bit plaintext
56-bit key
Initial Permutation
Permuted Choice 1
Iteration 1
Iteration 16
K1
K16
Permuted Choice 2
Left Circular Shift
Permuted Choice 2
Left Circular Shift
32-bit swap
Inverse Initial
Permutation
64-bit ciphertext
Network Security
41
Operations
 Initial Permutation and Inverse Initial
Permutations follow the rule:

X = IIP(IP(X))
 They probably add nothing to the strength
of DES
Network Security
42
Li = R i-1
Ri = Li-1 (+) f(Ri-1,Ki)
Network Security
43
Dealing With Keys First
Permuted choice 1 and 2
and the left-shifts are
specified by the standard.
Permuted choice 2 throws
away bits 9, 18, 22, 25, 35,
38, 43, and 54 yielding a
key of length 48 bits.
Network Security
44
A Single Iteration of f(R,K)
E = Expansion
P = Permute
S = S Boxes
(Each of these is
specified by the
standard)
Network Security
45
DES Decryption
 Runs the encryption process in the same
way, except the sequence of 48-bit keys
(K1 to K16) is applied in the reverse order

Recall
• Li = Ri-1
• Ri = Li-1 (+) f(Ri-1,Ki)

Thus
• Ri-1 = Li
• Li-1 = Ri (+) f(Ri-1,Ki) = Ri (+) f(Li,Ki)
Network Security
46
Avalanche Effect
 A small change in plaintext or key should
cause a large change in ciphertext
 DES exhibits this well

A single bit change in the key or plaintext
results in around half of the ciphertext bits
changing
Network Security
47
Concerns about DES
 256 possible keys
 Brute-force attack with special-purpose
hardware (costing around $250,000) EEF
cracked DES encrypted text in 56 hours
(1998)

Note: this would require knowledge of the
plaintext nature so as to automate detection of
a valid output
Network Security
48
Differential Cryptanalysis
 First reported in open literature in 1990
 Chosen plaintext attack where the effect
of the difference between plaintext
choices is observed through the DES
operation, to enable probably key
determination
 DES is fairly secure against such attacks
due to the S-Boxes and the permutation
after each iteration
 Requires 247 rounds with 247 chosen texts
Network Security
49
Modes of Operation
 Electronic Codebook (EBC)

Each block encoded independently
 Cipher Block Chaining (CBC)
 XOR each block of plaintext with ciphertext of
previous block
 At decryption, XOR ciphertext of previous
block with decrypted output
 Need initialization vector for first block
Network Security
50
Cipher Block Chaining Mode
 Cipher block chaining. (a) Encryption. (b)
Decryption.
Network Security
51
Modes of Operation
 Cipher Feedback (CFB)
Used for streaming data – j bits at a time
 Start with initialization vector and encrypt
 Select j bits of output

• This is XORed with the plaintext for transmission
• This j-bit ciphertext is shifted into the IV for
computing the next j-bit output
• Decryption is the same process
 Output Feedback (OFB)
 Almost same as CFB, but don’t XOR before
shifting for next encryption
Network Security
52
Cipher Feedback Mode
 (a) Encryption. (c) Decryption.
Network Security
53
Stream Cipher Mode
 A stream cipher. (a) Encryption. (b)
Decryption.
Network Security
54
Counter Mode
 Encryption using counter mode.
Network Security
55
Triple DES
 DES maps 264 -> 264
 How do we know that C = Ek1(Ek2(P)) is not
equivalent to C = Ek3(P)?
Because for each key we must get a unique
mapping, where there are (264)! Possible
permutations of input blocks
 (Note, this is evidence, not proof ; Proof came
in 1992)

Network Security
56
So Why Not Double DES?
 Meet in the middle attack
 Given known plaintext/ciphertext pair:
 Encrypt P for all possible keys K1
 Decrypt C for all possible keys K2
 Check for matches. These are possible keys
• Check against another plaintext/ciphertext pair
 Requires O(256) work
 Also requires O(256) space!
Network Security
57
Triple DES
 C = Ek1(Dk2(Ek1(P)))
 Why this way?
 Because if K1 = K2 then it reduces to DES
 112-bit key
 No known practical attack on Triple DES
Network Security
58
So What Do We Do With DES?
 What do we encrypt?
 Where do we encrypt?
 How do we distribute keys?
Network Security
59
What and Where?
 The network is generally considered to be
untrustworthy

Broadcast LANs
• Ethernet
• 802.11
Physical penetration to wiring closet
 Interception of Microwave and Satellite
communication
 Separate authority domains

Network Security
60
Link v. End to End
 Link:
 How?
• Encrypt all link-layer traffic
• Decrypt and re-encrypt at routers to enable
forwarding
 Advantages
• Network addresses (thus ultimate destination) is not
visible
• One key per link

Disadvantages
• Every network provider must provide it
– But can still see message in the clear at the router
• Every customer gets it, whether they need it or not
Network Security
61
End-to-End Encryption
 How?
 Source encrypts
 Final destination decrypts
 Advantages
 Only those who need it use it
 Intermediate routers cannot decrypt
 User authentication
 Easy to change encryption scheme
 Disadvantages
 Anyone can see the final destination
 One key per communicating pair
 Key distribution is more problematic
 What layer? Network? Transport? Application?
Network Security
62
Key Distribution
 If I always use the same key, then if that
key is compromised, all prior communication
is compromised
 Need
frequent key exchange
 System is only as secure as key distribution
scheme
Network Security
63
Basic Schemes
 Alice gives Bob the key
 Alice gives her faithful friend Trish Trudy
Peterson (TTP) the key to deliver to Bob
 Alice uses the previous key to encrypt the
new key and send it to Bob
 Alice and Trish share a key KA. Bob and
Trish share a key KB. Trish delivers a key
K to Alice and Bob allowing them to
communicate
Network Security
64
Key Distribution Centre (KDC)
 Alice tell Trish that she wishes to talk to Bob




(encrypted with KA)
Trish responds with a KA-encrypted message
containing K, Time, and a KB-encrypted copy of K,
Alice’s identity, and the Time
Alice sends Bob the KB-encrypted message
together with her K-encrypted message
Bob decrypts the KB-encrypted messages,
extracts K and can then decrypt Alice’s message
The time information is verified to ensure that
this is not a replay-attack
Network Security
65
KDC in Pictures
KDC
1
Alice
2
3
Bob
4
5
Network Security
66
How do I scale a KDC?
 Hierarchical Key Control
Each KDC is responsible for a small domain
 KDCs the communicate using the next level in
the hierarchy

Master KDC
2
3
Alice’s KDC
4
Bob’s KDC
5
1
Alice
6
Bob
Network Security
67
Public Key Cryptography
symmetric key crypto
 requires sender,
receiver know
shared secret key
 Q: how to agree on
key in first place
(particularly if
never “met”)?
 Though this same
problem appears
to some extent in
public-key
cryptography
public key cryptography
 radically different
approach [DiffieHellman76, RSA78]
 sender, receiver do
not share secret key
 encryption key public
(known to all)
 decryption key
private (known only to
receiver)
Network Security
68
Public key cryptography
Figure 7.7 goes here
Network Security
69
Public Key Requirements
 Computationally easy to
generate eB, dB
 compute eB(M)
 compute dB(eB(M))

 Computationally infeasible to compute
 dB given eB and eB (M) for an arbitrary number
of messages M
 M given eB and eB(M)
 Nice to have
 eB(dB(M)) = dB(eB(M)) = M
Network Security
70
Diffie-Hellman Key Exchange
 Given a large prime, q, and r < q is r
primitive root of q

r is a primitive root iff for all z < q, rz mod(q)
are distinct integers
 Then, Alice selects private ka < q and
calculates public pa = rkamod(q)
 Likewise, Bob selects private kb < q and
calculates public pb = rkbmod(q)
 Public keys are exchanged
Network Security
71
Session Key
 Session key K = (pb)ka mod(q) = (pa)kb mod(q)
 Proof
 (pb)ka mod(q) = (rkbmod(q))ka mod(q)
= (rkb)ka mod(q)
= (rkb x ka mod(q)
= (rka)kb mod(q)
= (rkamod(q))kb mod(q)
= (pa)kb mod(q)
Network Security
72
Comments on Diffie-Hellman
 Security comes from the fact that
computing discrete logarithms is hard

That is, given knowledge of q, r and rkmod(q) it
is not feasible to compute private key k
 Do not need to use the same value for
private key every time
 Vulnerable to (wo)man-in-the-middle attack
Network Security
73
Rivest-Shamir-Adelman (RSA)
1. Choose two large prime numbers p, q.
(e.g., 1024 bits each)
2. Compute n = pq, z = (p-1)(q-1)
3. Choose e (with e<n) that has no common factors
with z. (e, z are “relatively prime”).
4. Choose d such that ed-1 is exactly divisible by z.
(in other words: ed mod z = 1 ).
5. Public key is (n,e). Private key is (n,d).
Network Security
74
RSA: Encryption, decryption
0. Given (n,e) and (n,d) as computed above
1. To encrypt bit pattern, m, compute
e
e
c = m mod n (i.e., remainder when m is divided by n)
2. To decrypt received bit pattern, c, compute
d
m = c d mod n (i.e., remainder when c is divided by n)
Observe:
m = (m e mod n)
d
mod n
Network Security
75
RSA example:
Bob chooses p=5, q=7. Then n=35, z=24.
e=5 (so e, z relatively prime).
d=29 (so ed-1 exactly divisible by z.
encrypt:
decrypt:
letter
m
me
l
12
1524832
c
17
d
c
481968572106750915091411825223072000
c = me mod n
17
m = cd mod n letter
12
l
Extension: Use RSA to exchange keys,
Use DES to converse
Network Security
76
Computational Aspects
 Note that when we compute cdmod(n) we do
not need to do the full computation of cd
and the divide by n to see the remainder
 Why?
 cdmod(n) = c2c(d-2)mod(n)
= c2mod(n)c(d-2)mod(n)
 Better: cdmod(n) = (c2)(d/2)mod(n)
= (c2mod(n))(d/2)mod(n)
Network Security
77
RSA: Why:
m = (m e mod n)
d
mod n
Number theory result: If p,q prime, n = pq, then
y
y mod (p-1)(q-1)
x mod n = x
mod n
e
(m mod n) d mod n = medmod n
= m
ed mod (p-1)(q-1)
mod n
(using number theory result above)
1
= m mod n
(since we chose ed to be divisible by
(p-1)(q-1) with remainder 1 )
= m
Network Security
78
Key Management
 Distribution of public keys
How to distribute
 How to revoke

 Use of public-keys to distribute secret
keys
Network Security
79
Distribution of Public Keys
 Public announcement
 Key authority
 Certificates
 Web of Trust
Network Security
80
Public Announcement
 Send the key to other participants
 Append public key on all e-mail (PGP)
 Place on web-page
 Problem:

Forged announcement
Network Security
81
Key Authority
 Have a publicly available directory
containing a name/public key database
Keys must be registered with authority
securely
 Key replacement by the same secure mechanism

 Alice requests Bob’s public key from
directory
Directory responds with encrypted (using
directory’s private key) copy of Bob’s key, the
original request, and the original message
timestamp
 Bob’s key can be kept for future use

Network Security
82
Certificates
 Do not want to contact key authority every
time we need a public key
 Solution:

a certificate that contains
• Public key
• Proof that the public key originates with the
certificate authority
Only the CA can create a certificate
 Any participant can verify the certificate

Network Security
83
Basic Mechanism for Certificate
 Certificate authority encrypts (using its
private key) the following three things:
Timestamp
 Identity of Alice
 Public Key of Alice

 Alice may now give this certificate to Bob
 Bob will decrypt the certificate using the
public key of the CA

Bob now has public key for Alice that can only
have been provided by the CA
Network Security
84
Certificates
 A possible certificate and its signed hash.
Network Security
85
X.509
 The basic fields of an X.509 certificate.
Network Security
86
Certificate Chains
 As with the KDC hierarchy, we do not wish
to all have to go to one location to get
certificates
Root CA (e.g. Verisign)
 CAs ‘R’ Us
 Root CA generates certificate for CAs ‘R’ Us
 CAs ‘R’ Us generates certificate for Bob
 Alice has public key for Root

• Uses it to determine public key for CAs ‘R’ Us
• Which can then be used to determine public key for
Bob
Network Security
87
Public-Key Infrastructures
 (a) A hierarchical PKI. (b) A chain of
certificates.
Network Security
88
Web of Trust
 Anyone can create such a certificate
 Bob and Trish were at a party, and Trish
created such a certificate for Bob’s public
key
 Alice and Trish were at a different party,
and Trish gave Alice a copy of her public
key
 Alice uses Trish’s public key to decode the
certificate from Bob
Network Security
89
Web of Trust (2)
 Trish knows Alice and Mary
Alice has Trish’s public key
 Trish creates a certificate for Mary’s public
key

 Mary knows Bob
 Mary creates a certificate for Bob’s public key
 Alice can now follow the chain to determine
Bob’s public key
Network Security
90
PPP: Particularly Paranoid People
 Select multiple independent sources for
certificates
 If they all agree on the public key, then it
is probably valid
 This applies to both certificate authorities
and web of trust
Network Security
91
Key Revocation
 What happens when Alice’s key is
compromised?
 Solutions:
Use short-durations certificates
 Use revocation lists from certificate
authorities

Network Security
92
Attacks
 Get the private key of the root authority
 Compromise client software
 Change the self-signing certificate
 Capture the decrypted output
 Etc.
Network Security
93
Secret Keys
 Problem:
Public-key encryption is computationally slow
 DES is relatively fast

 Use PKE to exchange a DES key, and then
use DES to exchange data
 More on this when we discuss
authentication and digital signatures
Network Security
94
Authentication and Digital
Signatures
 Requirements
 No disclosure
 No masquerade
 No replay
 No sequence modification
 No timing modification
 No repudiation
 Functions
 Encryption
 Cryptographic Checksum
 Hash Function
Network Security
95
Authentication
Goal: Bob wants Alice to “prove” her identity
to him
Protocol ap1.0: Alice says “I am Alice”
Failure scenario??
Network Security
96
Authentication: another try
Protocol ap2.0: Alice says “I am Alice” and sends her IP
address along to “prove” it.
Failure scenario??
Network Security
97
Authentication: another try
Protocol ap3.0: Alice says “I am Alice” and sends her
secret password to “prove” it.
Failure scenario?
Network Security
98
Authentication: yet another try
Protocol ap3.1: Alice says “I am Alice” and sends her
encrypted secret password to “prove” it.
I am Alice
encrypt(password)
Failure scenario?
Network Security
99
Authentication: yet another try
Goal: avoid playback attack
Nonce: number (R) used only once in a lifetime
ap4.0: to prove Alice “live”, Bob sends Alice nonce, R. Alice
must return R, encrypted with shared secret key
Figure 7.11 goes here
Failures, drawbacks?
Network Security
100
Authentication: ap5.0
ap4.0 requires shared symmetric key
problem: how do Bob, Alice agree on key
 can we authenticate using public key techniques?

ap5.0: use nonce, public key cryptography
Figure 7.12 goes here
Network Security
101
ap5.0: security hole
Man (woman) in the middle attack: Trudy poses
as Alice (to Bob) and as Bob (to Alice)
Figure 7.14 goes here
Network Security
102
Digital Signatures
Cryptographic technique
analogous to handwritten signatures.
Simple digital signature
for message m:
 Sender (Bob) digitally signs
public key dB, creating
signed message, dB(m).
 Bob sends m and dB(m) to
Alice.
document, establishing he
is document owner/creator.
 Verifiable, nonforgeable:
recipient (Alice) can verify
that Bob, and no one else,
signed document.
 Bob encrypts m with his
Network Security
103
Digital Signatures (more)
 Suppose Alice receives Alice thus verifies that:
msg m, and digital
 Bob signed m.
signature dB(m)
 No one else signed m.
 Alice verifies m signed
 Bob signed m and not m’.
by Bob by applying
Non-repudiation:
Bob’s public key eB to
 Alice can take m, and
dB(m) then checks
signature dB(m) to court
eB(dB(m) ) = m.
and prove that Bob
 If eB(dB(m) ) = m,
signed m.
whoever signed m must
have used Bob’s
private key.
Network Security
104
Message Digests
Computationally expensive
to public-key-encrypt
long messages
Goal: fixed-length,easy to
compute digital
signature, “fingerprint”
 apply hash function H
to m, get fixed size
message digest, H(m).
Hash function properties:
 Produces fixed-size msg
digest (fingerprint)
 Given message digest x,
computationally infeasible
to find m such that x =
H(m)
 computationally infeasible
to find any two messages m
and m’ such that H(m) =
H(m’).
Network Security
105
Digital signature = Signed message digest
Bob sends digitally signed
message:
Alice verifies signature and
integrity of digitally signed
message:
Network Security
106
Hash Function Algorithms
 Internet checksum
would make a poor
message digest.
 Too easy to find
two messages with
same checksum.
 MD5 hash function widely
used.
 Computes 128-bit
message digest in 4-step
process.
 arbitrary 128-bit string
x, appears difficult to
construct msg m whose
MD5 hash is equal to x.
 SHA-1 is also used.
 US standard
 160-bit message digest
Network Security
107
Secure e-mail
• Alice wants to send secret e-mail message, m, to Bob.
• generates random symmetric private key, KS.
• encrypts message with KS
• also encrypts KS with Bob’s public key.
• sends both KS(m) and eB(KS) to Bob.
Network Security
108
Secure e-mail (continued)
• Alice wants to provide sender authentication
message integrity.
• Alice digitally signs message.
• sends both message (in the clear) and digital signature.
Network Security
109
Secure e-mail (continued)
• Alice wants to provide secrecy, sender authentication,
message integrity.
Note: Alice uses both her private key, Bob’s public
key.
Network Security
110
Pretty good privacy (PGP)
 Internet e-mail encryption
scheme, a de-facto
standard.
 Uses symmetric key
cryptography, public key
cryptography, hash
function, and digital
signature as described.
 Provides secrecy, sender
authentication, integrity.
 Inventor, Phil Zimmerman,
was target of 3-year
federal investigation.
A PGP signed message:
---BEGIN PGP SIGNED MESSAGE--Hash: SHA1
Bob:My husband is out of town
tonight.Passionately yours,
Alice
---BEGIN PGP SIGNATURE--Version: PGP 5.0
Charset: noconv
yhHJRHhGJGhgg/12EpJ+lo8gE4vB3mqJ
hFEvZP9t6n7G6m5Gw2
---END PGP SIGNATURE---
Network Security
111
Secure sockets layer (SSL)
 PGP provides security for a
specific network app.
 SSL works at transport
layer. Provides security to
any TCP-based app using
SSL services.
 SSL: used between WWW
browsers, servers for Icommerce (shttp).
 SSL security services:



server authentication
data encryption
client authentication
(optional)
 Server authentication:



SSL-enabled browser
includes public keys for
trusted CAs.
Browser requests server
certificate, issued by
trusted CA.
Browser uses CA’s public
key to extract server’s
public key from
certificate.
 Visit your browser’s
security menu to see its
trusted CAs.
Network Security
112
SSL (continued)
Encrypted SSL session:
 Browser generates
symmetric session key,
encrypts it with server’s
public key, sends encrypted
key to server.
 Using its private key, server
decrypts session key.
 Browser, server agree that
future msgs will be
encrypted.
 All data sent into TCP
socket (by client or server)
i encrypted with session
key.
 SSL: basis of IETF
Transport Layer Security
(TLS).
 SSL can be used for nonWeb applications, e.g.,
IMAP.
 Client authentication can
be done with client
certificates.
Network Security
113
Secure electronic transactions (SET)
 designed for payment-card
transactions over Internet.
 provides security services
among 3 players:
 customer
 merchant
 merchant’s bank
All must have certificates.
 SET specifies legal
meanings of certificates.
 apportionment of
liabilities for
transactions
 Customer’s card number
passed to merchant’s bank
without merchant ever
seeing number in plain text.
 Prevents merchants from
stealing, leaking payment
card numbers.
 Three software components:
 Browser wallet
 Merchant server
 Acquirer gateway
 See text for description of
SET transaction.
Network Security
114
IPsec: Network Layer Security
 Network-layer secrecy:
sending host encrypts the
data in IP datagram
 TCP and UDP segments;
ICMP and SNMP
messages.
 Network-layer authentication
 destination host can
authenticate source IP
address
 Two principle protocols:
 authentication header
(AH) protocol
 encapsulation security
payload (ESP) protocol

 For both AH and ESP, source,
destination handshake:
 create network-layer
logical channel called a
service agreement (SA)
 Each SA unidirectional.
 Uniquely determined by:
 security protocol (AH or
ESP)
 source IP address
 32-bit connection ID
Network Security
115
ESP Protocol
 Provides secrecy, host
authentication, data
integrity.
 Data, ESP trailer
encrypted.
 Next header field is in
ESP trailer.
 ESP authentication
field is similar to AH
authentication field.
 Protocol = 50.
Network Security
116
Authentication Header (AH) Protocol
 Provides source host
authentication, data
integrity, but not secrecy.
 AH header inserted
between IP header and IP
data field.
 Protocol field = 51.
 Intermediate routers
process datagrams as usual.
AH header includes:
 connection identifier
 authentication data: signed
message digest, calculated
over original IP datagram,
providing source
authentication, data integrity.
 Next header field: specifies
type of data (TCP, UDP, ICMP,
etc.)
Network Security
117
System Security
 Network Security =/= System Security
 Most common attacks exploit
 Buffer overflow
• E.g. bind, Windows XP, …
 Protocol
vulnerability
• E.g. NFS

Weak passwords
• Weak defaults
 User
behaviour
 Denial of Service
Network Security
118
Buffer Overflow
 Read in text from user with function such
as gets()
 No matter how big a buffer is allocated,
the attacker can send in a larger amount
 If heap allocated, will overflow on the heap

Harder to exploit
 If stack allocated, can easily change the
return address of the function call
Network Security
119
Buffer Overflow Solutions
 Use library calls that have limits on what
the amount of copying they will do
 Use a language that performs array-bounds
checking
 Limit services that are offered on the
system
Network Security
120
Protocol Vulnerabilities
 ARP:
Need access to LAN
 Wait till machine X is down
 Respond to ARP request as X

 NFS
 No per-user authentication
 No revocation
 Access by IP address; group and user IDs
Network Security
121
Weak Password Solutions
 Run crack programs to check the
passwords
 Require strong passwords at selection time
 Require frequent changes
 Biometric Login

E.g. face recognition
 Passwordless solutions
Network Security
122
User Behaviour
 E-mail attachments can be executable, but
not look like they are executable

E.g. my.pictures.yahoo.com
 Compromised machines can then contact
other machines, and therefore look
reputable
Network Security
123
Denial of Service
 Send more in than can come out

E.g. SYN attack
 Distributed DoS:
 Use a set of compromised machines
 No known solution at present
Network Security
124
Skills
 Most attacks are “script kiddies”
 See www.rootshell.com
 Defense is not much better
Network Security
125
Defense Mechanisms
 Configuration management
What services are run?
 Are they patched?
 Is this realistic?

 Firewalls
 Packet filtering
 Application-level gateway
 Antivirus measures
 Intrusion Detection
Network Security
126
Firewalls
firewall
isolates organization’s internal
net from larger Internet,
allowing some packets to pass,
blocking others.
Two firewall types:
 packet filter
 application gateways
To prevent denial of service
attacks:
 SYN flooding: attacker
establishes many bogus
TCP connections.
Attacked host alloc’s
TCP buffers for bogus
connections, none left
for “real” connections.
To prevent illegal modification
of internal data.
 e.g., attacker replaces
CIA’s homepage with
something else
To prevent intruders from
obtaining secret info.
Network Security
127
Packet Filtering
 Internal network is
connected to Internet
through a router.
 Router manufacturer
provides options for
filtering packets, based on:





source IP address
destination IP address
TCP/UDP source and
destination port numbers
ICMP message type
TCP SYN and ACK bits
 Example 1: block incoming
and outgoing datagrams
with IP protocol field = 17
and with either source or
dest port = 23.

All incoming and outgoing
UDP flows and telnet
connections are blocked.
 Example 2: Block inbound
TCP segments with ACK=0.

Prevents external clients
from making TCP
connections with internal
clients, but allows internal
clients to connect to
outside.
Network Security
128
Fragmentation Attack
 Use IP fragmentation to get past the
firewall
 Send a small initial fragment that looks
acceptable
 The second fragment overwrites most of
the first
Network Security
129
Application gateways
 Filters packets on
application data as well
as on IP/TCP/UDP fields.
 Example: allow select
internal users to telnet
outside.
gateway-to-remote
host telnet session
host-to-gateway
telnet session
application
gateway
router and filter
1. Require all telnet users to telnet through gateway.
2. For authorized users, gateway sets up telnet connection to
dest host. Gateway relays data between 2 connections
3. Router filter blocks all telnet connections not originating
from gateway.
Network Security
130
Limitations of firewalls and gateways
 IP spoofing: router
can’t know if data
“really” comes from
claimed source
 If multiple app’s. need
special treatment, each
has own app. gateway.
 Client software must
know how to contact
gateway.

e.g., must set IP address
of proxy in Web
browser
 Filters often use all or
nothing policy for UDP.
 Tradeoff: degree of
communication with
outside world, level of
security
 Many highly protected
sites still suffer from
attacks.
Network Security
131
Anti-Virus Mechanisms
 Ross Anderson: filter out Microsoft
executables at the firewall

Web-based e-mail gets around the firewall
 Two main techniques
 Look
for virus signature
 Look at program behaviour
Network Security
132
Intrusion Detection
 Assume that system will become
compromised, then detect

Misuse detection
• Honey trap
 Anomaly
detection
 Many false positives
 If accuracy is 99.9% and there are ten attacks
per million sessions, what is the ratio of false
alarms to real alarms?
Network Security
133
Network Security (summary)
Basic techniques…...
 cryptography (symmetric and public)
 authentication
 message integrity
…. used in many different security scenarios
 secure email
 secure transport (SSL)
 IP sec
 Firewalls
 Etc.
Network Security
134