Brad Templeton's
USENET-Format Pages

SPKI based USENET Certification Permission Language - Preliminary

SPKI based USENET Certification Permission Language - Preliminary

This is a preliminary document for a USENET certification language. It is based on the draft certificate language SPKI, currently defined in raft-ietf-spki-cert-structure-05.txt, which can be found at the SPKI site.

This is an alternative to a certificate language just for USENET that I drafted.

Another certificate system being drafted is KeyNote or RFC 2704. This system has some working beta code. It also has bulkier-than-necessary certificates, but again there may be fixes for that. The speed of its interpreter is unknown.

SPKI is a general certificate system mostly suitable for USENET certificates. The certificates are a little bulkier than necessary, and offer more features than USENET requires. USENET would probably take a subset of this language, though systems could implement the entire system. In addition, some variations of the system may make sense.

For USENET, only one signing system should exist at the start. That should be the use of SHA-1 as the hash, and DSS for the signature. DSS generates a 320 bit signature. (Two 160 bit numbers.)

Note: This document is extremely preliminary. It's not complete nor would it be possible to build a system from it.

Certificates on USENET grant permissions to the owners of the keys certified by providing tagged S-expressions in the SPKI format. Certificates do not necessarily certify a user's identity, rather they certify some attribute of the holder of the key, or some permission granted to the holder of the key.

However, the most common certificate, an E-mail address certificate, may be thought of as certifying something that is like an identity. But it really certifies ownership of (or access to) an E-mail address, and thus the ability to post using that E-mail address in the From line or other header lines, to cancel messages which used that address in such lines, and to use a segment of Message-id space based on that address.

Most other certificates would certify not an identity but an authority. Such as "The authority to approve postings in a moderated newsgroup X" or "The authority to issue newgroup messages in hierarchy Y" and so on.

Space constraints

USENET messages are broadcast. They are transmitted hundreds of thousands of times to various sites, and stored on hundreds of thousands of disks. From there they are transmitted to millions of users (though the users probably have no interest in the signatures and certificates.)

In a world of signed messages, by far the most common signature/certificate use would be a basic E-mail address certificate, used for a cancel message or eventually an ordinary posting. This should be kept to an efficient size. In particular, such postings should include only one certificate, signed by a "high level" or CA with what is termed a "keeper" key. (One which all sites are expected to keep in local cache or "ring" of keys.)

The signing of ordinary messages and single-user cancels is referred to here as "Basic" signing and a "Basic" certificate.

For other uses -- special control messages and even to some extent moderated groups, size is less of a constraint, and multiple chains of certificates up to the high-level keeper key are possible. Such signing uses "Advanced" certificates.

Because of space constraints, particularly on Basic certificates, the use of commentary information not necessary to authenticate a particular message is discouraged. Indeed, it is expected that parties will keep more than one certficate around, and use the most appropriate one, rather than having only a master certificate certifying all their attributes. In particular, holders of Advanced certificates should usually keep both their Advanced certificate and a Basic certificate, and use the Advanced one only when issuing a message that needs it. Posting systems should attempt to understand the various certificates available to the user and include the most compact one that authorizes the message to be posted. Multiple certificates can certify the same key, with different attributes about it.

In order to provide commentary information on certificates, it is expected that web sites may be available where one can look up additional publicly available information about a keyholder based on the key. It is up to keyholders to register such information.

SPKI Issuer

An SPKI certificate identifies its issuer in the issuer component. In SPKI, this is often a hash of the issuer's public key, as well as optional information about locating the key known as an issuer-loc. However, for USENET, it must never be necessary to fetch a key from some remote location, so generally such information should not be included in Basic certificates.

SPKI Subject

The subject of a certificate is the key being certified and its holder's attributes. In this place, they key being certified itself MUST be present. Sites are not expected to have to fetch the key to verify a message. The use of a hash, or a "subject-loc" term, is discouraged.

The "subj-thresh" element is supported, though I am as yet unsure why this feature is implemented here, rather than as a tag. The most powerful keys in USENET would be implemented using the subj-thresh element, so that their actions require several signers, all with a powerful subj-thresh key.

Other subject forms are of limited use on USENET.

Version

Unless the version number has changed from the base version, this tag should not be included.

deleg

The deleg field should generally be used only in Advanced certificates. It is used in the keys of certifiers themselves, allocating to them the power to write certificates for others. As with such systems, when a chain of certificates is present, all certificates in the chain must be authorized to grant a particular attribute or authority.

valid

The valid fields, not-before and not-after define the lifetime of a certificate. Normally only the not-after field would be used, specifying when a certificate expires.

