# How should one implement a delegated shared trust protocol?

Consider the following (probably naive) scenario.

Alice, who is very limited in her knowledge of security in general (clueless about securing a private key for example), wishes to delegate certain contractual operations to Trent, an apparent trusted expert in that field.

However, Alice is rightly cautious and is of the opinion that Trent could be compromised (by Eve or Mallory) and so she asks Trent to provide a number of substitutes (Steve, Sam and Sarah) who can fulfil the same role as Trent (if he is away) and also make sure that Trent remains trustworthy (by observing his behaviour). Steve, Sam and Sarah cannot request to talk to Alice directly since all communication directly to her is through Trent.

Fortunately, Alice is protected by Walter, who she trusts completely, who is able to convert her simple password-like authorisation into a one-time only authorisation that Trent, Steve, Sam and Sarah can all see and verify.

From the above, it is apparent that in the normal situation when Alice requires a contract to be issued she provides Trent with the basic details, along with her authorisation via Walter. Trent creates and signs a contract on Alice's behalf (first problem) and then appeals to Steve, Sam or Sarah to counter-sign. Steve, Sam and Sarah all check Trent's public record of contracts to ensure that he is not exceeding agreed boundaries (second problem) and, after checking with Walter, sign if everything is OK. Once all signatures are in place then the contract is valid.

However, problems arise in the abnormal situations when Mallory enters the scene. Mallory may attempt to create a contract by taking Alice's authorisation and altering the provided details. Equally, since Trent is able to create arbitrary contracts, perhaps Mallory could create one that does not require Steve, Sam and Sarah to counter-sign but still appears to originate from Alice.

So my question is this: how can Alice ensure that her contracts can only be issued with her express permission without alteration, but still allow her to delegate the mechanics of this operation to others?

Please forgive the rather basic approach, I imagine that this scenario has been solved, but I'm not sure where I can find the details. Also, there are probably gaping holes which I would appreciate a more experienced eye pointing out.

It can be assumed that a contract requires a private key associated with Alice to enforce non-repudiation. However, if that private key could be hidden from both Trent and Mallory, perhaps by distributing it around Steve, Sam and Sarah that would be extra protection for Alice.

A real world example

