2. Services Used

   Aside from operating system services needed to maintain its internal
   state, DASS relies on a global distributed database in which to store
   its certificates, a reliable source of time, and a source of random
   numbers for creating cryptographic keys.

2.1 Time Service

   DASS requires access to the current time in several of its
   algorithms.  Some of its uses of time are security critical.  In
   others, network synchronization of clocks is required.  DASS does
   not, however, depend on having a single source of time which is both
   secure and tightly synchronized.

   The requirements on system provided time are:

    - For purposes of validating certificates and tickets, the
      system needs access to know the date and time accurate to
      within a few hours with no particular synchronization
      requirements.  If this time is inaccurate, then valid requests
      may be rejected and expired messages may be accepted.
      Certificate expiration is a backup revocation mechanism, so
      this can only cause a security compromise in the event of
      multiple failures.  In theory, this could be provided by
      having a local clock on every node accurate to within a few
      hours over the life of the product to provide this function.

      If an insecure network time service is used to provide this
      time, there are theoretical security threats, but they are
      expected to be logistically impractical to exploit.

    - For purposes of detecting replay of authentication tokens, the
      system needs access to a  strictly monotonic time source which
      is reasonably synchronized across the network (within a few
      minutes) for the system to work, but inaccuracy does not
      present a security threat except as noted below. It may
      constitute an availability threat because valid requests may
      be rejected.  In order to get strict monotonicity in the
      presence of a rapid series of requests, time must be returned
      with high precision.  There is no requirement for a high
      degree of accuracy.  Inaccurate time could present a security
      threat in the following scenario: if a client's clock is made
      sufficiently fast that its tokens are rejected, someone
      harvesting those tokens from the wire could replay them later
      and impersonate the client.  In some environments, this might
      be an easier threat than harvesting tokens and preventing
      their delivery.

    - For purposes of aging stale entries from caches, DASS requires
      reasonably accurate timing of intervals.  To the extent that
      intervals are reported as shorter than the actually were,
      revocation of certificates from the naming service may not be
      as timely as it should be.

2.2 Random Numbers

   In order to generate keys, DASS needs a source of "cryptographic
   quality" random numbers.  Cryptographic quality means that
   knowing any of the "random numbers" returned from a series and
   knowing all state information which is not protected, an attacker
   cannot predict any of the other numbers in the series.  Hardware
   sources are ideal, but there are alternative techniques which may
   also be acceptable. A 56 bit "truly random" seed (say from a
   series of coin tosses) could be used as a DES key to encrypt an
   infinite length known text block in CBC mode to produce a pseudo-rand
   sequence provided the key and current point in the sequence were
   adequately protected.  There is considerable controversy
   surrounding what constitutes cryptographic quality random
   numbers, and it is not a goal of this document to resolve it.

2.3 Naming Service

   DASS stores creates and uses "certificates" associated with every
   principal in the system, and encrypted credentials associated
   with most.  This information is stored in an on-line service

   associated with the principal being certified.  The long term
   vision is for DASS to use an X.500 naming service, and DASS will
   from its inception authenticate X.500 names.  To avoid a
   dependence on having an X.500 naming service available (and to
   gain the benefits of a "login agent" that controls password
   guessing), an alternative certificate  distribution center
   protocol is also described.

   The specific requirements DASS places on the naming service are:

    - It must be highly available.  A user's naming service entry
      must be available to any node where the user is to obtain
      services (or service will be denied).  A server's naming
      service entry must be available from any node from which the
      service is to be invoked (or service will be denied).

    - It must be timely.  The presence of "stale" information in the
      naming service may cause some problems.  When a password
      changes, the old password may remain valid (and the new
      password invalid) to the extent the naming service provides
      stale information.  When a user or server is added to the
      network, it will not be able to participate in authentication
      until the information added to the naming service is available
      at the node doing the authentication.  In the unusual
      circumstance that a key changes, the entity whose key has
      changed will not be able to use the new key until the new
      certificate is uniformly available.

    - It must be secure with regard to certain specific properties.
      In general, the security of DASS protected applications does
      not depend on the security of the naming service.  It is
      expected that the availability needs of the naming service
      will prevent it from being as secure as some applications need
      to be.  There are two aspects of DASS security which do depend
      on the security of the naming service: timely revocation of
      certificates and protection of user secrets against dictionary
      based password guessing. DASS depends on the removal of
      certificates from the naming service in order to revoke them
      more quickly than waiting for them to time out.  For this
      mechanism to provide any actual security, it must not be
      possible for a network entity to "impersonate" the naming
      service and the naming service must be able to enforce access
      controls which prevent a revoked certificate from being
      reinstated by an unauthorized entity.  In the long run, it is
      expected that DASS itself will be used to secure the naming
      service, which presents certain potential recursion problems
      (to be addressed in the naming service design).  If the naming
      service is not authenticated (as is expected in early

      versions) attacks where a revoked certificate is "reinstated"
      through impersonation of the naming service are possible.

   The specific functions DASS requests of the naming service are
   simple:

    - Given an X.500 name, store a set of certificates associated
      with that name.

    - Given an X.500 name, retrieve the set of certificates
      associated with that name.

    - Given an X.500 name, store a set of encrypted credentials
      associated with that name.

    - Given and X.500 name, retrieve a set of encrypted credentials
      associated with that name.

   Implementation over a particular naming service may implement more
   specialized functions for reasons of efficiency.  For example, the
   certificates associated with a name may be separated into several
   sets (child, parent, cross, self) so that only the relevant ones may
   be retrieved.  In order that access to the naming service itself be
   secure, the protocols should be authenticated.  Certificates should
   generally be readable without authentication in order to avoid
   recursion problems.  Requests to read encrypted credentials should be
   specialized and should include proof of knowledge of the password in
   order that the naming service can audit and slow down false password
   guesses.

   The following sections describe the interfaces to specific naming
   services:

2.3.1 Interface to X.500

   Certificates associated with a particular name are stored as
   attributes of the entry as specified in X.509.  X.509 defines
   attributes appropriate for parent and cross certificates
   (CrossCertificatePair, CACertificate) for some principals; we will
   have to define a DASSUserPrincipal object class including these
   attributes in order to properly use them with ordinary users.
   Retrieval is via normal X.500 protocols.  Certificates should be
   world readable and modifiable only by appropriate authorities.

   Encrypted credentials are stored with the entry of the principal
   under a yet to be defined attribute.  The credentials should be
   encoded as specified in section 4.  In the absence of extensions to
   the X.500 protocol to control password guessing, the encrypted

   credentials should be world readable and updatable only by the named
   principal and other appropriate authorities.

