The KeyNote compliance checker verifies correct signatures for all
assertions submitted over the untrusted interface. The integrity of
KeyNote evaluation requires that only assertions trusted as
reflecting local policy are submitted to KeyNote via the trusted
interface.
Note that applications that use KeyNote exclusively as a local policy
specification mechanism need use only trusted assertions. Other
applications might need only a small number of infrequently changed
trusted assertions to `bootstrap' a policy whose details are
specified in signed credentials issued by others and submitted over
the untrusted interface.
5.5 Implementation Issues
Informally, the semantics of KeyNote evaluation can be thought of as
involving the construction a directed graph of KeyNote assertions
rooted at a POLICY assertion that connects with at least one of the
principals that requested the action.
Delegation of some authorization from principal <A> to a set of
principals <B> is expressed as an assertion with principal <A> given
in the Authorizer field, principal set <B> given in the Licensees
field, and the authorization to be delegated encoded in the
Conditions field. How the expression digraph is constructed is
implementation-dependent and implementations may use different
algorithms for optimizing the graph's construction. Some
implementations might use a `bottom up' traversal starting at the
principals that requested the action, others might follow a `top
down' approach starting at the POLICY assertions, and still others
might employ other heuristics entirely.
Implementations are encouraged to employ mechanisms for recording
exceptions (such as division by zero or syntax error), and reporting
them to the invoking application if requested. Such mechanisms are
outside the scope of this document.
6. Examples
In this section, we give examples of KeyNote assertions that might be
used in hypothetical applications. These examples are intended
primarily to illustrate features of KeyNote assertion syntax and
semantics, and do not necessarily represent the best way to integrate
KeyNote into applications.
In the interest of readability, we use much shorter keys than would
ordinarily be used in practice. Note that the Signature fields in
these examples do not represent the result of any real signature
calculation.
1. TRADITIONAL CA / EMAIL
A. A policy unconditionally authorizing RSA key abc123 for all
actions. This essentially defers the ability to specify
policy to the holder of the secret key corresponding to
abc123:
Authorizer: "POLICY"
Licensees: "RSA:abc123"
B. A credential assertion in which RSA Key abc123 trusts either
RSA key 4401ff92 (called `Alice') or DSA key d1234f (called
`Bob') to perform actions in which the "app_domain" is
"RFC822-EMAIL", where the "address" matches the regular
expression "^.*@keynote\.research\.att\.com$". In other
words, abc123 trusts Alice and Bob as certification
authorities for the keynote.research.att.com domain.
KeyNote-Version: 2
Local-Constants: Alice="DSA:4401ff92" # Alice's key
Bob="RSA:d1234f" # Bob's key
Authorizer: "RSA:abc123"
Licensees: Alice || Bob
Conditions: (app_domain == "RFC822-EMAIL") &&
(address ~= # only applies to one domain
"^.*@keynote\\.research\\.att\\.com$");
Signature: "RSA-SHA1:213354f9"
C. A certificate credential for a specific user whose email
address is mab@keynote.research.att.com and whose name, if
present, must be "M. Blaze". The credential was issued by the
`Alice' authority (whose key is certified in Example B
above):
KeyNote-Version: 2
Authorizer: "DSA:4401ff92" # the Alice CA
Licensees: "DSA:12340987" # mab's key
Conditions: ((app_domain == "RFC822-EMAIL") &&
(name == "M. Blaze" || name == "") &&
(address == "mab@keynote.research.att.com"));
Signature: "DSA-SHA1:ab23487"
D. Another certificate credential for a specific user, also
issued by the `Alice' authority. This example allows three
different keys to sign as jf@keynote.research.att.com (each
for a different cryptographic algorithm). This is, in
effect, three credentials in one:
KeyNote-Version: "2"
Authorizer: "DSA:4401ff92" # the Alice CA
Licensees: "DSA:abc991" || # jf's DSA key
"RSA:cde773" || # jf's RSA key
"BFIK:fd091a" # jf's BFIK key
Conditions: ((app_domain == "RFC822-EMAIL") &&
(name == "J. Feigenbaum" || name == "") &&
(address == "jf@keynote.research.att.com"));
Signature: "DSA-SHA1:8912aa"
Observe that under policy A and credentials B, C and D, the
following action attribute sets are accepted (they return
_MAX_TRUST):
_ACTION_AUTHORIZERS = "dsa:12340987"
app_domain = "RFC822-EMAIL"
address = "mab@keynote.research.att.com"
and
_ACTION_AUTHORIZERS = "dsa:12340987"
app_domain = "RFC822-EMAIL"
address = "mab@keynote.research.att.com"
name = "M. Blaze"
while the following are not accepted (they return
_MIN_TRUST):
_ACTION_AUTHORIZERS = "dsa:12340987"
app_domain = "RFC822-EMAIL"
address = "angelos@dsl.cis.upenn.edu"
and
_ACTION_AUTHORIZERS = "dsa:abc991"
app_domain = "RFC822-EMAIL"
address = "mab@keynote.research.att.com"
name = "M. Blaze"
and
_ACTION_AUTHORIZERS = "dsa:12340987"
app_domain = "RFC822-EMAIL"
address = "mab@keynote.research.att.com"
name = "J. Feigenbaum"
2. WORKFLOW/ELECTRONIC COMMERCE
E. A policy that delegates authority for the "SPEND" application
domain to RSA key dab212 when the amount given in the
"dollars" attribute is less than 10000.
Authorizer: "POLICY"
Licensees: "RSA:dab212" # the CFO's key
Conditions: (app_domain=="SPEND") && (@dollars < 10000);
F. 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"
G. 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);
H. 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 management clones
"DSA:bcd987" ||
"DSA:cde333" ||
"DSA:def975" ||
"DSA:978add"
Conditions: (app_domain="SPEND") # nested clauses
-> { (@(dollars) < 100) -> _MAX_TRUST;
(@(dollars) < 500) -> "ApproveAndLog";
};
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
"Approve" (_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"
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 from that required 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 compliance checker will
determine, based on policy and credential assertions, whether a
proposed action is permitted according to policy. The usefulness of
KeyNote output as a policy enforcement mechanism depends on a number
of factors:
* The action attributes and the assignment of their values must
reflect accurately the security requirements of the application.
Identifying the attributes to include in the action attribute set
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 principals that should,
in fact, be trusted by the application.
* The application itself must be trustworthy. KeyNote does not
directly enforce policy; it only provides advice to the
applications that call it. In other words, KeyNote assumes that
the application itself is trusted and that the policy assertions
it specifies are correct. Nothing prevents an application from
submitting misleading or incorrect 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, however, that even if inappropriate
credentials are provided to KeyNote, this cannot result in the
approval of an illegal action (as long as the policy assertions are
correct and the the action attribute set itself is correctly passed
to KeyNote).
KeyNote is monotonic; adding an assertion to a query can never result
in a query's having a lower compliance value that it would have had
without the assertion. Omitting credentials may, of course, result
in legal actions being disallowed. Selecting appropriate credentials
(e.g., from a distributed database or `key server') is outside the
scope of the KeyNote language and may properly be handled by a remote
client making a request, by the local application receiving 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 document 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 its simplest form, a KeyNote compliance checker
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
Trust management is itself a security service. Bugs in or incorrect
use of a KeyNote compliance checker implementation could have
security implications for any applications in which it is used.
9. IANA Considerations
This document contains three identifiers to be maintained by the
IANA. This section explains the criteria to be used by the IANA to
assign additional identifiers in each of these lists.
9.1 app_domain Identifiers
The only thing required of IANA on allocation of these identifiers is
that they be unique strings. These strings are case-sensitive for
KeyNote purposes, however it is strongly recommended that IANA assign
different capitalizations of the same string only to the same
organization.
9.2 Public Key Format Identifiers
These strings uniquely identify a public key algorithm as used in the
KeyNote system for representing keys. Requests for assignment of new
identifiers must be accompanied by an RFC-style document that
describes the details of this encoding. Example strings are "rsa-
hex:" and "dsa-base64:". These strings are case-insensitive.
9.3 Signature Algorithm Identifiers
These strings uniquely identify a public key algorithm as used in the
KeyNote system for representing public key signatures. Requests for
assignment of new identifiers must be accompanied by an RFC-style
document that describes the details of this encoding. Example strings
are "sig-rsa-md5-hex:" and "sig-dsa-sha1-base64:". Note that all
such strings must begin with the prefix "sig-". These strings are
case-insensitive.
A. 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 document.
B. Full BNF (alphabetical order)
<ALGORITHM>:: {see section 4.4.2} ;
<Assertion>:: <VersionField>? <AuthField> <LicenseesField>?
<LocalConstantsField>? <ConditionsField>?
<CommentField>? <SignatureField>? ;
<Assignments>:: "" | <AttributeID> "=" <StringLiteral> <Assignments>
;
<AttributeID>:: {Any string starting with a-z, A-Z, or the
underscore character, followed by any number of
a-z, A-Z, 0-9, or underscore characters} ;
<AuthField>:: "Authorizer:" <AuthID> ;
<AuthID>:: <PrincipalIdentifier> | <DerefAttribute> ;
<Clause>:: <Test> "->" "{" <ConditionsProgram> "}"
| <Test> "->" <Value> | <Test> ;
<Comment>:: "#" {ASCII characters} ;
<CommentField>:: "Comment:" {Free-form text} ;
<ConditionsField>:: "Conditions:" <ConditionsProgram> ;
<ConditionsProgram>:: "" | <Clause> ";" <ConditionsProgram> ;
<DerefAttribute>:: <AttributeID> ;
<ENCODEDBITS>:: {see section 4.4.2} ;
<FloatEx>:: <FloatEx> "+" <FloatEx> | <FloatEx> "-" <FloatEx>
| <FloatEx> "*" <FloatEx> | <FloatEx> "/" <FloatEx>
| <FloatEx> "^" <FloatEx> | "-" <FloatEx>
| "(" <FloatEx> ")" | <FloatLiteral> | "&" <StrEx> ;
<FloatRelExpr>:: <FloatEx> "<" <FloatEx> | <FloatEx> ">" <FloatEx>
| <FloatEx> "<=" <FloatEx>
| <FloatEx> ">=" <FloatEx> ;
<FloatLiteral>:: <IntegerLiteral>"."<IntegerLiteral> ;
<IDString>:: <ALGORITHM>":"<ENCODEDBITS> ;
<IntegerLiteral>:: {Decimal number of at least one digit} ;
<IntEx>:: <IntEx> "+" <IntEx> | <IntEx> "-" <IntEx>
| <IntEx> "*" <IntEx> | <IntEx> "/" <IntEx>
| <IntEx> "%" <IntEx> | <IntEx> "^" <IntEx>
| "-" <IntEx> | "(" <IntEx> ")" | <IntegerLiteral>
| "@" <StrEx> ;
<IntRelExpr>:: <IntEx> "==" <IntEx> | <IntEx> "!=" <IntEx>
| <IntEx> "<" <IntEx> | <IntEx> ">" <IntEx>
| <IntEx> "<=" <IntEx> | <IntEx> ">=" <IntEx> ;
<K>:: {Decimal number starting with a digit from 1 to 9} ;
<KeyID>:: <StrEx> ;
<LicenseesExpr>:: "" | <PrincExpr> ;
<LicenseesField>:: "Licensees:" <LicenseesExpr> ;
<LocalConstantsField>:: "Local-Constants:" <Assignments> ;
<OpaqueID>:: <StrEx> ;
<PrincExpr>:: "(" <PrincExpr> ")" | <PrincExpr> "&&" <PrincExpr>
| <PrincExpr> "||" <PrincExpr>
| <K>"-of(" <PrincList> ")" | <PrincipalIdentifier>
| <DerefAttribute> ;
<PrincipalIdentifier>:: <OpaqueID> | <KeyID> ;
<PrincList>:: <PrincipalIdentifier> | <DerefAttribute>
| <PrincList> "," <PrincList> ;
<RegExpr>:: {POSIX 1003.2 Regular Expression}
<RelExpr>:: "(" <RelExpr> ")" | <RelExpr> "&&" <RelExpr>
| <RelExpr> "||" <RelExpr> | "!" <RelExpr>
| <IntRelExpr> | <FloatRelExpr> | <StringRelExpr>
| "true" | "false" ;
<Signature>:: <StrEx> ;
<SignatureField>:: "Signature:" <Signature> ;
<StrEx>:: <StrEx> "." <StrEx> | <StringLiteral> | "(" <StrEx> ")"
| <DerefAttribute> | "$" <StrEx> ;
<StringLiteral>:: {see section 4.3.1} ;
<StringRelExpr>:: <StrEx> "==" <StrEx> | <StrEx> "!=" <StrEx>
| <StrEx> "<" <StrEx> | <StrEx> ">" <StrEx>
| <StrEx> "<=" <StrEx> | <StrEx> ">=" <StrEx>
| <StrEx> "~=" <RegExpr> ;
<Test>:: <RelExpr> ;
<Value>:: <StrEx> ;
<VersionField>:: "KeyNote-Version:" <VersionString> ;
<VersionString>:: <StringLiteral> | <IntegerLiteral> ;
References
[BFL96] M. Blaze, J. Feigenbaum, J. Lacy. Decentralized Trust
Management. Proceedings of the 17th IEEE Symp. on Security
and Privacy. pp 164-173. IEEE Computer Society, 1996.
Available at
<ftp://ftp.research.att.com/dist/mab/policymaker.ps>
[BFS98] M. Blaze, J. Feigenbaum, M. Strauss. Compliance-Checking in
the PolicyMaker Trust-Management System. Proc. 2nd Financial
Crypto Conference. Anguilla 1998. LNCS #1465, pp 251-265,
Springer-Verlag, 1998. Available at
<ftp://ftp.research.att.com/dist/mab/pmcomply.ps>
[Bla99] M. Blaze, J. Feigenbaum, J. Ioannidis, A. Keromytis. The
Role of Trust Management in Distributed System Security.
Chapter in Secure Internet Programming: Security Issues for
Mobile and Distributed Objects (Vitek and Jensen, eds.).
Springer-Verlag, 1999. Available at
<ftp://ftp.research.att.com/dist/mab/trustmgt.ps>.
[Cro82] Crocker, D., "Standard for the Format of ARPA Internet Text
Messages", STD 11, RFC822, August 1982.
[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] R. L. Rivest, A. Shamir, L. M. Adleman. A Method for
Obtaining Digital Signatures and Public-Key Cryptosystems.
Communications of the ACM, v21n2. pp 120-126. February 1978.
Authors' Addresses
Comments about this document should be discussed on the keynote-users
mailing list hosted at nsa.research.att.com. To subscribe, send an
email message containing the single line
subscribe keynote-users
in the message body to <majordomo@nsa.research.att.com>.
Questions about this document can also be directed to the authors as
a group at the keynote@research.att.com alias, or to the individual
authors at:
Matt Blaze
AT&T Labs - Research
180 Park Avenue
Florham Park, New Jersey 07932-0971
EMail: mab@research.att.com
Joan Feigenbaum
AT&T Labs - Research
180 Park Avenue
Florham Park, New Jersey 07932-0971
EMail: jf@research.att.com
John Ioannidis
AT&T Labs - Research
180 Park Avenue
Florham Park, New Jersey 07932-0971
EMail: ji@research.att.com
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
Full Copyright Statement
Copyright (C) The Internet Society (1999). All Rights Reserved.
This document and translations of it may be copied and furnished to
others, and derivative works that comment on or otherwise explain it
or assist in its implementation may be prepared, copied, published
and distributed, in whole or in part, without restriction of any
kind, provided that the above copyright notice and this paragraph are
included on all such copies and derivative works. However, this
document itself may not be modified in any way, such as by removing
the copyright notice or references to the Internet Society or other
Internet organizations, except as needed for the purpose of
developing Internet standards in which case the procedures for
copyrights defined in the Internet Standards process must be
followed, or as required to translate it into languages other than
English.
The limited permissions granted above are perpetual and will not be
revoked by the Internet Society or its successors or assigns.
This document and the information contained herein is provided on an
"AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Acknowledgement
Funding for the RFCEditor function is currently provided by the
Internet Society.