[bisq-network/proposals] Use of a third party to unlock the maker's trade reserve (#278)

Tue Nov 3 19:17:32 CET 2020

> _This is a Bisq Network proposal. Please familiarize yourself with the [submission and review process](https://docs.bisq.network/proposals.html)._

The Bisq app currently allows the user to encrypt their wallet with a password, which is stretched to a temporary AES key and used to encrypt their seed phrase and private keys, avoiding them being stored to disc in plaintext. However, since access is needed to the maker's wallet to fund trade deposits when they are away from their machine, it needs to be kept unlocked by holding the AES key in RAM throughout the lifetime of the Bisq instance, weakening the user's security.

We could improve things a little by only holding the unencrypted EC key of the trade reserve UXTO and forgetting the wallet AES key at rest, but that still puts some of the maker's funds at risk. It also does not interact well with https://github.com/bisq-network/proposals/issues/265, which would do away with the maker fee tx and would thus requires a bunch of EC keys to be held unencrypted (of some current wallet UXTOs and reserved change addresses), putting a potentially much larger pool of wallet funds at risk.

This proposal describes a way to hold a maker's EC key in an encrypted state, using a long term public key (say an RSA key) belonging to a third party server. When the time comes to sign a deposit tx + delayed payout tx when someone takes the maker's offer, the third party is used to authorise access to the required encrypted EC keys, conditional on what exactly is being signed. This isn't done by simply sending the EC key to the third party to decrypt, as that would give them custody over (some of) the user's funds, putting an inappropriate amount of trust in them. Instead, a special kind of secure 2-party computation is done which allows neither the maker's computer nor the third party direct access to the unencrypted EC key at any point, and so that they individually learn nothing about it.

Only collusion between a compromised maker's computer and the third party could expropriate the funds, with the third party on its own only having the power of veto. Moreover, when the maker returns to their computer they can unlock their wallet with their password as before, without involving the third party, thus they have strictly better security than before and retain full custody over their funds at all times.

### Details of a possible cryptographic scheme

To protect a given EC key _e_ when the maker is away from their machine, the wallet is first unlocked with their password to give direct unencrypted access to it. (The maker's computer is in a trusted state at this point.)

#### Initial EC key encryption

We take a fresh random number _e1_ from the field _GF(N)_ of integers modulo _N_, where _N_ is the secp256k1 elliptic curve order, and compute:

> e<sub>2</sub> = e - e<sub>1</sub>

_e1_ will be the (untrusted) maker's computer's EC key share and _e2_ will be the third party's EC key share, when the time comes to sign a tx. Note that individually they tell you nothing about _e_ and there is no interaction with the third party at this point.

We tag _e2_ with optional auxilliary data _D_, specifying any extra ad-hoc restrictions on the use of _e_ we may want the third party to enforce and optionally specifying the public key _P = e . G_ of the wallet address, where _G_ is the curve generator. This is then encrypted with the long term RSA public key _TP_pub_ of the third party, to give:

> f<sub>2</sub> = Encrypt<sub>TP_pub</sub>(e<sub>2</sub>||D)

It is important that the public key encryption done above is not malleable, so an appropriate MAC-based encryption mode with a nonce should be used, rather than direct RSA encryption. The wallet AES key and _e2_ are then forgotten, leaving behind the pair _(e1, f2)_ which are held on the (now untrusted) maker's computer to do the signing.

#### Authorised signing with the encrypted EC key

When the time comes to sign a message _m_, with Sha256 hash _z_, the maker's computer (say Alice) needs to compute the ECDSA signature _(r, s)_ where:

> s = (z + r * (e<sub>1</sub> + e<sub>2</sub>)) / k

and _r_ is the x-component of the curve point _R = k . G_, for some random nonce _k_. She will do this in collaboration with the third party (say Bob) as follows:

Alice chooses a random _k<sub>1</sub>_ in _GF(N)_ and sends _R<sub>1</sub> = k<sub>1</sub> . G_ to Bob, along with _m_, _f<sub>2</sub>_ and the private 2-vector:

> u<sup>T</sup> = (1 / k<sub>1</sub>, e<sub>1</sub> / k<sub>1</sub>)

to Bob, with the latter in an encrypted form to be described below.

Bob first of all decrypts f2 using his private RSA key _TP_priv_ as follows:

> e<sub>2</sub>||D = Decrypt<sub>TP_priv</sub>(f<sub>2</sub>)

and checks the message _m_ against the auxilliary data _D_ to make sure it is good to sign. Bob then chooses a random _k2_ in _GF(N)_ and computes _R = k2 . R1_ = k2 . k1 . G_ to give the x-component _r_. Thus we take the nonce _k_ of final signature _(r, s)_ to be _k1 * k2_, which neither Alice nor Bob know directly but instead have a multiplicative share of, like the additive shares they have of _e_. Bob also computes a private 2-vector:

> v<sup>T</sup> = ((z + r * e<sub>2</sub>) / k<sub>2</sub>, r / k<sub>2</sub>)

This is then combined with Alice's encrypted vector _u_ in a special way and sent back to Alice, along with _r_, who is then able to compute the inner product _uTv_. Now observe that:

> u<sup>T</sup>v = (z + r * e<sub>2</sub>) / (k<sub>1</sub> * k<sub>1</sub>) + r * e<sub>1</sub> / (k<sub>1</sub> * k<sub>2</sub>) = (z + r * (e<sub>1</sub> + e<sub>2</sub>)) / k = s

So the problem of jointly computing an ECDSA signature _(r, s)_ reduces to that of Alice and Bob securely computing an inner product of their respective private vectors _u_ and _v_ over a finite field. We describe an encoding scheme for doing this below.

Note that the above is intended to be secure in the semi-honest model. If Alice or Bob are actively subverting the protocol with maliciously chosen data, then a few extra minor steps need to be taken. For example Alice can easily trick Bob into helping her sign _m_ with _e + e'_ instead of _e_, for an arbitrary offset _e'_ of her choosing (although it's doubtful if she could exploit that). Likewise, Bob can exert some malicious influence over _r_ and need not choose _k2_ to be random, in the unmodified scheme as described, possibly leaking information about _e_ in the final signature.

#### Securely computing the inner product of two private vectors

Suppose that Alice has a private vector _u_ and Bob has a private vector _v_ over a large finite field. Then the task of securely computing the inner product _uTv_ can be seen as a generalisation of 1-out-of-n [oblivious transfer](https://en.wikipedia.org/wiki/Oblivious_transfer), where _n_ is dimension of the vectors. Indeed, Alice may set all but one of the components of her vector to zero, and the remaining component to some random secret. If Bob sets the components of his vector to secrets _v1_,...,_vn_, of which Alice is supposed to learn exactly one, then computing the inner product and revealing the result to both sides (or just Alice) obliviously transfers exactly one component _vi_ to Alice, of her choosing. Accordingly, we shall go the other way and attempt to build a secure 2-party inner product computation protocol from k-out-of-n oblivious transfer.

Concretely, take the 2-dimensional case as needed above. Fix a public 256 * 2 random matrix _A_ over the (256-bit) finite field _GF(N)_ of EC keys. This could be known in advance or a fresh matrix could be generated each time by Alice (say from a random seed) and sent to Bob, for slightly better security.

Take a [256,127,130] [Reed-Solomon](https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction) code _C_ over the finite field. Then there is a fixed linear dependency between any given 128 components of its 256-component codewords. That is, for any choice _S_ of 128 indices from the 256 available, there is exactly one 256-dimensional vector _f_, up to a scalar multiple, such that _f_ annihilates _C_ (i.e. _fTc = 0_ for every c in _C_) and _f_ has support S (i.e. the set of indices of nonzero components of _f_ is precisely _S_).

Now Alice makes a completely random choice of the set _S_ above and computes the corresponding vector _f_. Note that this choice has a little under 256 bits of entropy. The security of the scheme depends upon the following (hopefully quite mild) hardness assumption:

- For a _fixed_ random matrix _A_, known in advance by both parties, the 2-vector _A<sup>T</sup>f_ is computationally indistinguishable from a fresh pair of random numbers. That is, Bob would not be able to tell it apart from a totally random 2-vector.

Assuming both components of Alice's private vector _u_ are always nonzero, she may find a diagonal matrix _D_ such that:

> u = DA<sup>T</sup>f

and then send it to Bob, who won't be able to tell it apart from random or learn anything about _u_ from it.

Bob then takes a random codeword _c_ from _C_ and computes the 256-dimensional vector:

> d = ADv + c

Now by the properties of the Reed-Solomon code _C_, any 127 components of _d_ on their own will be indistinguishable from independent random variables, but adding a 128th component will start to leak information about _v_. So Bob obliviously transfers exactly 128 of the 256 components of _d_ to Alice, specified by Alice's secret choice _S_ of indices. This allows Alice to compute:

> f<sup>T</sup>d = (DA<sup>T</sup>f)<sup>T</sup>v + f<sup>T</sup>c = u<sup>T</sup>v

since the known components of _d_ exactly align with the nonzero components of _f_. Thus Alice learns the inner product _uTv_ and precisely no more information about _v_ from Bob.

Carrying out the oblivious transfer itself can be done basically by Alice sending 128 (EC or RSA) public encryption keys to Bob, along with 128 random decoys, such that it is provably impossible for Bob to tell the decoys apart from the actual keys and provably impossible for Bob to receive more than 128 keys from Alice without realising. (This can also be achieved using Reed-Solomon codes, plus some symmetric cryptography.) Bob then encrypts and sends the 256 components of _d_ back using the respective keys/decoys, but those encrypted with decoys will be completely unintelligible to Alice.

#### Cost estimate and comparison with other schemes

The entire 2-party authorisation and signing scheme for a given EC key & message, including the oblivious transfer step above, can be accomplished with a single round of communication between Alice (the maker's computer) and Bob (the third party), where Alice sends Bob some data, including the message to sign, Bob checks it, computes and sends some data back, then Alice is able to complete the calculation of the signature. The most expensive part of the computation and network use is the oblivious transfer, requiring 128 (say EC) key pair generations by Alice and 256 public key encryptions by Bob. I doubt that would take more than a second or two to compute. I estimate that with some optimisation using random seeds and random data elision, Alice would need to send Bob a little over 4 KiB and Bob would need to send Alice a little over 16 KiB to authorise signing with a single EC key - those estimates may however turn out to be out by a factor of two.

Realistically, half a dozen or so of the maker's encrypted EC keys may need to be signed with to start a trade (i.e. sign the deposit tx and delayed payout tx). It would be nice to extend the scheme above to support batch signing with different keys. I believe this can be done with only a small growth in the _total_ size of the data sent, by using bigger (i.e. > 2 dimensional) vectors and revealing multiple inner products of Bob's secret vector _v_ to Alice. So there should be a much smaller than linear growth in the bandwidth required with the number of EC keys used. Also, with the upgrade of the trade protocol to SegWit, the delayed payout tx should have input depending only on the unsigned deposit tx, so it should be possible to sign both in a single round of communication between Alice and Bob.

I found a couple of interesting papers describing similar 2-out-of-2 distributed ECDSA signing schemes: https://eprint.iacr.org/2018/499.pdf and https://eprint.iacr.org/2017/552.pdf. They both use multiplicative instead of additive shares _e1_ and _e2_ of _e_, that is they set _e = e1 * e2_, but that would make little high-level difference to our scheme.

The former also makes use of oblivious transfer and describes a scheme using a single round in the 2-out-of-2 case, like the above. (They also support 2-out-of-n signing and conveniently provide a Rust implementation.) The 2-out-of-2 case requires 169.8 KiB of communication and it's unclear if any savings could be made by batching. However, the main advantage over my scheme is a provable security reduction to standard EC assumptions, in contrast to the nonstandard hardness assumption made above (which needs to be suitably generalised to longer vectors in the batch signing case).

The scheme described in the latter paper uses Paillier homomorphic encryption to achieve very low total communication costs, at the expense of heavier computation and the extra security assumptions the Paillier encryption brings, although it's probably still fast enough for our purposes, taking perhaps seconds per EC key. However, it appears to require multiple communication rounds between Alice and Bob and it's also unclear to me if batching could be used to reduce costs.

### Optional storage of the delayed payout tx to prevent blackmail attacks

The basic scheme described above for protecting the maker's EC keys involves a completely stateless third party, with no communication prior to the actual signing required. While it should prevent outright theft of the funds, there is nothing the third party can do to prevent the compromised maker's computer from simply throwing away the delayed payout tx, where it is assumed that the hacker is colluding with the taker (or they are one and the same). This could open the maker to a blackmail attack when they finally regain control of their computer.

To prevent this, the third party could optionally store the delayed payout tx, pre-signed by the taker (but _not_ the maker, so the third party couldn't publish it himself). This would then be returned to the maker when he regains control of his computer. However, now the third party would no longer be stateless. (Although perhaps the delayed payout tx could be public key encrypted and stored by the third party in a mailbox on the P2P network, accessible only via the maker's password-derived AES key.)

### Optional use of a secure enclave by the third party

To further reduce the level of trust in the third party, and mainly to help prevent insider attacks, the cryptographic algorithm described above could be made to run in a secure enclave on the third party computer, perhaps using an Intel SGX enclave or a standalone HSM. The former has the advantage of providing some kind of remote + local attestation features (which I would need to look into further), possibly eliminating the need of a trusted admin to set up the enclave in the first place. It would also probably be much cheaper and easier to develop for. However, great care is required when writing the enclave code, to prevent cache-timing / SPECTRE-like attacks, and I don't suppose the enclave is completely impregnable because it's not running on a cryptoprocessor, but merely expensive to breach.

A standalone HSM would probably provide a much stronger enclave if it could be set up properly, but custom firmware might be required for that, which I guess would be rather expensive and difficult to write (perhaps requiring expensive SDK licenses). It could be a longer term option, however.

### Optional use of a custom third party server by the user

A power user could choose to run their own tx signing veto service, with a custom list of _TP_pub_ public keys provided to their Bisq instance, to tag and encrypt the EC keys of their trade reserve with. They could even run it on the same computer, as a daemon, as a separate user + group talking over localhost to Bisq. This would still provide good protection in case the attacker can't gain full root access. If the daemon detected the presence of SGX and then auto-enabled it's use, the user would gain almost as high a level of security as with the default third-party, but with possibly better privacy.

For this reason, I think it would be best to make the third party service executable as lightweight as possible, to minimise attack surface and so that an individual user could run it as a daemon on their own computer if they wished. Perhaps we could consider writing it in Rust or C++ instead of Java, especially since the cryptographic module would possibly be designed to run in an SGX enclave where it is available.

### Future integration of a second factor for more complete wallet protection

The threat model implicit in the above scheme is rather narrow, since it assumes the user's computer was in a good state when he first enters his wallet password and only later gets compromised, while he is waiting for an offer to be taken. It also assumes that he is somehow able to realise it was compromised (or the malware failed to persist itself) before he next enters his wallet password. More realistically I think, if an attacker gains access to the Bisq instance, he will try to plant persistent, silent malware. Or the Bisq binary would be tainted so that the app was compromised before it was even launched, perhaps before the wallet was even set up or encrypted.

So ideally the Bisq instance (on its own) would be considered untrustworthy from the moment the wallet seed is first (re)created and the user would use a second factor, either a hardware wallet or a smartphone, whenever any activity on their wallet requiring private keys needs to be authorised.

In the case of a hardware wallet, like a Trezor, instead of using it to directly hold funds, we would use its ability to sign human-readable messages which can be verified against tampering on the Trezor screen. The third party would then check the Trezor's signature to _itself_ authorise a particular use of a bunch of encrypted wallet EC keys held by the Bisq instance. This solves the major problem with hardware wallet integration which is that the Bisq instance can't fund a trade for a taken offer while the maker is away from his computer, since all wallet activity has to be authorised explicitly by the user via the hardware wallet.

In the case of a smartphone second factor, the user would scan a QR code which would show the activity being authorised on the smartphone screen. A 6 or 8 digit one-time numeric passcode, derived from a hash of the message and a smartphone-held secret, would be generated by the app which the user would then type into their Bisq instance. The message, encrypted secret, passcode and encrypted EC keys would be sent to the third party, who would then be able to check the passcode is valid against the message to complete the authorisation. This setup enables the smartphone to be used offline as a dedicated second factor, for extra security.

#### Initial seed phrase setup

To ensure the user retails full custody of their funds at all times, the entire Bisq wallet should continue to be derived from a seed phrase which is known only to them, so the wallet can be recreated in, say, Electrum or another Bisq installation at any time. However, the user's computer shouldn't be completely trusted at any point, when setting up a seed phrase in Bisq.

To solve this problem, we could follow something like Trezor's seed phrase recovery procedure: the Bisq instance learns the words of the phrase but not the order, while the second factor (say smartphone) learns the correct order of the words but not the words themselves. So neither device on its own can recover the seed phrase to unilaterally access the wallet. (At this point, we should probably use 24 rather than 12 word seed phrases for sufficient entropy.)

A secure 2-party computation is then done to derive the (_TP_pub_-encrypted) master private key of the wallet, which is then stored by the Bisq instance for all future wallet access. This would probably require a generic 2-party computation using [garbled circuits](https://en.wikipedia.org/wiki/Garbled_circuit), so it's likely to be quite a heavyweight operation, unlike the above cryptographic scheme, but would only need to be done once.

The 2-party computation is either done directly between the smartphone and the Bisq instance (which would require the former to be online) or it could be done between the third party and Bisq instance (following instructions on the smartphone screen) in such a way that the third party learns nothing - not even the order of the words since it shouldn't be necessary to tell that to them directly. A somewhat more elaborate and complicated-to-follow procedure could be similarly devised for the Trezor, I think, where the user would need to manually check the third party's public key against messages shown on the Trezor's screen (as I believe the Trezor can verify messages signed by others).

#### Threat model and security of the two factor scheme

We now have three entities: the user's smartphone or Trezor, their computer running the Bisq instance and the third party (which could later be extended to a network of servers). The wallet funds can be stolen if and only if either the first two devices are compromised or the last two devices are compromised. So this doesn't provide quite as good security as a hardware wallet but I think still quite good security, especially if the network of third party servers could later be made to use SGX or HSMs and perhaps even some threshold signing scheme.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/bisq-network/proposals/issues/278
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.bisq.network/pipermail/bisq-github/attachments/20201103/914a3d9a/attachment-0001.html>