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

Go for PGP/MIME!

[hodja.livejournal.com]

I think, PGP/MIME is the way to go. It has a well-defined and quite interoperable way of signing metadata together with the document and OpenPGP trumps everything else in terms of flexibility when it comes to keys making assertions about other keys.
Yes, it's a heavy standard, but partial implementations work quite well. My suggestion would be to adopt OpenPGP for signatures and design something simpler for transport-level crypto. You are free to leave the Web of Trust out, too.

That's what I'd do, anyway.

P.S.: There are usable OpenPGP libraries around, but neither is good for all purposes. If you tell me more, I can give you recommendations what libraries to use. But even coding up OpenPGP from scratch (referring to RFC2440bis) is not that terribly difficult, if you leave out the functionality that you don't need.

Zooko's triangle

[hodja.livejournal.com]

Also, PGP key ID's are almost in the middle of Zooko's triangle. Short hashes are more secure in practice than most people think.

Re: Zooko's triangle

[ciphergoth.livejournal.com]

Do you mean PGP fingerprints? PGP fingerprints are the canonical example of one edge of Zooko's triangle: they are transferrable, securely unique, and free from global control, but they are not human-memorable. (Well, OK, you could memorize your own, but mostly people can't see one written on the side of a bus and go home and type it in accurately.)

If you do mean PGP key IDs, they are just 32 bits long. I can generate 2^32 DSS keys pretty rapidly and find the ID of them all to generate a key whose ID matches a particular target. If I only need to match any one of a thousand keys, my attack is a thousand times easier.

For a V3 key things are even worse: one may directly generate a key with a desired ID, because the ID is simply the low bits of the RSA public key.

The OpenPGP documentation (11.2) seems to talk about 64-bit IDs, which are obviously more work to attack but still within range. However, my own ID, 0x12F7E63D, is pretty definitely 32 bits, as are other examples I find online.

Even that doesn't fall under what we mean by "human memorable" in Zooko's triangle.

Re: Zooko's triangle

[hodja.livejournal.com]

I mean PGP key IDs, both long (64 bits) and short (32 bits). Even enumerating 2^32 keys takes considerable effort (try!). A 32-bit key ID is not more difficult to remember than a telephone number, although definitely more difficult than a domain name or an email address. If your system is well designed, a 32 bit key ID will be a securely transferable, self-authenticating (free from global control) and easy-to-remember identifier, albeit a little bit of a compromise an all accounts.

Also, the ability to generate keys with the same 32-bit identifier does not necessarily compromise the security of the whole system. There can be more than one security measure in place in such a way that none of them is critical by itself.

Remembering 64 bits is considerably more difficult. However, it is completely unfeasible to enumerate for the purposes of an attack excepting extreme cases when enormous resources can be marshalled for the purpose.

V3 keys are obsolete and should not be used. (Wow, you still use a V2 key!)

Your long key ID is 0x40034F5712F7E63D. Every PGP key has both a short and a long key ID and you can refer to either, depending on the security needs of the moment.

A good solution may be to use as many digits of the fingerprint (key IDs for V4 keys are just the tail of the fingerprint) as the user desires. Good security systems let their users make the decisions on security trade-offs.

Re: Zooko's triangle

[ciphergoth.livejournal.com]

Are you imagining an attacker who genereates a new DSS key from scratch for each trial? Enumerating DSS keys is cheaper than that.

Preparation:
(1) Choose group parameters p, q, g
(2) Choose a random x in 1 < x < q
(3) Find y = g^x
Loop:
(4) Hash the resulting key to see if it matches
(5) If it doesn't, set x <- x + 1, y <- gy and go back to step 4

There are also tricks you can do to enumerate many RSA keys rapidly but they aren't quite as simple.

With 64-bit IDs and a single target you're talking about something a little like the successful RC5-64 crack - but easier, since that was a good few years ago now. But remember that multiple targets makes it easier - if my goal is only to imitate any key in a population of a million, then the task is a million times easier. 32-bit IDs will probably take under a second. With 64-bit IDs and a target population of a million, I have to do 2^44 work to get a match, which is easily within the range of a lone, unfunded attacker.

So - 32-bit identifiers are only barely human-memorable and are miles from being securely unique, while 64-bit identifiers are neither human memorable nor securely unique.

I have no idea what your second paragraph is supposed to mean. And I giggle at your last sentence!

Re: Zooko's triangle

[ciphergoth.livejournal.com]

On the other hand, this gives me an interesting thought.

If you could force private keys to be expensive to generate, this attack wouldn't work. It might be interesting to have a special kind of private key, which was expensive to generate but that had a relatively short secure ID. You could do this by accompanying the key itself with a proof of work bound to the key; for example, the key could be