2.3.2 Interface to CDC

   The CDC (Certificate Distribution Center) is a special purpose name
   server created to service DASS until an X.500 service is available in
   all of the environments where DASS needs to operate.  The CDC uses a
   special purpose protocol to communicate with DASS clients.  The
   protocol was designed for efficiency, simplicity, and security.  CDCs
   use DASS as an authentication mechanism and to protect encrypted
   credentials from unaudited password guessing.

   Each DASS client maintains a list of CDCs and the portion of the
   namespace served by that CDC.  Each directory has a master replica
   which is the only one which will accept updates.  The CDCs maintain
   consistency with one another using protocols beyond the scope of this
   document.  When a DASS client wishes to make a request of a CDC, it
   opens a TCP or DECnet connection to the CDC and sends an ASN.1 (BER)
   encoded request and receives a corresponding ASN.1 (BER) encoded
   response.  Clients are expected to learn the IP or DECnet address and
   port number of the CDC supporting a particular name from a local
   configuration file.  To maximize performance, the requests bundle
   what would be several requests if made in terms of requests for
   individual certificates.  It is intended that all certificates needed
   for an authentication operation be retrievable with at most two CDC
   requests/responses (one to the CDC of the client and one to the CDC
   of the server).

   Documented here is the protocol a DASS client would use to retrieve
   certificates and credentials from a CDC and update a user password.
   This protocol does not provide for updates to the certificate and
   credential databases.  Such updates must be supported for a practical
   system, but could be done either by extensions to this protocol or by
   local security mechanisms implemented on nodes supporting the CDC.
   Similarly, availability can be enhanced by replicating the CDC.
   Automating the replication of updates could be implemented by
   extensions to this protocol or by some other mechanism.  This
   specification assumes that updates and replication are local matters
   solved by individual CA/CDC implementations.

   Requests and responses are encoded as follows:

2.3.2.1 ReadPrinCertRequest

   This request asks the CDC to return the child certificates and
   selected incoming cross certificates for the specified object.  The
   format of the request is:

        ReadPrinCertRequest ::= [4] IMPLICIT SEQUENCE {
             flags [0] BIT STRING DEFAULT {},
             index [1] IMPLICIT INTEGER DEFAULT 0,
             resolveFrom [2] Name OPTIONAL,
             principal Name,
             crossCertIssuers ListOfIssuers OPTIONAL
             }
        ListOfIssuers ::= SEQUENCE OF Name

   The first 24 bits of flags, if present, contain a protocol version
   number.  Clients following this spec should place the value 2.0.0 in
   the three bytes.  Servers following this spec should accept any value
   of the form 1.x.x or 2.x.x.  flags bits beyond the first 24 are
   reserved for future use (should not be supplied by clients and should
   be ignored by servers).

   index is only used if the response exceeds the size of a single
   message; in that case, the query is repeated with index set to the
   value that was returned by ReadPrinCertResponse.  resolveFrom and
   principal imply a set of entities for which certificates should be
   retrieved.  resolveFrom (if present) must be an ancestor of principal
   and child certificates will be retrieved for principal and all names
   which are ancestors of principal but descendants of resolveFrom.  The
   encoding of names is per X.500 and is specified in more detail in
   section 4.  The CDC returns the certificates in order of the object
   they came from, parents before children.

   crossCertIssuers is a list of cross certifiers that would be believed
   in the context of this authentication.  If supplied, the CDC may
   return a chain of certificates starting with one of the named
   crossCertIssuers and ending with the named principal.  One of
   resolveFrom or crossCertIssuers must be present in any request; if
   both are present, the CDC may return either chain.

2.3.2.2 ReadPrinCertResponse

   This is the response a CDC sends to a ReadPrinCertRequest.  Its
   syntax is:

        ReadPrinCertResponse ::= [5] IMPLICIT SEQUENCE {
             status [0] IMPLICIT CDCstatus DEFAULT success,
             index [1] INTEGER OPTIONAL,
             resolveTo [2] Name OPTIONAL,
             certSequence [3] IMPLICIT CertSequence,
             indexInvalidator [4] OCTET STRING (SIZE(8)) OPTIONAL,
             flags [5] BIT STRING OPTIONAL
             }
        CertSequence ::= SEQUENCE OF Certificate

   status indicates success or the cause of the failure.

   index if present indicates that the request could not be fully
   satisfied in a single request because of size limitations.  The
   request should be repeated with this index supplied in the request to
   get more.

   resolveTo will be present if index is present and should be supplied
   in the request for more certificates.  certSequence contains
   certificates found matching the search criteria.

   indexInvalidator may be present and indicates the version of the
   database being read.  If a set of certificates is being read in
   multiple requests (because there were too many to return in a single
   message), the reader should check that the value for indexInvalidator
   is the same on each request.  If it is not, the server may have
   skipped or duplicated some certificates.  This field must not be
   present if the version number in the request was missing or version
   1.x.x.

   The first 24 bits of flags, if present, indicate the protocol version
   number.  Implementers of this version of the spec should supply 2.0.0
   and should accept any version number of the form 1.x.x or 2.x.x.

2.3.2.3 ReadOutgoingCertRequest

   This requests from the CDC a list of all parent and outgoing cross
   certificates for a specified object.  A CDC is capable of storing
   cross certificates either with the subject or the issuer of the cross
   certificate.  In response to this request, the CDC will return all
   parent and cross certificates stored with the issuer for the named
   principal and all of its ancestors. Its syntax is:

        ReadOutgoingCertRequest ::= [6] IMPLICIT SEQUENCE {
             flags [0] BIT STRING DEFAULT {},
             index [1] IMPLICIT INTEGER DEFAULT 0,
             principal Name
             }

   The first 24 bits of flags is a protocol version number and should
   contain 2.0.0 for clients implementing this version of the spec.
   Servers implementing this version of the spec should accept any
   version number of the form 1.x.x or 2.x.x.  The remaining bits are
   reserved for future use (they should not be supplied by clients and
   they should be ignored by servers).

   index is used for continuation (see ReadPrinCertRequest).

   principal is the name for which certificates are requested.