Tags for USENET

The following tags and tag structures apply to USENET.

Patterns

The language supports two types of patterns.

<sim-pat>
A simple pattern language using '*' to mean all strings. In addition, the "|" character allows the selection of alternates, any of which may match. "yes|no" matches either "yes" or "no". A sim-pat may also include a pattern preceded by a "!" character. This indicates the pattern must not match.
Regular Expression <regpat>
A full regular expression as matched by the popular Unix program "egrep" or the popular "regexp" package by Henry Spencer.
Anchored regular expression <anchpat>
A regular expression with an implied '^' at the start, which must match the beginning of the string being tested. Note that an anchored regexp can be turned into an unanchored one by placing '.*' at the beginning.
Fully anchored regular expression <fullpat>
An anchored regular expression with an implied '$' and the end, so that the entire expression must match the entire string being tested.

Modifiers

The following tags modify other tags. Thus they include within them an S-Expr of other tags. Modifiers are of course also inherited from the certifer, if their certificate was based on tags with modifiers.

<group>

<group>:: "(" "group" <groups> <tags> ")
<groups>:: <sim-pat>

A group modifier means the tags only apply within the newsgroups matching <groups> which is a <sim-pat>. Normally this is used to grant a permission only within specified groups. However it may also simply exist to grant a permission in groups that have specified they need a specific certificate naming the group to perform what is ordinarily a non-privileged operation.

Normally this applies to the groups in which the message is posted. However, for control messages, this modifier also applies to groups affected by the control message. (A control message is posted to some newsgroups but may contain other groups named in the message, or may affect messages in other groups.)

(group "comp.*" (control "newgroup"))

bestows the right to issue "newgroup" messages in any group matching the "comp.*" sim-pat.

<dist>

<dist>:: "(" "dist" <distributions> <tags> ")
<distributions>::<sim-pat>

A modifier of this form indicates the permission is valid only at sites in a subnet matching the (sim-pat) pattern. Typically that means sites which belong to a distribution which matches the pattern, however this can also be used to set up any sort of administrative group for granting powers.

(group "alt.*" (dist "knights.*" (control rmgroup)(control newgroup)))

Establishes the permission to issue newgroup and rmgroup messages in the alt hierarchy, only at sites that are in any subnet matching "knights.*"

<control>

(" "control" <anchpat> ")

Takes as argument which is an anchored regular expression. Bestows the power to execute any control message matching that pattern.

A special rule for this tag: If the control message affects a particular newsgroup, then that newsgroup must match any group modifiers on this tag. Normally, the group modifier affects the groups the message is posted to.

This means, for example, that for a cancel message, the original message's groups should be retrieved, and the cancel executed only in groups that match the group modifiers, if any on this tag.

(group comp.* (control "newgroup "))
This keyholder can issue newgroup control messages only in the comp newsgroups.
(group news.announce.newusers (dist moose (control "cancel ")))
This keyholder has the right to issue cancels of messages that appear in the newsgroup news.announce.newusers. However, only sites that consider themselves in the "moose" subnet should execute this cancel.
(group clari.* (control "checkgroups"))
This would allow this keyholder to issue checkgroups that describe only groups in the "clari" hierarchy. Any groups not in that hierarchy contained in the checkgroups message would be discarded.
(group foo.bar (control "."))
This user is given somewhat godlike powers over the foo.bar newsgroup -- they can issue any control message there, cancel any message there, adjust named articles there, etc.

cancel

This special tag takes a regexp which describes a message-id, including angle brackets. The keyholder may cancel any message-id which matches that pattern.

sitecancel

This special tag takes a string argument which is a site name. The keyholder may cancel any message for which the specified site is the article's injection point, as defined in the syntax for the "Path" header.

relaycancel

This special tag takes a sim-pat argument which is a site name. The keyholder may cancel any article which has a "Path" entry which matches the sim-pat, including the injection site.

User

Takes a set of comma-delimited E-mail addresses as arguments. Bestows the power to post, cancel and otherwise use the provided E-mail addresses in headers where such are used. Commonly the addresses will be the result of macro expansion.

(User "brad@clari.net")

Keep

Indicates that this key should be kept locally, as it will be frequently used. Common for certifier's keys.

Head

Takes as an argument a regular expression matching a header line in an article. This general header can accomodate almost all future generated headers that require authorization. Most other items are special cases of this. The expression must match the header line entirely.

(group comp.foo.bar (Head "^Magical:.*$"))

Gives the keyholder the ability to use the "Magical" header in the comp.foo.bar newsgroup. It is presumed that if this header has special powers, any software that implemented those special powers would check to see that the signer of the message is able to use this header.

