Introduction to Computer Science Week 10 – Network Security
Based on material and slides from
Computer Networking: A Top Down
th
Approach, 7 Edition – Chapter 8
Jim Kurose, Keith Ross
Pearson/Addison Wesley
Lecture Objective
The objective of this lecture is to understand the conceptual aspects of network security with emphasis on cryptography.
Slide# 2 of 29
Lecture Outline
uIntroduction to Network Security uPrinciples of Cryptography uSymmetric Key Cryptography uPublic Key Cryptography
u Summary
Slide# 3 of 29
What is Network Security?
uConfidentiality: only sender, intended receiver should “understand” message contents
nsender encrypts message nreceiver 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# 4 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# 5 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# 6 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)
nImpersonation: 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# 7 of 29
Principles of Cryptography
m plaintext message
KA(m) ciphertext, encrypted with key KA m = KB(KA(m))
Slide# 8 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# 9 of 29
Symmetric Key Cryptography
KS
KS
plaintext message, m
ciphertext KS (m)
plaintext
m = KS(KS(m))
encryption algorithm
decryption algorithm
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?
Slide# 10 of 29
Simple Encryption Scheme
Substitution Cipher: substituting one thing for another nmonoalphabetic cipher: substitute one letter for another
plaintext: abcdefghijklmnopqrstuvwxyz
ciphertext: mnbvcxzasdfghjklpoiuytrewq
e.g.:
Encryption key: mapping from set of 26 letters to set of 26 letters
Plaintext: bob. i love you. alice
ciphertext: nkn. s gktc wky. mgsbc
Slide# 11 of 29
Symmetric Key Crypto: DES
DES: Data Encryption Standard
uUS encryption standard [NIST 1993] u56-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# 12 of 29
Symmetric Key Crypto: DES
DES Operation
u Initial permutation
u 16 identical “rounds” of function application, each using different 48 bits of key
u Final permutation
Slide# 13 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# 14 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# 15 of 29
Public Key Cryptography
Slide# 16 of 29
Public Key Encryption Algorithms
Requirements:
+. -.
1 NeedK ()andK ()suchthat
B-+B
K (K (m)) = m
B
B
2
+
, it should be impossible to compute private
Given public key K B
key K – B
RSA: Rivest, Shamir, Adelson algorithm
Slide# 17 of 29
Pre-Requisite: Modular Arithmetic
ux mod n = remainder of x when divided by n u 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
uThus (from the last fact)
(amodn)d modn=ad modn
Example: a=14, n=10, d=2:
(amodn)d modn=ad modn =>(14mod10)2 mod10=142 mod10 => 16 mod 10 = 196 mod 10 = 6
Slide# 18 of 29
RSA: Getting Ready!
uMessage: just a bit pattern
uBit pattern can be uniquely represented by an integer
number
uThus, encrypting a message is equivalent to encrypting a number.
Example:
um = 10010001 . This message is uniquely represented by the decimal number 145.
uTo encrypt m, we encrypt the corresponding number, which gives a new number (the ciphertext).
Slide# 19 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