Trust Management Working Group                                Matt Blaze
Internet Draft                                           Joan Feigenbaum
expires in six months                               Angelos D. Keromytis
                                                          John Ioannidis
                                                             August 1998

                 The KeyNote Trust-Management System
                draft-blaze-trustmgt-keynote-00.txt (A)


Status of this Memo

   This document is an Internet-Draft.  Internet Drafts are working doc-
   uments of the Internet Engineering Task Force (IETF), its Areas, and
   its Working Groups.  Note that other groups may also distribute work-
   ing 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 refer-
   ence material, or to cite them other than as a ``working draft'' or
   ``work in progress.''

   To view the entire list of current Internet-Drafts, please check
   the "1id-abstracts.txt" listing contained in the Internet-Drafts
   Shadow Directories on ftp.is.co.za (Africa), ftp.nordu.net
   (Northern Europe), ftp.nis.garr.it (Southern Europe), munnari.oz.au
   (Pacific Rim), ftp.ietf.org (US East Coast), or ftp.isi.edu
   (US West Coast).

   Distribution of this memo is unlimited.


Abstract

   This memo describes KeyNote, a simple trust-management system.  It
   outlines the syntax and semantics of KeyNote credentials, describes
   action environment processing, and describes the application
   architecture into which a KeyNote implementation would fit.


Terminology

   The key words "MUST," "MUST NOT," "REQUIRED," "SHALL," "SHALL NOT,"
   "SHOULD," "SHOULD NOT," "RECOMMENDED,"  "MAY," and "OPTIONAL" in this
   document are to be interpreted as described in [Bra97].


1.  Introduction

   This memo describes KeyNote, a simple trust-management system.
   Trust management, introduced in the PolicyMaker system [BFL96], is
   a unified approach to specifying and interpreting security
   policies, credentials, and relationships that allows direct


KeyNote                 expires in six months                   [Page i]


DRAFT                         KeyNote                        August 1998


   authorization of security-critical actions.  In particular, a
   trust-management system combines the notion of specifying security
   policy with the mechanism for specifying security credentials
   (subsuming the role of "certificates").  Credentials describe a
   specific delegation of trust among public keys; unlike traditional
   certificates, which bind keys to names, trust-management credentials
   bind keys to the authorization to perform specific tasks.

   KeyNote provides a simple notation for specifying both local security
   policies and security credentials that can be sent over an untrusted
   network.  Policies and credentials, called "assertions", contain
   predicates that describe the trusted actions permitted by the holders
   of specific public keys.  A signed assertion that can be sent over an
   untrusted network is also called a Credential Assertion.  Credential
   assertions, which serve the role of "certificates," have the same
   syntax as policy assertions but are also signed by the entity
   delegating the trust.

   In this document we assume that applications communicate with a
   "KeyNote evaluator" that interprets KeyNote assertions and returns
   results to applications.  However, different hosts and environments
   may provide a variety of interfaces to the KeyNote evaluator and
   this document does not aim to specify a KeyNote API.

   A KeyNote evaluator accepts as input a set of local policy and
   credential assertions, and a set of attributes, called an "action
   environment," that describes a proposed trusted action associated
   with a set of public keys.  The KeyNote evaluator determines whether
   proposed actions are consistent with local policy by applying the
   assertion predicates to the action environment.  The KeyNote
   evaluator can return values other than simply true and false,
   depending on the application and the action-environment definition.
   Furthermore, KeyNote assertions can return additional information
   (such as arguments) to the invoking application.


2.  KeyNote Syntax

   The version of KeyNote assertions described in this document is 1.
   All KeyNote assertions are encoded in ASCII strings.  Four mandatory
   fields MUST appear in all assertions (KeyNote-Version, Authorizer,
   Licensees, and Conditions); these fields describe who authorizes
   whom under what conditions.  Four optional fields MAY appear (Export,
   Comment, Signature, and Local-Init).

   All fields MUST start at the beginning of a line; fields may be
   continued by indenting with at least one SPACE or TAB character at
   the beginning of the line.  Whitespace separates tokens but is
   otherwise ignored outside of quoted strings.  (Our grammars below
   omit whitespace processing in the interest of readability.)  All
   name tokens are case-insensitive.



KeyNote                 expires in six months                   [Page 1]


