Brad Templeton's
USENET-Format Pages

Certificate FAQ

Certificate FAQ

Aren't signatures large?

A digital signature on its own using SHA is 320 bits, which means 54 bytes of "base64" style ascii printable characters. With a few other fields such as the name of the key used in the signing, expect about 75 bytes to be added to an article to sign it. Signatures can, in theory be reduced to hashes to make them smaller.

What about certificates?

A certificate is much larger. Expect 250 to 300 bytes for a compact certificate. Some mail systems have certificates that are several kilobytes. For USENET, the concept of "signature collapse" allows articles to mostly be sent with just a single, 75 byte signature from a known party. A simpler "certificate collapse" assures only one certificate need be present.

It is possible to make smaller certificates, in particular by using smaller keys. Eliptic curve cryptography is currently believed secure enough for USENET with keys in only the 100 bit (17 base64 bytes) range, and this can shrink certs quite a bit.

How do I verify an article?

An article, as posted, includes everything you need to verify it offline, except for the most toplevel key. You should already have the top level key on hand. In the rare event you don't, it will be available quickly online.

An article will have of a signature, with the name of the key that signed it. If that key is a top-level key you already have, you can simply use that key to verify the article.

If it isn't a top-level key, the article had better also have with it a certificate verifying the lower level key. That certificate is signed by a higher level key. It might be a top level one, or a middle-level one.

If it's a middle level one we repeat the process, needing a certificate that verifies each level with a key at a level above it until we get to the top. When you get to the top you have a chain of trust. The top level keyholder certified the middle-level keyholder, and so on down to the keyholder who actually signed the message.

In English, a set of certificatess looks like this:

  1. I'm Alice, and I sign this message with my key.
  2. I'm Bob, and I verify that Alice's key is XXX.
  3. I'm Mary, and I verify that Bob's key is YYY, and I trust Bob to verify people's keys.
  4. I'm your root. You know me. I verify that Mary's key is ZZZ, and that I trust Mary to certify other key signers one level below her.

As you can see, if you check all these signatures, you have a chain of trust. You can confirm that the person you personally trusted -- root, has delegated that trust to Mary, and that Mary delegated it to Bob, and Bob "met" Alice and got her key and confirmed what it is. Now you have Alice's key in a way you can trust -- and you can check that she really signed the message.

How do I keep track of all these keys?

You don't. There are no key servers. Your system only needs to have on hand the top level keys from the groups you trust for the news hierarchies you get. Those trusted people will update those keys over time with control messages -- you don't even need a connection to the live internet. Every message contains everything you need, except that highest level key, to authenticate it for any authority it wants to claim.

Isn't this immensely complex?

Actually, it's relatively simple. The powers and certificates form a tree, just like a filesystem or the newsgroup hierarchy. All we need is a language in which you can spell out attributes and permissions that will be authenticated. Then, when an article wants to do something that needs authentication, you just test that every certificate in the chain to the root permits it. A simple "AND" of the certificates.

This simple rule lets you create an arbitrarily detailed authorization structure. You don't have to -- it just allows it. In reality it sits at the level of complexity and simplicity the users demand.

Isn't this authorization language complex?

The authorization language can get complex if you want it to. But it's going to be simpler than any of the alternatives, which tend to be configuration files somehow mapping the permissions granted to some representation of the IDs or keys of those granted them.

If you want an ability to say that only somebody with a given key can approve articles in moderated group X, you have to express it somewhere. Whether in a config file, or code that fetches from a database, or right in the certificate itself, you can't get away from it.

How do I get the top level keys?

For the system to work, a variety of keys must exist that everybody who will get an article already has. But the number of such keys is small, and even over the scope of all the subnets and hierarchies of usenet, the number any one site would have to keep track of is likely to stay below 100, and even below 1000 for the whole net.

If people were willing to trust one party there could be just one top level key. But that's not a good idea, and not likely to happen. The actual number will strike a balance.

The file of such keys will be readily available by FTP or HTTP. In addition, the keys would be "broadcast" regularly in a special newsgroup. Your news server would listen, and store the keys from the broadcasts. The broadcast messages, and FTP files, would themselves be signed.

Signed by who?

Well, they might be signed by somebody you really trust to manage this task for you. Somebody you've dealt with personally. They would be signed by several people -- lots of people, so that in the pool there is somebody everybody trusts. Or there might be a voting system.

What's a voting system?

In such a system, many trusted people sign truly powerful (root) keys, or the repuidiation of truly powerful keys. In order to create a new powerful key or revoke one, your system demands that a majority of the trusted people sign the message. Thus power is not concentrated in the hands of one person, but in a group. And you don't have to trust the vote -- it's recorded right in front of you.

What's a root key?

