INTERNET-DRAFT                                        Jonathan Trostle
draft-ietf-cat-kerberos-pk-recovery-00.txt
Updates: RFC 1510
expires August 2, 1998


    Public Key Cryptography for KDC Recovery in Kerberos V5


0. Status Of this Memo

   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 docu-
   ments at any time.  It is inappropriate to use  Internet-Drafts  as
   reference  material  or  to  cite them other than as ``work in pro-
   gress.''

   To learn the current status of any Internet-Draft, please check the
   ``1id-abstracts.txt'' listing contained in the Internet-Drafts Sha-
   dow Directories on ds.internic.net (US East  Coast),  nic.nordu.net
   (Europe),  ftp.isi.edu  (US  West Coast), or munnari.oz.au (Pacific
   Rim).

   The distribution of  this  memo  is  unlimited.   It  is  filed  as
   draft-ietf-cat-kerberos-pk-recovery-00.txt, and expires August 2,
   1998. Please send comments to the authors.


1. Abstract

   This document defines extensions to the Kerberos protocol
   specification (RFC 1510, ''The Kerberos Network Authentication
   Service (V5)'', September 1993) to enable the recovery of a
   compromised Kerberos V5 KDC using public key cryptography.
   The document specifies the recovery protocol which uses
   preauthentication data fields and error data fields in Kerberos
   messages to transport recovery data.

2. Motivation

   For both secret key based systems and public key based systems,
   compromise of the security server (KDC in the secret key system and
   CA or certificate authority in the public key system) leads to a
   complete breakdown of the authentication service. The difference
   between the two systems comes when the compromise is detected.
   Assuming that a root key is intact in the public key system, new
   high-level certificates can be signed, any suspicious certificates
   can be revoked, and the system can eventually return to normal
   operation without excessive administrator involvement. For a pure
   secret key based system such as Kerberos V5, the recovery
   operation is very difficult from an administrative point of view,
   since all users must receive new passwords out of band.


   This document describes an extension to Kerberos V5 that can be
   used in conjunction with the protocol in [2]
   (draft-ietf-cat-kerberos-pkinit-05.txt) to allow a KDC to be
   automatically recovered once the administrator has reinstalled
   the operating system and loaded (and certified) the new KDC public
   key. Although the protocols in [2] are a step towards making the KDC
   recovery problem easier, they do not go far enough since there are
   still potentially many secret keys stored on the KDC. For example,
   when the user private key is stored on the KDC, the user and the
   KDC share a secret key that is used for authentication. The two main
   issues for recovery are updating the KDC public key with all clients
   (which will happen automatically if the KDC public keys are signed
   as part of a public key infrastructure with a revocation
   capability), and updating the shared secret keys that are stored on
   the KDC.

   We now describe the requirements for the recovery extension:
   (1) Users that use password based keys to authenticate to the KDC
   (as in section 3.4 of [2] will have those keys automatically changed
   by the recovery protocol; the users will not have to change their
   passwords. We will satisfy this requirement by obtaining the secret
   key K2 of section 3.4 of [2] by hashing the key K1 with a salt value
   supplied by the KDC. The update operation during recovery consists
   of changing the salt value.
   (2) The recovery extension should work either in the case where
   the KDC public keys are signed as keys in a public key infrastructure
   or in the case where the KDC public keys are self-signed (i.e., root
   keys). The second case will be satisfied by downloading multiple
   KDC public keys into clients and keeping the later version KDC
   private keys offline. The second case is useful in an environment
   without a deployed public key infrastructure that includes a
   revocation mechanism.

   We will use the definitions and ASN.1 structures from [2]; we assume
   familiarity on the part of the reader.

3. The Recovery Extension Protocol

   We now briefly overview the proposed recovery extension. When the
   recovery operation is launched, the KDC host operating system along
   with the database is reloaded from backup media. The new KDC public
   key certificate is placed into the appropriate certificate database
   (if needed), and the old certificate is revoked if the the KDC
   certificate was signed by another authority. In the case the KDC
   certificate is self-signed, the KDC contacts the clients that need
   to receive the new certificate (using the
   KDC_ERR_RECOVERY_HOST_NEEDED error code in a KRB_ERROR message).
   This message allows the new self-signed certificates to be
   downloaded. Also, any secret keys will be updated. The
   sequence of messages between the KDC and the client is as follows:


   KDC <-------- AS_REQ (optional) -------- client

   KDC  -------- KRB_ERROR message -------> client
              (error code KDC_ERR_RECOVERY_HOST_NEEDED)
               error data: KDC DH parameters, optional self-signed
                           certs, all signed with new KDC private key

   KDC <-------- AS_REQ message  ---------- client
              (with PA-PK-AS-REQ and PA-PK-RECOVERY-DATA
               preauthentication fields)

   KDC  -------- AS_REP message  ---------> client
              (with PA-PK-AS-REP preauthentication field)


   After these exchanges, the recovery operation is complete except for
   the updating of the kdcSalt value to clients and the creation of new
   user shared secrets in the KDC database. This last task is completed
   by the following sequence of messages:

   KDC <-------- AS_REQ message ----------- client

   KDC  -------- KRB_ERROR message -------> client
              (error code KDC_ERR_RECOVERY_USER_NEEDED)
               error data: KDC DH parameters, kdcSalt value,
               optional PA-PK-KEY-REP (encrypted user private keys))

   KDC <-------- AS_REQ message  ---------- client
              (with PA-PK-AS-REQ and PA-PK-RECOVERY-DATA (with new user
               secret key K2 encrypted in Diffie-Hellman shared secret
               key) preauthentication fields)

   KDC  -------- AS_REP message  ---------> client
              (with PA-PK-AS-REP preauthentication field)

   This exchange of messages is only necessary between the KDC and each
   user principal that has a shared secret key stored in the KDC
   database.

