Transcript Document

Chapter 11
Security Protocols
Network Security Threats
Security and Cryptography
Network Security Protocols
Cryptographic Algorithms
Chapter 11
Security Protocols
Network Security Threats
Network Security

The combination of low-cost powerful computing
and high-performance networks is a two-edged
sword:



Many powerful new services and applications are enabled
But computer systems and networks become highly
susceptible to a wide variety of security threats
Network security involves countermeasures to
protect computer systems from intruders


Firewalls, security protocols, security practices
We will focus on security protocols
Threats, Security Requirements,
and Countermeasures

Network Security Threats




Network Security Requirements


Eavesdropping, man-in-the-middle, client and server
imposters
Denial of Service attacks
Viruses, worms, and other malicious code
Privacy, Integrity, Authentication, Non-Repudiation,
Availability
Countermeasures


Communication channel security
Border security
Security Requirements
Security threats motivate the following requirements:

Privacy: information should be readable only by
intended recipient

Integrity: recipient can confirm that a message has
not been altered during transmission

Authentication: it is possible to verify that sender
or receiver is who he claims to be

Non-repudiation: sender cannot deny having sent
a given message.

Availability: of information and services
Key Security Concepts
Eavesdropping
Request
Server
Client
Response



Information transmitted over network can be observed
and recorded by eavesdroppers (using a packet
sniffer)
Information can be replayed in attempts to access
server
Requirements: privacy, authentication, nonrepudiation
Client Imposter
Client
Imposter

Imposters attempt to gain unauthorized
access to server



Server
Ex. bank account or database of personal records
For example, in IP spoofing imposter sends
packets with false source IP address
Requirements: privacy, authentication
Denial of Service Attack
Attacker

Attacker can flood a server with requests,
overloading the server resources



Server
Results in denial of service to legitimate clients
Distributed denial of service attack on a server
involves coordinated attack from multiple (usually
hijacked) computers
Requirement: availability
Server Imposter
Client

An imposter impersonates a legitimate server
to gain sensitive information from a client


Server
Imposter
E.g. bank account number and associated user
password
Requirements: privacy, authentication, nonrepudiation
Man-in-the-Middle Attack
Client

Server
An imposter manages to place itself as man in the
middle




Man in
the
middle
convincing the server that it is legitimate client
convincing legitimate client that it is legitimate server
gathering sensitive information and possibly hijacking
session
Requirements: integrity, authentication
Malicious Code
Client

A client becomes infected with malicious code






Server
Imposter
Opening attachments in email messages
Executing code from bulletin boards or other sources
Virus: code that, when executed, inserts itself in
other programs
Worms: code that installs copies of itself in other
machines attached to a network
Many variations of malicious code
Requirements: privacy, integrity, availability
Countermeasures
Secure communication
channels
 Encryption
 Cryptographic
checksums and hashes
 Authentication
 Digital Signatures
Countermeasures
Secure borders
 Firewalls
 Virus checking
 Intrusion detection
 Authentication
 Access Control
Chapter 11
Security Protocols
Security and Cryptography
Cryptography




Encryption: transformation
of plaintext message into
encrypted (and unreadable)
message called ciphertext
Decryption: recovery of
plaintext from ciphertext
Cipher: algorithm for
encryption & decryption
A secret key is required to
perform encryption &
decryption
Substitution Ciphers
Substitution Cipher: Map each letter or
numeral into another letter of numeral:
abcdefghijklmnopqrstuvwxyz
zyxwvutsrqponmlkjihgfedcba

Example:


hvxfirgb security
Substitution ciphers are easy to break


Take histogram of frequency of occurrence of
letters in a ciphertext message
Match to known frequencies of letters
Transposition Cipher
Transposition Cipher: Rearrange order of
letters/numerals in a message using a
particular rearrangement:


Example:


interchange character k with character k+1
security esuciryt
Transposition Ciphers are easy to break


