Internet DRAFT - draft-karn-photuris
draft-karn-photuris
HTTP/1.1 200 OK
Date: Tue, 09 Apr 2002 09:26:46 GMT
Server: Apache/1.3.20 (Unix)
Last-Modified: Tue, 11 Apr 1995 22:00:00 GMT
ETag: "323f44-f0f4-2f8afbe0"
Accept-Ranges: bytes
Content-Length: 61684
Connection: close
Content-Type: text/plain
Network Working Group Phil Karn
Internet Draft Qualcomm
W A Simpson
DayDreamer
expires in six months March 1995
The Photuris Session Key Management Protocol
draft-karn-photuris-01.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:
ftp.is.co.za (Africa)
nic.nordu.net (Europe)
ds.internic.net (US East Coast)
ftp.isi.edu (US West Coast)
munnari.oz.au (Pacific Rim)
Abstract
Photuris [1] is an experimental session-key management protocol
intended for use with the IP Security Protocols (AH and ESP) in a
point-to-point mode.
Karn & Simpson expires in six months [Page i]
DRAFT Photuris March 1995
Photuris is still in the early design stages and has not yet been
completely specified. It is hoped that this draft will stimulate
discussion about the merits of the design philosophy.
Karn & Simpson expires in six months [Page ii]
DRAFT Photuris March 1995
1. Introduction
The ultimate goal of Internet Security is to facilitate direct IP
connectivity between sensitive hosts and users across the Internet.
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 depend on it to
block unauthorized external access to their internal hosts and
networks. Without this confidence, users may erect barriers that
impede legitimate use of the Internet, or forego the Internet
entirely.
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.
Photuris combines Diffie-Hellman key exchange with authentication to
provide perfect forward secrecy, as defined by Diffie [2]. The
protocol is also designed to thwart certain types of denial of
service attacks on host resources.
This draft assumes familiarity with the Diffie-Hellman public-key
algorithm. A good description can be found in [5].
1.1. Terminology
Initiator The key establishment party which sends the first
Photuris session request.
public/private key-pair
A pair of keys, one of which is publically
distributable, the other of which is kept secret.
public-value As used in this document, the publically
distributable value used in the D-H exchange to
calculate a shared-secret.
Responder The key establishment party which receives the first
Photuris session request.
shared-secret As used in this document, the calculated result of
the D-H exchange.
Karn & Simpson expires in six months [Page 1]
DRAFT Photuris March 1995
secret-key A single key which is not publically distributable
and not part of a public/private key-pair.
Security Association
A collection of parameters describing the security
relationship between two nodes. These parameters
include the transform (including algorithm and
algorithm mode), the key(s) (such as a secret-key,
or appropriate public/private key-pair), and
possibly other information such as sensitivity
labelling. For further details, see [A-SA].
1.2. Use of Public-Key Cryptography
Photuris is based on public-key cryptography, specifically Diffie-
Hellman key exchange. Exchange of D-H public-values based on
private/secret values results in a mutual shared-secret between the
parties. This shared-secret can be used on its own, or to generate a
series of session-keys for authentication and encryption of
subsequent traffic.
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 (KDC), with a database containing every principal's secret-
key. This carries significant security risks.
Public-key cryptography enables decentralization. Entities generate
session-keys without real-time communication with any other party.
1.3. Authentication
It has been shown in [DOW92] that key exchange must be coupled to
authentication. Photuris supports the use of a variety of digital
signature methods.
The Photuris messages include selection of authentication algorithms,
and facilitate the exchange of any chosen certificate type. The DSS
and RSA are examples of digital signatures which will provide strong
Karn & Simpson expires in six months [Page 2]
DRAFT Photuris March 1995
authentication. Details of DSS, RSA, and other signature algorithms
may be found in [5].
1.4. Defense against Clogging
Protecting sensitive data on the Internet 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.
To grant access to authorized users regardless of location, it must
be possible to cheaply detect and discard bogus datagrams.
Otherwise, an attacker intent on sabotage might rapidly send
datagrams to exhaust the host's CPU or memory resources.
Using Internet Security authentication facilities, when a datagram
does not pass an authentication check, it can be discarded without
further processing. This is easily done with manual (null) key
management between trusted hosts at relatively little cost, given the
speed of cryptographic hash functions compared to public-key
algorithms.
Unfortunately, such a trusted host will have only a fixed number of
keys available. The keys will tend to have long lifetimes. This
carries significant security risks.
Automatic key management is necessary to generate keys between
parties without prior arrangement. But, there is a potential
Achilles heel in the key management protocol.
Because of their use of CPU-intensive operations, such as modular
exponentiation, key management schemes based on public-key
cryptography are vulnerable to resource clogging attacks. 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. The simple validation of this cookie uses the same level
of resources as other Internet Security authentication mechanisms.
This limits an attacker to methods which intercept the cookie,
forcing the attacker to:
1) use her own IP address,
Karn & Simpson expires in six months [Page 3]
DRAFT Photuris March 1995
2) gain access to a transmission link to a subnet whose addresses she
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.
The cookie does not protect against an observer which can copy a
valid cookie, or an interceptor which can modify or substitute
another cookie. These attacks are mitigated through using time-
variant cookies, and the elimination of receiver state during initial
exchanges of the protocol.
1.5. Perfect Forward Secrecy
Many security breaches in cryptographic systems have been facilitated
by designs which 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
digital signature authentication, as follows:
1. Agree on a shared-secret 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, thwarting the "man in the middle"
active attack against Diffie-Hellman.
When the shared-secret generated in step 1 is eventually destroyed,
it is unrecoverable. The generating information is not based on any
other stored information.
Karn & Simpson expires in six months [Page 4]
DRAFT Photuris March 1995
Theft of the private/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 decode any past traffic that might
have been recorded.
1.6. Traffic Anonymity
As noted above, a fundamental role of a key management protocol is to
verify the identities of the communicating parties to each other.
One would often like to deny this information to an eavesdropper,
especially when this would reveal the location of a user. Although
each datagram carries a cleartext IP Destination address, the
ultimate destination could be hidden by "laundering" it through an
encrypted tunnel.
A user's IP Source address could be hidden in the same manner. If
the address has been dynamically allocated, it provides no useful
information to an eavesdropper.
This leaves the identifying authentication information that the user
sends during key exchange. The identification can be easily
protected in the Photuris protocol by encrypting the digital
signature exchanges with the key just established with Diffie-
Hellman. This keeps a passive eavesdropper from learning the
identities of the parties by intercepting possible exchanges of
public keys and certificates, or by checking the signatures against a
known database of public keys.
The scheme is not foolproof. By posing as the Responder, an active
attacker could trick the Initiator into revealing her identity.
However, this active attack is considerably more difficult than
passive vacuum-cleaner monitoring. Unless the attacker can steal the
private/secret key belonging to the Responsder, the Initiator will
discover the deception when checking the digital signature of the key
exchange.
1.7. Security Parameters
In addition to the key(s) used to encrypt, decrypt or authenticate
the payload, the key management mechanism is used to determine a
number of parameters for each Security Association between the
communicating parties. This includes the particular authentication
and/or encryption transforms.
Karn & Simpson expires in six months [Page 5]
DRAFT Photuris March 1995
The key management implementation usually maintains a table
containing the several parameters for each current Security
Association. The implementation needs to access that security
parameter table to determine how to process each datagram.
The Security Parameters Index (SPI) is assigned by the entity
controlling the IP Destination address. A session between two
parties will normally have two SPI values (one in each direction).
The parties use the combination of SPI and IP Destination to
distinguish the correct association.
The selection mechanism used for the SPI is implementation dependent.
However, selection of a random value can help prevent attacks which
depend on a predicatable sequence of values.
To provide protection against an interceptor which can modify or
substitute another SPI, the SPI is used in creating a separate
session-key in each direction. While alteration of the SPI will
interrupt communication, the attacker will gain no additional
information.
1.8. Multicast Support
Key management is more difficult in a multicast environment.
Senders to a multicast group may share common a Security Parameters
Index, if all communications are using the same security
configuration parameters. In this case, the receiver only knows that
the message came from a node knowing the SPI for the group, and
cannot authenticate which member of the group sent the datagram.
Multicast groups may also use a separate SPI value for each Source.
If each sender is keyed separately and asymmetric algorithms are
used, data origin authentication is also provided.
A given Destination is not necessarily in control of the selection
process. In the case of multicast groups, a single node or
cooperating subset of the multicast group may work on behalf of
the entire group to set up a Security Association.
The author is also open to suggestions on how multicast capability
might be added to Photuris, without compromising its fundamental
features.
Karn & Simpson expires in six months [Page 6]
DRAFT Photuris March 1995
2. Protocol Description
The Photuris protocol consists of several simple phases:
1. A "cookie" exchange to guard against simple flooding attacks
with bogus IP Source addresses.
2. A Diffie-Hellman exchange to establish a session-key for
conventional authentication or encryption.
3. An exchange of digital signatures on the Diffie-Hellman
messages that were sent in phase 2, to verify their integrity
and the identities of the two parties. This exchange may be
encrypted to protect the privacy of the parties.
4. Once an initial Security Association has been established,
regular operation of the Internet Security protocol begins
encryption and/or authentication of user datagrams.
5. Additional messages may be exchanged to periodically change the
session-key and to establish new security parameters.
Either party may initiate a session at any time. For example, the
Initiator need not be a "caller" in a telephony link.
The Initiator is responsible for recovering from all message losses
by retransmission. The Responder remains stateless until a session-
key has been created. Once the session-key calculation has been
initiated, the Responder cooperates in creating a second
serendipitous session-key, in order to save the effort of another
round of key establishment in the other direction.
When both parties initiate Photuris key establishment concurrently,
or one party initiates more than one Photuris session, the UDP Ports
keep the sessions separate. This results in more than one SPI for
each Destination. There is no requirement that all such SPIs be
used. The sender chooses the SPI for each transmission.
Old SPI simply expires after a short period of time (typically 30
seconds), and is purged sometime later (typically 10 minutes).
LifeTimes are implementation dependent.
Should an expired SPI (which is not yet purged) arrive from an IP
Source, a new COOKIE_REQUEST is sent, and the Photuris exchange
begins again.
Karn & Simpson expires in six months [Page 7]
DRAFT Photuris March 1995
Implementation Notes:
To provide user-oriented keying, or create multiple Security
Associations with different parameters, the sender can initiate
multiple Photuris exchanges.
It is the responsibility of the sender to assign and segregate the
different session-keys.
The Destination SHOULD be capable of maintaining multiple SPI
values for each Source.
2.1. UDP
All Photuris messages use the User Datagram Protocol header [RFC-
768]. The Initiator sends to UDP Destination Port <tbd>. The
Responder reverses the IP Source and Destination, and the UDP Source
and Destination Ports.
The UDP checksum is required. Any message with an incorrect or zero
UDP checksum is silently discarded.
2.2. Variable Precision Numbers
Many of the message fields require a value which may vary in the
number of bits. These bits may not make up an integral number of
octets. Each variable precision number is composed of two parts.
Size 2 octets. Number of bits used in the value. Always
transmitted most significant octet first.
Value variable. The bits used are right justified and
zero filled on octet boundaries; that is, any unused
bits are in the most significant octet. Always
transmitted most significant octet first.
2.3. Transforms
Whether authenticating or encrypting, selection among several
different transforms is needed to enable future implementation
changes without affecting the basic protocol. Each party specifies a
list of the transforms supported.
Karn & Simpson expires in six months [Page 8]
DRAFT Photuris March 1995
The list includes authentication, encryption, and signature types.
These are mixed in the same list for simplicity. The implementation
can easily distinguish between the separate uses of each supported
type.
This is not a "negotiation". The Destination indicates what
facilities it supports in order of preference, and the Source selects
from that list.
Each party selects an authentication function from the list of
mechanisms supported by the other party. Authentication policy is in
the receiver direction. Only the receiver can determine that
arriving traffic is authentic. It indicates its need for
authentication by including authentication transforms, and/or
authenticated encryption transforms, in its transform list. It
enforces the authentication through the simple expedient of dropping
all datagrams that don't arrive with authentication.
Each party additionally selects an encryption mode (if any) according
to its own local policy database. Encryption policy is in the
transmitter direction. Only the sender knows whether each datagram
needs privacy protection. If no, it picks an authentication-only
algorithm SPI. If yes, it picks an encryption algorithm SPI.
Note that the authentication, encryption and signature mechanisms, as
well as the encapsulation mode (if any), need not be the same in both
directions.
Up-to-date values for the Transform are specified in the most recent
"Assigned Numbers" [RFC-1700]. Initial values are assigned as
follows:
Transforms
K INR S
0 Administratively Configured + + +
1 SHA + + +
2 MD2 + + +
3 unassigned
4 MD4 + + +
5* MD5 + + +
6 RSA +
7 DSS +
8 PGP certificate +
9 X.509 certificate +
10 DNS-SIG certificate +
11 unassigned
12 RC2 +
13 unassigned
Karn & Simpson expires in six months [Page 9]
DRAFT Photuris March 1995
14 RC4 +
15 IDEA +
16 DES-CBC, 0-bit IV +
17* DES-CBC, 32-bit IV +
18* DES-CBC, 64-bit IV +
19 unassigned
20 Triple DES-CBC, 0-bit IV +
21 Triple DES-CBC, 32-bit IV +
22 Triple DES-CBC, 64-bit IV +
24 unassigned
* (implementation required)
2.4. Modular Exponentiation Groups
The original Diffie-Hellman technique specified modular
exponentiation. A public-value is generated using a generator (g),
raised to a private/secret exponent (x), modulo a prime (p).
(g**x) mod p
When two of these public-values are exchanged between parties, the
parties can calculate a shared-secret value between themselves.
Each modular exponentiation prime (p) must have the property that
both p and (p-1)/2 are prime. A small set of such recommended strong
primes for use as Photuris moduli are specified.
The modulus-index takes the form of a small index into a well-known
table (see "Group Table" Appendix). Since only the first few indices
will be published, the remaining values may be used by cooperating
parties to indicate private moduli.
Use of a very limited number of moduli (preferably one) has one minor
and two very significant advantages:
Overhead
Avoiding the overhead of sending the full modulus.
Prime and Generator Pair Selection
Discovery of strong primes is extremely computationally intensive,
and practically impossible for commercially available processors
to find in a reasonable interactive time. Thus, the primes used
will be well-known, and embedded in the implementations.
Karn & Simpson expires in six months [Page 10]
DRAFT Photuris March 1995
The generator (g) should be chosen such that the secret exponents
will generate all possible public exponential values, evenly
distributed throughout the range, without cycling through a
smaller subset. Such a generator is called a "primitive root"
(which is trivial to find when p is strong) [!!! reference].
When the strong prime and generator pair are well chosen, the
difficulty of a discrete log attack is maximized. By choosing the
pairs in advance, thorough analysis of the pair characteristics is
possible. This analysis can promote confidence in the security of
the implementations.
Precomputation
Each party can precompute the D-H public-value.
A background process can periodically destroy the old values,
generate a new random secret exponent, and recalculate the
public-value. This limits the exposure of both the secret
exponenent and shared-secret, as past secrets are not kept for
possible discovery by a future intrusion, protecting earlier
communications. Also, the secret exponent 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 reduces CPU loading sufficiently to allow a single
public/private key-pair to be used in several closely spaced
Photuris executions, when setting up Security Associations with
several different hosts over a short period of time.
Other precomputation suggestions are described in [w].
2.5. Elliptic Curve Groups
The points on an elliptic curve form a group under addition CITE[x].
This group can be used as the basis for the efficient implementation
of the Diffie-Hellman operations. In order to uniquely specify the
computation, the implementor must know the finite field for
representation of the point coordinates, the elliptic curve, and the
generator.
Note that while the literature uses the term "addition" for the group
operation, it is directly analogous to "multiplication" in modular
Karn & Simpson expires in six months [Page 11]
DRAFT Photuris March 1995
exponentiation groups. Thus, the analogous term for "g**r" is "r*g"
(that is, the scalar multiple r of g).
The generator is specified as the (x,y) coordinates of an elliptic
curve point, and the representation of x and y is given with respect
to a finite field. Multiples of the generator are (x,y) pairs.
Thus, the Initiator and Responder D-H public-values are to be
interpreted as two concatenated bit values in the order (x,y). The
lengths of the numbers are implicit in the specification of the
field.
The field representation is uniquely determined by the irreducible
polynomial specified in the group description.
The elliptic curve addition formulas are more complicated than
straight-forward component-wise addition, and the use of finite
fields further complicates the description of the algorithms. A good
reference for a succinct description of elliptic curves with finite
fields is CITE[y]; a more general treatment can be found in CITE[y].
(same cite ???)
Use of a very limited number of fields has similar advantages to
those cited for modular exponentiation: reduced overhead, generator
selection, and precomputation of the public-values.
Karn & Simpson expires in six months [Page 12]
DRAFT Photuris March 1995
3. Cookie Exchange
3.1. Cookie Request
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
~ Initiator-Cookie ~
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Groups ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
Type 0
Reserved Unused. Zero filled.
Initiator-Cookie 16 octets. A randomized value which identifies the
exchange.
Groups variable. A list of one or more groups supported by
the Responder, in order of preference (see "Group
Table" Appendix). Each value is one octet. The end
of the list is indicated by the Length of the UDP
datagram.
The Initiator initializes local state, and sends a COOKIE_REQUEST
message to the Responder.
The Initiator also starts a retransmission timer. If no
COOKIE_RESPONSE is obtained within the time limit, a new
COOKIE_REQUEST is retransmitted. The I-Cookie value in each
successive request SHOULD be different.
Karn & Simpson expires in six months [Page 13]
DRAFT Photuris March 1995
3.2. Cookie Response
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Group-Index | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
~ Initiator-Cookie ~
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
~ Responder-Cookie ~
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
~ Responder-Public-Value ~
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Transforms ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
Type 1
Group-Index A Responder selected value which indicates which
group will be used for the exchange (see "Group
Table" Appendix).
Reserved Unused. Zero filled.
Initiator-Cookie 16 octets. Copied from the COOKIE_REQUEST.
Responder-Cookie 16 octets. A randomized value which identifies the
exchange.
Responder-Public-Value
variable precision number. The format is indicated
by the Group-Index. Must not be zero or one.
Transforms variable. A list of one or more transforms
supported by the Responder, in order of preference.
Each value is one octet. The end of the list is
indicated by the Length of the UDP datagram.
On receipt of a COOKIE_REQUEST, the Responder generates a cookie, and
returns it in a COOKIE_RESPONSE message. The R-Cookie value in each
successive response MAY be different.
Karn & Simpson expires in six months [Page 14]
DRAFT Photuris March 1995
When too many SPI values are already in use, the COOKIE_REQUEST Is
ignored.
Note that the Responder creates no state at this time.
3.3. Cookie Generation
The exact method by which a Photuris party generates a cookie is
implementation dependent. The function chosen must satisfy some
basic requirements:
1. The cookie must depend on the specific parties. This prevents
an attacker from obtaining a cookie using a real IP address and
UDP port, and then using it to swamp the victim with Diffie-
Hellman requests from randomly chosen IP addresses or ports.
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. 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 calculate a fast cryptographic one-way
hash function (such as MD5) over the IP Source and Destination
addresses, the UDP Source and Destination ports, and a locally
generated secret random value. An incoming cookie can be verified at
any time by regenerating it locally from values contained in the
incoming IP datagram and the local secret random value.
When an old (or invalid) cookie is detected by the Initiator, the
message is silently discarded.
When an old (or invalid) cookie is detected by the Responder, it is
indicated to the Initiator in an ERROR_MESSAGE, which begins the
Photuris exchange again from the COOKIE_REQUEST.
Implementation Notes:
The Initiator secret random value which affects the cookie SHOULD
change for each new COOKIE_REQUEST, and is thereafter cached on a
Responder basis. This provides improved synchronization and
protection against replay attacks.
Karn & Simpson expires in six months [Page 15]
DRAFT Photuris March 1995
The Responder secret random value is changed whenever the
Responder D-H public-value is changed, in order to detect changes
between COOKIE_RESPONSE and KEY_REQUEST.
Karn & Simpson expires in six months [Page 16]
DRAFT Photuris March 1995
4. Security Parameter Exchange
4.1. Key Request
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | I-Transform | I-Parameters |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Initiator-Security-Parameter-Index |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
~ Initiator-Cookie ~
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
~ Responder-Cookie ~
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| LifeTime |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
~ Initiator-Public-Value ~
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Transforms ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
Type 2
I-Transform An authentication or encryption transform selected
by the Initiator from the list of Transforms in the
COOKIE_RESPONSE.
I-Parameters The format and contents of this field are specific
to the I-Transform chosen. The formats are detailed
in the transform specifications. Common transform
formats are included in the "Transform Parameters"
Appendix.
Initiator-Security-Parameter-Index (I-SPI)
The SPI to be used for communicating with the
Initiator.
Initiator-Cookie 16 octets. Copied from the COOKIE_RESPONSE.
Responder-Cookie 16 octets. Copied from the COOKIE_RESPONSE.
LifeTime The number of seconds remaining before the I-SPI
Karn & Simpson expires in six months [Page 17]
DRAFT Photuris March 1995
expires.
Initiator-Public-Value
variable precision number. The format is indicated
by the Group-Index in the COOKIE_RESPONSE. Must not
be zero or one.
Transforms variable. A list of one or more transforms
supported by the Initiator, in order of preference.
Each value is one octet. The end of the list is
indicated by the Length of the UDP datagram.
On receipt of a COOKIE_RESPONSE, the Initiator validates the
Initiator-Cookie. Invalid messages are silently discarded.
When a valid COOKIE_RESPONSE has been received, a KEY_REQUEST is
sent. Later COOKIE_RESPONSES between the same parties are silently
discarded, until a new COOKIE_REQUEST is sent.
The Initiator also starts a retransmission timer. If no KEY_RESPONSE
is obtained within the time limit, the same KEY_REQUEST is
retransmitted.
Implementation Notes:
At this time, the Initiator can begin calculation of the D-H
shared-secret. This may take a substantial amount of time. The
implementor should ensure that retransmission is not blocked by
this calculation. Typically, this is not a problem, as
retransmission timeouts exceed calculation time.
Karn & Simpson expires in six months [Page 18]
DRAFT Photuris March 1995
4.2. Key Response
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | R-Transform | R-Parameters |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Responder-Security-Parameter-Index |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
~ Initiator-Cookie ~
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
~ Responder-Cookie ~
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| LifeTime |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Reserved | K-Transform | K-Parameters |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Type 3
R-Transform An authentication or encryption transform selected
by the Responder from the list of Transforms in the
KEY_REQUEST.
R-Parameters The format and contents of this field are specific
to the R-Transform chosen. The formats are detailed
in the transform specifications. Common transform
formats are included in the "Transform Parameters"
Appendix.
Responder-Security-Parameter-Index (R-SPI)
The SPI to be used for communicating with the
Responder.
Initiator-Cookie 16 octets. Copied from the KEY_REQUEST.
Responder-Cookie 16 octets. Copied from the KEY_REQUEST.
LifeTime The number of seconds remaining before the R-SPI
expires.
Reserved Unused. Zero filled.
K-Transform A cryptographic hash function selected by the
Responder from the intersection of the two lists of
Karn & Simpson expires in six months [Page 19]
DRAFT Photuris March 1995
Transforms, which is used to calculate the session-
key. This transform is not necessarily the same as
either SPI Transform in use.
K-Parameters The format and contents of this field are specific
to the K-Transform chosen. Common transform formats
are included in the "Transform Parameters" Appendix.
On receipt of a KEY_REQUEST, the Responder validates the Responder-
Cookie. Invalid messages are silently discarded.
The Responder keeps a copy of the incoming KEY_REQUEST message, and
its KEY_RESPONSE message. If a duplicate KEY_REQUEST is received, it
merely resends the previous KEY_RESPONSE message, and takes no
further action.
Implementation Notes:
At this time, the Responder begins calculation of the D-H shared-
secret. This may take a substantial amount of time. The
implementor should ensure that retransmission is not blocked by
this calculation. Typically, this is not a problem, as
retransmission timeouts exceed calculation time.
4.3. Session-Key Computation
Each session-key is the K-Transform cryptographic hash of the the
computed D-H shared-secret, followed by (concatenated with) the SPI,
followed by (concatenated with) the remote party (SPI owner) Cookie
followed by (concatenated with) the local party Cookie. Since the
SPI is likely to be different in each direction, and the order of the
Cookies is different in each direction, the resulting session-key
will usually be different in each direction.
Both the Initiator and Responder use the resulting SPI session-keys
to authenticate or encrypt subsequent messages, including the
SIGNATURE_MESSAGE, REKEY_MESSAGE, and new instantiations of the
Photuris exchange between the same nodes.
Implementation Notes:
Calculation of the D-H shared-secret by the Initiator and
Responder is executed in parallel to minimize delay.
The D-H public-values and resulting shared-secret SHOULD be cached
for the LifeTime of the SPI. When multiple Photuris exchanges
Karn & Simpson expires in six months [Page 20]
DRAFT Photuris March 1995
occur between the same parties, and the public-values are
discovered to be unchanged, the cached shared-secret can be used
to rapidly generate new session-keys.
Note that the Cookie order is reversed when calculating the
Responder session-key.
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 party will compromise the shared-secret
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. Secret D-H 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.
The exponent 0 will generate the public value 1, and exponent 1 will
generate the public value g mod p. These exponents do not qualify as
secret. In general, small secret exponent values should not be used.
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.
Implementation Notes:
A single modular exponentiation on a 486-66DX2 processor using
RSAREF and Borland C under MS-DOS took 20 seconds with a 1024-bit
Karn & Simpson expires in six months [Page 21]
DRAFT Photuris March 1995
prime modulus and a 1024-bit random exponent. This dropped to
about 1 to 1.5 seconds when the random exponent was shortened to
128 bits, with the same 1024-bit modulus.
The size of the exponent is entirely implementation dependent, is
unknown to the other party, and can be easily changed.
Karn & Simpson expires in six months [Page 22]
DRAFT Photuris March 1995
5. Signature Exchange
5.1. Signature Message
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | S-Transform | S-Parameters |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
~ Initiator-Cookie ~
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
~ Responder-Cookie ~
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
~ Signature ~
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
~ Certificate ~
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Type 4
S-Transform An authentication or certificate transform selected
from the list of Transforms sent by the peer, which
is used to calculate the Signature. This transform
is not necessarily the same as any SPI Transform in
use.
S-Parameters The format and contents of this field are specific
to the transform chosen. Common transform formats
are included in the "Transform Parameters" Appendix.
Reserved Unused. Zero filled.
Initiator-Cookie 16 octets. Copied from the KEY_REQUEST.
Responder-Cookie 16 octets. Copied from the KEY_REQUEST.
Signature variable precision number. The indicated S-
Transform is calculated over the SPI session-key for
this direction, followed by (concatenated with) the
Karn & Simpson expires in six months [Page 23]
DRAFT Photuris March 1995
remote party (SPI owner) Public-Value, followed by
(concatenated with) the local party Public-Value,
and optionally followed by (concatenated with) an
identifying public-key, certificate, or
distinguishing name of the local party.
Note that the order of the Public-Values is
different in each direction.
Certificate variable precision number. The presence or absence
of this field is indicated by the Length of the UDP
datagram.
When the S-Transform indicates a certification
method, such as X.509, PGP or DNS-SIG, the
certificate is always included.
When the Initiator completes its parallel computation of the D-H
shared-secret, and upon receipt of a valid KEY_RESPONSE, it sends a
SIGNATURE_MESSAGE to the Responder. This message is required to be
authenticated or encrypted, using the R-SPI Transform indicated in
the KEY_RESPONSE.
The Initiator also starts a retransmission timer. If no
SIGNATURE_MESSAGE is obtained within the time limit, the same
SIGNATURE_MESSAGE is retransmitted.
When the Responder completes its parallel computation of the D-H
shared-secret, and upon receipt of a valid SIGNATURE_MESSAGE, it
sends a SIGNATURE_MESSAGE to the Initiator. This message is required
to be authenticated or encrypted, using the I-SPI Transform indicated
in the KEY_REQUEST.
The Responder keeps a copy of its SIGNATURE_MESSAGE. If a duplicate
SIGNATURE_MESSAGE is received, it merely resends the previous
SIGNATURE_MESSAGE, and takes no further action.
5.2. Signature Verification
The two parties now verify the signatures 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 datagrams.
Each party implements local policy that determines what access, if
any, is granted to the holder of a particular certification.
Karn & Simpson expires in six months [Page 24]
DRAFT Photuris March 1995
Implementation Notes:
Any encrypted and/or authenticated user datagrams received before
the completion of signature verification can be placed on a queue
pending completion of this step. If the verification succeeds,
the queue is processed as though the datagrams had arrived
subsequent to the verification. If the verification fails, the
queue is discarded.
Early implementations may wish to keep their own trusted public-
key databases, such as the Pretty Good Privacy web of trust, and
accept only those users found there.
Karn & Simpson expires in six months [Page 25]
DRAFT Photuris March 1995
6. Other Message Types
6.1. Re-Key Message
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | N-Transform | N-Parameters |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Security-Parameter-Index |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
~ Initiator-Cookie ~
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
~ Responder-Cookie ~
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| LifeTime |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Type 5
N-Transform An authentication or encryption transform selected
from the list of Transforms sent by the peer, which
is used for the new SPI. This transform is not
necessarily the same as any SPI Transform in use.
N-Parameters The format and contents of this field are specific
to the N-Transform chosen. Common transform formats
are included in the "Transform Parameters" Appendix.
Security-Parameter-Index
The SPI to be used for incoming communications.
This value is required to be different from existing
SPI values. The value zero indicates all old SPIs
for this IP Destination.
Initiator-Cookie 16 octets. Copied from the KEY_REQUEST.
Responder-Cookie 16 octets. Copied from the KEY_REQUEST.
LifeTime The number of seconds remaining before the SPI
expires. A value of zero indicates deletion of the
indicated SPI.
At any time after the validation of signatures, either party can send
a REKEY_MESSAGE. The message has effect only in one direction.
Karn & Simpson expires in six months [Page 26]
DRAFT Photuris March 1995
When too many SPI values are already in use, an ERROR_MESSAGE is
sent.
No retransmission timer is necessary. Success of the re-keying is
indicated by the peer use of the new SPI. Failure will be indicated
at expiration of the old SPI, which begins the Photuris exchange
again from the COOKIE_REQUEST.
This message is required to be authenticated or encrypted.
The new session-key is calculated in the same fashion as described
previously. The resulting session-key will be different because the
SPI value is different. Since the cached D-H shared-secret remains
the same, no new exponentiation is needed.
Karn & Simpson expires in six months [Page 27]
DRAFT Photuris March 1995
6.2. Error Message
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Code | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
~ Initiator-Cookie ~
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
~ Responder-Cookie ~
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Type 7
Code Indicates the problem:
0 reserved
1 invalid/expired cookie
2 too many concurrent key requests
Reserved Unused. Zero filled.
Initiator-Cookie 16 octets. Copied from the offending message.
Responder-Cookie 16 octets. Copied from the offending message.
Issued in response to Photuris state loss or other problems. The
message has effect only in one direction.
No retransmission timer is necessary.
This message is not required to be authenticated or encrypted.
Karn & Simpson expires in six months [Page 28]
DRAFT Photuris March 1995
A. Group Table
Although these groups are suggested for use in this protocol,
cooperating installations might use additional groups.
(1) Implementation Required. A 1024-bit strong prime (p),
expressed in hex:
a478 8e21 84b8 d68b fe02 690e 4dbe 485b
17a8 0bc5 f21d 680f 1a84 1313 9734 f7f2
b0db 4e25 3750 018a ad9e 86d4 9b60 04bb
bcf0 51f5 2fcb 66d0 c5fc a63f bfe6 3417
3485 bbbf 7642 e9df 9c74 b85b 6855 e942
13b8 c2d8 9162 abef f434 2435 0e96 be41
edd4 2de9 9a69 6163 8c1d ac59 8bc9 0da0
69b5 0c41 4d8e b865 2adc ff4a 270d 567f
The recommended generator (g) for this prime is 5.
This prime was randomly generated by a freely available program
written by the author.
(2) Implementation Optional. Elliptic curve:
curve: y^2 + xy = x^3 + 0x7338F
generator: (0x7B, 0x1C8)
irreducible polynomial: u^155 + u^62 + 1
Supplied by Hilarie Orman <ho@cs.arizona.edu>.
(129) Moduli-indices of 129 to 254 are available for private use.
B. Transform Parameters
B.1. (Triple) DES-CBC
B.2. MD5
There are no parameters. The Parameters field may be any (preferably
random) value on transmission, and will be ignored on receipt.
Karn & Simpson expires in six months [Page 29]
DRAFT Photuris March 1995
Security Considerations
Security issues are the topic of this memo.
Acknowledgements
This protocol has many elements in common with the Station-To-Station
authentication protocol, described in [DOW92].
Hilarie Orman provided text regarding elliptic curves, and extensive
review of the protocol details.
Paul C van Oorschot suggested signing both the public exponents and
the session-key, in order to provide an authentication-only version
of signature verification.
Randall Atkinson, Cheryl Madson, James Hughes, and Perry Metzger
provided useful critiques of earlier versions of this document.
Thanks to Bill Simpson for his protocol suggestions, editorial
changes and NROFF formatting. All such mistakes are his
responsibity.
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.
Karn & Simpson expires in six months [Page 30]
DRAFT Photuris March 1995
[6] Kerberos?
[A-SA] Randall Atkinson, "Security Architecture for the Internet
Protocol", work in progress.
[DOW92] Whitfield Diffie, Paul C van Oorshot, Michael J Wiener,
"Authentication and Authenticated Key Exchanges", Designs,
Codes and Cryptography, v 2 pp 107-125, Kluwer Academic
Publishers, 1992.
[w] E. Brickell, D. Gordon, K. McCurley, and D. Wilson, "Fast
Exponentiation with Precomputation (Extended Abstract)",
Advances in Cryptology -- EUROCRYPT '92, Lecture Notes in
Computer Science, 658 (1993), Springer-Verlag, 200-207.
[x] Alfred J. Menezes, "Elliptic Curve Public Key
Cryptosystems", Kluwer Academic Publishers, 1993.
[y] Alfred J. Menezes, Minghua Qu, and Scott A. Vanstone,
"Standard for RSA, Diffie-Hellman and Related Public Key
Cryptography", Working Draft of IEEE P1363 Standard, Oct.
30, 1994. http://www.rsa.com/pub/p1363/draft/
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@qualcomm.com
karn@unix.ka9q.ampr.org
William Allen Simpson
Daydreamer
Computer Systems Consulting Services
1384 Fontaine
Madison Heights, Michigan 48071
Bill.Simpson@um.cc.umich.edu
bsimpson@MorningStar.com
Karn & Simpson expires in six months [Page 31]