2.3.2.4 ReadOutgoingCertResponse

   This is the response to a ReadOutgoingCertRequest.  Its syntax is:

        ReadOutgoingCertResponse::= [7] IMPLICIT SEQUENCE {
             status [0] IMPLICIT CDCStatus DEFAULT success,
             index [1] INTEGER OPTIONAL,
             certSequence [2] IMPLICIT CertSequence,
             indexInvalidator [3] OCTET STRING (SIZE(8))
        OPTIONAL,
             flags [4] BIT STRING OPTIONAL
             }

        CertSequence ::= SEQUENCE OF Certificate

   status indicates success of the cause of failure of the operation.

   index is used for continuation; see ReadPrinCertRequest.

   certSequence is the list of parent and outgoing cross certificates.

   indexInvalidator is used for continuation; see ReadPrinCertResponse
   (the same rules apply with respect to version numbers).

   The first 24 bits of flags, if present, contain the protocol version
   number.  Clients implementing this version of the spec should supply
   the value 2.0.0.  Servers should accept any values of the form 1.x.x
   or 2.x.x.  The remaining bits are reserved for future use (they
   should not be supplied by clients and should be ignored by servers).

2.3.2.5 ReadCredentialRequest

   This request is made to retrieve an principal's encrypted
   credentials.  To prevent unaudited password guessing, this structure
   includes an encrypted value that proves that the requester knows the
   password that will decrypt the structure.  The syntax of the request
   is:

        ReadCredentialRequest ::= [2] IMPLICIT SEQUENCE {
             flags [0] BIT STRING DEFAULT {}
             principal Name,
             logindata [2] BIT STRING DEFAULT {},
             token [3] BIT STRING OPTIONAL
             }

   The first 24 bits of flags contains the version number of the
   protocol.  The value 2.0.0 should be supplied. Any value of the form
   1.x.x or 2.x.x should be accepted. Any additional bits are reserved
   for future use (should not be supplied by clients and should be
   ignored by servers).

   principal is the name of the principal for whom encrypted credentials
   are desired.

   logindata is an encrypted value.  It may only be present if the
   version number is 2.0.0 or higher.  It must be present to read
   credentials which are protected by the login agent functionality of
   the CDC.  It is constructed as a single RSA block encrypted under the
   public key of the CDC.  The public key of the CDC is learned by some
   local means.  Possibilities include a local configuration file or by
   using DASS to read and verify a chain of certificates ending with the
   CDC [the CDC serving a directory should have its public key listed
   under a name consisting of the directory name with the RDN
   "CSS=X509"; the OID for the type CSS is 1.3.24.9.1].  The contents of
   the block are as follows:

    - The low order eight bytes contain a randomly generated DES key
      with the last byte of the DES key placed in the last byte of
      the RSA block.  This DES key will be used by the CDC to
      encrypt the response.  Key parity bits are ignored.

    - The next to last eight bytes contain a long Posix time with
      the integer time encoded as a byte string using big endian
      order.

    - The next eight bytes (from the end) contain a hash of the
      password.  The algorithm for computing this hash is listed in
      section 4.4.2.  The CDC never computes this hash; it simply
      compares the value it receives with the value associated with
      the credentials.

    - The next sixteen bytes (from the end) contain zero.

    - The remainder of the RSA block (which should be the same size
      as the public modulus of the CDC) contains a random number.
      The first byte should be chosen to be non-zero but so the
      value in the block does not exceed the RSA modulus.  Servers
      should ignore these bits.  This random number need not be of
      cryptographic strength, but should not be the same value for
      all encryptions.  Repeating the DES key would be adequate.

    - The byte string thus constructed is encrypted using the RSA
      algorithm by treating the string of bytes as a "big endian"

      integer and treating the integer result as "big endian" to
      make a string of bytes.

   token will not be present in the initial implementation but a space
   is reserved in case some future implementation wants to authenticate
   and audit the node from which a user is logging in.

2.3.2.6 ReadCredentialProtectedResponse

   This is the second possible response to a ReadPrinLoginRequest.  It
   is returned when the encrypted credentials are protected from
   password guessing by the CDC acting as a login agent.  Its syntax is:

   ReadCredentialProtectedResponse::=[16] IMPLICIT SEQUENCE {
           status [0] IMPLICIT CDCStatus DEFAULT success,
           encryptedCredential [1] BIT STRING,
           flags [2] BIT STRING OPTIONAL
           }

   status indicates that the request succeeded or the cause of the
   failure.

   encryptedCredential contains the DASSPrivateKey structure (defined in
   section 4.1) encrypted under a DES key computed from the user's name
   and password as specified in section 4.4.2 and then reencrypted under
   the DES key provided in the ReadPrinLoginRequest.

   The first 24 bits of flags, if present, contains the version number
   of the protocol.  Implementers of this version of the spec should
   supply 2.0.0 and should accept any version number of the form 2.x.x.
   Other bits are reserved for future use (they should not be supplied
   and they should be ignored).