Suppose plaintext and ciphertext are known
Matching of letters in plaintext and ciphertext will
reveal transposition mapping
Secret Key Cryptography
Encryption
Plaintext P
EK(.)
Key K


Decryption
Ciphertext C=EK(P)
DK(.)
P
Key K
Sender encrypts P by applying mapping EK which
depends on secret key K: C = EK(P)
Receiver decrypts C by applying inverse mapping
DK which also depends on K: DK(EK(P)) = P
What makes a good cipher?
Algorithm should be easy to implement and deploy
on large scale
Algorithm should be difficult to break:
Number of keys should be very large


1.

Attacker cannot try all possible keys
The secret key should be very hard to derive from
intercepted messages
2.

Even if a large number of plaintext & corresponding
cyphertexts are known to the attacker
Examples of secret key methods discussed later:



Data Encryption Standard (DES) and Triple DES
Advanced Encryption Standard (AES)
Security using Secret Key
Cryptography


Privacy: secret key renders messages
confidential
Integrity: alteration of the cyphertext will be
detected, because the decrypted message
will be gibberish


When privacy is not required, encryption of the
entire message is overkill because much
processing involved
We will see that cryptographic checksums provide
integrity and require less processing
Authentication using Secret Key
Cryptography
John to Jane, “let’s talk”
r
Sender
(John)
Receiver
(Jane)
Ek(r)
r´
Ek(r´)



Send message identifying self
Send response with
encrypted r
Can now authenticate receiver
by issuing a challenge


Reply with challenge that
contains random number r,
nonce = number once
Apply secret key to decrypt
message. If decrypted number
is r then the transmitter is
authenticated
Cryptographic Checksums and
Hashes
CrytoChk
Message
P
K


Crypto
Checksum
Calculator
Message
P
HK(P)
Transmitter calculates a fixed number of bits
(crypto checksum/hash) that depends on
secret key K: HK(P)
Receiver recalculates hash from received
message & compares to received hash
What makes a Good Hash?

To be secure, it must be very difficult to find a
message that generates a given hash


If not difficult, an attacker could produce a message and
corresponding hash that would be accepted as valid
Suppose message is M bits long and hash is m bits
long, and m<<M




For each given hash value there are 2M/m messages that
give that hash
How long does it take to find a match?
Probability that a random message generates given hash
is 2-m since there are 2m hashes
Mean # tries to find given hash is: 2m
Example






M = 1000, m = 128
Number of possible messages: 21000
Number of possible hashes: 2128
For each hash value there are 21000/2128 = 2872
messages that generate the hash
A randomly selected message produces a desired
hash value with probability 2-128
If each attempt requires 1 microsecond, time to find
matching message to a hash is:
2128x1 microsecond = 225 years
Some Hashing Algorithms



Message Digest 5 (MD5)
 Pad message to be multiple of 512 bits
 Initialize 128 buffer to given value
 Modify buffer content according to next 512 bits
 Repeat until all blocks done
 Buffer holds 128 bit hash
Keyed MD5
 Pad message to be multiple of 512 bits
 Attach and append secret key to padded message prior to
performing hash function
 Could also append/attach other information such as sender ID
Secure Hash Algorithm 1 (SHA-1)
 Produce a 160-bit hash; more secure than MD5
 Keyed version available
Hashed Message Authentication
Code Method

HMAC improves strength of a hash code







Pad secret key with zeros to length of 512 bits
and X-OR with 64 repetitions of 00110110
Pad message to multiple of 512 bits
Calculate hash of padded key followed by padded
message, 128 bits for MD5, 160 bits for SHA-1
Pad hash to 512 bits
Pad secret key with zeros to 512 bits and X-OR
with 64 repetitions of 01011010
Calculate hash of padded key and padded hash
Result is final hash
Public Key Cryptography
Encryption
Decryption
Ciphertext C = EK1(P)
Plaintext P
EK1(.)
Public key K1

