[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