2.3.2.7 WriteCredentialRequest

   This is a request to update the encrypted credential structure.  It
   is used when a user's key or password changes.  The syntax of the
   request is:

        WriteCredentialRequest ::= [17] IMPLICIT SEQUENCE {
             flags [0] BIT STRING DEFAULT {},
             authtoken [2] BIT STRING OPTIONAL,
             principal [3] Name,
             logindata [4] BIT STRING DEFAULT {},
             furtherSensitiveStuff [5] BIT STRING
             }

   The first 24 bits of flags is a version number.  Clients implementing

   this version of the spec should supply 2.0.0.  Servers should accept
   any value of the form 2.x.x.  Additional bits are reserved for future
   use (clients should not supply them and servers should ignore them).

   token, if present, authenticates the entity making the request.  A
   request will be accepted either from a principal proving knowledge of
   the password (see logindata below) or a principal presenting a token
   in this field and satisfying the authorization policy of the CDC.
   This field need not be present if logindata includes the hash2 of the
   password (anyone knowing the old password may set a new one).

   principal is the name of the object for which encrypted credentials
   should be updated.

   logindata is encrypted as in ReadPrinLoginRequest.  It proves that
   the requester knows the old password of the principal to be updated
   (unless the token supplied is from the user's CA) and includes the
   key which encrypts furtherSensitiveStuff.

   furtherSensitiveStuff is an encrypted field constructed as follows:

    - The first eight bytes consist of the hash2 defined in section
      4.4.2 with the last byte of the hash2 value stored first.  The
      CDC stores this value and compares it with the values supplied
      in future requests of ReadCredentialRequest and
      WriteCredentialRequest.

    - The next (variable number of) bytes contains a DASSPrivateKey
      structure (defined in section 4.1).  This is the new
      credential structure that will be returned by the CDC on
      future ReadCredentialRequests.

    - The result is padded with zero bytes to a multiple of eight
      bytes.

    - The entire padded string is encrypted using the key from
      logindata or token using DES in CBC mode with zero IV.

   the new eight byte "hash2" defined in section 4.4.2 concatenated with
   the DASSPrivateKey structure encrypted under the new "hash1" all
   encrypted under the DES key included in logindata.

2.3.2.8 HereIsStatus

   This is the response message to ill-formed requests and requests that
   only return a status and no data.  It's syntax is:

        HereIsStatus ::= [1] IMPLICIT SEQUENCE {
             status [0] IMPLICIT CDCStatus DEFAULT success
             }

   status indicates success or the cause of the failure.

2.3.2.9 Status Codes

   The following are the CDCStatus codes that can be returned by
   servers.  Not all of these values are possible with all calls, and
   some of the status codes are not possible with any of the calls
   described in this document.

        CDCStatus ::= INTEGER {

             success(0),
             accessDenied(1),

             wrongCDC(2),     --this CDC does not store the
                              --requested information

             unrecognizedCA(3),
             unrecognizedPrincipal(4),

             decodeRequestError(5),--invalid BER
             illegalRequest(6),    --request not recognised

             objectDoesNotExist(7),
             illegalAttribute(8),

             notPrimaryCDC(9),--write requests not accepted
                              --at this CDC replica

             authenticationFailure(11),
             incorrectPassword(12),

             objectAlreadyExists(13),
             objectWouldBeOrphan(15),

             objectIsPermanent(16),

             objectIsTentative(17),
             parentIsTentative(18),

             certificateNotFound(19),
             attributeNotFound(20),

             ioErrorOnCertifDatabase(100),

             databaseFull(101),

             serverInternalError(102),
             serverFatalError(103),

             insufficientResources(104)
             }

3. Services Provided

   This section specifies the services provided by DASS in terms of
   abstract interfaces and a model implementation.  A particular
   implementation may support only a subset of these services and may
   provide them through interfaces which combine functions and supply
   some parameters implicitly. The specific calling interfaces are in
   some cases language and operating system specific.  An actual
   implementation may choose, for example, to structure interfaces so
   that security contexts are established and then passed implicitly in
   calls rather than explicitly including them in every call.  It might
   also bundle keys into opaque structures to be used with supplied
   encryption and decryption routines in order to enhance security and
   modularity and better comply with export regulations. Annex B
   describes a Portable API designed so that applications using a
   limited subset of the capabilities of DASS can be easily ported
   between operating systems and between DASS and Kerberos based
   environments.  The model implementation describes data structures
   which include cached values to enhance performance.  Implementations
   may choose different contents or different caching strategies so long
   as the same sequence of calls would produce the same output for some
   caching policy.

   DASS operates on four kinds of data structures: Certificates,
   Credentials, Tokens, and Certification Authority State.  Certificates
   and Tokens are passed between implementations and thus their exact
   format must be architecturally specified. This detailed bit-for-bit
   specification is in section 4. Credentials generally exist only
   within a single node and their format is therefore not specified
   here. The contents of all of these data structures is listed below
   followed by the algorithms for manipulating them.

   There are three kinds of services provided by DASS: Certificate
   Maintenance, Credential Maintenance, and Authentication. The first
   two kinds exist only in support of the third. Certificate maintenance
   functions maintain the database of public keys in the naming service.
   These functions tend to be fairly specialized and may not be
   supported on all platforms. Before authentication can take place,
   both authenticating principals must have constructed credentials
   structures. These are built using the Credential Maintenance calls.

   The Authentication functions use credential information and
   certificates, produce and consume authentication tokens and tell the
   two communicating parties one another's names.

3.1 Certificate Contents

   For purposes of this architecture, a certificate is a data structure
   posted in the naming service which proclaims that knowledge of the
   private key associated with a stated public key authenticates a named
   principal. Certificates are "signed" by some authority, are readable
   by anyone, and can be verified by anyone knowing the public key of
   the authority.  DASS organizes the CA trust hierarchy around the
   naming hierarchy. There exists a trusted authority associated with
   each directory in the naming hierarchy. Generally, each authority
   creates certificates stating the public keys of each of its children
   (in the naming hierarchy) and the public key of its parent (in the
   naming hierarchy). In this way, anyone knowing the public key of any
   authority can learn the public key of any other by "walking the
   tree". In order that principals may authenticate even when all of
   their ancestor directories do not participate in DASS, authorities
   may also create "cross-certificates" which certify the public key of
   a named entity which is not a descendent.  Rules for finding and
   following these cross-certificates are described in the Get_Pub_Keys
   routines.  Every principal is expected to know the public key of the
   CA of the directory in which it is named. This must be securely
   learned when the principal is initialized and may be maintained in
   some form of local storage or by having the principal sign a
   certificate listing the name and public key of its parent and posting
   that certificate in the naming service.

   The syntax and content of DASS certificates are defined in terms of
   X.509 (Directory - Authentication Framework).  While that standard
   prescribes a single syntax for certificates, DASS considers
   certificates to be of one of six types:

    - Normal Principal certificates are signed by a CA and certify
      the name and public key of a principal where the name of the
      CA is a prefix of the name of the principal and is one
      component shorter.

    - Trusted Authority certificates are signed by an ordinary
      principal and certify the name and public key of the
      principal's CA (i.e., the CA whose name is a prefix of the
      principal's name and is one component shorter).

    - Child certificates are signed by a CA and certify the name and
      public key of a CA of a descendent directory (i.e., where the
      name of the issuing CA is a prefix of the name of the subject

      CA and is one component shorter).

    - Parent certificates are signed by a CA and certify the name
      and public key of the CA of its parent directory (i.e., whose
      name is a prefix of the name of the issuer and is one
      component shorter).

    - Cross certificates are signed by a CA and certify the name and
      public key of a CA of a directory where neither name is a
      prefix of the other.

    - Self certificates are signed by a principal or a CA and the
      issuer and subject name are the same.  They are not used in
      this version of the architecture but are defined as a
      convenient data structure in which in which implementations
      may insecurely pass public keys and they may be used in the
      future in certain key roll-over procedures.

   It is intended that some future version of the architecture relax the
   restrictions above where prefixes must be one component shorter.
   Being able to handle certificates where prefixes are two or more
   components shorter complicates the logic of treewalking somewhat and
   is not immediately necessary, so such certificates are disallowed for
   now.

   The syntax of certificates is defined in section 4. For purposes of
   the algorithms which follow, the following is the portion of the
   content which is used (names in brackets refer to the field names in
   the ASN.1 encoded structure):

    - UID of the issuer (optional)

    - Full name of the issuer (the authority or principal signing)
      [issuer]

    - UID of the subject (optional)

    - Full name of the subject (the authority or principal whose key
      is being certified) [subject]

    - Public Key of the subject [subjectPublicKey]

    - Period of validity (effective date and expiration date)
      [valid]

    - Signature over the entire content of the certificate created
      using the private key of the issuer.

   When parsing a certificate, the reader compares the two name fields
   to determine what type of certificate it is. For Parent and Trusted
   Authority certificates, the names are ignored for purposes of all
   further processing. For Child and Normal Principal certificates, only
   the suffix by which the child's name is longer than the parent's is
   used for further processing. The reason for this is so that if a
   branch of the namespace is renamed, all of the certificates in the
   moved branch remain valid for purposes of DASS processing. The only
   purposes of having full names in these certificates are (1) to comply
   with X.509, (2) for possible interoperability with other
   architectures using different algorithms, and (3) to allow principals
   to securely store their own names in trusted authority certificates
   in the case where they do not have enough local storage to keep it.

3.2 Encrypted Private Key Structure

   In order that humans need only remember a password rather than a full
   set of credentials, and also to make installation of nodes and
   servers easier, there is a defined format for encrypting RSA secrets
   under a password and posting in the naming service. This structure
   need only exist when passwords are used to protect RSA secrets; for
   servers which keep their secrets in non-volatile memory or users who
   carry smart cards, they are unnecessary.

   This structure includes the RSA private/public key pair encrypted
   under a DES key. The DES key is computed as a one-way hash of the
   password.  This structure also optionally includes the UID of the
   principal.  It is needed only if a single RSA key is shared by
   multiple principals (with multiple UIDs).

   Since this structure is posted in the name service and may be used by
   multiple implementations, its format must be architecturally defined.
   The exact encoding is listed in section 4.

3.3 Authentication Tokens

   This section of the document defines the contents of the
   authentication tokens which are produced and consumed by Create_token
   and Accept_token. With DASS, the token passed from the client to the
   server is complex, with a large number of optional parts, while the
   token passed from server to client (in the case of mutual
   authentication only) is small and simple.

   The authentication token potentially contains a large number of
   parts, most of which are optional depending on the type of
   authentication. The following defines the content and purpose of each
   of the parts, but does not describe the actual encoding (in the
   belief that such details would be distracting). The encoding is in

   section 4.

   The authentication process begins when the initiator calls
   Create_token with the name of the target. This routine returns an
   authentication token, which is sent to the target. The target calls
   Accept_token passing it the token. Both routines produce a second
   "mutual authentication token". The target returns this to the
   initiator to prove that it received the token.

3.3.1 Initial Authentication Token

   The components of the initial authentication token are (names in
   brackets refer to the field names within the ASN.1 encoded structures
   defined in section 4):

    a) Encrypted Shared Key - [authenticatingKey] - This is a Shared
       (DES) key encrypted under the public key of the target. Also
       included in the encrypted structure is a validity interval and
       a recognizable pattern so that the receiver can tell whether
       the decryption was successful.

    b) Login Ticket - [sourcePrincipal.userTicket] - This is a
       "delegation certificate" signed by a principal's long term
       private key delegating to a short term public key. Its "active
       ingredients" are:

      1) UID of delegating principal [subjectUID]

      2) Period of validity [validity]

      3) Delegation public key [delegatingPublicKey]

      4) Signature by private key of principal
         The existence of this signature is testimony that the
         private key corresponding to the delegation public key
         speaks for the user during the validity interval.
         This data structure is optional and will be missing if the
         authentication is only on behalf of a Local Username on a
         node (i.e., proxy) rather than on behalf of a real principal
         with a real key.

    c) Shared Key Ticket - [sourcePrincipal.sharedKeyTicketSignature]
       - This is a signature of the Encrypted Shared Key by the
       Delegation Public key in the Login Ticket.  The existence of
       this signature is testimony that  the DES key in the encrypted
       shared key speaks for the user.

       This data structure is optional and will be missing if the

       authentication is only on behalf of a Local Username on a node
       (i.e., proxy) rather than on behalf of a real principal with a
       real key. It will also be missing if delegation is taking
       place.

    d) Node Ticket - [sourceNode.nodeTicketSignature] - This is a
       signature of the Encrypted Shared key and a "Local Username"
       on the host node by the node's private key.  The existence of
       this signature is testimony by the node that the DES key in
       the encrypted shared key speaks for the named account on that
       node.

    e) Delegator - [sourcePrincipal.delegator] - This data structure
       contains the private login key encrypted under the Shared key.
       It is optional and is present only if the initiator is
       delegating to the destination.

    f) Authenticator - [authenticatorData] - This data structure
       contains a timestamp and a message digest of the channel
       bindings signed by the Shared Key. It is always present.

    g) Principal name - [sourcePrincipal.userName] - This is the name
       of the initiating principal. It is optional and will be
       missing for strong proxy where bits on the wire are at a
       premium and where the destination is capable of independently
       constructing the name.

    h) Node name - [sourceNode.nodeName] - This is the name of the
       initiating node. It is optional and will be missing for strong
       proxy where bits on the wire are at a premium and the name is
       present elsewhere in the message being passed.

    i) Local Username - [sourceNode.username] - This is the local
       user name on the initiating node. It is optional and will be
       missing for strong proxy where bits on the wire are at a
       premium and where the name is present elsewhere in the message
       being passed.