3.1 Definitions

   The proposed extension includes a new algorithm for computing the
   shared key between a user and the KDC. The new algorithm involves
   computing the SHA1 hash of a string (kdcSalt) supplied by the KDC
   concatenated with the RFC 1510 shared key (the key K1 from section
   3.4 of [2]) to obtain a new DES key K2 that is shared between the
   user and the KDC. We propose etype and keytype 16 for this
   algorithm:

      DES-recoverable-key                   16

   If the KDC expects the client to preauthenticate using the key K2
   with keytype DES-recoverable-key, and the client does not
   preauthenticate, then the e-data for the error
   KDC_ERR_PREAUTH_REQUIRED will be present containing the kdcSalt
   value encoded as an OCTET STRING. If the client preauthenticates

   with the key K2 having keytype DES-recoverable-key, the
   preauthentication fails, and the KDC has a key of the same keytype
   in the database, then the e-data for the error KDC_ERR_PREAUTH_FAILED
   will be present containing the kdcSalt value encoded as an OCTET
   STRING.

   As a performance optimization, the kdcSalt is stored in the
   /krb5/salt file along with the realm. Thus the /krb5/salt file
   consists of realm-salt pairs. If the file is missing, or the salt is
   not correct, the above error messages allow the client to find out
   the correct salt. Clients which are configured for symmetric key
   authentication with the keytype DES-recoverable-key attempt to
   preauthenticate with the salt from the /krb5/salt file as an input
   into their key, and if the file is not present, the client does not
   use preauthentication.

   The following new preauthentication types are proposed:

      PA-PK-RECOVERY-SUPPORTED              19
      PA-PK-RECOVERY-DATA                   20

   The following new error codes are proposed:

      KDC_ERR_RECOVER_HOST_NEEDED           67
      KDC_ERR_RECOVER_USER_NEEDED           68

   We propose the following additional KDC database bits. The first new
   KDC database bit applies to all clients (non-human principals) and
   indicates whether a client supports recovery. The second database bit
   applies to all principals to indicate whether a principal should have
   a valid symmetric key in the database. The third bit applies to all
   principals to indicate if the principal symmetric key in the KDC
   database is valid. The fourth bit applies to all clients and
   indicates whether the recovery capable client (this bit is only set
   if the client is recovery capable) needs to receive self-signed KDC
   certificates from the KDC. The fifth bit applies to all clients and
   tells whether the recovery capable client that needs self-signed KDC
   certificates has received them as part of the most recent recovery
   operation.

   The third and fifth database bits are cleared when the KDC undergoes
   a recovery operation.

