12.Security
1
COMP 3331/9331:
Computer Networks and
Applications
Week 10
Network Security
Reading Guide: Chapter 8: 8.1 – 8.5
2
Complete your myExperience and shape
the future of education at UNSW.
Click the link in Moodle
or login to myExperience.unsw.edu.au
(use .edu.au to login)
The survey is confidential, your identity will never be released
Survey results are not released to teaching staff until after your results are published
3
Network Security: Overview
Our goals:
v understand principles of network security:
§ cryptography and its many uses beyond “confidentiality”
§ authentication
§ message integrity
4
Network Security: roadmap
8.1 What is network security?
8.2 Principles of cryptography
8.3 Message integrity
8.4 Authentication
8.5 Securing email
8.6 – 8.9 SSL, IPSec, Firewall/IDS – not covered.
There are several security electives offered
5
What is network security?
confidentiality: only sender, intended receiver should
“understand” message contents
§ sender encrypts message
§ receiver decrypts message
authentication: sender, receiver want to confirm identity of
each other
message integrity: sender, receiver want to ensure message
not altered (in transit, or afterwards) without detection
access and availability: services must be accessible and
available to users
6
Friends and enemies: Alice, Bob, Trudy
v well-known in network security world
v Bob, Alice want to communicate “securely”
v Trudy (intruder) may intercept, delete, add messages
secure
sender
secure
receiver
channel data, control
messages
data data
Alice Bob
Trudy
7
Who might Bob, Alice be?
v … well, real-life Bobs and Alices!
v Web browser/server for electronic transactions
(e.g., on-line purchases)
v on-line banking client/server
v DNS servers
v routers exchanging routing table updates
v etc.
8
There are bad guys (and girls) out there!
Q: What can a “bad guy” do?
A: A lot!
§ eavesdrop: intercept messages
§ actively insert messages into connection
§ impersonation: can fake (spoof) source address in
packet (or any field in packet)
§ hijacking: “take over” ongoing connection by
removing sender or receiver, inserting himself in
place
§ denial of service: prevent service from being used
by others (e.g., by overloading resources)
9
Network Security: roadmap
8.1 What is network security?
8.2 Principles of cryptography
8.3 Message integrity
8.4 Authentication
8.5 Securing email
10
The language of cryptography
m plaintext message
KA(m) ciphertext, encrypted with key KA
m = KB(KA(m))
plaintext plaintextciphertext
K
A
encryption
algorithm
decryption
algorithm
Alice’s
encryption
key
Bob’s
decryption
key
K
B
11
Symmetric key cryptography
symmetric key crypto: Bob and Alice share same (symmetric)
key: K
Q: how do Bob and Alice agree on key value?
plaintextciphertext
K S
encryption
algorithm
decryption
algorithm
S
K S
plaintext
message, m
K (m)
S
m = KS(KS(m))
12
Simple encryption scheme
substitution cipher: substituting one thing for another
v monoalphabetic cipher: substitute one letter for another
v Ceaser Cipher: replace each letter of the alphabet with the
letter standing three places further down the alphabet.
Plaintext: meet me after the party
ciphertext: phhw ph diwhu wkh sduwb
e.g.:
Encryption key: c = (p+3) mod 26
Each plaintext letter p substituted by the ciphertext letter c
In general, we have c = (p+k) mode 26
where k is in range 1 to 25
Plain : 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
cipher: d e f g h i j k l m n o p q r s t u v w x y z a b c
13
Simple encryption scheme
v With only 25 possible keys, the Caeser cipher is vulnerable to
brute force cryptanalysis
v Cipher can be any permutation of the 26 alphabet characters
plaintext: abcdefghijklmnopqrstuvwxyz
ciphertext: mnbvcxzasdfghjklpoiuytrewq
Plaintext: bob. i love you. alice
ciphertext: nkn. s gktc wky. mgsbc
e.g.:
Encryption key: mapping from set of 26 letters
to set of 26 letters
We have 26! (> 4 x1026) possible keys
14
Breaking an encryption scheme
v cipher-text only attack:
Trudy has ciphertext she
can analyze
v two approaches:
§ brute force: search
through all keys
§ statistical analysis
v known-plaintext attack:
Trudy has (part of) plaintext
corresponding to ciphertext
§ e.g., in monoalphabetic
cipher, Trudy determines
pairings for a,l,i,c,e,b,o,b
v chosen-plaintext attack:
Trudy can get ciphertext for
chosen plaintext
15
Breaking an encryption scheme
ETAOIN SHRDLU
Frequency Histogram Analysis for letters in English language
Monoalphabetic ciphers are easy to break because they
reflect the frequency data of the original alphabet
16
A more sophisticated encryption approach
v Polyalphabet ciphers
v n substitution ciphers, M1,M2,…,Mn
v cycling pattern:
§ e.g., n=4: and key is M1,M3,M4,M3,M2; M1,M3,M4,M3,M2; ..
v for each new plaintext symbol, use subsequent
subsitution pattern in cyclic pattern
§ dog: d from M1, o from M3, g from M4
Encryption key: n substitution ciphers, and cyclic
pattern
17
Two types of symmetric ciphers
v Stream ciphers
§ encrypt one bit at time
v Block ciphers
§ Break plaintext message in equal-size blocks
§ Encrypt each block as a unit
18
Stream Ciphers
v Combine each bit of keystream with bit of plaintext to get
bit of ciphertext
v m(i) = ith bit of message
v ks(i) = ith bit of keystream
v c(i) = ith bit of ciphertext
v c(i) = ks(i) Å m(i) (Å = exclusive or)
v m(i) = ks(i) Å c(i)
keystream
generatorkey keystream
pseudo random
19
RC4 Stream Cipher
v RC4 is a popular stream cipher
§ Extensively analyzed and considered good
§ Key can be from 1 to 256 bytes
§ Used in WEP for 802.11
§ Known to have vulnerabilities
§ Many other alternatives: ChaCha, SOBER, SEAL, …
20
Block Cipher
v Ciphertext processed as k bit blocks
v 1-to-1 mapping is used to map k-bit block of
plaintext to k-bit block of ciphertext
v E.g: k=3 (see table)
§ 010110001111 => 101000111001
v Possible permutations = 8! (40,320)
v To prevent brute force attacks
§ Choose large K (64, 128, etc)
v Full-table block ciphers not scalable
§ E.g., for k = 64, a table with 264 entries required
§ instead use function that simulates a randomly
permuted table
Input Output
000 110
111 001
001 111
010 101
011 100
100 011
101 010
110 000
21
Block Cipher (contd.)
v If only a single round,
then one bit of input
affects at most 8 bits of
output
v In 2nd round, the 8
affected bits get
scattered and inputted
into multiple
substitution boxes
v How many rounds?
§ How many times do
you need to shuffle
cards
§ Becomes less efficient
as n increases
64-bit input
T1
8bits
8 bits
8bits
8 bits
8bits
8 bits
8bits
8 bits
8bits
8 bits
8bits
8 bits
8bits
8 bits
8bits
8 bits
64-bit scrambler
64-bit output
loop for
n rounds
T2 T3 T4 T6T5 T7 T8
From Kaufman
et al
8-bit to
8-bit
mapping
22
Symmetric key crypto: DES
DES: Data Encryption Standard
v US encryption standard [NIST 1993]
v 56-bit symmetric key, 64-bit plaintext input
v block cipher with cipher block chaining
v how secure is DES?
§ DES Challenge: 56-bit-key-encrypted phrase decrypted
(brute force) in less than a day using distributed computing
§ no known good analytic attack
v making DES more secure:
§ 3DES: encrypt 3 times with 3 different keys
23
Symmetric key
crypto: DES
initial permutation
16 identical “rounds” of
function application,
each using different 48
bits of key
final permutation
DES operation
24
AES: Advanced Encryption Standard
v symmetric-key NIST standard, replaced DES
(Nov 2001)
v processes data in 128 bit blocks
v 128, 192, or 256 bit keys
v brute force decryption (try each key) taking 1 sec
on DES, takes 149 trillion years for AES
25
Cipher Block Chaining
v cipher block: if input block
repeated, will produce same
cipher text:
t=1
m(1) = “HTTP/1.1” block
cipher
c(1) = “k329aM02”
…
• Use random numbers: XOR
ith input block, m(i) and
random number r(i) and
apply block-cipher
encryption algorithm
• C(i) = Ks(m(i) + r(i))
• Send across c(i) and r(i)
t=17
m(17) = “HTTP/1.1” block
cipher
c(17) = “k329aM02”
26
CBC Example
v Plaintext: 010 010 010
v If no CBC, sent txt : 101 101 101
§ 1-to-1 mapping table used
v Lets use the following random bits
§ r1: 001, r2: 111, r3: 100
§ XoR the plaintext with these random bits
§ 010 XoR 001 = 011
§ Now do table lookup for 011 -> 100
v We get c(1)=100, c(2)=010 and c(3)=000, although
plaintext is the same (010)
v Need to transmit twice as many bits (c(i) as well as r(i))
Input Output
000 110
111 001
001 111
010 101
011 100
100 011
101 010
110 000
27
Cipher Block Chaining
• cipher block chaining: send
only one random value
alongwith the very first
message block, and then
have the sender and receiver
use the computed cipher
block in place of the
subsequent random number
• XOR ith input block, m(i),
with previous block of
cipher text, c(i-1)
• c(0) is an initialisation vector
(random) transmitted to
receiver in clear
+
m(i)
c(i)
block
cipher
c(i-1)
28
Cipher Block Chaining (CBC)
v CBC generates its own random numbers
§ Have encryption of current block depend on result of previous
block
§ c(i) = KS( m(i) Å c(i-1) )
§ m(i) = KS( c(i) ) Å c(i-1)
v How do we encrypt first block?
§ Initialization vector (IV): random block = c(0)
§ IV does not have to be secret
v Change IV for each message (or session)
§ Guarantees that even if the same message is sent repeatedly, the
ciphertext will be completely different each time
29
Cipher Block Chaining (CBC)
30
Public Key Cryptography
symmetric key crypto
v requires sender, receiver
know shared secret key
v Q: how to agree on key in
first place (particularly if
never “met”)?
public key crypto
v radically different
approach [Diffie-
Hellman76, RSA78]
v sender, receiver do not
share secret key
v public encryption key
known to all
v private decryption key
known only to receiver
31
Public key cryptography
plaintext
message, m
ciphertextencryption
algorithm
decryption
algorithm
Bob’s public
key
plaintext
messageK (m)
B
+
K B
+
Bob’s private
key
K
B
–
m = K (K (m))
B
+
B
–
32
Public key encryption algorithms
need K ( ) and K ( ) such thatB B
. .
given public key K , it should be
impossible to compute private
key K
B
B
requirements:
1
2
RSA: Rivest, Shamir, Adelson algorithm
+ –
K (K (m)) = m
BB
– +
+
–
33
Prerequisite: modular arithmetic
v x mod n = remainder of x when divide by n
v facts:
[(a mod n) + (b mod n)] mod n = (a+b) mod n
[(a mod n) – (b mod n)] mod n = (a-b) mod n
[(a mod n) * (b mod n)] mod n = (a*b) mod n
v thus
(a mod n)d mod n = ad mod n
v example: x=14, n=10, d=2:
(x mod n)d mod n = 42 mod 10 = 6
xd = 142 = 196 xd mod 10 = 6
Note: You don’t need to know this for the exam
34
RSA: getting ready
v message: just a bit pattern
v bit pattern can be uniquely represented by an integer
number
v thus, encrypting a message is equivalent to encrypting a
number.
example:
v m= 10010001 . This message is uniquely represented by
the decimal number 145.
v to encrypt m, we encrypt the corresponding number,
which gives a new number (the ciphertext).
35
RSA: Creating public/private key pair
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