Note that if there is a specific tag devoted to the header (such as the Control tag) then the Head tag should not be used, and can't be assured to grant permission.

Name

Takes as an argument a regexp matching article names this keyholder is permitted to use in a "Control Name" message

(group rec.humor (Name faq))

The holder of this certificate is allowed to issue "Control name * faq" messages in the newsgroup rec.humor. This means they can set, delete or add to the FAQ file.

Volume

Takes a numerical argument, indicating a volume of articles per hour the poster is allowed to post. Needed by users who generate posts using autoposting programs, such as those who post FAQs and stats. Other users may be subject to posting volume throttles limiting them to what a typing human being would be likely to need to post. Programs that check for or throttle high posting volumes would check for such an attribute in the signer's certificate, and alter the limits for such posters. Most sites wouldn't do this checking, but instead would leave it to special checkers.

(Volume 9999)

Effectively gives this keyholder the ability to post as fast as she wants.

Realname

Takes as an argument a quoted string which is certified to be the keyholder's real name. Takes optional 2nd argument indicating a name for the level of security in that certification. The default is the keyholder appeared in person with adequate photo ID to a certifying agent. The same "%" macros used in the "U" keyword apply here, however only the comment portion of the E-mail address line is inserted.

(Realname "Brad Templeton")

Indicates the keyholder is certified to have that real name. On USENET, it may be unlikley that real names are commonly certified, but some newsgroups may wish this.

Note that other tags from general SPKI may be better suited to certify real names and other such attributes.

CancelAs

Takes a pattern, may cancel any message from a user matching that pattern.

ActAs