(hardkey *key* *nonce*)

such that H((hardkey *key* *nonce*)) matches H(*key*) in, say, the last 25 bits; these bits are not used in generating the key identifier. That shaves 25 bits off the minimum secure length of the identifier for the key. With such a scheme I can imagine reasonably secure identifiers which were, say, 20 letters long, noticeably more convenient to match than the 40 hex digits OpenPGP uses.

Re: Zooko's triangle

[hodja.livejournal.com]

Interesting idea, indeed. But I would go with 10-12 letters instead of 20. :-)

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.

Re: Zooko's triangle

[hodja.livejournal.com]

No, I'm not imagining dumb attackers, thank you very much. I do adhere to the Rational Attacker paradigm in my security analysis.

I know that enumerating DSS keys is relatively cheap. Moreover, there is an even simpler way of enumerating 2^32 OpenPGP keys of any kind, since the date of creation (which, is, by the, way unused by modern implementations -- they use the timestamp in the self-signature) is represented in 32 bits and hashed into the key ID. But just hashing 2^32 times roughly half a kilobyte is difficult enough to prevent most casual attacks.

FYI: the fast way of enumerating RSA keys is to make them asymmetric: one of the primes is chosen to be small. Thus, one trial implies one multiplication and one hashing (and a small prime sieve).

Your second assertion does not hold much water either. You're talking from the point of view of theoretical cryptography (where the goal is to make attacks computationally infeasible), whereas I am talking about practical security (where the goal is to make attacks economically unattractive). From your point of view, putting a lock on your front door doesn't make any sense, since affordable locks are easily picked and the door can be kicked down anyway. In reality, having a lock on your front door vastly increases your security, because it raises the costs sufficiently to keep casual attackers out. Sufficiently determined attackers will find their way in anyway. Yes, an 2^44 enumeration is within the range of a lone, unfunded attacker (albeit on the very far end of it), but he has better things to do with his resources than generating a key with the same ID as another random key for which he probably has no use whatsoever.

Thus, I hold on to my assessment of the security of 32 and 64 bit identifiers. I challenge you to generate a feasible-looking V4 PGP key with the same 32-bit ID as mine. It's 0x34F5BB91, as you can see from my user profile.

As for the second paragraph. There can be many additional security measures: the system can refuse to register keys with already taken 32-bit IDs, the system can provide facilities for verifying 64-bit IDs or even fingerprints, there can be some PKI-ish thing in place (WoT, CA hierarchy, whatever). And so on and so on.

Giggle all you want, but take look at the really successful security system. For instance, paper money. It has many security measures in place and it is up to the users to decide which ones are worth checking in every particular situation. Yes, there's some fraud in the system, but its overall security is sufficient to keep the economy afloat. The '90s ideal of unbreakable security for every joe (for free!) is just that: a pipe dream. It's time to get back to Earth.

Re: Zooko's triangle

[ciphergoth.livejournal.com]

(*) You don't have to hash the entire half a kilobyte - only the changing suffix

(*) You're still not taking multiple target attacks into account

(*) Even setting that aside, on my machine OpenSSL reports

Doing sha1 for 3s on 1024 size blocks: 693215 sha1's in 3.00s

By my sums, that suggests that it could do 2^32 trials in 2.58 hours. So finding a match for a single target will take around 78 minutes. If you have a thousand targets, it will take 4.64 seconds to find a match.

No, I don't plan to implement this attack unless you can find some very surprising reason to think that these sums aren't at least in the right order of magnitude.

It's clear from your answers in any case that you don't understand Zooko's triangle and its implications - please try to engage with that before you return.

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.

Re: Zooko's triangle

[hodja.livejournal.com]

Okay. Let's agree to disagree.

Re: Zooko's triangle

[trs80.ucc.asn.au (from livejournal.com)]

I see quite a few keys ending in 00000000 in my gpg keyring. So it must be pretty simple to generate a collision with a desired 32bit key fingerprint.

Re: Zooko's triangle

[hodja.livejournal.com]

Those are pre-v4 keys.

Re: Go for PGP/MIME!

[(Anonymous)]

Why go for PGP/MIME?

What in the above description gives anyone enough information to decide what to go for? Either you guys are sitting in a pub somewhere and have a whole bunch of shared but private info, or cyphergoth needs to sit down and write out the requirements.

"They need to sign things,..." is a clue, but it doesn't say enough to even imagine what the purpose is here.

Signing for what? Authentication? Authorisation? Receipting? Audit trail? Non-repudiation-blah-blah? Because you can?