SPKI Working Group Matt Blaze
Internet Draft Joan Feigenbaum
expires in six months Angelos D. Keromytis
March 1998
The KeyNote Trust Management System
draft-angelos-spki-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 learn the current status of any Internet-Draft, please check the
``1id-abstracts.txt'' listing contained in the internet-drafts Shadow
Directories on:
ftp.is.co.za (Africa)
nic.nordu.net (Europe)
ds.internic.net (US East Coast)
ftp.isi.edu (US West Coast)
munnari.oz.au (Pacific Rim)
Distribution of this memo is unlimited.
Abstract
This memo describes KeyNote, a simple trust management system to
support public-key infrastructure. 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.
Blaze/Feigenbaum/Keromytis expires in six months [Page i]
DRAFT KeyNote March 1998
1. Introduction
This memo describes KeyNote, a simple trust management system for
public key infrastructures. Trust management, introduced in the
PolicyMaker system [cite BFL96], is a unified approach to
specifying and interpreting security policies, credentials, and
relationships that allows direct 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 called a Credential
Assertion. Credential assertions, which serve the role of
"certificates," have the same syntax as policy assertions with the
additional feature that they are signed by the entity delegating
the trust. A KeyNote evaluator accepts as input a set of local
policy assertions, a collection of credential assertions, and a
collection of attributes, called an "action environment," that
describes a proposed trusted action associated with a set of public
keys. KeyNote determines whether proposed actions are consistent
with local policy by applying the assertion predicates to the
action environment.
Although the basic design of KeyNote is similar in spirit to that of
PolicyMaker, KeyNote's features have been simplified to more directly
support public-key infrastructure-like applications. The central
differences between PolicyMaker and KeyNote are:
- KeyNote predicates are written in a simple notation based on
C-like expressions and regular expressions.
- The KeyNote system always returns a boolean (trusted or not)
answer.
- Credential signature verification is built in to the
KeyNote system.
- Assertion syntax is based on a human-readable
"RFC-822"-style syntax.
- Trusted actions are described by simple attribute/value pairs.
Blaze/Feigenbaum/Keromytis expires in six months [Page 1]
DRAFT KeyNote March 1998
2. KeyNote Assertion Format
All KeyNote assertions are encoded in ASCII strings. Four mandatory
fields MUST appear in all assertions (VERSION, SIGNER,
KEY-PREDICATE, and TRUST-PREDICATE); one optional field MAY appear
(SIGNATURE).
The version of KeyNote assertions described in this document is 1.
In this version of KeyNote, field names (such as VERSION, SIGNER
etc.) can be at most 20 characters long. All fields have to start
at the begining of a line; fields may be continued by indenting
with at least one SPACE or TAB character at the begining 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 (converted to lower case
before processing). 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.
2.1 Key Encoding
Keys are encoded as ALG[:LEN:HEXDIGITS]+, where LEN is an
ASCII-encoded decimal number at most 20 characters long, indicating
the number of characters in the HEXDIGITS field. HEXDIGITS is a
string of hex digits, containing the key. If more than one
component is needed by the signature algorithm, the extra
components are appended. The required number of components is
determined by the key type. ALG is an ASCII string at most 20
characters long that describes the key type (such as RSA or DSA).
2.2 The VERSION field
The VERSION field is of the form VERSION:VerNumber, where VerNumber
is an ASCII-encode decimal up to 20 characters long. The current
version is 1.
2.3 The SIGNER field
The SIGNER field is of the form SIGNER:KEY, where KEY is a key
encoded as described in 2.1. The SIGNER field may instead be of
the form SIGNER:Policy. A Policy assertion is one that is trusted
directly by the local environment. It can serve as the "root" of a
trust structure that authorizes a requested action. A valid input
to the KeyNote evaluator must contain at least one Policy
Blaze/Feigenbaum/Keromytis expires in six months [Page 2]
DRAFT KeyNote March 1998
assertion. Because they are trusted locally, Policy assertions do
not require cryptographic signature verification.
2.4 The KEY-PREDICATE field
The KEY-PREDICATE field is of the form Key-Predicate: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) |
KEY
KEYLIST: KEY |
KEY, KEYLIST
The "&&" operator has higher precedence than the "||" operator.
"K" is an ASCII-encoded decimal number of at most 20 characters. A
KEYLIST SHOULD contain at least K keys. Whitespace characters
(space, tab, newline) in KEY-EXPR MUST be ignored. The semantics
of k-OF are that at least K distinct keys from the KEYLIST must
authorize a request. If the KEY-EXPR field is empty, it always
evaluates to TRUE and is used for direct authorization of a
TRUST-PREDICATE by a policy or a credential.
2.5 The SIGNATURE field
The SIGNATURE field is of the form Signature:NAME[:LEN:SIG]+, where
NAME is an ASCII string at most 20 characters long that indicates
the signature type (e.g. RSA-MD5-PKCS1). LEN is an ASCII encoded
decimal number at most 20 characters long, indicating the length of
the SIG field. SIG is a string of hex digits, containing the
digital signature. If more than one component is needed by the
signature algorithm, the extra components are appended. The
required number of components is determined by the NAME field
value. The signature is computed over the VERSION, SIGNER,
KEY-PREDICATE and TRUST-PREDICATE fields, concatenated with the
NAME field, as they appear in the credential.
2.6 The TRUST-PREDICATE field
The TRUST-PREDICATE field is of the form Trust-Predicate:EXPR.
EXPR is described by the following grammar:
Blaze/Feigenbaum/Keromytis expires in six months [Page 3]
DRAFT KeyNote March 1998
EXPR: (EXPR) |
EXPR && EXPR | /* Logical AND */
EXPR \|\| EXPR | /* Logical OR */
!EXPR | /* Logical NOT */
NUMEXPR |
STRINGEXPR |
true |
false
NUMEXPR: NUMEX < NUMEX | /* Numerical expression comparisons */
NUMEX > NUMEX |
NUMEX <= NUMEX |
NUMEX >= NUMEX |
NUMEX = NUMEX |
NUMEX != NUMEX
STRINGEXPR: STR = STR | /* String comparisons */
STR != STR |
STR < STR | /* Alphanumeric comparison */
STR > STR |
STR <= STR |
STR >= STR |
STR ~= REGEXP /* Regular expression matching */
STR: STR + STR | /* String concatenation */
LITERALSTRING |
VARIABLE
NUMEX: NUMEX + NUMEX | /* Arithmetic operations */
NUMEX - NUMEX |
NUMEX * NUMEX |
NUMEX / NUMEX |
NUMEX % NUMEX |
NUMEX ^ NUMEX | /* Exponentation */
-NUMEX
(NUMEX) |
NUMBER |
NUMVARIABLE
NUMBER: [0-9]+
STRING: [a-zA-Z][a-zA-Z0-9_\?\.;\\]*
DQUOTE: \"
LITERALSTRING: DQUOTE .* DQUOTE
VARIABLE: "$"STRING
NUMVARIABLE: "@"STRING
Blaze/Feigenbaum/Keromytis expires in six months [Page 4]
DRAFT KeyNote March 1998
The numeric operation precedence is (higher to lower) ^, (*, /, %),
(+, -). Operators of equal precedence are evaluated
left-to-right. REGEXP refers to the common regular expression
syntax and semantics as defined in the UNIX "egrep" command.
If a TRUST-PREDICATE field is empty, it always evaluates to TRUE.
3. 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 variables used by
assertion predicates.
The action environment specifies a collection of values of named
attributes. The attributes may be examined as variables 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
variables:
ATTRIBUTE1=VALUE1
ATTRIBUTE2=VALUE2
...
Only one attribute, called "$ACTION_SIGNERS", is mandatory. This
attribute lists the key or keys associated with the action
environment (e.g., signer of the message whose trust is being
evaluated by KeyNote). The $ACTION_SIGNERS attribute is used to
provide the initial keys to match against the KEY-PREDICATEs.
If an action environment attribute is not defined, it MUST
to evaluate to the empty string.
In most cases, the $ACTION_SIGNERS attribute will consist of a
single public key (of the ALG:LEN:VAL form specified in the previous
section):
$ACTION_SIGNERS="dsa:6:a1bc4f"
If an action is associated with more than one key, the
ACTION_SIGNERS attribute may contain a comma-separated list of
keys.
Blaze/Feigenbaum/Keromytis expires in six months [Page 5]
DRAFT KeyNote March 1998
$ACTION_SIGNERS="dsa:6:a1bc4f, rsa:8:f89a41bc"
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 defer trust between them. 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.
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 security headers.
Note that RFC822-EMAIL is simply an 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.)
4. 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 variable $App_Domain is assigned the name of the
application (e.g., "RFC822-EMAIL").
The keys that authenticate the request for a trusted action are
assigned to the variable $Action_Signers.
The rest of the action environment attributes are placed in their
Blaze/Feigenbaum/Keromytis expires in six months [Page 6]
DRAFT KeyNote March 1998
respective variables.
The time of day MAY be placed in the variables $GMTTimeOfDay and
$LocalTimeOfDay, using the format YYYYMMDDHHMMSS (e.g.,
19980307191512).
Any other implementation-dependent variables and their bindings are
also created at this step.
For each KeyNote assertion passed to the evaluation engine, the
following steps are taken:
The TRUST-PREDICATE expression is evaluated. If the result is
boolean TRUE, and the key expression in the KEY-PREDICATE
field is also true, the request is approved. Otherwise, it is
rejected.
The KEY-PREDICATE field public-key expression is evaluated as
follows:
Let the key expression contain public key PK_i. A boolean
variable `PK_i' corresponds to this key.
If there is no assertion in which PK_i is the
SIGNER, then the boolean variable `PK_i' is false.
If there is at least one assertion in which PK_i is
the source, then the boolean variable `PK_i' is true
if and only if at least one of those assertions is true.
For a request to be approved, there must exist a directed graph
of KeyNote assertions rooted at a POLICY assertion of the
evaluator that evaluates to TRUE. If such a directed graph cannot
be constructed, the request is denied for lack of authorization.
Delegation of some authorization from key A to a set of keys B is
expressed as an assertion with key A in the SIGNER field, key set B
in the KEY-PREDICATE field, and the authorization delegated encoded
in the TRUST-PREDICATE field. How the expression digraph is
constructed is implementation-dependent, in particular because
different implementations may use different algorithms for
optimizing the graph construction.
Blaze/Feigenbaum/Keromytis expires in six months [Page 7]
DRAFT KeyNote March 1998
5. Examples
In the interest of readability, these examples use much shorter
keys than would orinarily be used. Note that the "SIGNATURE"
fields in these examples do not represent the result of any real
signature calculation.
A. A policy unconditionally delegating trust to the holder of RSA
key abc123:
VERSION: 1
SIGNER: policy
KEY-PREDICATE: rsa-sha1-pkcsX:6:abc123;
TRUST-PREDICATE: true
B. A credential assertion in which RSA Key abc123 trusts either
DSA key def456 or RSA key 123aaa to perform actions in which
the "app_domain" is "rfc822-email", the "name" is either
"M. Blaze" or empty, and the "address" matches the regular
expression "^.*@keynote.research.att.com$". In other
words, abc123 trusts def456 and 123aaa as certification
authorities for the keynote.research.att.com domain.
VERSION: 1
SIGNER: rsa-sha1-pkcsX:6:abc123
KEY-PREDICATE: dsa-sha1-pkcsX:6:def456 ||
rsa-sha1-pkcsX:6:123aaa
TRUST-PREDICATE: (($app_domain="RFC822-EMAIL") &&
($name = "M. Blaze" || $name = "") &&
($address ~= "^.*@keynote.research.att.com$"))
SIGNATURE: rsa-md5-pkcsX:10:00112233445566a3
C. A certificate credential for a specific user, issued by one of
the certification authorities above:
VERSION: 1
SIGNER: dsa-sha1-pkcsX:6:def456
KEY-PREDICATE: dsa-sha1-pkcsX:6:01a32f
TRUST-PREDICATE: (($app_domain="RFC822-EMAIL") &&
($address="mab@keynote.research.att.com"))
SIGNATURE: rsa-sha1-pkcsX:10:f43a2c81ffea129d
Observe that under policy A and credentials B and C, the following
action environments are accepted:
Blaze/Feigenbaum/Keromytis expires in six months [Page 8]
DRAFT KeyNote March 1998
$action_signer = "dsa-sha1-pkcsX:6:01a32f"
$app_domain = "RFC822-EMAIL"
$address="mab@keynote.research.att.com"
and
$action_signer = "dsa-sha1-pkcsX:6:01a32f"
$app_domain = "RFC822-EMAIL"
$address="mab@keynote.research.att.com"
$name="M. Blaze"
while the following are not accepted:
$action_signer = "dsa-sha1-pkcsX:6:01a32f"
$app_domain = "RFC822-EMAIL"
$address="angelos@dsl.cis.upenn.edu"
and
$action_signer = "dsa-sha1-pkcsX:6:01a32f"
$app_domain = "RFC822-EMAIL"
$address="mab@keynote.research.att.com"
$name="J. Feigenbaum"
D. A policy that deligates trust for the "SPEND" application domain
to RSA key bbc1ab when @dollars is less than 10000.
VERSION: 1
SIGNER: policy
KEY-PREDICATE: rsa-sha1-pkcsX:6:bbc1ab
TRUST-PREDICATE: (($app_domain="SPEND") &&
(@dollars < 10000))
E. RSA key bbc1ab requires the signature of at least 2 signers,
one of which must be DSA key 44aabb in the "SPEND" application
when @dollars is less than 5000
VERSION: 1
SIGNER: rsa-sha1-pkcsX:6:bbc1ab
KEY-PREDICATE: (dsa-sha1-pkcsX:6:44aabb &&
((rsa-sha1-pkcsX:6:ffb1c4 ||
dsa-sha1-pkcsX:6:c2d100 ||
dsa-sha1-pkcsX:6:6a5023 ||
dsa-sha1-pkcsX:4:dead ||
dsa-sha1-pkcsX:4:beef))
TRUST-PREDICATE: (($app_domain="SPEND") &&
(@dollars < 5000))
SIGNATURE: rsa-sha1-pkcsX:10:ffab110c761b41cd
F. As above, but only one signer required if @VALUE < 100.
Blaze/Feigenbaum/Keromytis expires in six months [Page 9]
DRAFT KeyNote March 1998
VERSION: 1
SIGNER: rsa-sha1-pkcsX:6:bbc1ab
KEY-PREDICATE: (dsa-sha1-pkcsX:6:44aabb ||
rsa-sha1-pkcsX:6:ffb1c4 ||
dsa-sha1-pkcsX:6:c2d100 ||
dsa-sha1-pkcsX:6:6a5023 ||
dsa-sha1-pkcsX:4:dead ||
dsa-sha1-pkcsX:4:beef)
TRUST-PREDICATE: (($app_domain="SPEND") &&
(@dollars < 100))
SIGNATURE: rsa-sha1-pkcsX:10:a000ff1c0a44ccdd
G. A policy that at least two signers are required to authorize the
launch of missiles against London or Moscow.
VERSION: 1
SIGNER: policy
KEY-PREDICATE: 2-of(dsa-sha1-pkcsX:6:44aabb,
rsa-sha1-pkcsX:6:ffb1c4,
dsa-sha1-pkcsX:6:c2d100,
dsa-sha1-pkcsX:6:6a5023,
dsa-sha1-pkcsX:4:dead,
dsa-sha1-pkcsX:4:beef)
TRUST-PREDICATE: (($app_domain="NUKE") &&
($action="launch") &&
($delivery_system="missile") &&
(($target="moscow") || ($target="london")))
6. 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 [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
Blaze/Feigenbaum/Keromytis expires in six months [Page 10]
DRAFT KeyNote March 1998
of this determination depends on a number of factors. First, 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. Second, 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 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.
Observe that KeyNote adopts an almost opposite approach from that
of a general-purpose name-based certification scheme. In
name-based schemes (such as X.509), the infrastructure aims to
provide a common application-independent certificate, with each
application left to develop its own mechanism to interpret the
security semantics of the name. KeyNote, on the other hand, aims
to provide a common, application-independent mechanism for use with
application-specific credentials and policies. Each application
Blaze/Feigenbaum/Keromytis expires in six months [Page 11]
DRAFT KeyNote March 1998
(or class of applications) will develop its own set of attributes,
with application-specific credentials and policies created to
operate on them.
Nevertheless, it is possible to take advantage of an existing
general-purpose name-based infrastructure but still use KeyNote to
specify policy and trust in some applications. If an X.509 [X509],
PGP [Zim95], or SDSI [LR97] -based certificate distribution
infrastructure provides reliable bindings between names and keys,
these certificates can be converted to KeyNote assertions that
verify that an appropriate action environment attribute has the
correct name. Policy assertions can be used to specify the X.509,
PGP, or SDSI certification authorities that are trusted for various
kinds of names, etc.
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.
7. Security Considerations
This draft discusses a trust management system for public key
infrastructures. The draft is itself concerned with a security
mechanism.
References
[BFL96] M. Blaze, J. Feigenbaum, J. Lacy. Decentralized Trust
Management. 1996 IEEE Conference on Privacy and Security.
Oakland, 1996.
[LR97] B. Lampson, R. Rivest. SDSI - Simple Distributed System
Infrastructure. Draft. 1997.
[Zim95] P. Zimmermann. PGP User's Manual. 1995.
(More comprehensive reference list to appear in a future version of
this draft).
Blaze/Feigenbaum/Keromytis expires in six months [Page 12]
DRAFT KeyNote March 1998
Contacts
Comments about this document should be discussed on the spki@c2.net
mailing list.
Questions about this document can also be directed to:
Matt Blaze
AT&T Labs - Research
180 Park Avenue
Florham Park, New Jersey 07932
mab@research.att.com
Joan Feigenbaum
AT&T Labs - Research
180 Park Avenue
Florham Park, New Jersey 07932
jf@research.att.com
Angelos D. Keromytis
Distributed Systems Lab
CIS Department, University of Pennsylvania
200 S. 33rd Street
Philadelphia, Pennsylvania 19104-6389
angelos@dsl.cis.upenn.edu
Blaze/Feigenbaum/Keromytis expires in six months [Page 13]