A crypto standards manifesto, version 0.1

[ciphergoth]

Update: Anonymous comments must be signed! I've made a couple of exceptions to this policy, but I may stop unscreening comments that don't have any kind of name at the bottom.

My current plan to change the world involves writing a manifesto for a proposed mailing list to work out crypto standards that actually work and stand a chance of getting widely adopted in the open source world. This is essentially version 0.1.5 of that rant, and may contain some inaccuracies or overstatements; I look forward to your comments and corrections.

Currently there are four crypto standards that see any real use in open source land; in order of deployment, they are:

• SSL/TLS
• SSH
• OpenPGP/GnuPG
• IPSec

These are the best examples of good practice that we cite when we're trying to encourage people to use standards rather than make it up, and all of them fail to be any good as a practical, convenient basis by which people writing open source software can make their software more secure through cryptography. All of them suffer from three problems; in order of increasing severity

• They are all designed long ago, in three cases initially by people who were not cryptographers, and are difficult to adapt to new knowledge in the crypto world about how to build good secure software. As a result, deprecated constructions for which there are no good security reductions are common. They are also generally far less efficient than they need to be, which would be a very minor problem if it didn't put people off using them.
• In every case protocols and file formats introduce far more complexity than is needed to get the job done, and often this shows up as complexity for the users and administrators trying to make them work, as well as unnecessary opportunities to make them insecure through misconfiguration.
• But by far the worst of all is the parlous state of PKI. This of course is something I've ranted about before:
  • SSL's dependence on the disaster that is X.509 makes it insecure, painful for clients, and imposes the ridiculous Verisign Tax on servers, as well as making it very unattractive as a platform for new software development.
  • SSH occasionally shows you a dialog saying "you haven't connected to this server before, are you sure?" I'm sure someone's going to tell me they actually check the fingerprints before connecting, but let me assure you, you are practically alone in this. I can't even share this information across all the machines I log in from, even if I use ssh-agent. The situation for authenticating clients to servers is slightly better, but still involves copying private keys about by hand if you want the most convenience out of it. It makes you copy whole public keys rather than something shorter and more convenient like OpenPGP fingerprints. It certainly doesn't make use of the basic fact that keys can sign assertions about other keys to make life more convenient.
  • OpenPGP's authentication is based on the PGP Web of Trust, which is all about binding keys to real names using things like passports. As I've argued before, this is a poor match for what people actually want keys to do; it's a very poor match for authenticating anything other than a person.
  • IPSec is also tied to the X.509 disaster. It is also so complex and hard to set up that AFAICT most IPSec installations don't use public key cryptography at all.

Perhaps the key management problems in all these applications can be pinned down to one thing: they were all designed and deployed before Zooko's triangle was articulated with sufficient clarity to understand the options available.

It's worth noting one other infuriating consequence of the PKI problems these applications display: none of them really talk to each other. You can buy an X.509 certificate that will do for both your SSL and IPSec applications, if you're really rich; these certificates will cost you far more than a normal SSL certificate, and for no better reason than that they are more useful and so Verisign and their friends are going to ream you harder for them. Apart from that, each application is an island that will not help you get the others set up at all.

I've left out WEP/WPA basically because it's barely even trying. It should never have existed, and wouldn't have if IPSec had been any good.

---

I'm now in the position of wanting to make crypto recommendations for the next generation of the Monotone revision control system. I wish I had a better idea what to tell them. They need transport-level crypto for server-to-server connections, but I hesitate to recommend SSL because the poison that is X.509 is hard to remove and it makes all the libraries for using SSL ugly and hard to use. They need to sign things, but I don't want to recommend OpenPGP: it's hard to talk to and the Web of Trust is a truly terrible fit for their problem; on top of which, OpenPGP has no systematic way to assert the type of what you're signing. They need a way for one key to make assertions about another, and we're going to invent all that from scratch because nothing out there is even remotely suitable.

Monotone has re-invented all the crypto for everything it does, and may be about to again. And in doing so, it's repeating what many, many open source applications have done before, in incompatible and (always) broken ways, because the existing standards demand too much of them and give back too little in return. As a result, crypto goes unused in practically all the circumstances where it would be useful, and in the rare case that it is used it is at best inconvenient and unnecessarily insecure.

I don't believe that things are better in the closed source world either; in fact they are probably worse. I just care more about what happens in the open source world.

We can do better than this. Let's use what we've learned in the thirty-odd years there's been a public crypto community to do something better. Let's leave the vendors out, with their gratuitous complexity and incompatibility as commercial interests screw up the standards process, and write our own standards that we'll actually feel like working with. We can make useful software without their support, and it seems in this instance that their support is worse than useless.

A good starting point is SPKI. SPKI has a very nice, clean syntax that's easy to work with in any programming language, very straightforward semantics, and supports constructions that anticipate the central ideas behind petnames and Zooko's Triangle. Unfortunately SPKI seems to be abandoned today; the feeling when I last looked at it was that despite their inadequacies, the victory of PKIX and X.509 was now inevitable and resistance was futile.

