[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Photuris KMP draft
Network Working Group Phil Karn
Internet Draft Qualcomm
expires in six months December 1994
The Photuris Key Management Protocol
draft-karn-photuris-00.txt
Status of this Memo
This document is a submission to the IP-Security Working Group of the
Internet Engineering Task Force (IETF). Comments should be submitted
to the ipsec@ans.net mailing list.
Distribution of this memo is unlimited.
This document is an Internet-Draft. Internet Drafts are working
documents of the Internet Engineering Task Force (IETF), its Areas,
and its Working Groups. Note that other groups may also distribute
working documents as Internet Drafts.
Internet Drafts are draft documents valid for a maximum of six
months, and may be updated, replaced, or obsoleted by other documents
at any time. It is not appropriate to use Internet Drafts as
reference material, or to cite them other than as a ``working draft''
or ``work in progress.''
To learn the current status of any Internet-Draft, please check the
``1id-abstracts.txt'' listing contained in the internet-drafts Shadow
Directories on ds.internic.net (US East Coast), nic.nordu.net
(Europe), ftp.isi.edu (US West Coast), or munnari.oz.au (Pacific
Rim).
Abstract
Photuris [1] is an experimental key management protocol intended for
use with the IP Security Protocol (IPSP) in a point-to-point mode.
Photoris is still in the early design stages and has not yet been
completely implemented. Detailed packet formats are not yet
specified, but it is hoped that this draft will stimulate discussion
about the merits of the design philosphy.
Karn expires in six months [Page i]
DRAFT Photuris December 1994
1. Introduction
Users must have confidence in every Internet Security component,
including key management. Users will rely on Internet Security to
protect the confidentiality of the traffic they send across the
Internet, and they depend on it to block unauthorized external access
to their internal hosts and networks. Otherwise, they will either
erect barriers that impede legitimate use of the Internet, or they
will forego the Internet entirely.
Photuris combines Diffie-Hellman key exchange with RSA authentication
to provide perfect forward secrecy, as defined by Diffie [2]. The
protocol is also designed to thwart certain types of active denial of
service attacks on host resources.
This draft assumes familiarity with both the Diffie-Hellman and RSA
public-key algorithms. Good descriptions can be found in [5].
1.1. Use of Public-Key Cryptography
Widespread deployment and use of an Internet Security protocol is
possible without public-key cryptography. For example, Kerberos [6]
can generate host-pair keys for use in Internet Security much as it
now generates session keys for use by encrypted telnet and other
kerberized applications.
The Kerberos model has some widely recognized drawbacks. Foremost is
the requirement for a highly available on-line key distribution
center with a database containing every principal's secret key. This
carries significant security risks.
Public-key cryptography decentralizes things considerably. Entities
authenticate themselves to each other, and generate shared session
keys, without real-time communication with any other party.
Photuris is based on public-key cryptography, specifically Diffie-
Hellman and RSA. Photuris uses RSA only for signature purposes, so
in principle it could be replaced by the Digital Signature Standard
(DSS).
1.2. Defense against Sabotage
The ultimate goal of Internet Security is to facilitate direct IP
connectivity between sensitive internal hosts and the external
Karn expires in six months [Page 1]
DRAFT Photuris December 1994
Internet. Protecting sensitive data on these hosts against
compromise -- either by interception or by unauthorized access -- is
necessary, but not sufficient.
The computing resources themselves must also be protected against
malicious attack or sabotage. This is accomplished mainly by the
authentication facilities in Internet Security. If a packet does not
pass an authentication check, it can be immediately discarded at
relatively little cost, given the speed of fast cryptographic hash
functions (such as MD5).
Internet Security does not place any significance on easily forged IP
source addresses. It relies instead on proof of possession of secret
knowledge: that is, a cryptographic key.
But there is a potential Achilles heel in the key management
protocol. If we are to grant access to authorized users regardless
of location, we must be able to cheaply detect and discard bogus
packets. Otherwise, an attacker intent on sabotage might rapidly
send them to exhaust the host's CPU or memory resources.
This is easily done with manual (null) key management, since each
packet encounters only the fast crypto-hash functions just mentioned.
But key management schemes based on public-key cryptography are
potentially vulnerable because of their use of CPU-intensive
operations, such as modular exponentiation. Although a complete
defense against such attacks is impossible, a simple feature makes
them much more difficult.
Photuris exchanges a "cookie" before initiating public-key
operations, thwarting the saboteur from using random IP source
addresses. He must then either:
1) use his own IP address,
2) gain access to a transmission link to a subnet whose addresses he
appropriates, or
3) subvert Internet routing for the same purpose.
The first option allows the target to detect and filter out such
attacks, and significantly increases the likelihood of identifying
the attacker.
The latter two options are much more difficult than merely sending
large numbers of datagrams with randomly chosen IP source addresses
from an arbitrary point on the Internet.
Karn expires in six months [Page 2]
DRAFT Photuris December 1994
1.3. Perfect Forward Secrecy
As Diffie points out, many security breaches in government
cryptographic systems have been facilitated by designs that generate
traffic-encrypting keys (or their equivalents) well before they are
needed, and then keep them around longer than necessary. This
creates many opportunities for compromise, especially by insiders. A
carefully designed public-key system can avoid this problem.
The rule is to avoid using any long-lived keys (such as an RSA key
pair) to encrypt session keys or actual traffic. Such keys should be
used solely for authentication purposes. All keys for traffic
encryption should be randomly generated immediately before use, and
then destroyed immediately after use, so that they cannot be
recovered.
Photuris uses a combination of Diffie-Hellman (for key exchange) and
RSA (for authentication), as follows:
1. Agree on a session key using the Diffie-Hellman algorithm.
2. Authenticate the Diffie-Hellman exchanges with a digital
signature algorithm, such as RSA or DSS. This authenticates
the parties to each other, and thwarts the "man in the middle"
active attack against Diffie-Hellman.
When the session key generated in step 1 is eventually destroyed, it
is gone for good. The generating information is not based on any
other stored information.
Theft of the secret key used to sign the exchanges in step 2 would
allow the thief to impersonate the party in future conversations, but
it would not allow him to decode any past traffic that he might have
recorded.
1.4. Mobile Traffic Anonymity
A fundamental role of a key management protocol is to verify the
identities of the communicating parties to each other. But one would
often like to deny this information to an eavesdropper, especially
when this would reveal the location of a mobile user. Although each
packet carries a cleartext IP destination address, the ultimate
destination could be hidden by "laundering" it through an encrypted
tunnel.
A mobile user's IP source address could be hidden in the same manner.
Karn expires in six months [Page 3]
DRAFT Photuris December 1994
If the address has been dynamically allocated, it provides no useful
information to an eavesdropper.
This leaves the identifying information that the mobile user sends
during key exchange. This identification can be easily protected in
the two-step DH/RSA protocol by encrypting the RSA signature
exchanges with the key just established with Diffie-Hellman. This
keeps a passive eavesdropper from learning the identities of the
parties, either by checking the signatures against a known database
of public keys, or by intercepting possible exchanges of public keys
and certificates.
The scheme is not foolproof. By posing as the home system, an active
attacker could trick the mobile user into revealing his identity.
But an active attack is considerably more difficult than passive
vacuum-cleaner monitoring. And unless the attacker can steal the RSA
secret key belonging to the user's home system, the mobile user will
discover the deception when checking the RSA signature in the home
system's key exchange message.
1.5. Multicast Support
Key management is much more difficult in a multicast environment.
The author is not convinced that it is possible to provide all the
features just described in a multicast key management protocol.
Since the most common use of Internet Security will be in
conventional point-to-point IP communications, the author feels that
the lack of multicast support in Photuris is acceptable.
Nothing in this proposal is meant to discourage the development of
other key management protocols with multicast support. If such a
protocol can also provide all of the design features of Photuris with
reasonable complexity, this author is willing to withdraw this
proposal.
The author is also open to suggestions on how multicast capability
might be added to Photuris, without compromising its fundamental
features.
Karn expires in six months [Page 4]
DRAFT Photuris December 1994
2. Protocol Description
The Photuris protocol combines all these elements into a single
protocol. The protocol consists of three phases:
1. A "cookie" exchange to guard against simple flooding attacks
with bogus IP source addresses.
2. A Diffie-Hellman key exchange to establish a session key for
conventional encryption.
3. An encrypted exchange of RSA signatures on the Diffie-Hellman
messages that were sent in step 2 to verify their integrity and
the identities of the two parties.
Regular operation of the Internet Security protocol (encryption
and/or authentication of user packets) then begins.
Either party may initiate a key exchange. This party is the
initiator, while the other party is the responder. The initiator is
responsible for recovering from all packet losses by retransmission.
3. Cookie Exchange
3.1. Cookie Request
The initiator initializes local state, and sends a COOKIE_REQUEST
message to the responder containing the initiator's cookie. The
initiator starts a retransmission timer. If no response is obtained
within the time limit, the same COOKIE_REQUEST is retransmitted.
3.2. Cookie Response
On receipt of the COOKIE_REQUEST, the responder generates a cookie
for the incoming IP source address, and returns it in a
COOKIE_RESPONSE message, along with the initiator's cookie.
Note that the responder creates no state at this time.
3.3. Cookie Generation
The exact method in which a Photuris entity generates a cookie is
Karn expires in six months [Page 5]
DRAFT Photuris December 1994
implementation dependent. The function chosen must satisfy some
basic requirements:
1. The cookie must depend on the remote IP address. This prevents
an attacker from obtaining a cookie with his real IP address,
and then using it to swamp the victim with Diffie-Hellman
requests from randomly chosen IP addresses.
2. It must not be possible for anyone other than the issuing
entity to generate cookies that will be accepted by that
entity. This implies that the issuing entity must use local
secret information in the generation and subsequent
verification of a cookie, and it must not be possible to deduce
this secret information from any particular cookie.
3. The cookie generation function must be fast to thwart attacks
intended to sabotage CPU resources.
A recommended method is to run a cryptographic one-way hash function
(such as MD5) over the remote IP address and a locally generated
random value. An incoming cookie can be verified at any time by
regenerating it locally from the incoming IP address and the local
random value. The random value may be generated once at boot time
and remain static until the next reboot. It is kept secret.
4. Diffie-Hellman Exchange
4.1. Diffie-Hellman Request
On receipt of a valid COOKIE_RESPONSE, the initiator sends a
DH_REQUEST message containing the following items:
a) The initiator's cookie.
b) The responder's cookie.
c) The public part of the initiator's Diffie-Hellman exchange.
d) The prime modulus used to compute (c).
e) A list of transport protocols supported by the initiator
f) A list of Internet Security encapsulation modes (encryption and
authentication algorithms) supported by the initiator.
g) A policy indicator showing whether the initiator requires the use
Karn expires in six months [Page 6]
DRAFT Photuris December 1994
of authentication on incoming Internet Security protected packets.
The initiator then starts a timer that runs until it receives a
DH_RESPONSE message. If the timer expires, the same DH_REQUEST is
retransmitted.
4.2. Diffie-Hellman Response
On receipt of a valid DH_REQUEST message, the responder returns a
DH_RESPONSE message with the following items:
a) The initiator's cookie.
b) The responder's cookie.
c) The public part of the initiator's Diffie-Hellman exchange,
computed using the prime modulus received in the DH_REQUEST
message.
d) A list of transport protocols supported by the responder.
e) A list of Internet Security encapsulation modes (encryption and
authentication algorithms) supported by the responder.
f) A policy indicator showing whether the responder requires the use
of authentication on incoming Internet Security protected packets.
At this time, the responder begins execution of the final modular
exponentiation step in Diffie-Hellman that yields a shared key.
The responder keeps a copy of the incoming DH_REQUEST message, and
its DH_RESPONSE message. If a duplicate DH_REQUEST is received, it
merely resends the previous DH_RESPONSE message, and takes no further
action.
4.3. Session Key Computation
On receipt of the DH_RESPONSE message, the initiator begins execution
of the final modular exponentiation step in Diffie-Hellman that
yields a shared key.
This final step is executed in parallel with the responder's
computation, minimizing delay.
Karn expires in six months [Page 7]
DRAFT Photuris December 1994
Both the initiator and responder use the resulting shared key to
encrypt all subsequent exchanges, with the exception of any
DH_RESPONSE retransmissions.
Each party selects an encryption mode (if any) according to its own
local policy database, and the list of encryption functions supported
by the other party.
Each party additionally selects an authentication function according
to the requirements and facilities of the other party.
Note that the encryption and authentication modes, as well as the
IP-IP encapsulation mode (if any), need not be the same in both
directions.
4.4. Random Number Generation
The security of Diffie-Hellman depends critically on the quality of
the secret random numbers generated by each party. A poor random
number generator at either end will compromise the shared key
produced by the algorithm.
Generating cryptographic quality random numbers on a general purpose
computer without hardware assistance is a very tricky problem. In
general, this requires using a cryptographic hash function to
"distill" the entropy from a large number of semi-random external
events, such as the timing of key strokes. An excellent discussion
can be found in [4].
4.5. Moduli
It is envisioned that a small set of recommended strong primes for
use as Diffie-Hellman moduli will be specified in the Photuris
standard. The preferred modulus will be 1024 bits long. The modulus
indicated in the "Diffie-Hellman Request" may then take the form of a
one-byte index into a well-known table, with a reserved escape value
allowing an arbitrary modulus.
Use of a very limited number of moduli (preferably one) has one minor
and one very significant advantage:
Minor advantage:
Avoiding the overhead of sending the full modulus in every
DH_REQUEST packet.
Karn expires in six months [Page 8]
DRAFT Photuris December 1994
Major advantage:
Allowing each party to precompute the public DH part in the
DH_REQUEST and DH_RESPONSE, and for the RSA signatures (described
later).
A background process can periodically destroy the old values,
generate a new random secret, and recalculate the public DH part
and the RSA signature. This limits the exposure of the secret, as
past secrets are not kept for possible discovery by a future
intrusion, protecting earlier communications. Also, the secret
currently in use is less likely to be anticipated, as the element
of random timing is introduced.
Since these operations involve several time-consuming modular
exponentiations, moving them to the "background" substantially
speeds up the apparent execution speed of the Photuris protocol.
It also allows a single DH key pair and associated RSA signature
to be used in several closely spaced Photuris executions, when
setting up security associations with several different hosts over
a short period of time, thus reducing total CPU loading.
4.6. Size of Secret DH Components
There is surprisingly little guidance in the literature about how
large the randomly chosen secret exponent in Diffie-Hellman should
be. The size of this exponent dramatically affects the speed of both
modular exponentiations involved in Diffie-Hellman.
For example, a single modular exponentiation on a 486-66DX2 processor
using RSAREF and Borland C under MS-DOS took 20 seconds with a 1024-
bit prime modulus and a 1024-bit random exponent. This dropped to
about 1 to 1.5 seconds when the random exponent was shortened to 256
bits, with the same 1024-bit modulus.
Therefore, it is desirable to use the smallest random exponent that
is consistent with good security. The most conservative advice
received to date [3] is to make the random exponent twice as long as
the intended session key. This ensures that any space/time "meet in
the middle" attack on the discrete logarithm problem will be at least
as complex as a brute-force search on the resulting session key
space.
Karn expires in six months [Page 9]
DRAFT Photuris December 1994
5. Signature Exchange
5.1. Signature Transmission
When each party completes its parallel computation of the Diffie-
Hellman key agreement, and encryption has begun, each party sends the
other a RSA_SIG message containing the following items:
a) The initiator's cookie.
b) The responder's cookie.
c) An RSA signature on the public part of the sender's Diffie-Hellman
exchange.
d) The corresponding RSA public key, or an indicator of same.
e) Certificates on the RSA public key (optional).
Each party keeps a copy of its RSA_SIG message and starts a timer.
When it receives the other party's RSA_SIG message, it stops the
timer.
If it does not receive the other party's RSA_SIG message before the
timer expires, it retransmits its own RSA_SIG message and restarts
the timer. If it receives a duplicate of the other party's RSA_SIG
message (after its timer has been stopped), it retransmits its own
RSA_SIG message without restarting the timer.
5.2. Signature Verification
The two parties now verify the RSA signatures just received. If they
fail, the users are notified, and the security association is
destroyed. If they succeed, normal operation begins with the
encryption and/or authentication of user packets.
Each party implements local policy that determines what access, if
any, is granted to the holder of a particular RSA key pair. Exchange
of RSA public key certificates is optional; early implementations may
wish to keep their own trusted public key databases, and accept only
those users found there.
Any encrypted and/or authenticated user packets received before the
completion of RSA signature verification are placed on a queue
pending completion of this step. If the RSA verification succeeds,
the queue is processed as though the packets had arrived subsequent
Karn expires in six months [Page 10]
DRAFT Photuris December 1994
to the verification. If the verification fails, the queue is
discarded.
Karn expires in six months [Page 11]
DRAFT Photuris December 1994
A. Strong Primes
This 1024-bit prime p, expressed in hex, has the property that both p
and (p-1)/2 are prime:
1 a4788e2184b8d68bfe02690e4dbe485b17a80bc5f21d680f1a8413139734f7f2b0db4e253750018a
ad9e86d49b6004bbbcf051f52fcb66d0c5fca63fbfe634173485bbbf7642e9df9c74b85b6855e942
13b8c2d89162abeff43424350e96be41edd42de99a6961638c1dac598bc90da069b50c414d8eb865
2adcff4a270d567f
The recommended generator g for this prime is 5.
Although this prime is suggested for use in this protocol,
cooperating installations might use additional primes.
Karn expires in six months [Page 12]
DRAFT Photuris December 1994
Security Considerations
Security issues are the topic of this memo.
References
[1] "Photuris" is the latin name for the firefly.
"Firefly" is in turn the name for NSA's
(classified) key exchange protocol for the STU-
III secure telephone. Informed speculation has
it that Firefly is based on very similar design
principles.
[2] Whitfield Diffie, "Authenticated Key Exchange and
Secure Interactive Communication", Northern
Telecom, Securicom '90, Paris France, 16 March
1990.
[3] Martin Hellman, personal communication.
[4] Eastlake, Crocker & Schiller, "Randomness
Requirements for Security", work in progress.
[5] Bruce Schneier, "Applied Cryptography", ISBN 0-
471-59756-2.
[6] Kerberos?
Acknowledgements
Thanks go to Bill Simpson for his protocol suggestions, editorial
changes and NROFF formatting.
Author's Address
Questions about this memo can also be directed to:
Phil Karn
Qualcomm, Inc.
6455 Lusk Blvd.
San Diego, California 92121-2779
Karn expires in six months [Page 13]
DRAFT Photuris December 1994
karn@qualcomm.com
karn@unix.ka9q.ampr.org
Karn expires in six months [Page 14]
DRAFT Photuris December 1994
Table of Contents
1. Introduction .......................................... 1
1.1 Use of Public-Key Cryptography .................. 1
1.2 Defense against Sabotage ........................ 1
1.3 Perfect Forward Secrecy ......................... 3
1.4 Mobile Traffic Anonymity ........................ 3
1.5 Multicast Support ............................... 4
2. Protocol Description .................................. 5
3. Cookie Exchange ....................................... 5
3.1 Cookie Request .................................. 5
3.2 Cookie Response ................................. 5
3.3 Cookie Generation ............................... 5
4. Diffie-Hellman Exchange ............................... 6
4.1 Diffie-Hellman Request .......................... 6
4.2 Diffie-Hellman Response ......................... 7
4.3 Session Key Computation ......................... 7
4.4 Random Number Generation ........................ 8
4.5 Moduli .......................................... 8
4.6 Size of Secret DH Components .................... 9
5. Signature Exchange .................................... 10
5.1 Signature Transmission .......................... 10
5.2 Signature Verification .......................... 10
APPENDICES ................................................... 12
A. Strong Primes ......................................... 12
SECURITY CONSIDERATIONS ...................................... 13
REFERENCES ................................................... 13
ACKNOWLEDGEMENTS ............................................. 13
AUTHOR'S ADDRESS ............................................. 13