Transcript public key cryptography

INSF 612Review
Chapter 4: Network Layer
Chapter goals:
Overview:
• understand principles
behind network layer
services:
• network layer services
• routing principle: path
selection
• hierarchical routing
• IP
• Internet routing protocols
reliable transfer
–
–
–
–
routing (path selection)
dealing with scale
how a router works
advanced topics: IPv6,
multicast
• instantiation and
implementation in the
Internet
– intra-domain
– inter-domain
• what’s inside a router?
• IPv6
• multicast routing
Highlights
• Packet switching and circuit switching
• Routing Algorithms
–
–
–
–
Dijkstra and Bellman-ford
Performance
Scalability
Stability
• Know how to compute routes
– Change in link cost
– Poisoned reverse
Comparison of LS and DV algorithms
Message complexity
• LS: with n nodes, E links,
O(nE) msgs sent each
• DV: exchange between
neighbors only
– convergence time varies
Speed of Convergence
• LS: O(n**2) algorithm
requires O(nE) msgs
– may have oscillations
• DV: convergence time
varies
– may be routing loops
– count-to-infinity problem
Robustness: what happens if
router malfunctions?
LS:
– node can advertise incorrect
link cost
– each node computes only its
own table
DV:
– DV node can advertise
incorrect path cost
– each node’s table used by
others
• error propagate thru network
Hierarchical Routing
Our routing study thus far - idealization
• all routers identical
• network “flat”
… not true in practice
administrative autonomy
scale: with 50 million
• internet = network of
destinations:
• can’t store all dest’s in
routing tables!
• routing table exchange
would swamp links!
networks
• each network admin may
want to control routing in its
own network
Intra-AS and Inter-AS routing
C.b
a
Host
h1
C
b
A.a
Inter-AS
routing
between
A and B
A.c
a
d
c
b
A
Intra-AS routing
within AS A
B.a
a
c
B
Host
h2
b
Intra-AS routing
within AS B
• We’ll examine specific inter-AS and intra-AS
Internet routing protocols shortly
The Internet Network layer
Host, router network layer functions:
Transport layer: TCP, UDP
Network
layer
IP protocol
•addressing conventions
•datagram format
•packet handling conventions
Routing protocols
•path selection
•RIP, OSPF, BGP
routing
table
ICMP protocol
•error reporting
•router “signaling”
Link layer
physical layer
IP Addressing: introduction
• IP address: 32-bit
identifier for host, router
interface
• interface: connection
between host, router and
physical link
– router’s typically have
multiple interfaces
– host may have multiple
interfaces
– IP addresses associated
with interface, not host,
router
223.1.1.1
223.1.2.1
223.1.1.2
223.1.1.4
223.1.1.3
223.1.2.9
223.1.3.27
223.1.2.2
223.1.3.2
223.1.3.1
223.1.1.1 = 11011111 00000001 00000001 00000001
223
1
1
1
IP Fragmentation and Reassembly
length ID fragflag offset
=4000 =x
=0
=0
One large datagram becomes
several smaller datagrams
length ID fragflag offset
=1500 =x
=1
=0
length ID fragflag offset
=1500 =x
=1
=1480
length ID fragflag offset
=1040 =x
=0
=2960
Why different Intra- and Inter-AS routing ?
Policy:
• Inter-AS: admin wants control over how its traffic
routed, who routes through its net.
• Intra-AS: single admin, so no policy decisions needed
Scale:
• hierarchical routing saves table size, reduced update
traffic
Performance:
• Intra-AS: can focus on performance
• Inter-AS: policy may dominate over performance
Router Architecture Overview
Two key router functions:
• run routing algorithms/protocol (RIP, OSPF, BGP)
• switching datagrams from incoming to outgoing link
IPv6
• Initial motivation: 32-bit address space
completely allocated by 2008.
• Additional motivation:
– header format helps speed processing/forwarding
– header changes to facilitate QoS
– new “anycast” address: route to “best” of several
replicated servers
• IPv6 datagram format:
– fixed-length 40 byte header
– no fragmentation allowed
Chapter 7: Network security
Foundations:
•
•
•
•
•
what is security?
cryptography
authentication
message integrity
key distribution and certification
Security in practice:
• application layer: secure e-mail
• transport layer: Internet commerce, SSL, SET
• network layer: IP security
Symmetric key cryptography
substitution cipher: substituting one thing for another
– monoalphabetic cipher: substitute one letter for another
plaintext: abcdefghijklmnopqrstuvwxyz
ciphertext:
E.g.:
mnbvcxzasdfghjklpoiuytrewq
Plaintext: bob. i love you. alice
ciphertext: nkn. s gktc wky. mgsbc
Q: How hard to break this simple cipher?:
•brute force (how hard?)
•other?
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”)?
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
RSA: Choosing keys
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).
Digital Signatures
Cryptographic technique
analogous to handwritten signatures.
• Sender (Bob) digitally
signs document,
establishing he is
document owner/creator.
• Verifiable, nonforgeable:
recipient (Alice) can
verify that Bob, and no
one else, signed
document.
Simple digital signature
for message m:
• Bob encrypts m with his
public key dB, creating
signed message, dB(m).
• Bob sends m and dB(m) to
Alice.
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
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
Key Distribution Center (KDC)
• Alice,Bob need shared
symmetric key.
• KDC: server shares
different secret key
with each registered
user.
• Alice, Bob know own
symmetric keys, KAKDC KB-KDC , for
communicating with
KDC.
• Alice communicates with
KDC, gets session key R1,
and KB-KDC(A,R1)
• Alice sends Bob
KB-KDC(A,R1), Bob extracts
R1
• Alice, Bob now share the
symmetric key R1.
Certification Authorities
• Certification authority
(CA) binds public key to
particular entity.
• Entity (person, router,
etc.) can register its public
key with CA.
– Entity provides “proof
of identity” to CA.
– CA creates certificate
binding entity to public
key.
– Certificate digitally
signed by CA.
• When Alice wants Bob’s
public key:
• gets Bob’s certificate (Bob or
elsewhere).
• Apply CA’s public key to
Bob’s certificate, get Bob’s
public key
Pretty good privacy (PGP)
A PGP signed message:
• 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.
---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+lo8gE4vB3
mqJhFEvZP9t6n7G6m5Gw2
---END PGP SIGNATURE---
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.
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 (summary)
Basic techniques…...
• cryptography (symmetric and public)
• authentication
• message integrity
…. used in many different security scenarios
• secure email
• secure transport (SSL)
• IP sec
See also: firewalls , in network management
Chapter 8: Network Management
Chapter goals:
• introduction to network management
– motivation
– major components
• Internet network management framework
– MIB: management information base
– SMI: data definition language
– SNMP: protocol for network management
– security and administration
• presentation services: ASN.1
• firewalls
SNMP overview: 4 key parts
• Management information base (MIB):
– distributed information store of network
management data
• Structure of Management Information (SMI):
– data definition language for MIB objects
• SNMP protocol
– convey manager<->managed object info, commands
• security, administration capabilities
– major addition in SNMPv3
Network Management standards
SNMP: Simple Network
OSI CMIP
Management Protocol
• Common Management • Internet roots (SGMP)
Information Protocol • started simple
• designed 1980’s: the
• deployed, adopted rapidly
unifying net
• growth: size, complexity
management standard
• currently: SNMP V3
• too slowly
• de facto network
standardized
management standard
SNMP Naming
question: how to name every possible standard object
(protocol, data, more..) in every possible network
standard??
answer: ISO Object Identifier tree:
– hierarchical naming of all objects
– each branchpoint has name, number
1.3.6.1.2.1.7.1
ISO
ISO-ident. Org.
US DoD
Internet
udpInDatagrams
UDP
MIB2
management
OSI
Object
Identifier
Tree
Check out www.alvestrand.no/harald/objectid/top.html
TLV Encoding
Idea: transmitted data is self-identifying
– T: data type, one of ASN.1-defined types
– L: length of data in bytes
– V: value of data, encoded according to ASN.1 standard
Tag Value
1
2
3
4
5
6
9
Type
Boolean
Integer
Bitstring
Octet string
Null
Object Identifier
Real
Firewalls
To prevent denial of service
firewall
isolates organization’s internal
net from larger Internet,
allowing some packets to pass,
blocking others.
Two firewall types:
– packet filter
– application gateways
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
Chapter 5: The Data Link Layer
Our goals:
Overview:
• understand principles
behind data link layer
services:
–
–
–
–
• link layer services
• error detection, correction
• multiple access protocols and
error detection, correction
LANs
sharing a broadcast
channel: multiple access • link layer addressing, ARP
• specific link layer
link layer addressing
technologies:
reliable data transfer,
flow control: done!
• instantiation and
implementation of
various link layer
technologies
–
–
–
–
–
Ethernet
hibs, bridges, switches
IEEE 802.11 LANs
PPP
ATM
Checksumming: Cyclic Redundancy Check
• view data bits, D, as a binary number
• choose r+1 bit pattern (generator), G
• goal: choose r CRC bits, R, such that
– <D,R> exactly divisible by G (modulo 2)
– receiver knows G, divides <D,R> by G. If non-zero remainder:
error detected!
– can detect all burst errors less than r+1 bits
• widely used in practice (ATM, HDCL)
MAC Protocols: a taxonomy
Three broad classes:
• Channel Partitioning
– divide channel into smaller “pieces” (time slots,
frequency)
– allocate piece to node for exclusive use
• Random Access
– allow collisions
– “recover” from collisions
• “Taking turns”
– tightly coordinate shared access to avoid collisions
Goal: efficient, fair, simple, decentralized
Slotted Aloha
• time is divided into equal size slots (= pkt trans. time)
• node with new arriving pkt: transmit at beginning of
next slot
• if collision: retransmit pkt in future slots with
probability p, until successful.
Success (S), Collision (C), Empty (E) slots
Pure (unslotted) ALOHA
• unslotted Aloha: simpler, no synchronization
• pkt needs transmission:
– send without awaiting for beginning of slot
• collision probability increases:
– pkt sent at t0 collide with other pkts sent in [t0-1, t0+1]
MAC Protocols: a taxonomy
Three broad classes:
• Channel Partitioning
– divide channel into smaller “pieces” (time slots,
frequency)
– allocate piece to node for exclusive use
• Random Access
– allow collisions
– “recover” from collisions
• “Taking turns”
– tightly coordinate shared access to avoid collisions
Goal: efficient, fair, simple, decentralized
“Taking Turns” MAC protocols
channel partitioning MAC protocols:
– share channel efficiently at high load
– inefficient at low load: delay in channel access, 1/N
bandwidth allocated even if only 1 active node!
Random access MAC protocols
– efficient at low load: single node can fully utilize
channel
– high load: collision overhead
“taking turns” protocols
look for best of both worlds!
Reservation-based protocols
Distributed Polling:
• time divided into slots
• begins with N short reservation slots
– reservation slot time equal to channel end-end
propagation delay
– station with message to send posts reservation
– reservation seen by all stations
• after reservation slots, message transmissions ordered by
known priority