keynote(4)

NAME

keynote - a trust-management system

SYNOPSIS

#include <sys/types.h>
#include <regex.h>
#include <keynote.h>
Link options: -lkeynote -lm -lcrypto

DESCRIPTION

For more details on KeyNote, see RFC 2704.

Details on the API, assertion syntax, and command-line tool
are given in the man pages listed at the end of this manual.
Trust management, introduced in the PolicyMaker system, is a
unified approach to specifying and interpreting security poli
cies, credentials, and relationships; it allows direct authoriza
tion of security-critical actions. A trust-management system pro
vides standard, general-purpose mechanisms for specifying appli
cation security policies and credentials. Trust-management cre
dentials describe a specific delegation of trust and subsume the
role of public key certificates; unlike traditional certificates,
which bind keys to names, credentials can bind keys directly to
the authorization to perform specific tasks.
A trust-management system has five basic components:
* A language for describing `actions,' which are operations
with: security consequences that are to be controlled by the; system.
* A mechanism for identifying `principals,' which are enti
ties that: can be authorized to perform actions.
* A language for specifying application `policies,' which
govern the: actions that principals are authorized to perform.
* A language for specifying `credentials,' which allow prin
cipals: to delegate authorization to other principals.
* A `compliance checker,' which provides a service to appli
cations: for determining how an action requested by principals; should be
handled, given a policy and a set of credentials.
The trust-management approach has a number of advantages
over other mechanisms for specifying and controlling authoriza
tion, especially when security policy is distributed over a net
work or is otherwise decentralized.
Trust management unifies the notions of security policy,
credentials, access control, and authorization. An application
that uses a trust-management system can simply ask the compliance
checker whether a requested action should be allowed. Further
more, policies and credentials are written in standard languages
that are shared by all trust-managed applications; the security
configuration mechanism for one application carries exactly the
same syntactic and semantic structure as that of another, even
when the semantics of the applications themselves are quite dif
ferent.
Trust-management policies are easy to distribute across net
works, helping to avoid the need for application-specific dis
tributed policy configuration mechanisms, access control lists,
and certificate parsers and interpreters.
For a general discussion of the use of trust management in
distributed system security, see the papers listed at the end of
this manual.
KeyNote is a simple and flexible trust-management system de
signed to work well for a variety of large- and small- scale In
ternet-based applications. It provides a single, unified language
for both local policies and credentials. KeyNote policies and
credentials, called `assertions,' contain predicates that de
scribe the trusted actions permitted by the holders of specific
public keys. KeyNote assertions are essentially small, highly
structured programs. A signed assertion, which can be sent over
an untrusted network, is also called a `credential assertion.'
Credential assertions, which also serve the role of certificates,
have the same syntax as policy assertions but are also signed by
the principal delegating the trust.
In KeyNote:
* Actions are specified as a collection of name-value pairs.
* Principal names can be any convenient string and can di
rectly: represent cryptographic public keys.
* The same language is used for both policies and creden
tials.
* The policy and credential language is concise, highly ex
pressive,: human readable and writable, and compatible with a variety; of
storage and transmission media, including electronic mail.
* The compliance checker returns an application-configured
`policy: compliance value' that describes how a request should be; handled
by the application. Policy compliance values are always
positively derived from policy and credentials, facilitat; ing
analysis of KeyNote-based systems.
* Compliance checking is efficient enough for high-perfor
mance and: real-time applications.
In KeyNote, the authority to perform trusted actions is as
sociated with one or more `principals.' A principal may be a
physical entity, a process in an operating system, a public key,
or any other convenient abstraction. KeyNote principals are iden
tified by a string called a `Principal Identifier.' In some cas
es, a Principal Identifier will contain a cryptographic key in
terpreted by the KeyNote system (e.g., for credential signature
verification). In other cases, Principal Identifiers may have a
structure that is opaque to KeyNote.
Principals perform two functions of concern to KeyNote: They
request `actions' and they issue `assertions.' Actions are any
trusted operations that an application places under KeyNote con
trol. Assertions delegate the authorization to perform actions
to other principals.
Actions are described to the KeyNote compliance checker in
terms of a collection of name-value pairs called an `action at
tribute set.' The action attribute set is created by the invoking
application. Its structure and format are described in detail
elsewhere of this document.
KeyNote provides advice to applications on the interpreta
tion of policy with regard to specific requested actions. Appli
cations invoke the KeyNote compliance checker by issuing a
`query' containing a proposed action attribute set and identify
ing the principal(s) requesting it. The KeyNote system determines
and returns an appropriate `policy compliance value' from an or
dered set of possible responses.
The policy compliance value returned from a KeyNote query
advises the application how to process the requested action. In
the simplest case, the compliance value is Boolean (e.g., "re
ject" or "approve"). Assertions can also be written to select
from a range of possible compliance values, when appropriate for
the application (e.g., "no access", "restricted access", "full
access"). Applications can configure the relative ordering (from
`weakest' to `strongest') of compliance values at query time.
Assertions are the basic programming unit for specifying
policy and delegating authority. Assertions describe the condi
tions under which a principal authorizes actions requested by
other principals. An assertion identifies the principal that made
it, which other principals are being authorized, and the condi
tions under which the authorization applies. The syntax of asser
tions is given keynote(5).
A special principal, whose identifier is "POLICY", provides
the root of trust in KeyNote. "POLICY" is therefore considered to
be authorized to perform any action.
Assertions issued by the "POLICY" principal are called `pol
icy assertions' and are used to delegate authority to otherwise
untrusted principals. The KeyNote security policy of an applica
tion consists of a collection of policy assertions.
When a principal is identified by a public key, it can digi
tally sign assertions and distribute them over untrusted networks
for use by other KeyNote compliance checkers. These signed asser
tions are also called `credentials,' and serve a role similar to
that of traditional public key certificates. Policies and creden
tials share the same syntax and are evaluated according to the
same semantics. A principal can therefore convert its policy as
sertions into credentials simply by digitally signing them.
KeyNote is designed to encourage the creation of human-read
able policies and credentials that are amenable to transmission
and storage over a variety of media. Its assertion syntax is in
spired by the format of RFC822-style message headers. A KeyNote
assertion contains a sequence of sections, called `fields,' each
of which specifying one aspect of the assertion's semantics.
Fields start with an identifier at the beginning of a line and
continue until the next field is encountered. For example:: KeyNote-Version: 2
Comment: A simple, if contrived, email certificate for us; er mab
Local-Constants: ATT_CA_key = "RSA:acdfa1df1011bbac"
mab_key = "DSA:deadbeefcafe001a"; Authorizer: ATT_CA_key
Licensees: mab_key
Conditions: ((app_domain == "email") # valid for email; only
&& (address == "mab@research.att.com"));; Signature: "RSA-SHA1:f00f2244"
For the exact meanings of all the fields, see the RFC refer
ence at the end of this manual, and/or keynote(5).
KeyNote semantics resolve the relationship between an appli
cation's policy and actions requested by other principals, as
supported by credentials. The KeyNote compliance checker process
es the assertions against the action attribute set to determine
the policy compliance value of a requested action. These seman
tics are defined later in this document.
An important principle in KeyNote's design is `assertion
monotonicity'; the policy compliance value of an action is always
positively derived from assertions made by trusted principals.
Removing an assertion never results in increasing the compliance
value returned by KeyNote for a given query. The monotonicity
property can simplify the design and analysis of complex network
based security protocols; network failures that prevent the
transmission of credentials can never result in spurious autho
rization of dangerous actions.
Trusted actions to be evaluated by KeyNote are described by
a collection of name-value pairs called the `action attribute
set'. Action attributes are the mechanism by which applications
communicate requests to KeyNote and are the primary objects on
which KeyNote assertions operate. An action attribute set is
passed to the KeyNote compliance checker with each query.
Each action attribute consists of a name and a value. The
semantics of the names and values are not interpreted by KeyNote
itself; they vary from application to application and must be
agreed upon by the writers of applications and the writers of the
policies and credentials that will be used by them.
Action attribute names and values are represented by arbi
trary-length strings. KeyNote guarantees support of attribute
names and values up to 2048 characters long. Applications and as
sertions should therefore avoid depending on the use of at
tributes with names or values longer than 2048 characters.
Attribute values are inherently untyped and are represented
as character strings by default. Attribute values may contain any
non- NUL ASCII character. Numeric attribute values should first
be converted to an ASCII text representation by the invoking ap
plication, e.g., the value 1234.5 would be represented by the
string "1234.5".
An <AttributeID> begins with an alphabetic or underscore
character and can be followed by any number of alphanumerics and
underscores. Attribute names are case-sensitive.
If an action attribute is not defined its value is consid
ered to be the empty string.
Attribute names beginning with the "_" character are re
served for use by the KeyNote runtime environment and cannot be
passed from applications as part of queries. The following spe
cial attribute names are used:
_MIN_TRUST: Lowest-order (minimum) compliance value in query.
_MAX_TRUST: Highest-order (maximum) compliance value in query.
_VALUES: Linearly ordered set of compliance value in query.
_ACTION_AUTHORIZERS: Names of principals directly authorizing action in; query. Comma separated.
In addition, attributes with names of the form "_<N>", where
<N> is an ASCII-encoded integer, are used by the regular expres
sion matching mechanism described in keynote(5).
By convention, the name of the application domain over which
action attributes should be interpreted is given in the attribute
named "app_domain". The IANA (or some other suitable authority)
will provide a registry of reserved app_domain names. The reg
istry will list the names and meanings of each application's at
tributes.
The app_domain convention helps to ensure that credentials
are interpreted as they were intended. An attribute with any giv
en name may be used in many different application domains but
might have different meanings in each of them. However, the use
of a global registry is not always required for small-scale,
closed applications; the only requirement is that the policies
and credentials made available to the KeyNote compliance checker
interpret attributes according to the same semantics assumed by
the application that created them.
For example, an email application might reserve the app_do
main "RFC822-EMAIL" and might use the attributes named "address"
(the mail address of a message's sender), "name" (the human name
of the message sender), and any "organization" headers present
(the organization name). The values of these attributes would be
derived in the obvious way from the email message headers. The
public key of the message's signer would be given in the "_AC
TION_AUTHORIZERS" attribute.

QUERY SEMANTICS

The discussion in the following sections assume some famil
iarity with assertion syntax. Please refer to keynote(5) for more
details on the syntax.

QUERY PARAMETERS

A KeyNote query has four parameters:

* The identifier of the principal(s) requesting the action.

* The action attribute set describing the action.

* The set of compliance values of interest to the applica
tion,: ordered from _MIN_TRUST to _MAX_TRUST
* The policy and credential assertions that should be in
cluded in: the evaluation.
The mechanism for passing these parameters to the KeyNote
evaluator is application dependent. In particular, an evaluator
might provide for some parameters to be passed explicitly, while
others are looked up externally (e.g., credentials might be
looked up in a network- based distribution system), while still
others might be requested from the application as needed by the
evaluator, through a `callback' mechanism (e.g., for attribute
values that represent values from among a very large namespace).

