Transcript Encrypting the Internet 18 April 2000

Encrypting the Internet
Phil Karn
18 April 2000
[email protected]
http://people.qualcomm.com/karn
Overview
•
•
•
•
•
Threat models
Cryptography basics
Layer tradeoffs
Cryptographic protocols on the Internet
Crypto politics
Threat Models
I.e, What are you worried about?
•
•
•
•
•
•
Message confidentiality
Message authentication/integrity
Traffic analysis
Denial of service
Maintaining anonymity
Enforcing transparency
Confidentiality
• Preventing an eavesdropper from understanding
the contents of a message
• Cryptography’s traditional role
Authentication/Integrity
• Verifying who sent a message, and that it has not
been modified en route
• Major role for public key cryptography
– digital signatures can be verified with public key
Traffic Analysis
• Gleaning information from traffic patterns even if
the contents are not decipherable
• A threat often overlooked or ignored in civilian
applications
• Difficult to do at upper layers
– a traditional function of bulk link encryption
Denial of Service
• An attacker might sabotage a network even if he
cannot read or forge legitimate messages
– overloading a network (e.g, Internet MS-DOS)
– jamming a radio channel (e.g., Captain Midnight)
• Limited role for crypto in a public network
– conditional access to resources, controls, etc
Enforcing Subnetwork Transparency
• Some ISPs violate layering, or impose policy
constraints on user content or protocols
– transparent web proxies
– server & Napster bans on college campuses and cable
modems
• Higher layer crypto can thwart this
– e.g., tunneling IP in a TCP connection to port 443
(SSL)
• Carrier can still monitor traffic levels
– which is the better way anyway
Cryptography Basics
• Crypto = secret, graphy = writing
– only someone with the key can understand an encrypted
message
• Used in ancient times
• Modern cryptography began during WW2
– first machine-aided cryptanalysis (Enigma)
• Invention of public key crypto in 1970s
– finally made conventional crypto practical
Properties of a Good Modern Cipher
• Large key to resist brute-force search
• Published, reviewed algorithm
– security depends entirely on secrecy of key
– security cannot depend on algorithm secrecy
• Resistance to chosen-plaintext attack
– attacker cannot determine key even if given ability to
encrypt plaintext of the attacker’s choosing
– implies resistance to known-plaintext and knownciphertext attacks
Types of Cryptography
• Symmetric
– same key for both encryption and decryption
– DES, IDEA, AES candidates
• Asymmetric (Public Key)
–
–
–
–
–
key pairs: private and public
based on factorization or discrete log problem
RSA, Diffie-Hellman, etc
much slower than symmetric
digital signature capability
DES: a typical symmetric block cipher
plaintext
64
bits
DES
ciphertext
64
bits
56 bits
key
Brute force keysearching
• For a 56-bit key, there are 256 or
72,057,594,037,927,936 possibilities
• This seems like a lot, but even in 1976 it seemed
too small given Moore’s Law
– this was the major objection to DES
• EFF’s Deep Crack machine has made this a reality
Deep Crack
• The name is a play on Deep Blue, the IBM chess
playing computer, which in turn played on Deep
Thought, CMU’s chess playing computer named
after the computer in Douglas Adams’ The
Hitchhiker’s Guide to the Galaxy (aren’t you glad
you asked?)
• All crunch a long time and produce very little
output
Deep Crack
• Sponsored by John Gilmore, EFF co-founder.
Cost: $210K
• 6 cabinets x 5 boards/cabinet x 64 custom
ASICS/board x 24 keysearch engines/ASIC
• Total of 1800 functional chips
– Tests 90,000,000,000 keys/sec
– Can search the whole keyspace in <5 days
• Complete plans published in book form to exploit
my paper-format export loophole
Alternatives to DES
• Triple DES
– encrypt three times with 2 or 3 distinct keys
– no brute-force attack for the forseeable future
• IDEA
– 64-bit block cipher with 128-bit key
– Used in PGP, SSH
More DES alternatives
• RC4/RC5
– proprietary ciphers designed by Ron Rivest, owned by
RSA Data Security Inc
– widely implemented in web browsers
– variable key lengths to meet export limits
• NIST AES (Advanced Encryption Standard)
– now fielding candidates, >=15 so far
Encryption for Authentication
• A more recent application for cryptography
• Vital for electronic commerce
• Provides two related features:
– proof that whoever sent a message possesses a
particular key
– integrity protection - confidence that a legitimate
message has not been modified in transit
Sample authentication scheme
challenge
64
bits
DES
response
64
bits
56 bits
key
Challenge-response protocols
• Prove possession of a secret key without revealing
that key on an open channel
• Handy for computer logins, cellular phone
accesses, etc
Cryptographic hash functions
• Block ciphers like DES can be used as hash
functions, but they’re slow and clumsy
• Other functions have been specifically designed as
hashes:
– MD5
– SHA-1
– CAVE
Generic hash function
data, variable amount
fixed-size hash
128 bits (MD5)
160 bits (SHA-1)
Properties of hash functions
• Computing a hash is fast
• Finding an input that produces a given hash is
(hopefully) extremely hard
• So is finding two inputs that hash to the same
result
• Hash functions are also known as one-way
functions because of this property
Hash functions for confidentiality
• Hash functions were custom-designed for
authentication applications
• But they can still be used as building-blocks for
confidentiality!
– Dan Bernstein’s Snuffle is the subject of his lawsuit
pending in the 9th Cir since Dec 1997
– I designed one that’s described in Applied
Cryptography
Public key cryptography
• All of the ciphers described so far have been
symmetric ciphers, I.e., the same key is used to
encrypt and to decrypt
• Until the mid 1970s, all ciphers were symmetric
• Public key ciphers are also called asymmetric-key
– different keys to encrypt and decrypt
Why public key?
• Use insecure channel to agree on shared secret key
for symmetric cipher
• Allow anyone to send you a message without
having to first agree on a shared secret key
– avoids n2 key management problem
• Provide digital signatures
– a unique capability
Public key theory
• Public key ciphers are generally based on
mathematical problems known to be “hard”
– discrete logarithm
– factoring
• The reverse operations are easy
– discrete exponentiation
– multiplication
Discrete logarithm
• Computing the expression
y = gx mod p
where x and p are suitably large integers (e.g.,
1Kbit) is relatively easy
• Finding the value of x that produced a given y is
much harder!
Diffie-Hellman key exchange
• The first public key scheme invented
– patent expired in 1997
• Not actually a public key encryption scheme, but a
key agreement scheme
• Based on discrete log problem
• Used in CDMA over-the-air service activation to
generate A-key
Diffie-Hellman in detail
• Alice
• Generates secret integer x
• Computes gx mod p, sends
to Bob
• Computes (gy)x mod p
• Use result as symmetric
key
• Bob
• Generates secret integer y
• Computes gy mod p, sends
to Alice
• Computes (gx)y mod p
• Use result as symmetric
key
RSA
• The major public key scheme, discovered ~1977
– patent expires Sep 20, 2000
• Based on the difficulty of factoring as opposed to
multiplication
– thought to be related to discrete log
• Can encrypt or decrypt
– different keys for each
– encryption key can be published, decryption key kept
secret
RSA in detail
• User’s public key is {n,e}
– e is a small number, typically 3 or 17
– n is the product of two randomly chosen secret prime
numbers, p*q. Typically 1024 bits long
• To encrypt, compute
C = Me mod n
RSA decryption
• User’s secret key is {n,d}
– n is same value as in public key, so only d is secret
• User computes
M = Cd mod n
• The math is hairy, but to compute d it is believed
that you must know p,q, the factorization of n
RSA Signatures
• Nothing says M has to be secret and C has to be
public
• If you reverse the algorithm, you can get a
message that anybody can decrypt, but only you
could have encrypted.
Generating a digital signature
message
Hash
function
()d mod n
digital signature
Verifying a digital signature
digital signature
message
()e mod n
Hash
function
compare
Public Key Management
• Although public keys can be openly published,
how do you know that a particular key in the
directory really belongs to who you think it does?
• This is the thorniest problem in public key
cryptography!
Certificates
• PK cryptography can solve its own problem
• Use PK signatures to vouch for the authenticity of
others’ keys
• Two general approaches
– X.509 Certification Authorities
• centralized, hierarchical, authoritarian
• used in secure web transactions
– PGP “web of trust”
• decentralized, flat, democratic
Other PK algorithms
• Digital Signature Standard (DSS)
– promoted by the government largely because it cannot
be used for encryption
– used by PGP 5.0 to avoid RSA patent
• Elliptic Curves
– not actually an algorithm, but a different way to
implement existing algorithms like Diffie-Hellman with
supposedly less computational effort for a given degree
of security
Crypto - Necessary But Not Sufficient
• Many (most?) vulnerabilities in practice due to:
– software bugs
• e.g., buffer overflows
– configuration errors
• especially insecure installation defaults
– Trojan horses
• e.g., Microsoft Word macros, innumerable Windows viruses
• Old bugs are exploited much more than new ones
– many machines run old software versions
The Internet Reference Model
Application
Host-to-Host
(end-to-end)
Internet
Subnet
The Internet Reference Model
• Application Layer
– covers OSI application & presentation layers
– HTTP, Telnet, FTP, SMTP, POP, DNS, etc
• End-to-End Layer
– OSI transport & session layers
– TCP & UDP
• Internet Layer
– OSI network (upper part)
– IP
• Subnet Layer
– OSI network (lower part), link, physical
The Major Internet Protocols
SMTP
Telnet
FTP
TCP
POP
HTTP
DNS
UDP
ICMP
IP
ARP
Enet
PPP
DHCP
ATM
other subnets
The End-to-End Principle
• Saltzer, Reed and Clark, 1981:
– many traditional low-level network functions are better
done at the endpoints, I.e., at higher protocol levels
– some functions can sometimes be justified within the
network as a performance enhancement
• IMHO, one of the most important CS papers of all
time
– http://people.qualcomm.com/karn/library.html has links
Encryption in the Internet
• Encryption in the subnetwork
• Encryption just above IP
– IPSEC
– PPTP
• Encryption above TCP
– SSH
– TLS
– SSL
• Encryption in the application
– PGP, S/MIME, etc
Encryption in the Subnet
• Link encryptors widely available
– but beware of single-DES
•
•
•
•
Easy to deploy incrementally
Transparent to routers, hosts & applications
Good resistance to traffic analysis
No defense against compromised routers or hosts
Encryption Above IP
• Layer inserted between IP and transport
• IPSec (IP Security) on IETF standards track
– many vendors, including open source (FreeSWAN)
• Protects transport header along with application
• Can be used end-to-end, or to carry other IP
packets in “tunnel” mode
• Increased header overhead, esp with
authentication
– IP fragmentation issues
– no VJ TCP/IP header compression
– unavoidable for strong packet-level security
IP Security (IPSEC)
• Started in IETF circa 1992
– architecture similar to earlier govt network layer
security work for ISO CLNP
• Unusually long gestation period
– reflects creeping featurism, committee design,
excessive generality (imho)
• Most useful for virtual private networks, “road
warrier” access to closed corporate network
through firewall
IPSec Packet Format
IP
Header
IPSEC
Header
End-to-end
Header & Data
Two types of IPSec packets:
Authentication Header (AH), protocol number 51
Encapsulating Security Protocol (ESP), proto 50
Both carry the original IP protocol field
Note “end-to-end header and data” can be another
IP datagram! This is tunnel mode
Authentication Header (AH)
• Provides cryptographic authentication (not
encryption) of layers above IP plus selected fields
in IP header (the ones that don’t change)
• Doesn’t actually specify the algorithm
– one (keyed MD5) is mandatory to implement for
interoperability
– others may be used between consenting parties
packet data
shared secret
hash function
authentication value
Encapsulating Security Protocol (ESP)
• ESP encrypts and/or authenticates everything
above the IPSec layer
• ESP does not protect fields in the outer IP header
– if you want to protect an IP header, cover it with ESP
and wrap it in another IP packet
• ESP arguably makes AH unnecessary
– even the guy who originally proposed AH agrees
– but these things tend to get lives of their own...
IPSec Key Management
• Both AH and ESP presume a secret key shared by
the two parties
• To establish this key, a key management protocol
called ISAKMP/IKE is defined
– Diffie-Hellman key exchanges signed with RSA, etc
– lots and lots of options to please everybody
• Manual key establishment is still possible if you
don’t want all that complexity
Encryption Above TCP
• Most important Internet applications run atop TCP
– web browsing, remote login, mail transfer, etc
• Much easier to install without OS vendor help
– usually runs in user space
• SSL included in Netscape and IE
– TCP/IP usually implemented in OS kernel, requiring
kernel modifications for IPSec
• Fine-grained (per user) security easy to do
– fine-grained security in IPSec significantly complicated
spec and delayed implementation by years
• No protection for transport headers
Encryption Protocols Above TCP
• Secure Sockets Layer (SSL)
– developed by Netscape to secure web transactions
– very widely deployed in web servers and browsers
• but actually a general purpose transport layer security protocol
– formal X.509 public key certificates
• Secure Shell (SSH)
– developed by Tatu Ylonen for UNIX environments
• originally open source, taken commercial
– scp/ssh/slogin replace insecure rcp/rsh/rlogin
– TCP port forwarding facility
– simplified public key management
• man-in-middle attack on first connect
Application-layer Encryption
• Some Internet applications (esp. email) implement
network-like functionality, making end-to-end
security unattainable at any lower layer
• PGP is most popular email encryption
protocol/software
– public key “web of trust”
– also popular for “clearsigning” software distributions
Encryption Layer Choices
• No one correct answer
• Often desirable to encrypt at multiple layers:
– link layer to thwart traffic analysis
– IP layer to build virtual private networks
– transport or application layer for end-to-end protection
• Architectural issues
– Network address translators (NAT) and IPSEC
Crypto Politics
• Crypto doesn’t distinguish between “good” and
“bad” users (as the government defines them)
• Long regulated for export as a munition by the US
government
– but domestic use never restricted
• US “Clipper” proposal in 1993
– require use of secret algorithm with govt back door
• Significant export relaxation January 2000
– after years of proposed legislation, court challenges and
lobbying
Bernstein Case
• Proposed Internet publication of “Snuffle”
algorithm by CS grad student/professor
• Won at district level in Aug 1997
• Affirmed by 9th Cir panel 2-1 in May 1999
• Granted en banc rehearing
• Remanded to district court after Jan 2000 rule
relaxation
Karn Case
• Focused on paper/machine readable distinction
– source code published on paper is explicitly exportable
– same source code on floppy or Internet was controlled
• only Americans can type…!
• Lost at district level in March 1996
• Remanded by DC Cir in Jan 1997
– cosmetic rule changes (State->Commerce)
– new judge
• Mooted by Jan 2000 rule change
Junger Case
• Law prof seeking to publish crypto source code on
web for students
• Lost in district court July 1998
• Reversed and remanded by 6 Cir panel 3-0 Apr
2000
– surprising considering rule changes in Jan 2000
Current Status of Export Controls
• Publication of non-proprietary crypto source code
on Internet now OK
– but you have to send a copy (or URL) to BXA
• Mass-market products OK after 1-time review
• Direct sales to foreign governments still controlled
• Confusing skeleton of rules remains
– consult your attorneys!
Legal Status
• Bernstein
• Karn
– dismissed at district level, remanded by DC cir
– mooted by Jan 2000 rule relaxation
• Junger
– dismissed at district level, reversed and remanded by
6th Cir