3.3.2 Mutual Authentication Token

   The authentication buffer sent from the target to the initiator (in
   the case of mutual authentication) is much simpler. It contains only
   the timestamp taken from the authenticator encrypted under the Shared
   Key.  It is ASN.1 encoded to allow for future extensions.

3.4 Credentials

   DASS organizes its internal state with Credentials structures.  There
   are many kinds of information which can be stored in credentials.
   Rather than making a different kind of data structure for each kind
   of data, DASS provides a single credentials structure where most of
   its fields are optional.  Operating systems must provide some
   mechanism for having several processes share credentials. An example
   of a mechanism for doing this would be for credentials to be stored
   in a file and the name of the file is used as a "handle" by all
   processes which use those credentials. Some of the calls which follow
   cause credentials structures to be updated. It is important to the
   performance of a system that updates to credentials (such as occur
   during the routines Verify_Principal_Name and Verify_Node_Name, where
   the caches are updated) be visible to all processes sharing those
   credentials.

   In many of the calls which follow, the credentials passed may be
   labeled: claimant credentials, verifier credentials or some such.
   This indicates whose credentials are being passed rather than a type
   of credentials. DASS supports only one type of credentials, though
   the fields present in the credentials of one sort of principal may be
   quite different from those present in the credentials of another.

   An implementation may choose to support multiple kinds of credentials
   structures each of which will support only a subset of the functions
   available if it is not implementing the full architecture.  This
   would be the case, for example, if an implementation did not support
   the case where a server both received requests from other principals
   and made requests on its own behalf using a single set of
   credentials.

   The following are a list of the fields that may be contained in a
   credentials structure. They are grouped according to common usage.