P
DK2(.)
Private key K2
Public key cryptography provides privacy
using two different keys:


Public key K1 available to all for encrypting
messages to a certain user: C = EK1(P)
Private key K2 for user to decrypt messages:
P = DK2(EK1(P))
What makes a good public key
algorithm?


EK1 and DK2 should be readily implementable
Inverse relationship should hold:





P = DK2(EK1(P)) and sometimes P = EK1(DK2(P))
K1 is a relatively small number of bits and K2 is
usually a large number of bits
It is extremely difficult to decrypt EK1(P) without K2
It should not be possible to deduce K2 from K1
Example: RSA public key cryptography (discussed
later)
Integrity using Public Key
Cryptography
Integrity:



Any one can send messages using public key, so
integrity not assured directly
For integrity, transmitter:
1.
2.

encodes P with its private key K2΄ to obtain P΄ = DK2΄
P)
encodes P΄ using receiver’s public key: C = EK1(P΄)
Receiver:
1.
2.

decrypts C, DK2(EK1(P΄)) = P΄
decrypts P΄ using transmitters public key, EK1΄(DK2΄(P))
=P
Only the transmitter could have sent this message.
Authentication using Public Key
Cryptography
John to Jane, “let’s talk”
Receiver
Sender
EK1(r)
r




Transmitter identifies itself
Receiver sends a nonce encoded using the sender’s
public key in a challenge message
Transmitter uses its private key to recover the
nonce, and it returns the unencrypted nonce
Only the holder of the private key can find the nonce
Digital Signatures using Public
Key Cryptography

Digital signatures provide nonrepudiation


Digital signature obtained as follows:




User “signs” a message that cannot be repudiated
Transmitter obtains a hash of the message
Transmitter encrypts the hash using its private key; result
is the digital signature
Transmitter sends message and signature
To check the signature:




Receiver obtains hash of message
Receiver decrypts signature using sender’s public key
Receiver compares hash computed from message and
hash obtained from signature
Procedure also ensures message integrity
Secret Key vs. Public Key

Public key systems have more capabilities



Public key algorithms are more complex


Secret key: privacy, integrity, authentication
Public key: all of above + digital signature
Require more processing and hence much slower than
secret key
Practice:


Use public key method during session setup to establish a
session key
Use secret key cryptography during session using the
session key
Example: Pretty Good Privacy
(PGP)

PGP developed by Phillip Zimmerman to provide
secure email




Notorious for becoming publicly available for
download over Internet in violation of US export
restrictions
Uses public key cryptography to provide



http://www.philzimmermann.com/index.shtml
http://www.pgpi.org
Privacy, integrity, authentication, digital signature
De facto standard for email security
Also provides privacy and integrity for stored files
Key Distribution in Secret Key
Systems

Every pair of users requires a separate
shared secret key



N(N – 1) keys for N users; Grows quickly with N
Similar to full-mesh connections for N users
Solution: Introduce Key Distribution Centers




Each users has shared key with the KDC
User A has shared key KKA with KDC
User B has shared key KKB with KDC
KDC provides shared key when A & B need to
communicate
Key Distribution Center
A
EKB(KAB)

User A contacts the KDC to
request a key for use with user B.

KDC:
B
challenge
request
response
EKA(KAB), EKB(KAB)
KDC
C
D

Authenticates user A

Selects a key KAB and encrypts it
to produce EKA(KAB) and EKB(KAB).

KDC sends both versions of the
encrypted key to A.

User A contacts user B and
provides a ticket in the form of
EKB(KAB)

Users A & B both have KAB
Example: Kerberos




Kerberos: authentication service for users
to access servers over network
KDC has secret key with every user
At login, user supplies ID and password
 KDC authenticates user & generates
session key
 Session key & ticket-granting ticket (TGT)
is sent to user encrypted using shared
secret key
To access a particular server, user sends
request to KDC with server name and TGT
 KDC decrypts TGT to recover session key