3.2 Protocol Specification

   We now describe the recovery protocol. The recovery operation can be
   set into motion either because a compromise is detected, or as part of
   a periodic preventative operation. The KDC host operating system and
   KDC executable is restored from backup media, and the KDC is loaded
   with a backup private/public key pair. The KDC database is also
   reloaded, and any secret keys are zeroized. The clients already have
   the public half of this backup key pair in the form of a self-signed
   certificate, or the new KDC public key is signed by the appropriate
   authority and placed in the appropriate location and any necessary
   revocation steps are taken for the old certificate.

   Any clients that hold the KDC public keys in the form of self-signed
   certificates must be notified by the KDC and sent any new self-signed

   certificates. These clients can now discard the current KDC self
   -signed certificate (if it has not already been discarded due to an
   expired validity date). We propose ports 10001/TCP and 10001/UDP as
   the ports for these clients to listen on.

   The KDC will notify the clients that need new self-signed certificates
   and/or to update their secret keys with a KRB_ERROR message with error
   code KDC_ERR_RECOVERY_HOST_NEEDED. The following ASN.1 structure is
   encoded and placed into the error message e-data field (an OCTET
   STRING):

   HostRecoveryError ::= SEQUENCE {
           kdcPublicValue     [0] SubjectPublicKeyInfo,
                                                     -- DH algorithm
           kdcPubValueId      [1] INTEGER,           -- DH algorithm
                                                     -- index for KDC
           nonce              [2] INTEGER OPTIONAL,  -- Only if in
                                                     -- response to AS_REQ
                                                     -- (copy nonce)
           newKDCPubKey       [3] KDCPubKey OPTIONAL
                                                     -- only if KDC sends
                                                     -- new self-signed
                                                     -- certs or kdcCert
  }

  KDCPubKey ::= CHOICE {
           kdcCert            [0] SEQUENCE OF Certificates
                                                     -- KDC cert chain
                                                     -- from [2]
           newKDCCertInfo     [1] KDCCertInfo
  }


  KDCCertInfo ::= SEQUENCE {
           kdcPublicKeys      [0] SEQUENCE OF Certificate
                                                     -- New KDC self-signed
                                                     -- certificates
           kdcPublicKeyKvno   [1] INTEGER            -- New KDC public
                                                     -- key kvno
  }

   The e-cksum field of the error message is not optional for this error
   code; it will contain the signature of the entire error message (as
   described in [1]: the signature is computed over the ASN.1 encoded
   error message without the e-cksum field, and then the signature is
   placed into the e-cksum field and the message is re-encoded.) The KDC
   will sign using the private half of its new active key pair. The key
   version number for the signing key must correspond to the new
   KDC certificate.

   The purpose of the kdcPubValueId identifier in the error message is
   to enable the KDC to offload state to the client; the client will then
   send this identifier to the KDC in an AS_REQ message; the identifier
   allows the KDC to look up the Diffie Hellman private value corresponding
   to the identifier. Depending on how often the KDC updates its private
   Diffie Hellman parameters, it will have to store anywhere between a
   handful and several dozen of these identifiers and their parameters.


   The newKDCCertInfo field is only present if the KDC sends new self
   -signed certificates to the client.

   Note: The non-PKI protocol for recovery depends on the downloading of
   new public key certificates into the client as a notification mechanism
   that the old KDC public key certificate is revoked. In the case where
   some clients are intermitently connected to the network (e.g., laptops
   and dial-in clients), then the non-PKI protocol for recovery may leave
   these intermitently connected clients open to server spoofing attacks.
   One way to solve this problem is to shorten the validity period of the
   KDC public key certificates. Another solution to the problem is to
   integrate PKI functionality (a revocation mechanism) into the
   Kerberos V5 public key clients.

   If the KRB_ERROR message passes the security checks (the nonce should
   match the client AS_REQ nonce if the error message is a reply, the KDC
   signature validates and the signing key has the proper key version
   number (kvno), and the KDC self-signed certificates are valid), the
   client replies to the KDC with an AS_REQ message containing the
   PA-PK-RECOVERY-DATA padata-type preauthentication field along with a
   PA-PK-AS-REQ preauthentication field (see [2]):

   PA-PK-RECOVERY-DATA ::= SEQUENCE {
           kdcPubValueId      [0] INTEGER,           -- Copied from error
                                                     -- message
           kdcPublicKeyKvno   [1] INTEGER OPTIONAL   -- New KDC public
                                                     -- key kvno if
                                                     -- KDCCertInfo was
                                                     -- present in error
                                                     -- (copied)
           newUserKey         [2] EncryptedData      -- only present in
                                  OPTIONAL           -- reply to
                                                     -- KDC_ERR_RECOVERY_
                                                     -- USER_NEEDED error;
                                                     -- uses DH shared
                                                     -- key to encrypt the
                                                     -- new key K2.
           sigAll             [3] Signature          -- uses shared DH key
                                                     -- computed over
                                                     -- entire encoded
                                                     -- AS_REQ without
                                                     -- this field, then
                                                     -- re-encode message
                                                     -- with this field
   }

   The clientPublicValue field in the AuthPack structure must be filled
   in by the client (in the PA-PK-AS-REQ preauthentication field, since
   Diffie-Hellman is required).

   Upon receiving this message from the client, the KDC then makes the
   normal PA-PK-AS-REQ validation and also checks that the sigAll seal
   is valid after computing the shared Diffie-Hellman key. We note that
   the KDC should use the ctime and cusec fields in the PA-PK-AS-REQ
   message to ensure that the client AS_REQ message is not a replay.

   (The KDC also checks that the kdcPublicKeyKvno is correct (that it
   is the current version), and uses the kdcPubValueId to look up its
   own Diffie-Hellman parameters).

   The KDC now sends an AS_REP message with the PA-PK-AS-REP
   preauthentication fields.
   The client should validate this message (including the normal
   PA-PK-AS-REP checks) before updating any secret keys or KDC
   self-signed certificates.

   To complete the recovery process, the KDC will also notify users
   that need to update any shared secrets that are stored in the KDC
   database; a KRB_ERROR message with the error code
   KDC_ERR_RECOVERY_USER_NEEDED is sent in response to these user's
   AS_REQ messages that do not contain the PA-PK-RECOVERY-DATA
   preauthentication types. The following ASN.1 structure is encoded
   and placed into the error message e-data field (an OCTET STRING):

     UserRecoveryError ::= SEQUENCE {
           kdcSalt            [0] OCTET STRING,      -- to be hashed
                                                     -- with password
                                                     -- key K1
           kdcPublicValue     [1] SubjectPublicKeyInfo,
                                                     -- DH algorithm
           kdcPubValueId      [2] INTEGER,           -- DH algorithm
           nonce              [3] INTEGER OPTIONAL,  -- copy nonce
                                                     -- from AS_REQ
                                                     -- if paPkKeyRep
                                                     -- is not below
           paPkKeyRep         [4] OCTET STRING OPTIONAL
                                                     -- ASN.1 encoded
                                                     -- PA-PK-KEY-REP
                                                     -- from section
                                                     -- 3.4 of [2]
                                                     -- (encrypted
                                                     -- user private
                                                     -- keys)
           kdcCert            [5] SEQUENCE OF Certificate, OPTIONAL
                                                     -- cert chain
     }

   The e-cksum field of the error message is not optional for this error
   code; it will contain the signature of the entire error message (as
   described in [1]: the signature is computed over the ASN.1 encoded
   error message without the e-cksum field, and then the signature is
   placed into the e-cksum field and the message is re-encoded.) The
   KDC will sign using the private half of its new active key pair.

   Upon checking the KRB_ERROR message, the client obtains the user
   password and uses the kdcSalt to compute the new key K2 which is
   computed by SHA1 hashing the concatenation of the kdcSalt and the
   key K1 obtained from the user password. The result of the hash is
   converted into a DES key by truncating the last 12 bytes and fixing
   the parity on each of the first 8 bytes. The client then responds
   with a new AS_REQ message that includes both a PA-PK-RECOVERY-DATA
   padata-type preauthentication field along with a PA-PK-AS-REQ
   preauthentication field (see [2]). The PA-PK-RECOVERY-DATA must

   contain the newUserKey field. If the user's AS_REQ message passes
   the security checks, the KDC will reply with an AS_REP message
   that contains a PA-PK-AS-REP preauthentication field. The client
   will validate this message as described in [2].

   We also define the PA-PK-RECOVERY-SUPPORTED preauthentication
   field; it will accompany all AS_REQ messages from clients that
   support the recovery protocol. It serves as an optimization to
   allow the KDC to quickly identify whether the requesting client
   supports recovery. The padata-value for this padata-type is an
   empty octet string.