ACTION REQUESTER

At least one Principal must be identified in each query as
the `requester' of the action. Actions may be requested by sever
al principals, each considered to have individually requested it.
This allows policies that require multiple authorizations, e.g.,
`two person control'. The set of authorizing principals is made
available in the special attribute "_ACTION_AUTHORIZERS"; if sev
eral principals are authorizers, their identifiers are separated
with commas.

ORDERED COMPLIANCE VALUE SET

The set of compliance values of interest to an application
(and their relative ranking to one another) is determined by the
invoking application and passed to the KeyNote evaluator as a pa
rameter of the query. In many applications, this will be Boolean,
e.g., the ordered sets {FALSE, TRUE} or {REJECT, APPROVE}. Other
applications may require a range of possible values, e.g.,
{No_Access, Limited_Access, Full_Access}. Note that applications
should include in this set only compliance value names that are
actually returned by the assertions.
The lowest-order and highest-order compliance value strings
given in the query are available in the special attributes named
"_MIN_TRUST" and "_MAX_TRUST", respectively. The complete set of
query compliance values is made available in ascending order
(from _MIN_TRUST to _MAX_TRUST) in the special attribute named
"_VALUES". Values are separated with commas; applications that
use assertions that make use of the _VALUES attribute should
therefore avoid the use of compliance value strings that them
selves contain commas.