& then returns ticket to client for desired
server
Key Distribution in Public Key
Systems



In public key only one pair of keys per user
Key distribution problem: How to determine whether
an advertised public key is not from an imposter?
Certification Authority (CA)




Issues digitally signed certificate that provides
 User’s name & public key
 Certificate serial #, expiration date
Certificates can be stored in publicly accessible directories
To communicate with B, a user contacts the CA to obtain
the certificate for B
Users are configured to have the CA’s public key, which
they use to verify the digital signature
Key Generation: Diffie-Hellman
Exchange
T = gx
Transmitter
A



K = Rx mod p
K = Ty mod p
= gxy mod p
= gxy mod p
Generate keys instead of distributing keys
Diffie-Hellman exchange to create a shared key
A & B pick p a large prime #, and generator g < p



R = gy
Receiver
B
A picks x and sends T = gx to B; B picks y and sends R = gy
Secret key is K = (gx)y = (gy)x which are calculated by A & B
Eavesdropper that obtains p, g, T, R cannot obtain x and y
because x = logT and y = logR are extremely difficult to solve
Man-in-the-Middle Attack
T
Transmitter A





R'
K1 = R´x
K1 = T y ´
= gxy´
= gxy´
Man in
the
middle
C
T'
R
K2 = R x ´
=
gx ´ y
Receiver
B
K2 = T´ y
= gx´ y
An intruder C can interpose itself between A & B
C establishes a shared key K1 with A and a shared key K2
with B
C can then intercept, decipher, and re-encrypt all
communications
Need mutual authentication between A & B
Alternative: Community agrees on g & p; users publish their
T, R, …
Diffie-Hellman Complexity

Diffie-Hellman exchange involves
computation of powers of large numbers


Large number of multiplications implies heavy
computational burden
Susceptible to denial-of-service attacks
Chapter 11
Security Protocols
Network Security Protocols
Direct Connections to Internet
Internet
A



B
Computers A & B communicate across the Internet
Exposure to eavesdropping, imposters, DoS
Can encrypt some transmitted information



But IP headers need to be visible to routers & hence others
Eavesdropper can gather variety of usage information & deduce
nature of interaction
Choice of which layer to apply security: IP, transport, or
application layer
Gateway-to-Gateway
Internet
A


Computers A and B have gateways interposed between their
internal network and Internet
Gateway can be a firewall


Controls external access to internal network
Packet filtering according to various header fields


B
IP addresses, port numbers, ICMP types, fields within payload
Secure tunnels can be established between gateways

All internal information including headers can be encrypted
Remote user to Gateway
Internet




Mobile host needs access to internal network
Gateway must provide user with access while
barring intruders from accessing internal network
May also need to protect identity of mobile user
IP-address of mobile user changes
Firewall Options

Firewalls can operate at different layers


Circuit-Level Gateways



IP-layer filtering cannot operate on payload contents
Direct client-to-server TCP connections not allowed
Relays TCP segments between actual client & actual
server
Application-Level Gateways or Proxies



Interposed between actual client and actual server
Performs authentication and determines what features are
available to client
Monitors, filters & relays messages
Protocol Layer Options


Security Services can be provided at different layers of
the protocol stack
Data Link Layer security


IP-Layer security



Point-to-point security between directly-connected devices,
e.g. wireless LAN security
Security service between IP-layer & Transport layer
End-to-end security across an internet, e.g. IPsec
Transport Layer security


Security service between Transport & Application Layers
E.g. Secure Sockets Layer & Transport Layer Security
Network Security Services




Integrity Service: information received from
network has not been altered during
transmission
Authentication Service: the receiver can
authenticate that information came from
purported sender
Privacy Service: information is readable only by
intended recipient
In applications that require network security,
integrity & authentication essential; privacy not
always justified
IP Security (IPsec)
.