4. Encryption of User Private Key on KDC

   We now discuss recovery issues that arise when the user stores his
   private key on the KDC in a key derived from a password. As in
   conventional Kerberos V5, it is important that a good password
   policy be used. This password policy will prevent dictionary
   attacks against the user private key by an attacker that
   compromises the KDC.

   A weakness of using the DES algorithm to encrypt the user private
   key is that the keyspace is only 56 bits. Thus the attacker that
   compromises the KDC can perform an offline brute force attack
   against the encrypted user private key. We list three approaches
   to improving security with respect to such attacks; we solicit
   input on these and other approaches.

   (1) Use a new encryption algorithm for encrypting private keys: a
   strawman is the following DESX-like algorithm. The password is
   required to be at least 10 characters and the first 64 bits of it
   are used as a pre-xor key and as a post-xor key before and after
   the normal DES encryption step is completed. Perhaps another
   variable length cipher would be appropriate here.

   (2) Change the recovery protocol to allow the password derived key
   K1 that encrypts the user private key to be automatically changed
   (by hashing it with a KDC supplied value) after a compromise.

   (3) Force users to change their passwords and private keys after a
   compromise, or just change passwords and private keys for users that
   have a lot of access rights. Perhaps an extra bit in the database
   could be used to indicate which users need to change their password
   as part of the recovery operation.

5. Acknowledgement

   This work was previously published as part of draft-ietf-cat-
   kerberos-pkinit-02.txt while the author was employed at Cybersafe
   Corporation, 1605 NW Sammamish Rd., Suite 310, Issaquah, WA 98027.

6. Bibliography

   [1] J. Kohl, C. Neuman. The Kerberos Network Authentication
   Service (V5). Request for Comments 1510.

   [2] B. Tung, C. Neuman, J. Wray, A. Medvinsky, M. Hur, J. Trostle.
   Public Key Cryptography for Initial Authentication in Kerberos.
   ftp://ds.internic.net/internet-drafts/
   draft-ietf-cat-kerberos-pkinit-05.txt

7. Expiration Date

This draft expires on August 2, 1998.


8. Authors' Addresses

   Jonathan Trostle
   150 Woodside Dr.
   Provo, UT 84604

   Email: jtrostle@world.std.com, jtt@aa.net