Network Security

• introduction
• cryptography
• authentication
• key exchange
• required reading: text section 7.1

Network Security

intruder may

• eavesdrop
• remove, modify, and/or insert messages
• read and playback messages

important issues:

• cryptography: secrecy of info being transmitted
• authentication: proving who you are and having correspondent prove his/her/its identity

Security in Computer Networks

user resources:

• login passwords often transmitted unencrypted in TCP packets between applications (e.g., telnet, ftp)
• passwords provide little protection

network resources:

• often completely unprotected from intruder eavesdropping, injection of false messages
• mail spoofs, router updates, ICMP messages, network management messages

bottom line:

• intruder attaching his/her machine (access to OS code, root privileges) onto network can override many system-provided security measures
• users must take a more active role

Encryption

plaintext: unencrypted message

ciphertext: encrypted form of message

intruder may

• intercept ciphertext transmission
• intercept plaintext/ciphertext pairs
• obtain encryption decryption algorithms

A simple encryption algorithm

substitution cipher:

abcdefghijklmnopqrstuvwxyz

poiuytrewqasdfghjklmnbvczx

• replace each plaintext character inmessage with matching ciphertext character:

plaintext: Charlotte, my love

ciphertext: iepksgmmy, dz sgby

• key is pairing betweenb plaintext characters and ciphertext characters
• symmetric key: sender and receiver use same key
• 26! (approx 10**26) different possible keys: unlikely to be broken by random trys
• substitution cipher subject to decryption using observed frequency of letters
  • 'e' most common letter, ;the' most common word

DES: Data Encryption Standard

• encrypts data in 64-bit chunks
• encryption/decryption algorithm is a published standard
  • everyone knows how to do it
• substituion cipher over 64-bit chunks: 56-bit key determines which of 56! Substitution ciphers used
  • substitution: 19 stages of transformations, 16 involving functions of key

• decryption done by reversing encryption steps
• sender and receiver must use same key

Key Distribution Problem

• problem: how do communicant agree on symmetric key?
  • N communicants implies N keys
• trusted agent distribution:
  • keys distributed by centralized trusted agent
  • any communicant need only know key to communicate with trusted agent
  • for communication between I and j, trusted agent will provide a key

• we will cover in more detail shortly

Public Key Cryptography

• separate encryption/decryption keys
  • receiver makes known (!) its encryption key
  • receiver keeps its decryption key secret
• to send to receiver B, encrypt message M using B's publicly available key, EB
  • send EB(M)
• to decrypt, B applies its private decrypt key DB to receiver message:
  • compute DB( EB(M) ) gives M

• knowing encryption key does not help with decryption: decryption is a non-trivial inverse of encryption
• only receiver can decrypt message
• question: good encryption/decryption algorithms

RSA: public key encryption/decryption

RSA: a public key algorithm for encrypting/decrypting

entity wanting to receive encrypted messages:

• choose two prime numbers, p, q greater than 10**100
• compute n=pq and z = (p-1)(q-1)
• choose number d which has no common factors with z
• compute e such that ed = 1 mod z, i.e.,

integer-remainder( (ed) / ((p-1)(q-1)) ) = 1, i.e.,

ed = k(p-1)(q-1) +1

• three numbers:
  • e, n made public
  • d kept secret

RSA (continued)

to encrypt:

• divide message into i blocks, bi of size k: 2**k < n
• encrypt: encrypt(bi) = bi**e mod n

to decrypt:

• bi = encrypt(bi)**d

to break RSA

• need to know p, q, given pq=n, n known
• factoring 200 digit n into primes takes 4 billion years using known methods

RSA example

• choose p=3, q=11, gives n=33, (p-1)(q-1)=z=20
• choose d = 7 since 7 and 20 have no common factors
• compute e = 3, so that ed = k(p-1)(q-1)+1 (note: k=1 here)

sender:

plaintext		use e=3	ciphertext
char	#	#**3	#**3 mod 33
S	19	6859	28
U	21	9261	21
N	19	2744	5

receiver:

ciphertext		use d=7	plaintext
C	c**7	c**7 mod 33	char
28	13492928512	19	S
21	1801088541	21	U
5	78125	14	N

Further notes on RSA

why does RSA work?

• Crucial number theory result: of p, q prime then bi**((p-1)(q-1)) mod pq = 1
• using mod pq arithmetic:

(b**e)**d = b**(ed)

= b**(k(p-1)(q-1)+1) for some k

= b b**(p-1)(q-1) b**(p-1)(q-1) ... b**(p-1)(q-1)

= b 1 1 ... 1

= b

• Note: we can also encrypt with d and encrypt with e.
  • This will be useful shortly

How to break RSA?

Brute force: get B's public key

• for each possible bi in plaintext, compute bi**e
• for each observed bi**e, we then know bi
• more: choose size of bi "big enough"

man-in-the-middle: intercept keys, spoof identity:

Authentication

question: how does a receiver know that remote communicating entity is hwo it is claimed to be?

Approach 1: peer-peer key-based authentication

• A, B (only) know secure key for encryption/decryption
• A sends encrypted msf to B and B decrypts:

A to B: msg = encrypt("I am A")
B computes: if decrypt(msg)=="I am A"
   then A is verified
   else A is fradulent

• failure scenarios?

Authentication Using Nonces

to prove that A is alive, B sends "once-in-a-lifetime-only" number (nonce) to A, which A encodes and returns to B

A to B: msg = encrypt("I am A")
B compute: if decrypt(msg)=="I am A"
   then A is OK so far
B to A: once-in-a-lifetime value, n
A to B: msg2 = encrypt(n)
B computes: if decrypt(msg2)==n
   then A is verified
   else A is fradulent

• note similarities to three way handshake and initial sequence number choice
• problems with nonces?

Authentication Using Public Keys

B wants to authenticate A

A has made its encryption key EA known

A alone knows DA

symmetry: DA( EA(n) ) = EA ( DA(n) )

A to B: msg = "I am A"
B to A: once-in-a-lifetime value, n
A to B: msg2 = DA(n)
B computes: if EA (DA(n))== n
   then A is verified
   else A is fradulent

Goals of digital signature:

• sender can not repudiate message never sent ("I never sent that")
• receiver can not fake a received message

Suppose A wants B wants to "sign" a message M

B sends DA(M) to A
A computes if EA ( DA(M)) == M
  then A has signed M

question: can A plausibly deny having sent M?