technology from back to front

Squaring Zooko’s triangle

(Note: a more detailed explanation and justification can be found in Squaring Zooko’s Triangle, part two)

Zooko’s Triangle [old link: https://www.zooko.com/distnames.html ] encompasses the three properties you’d like a name to have:

  • secure given the name, you can securely find the person it belongs to in order to, say, check their cryptographic signature on an email
  • memorable you should be able to see a name on a poster, and recognise it later when you come to use it
  • decentralized there should be no central naming authority who can screw things up the way that ICANN/Verisign inevitably do

The thesis behind the triangle is that of these three desirable properties, you can have any two. If you’re not familiar with Zooko’s Triangle, Clay Shirky‘s essay is the clearest explanation (he independently rediscovered the same idea), and Marc Stiegler‘s essay on petnames illustrates it and discusses one solution.

In this essay I propose a kind of name which is entirely decentralized, reasonably secure, and at least somewhat memorable. They look like this:

Paul_Crowley:area-fluid-above-movie-start

The name is in two parts: the handle h (“Paul_Crowley”) and the tag t (“area-fluid-above-movie-start”). Associated with a particular name will be a public key k and a 32-bit nonce n. I can print the name on my business cards, and publish the key and nonce on my website, and you can securely verify using the nonce that the key belongs to the name.

The scheme is based on a fixed, globally shared word list. I got a possible list using the Beale list from Diceware, which is designed for a different but related purpose, and removing all the words that contained special characters; the resulting list contains 7322 words. To fill out the details on this scheme, we’ll also need to fix a hash function and an input encoding for the hash function; SHA-256 and SPKI-like S-expressions seem plausible choices.

Given a name h:t as above, a key k, and the nonce n as above, you verify the match as follows: hash three of these together to generate v = H((h, k, n)). Now verify that the last 23 bits of v are all zero. Finally, treat the first 65 bits as five groups of 13 bits, and use each group of 13 bits as an index into the word list; ensure the resulting 5 words match the five words in the tag.

To generate yourself a name, you’ll need a public key k and a handle h; you should choose a handle that you don’t think many other people will have chosen. Repeatedly try lots of random values for the nonce n until you find one which results in a hash which is zero in the last 23 bits, and for which each of the five groups of 13 bits yields an index small enough that it doesn’t point off the end of the word table (since they can yield 8192 different values but there are only 7322 words in the table). On a standard PC it should take about 10-20 seconds to find a suitable nonce. Of course, you may not like the resulting tag (“paulcrowley:hitch-marty-grail-mild-coot”) in which case you can keep searching for a nonce you like better.

It’s clear that this is decentralized, and you can assess the memorability for yourself; the example I’ve used is randomly generated, though I had a few goes to find one I liked. How is it for security?

Let’s suppose our attacker wants to pretend to be me. They must find a (h, k’, n’) such that H((h, k, n)) matches H((h, k’, n’)) in 88 bits: the 65 bits at the start that make up the tag, and the 23 zero bits at the end. Assuming there’s no way of exploiting some useful property of the hash function, this will take about 288 trials, far outside the reach of even the best-funded attacker.

Our attacker might like to avail themselves of a multiple-target attack (as I’ve described earlier). However, they can only simultanously attack all those with the same handle, which if you’ve chosen your handle well will be few.

This makes sacrifices on both the memorability and security fronts, but it’s the closest thing I’ve seen to something that achieves all three goals.

(Continued in Squaring Zooko’s Triangle, part two)

by
Paul Crowley
on
10/11/07
  1. Patroklos Argyroudis
    on 10/11/07 at 9:37 pm

    This is a very interesting proposal. The main idea behind it reminds me of Davida’s and Desmedt’s hash function based key establishment protocol:

    http://portal.acm.org/citation.cfm?id=111563.111572

    As it has been extensively investigated in the relevant literature, I don’t think that Zooko’s triangle can be fully satisfied without making some trade-offs. Proposals like this one should be analysed according to these trade-offs and compared based on the possible target application domains.

  2. Clay Shirky
    on 11/11/07 at 4:18 am

    I wrote “Domain Names: Memorable, Global, Non-political?” before I’d read Zooko’s work. I have referenced that work since.

  3. OK – have fixed that in the article. Do you happen to know which of you has priority? It might be good to add an addendum to your article clarifying the situation. Thanks!

    Sounds like one of you was right on the others heels with this one either way – clearly an idea whose time had come. I remember thinking of a fantastic way to use multiple-target attacks to break 3DES, and getting part-way through writing it up when I went to check my references… and discovered that the exact attack is presented in the original paper about multiple-target attacks, Aargh.

 
 


6 × three =

2000-14 LShift Ltd, 1st Floor, Hoxton Point, 6 Rufus Street, London, N1 6PE, UK+44 (0)20 7729 7060   Contact us