new key-server abstraction for pfs

The key-server model used for textsecure is upload ~100 pre-keys to the key-server, then use a burn after reading approach to key fetching. This would be nice, but we cannot guarantee that every client will be connected after the server has given out, or had DOSed away, their 100 pre-keys.

Some mitigations that could help: 1) require that you authenticate yourself [presumably with your key] before you request pubkeys, and only send one key per user that is requested 2) request a client re-upload N keys after N keys have been consumed, I think ~50 should be good, and only keep ~100 unconsumed pre-keys on the server at a time 3) if you have not seen the client and thus cannot get more pre-keys, begin redistributing the burned keys with the assumption that two uses, while not optimal, is better than not allowing communication or reusing the last key only 4) you could also modify the ~100 and ~50, based on the frequency of connections that the server sees to prevent pre-key reuse. 5) some sort of rate-limiting could also help with DOS issues as well note: the textsecure method allows for the pre-key database to drop entries once they are used, but if you allow for 3) the keys can only be dropped once more are re-uploaded; meaning that they pre-key database will always have exactly ~100 entries. also, this should be done in a sane manner so that client and server can be kept in sync.

There is an issue that comes about with this method. The key-server needs a new index. Previously, I advocated using the key as the id, as it is mostly guaranteed to be unique. But with ~100 pre-keys, this fails; textsecure uses phone number ownership as its id, but this too fails for us. We could use one's email address, but this does not allow people to be covert. At its core, what we need is a system that ties a database id to the ownership of a secret. Thus I think we should use a challenge response protocol, that implements a standard crypto algorithm to verify that you own a particular secret.

Ids could either be first come first serve, or random, but they need a sizeable namespace. Continuing, we begin to get into an issue with Zooko's triangle < http://www.skyhunter.com/marcs/petnames/IntroPetNames.html >. For our key-server, ids need to be global and unique, thus they will never be memorable. Thus it will be best to allow for users to submit a petname to associate with their id, so that people could find their id on a keyserver.

Considering how to implement this, I think we should either increment through the id-space or allow the user to submit a nonce as their id; I prefer the second as it would allow a server to increase the id-space as necessary while still allowing backwards compatibility: an id first issued as 1f could be referenced as 1f, 01f, 001f, etc.

But we have a problem, if we have federated servers, as per https://github.com/winhowes/grd.me/issues/29, then we need global ids to be used. This removes the ability to use incremental ids, and honestly forces us to use crypto pubkeys as ids. This does solve the challenge response issue, as we can sign all uploads with our private key for authentication, and using a pubkey means the namespace is large enough that we will not need to worry about offline collisions. {Users a and b generate equal ids and talk to two different key-servers at "the same time", or while the two servers cannot talk. Then when they try to reconcile their databases they will have a collision. And I have NFC how to deal with a collision.}

tl;dr 1) we need a policy for pre-key upload, I have defined a few options; but we should stress test them to make sure they work 2) we need to redesign how the server handles the id field for this new type of key-server; again several options were discussed, but I feel like we should use the following: a) have a user generate a key-server only key that has no relation to the users encryption keys 1) this is effectively a nonce key b) upload a signed version of the public key as an id 1) signing proves ownership c) assign a petname/non-unique id to the key, so that others can find the real id when necessary d) upload ~100 pre-keys for pfs e) do more things based on 1) to keep pre-keys fresh and available

winhowes / grd.me

new key-server abstraction for pfs #30