Introduction to Computer Science
Week 10 – Network Security
Based on material and slides from
Computer Networking: A Top Down
Approach, 7
th
Edition – Chapter 8
,
Pearson/
Slide# 2 of 29
Lecture Objective
The objective of this lecture is to understand the
conceptual aspects of network security with
emphasis on cryptography.
Slide# 3 of 29
Lecture Outline
u Introduction to Network Security
uPrinciples of Cryptography
uSymmetric Key Cryptography
uPublic Key Cryptography
uSummary
Slide# 4 of 29
What is Network Security?
uConfidentiality: only sender, intended receiver should
“understand” message contents
n sender encrypts message
n receiver decrypts message
uEnd-point Authentication: sender, receiver want to
confirm identity of each other
uMessage Integrity: sender, receiver want to ensure
message not altered (in transit, or afterwards) without
detection
uAccess and Availability: services must be accessible
and available to users
Slide# 5 of 29
Friends and Enemies: Alice, Bob & Trudy
u Well-known in network security world
u Bob, Alice want to communicate “securely”
u Trudy (intruder) may intercept, delete, add messages
Slide# 6 of 29
Who might Bob, Alice be?
u … well, real-life Bobs and Alices!
u Web browser/server for electronic transactions (e.g.,
on-line purchases)
u On-line banking client/server
u DNS servers
u Routers exchanging routing table updates
u other examples?
Slide# 7 of 29
There are Bad Guys (and Girls) Out There!
Q: What can a “bad guy” do?
A: A lot!
nEavesdrop: intercept messages
nActively insert messages into connection (e.g. man in the
middle attack)
n Impersonation: can fake (spoof) source address in packet
(or any field in packet)
nHijacking: “take over” ongoing connection by removing
sender or receiver, inserting himself in place
nDenial of Service: prevent service from being used by
others (e.g., by overloading resources)
Slide# 8 of 29
Principles of Cryptography
m plaintext message
KA(m) ciphertext, encrypted with key KA
m = KB(KA(m))
Slide# 9 of 29
Encryption Schemes
There are two main types of encryption schemes:
uSymmetric Key Systems: Alice’s and Bob’s keys are
identical and are secret.
uPublic Key Systems, a pair of keys is used. One of the
keys is known to both Bob and Alice (known to the whole
world). The other key is known only by either Bob or Alice
(but not both).
Slide# 10 of 29
Symmetric Key Cryptography
Symmetric Key cryptography: Bob and Alice share same
(symmetric) key: Ks
ne.g., key is knowing substitution pattern in mono alphabetic
substitution cipher
Q: How do Bob and Alice agree on key value?
plaintextciphertext
K S
encryption
algorithm
decryption
algorithm
K S
plaintext
message, m
K (m)S m = KS(KS(m))
Slide# 11 of 29
Simple Encryption Scheme
Substitution Cipher: substituting one thing for another
nmonoalphabetic cipher: substitute one letter for another
plaintext: abcdefghijklmnopqrstuvwxyz
ciphertext: mnbvcxzasdfghjklpoiuytrewq
ciphertext: nkn. s gktc wky. mgsbc
Plaintext: bob. i love you. alicee.g.:
Encryption key: mapping from set of 26
letters to set of 26 letters
Slide# 12 of 29
Symmetric Key Crypto: DES
DES: Data Encryption Standard
uUS encryption standard [NIST 1993]
u 56-bit symmetric key, 64-bit plaintext input
uBlock cipher with cipher block chaining
uHow secure is DES?
nDES Challenge: 56-bit-key-encrypted phrase decrypted (brute
force) in less than a day!
nNo known good analytic attack
uMaking DES more secure:
n3DES: encrypt 3 times with 3 different keys
Slide# 13 of 29
DES Operation
Symmetric Key
Crypto: DES
u Initial permutation
u 16 identical “rounds” of
function application,
each using different 48
bits of key
u Final permutation
Slide# 14 of 29
AES: Advanced Encryption Standard
uSymmetric-key NIST standard, replaced DES (Nov
2001)
uProcesses data in 128 bit blocks
u128, 192, or 256 bit keys
uBrute force decryption (try each key) taking 1
second on DES, takes 149 trillion years for AES
Slide# 15 of 29
Public Key Cryptography
Symmetric Key Crypto
uRequires sender,
receiver know shared
secret key
uQ: How to agree on key
in first place (particularly
if never “met”)?
Public Key Crypto
uRadically different
approach [Diffie-
Hellman76, RSA78]
uSender, receiver do not
share secret key
uPublic encryption key
known to All
uPrivate decryption key
known only to receiver
Slide# 16 of 29
Public Key Cryptography
Slide# 17 of 29
Public Key Encryption Algorithms
RSA: Rivest, Shamir, Adelson algorithm
Requirements:
Need K ( ) and K ( ) such thatB B
. .
Given public key K , it should be
impossible to compute private
key K
B
B
1
2
+ –
K (K (m)) = m
BB
– +
+
–
Slide# 18 of 29
Pre-Requisite: Modular Arithmetic
ux mod n = remainder of x when divided by n
uFacts:
[(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
uThus (from the last fact)
(a mod n)d mod n = ad mod n
Example: a=14, n=10, d=2:
(a mod n)d mod n = ad mod n
=> (14 mod 10)2 mod 10 = 142 mod 10
=> 16 mod 10 = 196 mod 10 = 6
Slide# 19 of 29
RSA: Getting Ready!
uMessage: just a bit pattern
uBit pattern can be uniquely represented by an integer
number
u Thus, encrypting a message is equivalent to encrypting a
number.
Example:
um = 10010001 . This message is uniquely represented by
the decimal number 145.
u To encrypt m, we encrypt the corresponding number,
which gives a new number (the ciphertext).
Slide# 20 of 29
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