IPsec defined in RFCs 2401, 2402, 2406
Provides authentication, integrity, confidentiality, and
access control at the IP layer
Provides a key management protocol to provide
automatic key distribution techniques.
Security service can be provided between a pair of
communication nodes, where the node can be a host
or a gateway (router or firewall).
Two protocols & two modes to provide traffic security:


Authentication Header and Encapsulating Security Payload
Transport mode or tunnel mode
Security Association



A Security Association (SA) is a logical simplex
connection between two network-layer entities
Two SA’s required for bidirectional secure
communication
SA is specified by






A unique identifier
Security services to be used
Cryptographic algorithms to be used
How shared keys will be established
Other attributes such as lifetime
SA negotiated before security service begins
Integrity & Authentication Service


Integrity can be ascertained by sending a
cryptographic checksum or hash of message
Authentication also provided if hash covers:



To protect against replay attacks, message should
carry a sequence number that is covered by the
hash



Shared secret key, sender’s identity & message
Fields that are changed while packet traverses Internet are
set to zero in calculation of hash
Receiver accepts a packet only once
Receiver maintains a window of packets it accepts
Receiver recalculates hash and compares to hash in
received packet
Authentication Header
Packet Authentication
header header
Packet
payload
Authenticated except for changeable fields



Inserted between regular header & payload
Packet header contains field indicating
presence of authentication header
Authentication header includes:



Security association ID
Sequence number
Cryptographic hash
Tunneling
New Authentication Original
header header
header
Packet
payload
In
tunnel
mode
Authenticated except for changeable fields in new header

A tunnel can be created by encapsulating a packet
within another packet



Inner packet header carries original source address
Entire contents of inner packet covered by hash
Outer packet header carries gateway’s address
Internet
Tunnel
Privacy Service



Privacy requires encryption of message
Encryption header identifies security association &
sequence number
Encryption can cover payload + padding:
Packet Encryption
header header
Packet + pad
payload
Encrypted

Authentication header can be used to detect alteration of
any non-changeable fields & protect against replay attacks
New AuthenticationEncryption
header
headerheader
Packet + pad
payload
Encrypted
Privacy Service in Tunnel Mode
New
Encryption Original
header header
header
Packet
payload
In tunnel
mode
Encrypted

In tunnel mode, entire original packet is encrypted
and unreadable to eavesdroppers



All original packet header fields are unreadable
Only gateway packet header is visible
It is also possible to use tunnel mode between
trusted routers while traversing untrusted segments
of the Internet

Trusted routers can decrypt inner packet & perform routing
Setting up a Security Association

To setup security association, computers must:





Last two steps are difficult; possible approaches:




Agree on security services that will be provided
Agree on cryptographic algorithms
Authenticate each other
Establish a shared secret key
Manual set up of shared key between pair of users
Use Key Distribution Center
Contact a Certificate Authority
Internet Key Exchange (RFC 2409) for IPsec

Assumes parties have a name/identity for other party as
well as a pre-established shared secret (secret key or
private key)
Internet Key Exchange (IKE)
Initiator Host
Contains Ci
Select random # Ci:
initiator’s cookie
Proposes
Security
Association
options
HDR, SA
Cookie Request
Selects SA
options
Contains
Ci & Cr
HDR, SA
Check Ci & address
against list; Associate
(Ci, Cr) with SA;
record SA as
“unauthenticated”
Responder Host
Check to see if Ci already
in use; If not, generate Cr,
responder’s cookie;
Associate Cr with initiator’s
address
Cookie Response
Internet Key Exchange
Initiator Host
Initiate DiffieHellman exchange
Responder Host
T=gx mod p
Nonce Ni
HDR, KE, Ni
Key Request
R=gy mod p
Nonce Nr
Check responder cookie,
discard if not valid; If valid
identify SA with (Ci, Cr) &
record as “unauthenticated”
HDR, KE, Nr
Key Response
Calculate K=(gy)x mod p
Calculate secret string of bits
SKEYID known only to initiator
& responder
Calculate K=(gx)y mod p
Calculate secret string of bits
SKEYID known only to initiator
& responder
Internet Key Exchange
Initiator Host
Prepare signature
based on SKEYID, T,
R, Ci, Cr, the SA field,
initiator ID
Signature Request
Responder Host
SKEYID,
T, R, Ci,
Cr, SA, IDi
Hash of info
in HDR
HDR, {IDi, Sigi}
encrypted
SKEYID, T,
R, Ci, Cr, SA,
IDr
Authenticate initiator.
If successful, SA
declared authenticated.
Hash of
info in
HDR
Authenticates initiator
comparing decrypted hash to
recalculated hash.
If agree, SA declared
authenticated.
Prepares signature based on
SKEYID, T, R, Ci, Cr, the SA
field, responder IDr
HDR, {IDr, Sigr}
Signature Request
SKEYID & Cookies