3.4.1 Claimant information

   This is the information used when the holder of these credentials is
   requesting something. It includes:

    a) Full X.500 name of the principal

    b) Public Key of the principal

    c) Login Ticket - a login ticket contains:

      1) the UID of the principal

      2) a period of validity (effective date & expiration date)

      3) a delegation public key

      4) a signature of the ticket contents by the principal's long
         term key

    d) Delegation Private Key (corresponding to the public key in c3)

    e) Encrypted Shared Key (present only when credentials were
       created by accept_token; this information is needed to verify
       a node ticket after credentials are accepted)

3.4.2 Verifier information

   This is the information needed by a server to decrypt incoming
   requests. It is also used by generate_server_ticket to generate a
   login ticket.

    a) RSA private key.

3.4.3 Trusted Authority

   This is information used to seed the walk of the CA hierarchy to
   reliably find the public key(s) associated with a name.
   Normally, the trusted authority in a set of credentials will be
   the directory parent of the principal named in Claimant
   information.  In some circumstances, it may instead be the
   directory parent of the node on which the credentials reside.

    a) Full X.500 name of a CA

    b) Corresponding RSA Public Key

    c) Corresponding UID

3.4.4 Remote node authentication

   This information is present only for credentials generated by
   "Accept_token". It includes information about any remote node which
   vouched for the request.

    a) Full X.500 name of the node

    b) Local Username on the node

    c) Node ticket.

3.4.5 Local node credentials

   This information is added by Combine_credentials, and is used by
   Create_token to add a node signature to outbound requests.

    a) Full X.500 name of the node

    b) Local Username on the node

    c) RSA private key of the node

3.4.6 Cached outgoing contexts

   There may be one (or more) such structures for each server for which
   this principal has created authentication tokens. These represent a
   cache: they may be discarded at any time with no effect except on
   performance. For each association, the following information is kept:

    a) Destination RSA Public Key (index)

    b) Encrypted Shared key

    c) Shared Key Ticket (optional, included if there has been a
       non-delegating connection)

    d) Node Ticket

    e) Delegator (optional, included if there has been a delegating
       connection)

    f) Validity interval

    g) Shared Key

3.4.7 Cached Incoming Contexts

   There may be one such structure for each client from which this server
   has received an authentication token.  These represent a cache: they
   may be discarded at any time with no effect except on performance. (An
   implementation may choose to keep one System-wide Cache (and list of
   incoming timestamps). While it is unlikely that the same Encrypted
   Shared Key will result from encryption of Shared keys generated by
   different clients or for different servers, an implementation must
   ensure that an entry made for one client/server can not be reused by
   another client/server.  Similarly an implementation may choose to keep
   separate caches for the Shared Key/Validity Interval/Delegation Public
   Key, the Nodename/UID/key/username and the Principal name/UID/key.)
   For each association, the following information is kept:

    a) Encrypted Shared key (index)

    b) Shared Key

    c) Validity Interval

    d) Full X.500 name of Client Principal

    e) UID of Client Principal

    f) Public Key of Client Principal

    g) Name of Client Node

    h) UID of Client Node

    i) Public Key of Client Node

    j) Local Username on Client node

    k) Delegation Public key of Client Principal's Login Ticket

   The Name, UID and Public key of the Principal are all entered
   together once the Login Ticket has been verified. Similarly the Node
   name, Node key and Username are entered together once the Node Ticket
   has been verified. These pieces of information are only present if
   they have been verified.