Takes and argument which is a regexp, typically one that matches a particular domain. Provides the power to act as any address whose address matches the pattern. (Ie. to act as though the User tag is set to that user, and thus to post, cancel, supersede or replace as that user, plus use that user's message-id space.)

As a special case, if in a certificate with the "deleg" field, this keyholder can issue "User" certificates to userids that match the pattern.

An alternate might be a Domain certificate which doesn't use a pattern but conveys all things domain ownership might -- ability to act as any user in the domain, to use and cancel in the domain's message-id space, and to issue user certificates within the domain.

Post

Indicates the keyholder can post to the groups specified in their modifiers. (Always used with modifiers) Works even if they are moderated. This allows moderators the power to grant some people the right to post directly.

Approve

Allows the keyholder to approve posts. Generally used with modifiers to specify a group. Sites should check postings in moderated groups for either a "Post" attribute or "Approve" attribute by one of the signers.

Revoke

Grants the power to issue a revocation message for the certified key. Users may not wish this power by default. If their private key is stolen, the thief can act as the victim. It may be that the denial of service attack, where the thief revokes the victim's key, is worse than other impersonations. Users can always revoke by contacting a higher level certificate owner -- they need to do that to get a new certificate after revocation anyway. Thus this power is not normally granted.

Revdigest

This keyholder can issue "revocation digest" articles, which list the 160 bit secure hashes of keys that have been revoked and how long the revocation records should be kept for. Sites must listen for these digests and store a local database of revoked keys. Any key used to check a signature should first be looked up in the revoked keys database, and not used if found there.

The list of revoked certificates/keys should contain the identity (certificate) of the revoker, because when the first attempt to use a revoked key arrives, systems need to check that the revocation was actually authorized. For example, one might check that the revoker is authorized to revoke keys of the certifer.

All keys authenticated by a revoked key become invalid.

Genrevoke

Like the Revdigest, but may revoke any key, including keys not certified by the issuer of the revocation digest. Can't revoke "root" keys, however.

RootRevoke

This keyholder can vote to revoke a ROOT key. Normally this will only be issued in a sub-thresh form, with at least 3 signers required to revoke such a key. Once a root key is revoked all keys issued under it are invalid.

XPost

This keyholder has the power to violate crossposting restrictions within the groups and subnets specified for this header. This presumes these groups have crossposting restrictions.

Moderator

Defines the common subset of powers for a moderator. Namely:

Post
Approve
Limits none
Volume 9999
Name
Control cancel
Control newtopic

It is expected that any other generally accepted moderator powers SHOULD be added to this group as they are defined.

Limits

With the special argument of "none," the keyholder can violate all policy rules for the newsgroups and other parameters specified. Arguments will refer to specific rules and their own parameters to define new limits. These limits are not defined, they are up to the rules checkers, which must register their names is a rules registry to keep them unique, but otherwise are free to act as they wish. It's expected many groups will put on limits on article size, article types, use of anonymity.

(group "comp.*|rec.*" (Xpost))

Allows the keyholder to do crossposts among all of those groups.

deleg

The deleg attribute (a higher level field in SPKI, not a tag) grants the power to grant certificates delegating the powers in this certificate.

SPKI decided not to allow levels of delegation. There is some debate on this.

Count

For anonymous identities, indicates the number of identities the keyholder has acquired to the best of the knowledge of the certifyer. Note that this is not mandatory, but it is presumed that some systems which grant anonymous identities will be more palatable to some users if this count is present, and accurate. Users would use it to perhaps trust more a user's only (#1) anonymous identity than their 100th.

Root

This key has the power to issue any certificate at all. Itself it has no powers, it uses powers by creating certificates for those powers.

All

This certificate has all powers -- usually present with modifiers for a subnet or set of newsgroups. Not sure if we need this independent of the Root tag.

Inheritance

When one keyholder (who has the "deleg" tag) delegates power to another by signing a certificate, the two certificates must be combined together, unless the higher level one is a previously transmitted "keeper." Any command executed using the delegates certificate must be legal for all certificates used to authorize it, ie. the AND of the permissions test for each certificate. This prohibits delegation of powers a certifier never had.

This means that one certificate in the chain must have the "All" tag. However, this could be one the local site administrators installed, and not an external certificate.

As a special case, a ROOT certificate is not tested in combination with certificates it signed, though most chains will end up at a root certificate.

How it all works

Say a newgroup message comes in. As with any article, you order the certificates based on how they reference one another, leading to the top one that you recognize. For the signer that you recognize you will need to fetch their own certificate from your own database. Chances are that there, you have appended it with any certificates used to verify it. You will also have stored a list of trust certificates for your site, most notably some that trust one or more commonly used root keys.

Then you verify all the certificates down from the highest one that you haven't already verified (the ones in your database are already verified). Assuming they all verify, you will have developed a series of S-expressions in the certification language, the final one verifying the key of the signer of the actual message. Using that verified key, you can then test the signature on the actual message to assure it is good. This list of certificate strings includes certificates fetched from the local database.

If there is anything invalid, you probably will reject the message. You must also assure that no certificate has expired or been revoked. To test revocation, you must have your own database of revoked keys (or simply secure hashes of those keys to keep it compact.) Any higher level certificate must have the "deleg" attribute with enough levels of authority to issue the certificates underneath it.

You can then use this list to test if the signer is authorized to perform the operation in question. The test must pass for every certificate in the chain. At the end you have a list of permissions for the actual poster, and the poster's key. You check the article using the poster's key -- if it checks out that, poster really sent it out.

For an ordinary message to an ordinary newsgroup, all you are likely to test is whether the user is authorized to use the address on the "From:" line or similar lines. For this test, you will chain downwards, testing for either a "User" attribute, or an "ActAs" attribute that matches the from line, or of course the "All" attribute. Any attribute must be tested against its modifiers -- all modifiers must match parameters from the article.

(Thus if the top level certifier has permissions on comp.* and the middle certificate grants that power on *, permssions remain only on comp.*.)

For a more complex operation, like a "newgroup" control message, you would check that every certificate has either the "all" attribute or a "control" attribute whose pattern matches the control line of the message. Once again, the modifiers on these attributes must also be tested.

If all certificates test positive, you execute the command, if not, you discard it.

Examples

User

Most people would get a certificate for their name. For example,

(sequence
(public-key (dsa-sha1 (n lots-of-bytes-with-user's-public-key)))
(do hash sha1)
(cert
(
(issuer (hash sha1 |160-bit-hash-of-certifer's-key|))
(subject (hash sha1 |160-bit-hash-of-public-key-above|))
(tag
	(User "brad@templetons.com")
)
(not-after "1999-12-15_00:00:00")
)
)
(signature
(hash sha1 |54hash-of-certificatexRTSmmA==|)
(hash sha1 |+ghash-of-certifer's-key/3hQ==|)
|xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx|)
)

This allows posting, reply-to and cancel as this user. It also would permit use of a section of message-id space based on the E-mail address.

For all future examples, we shall show only the "tag" section of the certificate. The structure of the rest does not vary.

Site

A site like aol.com might get a certificate of the form:

(ActAs "^.*@.*\.aol.com$")

This would allow this keyholder to post, cancel or otherwise act as any user at the AOL.com domain. This key would actually belong to a server at the aol.com site, which would verify its own users using the site's own security and validation method, and sign their articles. This would avoid any need for the individual users to have their own keys. Such certificates would only be handed out to sites that had decent internal security. Nothing would prohibit AOL users from getting their own certificates, but the main AOL server would still have a key that let it act on the net as (and we presume for) any AOL user.

Moderator

A moderator might get a certificate that allows "All" but with a modifier of the moderated group. This is quite simple, but grants the moderator certain powers you might not want to grant, such as the ability to forge postings from other users.

A better scheme would grant the moderator specific powers.

  1. The ability to issue any control message, including cancel, in the moderated group: (control ".*")
  2. The ability to "approve" postings in the group: (Approve)
  3. The ability to post in the group: (Post) (This is redundant with Approve, but useful to delegate.)
  4. The ability to delegate these powers. (Delegation tag)

The resulting certificate, including the required attributes, looks like this:

(group foo.moderated ((control ".*") (Approve) (Post))

Certificate Collapse

When a user receives a certificate, they could include a chain of certificates to show their authority. However, as this is bulky, it is strongly recommended, and may be required, that the user contact a daemon run by a high-level key and arrange for certificate collapse.

This deamon will check the chain of certificates, combine them together and issue a new single certificate reflecting the resulting authorities and signed by its high-level key. Its key will be a "keeper" key, broadcast regularly and expected to be known by all sites.

The resulting single certificate will be used by the user in all postings, rather than the chain, to save everybody space and computation time.

For rarely used certificates or postings (such as newgroup messages) it may make sense to simply use a chain rather than doing the collapse. This should be acceptable. Common postings, namely user postings, cancels and moderator approvals, should use a single certificate. Indeed, the moderators of a few high-volume groups may even get a keeper key which will allow them to sign articles with no certificate.

Relationships

When a certifier certifies a keyholder, it is a good idea to consider recording or including some information about why the certifier came to trust the keyholder. This allows others to judge that trust. It is hoped that SPKI will provide any mechanisms needed for this.

For example, one might want to tell a User certificate written due to an E-mail challenge response (where all that is certified is that the keyholder was able to, at the time, read or intercept the mail of the specified address) from a user certificate written because the CA met the keyholder in person, and examined their passport.

Macro Expansion

To keep certificates compact, it is worth noting that the thing being certified, commonly an E-mail address, is almost always present elsewhere in the article, most commonly in the From line. It makes sense to provide a macro facility so that one can place a string like "%F" in the certificate, and have it expanded out to become the E-mail address from the From line before checking or using the certificate.

Missing Issues

Revocation messages and forms

Subset revocation, how to grant a power globally but exclude it within a subset -- ie. can post to anywhere but not in a specific group, or revocation within a specific subset or group. This may be more complexity than we need. This may be more complexity than we need.

Summary of SPKI issues

Here are the things I would change about SPKI to make it more adaptable to USENET:

Compact Forms

As we will be sending these certs 300,000 times to 300,000 machines and then off to users, it is ideal if they are slightly more compact. To that end:

  1. A simple namespace should exist whose scope is either a sequence or perhaps a "message", and that namespace could be used instead of a full MD5 (22 bytes) or SHA1 (27 bytes) hash of the indicated entity. One could simply refer to other elements by a single letter in most cases. However, if these references are in signed areas of certificates, they would of course have to be replaced before checking or signing a certificate. This might be considered a macro function in order to save space.
  2. If hashes are to be used, obviously a 128 bit hash like MD5 is better than a 160 bit hash like SHA1. However, since DSS uses SHA1, there is a certain desire to have only one hasher be required.
  3. The public key being signed should simply be present in full form in the "subject" field, as part of the certificate, not in its own special element.
  4. The signature should not repeat the hash being signed. The signature should simply be the signature, with the signer's key implied from the "issuer" field and the hash being signed implicitly the hash of the certificate in question.
  5. To simplify the use of the private namespace, should the issuer perhaps not be part of the signed section of a certificate?

Deleg

The ability to delegate is just another tag. It can be something that surrounds other tags, indicating they can be delegated. As such, one might have a certificate that can delegate certain things but not others. In any certificate chain, all certificates except the last must both have the given attribute and have it delegatable. If all tags are delegatable, then all tags would appear in an list inside a delegation tag.

Expiration Dates

These also are just another tag that modifies other tags. It's possible that different attributes might expire at different times, but while that's not likely, I think there is no need to give these special status.

They should also be expressable in more complex forms. First of all the time of expiration should be optional (default midnight GMT) and perhaps even the day (default 1st of month, midnight GMT).

To compactly express a validity range, it might make sense to provide the expiration date and then a delta which is a number of days (a possibly floating point number) to subtract from the expiration date to get the start date.)