SKEYID for authentication, based on:




Shared key that results from Diffie-Hellman
Pre-shared key
 Pre-configured secret key
 Private part of a public key pair
Nonces and/or cookies
Cookies



To counteract denial-of-service attacks
A user that wants to make a connection requests must first
request a cookie
Connections requests are only accepted from users that
have a valid cookie, and hence that must receive packets
at the IP address from which they sent the request
IPsec Authentication Header
IPv4 Header



AH
Upper Layer (e.g., TCP or UDP)
Authentication header (AH) placed after headers
that are examined at every hop
Presence of AH indicated by protocol value = 51 in
IPv4 header
Authentication performed over all fields including IP
header, except fields that change at every hop
Authentication Header Format
0
8
Next Header
16
Length
31
Reserved
Security Parameters Index
Sequence Number
Authentication Data






Format used in IPv4 and IPv6
Next Header indicates next payload after AH
Length of Authentication data in multiples of 32 bits
SPI = unique ID for security association
Sequence number for anti-replay protection
Authentication data contains result of authentication
computation
Encapsulating Security Payload

ESP provides:



Integrity & authentication service
Privacy service by encryption of payload
Authentication data at end is optional

Placement at ends makes implementation simpler
IPv4 Header
ESP
Upper Layer (e.g., TCP or UDP)
HMAC
ESP
Header
Format
0
16
24
31
Security Parameters Index
Sequence Number
Payload Data
Padding
Pad Length
Next Header
Authentication Data




Authenticated coverage from SPI until next header field
Encrypted coverage from payload data field until next header
Protocol type = 50
Next header field is encrypted, so transport type not visible
Secure Sockets Layer (SSL)

SSL developed by Netscape Communications


Operates on top of TCP
Provides secure connections




HTTP, FTP, telnet, …
Electronic ordering & payment; e-mail
SSL 3.0 submitted to IETF for standardization
TLS standardized by IETF (RFC 2246)

Slight differences with SSL 3.0
Transport Layer Security (TLS)
Handshake Change cipher
Protocol
spec Protocol
Alert
Protocol
HTTP
Protocol
TLS Record Protocol
TCP
IP



TLS protocols operate at two layers
TLS Record Protocol operates on top of TCP
Protocols on top of TLS Record Protocol



TLS Handshake Protocol
TLS Change Cipher Specification Protocol
TLS Alert Protocol
TLS Record Protocol

TLS Record protocol provides

Privacy service through secret key encryption



Encryption algorithm is negotiated at session setup
Secret keys generated per connection using another
protocol such as Handshake protocol
Reliability service through keyed message
authentication code


Hash algorithm negotiated at session setup
Operates without hash only during session negotiation
TLS Handshake Protocol

TLS Handshake protocol used by client & server





Negotiate protocol version, encryption algorithm, key
generation method
Can authenticate each other using public key algorithm
Client & server establish a shared secret
Multiple secure connections can be set up after session
setup
Session specified by following parameters