PRINCIPAL IDENTIFIER NORMALIZATION

Principal identifier comparisons among Cryptographic Princi
pal Identifiers (that represent keys) in the Authorizer and Li
censees fields or in an action's direct authorizers are performed
after normalizing them by conversion to a canonical form.
Every cryptographic algorithm used in KeyNote defines a
method for converting keys to their canonical form and that spec
ifies how the comparison for equality of two keys is performed.
If the algorithm named in the identifier is unknown to KeyNote,
the identifier is treated as opaque.
Opaque identifiers are compared as case-sensitive strings.
Notice that use of opaque identifiers in the Authorizer
field requires that the assertion's integrity be locally trusted
(since it cannot be cryptographically verified by the compliance
checker).

POLICY COMPLIANCE VALUE CALCULATION

The Policy Compliance Value of a query is the Principal Com
pliance Value of the principal named "POLICY".

PRINCIPAL COMPLIANCE VALUE

The Compliance Value of a principal <X> is the highest order
(maximum) of:
- the Direct Authorization Value of principal <X>; and
- the Assertion Compliance Values of all assertions identi
fying: <X> in the Authorizer field.

DIRECT AUTHORIZATION VALUE

The Direct Authorization Value of a principal <X> is
_MAX_TRUST if <X> is listed in the query as an authorizer of the
action. Otherwise, the Direct Authorization Value of <X> is
_MIN_TRUST.