A root key is a key that is all powerful, or at least all-powerful within a section of the net, like a hierarchy, or subnet. You trust it with the power to do everything, and most importantly the power to delegate that power to others. You need to install at least one root key, trusting the owner of it with everything you want to delegate. (If you don't want to delegate anything, you can of course not trust outsiders, or trust all of them -- this is your choice.) A root key is usually also a top level key.

What's a top level key?

A top level key is a key that everybody (who sees it) is expected to have on hand. A top level key doesn't have to be a root key. A top level key has in it an attribute saying "Keep me" to remind you that you should store it locally for future use when you see it.

Top level keys will tend to be used only for root keys (which themselves are very rarely used) and for "certificate collapse."

Every article on the net you want to verify must have within it a chain of signatures and certificates leading to a top level key. Once it does, everybody can verify it.

What's signature and certificate collapse?

The example given above with 3 certificates is bulky. Probably almost a kilobyte is added to that article to allow it to be verified.

A certificate collapse machine is a machine with a top level key. The key is also fairly high-level, close to root in power. The people who run it must be well trusted, and must keep it secure.

This machine can be fed a set of certificates. It checks them all for validity up to a root that it trusts, and writes a new certificate which is an "AND" (intersection) of the powers in the existing chain. It hands that single certificate back to the user, so they can use something compact, and not a chain of certifictes.

A signature collapse is deeper. Here, a machine relaying articles (or injecting them) checks the signature and all certificates on the article for validity. If it all checks out, the system signs the article with its own powerful key, in effect saying, "everything in this article checks out." (This machine must be trusted by all its downstreams. But then, that's the way USENET works right now, with nothing to authenticate the trust.)

Then it removes all the other signatures and certificates. You don't need them because you trust it to have done this other checking. When you get it, you don't see the original author's signature, but you have proof from somebody you trust that the article was properly signed and verified.

Now the article moves around the net with just one 75 byte signature on it.

Chances are that certificate collapse would be done only for the typical orindary certificate used for posting and cancel. Special messages, such as special control messages, should probably have their original keys preserved. In particular, the permissions required for these special messages may not reside within the collapse server's key, so collapse would not be possible. The special users who are allowed to issue special control messages would guard their keys more carefully, and use them directly to sign any messages.

In fact, ordinary users need not be aware of this most of the time. Their own certificate authority, if it happens to be online, can ask a higher CA to do this collapse right when the user asks for a certificate. They just return the certificate by E-mail via the higher level CA's collapse forwarder.

What about revocation?

If a key is compromised the key can be revoked with a special control message which announces the key is revoked. This is signed by a high level key that has this power -- or it can be signed by the very key being revoked if the key has that attribute. This means the key is no longer valid.

While ideally all sites keep a list of revoked keys along until the underlying key would have expired, this is not strictly necessary. Instead, the collapse servers would keep around such larger lists. If they, or other daemons like them see a message with a revoked key, they issue a signed cancel for it, rather than propagating it. It disappears. In fact, this allows a retroactive revocation of a key, if necessary.

Powerful keys, the kind that can do more than just post, are more important. If they are revoked, the revocation would be broadcast over the net, signed by a higher level key. All sites should remember that until the underlying key expires.

What about expiration?

When you get a certificate, it has an expiration. This is necessary to avoid having to keep around revocation data forever, and so that old keys can't suddenly come to life.

People using keys need to renew them before their expiration date. This renewal can be simple though. Getting an E-mail address key is simple to start with, and just involves mailing a request for one. Renewal can work the same. In fact, renewal of even more powerful keys can still be done by E-mail, as long as there is a challenge with some delay to assure the proper owner is aware of the renewal.

I expect ordinary keys might be set up to last 6 months to a year.

How do we trust all these people?

In the past, USENET worked by trusting everybody on the net. Anybody could post, as anybody. Anybody could cancel. Anybody could do a control message -- until it got so bad that people moved to not executing any newgroup or rmgroup control messages without manual oversight, in effect trusting nobody. Moving to a verified system simply reduces the number of people trusted.

It does not mean trusting only one person, though. These systems are simply a way to delegate trust. One can manage all permissions on one's news system, or delegate it all away.

I have written a description of how this might work.

How can we get a small set of people everybody trusts?

This is not a new problem. Almost all systems rely on this. The whole internet depends on the DNS, and we all trust the root servers to provide us with accurate DNS. And the consequences of bad DNS can be serious system invasion and hijacking, not just unauthenticated USENET operation.

Other distributed nets such as Fidonet etc. have relied on trusted parties to form the foundation.

In addition, there doesn't have to be just one set of parties trusted by all. It's easy to break down on a per hierarchy, per newsgroup and per subnet (distribution) basis. If you are only posting to a given hierarchy, you only need a top level key known by people who get that hierarchy. If you are only posting to a given subnet, you only need a top level key that works within that subnet.

Indeed, if you are only posting to a specific newsgroup, you only need a key known to people who get that newsgroup. For example the moderator of a newsgroup might actually have the top level key, if they can convince every site to keep their key. But chances are it's easier for the moderator just to convince somebody trusted by most of the net to certify their key. For the system to really work, it does need some people that almost everybody is willing to trust. But this is normal -- and in fact USENET itself depends on DNS and phone companies and other common factors already.

Who gets these root keys?

One way to make sure that we can get a set of people with top level keys who will be trusted by almost all sites is to not put power in one entity. Instead, a group of independent people would hold the master keys. Respected people who built the net, wrote the major software, designed the systems, forged the major links.

Those people could then, together, create, and revoke, the powerful keys that do the real work. Their keys would not do the real work. Instead, they would just vote on it.

Imagine there are 20 such people. You could program your system to accept a new powerful key only if any 12 of the 20 sign it. For a revocation, you might ask for a different number.

The keys handed out this way would expire quickly. This means that having "power" is something that would only continue at the pleasure of this "board of directors."

It's up to the site owners -- who are the owners of USENET -- to decide on a board of directors they like. Ideally there's only one board, but once again, it can be broken down by hierarchy, subnet or even group.

In fact, there would probably not be a master board at all. Chances are boards would be limited to hierarchies. Right now one person is trusted by almost everybody to issue newgroups, and the boards could all delegate the same person -- or different people.

Now all these complex systems may not even be necessary. There might not even be any harm in having one person hold the master keys for all of USENET, with proper delegation of course. Because it's important to remember that these are not actually strictly the keys to power -- they are power delegated by the site owners, who hold the true power. Site owners can turn off any key's power on their own site any time they want. Anybody who stops acting in the interests of site owners would lose their confidence, and lose any powers they might think they had.

Accepting a root key is really like issuing a password -- it can be taken away at any time. The real "superuser" password for any site stays with the site admin.

What if somebody wants to do something the top keys doesn't like?

Anybody can create a key of their own and ask site admins to install it and endow it with powers. If somebody wants to create a new group against the rules, they just have to convince sites to take it. Pretty much how it worked in the old days -- except people can't do it without your permission.

How about an example?

To use this system, you define something you want to be a privileged operation. Let's say posting an article to a moderated newsgroup. That ability should belong only to the moderator. This starts by the group being marked moderated. In the old system there was no security on that, so now the group must be marked "moderated-and-signed" meaning that no posting is allowed in it that is not signed by the moderator.

Your news software would come pre-installed to trust a board of custodians as set up by the author of the software. Just like your DNS server comes set up to use and trust a set of root servers. You can change this list, of course.

Step 1, Install.

Next you would install the "latest" master keys issued by the board of custodians. These keys, short lived, would be refreshed by control messages from time to time. You could just get a feed for a while and get them (they would go out at least once a day) or you could download them if you have a way to download. You don't need to check them, your software knows the keys of the board of custodians, and it confirms them and installs them. It checks that for each key, a majority of the custodians signed it. Once you have these keys, you need to nothing further, you are set up to fully authenticate. The only reason for you ever to change things after that would be to customize things. You might want to install your own master keys, revoke those of the board of custodians your news software liked, or install new ones for a new hierarchy not approved by them.

Step 2, Moderator gets certificate, and signs with it.

The board of custodians probably asked for a volunteer to look after a hierarchy like "rec". That volunteer is given a master key that works only in "rec." Expressed in a language that might be written as "if( group is rec.* ) grant *" to grant all powers when the group starts with "rec." Of course, there are many syntaxes for such a language.

Now I'm moderator of rec.humor.funny. So I would ask this person handling "rec" to issue me a certificate for my key. This certificate would say I am granted the "moderator" authority on that newsgroup. It lists my public key and my authorizations. It might say something like: "if ( group is rec.humor.funny* ) grant 'moderator'"

To approve a post, I sign the post and add my certificate, and the "rec" manager's certificate both. The rec manager's certificate points to a master key that you are expected to have.

Step 3 You test

So you see a post in rec.humor.funny. Because it is now marked as moderated and signed, your news server demands that any article in it be signed by somebody with moderator permission for the group.

You look at the certificates, and see two, plus an implicit third one for the root key you have in your cache. You simply test them all.

My moderator's certificate is explict, and says to grant me moderator power in the group. That's good. You see it is signed by the rec manager's certificate. You check that, and you see that since it grants all permissions in "rec" it also grants moderator permission in rec.humor.funny, so that's good. Finally you might check the root certificate you had in your cache. It grants all permissions everywhere, so of course it passes.

Is this bulky? Well, there is a way around that. I might take my moderator's certificate and had it directly to a computer run by the board of custodians. That computer would check it out and combine my certificate with the "rec" manager's certificate. The result would be the same, but now signed by the board's root key, which you have in your cache. So now I can moderate with this new "collapsed" certificate and you don't even need to check the rec manager's certificate.

Turns out that the collapse is only needed for the most common actions, namely posting signed articles or posting to moderated groups. Everything else is so rare that you might as well keep the whole chain in the article, bulky as it is, to see the trail.