Session Identifier: byte sequence selected by server
Peer Certificate: certificate of peer
Compression method: used prior to encryption
Cipher spec: encryption & message authentication code
Master Secret: 48-byte secret shared by client & server
Is resumable?: flag indicating if new connections can be
initiated
TLS Handshake Process
Client
TLS Record protocol initially specifies no
compression or encryption
Request connection
Includes:
Version #; Time & date;
Session ID (if resuming);
Ciphersuite (combinations
of key exchange, encryption, MAC,
compression)
ClientHello
* Optional messages
Server
Send ServerHello if there is
acceptable Ciphersuite
combination; else, send
failure alert & close
connection.
ServerHello includes:
New CipherSpec pending
ServerHello
May contain public key
Certificate*
Compute shared key
ServerKeyExchange*
ServerHelloDone
Version #; Random number;
Session ID ; Ciphersuite &
compression selections
Server Certificate
Server part of key exchange:
Diffie-Hellman, gx;; RSA, public key
Server part of handshake done
Handshake Protocol continued
Client
Client’s part of key agreement:
Diffie-Hellman gy; RSA, random #s
Server
ClientKeyExchange
Change Cipher protocol
[ChangeCipherSpec]
message notifies server that
subsequent records protected
under new CipherSpec & keys
Hash using new CipherSpec;
allows server to verify change
in Cipherspec
Finished
Compute shared key
Server changes CipherSpec
Verify CipherSpec
Handshake Protocol completion
Client
Client changes CipherSpec
Client verifies new
CipherSpec
Server
[ChangeCipherSpec]
Finished
Notify client that subsequent
records protected under new
CipherSpec & keys
Hash using new CipherSpec;
Application Data
TLS Record protocol encapsulates application-layer messages
•
•
•
•
Privacy through secret key cryptography
Reliability through MAC
Fragmentation of application messages into blocks for compression/encryption
Decompression/Decryption/Verification/Reassembly
TLS Handshake with Client
Authentication
Client
ClientHello
ServerHello
Certificate*
ServerKeyExchange*
CertificateRequest
ServerHelloDone
Client sends suitable
certificate
Certificate*
ClientKeyExchange
Client prepares digital
signature based on
messages sent using its
private key
CertificateVerify*
[ChangeCipherSpec]
Finished
[ChangeCipherSpec]
Finished
Application Data
Server
Server requests certificate if
client needs to be
authenticated
If server finds certificate
unacceptable; server can
send fatal failure alert
message & close connection
Server verifies client has
private key
TLS 1.0 & SSL 3.0 Compatibility


TLS 1.0 allows backwards compatibility with SSL 3.0
When TLS client sends ClientHello to SSL server:



Client sends TLS message with {3, 1} in version field to
indicate it also supports SSL 3.0
Server that supports SSL 3.0 will respond with SSL 3.0
ServerHello message
A TLS server that handles SSL 3.0 clients

Accepts SSL 3.0 ClientHello messages & responds with
SSL 3.0 Server Hello message if client message contains
{3,0} in version field indicating that it only supports SSL 3.0
Client Hello Message
ServerHello
SSL Message Exchange
Chapter 11
Security Protocols
Cryptographic Algorithms
Data Encryption Standard

DES adopted by U.S. National Bureau of Standards
in 1977



Encryption: Electronic Codebook (ECB) Mode




Most widely-used secret key system
Efficient hardware implementation
Message broken into 64-bit blocks
Each 64-bit plaintext block encrypted separtely into 64-bit
cyphertext
Original version of DES uses a 56-bit key
Decryption: Encryption operations performed in
reverse order
DES Algorithm
64-bit plaintext
Initial permutation
Iteration 1
Iteration 2
Iteration 16
32-bit swap
Inverse permutation
64-bit ciphertext
56-bit key
Generate 16 per-iteration keys
48-bit Key 1

48-bit Key 2

48-bit Key 16