3.4.8 Received Authenticators

   A record of all the authenticators received is kept. This is used to
   detect replayed messages. (This list must be common to all targets
   that could accept the same authenticator (channel bindings will
   prevent other targets from accepting the same authenticator). This
   includes different `servers' sharing the same key.)  The entries in
   this list may be deleted when the timestamp is old enough that they
   would no longer be accepted. This list is kept separate from the
   Cached incoming context in order that the information in the cached
   incoming context can be discarded at any time. An implementation
   could choose to save these timestamps with the cached incoming
   context if it ensures that it can never purge entries from the cache
   before the timestamp has aged sufficiently. This list is accessed
   based on an extract from the signature from the Authenticator. The
   extract must be at least 64 bits, to ensure that it is very unlikely
   that 2 authenticators will be received with matching signatures.

    a) Extract from Signature from Authenticator

    b) Timestamp

   If an implementation runs out of space to store additional
   authenticators, it may either reject the token which would have
   overflowed the table or it may temporarily narrow the allowed clock
   skew to allow it to free some of the space used to hold "old"
   authenticators.  The first strategy will always falsely reject
   tokens; the second may cause false rejection of tokens if the allowed
   clock skew gets narrowed beyond the actual clock skew in the network.

3.5 CA State

   The CA needs to maintain some internal state in order to generate
   certificates. This internal state must be protected at all times, and
   great care must be taken to prevent its being disclosed. A CA may
   choose to maintain additional state information in order to enhance
   security.  In particular, it is the responsibility of the CA to
   assure that the same UID is not serially reused by two holders of a
   single name.  In most cases, this can be done by creating the UID at
   the time the user is registered.  To securely permit users to keep
   their UIDs when transferring from another CA, the CA must keep a
   record of any UIDs used by previous holders of the name. Since
   actions of a CA are so security sensitive, the CA should also
   maintain an audit trail of all certificates signed so that a history
   can be reconstructed in the event of a compromise.  Finally, for the
   convenience of the CA operator, the CA should record a list of the
   directories for which it is responsible and their UIDs so that these
   need not be entered whenever the CA is to be used.  The state
   includes at least the following information:

    - Public Key of CA

    - Private Key of CA

    - Serial number of next certificate to be issued

3.6 Data types used in the routines

   There are several abstract data types used as parameters to the
   routines described in this section. These are listed here

    a) Integer

    b) Name
       Names unless otherwise noted are always X.500 names.  While
       most of the design of DASS is naming service independent, the
       syntax of certificates and tokens only permits X.500 names to
       be used.  If DASS is to be used in an environment where some

       other form of name is used, those names must be translated
       into something syntactically compliant with X.500 using some
       mechanism which is beyond the scope of this architecture.  The
       only other form of name appearing in this architecture is a
       "local user name", which corresponds to the simple name of an
       "account" on a node.  As a type, such names appear in
       parameter lists as "Strings".

    c) String
       A String is a sequence of printable characters.

    d) Absolute Time
       A UTC time. The precision of these Times is not stated. A
       precision of the order of one second in all times is
       sufficient.

    e) Time Interval
       A Time interval is composed of 2 times. A Start Time and an
       End Time, both of which are Absolute Times

    f) Timestamp
       A Timestamp is a time in POSIX format. I.e., two 32 bit
       Integers. The first representing seconds, and the second
       representing nanoseconds.

    g) Duration
       A Duration is the length of a time interval.

    h) Octet String
       A sequence of bytes containing binary data

    i) Boolean
       A value of either True or False

    j) UID
       A UID is an bit string of 128 bits.

    k) OID
       An OID is an ISO Object Identifier.

    l) Shared key
       A Shared key is a DES key, a sequence of 8 bytes

    m) CA State
       A structure of the form described in '3.5

    n) Credentials
       A structure of the form described in '3.4

    o) Certificate
       An ASN.1 encoding of the structure described in '3.1

    p) Authentication Token
       An ASN.1 encoding of the structure described in '3.3.1

    q) Mutual Authentication Token
       An ASN.1 encoding of the structure described in '3.3.2

    r) Encrypted Credentials
       An ASN.1 encoding of  the  structure described in '3.2

    s) Public key
       A representation of an RSA Public key, including all the
       information needed to encode the public key in a certificate.

    t) Set of Public key/UID pairs
       A set of Public key/UID pairs. This Data type is only used
       internally in DASS - it does not appear in any interface used
       to other architectures.

3.7 Error conditions

   These routines can return the following error conditions (an
   implementation may indicate errors with more or less precision):

    a) Incomplete chain of trustworthy CAs

    b) Target has no keys which can be trusted.

    c) Invalid Authentication Token

    d) Login Ticket Expired

    e) Invalid Password

    f) Invalid Credentials

    g) Invalid Authenticator

    h) Duplicate Authenticator

3.8 Certificate Maintenance Functions

   Authentication services depend on a set of data structures maintained
   in the naming service. There are two kinds of information:
   Certificates, which associate names and public keys and are signed by
   off-line Certification Authorities; and Encrypted Credentials, which

   contain RSA Private Keys and certain context information encrypted
   under passwords. Encrypted Credentials are only necessary in
   environments where passwords are used. Credentials may alternatively
   be stored in some other secure manner (for example on a smart card).

   The certificate maintenance services are designed so that the most
   sensitive - the actual signing of certificates - may be done by an
   off-line authority.  Once signed, certificates must be posted in the
   naming service to be believed.  The precise mechanisms for moving
   certificates between off-line CAs and the on-line naming service are
   implementation dependent.  For the off-line mechanisms to provide any
   actual security, the CAs must be told what to sign in some reliable
   manner.  The mechanisms for doing this are implementation dependent.
   The abstract interface says that the CA is given all of the
   information that goes into a certificate and it produces the signed
   certificate.  There are requirements surrounding the auditing of a
   CA's actions. The details of what actions are audited, where the
   audit trail is maintained, and what utilities exist to search that
   audit trail are not specified here. The functions a CA must provide
   are:

3.8.1 Install CA

   Install_CA(
                       keysize               Integer,   --inputs
                       CA_state              CA State,  --outputs
                       CA_Public_Key         Public Key)

   This routine need only generate a public/private key pair of the
   requested size. Keysize is likely to be in implementation constant
   rather than a parameter.  The value is likely to be either 512 or
   640.  Key sizes throughout will have to increase over time as
   factoring technology and CPU speeds improve.  Both keys are stored as
   part of the CA_state; the public key is returned so that other CAs
   may cross-certify this one. The `Next Serial number' in the CA state
   is set to 1.

3.8.2 Create Certificate

   Create_certificate(
                                                    --inputs
                       Renewal               Boolean,
                       Include_UID           Boolean,
                       Issuer_name           Name,
                       Issuer_UID            UID,
                       Effective_date        Absolute Time,
                       Expiration_date       Absolute Time,
                       Subject_name          Name,

                       Subject_UID           UID,
                       Subject_public_key    Public Key,
                                                    --updated
                       CA_state              CA State,
                                                    --outputs
                       Certificate           Certificate)

   This procedure creates and signs a certificate.  Note that the
   various contents of the certificate must be communicated to the CA in
   some reliable fashion.  The Issuer_name and UID are the name and UID
   of the directory on whose behalf the certificate is being signed.

   This routine formats and signs a certificate with the private key in
   CA_state. It audits the creation of the certificate and updates the
   sequence number which is part of CA_state. The Issuer and Subject
   names are X.500 names.  If the CA state includes a history of what
   UIDs have previously been used by what names, this call will only
   succeed in the collision case if the Renewal boolean is set true.  If
   the Include_UID boolean is set true, this routine will generate a
   1992 format X.509 certificate; otherwise it will generate a 1988
   format X.509 certificate.

3.8.3 Create Principal

   Create_principal(
                                                    --inputs
                       Password              String,
                       keysize               Integer,
                       Principal_name        Name,
                       Principal_UID         UID,
                       Parent_Public_key     Public Key,
                       Parent_UID            UID,
                                                    --outputs
                       Encrypted_Credentials Encrypted Credentials,
                       Trusted_authority_certificate Certificate)

   This procedure creates a new principal by generating a new
   public/private key pair, encrypting the public and private keys under
   the password, and signing a trusted authority certificate for the
   parent CA.  In an implementation not using passwords (e.g., smart
   cards), an alternative mechanism must be used for initially creating
   principals.  If a principal has protected storage for trusted
   authority information, it is not necessary to create a trusted
   authority certificate and store it in the naming service.  Some
   procedure analogous to this one must be executed, however, in which
   the principal learns the public key and UID of its CA and its own
   name.

   This routine creates two output structures with the following steps:

    a) Generate a public/private key pair using the indicated
       keysize. An implementation will likely fix the keysize as an
       implementation constant, most likely 512 or 640 bits, rather
       than accepting it as a parameter.  Key sizes generally will
       have to increase over time as factoring technology and CPU
       speeds improve.

    b) Form the encrypted credentials by using the public key,
       private key, and Principal_UID and encrypting them using a
       hash of the password as the key.

    c) Generate a trusted authority certificate (which is identical
       in format to a "parent" certificate) getting fields as
       follows:

      1) Certificate version is X.509 1992.

      2) Issuer name is the Principal name (which is an X.500 name).

      3) Issuer UID is the Principal UID.

      4) Validity is for all time.

      5) Subject name is constructed from the Principal name by
         removing the last simple name from the hierarchical name.

      6) Subject UID is the CA_UID.

      7) Subject Public Key is the CA_Public_Key

      8) Sequence number is 1.

      9) Sign the certificate with the newly generated private key of
         the principal.