Well, it turns out that X.509 was so bad that no amount of industry support could turn it into the universal standard for key management applications. There are places that it will simply never be able to go, and in fact these are the vast majority of real crypto applications. On top of which, there is a limit to how far a standard that hardly anyone will ever understand the application of can go.

It's time we brought back SPKI. But more than that, it's time we adapted it for the times it finds itself in; take out the parts that complicate it unnecessarily or slow its adoption, extend it to do more than just PKI, and specify how it can talk to the existing broken cryptographic applications in as useful a way as possible. Once we've built a working petnames system to serve as a workable PKI, my current feeling is that we should start with no lesser a goal than replacing all of the standards listed above.

Does anyone else think this sounds like a good idea? What other way forward is there?

Comments

Re: Zooko's triangle

[hodja.livejournal.com]

Those are pre-v4 keys.

Re: Zooko's triangle

[hodja.livejournal.com]

You have just proved me right. Duplicating a 32-bit key ID requires just enough effort to keep casual attackers out. You have a small incentive to carry out the attack, you are able to do it, and yet, your judgement is that it's not worth the effort. I won. That's how good security works.
Consider this: If I only check the 32-bit ID, I'm very probably on the safe side. If two keys with the same 32-bit ID show up, I do some more expensive checks to figure out what's going on. Rational attackers know this, and realize that they probably won't achieve much by attacking the 32-bit ID, and since it takes considerable effort (one hour of computing time is good enough) they just won't do it.

I'm not taking multiple target attacks into account, because for most applications they don't make sense from an economic point of view. What if you manage to impersonate a random person in a very superficial way? How is it beneficial for the attacker? Remember that attacks are events which are harmful for the victim and beneficial to the attacker.

Also note that attacking the 64-bit ID is completely out of reach for most practical purposes.

Believe or not, I do unserstand Zooko's triangle and its implications: you can't have ID's which are globally unique, human memorable and self-authenticating at the same time, but you can have any two of these properties. But all that is about perfect security stuff. In practice, you can (and should!) make compromises: a 32-bit key ID is almost unique, difficult (but possible) to remember and provides a weak self-authentication.

Now, this is clearly not enough as the only security measure in place, but it is a perfect solution for your first line of defense. Since there can be additional security measures in place (third-party authentication, expensive checking of 64-bit or full 160-bit IDs, etc, etc, etc) it will be irrational for attackers to breach even this first line even though it is technically possible.

Think of banknotes. There is a multitude of security measures in place, but you check only the most superficial ones, because in theory you could check all the others too, so in practice you actually don't have to, because even the superficial ones take some effort to attack and it doesn't guarantee success. In a foreign coutry, you will probably gladly accept paper money that you have never seen before simply on the grounds that it looks like money that is expensive to counterfeit.

Re: Zooko's triangle

[ciphergoth.livejournal.com]

Um.

Clearly, your ideas on what constitutes cryptographic security are too radical for my convention-addled brain to comprehend. Let's just agree to differ on this one.

[akicif.livejournal.com]

Depends what you mean by a single large institution: I'm working on this, these days....

Re: Zooko's triangle

[hodja.livejournal.com]

Okay. Let's agree to disagree.

Re: Zooko's triangle

[hodja.livejournal.com]

Here's a variation of your idea that is more backwards compatible and, IMHO, more elegant:
You require that the most significant bits (25, following your example) of the public key y = g^x be 0. This, in itself, is a proof of work, as one needs to try approx. 2²⁴ x's in order to find such a y.

Re: Zooko's triangle

[ciphergoth.livejournal.com]

Interesting variant. I'd rather require that the 25 most significant bits of the hash of y be 0, because it's then trivial to prove in the random oracle model that there's no way of avoiding the work. My variant allows existing keys to have short IDs while yours requires new keys; your variant means that the proofs of ID are in the keys themselves while mine requires that you publish special extra information in order to attest to an ID.

Either variant is amenable to modification such that the "hashing" process is made memory-hungry in a way that frustrates attackers using parallel hardware.

[randwolf.livejournal.com]

[in passing. got here via (http://nielsenhayden.com/makinglight/archives/008703.html#173824)]

I wish your project the best, and wide adoption; please include me any future mailing list.

[grendelkhan.livejournal.com]

Not only does no one have DNSSEC, but there doesn't even exist (as of October 2004, according to djb (http://cr.yp.to/djbdns/forgery.html)) such a thing as DNSSEC; it's just a name that makes people feel better.

[ciphergoth.livejournal.com]

interesting - thanks! I didn't know that DJB was another petnamer.

[akicif.livejournal.com]

Have you seen this on WS-* stuff?

(It's probably pitched at totally the wrong level, but it got shown me as a good place to start disentangling the rope)