Initial permutation is
independent of key
Final permutation is
inverse of initial
permutation
Penultimate step swaps
32-bits on left with 32-bits
on the right
Intermediate 16 iterations
apply a different key that is
derived from the original
56-bit key
DES Iteration

Ri-1
Li-1


Li-1
64-bit block divided into Li –1
and Ri –1 halves
Left output Li = Ri –1
Right output
Ri = Li –1 XOR f(Ri –1, Ki)
 bitwise XOR
f(Ri-1, K)

f(.,.) as follows:

L1
Ri


Ri –1 expanded to 48 bits
using fixed re-ordering &
duplication pattern
XORed with Ki
Each resulting group of 6bits is mapped into 4-bit
output according to
substitution mapping
Cipher Block Chaining

ECB mode encrypts 64-bit blocks
independently


Attacker can use knowledge about pattern in
message to attack encrypted sequence of blocks
Cipher Block Chaining (CBC) introduces
dependency between consecutive blocks


Current plaintext block is XORed with preceding
ciphertext block
First plaintext block XORed with an initialization
vector that is transmitted to receiver in ciphertext
Cipher Block Chaining
(a) Encryption
P1
P2
P3
Encrypt
Encrypt
Encrypt
C1
C2
C3
C1
C2
C3
Decrypt
Decrypt
Decrypt
P1
P2
P3
IV
(b) Decryption
IV
…
…
DES Security

DES vulnerable to brute-force attack



56-bit key is too short
Has been broken in less than one day using a speciallydesigned computer
Triple-DES (3DES)



Provides better security
Uses two 56-bit keys
C = EK1(DK2(EK1(P)))
P = DK1(EK2(DK1(P)))
Instead of “triple encryption”, use encryption-decryptionencryption
 If K1 = K2, reduces to original DES
Advanced Encryption Standard

AES selected in 2001 by U.S. NIST (National
Institute of Standards & Technology)






Developed by Rijmen and Daemen
Secret key system
Encryption of 128-bit blocks with keys of size 128, 192, or
256 bits
Software & efficient hardware implementation
3.4x1038 keys vs. 7.2x1016 keys for 56-bit DES
AES is gradually replacing DES/3DES

See:
 http://csrc.nist.gov/CryptoToolkit/aes/
RSA Public Key Algorithm


Named after Rivest, Shamir, and Adleman
Modular arithmetic & factorization of large
numbers

Let n = pq, where p & q are two large numbers



Find e relatively prime to (p – 1)(q – 1)



n typically several hundred bits long, i.e. 512 bits
Plaintext must be shorter than n
i.e. e has no common factors with (p – 1)(q – 1)
Public key is {e,n}
Let d be multiplicative inverse of e


de = 1 modulo (p – 1)(q – 1)
Private key is {d,n}
Encryption & Decryption

Fact: For P<n and n, p, q, d as above:
Pde mod n = P mod n

Encryption:
C = Pe mod n


Result is number less than n and is represented by same
number of bits as key
Decryption:
Cd mod n = Ped mod n = P mod n = P

Security stems from fact that it is very difficult to factor
large numbers n, and with e to then determine d
RSA Example

Let p = 5, q = 11


Let e = 7, which is relatively prime to 40



n = pq = 55 and (p – 1)(q – 1) = 40
7d mod 40 = 1, gives d = 23
Public key is {7, 55}
Private key is {23, 55}
RSA Example continued

Encrypt “RSA”: R=18, S=19, A=1
C1 = 187 mod 55 = 184+2+1 mod 55
= (18 mod 55) (182 mod 55) (184 mod 55) mod 55
= (18) (324 mod 55) (184 mod 55) mod 55
= (18) (49) (492 mod 55) mod 55 = (18)(49)(36) mod 55
= 31752 mod 55 = 17
C2 = 197 mod 55 = 24
C3 = 17 mod 55 = 1

Decrypt
1723 mod 55 = 1716+4+2+1 mod 55 =18
2423 mod 55 = 19
123 mod 55 = 1