DRAFT                         KeyNote                        August 1998


   In the following sections, the notation [X]* means zero or more
   repetitions of the string X.  The notation [X]+ means one or more
   repetitions of the string X.

   A complete sample assertion is shown below.  The meaning of the
   various fields is explained in the following sections.

     KeyNote-Version: 1
     Authorizer: rsa-pkcs1-hex:deaf
     Licensees: dsa-hex:feeddead || rsa-pkcs1-hex:cafe
     Export: Attr1, Attr2
     Local-Init: localattribute = "xxx"
     Comment: Your average credential assertion
     Conditions: $foo == "bar" -> {write1 = "yes", return true}
     Signature: rsa-md5-pkcs1-hex:f00f

2.1  Key Encoding

   Keys in KeyNote credential assertions are encoded as

      AlgorithmName:Encoding

   AlgorithmName is a case-insensitive ASCII string that describes
   the key type (e.g., RSA [RSA78] or DSA [DSA94]), encoding (e.g.,
   PKCS1 [PKCS1]), and string encoding (e.g., HEX or BASE64).
   AlgorithmName is given by [a-zA-Z][a-zA-Z0-9_-]*
   The IANA will provide a registry of reserved AlgorithmName names.

   Encoding is ([a-zA-Z0-9][a-zA-Z0-9_]*)|(\"(([^\"\n])|(\\[.\n]))*\")
   and its format depends on AlgorithmName.  Hex-encoded keys SHOULD
   use lower-case digits.  Encoding can can occupy more than one line
   by using the "+" string concatenation operator.

   Note that the keys used in examples in this document are fictitious
   and generally shorter than would be required for security.

2.2  Attributes

   Attributes in KeyNote are denoted by $AttrName in any of the
   Authorizer, Licensees, and Conditions fields.  Whenever an attribute
   is encountered, a lookup MUST be made in the Local-Init
   definitions.  If that fails, for the Authorizer and Licensees fields
   this results in the empty string.  In the Conditions, a subsequent
   lookup in the action environment must be made.  (For more details on
   the action environment, see section 4.)  If that fails to match as
   well, the result is the empty string.  In case of a match, the
   corresponding value is the result, in string form.

   In the Conditions, attributes can also be denoted by @AttrName and
   &AttrName.  These cause the resulting value to be an integer or a
   floating point number respectively.  If $AttrName contains
   characters other than whitespace, decimal digits and a


KeyNote                 expires in six months                   [Page 2]


DRAFT                         KeyNote                        August 1998


   single '.' character, the resulting value MUST be zero.  @AttrName
   is equivalent to floor(&AttrName).

2.3  Key Comparisons

   Key comparisons inside KeyNote (performed while trying to match
   keys in Authorizer and Licensees or the action authorizers (see
   section 5) should be between canonical forms of the keys.  Every
   algorithm used in KeyNote should define some method for converting
   keys to this canonical form, and how the comparison for equality of
   two keys is performed.  If the algorithm is unknown or unsupported,
   the implementation SHOULD do a case-sensitive string comparison,
   for comparisons between keys in a Licensees and the action
   authorizers (since a key that the application knows about but the
   KeyNote implementation does not, may appear in the action
   authorizers).  Comparisons involving a key in the Authorizer field
   MUST be between canonical forms, unless the assertion is localy
   trusted (case-sensitive string comparison is used in that case).

2.4  Return Values

   Some applications may use KeyNote in a form in which an assertion
   evaluates to one of two values (true/false).  However, KeyNote
   supports more than two values (the number of supported values, as
   well as the values themselves, SHOULD be a runtime option set by the
   invoking application).  The set of all possible return values should
   be a totally ordered one.  The return values are the possible values
   both Licensees and Conditions can take after they have been
   evaluated.

   The KeyNote system will attempt to return the highest possible value
   from a query using the evaluation rules described in the following
   sections (in particular, section 6).  The meaning and interpretation
   of these values is application-dependent, and should be defined along
   with the rest of action-environment details (see section 4).

2.5  Write-Back Environment

   In addition to returning a non-boolean value to the invoking
   application, KeyNote assertions can also pass back some additional
   information through a write-back environment mechanism.  Assertions
   can not lookup information in this write-back environment.  The
   rules of how a write-back attribute is propagated back to the
   invoking application are given in section 3.4.  Section 3.8 contains
   some additional information on scoping.

   In some cases, two write-back sets of attributes will be "combined"
   (section 3.4) using a non-reflective operation: an ordering of the
   two write-back sets is defined, and the resulting write-back set is
   the union of the two sets.  Write-back attributes common to both
   sets will have their values inherited from the second write-back
   set. In that sense, the second write-back set writes over the first.


KeyNote                 expires in six months                   [Page 3]


DRAFT                         KeyNote                        August 1998


3.  KeyNote Field Meanings

  The following sections explain the contents and meaning of the
  various fields that can appear in a KeyNote assertion.

3.1  The KeyNote-Version field

   The KeyNote-Version field is of the form

       KeyNote-Version: VersionNumber

   where VersionNumber is an ASCII-encoded decimal number.  The
   current version is 1.  This field MUST be the first field appearing
   in a KeyNote assertion.

3.2  The Local-Init field

   This field initializes action-environment attributes that are
   specific to this assertion only.  A typical use for this field is
   to assign keys to logical names, so that the Licensees
   field is more readable.  This field is of the form

       Local-Init: Name = ConstantString [, Name = ConstantString]*

   Name is an identifier that can be used as an attribute (see section
   2.2) in the Conditions, Authorizer, and Licensees fields instead
   of the string ConstantString.  If the Local-Init field defines more
   than one identifier, it can occupy more than one line and be
   indented.  ConstantString is given by STRING in section 3.8, and
   can also be composed by concatenating smaller strings using the
   "+" operator (see the examples) and can thus occupy more than one
   line. If an initialization identifier is accessed but has not been
   defined, it should evaluate to the empty string (or zero, if it was
   accessed as a numeric value).

   When an initialization identifier is accessed in an Conditions
   expression, it shadows the value of any existing action-environment
   identifier, for this assertion only (see section 2.2).  If an
   identifier appears more than once in the Local-Init field, the
   assertion MUST be considered invalid and omitted from processing by
   the evaluator.

3.3  The Authorizer field

   The Authorizer field is of the form

       Authorizer: KEY

   where KEY is a key encoded as described in section 2.1.  The
   Authorizer field can also be a logical tag, of the form

       Authorizer: SomeString


KeyNote                 expires in six months                   [Page 4]


DRAFT                         KeyNote                        August 1998


   for assertions that are trusted directly by the local environment
   and thus do not require cryptographic verification.  SomeString is
   given by STRING in section 3.8, or can be a concatenation of smaller
   strings, using the '+' operator.  Tag comparisons are
   case-sensitive.  Finally, the Authorizer field can be of the form

       Authorizer: $Attribute

   where Attribute is a Local-Init identifier (see section 2.2).  If
   the Attribute does not exist in the Local-Init identifiers, the
   assertion MUST be omitted from processing.  The result is treated
   as a key (see section 2.1) for comparison purposes.

   A valid input to the KeyNote evaluator MUST contain at least one
   Policy assertion (in which the authorizer field is the keyword
   "POLICY", case-insensitive), which will serve as the "root" of a
   trust structure that authorizes a requested action.

3.4  The Licensees field

   The Licensees field describes who is being authorized by the
   Authorizer.  This field is of the form

       Licensees: Key-Expr

   Key-Expr is given by the following grammar:

   Key-Expr: (Key-Expr)           |
             Key-Expr && Key-Expr |
             Key-Expr || Key-Expr |
             K-of(KeyList)        |      /* Threshold */
             STRING               |
             KEY                  |
             $STRING

   KeyList:  KEY                |
             ATTRIBUTE          |
             STRING             |
             KEY, KeyList       |
             ATTRIBUTE, KeyList |
             STRING, KeyList

   STRING: (([a-zA-Z][a-zA-Z0-9_-]*) | (\" (([^\"\n])|(\\[.\n]))* \"))
   ATTRIBUTE: "$"[a-zA-Z0-9][a-zA-Z0-9_]*

   The "&&" operator has higher precedence than the "||" operator.
   "K" is an ASCII-encoded decimal number.  A KeyList SHOULD contain
   at least K keys.

   Only identifiers that appear in the Local-Init can be used as
   attributes in Licensees (see section 2.2).  An attribute is
   resolved to a string, which is then treated as a key or logical


KeyNote                 expires in six months                   [Page 5]


DRAFT                         KeyNote                        August 1998


   tag.  STRING can also be a quoted string, and/or a concatenation
   of smaller strings using the '+' operator.

   The keys, attributes, or logical tags that appear in the Licensees
   and the various expressions are treated as variables for the
   purpose of evaluation.  The values these variables take are:

   - If a key, attribute, or logical tag appears in the action
     authorizers (see section 5), its value is the highest possible.
     The empty write-back set is associated with it.

   - Otherwise, if the key, attribute, or logical tag appears in the
     Authorizer field of one or more assertions, the value it takes
     is the higher value of those assertions, and the associated
     write-back set.  If more than one assertion shares the highest
     possible value, the write-back set of one is picked arbitrarily.
     Which one is picked is implementation-dependent and may be
     non-deterministic.

   - Otherwise, the value of the key, attribute, or logical tag is
     the lowest possible.  The empty write-back set is associated
     with it.

   If the Key-Expr field is empty, it always evaluates to the highest
   possible value (which is set by the application), and is used for
   direct authorization of an Conditions by a policy or a credential.

   The semantics of the various key expressions are:

   - An "(..)" expression has the value of the enclosed subexpression.
     It also inherits the write-back set from the enclosing
     subexpression.

   - An "&&" expression has the lower of its two subexpression
     values.  The resulting write-back set is the combination of the
     write-back sets of the two subexpressions, where the lower-value
     write-back set writes over variables that appear in the
     higher-value write-back set.  For example, let

        Licensees: Key1 && Key2

     Key1's value is "value1"
     Key2's value is "value2"
     'value1' is higher than 'value2' in the linear order of
      return values
     Key1's write-back set is "str1=val1, str2=val2"
     Key2's write-back set is "str1=val3, str4=val4"

     Then the resulting value will be "value2," and the write-back set
     will be "str1=val3, str2=val2, str4=val4."

     If both subexpressions have the same value, then the left


KeyNote                 expires in six months                   [Page 6]


DRAFT                         KeyNote                        August 1998


     subexpression's write-back set writes over the right
     subexpression's write-back set.  In the above setup, the resulting
     write-back set if the two keys had the same value would be
     "str1=val1, str2=val2, str4=val4"

  -  An "||" expression has the higher of its two subexpression
     values.  The resulting write-back set is that associated with the
     returned value.  In case of a tie, the left subexpression's
     write-back set is the resulting write-back set.

   - A "K-OF(...)" expression has the K-th highest value of those among
     the KEYs and logical tags enclosed, counting multiplicity.  That
     is, if K = 3 and the values are (0, 1, 2, 2, 3), the value of the
     threshold is 2.

     The resulting write-back set is the combination of the write-back
     sets associated with the K highest values in the list, with the
     higher write-back sets writing over lower write-back sets.  If more
     than K keys share the K highest values, the leftmost K (as they
     appear in the keylist) are used.  For example, if K = 3 and the
     values are (0, 1, 2, 2, 3), the resulting write-back set will be
     that of the right-most '2', written-over by the write-back set of
     the '2' on its left, and the result written-over by the write-back
     set of the '3'.

   Notice that in the case of two values (true/false), the above rules
   of value resolution reduce to boolean logic.

3.5  The Signature field

   The Signature field is of the form

       Signature: AlgorithmName:Encoding

   AlgorithmName is a case-insensitive ASCII string that indicates
   the signature type and encoding (e.g., RSA-MD5-PKCS1-BASE64).
   AlgorithmName is given by [a-zA-Z][a-zA-Z0-9_-]*
   The IANA will provide a registry of reserved AlgorithmName names.

   Encoding contains the signature encoded according to AlgorithmName.
   Encoding is given by STRING, in section 3.8, and can occupy more
   than one lines by using the '+' string concatenation operator.
   Hex-encoded signatures SHOULD use lower-case hex digits.  The
   AlgorithmName here is not the same, but generally is related to
   the AlgorithmName of the key that appears in the Authorizer field.

   The signature is computed over the assertion, beginning at the
   KeyNote-Version field (including the keyword), up to (and
   including) the Signature field (the colon following the keyword is
   also included), concatenated with the AlgorithmName field (trailing
   colon included).  This field MUST be last in a KeyNote assertion.



KeyNote                 expires in six months                   [Page 7]


DRAFT                         KeyNote                        August 1998


   Note that the Signatures used in examples in this document are
   fictitious and generally shorter than would be required for security.

3.6  The Comment field

   The Comment field is of the form

       Comment: .*

   The interpretation of this field is application-dependent.

3.7  The Export field

   The Export field is of the form

       Export: Keyword [, KeyWord]*

   where Keyword is given by [a-zA-Z][a-zA-Z0-9_-]*

   This field contains a list of write-back environment attributes
   that this assertion is willing to export to its descendants.
   If this field is present but empty, it is taken to mean "All
   write-back environment attributes are exported."  If it is missing,
   no write-back environment attribute is exported.  See section 2.5
   for more details on write-back environments.  See section 6 on how
   the Export field is used in conjunction with write-back
   environments.  Keyword may also be a quoted string, and/or the
   concatenation of smaller strings using the '+' operator.

3.8  The Conditions field

   The Conditions field describes what the Authorizer authorizes
   the key(s) appearing in Licensees to do.  This field is of the
   form

       Conditions: Program

   where Program is given by the following grammar:

   Program: /* Nothing */
          | Program2

   Program2: Expr -> { RecProgram2 }
           | Expr -> { RecProgram2 } Program2

   RecProgram2: Program2
              | AssignmentList

   AssignmentList: "return" STRING /* Case insensitive "return" */
                 | Str = Str , AssignmentList      /* WriteBack */
                 | Str = NumEx , AssignmentList    /* WriteBack */
                 | Str = FloatEx, AssignmentList   /* WriteBack */


KeyNote                 expires in six months                   [Page 8]


DRAFT                         KeyNote                        August 1998


   Expr: ( Expr )     |     /* Parentheses */
         Expr && Expr |     /* Logical AND */
         Expr || Expr |     /* Logical OR */
         !Expr        |     /* Logical NOT */
         NumExpr      |     /* Integer boolean expression */
         FloatExpr    |     /* Floating point boolean expression */
         StringExpr   |     /* String boolean expression */
         "true"       |     /* Case insensitive keyword */
         "false"            /* Case insensitive keyword */

   NumExpr: NumEx == NumEx |       /* Integer expression comparisons */
            NumEx != NumEx |
            NumEx < NumEx  |
            NumEx > NumEx  |
            NumEx <= NumEx |
            NumEx >= NumEx |

   FloatExpr: FloatEx < FloatEx  | /* Floating point */
              FloatEx > FloatEx  |
              FloatEx <= FloatEx |
              FloatEx >= FloatEx

   StringExpr: Str == Str |        /* String equality */
               Str != Str |        /* String inequality */
               Str < Str  |        /* Alphanumeric comparisons */
               Str > Str  |
               Str <= Str |
               Str >= Str |
               Str ~= RegExp    /* Regular expression matching */

   Str: Str + Str |   /* String concatenation */
        Str . Str |   /* Also string concatenation */
        STRING    |   /* Quoted or otherwise */
        ATTRIBUTE |   /* Lookup in Local-Init and action environment */
        $( Str )      /* Dynamic resolution */

   NumEx: NumEx + NumEx |       /* Integer operations */
          NumEx - NumEx |
          NumEx * NumEx |
          NumEx / NumEx |
          NumEx % NumEx |
          NumEx ^ NumEx |       /* Exponentiation */
          -NumEx        |
          ( NumEx )     |
          NUMBER        |
          NUMATTRIBUTE  |
          @( Str )              /* Dynamic resolution */

   FloatEx: FloatEx + FloatEx | /* Floating point operations */
            FloatEx - FloatEx |
            FloatEx * FloatEx |
            FloatEx / FloatEx |


KeyNote                 expires in six months                   [Page 9]


DRAFT                         KeyNote                        August 1998


            FloatEx ^ FloatEx | /* Exponentiation */
            -FloatEx          |
            ( FloatEx )       |
            FLOAT             |
            FLOATATTRIBUTE    |
            &( Str )            /* Dynamic resolution */

   NUMBER: [0-9]+
   FLOAT: {NUMBER} . {NUMBER}
   STRING: (([a-zA-Z][a-zA-Z0-9_-]*) | (\" (([^\"\n])|(\\[.\n]))* \"))
   VSTRING: [a-zA-Z0-9][a-zA-Z0-9_]*
   ATTRIBUTE: $VSTRING
   NUMATTRIBUTE: @VSTRING
   FLOATATTRIBUTE: &VSTRING

   The binary numeric operation precedence is (higher to lower) ^,
   (*, /, %), (+, -).  Operators of equal precedence are evaluated
   left-to-right.

   Single-backslash ("\") and quote elimination must be performed on
   quoted strings (e.g., "\ac" becomes ac).

   String operations (including regexps) in the Conditions can be
   case-sensitive or case-insensitive, specified as a run-time option.

   A division (or modulo) by zero causes the enclosing boolean
   expression to evaluate to the lowest value.

   The keywords `true', `false', and `return' have special meaning
   only in those grammar rules they are included.  They can be used as
   variable names or strings anywhere else in the Conditions.

   The "$(str)" construct causes a lookup of the string ``str'' in the
   Local-Init attributes (and if that fails to find a match, in the
   action-environment attributes).  If ``str'' evaluates to the empty
   string, the enclosing boolean expression MUST evaluate to false.
   Similarly for the "@(str)" and "&(str)" constructs.

   RegExpr refers to the POSIX 1003.2 regular expression syntax and
   semantics.  A regular expression is true if the left hand string
   expression matches RegExpr.  If group matching is used, the number
   of groups matched MUST be placed in the temporary attribute $0, and
   the subsequent matches should be placed in the temporary attributes
   $1, $2, ..., $($0).  These values should be discarded when a
   subsequent regular expression is encountered, or if the current
   expression does not evaluate to true.  If an invalid RegExpr is
   encountered, the assertion MUST be omitted from processing.

   If an Conditions field is empty, it always evaluates to the
   highest possible return value.  If no expressions match, the value
   of this assertion is the lowest value, and there is no associated
   write-back set.


KeyNote                 expires in six months                  [Page 10]


DRAFT                         KeyNote                        August 1998


   More than one expressions can exist in an Conditions.  The
   semantics then are that the first expression that evaluates to true,
   returns a value and a write environment.

   Furthermore, expressions can be nested, using the "-> { ... }"
   construct.  Consequently, an expression can be viewed as a series of
   boolean expressions that lead to a write-back environment/return
   value.  The first such expression where all the boolean expressions
   are true ``fires''.  As an example, consider the Conditions
   with the following expressions:

       expression1 -> { expression11 -> {return somevalue}
                        expression12 -> {return someothervalue}
                      }

       expression2 -> { expression21 -> {return somethirdvalue} }

       expression3 -> {return justavalue}

   If expression1 and expression11 are true, then the returned value
   will be "somevalue."  If expression1 is true, expression11 is false,
   and expression12 is true, "someothervalue" will be returned.  If
   expression1 if false, or both expression11 and expression12 are
   false, the following expressions will be evaluated.  A syntax or
   semantic error in any of these expressions MUST cause the
   assertion to be omitted from processing.

   If a write-back environment block causes an exception (either
   through a division by zero or through invalid use of one of the
   "$(str)," "@(str)," or "&str" constructs), the expressions is
   considered false.  For example, the expression set

       expression1 -> { expression11 -> {a=1/0, return something}
                        expression12 -> {a=1, return somethingelse}
                      }

   (assuming all three expressions are true) MUST return
   "somethingelse."  An exception is also raised if the same
   write-back attribute is used twice in the same block.

   The return values MUST be checked (case-insensitive) for validity.
   If a value is invalid, the assertion MUST be omitted from processing.

   For the write-back expressions (which are of the form "expression =
   expression"), the left subexpression MUST evaluate to a string.
   The result MUST be treated as the name of an attribute in the
   write-back environment.  All attribute lookups made in the process
   of constructing the left subexpression string MUST be made among
   the Local-Init and action-environment attributes.  All attribute
   lookups made in the process of constructing the right subexpression
   (which can be a string, integer, or floating point expression) are
   made among the Local-Init and action-environment attributes.


KeyNote                 expires in six months                  [Page 11]


DRAFT                         KeyNote                        August 1998


   The write-back set constructed, is associated with the return value
   for the purposes of Licensees evaluation (see section 3.4).


4.  Action Environments

   Trusted actions to be evaluated by KeyNote are described by a
   collection of attribute/value pairs called the Action Environment.
   An action environment is passed to the KeyNote system as part of
   each query and provides the values of the attributes used by
   assertion predicates.

   The action environment specifies a collection of values of named
   attributes.  The attributes may be examined as attributes by KeyNote
   trust predicates.

   The exact format for specifying an action environment is determined
   by the particular KeyNote implementation.  In general, an
   environment may be thought of as a list of assignments to
   attributes:

        ATTRIBUTE1=VALUE1
        ATTRIBUTE2=VALUE2
        ...

   If an action-environment attribute is not defined, it MUST
   evaluate to the empty string (if accessed as a string) or the
   value zero (if accessed as an integer or a float).

   An attribute that is accessed as an integer (by prepending the "@"
   character) or as a float (through the "&" character) MUST consist
   entirely of digits and at most one period.  In both cases if the
   attribute contains any illegal character, the resulting value MUST
   be zero.

   The attribute "$Action_Authorizers," MAY hold the keys that have
   signed the request.  This attribute lists the action authorizers
   keys (see section 5).

   The names of all other attributes in the action environment are not
   specified by KeyNote but must be agreed upon by the writers of any
   policies and credentials that are to cooperate in a KeyNote query
   evaluation.  By convention, the name of the application domain in
   which environment attributes should be interpreted is specified in
   the attribute App_Domain.  The IANA will provide a registry of
   reserved App_Domain names with the names and meanings of the
   attributes they use.  Note that an attribute with a particular name
   may have different meanings in different application domains.  Note
   that the use of the registry is optional; a policy or credential
   may depend on any attribute names used by the credentials to which
   trust is deferred.



KeyNote                 expires in six months                  [Page 12]


DRAFT                         KeyNote                        August 1998


   For example, an email application might reserve the App_Domain
   "RFC822-EMAIL" and might use the following attributes:

        $Address (the email address of a message's sender)
        $Name (the human name of the message sender)
        $Organization (the organization name).

   The values of these attributes may be derived in the obvious way
   from the email message headers.

   Note that RFC822-EMAIL is simply a hypothetical example; such a
   name may or may not appear in the actual registry with these or
   different attributes.  (Indeed, we recognize that the reality of
   email security is considerably more complex than this example
   suggests.)


5.  Action Authorizers

   The keys that authenticate (sign) a request (i.e., the keys that
   have signed a message whose trustworthiness KeyNote is evaluating)
   are placed in an implementation-dependent data structure.  Lookups
   are made in that data structure to match keys in the Licensees
   of an assertion and keys in the data structure, during the
   Licensees parse process (section 3.4).  Those comparisons are in
   key-canonical form (as defined by the algorithm name of the key).
   For logical tags or unsupported algorithms, case-sensitive string
   comparison is used instead (see section 3.4).


6.  KeyNote Action Evaluation

   This section describes the semantics of KeyNote action evaluation.
   An implementation is free to use any algorithm that provides
   equivalent semantics.

   Initialization:

     The attribute $App_Domain is assigned the name of the
     application (e.g., "RFC822-EMAIL").

     The keys that sign the request for a trusted action are placed
     in the implementation-dependent action authorizers data structure.

     The rest of the action-environment attributes are placed in their
     respective attributes.

     The time of day MAY be placed in the attributes $GMTTimeOfDay and
     $LocalTimeOfDay, using the format YYYYMMDDHHMMSS (e.g.,
     19980307191512).

     Any other implementation-dependent attributes and their bindings


KeyNote                 expires in six months                  [Page 13]


DRAFT                         KeyNote                        August 1998


     are also created at this step.

   For each KeyNote assertion passed to the evaluation engine, the
   following steps are taken:

     The Conditions expression is evaluated.  If the result is
     the lowest value, then the result of this assertion evaluation
     is the lowest value.

     Otherwise, the key expression in the Licensees field is
     evaluated, and the resulting value of this assertion is the
     lower of the values of its Conditions and its
     Licensees expressions.  The write-back set of this assertion
     is the combination of:

     - The write-back set of this assertion's Conditions (if
       any)

     - The write-back set that is the result of this assertion's
       Licensees, after all the write-back attributes that are
       not exported (through the Export field, see section 3.7) by
       this assertion are removed.

     The Licensees write-back set writes over the Conditions
     write-back set.

   The Licensees field public-key expression is evaluated as
   follows:

     Let the key expression contain public key PK_i.  A variable `PK_i'
     corresponds to this key.

     If there is no assertion in which PK_i is the Authorizer, and PK_i
     does not appear in the action authorizers,  the value of the
     variable `PK_i' is the lowest return value.

     If PK_i appears in the action authorizers, the value of the
     variable `PK_i' is the highest return value.

     If PK_i appears in the Authorizer field of an assertion, the value
     of the variable 'PK_i' is that of the assertion.  If there is more
     than one assertions where PK_i is the Authorizer, `PK_i' takes the
     highest value among those assertions.

   The goal is to construct a directed graph of KeyNote assertions
   rooted at a POLICY assertion of the evaluator that connects with
   at least one of the keys in the action authorizers.  The value
   returned to the application (and the associated write-back set) is
   that of the highest-valued POLICY assertion.

   Delegation of some authorization from key A to a set of keys B is
   expressed as an assertion with key A in the Authorizer field, key set


KeyNote                 expires in six months                  [Page 14]


DRAFT                         KeyNote                        August 1998


   B in the Licensees field, and the authorization delegated
   encoded in the Conditions field.  How the expression digraph is
   constructed is implementation-dependent, in particular because
   different implementations may use different algorithms for
   optimizing the graph construction.


7.   Trust-Management Architecture

   KeyNote provides a simple mechanism for describing security policy
   and representing credentials.  It differs from traditional
   certification systems in that the security model is based on
   binding keys to predicates that describe what the key is authorized
   by policy to do, rather than on resolving names.  The
   infrastructure and architecture to support a KeyNote system is
   therefore rather different than that for a name-based certification
   scheme.  The KeyNote trust-management architecture is based on that
   of PolicyMaker [BFL96,BFS98].

   It is important to understand the separation between the
   responsibilities of the KeyNote system and those of the application
   and other support infrastructure.  A KeyNote evaluator will
   determine, based on policy and credential assertions, whether a
   proposed action is permitted according to policy.  The usefulness
   of this determination depends on a number of factors:

    - The action-environment attributes and the assignment of their
      values must reflect accurately the security requirements of the
      application.  Identifying the attributes to include in the action
      environment is perhaps the most important task in integrating
      KeyNote into new applications.

    - The policy of the application must be correct and well-formed.
      In particular, trust must be deferred only to keys and for
      predicates that should, in fact, be trusted by the application.

    - Finally, KeyNote does not directly enforce policy; it only
      provides advice to the applications that call it. KeyNote assumes
      that the application itself is trusted and that the policy
      assertions are correct. Nothing prevents an application from
      submitting misleading assertions to KeyNote, or from ignoring
      KeyNote altogether.

   It is also up to the application (or some service outside KeyNote)
   to select the appropriate credentials and policy assertions with
   which to run a particular query.  Note that even if inappropriate
   credentials are provided to KeyNote, this cannot result in the
   approval of an illegal action environment (as long as the policy
   assertions are correct and the the action environment itself is
   correctly passed to KeyNote).

   KeyNote is monotonic; adding an assertion to a query can never


KeyNote                 expires in six months                  [Page 15]


DRAFT                         KeyNote                        August 1998


   result in a query being rejected if it would have been accepted
   without the assertion.  Omitting credentials may, of course, result
   in legal action environments being disallowed.  Selecting
   appropriate credentials (e.g., from a distributed database or "key
   server") is outside the scope of KeyNote itself, and may properly
   be handled by the remote client making a request, by the local
   machine verifying the request, or by a network-based service,
   depending on the application.

   In addition, KeyNote does not itself provide credential revocation
   services, although credentials can be written to expire after some
   date by including a date test in the predicate.  Applications that
   require credential revocation can use KeyNote to help specify and
   implement revocation policies.  A future draft will address
   expiration and revocation services in KeyNote.

   Because KeyNote is designed to support a variety of applications,
   several different application interfaces to a KeyNote
   implementation are possible.  In the simplest, a KeyNote evaluator
   would exist as a stand-alone application, with other applications
   calling it as needed.  KeyNote might also be implemented as a
   library to which applications are linked.  Finally, a KeyNote
   implementation might run as a local trusted service, with local
   applications communicating their queries via some interprocess
   communication mechanism.


8.   Security Considerations

   This draft discusses a trust-management system  The draft is itself
   concerned with a security mechanism.


9.   Acknowledgments

   We thank Lorrie Faith Cranor (AT&T Labs - Research) and Jonathan M.
   Smith (University of Pennsylvania) for their suggestions and
   comments on earlier versions of this draft.


  References

   [BFL96] M. Blaze, J. Feigenbaum, J. Lacy, Decentralized Trust
           Management, 1996 IEEE Conference on Privacy and Security,
           Oakland, 1996.

   [BFS98] M. Blaze, J. Feigenbaum, M. Strauss, Compliance-Checking in
           the PolicyMaker Trust-Management System, 1998 Financial
           Crypto Conference

   [Bra97] S. Bradner, Key words for use in RFCs to Indicate
           Requirement Level, RFC 2119, March 1997.


KeyNote                 expires in six months                  [Page 16]


DRAFT                         KeyNote                        August 1998


   [DSA94] Digital Signature Standard, FIPS-186, National Institute of
           Standards, U.S. Department of Commerce, May 1994.

   [PKCS1] PKCS #1: RSA Encryption Standard, Version 1.5, RSA
           Laboratories, November 1993.

   [RSA78] A Method for Obtaining Digital Signatures and Public-Key
           Cryptosystems, R. L. Rivest, A. Shamir, L. M. Adleman,
           Communications of the ACM, v21n2, February 1978.


  Contacts

   Comments about this document should be discussed on the
   trustmgt@east.isi.edu mailing list.  The archive for that list can
   be found at http://www.cairn.net/trustmgt/

   Questions about this document can also be directed to:

    Matt Blaze             Joan Feigenbaum       John Ioannidis
    mab@research.att.com   jf@research.att.com   ji@research.att.com

                         AT&T Labs - Research
                         180 Park Avenue
                         Florham Park, New Jersey 07932-0000

    Angelos D. Keromytis
    Distributed Systems Lab
    CIS Department, University of Pennsylvania
    200 S. 33rd Street
    Philadelphia, Pennsylvania  19104-6389
    Email: angelos@dsl.cis.upenn.edu






















KeyNote                 expires in six months                  [Page 17]