ASSERTION COMPLIANC VALUE

The Assertion Compliance Value of an assertion is the lowest
order (minimum) of the assertion's Conditions Compliance Value
and its Licensee Compliance Value.

CONDITIONS COMPLIANCE VALUE

The Conditions Compliance Value of an assertion is the high
est-order (maximum) value among all successful clauses listed in
the conditions section.
If no clause's test succeeds or the Conditions field is emp
ty, an assertion's Conditions Compliance Value is considered to
be the _MIN_TRUST value, as described previously.
If an assertion's Conditions field is missing entirely, its
Conditions Compliance Value is considered to be the _MAX_TRUST
value, as defined previously.
The set of successful test clause values is calculated as
follows:
Recall from the grammar of the Conditions field (see
keynote(5) for more details) that each clause in the conditions
section has two logical parts: a `test' and an optional `value',
which, if present, is separated from the test with the "->" to
ken. The test subclause is a predicate that either succeeds
(evaluates to logical `true') or fails (evaluates to logical
`false'). The value subclause is a string expression that evalu
ates to one value from the ordered set of compliance values given
with the query. If the value subclause is missing, it is consid
ered to be _MAX_TRUST. That is, the clause: foo=="bar";
is equivalent to: foo=="bar" -> _MAX_TRUST;
If the value component of a clause is present, in the sim
plest case it contains a string expression representing a possi
ble compliance value. For example, consider an assertion with
the following Conditions field:: Conditions:
@user_id == 0 -> "full_access"; #

clause (1)
@user_id < 1000 -> "user_access"; #

clause (2)
@user_id < 10000 -> "guest_access"; #

clause (3)
user_name == "root" -> "full_access"; #

clause (4)
Here, if the value of the "user_id" attribute is "1073" and
the "user_name" attribute is "root", the possible compliance val
ue set would contain the values "guest_access" (by clause (3))
and "full_access" (by clause (4)). If the ordered set of compli
ance values given in the query (in ascending order) is {"no_ac
cess", "guest_access", "user_access", "full_access"}, the Condi
tions Compliance Value of the assertion would be "full_access"
(because "full_access" has a higher-order value than "guest_ac
cess"). If the "user_id" attribute had the value "19283" and the
"user_name" attribute had the value "nobody", no clause would
succeed and the Conditions Compliance Value would be "no_access",
which is the lowest-order possible value (_MIN_TRUST).
If a clause lists an explicit value, its value string must
be named in the query ordered compliance value set. Values not
named in the query compliance value set are considered equivalent
to _MIN_TRUST.
The value component of a clause can also contain recursive
ly-nested clauses. Recursively-nested clauses are evaluated only
if their parent test is true. That is,: a=="b" -> { b=="c" -> "value1";
d=="e" -> "value2";
true -> "value3"; } ;
is equivalent to: (a=="b") && (b=="c") -> "value1";
(a=="b") && (d=="e") -> "value2";
(a=="b") -> "value3";
Notice that string comparisons are case-sensitive.
A regular expression comparison ("~=") is considered true if
the left-hand-side string expression matches the right-hand-side
regular expression. If the POSIX regular expression group match
ing scheme is used, the number of groups matched is placed in the
temporary meta- attribute "_0" (dereferenced as _0), and each
match is placed in sequence in the temporary attributes (_1, _2,
..., _N). These match-attributes' values are valid only within
subsequent references made within the same clause. Regular ex
pression evaluation is case- sensitive.
A runtime error occurring in the evaluation of a test, such
as division by zero or an invalid regular expression, causes the
test to be considered false. For example:: foo == "bar" -> {
@a == 1/0 -> "oneval"; # sub

clause 1
@a == 2 -> "anotherval"; # sub

clause 2; };
Here, subclause 1 triggers a runtime error. Subclause 1 is
therefore false (and has the value _MIN_TRUST). Subclause 2, how
ever, would be evaluated normally.
An invalid <RegExpr> is considered a runtime error and caus
es the test in which it occurs to be considered false.

LICENSEE COMPLIANCE VALUE

The Licensee Compliance Value of an assertion is calculated
by evaluating the expression in the Licensees field, based on the
Principal Compliance Value of the principals named there.
If an assertion's Licensees field is empty, its Licensee
Compliance Value is considered to be _MIN_TRUST. If an asser
tion's Licensees field is missing altogether, its Licensee Com
pliance Value is considered to be _MAX_TRUST.
For each principal named in the Licensees field, its Princi
pal Compliance Value is substituted for its name. If no Principal
Compliance Value can be found for some named principal, its name
is substituted with the _MIN_TRUST value.
The licensees expression (see keynote(5)) is evaluated as
follows:
* A "(...)" expression has the value of the enclosed subex
pression.
* A "&&" expression has the lower-order (minimum) of its two: subexpression values.
* A "||" expression has the higher-order (maximum) of its
two: subexpression values.
* A "<K>-of(<List>)" expression has the K-th highest order: compliance value listed in <list>. Values that appear; multiple
times are counted with multiplicity. For example, if K =; 3 and
the orders of the listed compliance values are (0, 1, 2,; 2, 3),
the value of the expression is the compliance value of or; der 2.
For example, consider the following Licensees field:: Licensees: ("alice" && "bob") || "eve"
If the Principal Compliance Value is "yes" for principal
"alice", "no" for principal "bob", and "no" for principal "eve",
and "yes" is higher order than "no" in the query's Compliance
Value Set, then the resulting Licensee Compliance Value is "no".
Observe that if there are exactly two possible compliance
values (e.g., "false" and "true"), the rules of Licensee Compli
ance Value resolution reduce exactly to standard Boolean logic.

ASSERTION MANAGEMENT

Assertions may be either signed or unsigned. Only signed as
sertions should be used as credentials or transmitted or stored
on untrusted media. Unsigned assertions should be used only to
specify policy and for assertions whose integrity has already
been verified as conforming to local policy by some mechanism ex
ternal to the KeyNote system itself (e.g., X.509 certificates
converted to KeyNote assertions by a trusted conversion program).
Implementations that permit signed credentials to be veri
fied by the KeyNote compliance checker generally provide two
`channels' through which applications can make assertions avail
able. Unsigned, locally-trusted assertions are provided over a
`trusted' interface, while signed credentials are provided over
an `untrusted' interface. The KeyNote compliance checker veri
fies correct signatures for all assertions submitted over the un
trusted interface. The integrity of KeyNote evaluation requires
that only assertions trusted as reflecting local policy are sub
mitted to KeyNote via the trusted interface.
Note that applications that use KeyNote exclusively as a lo
cal policy specification mechanism need use only trusted asser
tions. Other applications might need only a small number of in
frequently changed trusted assertions to `bootstrap' a policy
whose details are specified in signed credentials issued by oth
ers and submitted over the untrusted interface.

EXAMPLES

A policy that delegates authority for the "SPEND" applica
tion domain to RSA key dab212 when the amount given in the "dol
lars" attribute is less than 10000.: Authorizer: "POLICY"
Licensees: "RSA:dab212" # the CFO's key
Conditions: (app_domain=="SPEND") && (@dollars <; 10000);
RSA key dab212 delegates authorization to any two signers,
from a list, one of which must be DSA key feed1234 in the "SPEND"
application when @dollars < 7500. If the amount in @dollars is
2500 or greater, the request is approved but logged.: KeyNote-Version: 2
Comment: This credential specifies a spending policy
Authorizer: "RSA:dab212" # the CFO
Licensees: "DSA:feed1234" && # The vice president
("RSA:abc123" || # middle manager #1
"DSA:bcd987" || # middle manager #2
"DSA:cde333" || # middle manager #3
"DSA:def975" || # middle manager #4
"DSA:978add") # middle manager #5

Conditions: (app_domain=="SPEND") # note nested

clauses

-> { (@(dollars) < 2500)
-> _MAX_TRUST;

(@(dollars) < 7500)

-> "ApproveAndLog";

};

Signature: "RSA-SHA1:9867a1"
According to this policy, any two signers from the list of
managers will do if @(dollars) < 1000:: KeyNote-Version: 2
Authorizer: "POLICY"
Licensees: 2-of("DSA:feed1234", # The VP
"RSA:abc123", # Middle management

clones
"DSA:bcd987",
"DSA:cde333",
"DSA:def975",
"DSA:978add"); Conditions: (app_domain=="SPEND") &&
(@(dollars) < 1000);
A credential from dab212 with a similar policy, but only one
signer is required if @(dollars) < 500. A log entry is made if
the amount is at least 100.: KeyNote-Version: 2
Comment: This one credential is equivalent to six; separate
credentials, one for each VP and middle

manager.
Individually, they can spend up to $500,

but if
it's $100 or more, we log it.; Authorizer: "RSA:dab212" # From the CFO
Licensees: "DSA:feed1234" || # The VP
"RSA:abc123" || # The middle manage

ment clones
"DSA:bcd987"
"DSA:cde333"
"DSA:def975"
"DSA:978add"; Conditions: (app_domain="SPEND") # nested clauses
-> { (@(dollars) < 100) -> _MAX_TRUST;
(@(dollars) < 500) -> "Approve

AndLog";

};; Signature: "RSA-SHA1:186123"
Assume a query in which the ordered set of Compliance Values
is {"Reject", "ApproveAndLog", "Approve"}. Under policies E and
G, and credentials F and H, the Policy Compliance Value is "Ap
prove" (_MAX_TRUST) when:: _ACTION_AUTHORIZERS = "DSA:978add"
app_domain = "SPEND"
dollars = "45"
unmentioned_attribute = "whatever"
and: _ACTION_AUTHORIZERS = "RSA:abc123,DSA:cde333"
app_domain = "SPEND"
dollars = "550"
The following return "ApproveAndLog":: _ACTION_AUTHORIZERS = "DSA:feed1234,DSA:cde333"
app_domain = "SPEND"
dollars = "5500"
and: _ACTION_AUTHORIZERS = "DSA:cde333"
app_domain = "SPEND"
dollars = "150"
However, the following return "Reject" (_MIN_TRUST):: _ACTION_AUTHORIZERS = "DSA:def975"
app_domain = "SPEND"
dollars = "550"
and: _ACTION_AUTHORIZERS = "DSA:cde333,DSA:978add"
app_domain = "SPEND"
dollars = "5500"

FILES

keynote.h
libkeynote.a

AUTHOR

Angelos D. Keromytis (angelos@dsl.cis.upenn.edu)

WEB PAGE

http://www.cis.upenn.edu/~keynote

BUGS

None that we know of. If you find any, please report them
at: keynote@research.att.com
BSD May 22, 1999

docs.sk

comprehensive documentation repository

In section

See also