The above is a rather generalised version of a problem that has arisen in the Bitcoin SE site (see http://bitcoin.stackexchange.com/q/517/117 for some interesting approaches) but has wider appeal than Bitcoin. However, using Bitcoin as a real world example may help clarifying some of the problems.

First, a quick overview of Bitcon. Bitcoin is a cryptocurrency that uses transactions to indicate a change in ownership of the underlying amount. It's not necessary to understand how this works, other than that a cryptographic signing protocol (elliptic curve DSA) is used to enforce non-repudiation. This signing protocol requires a public and private key.

So, to the problem. Given that Bitcoin is intended to provide a general-purpose replacement for cash it will be used by mainstream (non-technical) people - Alice in the above scenario. The vast majority of these people will want to delegate the security of their private key to someone who has put in place strong security measures, and use a password or OpenId type authentication and authorisation process (Walter).

Those people in charge of the private key (Trent) have the ability to create arbitrary transactions. Assuming those people are never compromised all is well. However, there have been many cases where servers have been hacked and keys stolen. As Bitcoin grows so that, for example, high value international trade with suitable escrow becomes a reality then the possibility for intimidation arises (force the owner of the escrow company to copy all the private keys across to Mallory). This is another attack vector to the private key. Since Bitcoin transactions are non-refundable, once the private key is lost all hope of retrieving the bitcoins is lost - it will be very hard for a legal system to help you recover the funds.

An approach to combat this is some form of shared trust protocol so that any single operator does not have full access to the private key. Instead a random group (or federation) of co-operating, largely trustworthy, operators can collaborate to construct the key and then use it. This protects each individual operator (the Trent's) from intimidation because they have no control so it's useless to expend effort compromising or intimidating them.

It might be possible to use oblivious transfer in some way, but I am not sufficiently versed in this area to comment.

-
Is that a tumbleweed I see before me? –  Gary Rowe Sep 22 '11 at 21:23
I could be wrong but, this sounds very much like a replay attack that could simply be resolved by adding a nonce to Alice's authorisation. A nonce is a one time (typically integer or timestamp) value that can prevent replay attacks. Is this a replay attack that you are referring to? –  user476 Sep 25 '11 at 3:22
@Bill It's more complex than that. Perhaps this related question on the Bitcoin site may shed more light on a problem that would benefit from this protocol: bitcoin.stackexchange.com/q/517/117 –  Gary Rowe Sep 25 '11 at 12:38
@Bill Thanks for your interest in this. I'm not sure your approach is quite on the mark. Assume I'm Alice (or Bob :-) ). I don't have any understanding of crypto at all, so I pay Trent to issue contracts on my behalf using a PKI, in my case Trent is using a combination of SHA-256 and elliptic curve DSA. Unfortunately, Trent gets hacked by Mallory and suddenly my private key is exploited. Disaster! How can I protect myself against this? Trent can't rely on me encrypting my private key with a password since Mallory simply roots the server and monitors cleartext memory. –  Gary Rowe Sep 25 '11 at 14:11
In light of the comments to my solution, you can see why I was reluctant to post an answer. Not that any answer is incorrect; this other author and I just happen to have an opposing opinion. I hope that you find an answer to your problem. Sincerely. –  user476 Sep 26 '11 at 3:55

I found the original question vague/ambiguous but the Bitcoin example is concrete enough to answer. In short, what you want is impossible without relaxing some of your requirements.

One of the many requirements you list is that Alice, essentially, has no signing power and can only perform password-based authentication. This is problematic for a fundamental reason. If $a_i$ is some authentication token (whatever it may be) and $m_i$ is her instructions or transaction, a corrupted Trent can always take $\{a_i,m_i\}$ and replace $m_i$ with $\hat{m}_i$ of his choosing.

There are only two ways to prevent this and both are more-or-less blocked by your requirements:

1. Alice has a secure channel to a trusted party (Steve/Sarah/Sam).
2. Alice applies her authentication token to the message: $\{m_i, \mathsf{f}_{a_i}(m_i)\}$. Maybe it is possible to use something weaker than a signature for $\mathsf{f}$ but essentially you want a digital signature (in this case, $a_i$ is a secret but a related value can be used to verify $\mathsf{f}_{a_i}(m_i)$).

Contra 1, you want all communication relayed through Trent. Contra 2, you seem to object to Alice being able to sign things, however I think there is some room in your scenario to play with this. It seems your main objection to Alice being able to sign things for herself is that she needs to keep a stored private key (e.g., $\mathtt{wallet.dat}$) secure.

However it is possible to derive a signing key from a password using a password-based key derivation function (PBKDF). So an alternative Bitcoin architecture could be password-based, where the signing key is derived from the password every time Alice has a transaction to sign. Niether the password nor the key from it is ever stored.

A drawback is if she forgets it, just like loosing your $\mathtt{wallet.dat}$, it is unrecoverable. Another drawback of using a password (whether to derive a signing key or to log into a service that has signing power) is that it will have less entropy than a randomly generated private key that is not meant to be memorized (just stored).

This is where maybe some distributed entity could come in. They could hold shares of the password to allow recoverability (however if they collude, they could recover it).

Finally, if you are still interested in delegation, observe that if Steve/Sarah/Sam are able to act in the absence of Trent, they have to have sufficient power to sign anything. Since they are never corrupted by the adversary in your threat model, the trivial solution is to cut out Trent from any power except relaying messages (the messages will have to be signed or have some end-to-end encryption for the reasons above). Steve/Sarah/Sam will be a distributed authority, where you trust that no more than a certain threshold $k$ will collude and no more than $\ell$ will be offline/non-responsive. You can then use secret sharing (for recovery) or threshold signatures (for delegating the signing) to set the appropriate number of shares required to perform the operation.

-
Thanks for a good answer. The reason that all communication goes through Trent is to allow him to build up a customer base and obtain an income from his efforts. Trent must have an incentive to act on Alice's behalf. Steve/Sarah/Sam are there to allow Alice to recover from an absence of Trent (either temporary or permanent). The general idea is that if enough substitutes are present then it is harder to attack the overall network. Finally, if Trent is the initiator, but not implementor, is there a way to ensure random selection of substitutes outside of Trent's control? –  Gary Rowe Sep 26 '11 at 15:06
Assuming all traffic goes through Trent, either Alice selects (and signs) a list of random substitutes, or you use the message itself (e.g., Alice's name) to select them. An example of the latter is a distributed hash table (DHT). (There are subtleties to using DHT securely. e.g., goo.gl/QqQln goo.gl/ThDlD ) –  PulpSpy Sep 26 '11 at 15:32

A quick search has found this wiki article, which suggests employing a trusted third-party certificate authority in a Public-Key Infrastructure responsible for verifying the identity of a user of the system and issuing a tamper resistant and non-spoofable digital certificate for participants.

Such certificates are signed data blocks stating that this public key belongs to that person, company or other entity. This approach also has weaknesses. For example, the certificate authority issuing the certificate must be trusted to have properly checked the identity of the key-holder, the correctness of the public key when it issues a certificate, and has made arrangements with all participants to check all certificates before protected communications can begin.

Note that in the (more recent) OpenPGP specification, (a variant of the PGP protocol), trust signatures can be used to support creation of certificate authorities, also. So, whether you use PKI or PGP, the responsibility of security then falls on the certificate authority. If this is compromised, then I suppose nobody can be trusted.

-
I've removed all the comments under this question as I don't think there was anything positive in the discussion taking place. Just a polite reminder to everyone to keep it constructive and on-topic please. –  Rhino Sep 26 '11 at 9:15