3.8.4 Change Password

   Change_password(                                 --inputs
                       Encrypted_credentials Encrypted Credentials,
                       Old_password          String,
                       New_password          String,
                                                    --outputs
                       Encrypted_credentials Encrypted Credentials)

   If credentials are stored encrypted under a password, it is possible
   to change the password if the old one is known.  Note that it is

   insufficient to just change a user's password if the password has
   been disclosed.  Anyone knowing the old password may have already
   learned the user's private key.  If a password has been disclosed,
   the secure recovery procedure is to call create_principal again
   followed by create_certificate to certify the new key.

   Using DASS, it may not be appropriate for users to periodically
   change their passwords as a precaution unless they also change their
   private keys by the procedure above.  The only likely use of the
   change_password procedure is to handle the case where an
   administrator has chosen a password for the user in the course of
   setting up the account and the user wishes to change it to something
   the user can remember.  A future version of the architecture may
   smooth key roll-over by having the change_password command also
   generate a new key and sign a "self" certificate in which the old key
   certifies the new one.  As a separate step, a CA which notices a self
   certificate posted in the naming service could certify the new key
   instead of the old one when the user's certificate is renewed.  While
   this procedure is not as rapid or as reliable as having the user
   directly interact with the CA, it offers a reasonable tradeoff
   between security and convenience when there is no evidence of
   password compromise.

   This routine simply decrypts the encrypted credentials structure
   supplied using the password supplied. It returns a bad status if the
   format of the decrypted information is bad (indicating an incorrect
   password). Otherwise, it creates a new encrypted credentials
   structure by encrypting the same data with the new password. It would
   be highly desirable for the user interface to this function to
   provide the capability to randomly generate passwords and prohibit
   easily guessed user chosen passwords using length, character set, and
   dictionary lookup rules, but such capabilities are beyond the scope
   of this document.  If encrypted credentials are stored in some local
   secure storage, the above function is all that is necessary (in fact,
   if the storage is sufficiently secure, no password is needed;
   credentials could be stored unenciphered).  If they are stored in a
   naming service, this function must be coupled with one which
   retrieves the old encrypted credentials from the naming service and
   stores the new.  The full protocol is likely to include access
   control checks that require the principal to acquire credentials and
   produce tokens.  For best security, the encrypted credentials should
   be accessible only through a login agent.  The role of the login
   agent is to audit and limit the rate of password guessing.  If
   passwords are well chosen, there is no significant threat from
   password guessing because searching the space is computationally
   infeasible.  In the context of a login agent, change password will be
   implemented with a specialized protocol requiring knowledge of the
   password and (for best security) a trusted authority from which the

   public key of the login agent can be learned.  See section 2.3.2 for
   the plans for the non-X.500 credential storage facility.

3.8.5 Change Name

   Change_name(
                                                    --inputs
                       Claimant_Credentials  Credentials,
                       New_name              Name,
                       CA_Public_Key         Public Key,
                       CA_UID                UID,
                                                    --outputs
                       Trusted_Authority_Certificate Certificate)

   DASS permits a principal to have many current aliases, but only one
   current name.  A principal can authenticate itself as any of its
   aliases but verifies the names of others relative to the name by
   which it knows itself.  Aliases can be created simply by using the
   create_certificate function once for each alias.  To change the name
   of a principal, however, requires that the principal securely learn
   the public key and UID of its new parent CA.  As with
   create_principal, if a principal has secure private storage for its
   trusted authority information, it need not create a certificate, but
   some analogous procedure must be able to install new naming
   information.

   This routine produces a new Trusted Authority Certificate with
   contents as follows:

    a) Issuer name is New_name (an X.500 name)

    b) Issuer_UID is Principal UID from Credentials.

    c) Validity is for all time.

    d) Subject name is constructed from the Issuer name by removing
       the last simple name from the hierarchical name, and
       converting to an X.500 name.

    e) Subject UID is CA_UID

    f) Subject Public Key is CA_Public_Key

    g) Sequence number is 1.

    h) The certificate is signed with the private key of the
       principal from the credentials. Note that this call will only
       succeed if the principal's private key is in the credentials,

       which will only be true if the credentials were created by
       calling Create_server_credentials.